Blog - wingsico

前言

看到实验内容的时候,我的内心是拒绝的,因为在大一下学的线性代数实在是太差了,差点挂科了。所以关于矩阵啊行列式啊感觉是特别不熟悉的,但也没办法,我还是得好好掌握这些内容,在以后应该会十分有用。 实验开始前,特意先复习了一下矩阵的运算。

  1. 矩阵的逆置 $\begin{Bmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \7 & 8 & 9\end{Bmatrix}$ –逆置–> $ \begin{Bmatrix} 1 & 4 & 7 \ 2 & 5 & 8 \ 3 & 6 & 9 \end{Bmatrix} $ 具体也就是 第一行变成第一列,第二行变成第二列…以此类推。这种计算得到的结果与原矩阵行列数相等。

  2. 矩阵的加法 $\begin{Bmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \7 & 8 & 9\end{Bmatrix} $ + $\begin{Bmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \7 & 8 & 9\end{Bmatrix} $ = $\begin{Bmatrix} 2 & 4 & 6 \ 8 & 10 & 12 \14 & 16 & 18\end{Bmatrix} $ 对应位置的数值相加,并将结果放至同一位置。这种计算得到的结果与之前的两个矩阵的行列数相等,且该运算对加数与被加数有一个限制:

    加数矩阵与被加数矩阵的行列数必须一致
  1. 矩阵的乘法 $\begin{Bmatrix} 2 & 1 & 0 \ 0 & 0 & 3 \\end{Bmatrix} $ × $\begin{Bmatrix} 0 & 0 \0 & 0 \ 0 & 2\end{Bmatrix} $ = $\begin{Bmatrix} 0 & 0 \ 0 & 6\end{Bmatrix} $ 乘法稍微复杂一点,他的运算是第一个矩阵的每一行与第二个矩阵的每一列对应相乘并相加,得到的值放入第一个矩阵的行的标号作为结果的行标,第二个矩阵的列的标号作为结果的列标,放入结果矩阵对应的位置。 说的好难懂,还是把过程列一下

    1. 第一个矩阵的第一行与第二个矩阵的第一列相乘,得到的是结果矩阵[1][1]位置的值。

      Bmatrix[1][1] = 2 * 0 + 1 * 0 + 0 * 0 = 0
2.  第一个矩阵的第一行与第二个矩阵的第二列相乘,得到的是结果矩阵\[1\]\[2\]位置的值。

        Bmatrix[1][2] = 2 * 0 + 1 * 0 + 0 * 3 = 0


3.  第一个矩阵的第二行与第二个矩阵的第一列相乘,得到的是结果矩阵\[2\]\[1\]位置的值。

        Bmatrix[2][1] = 0 * 0 + 0 * 0 + 3 * 0 = 0


4.  第一个矩阵的第二行与第二个矩阵的第一列相乘,得到的是结果矩阵\[2\]\[1\]位置的值。


        Bmatrix[2][2] = 0 * 0 + 0 * 0 + 3 * 2 = 6


经过四步得到了结果矩阵的值,且得到的矩阵的结构与乘数矩阵和被乘数矩阵都不相同,但从运算过程中我们知道了他为何会不一样,那么如何快速判断得到的矩阵的行列数呢?

easy,用**第一个矩阵的行数**作为结果矩阵的行数,用**第二个矩阵的列数**作为结果矩阵的列数。

从上面的运算过程中我们还看到了,第一个矩阵的每一行是乘了第二个矩阵的所有列的,因此,如果第二个矩阵含有四列,那么第一个矩阵的每一行都要乘以第二个矩阵的所有列,也就是每一行会运算四次,这样得到的是结果矩阵的第一行的各个数值。这就是矩阵的乘法。

既然矩阵的相关知识我们都已了解,接下来就到实践的时候了,去实现一个矩阵!

矩阵的实现

一看矩阵这样有行列坐标定位数值的,我就想到了二位数组(当然别的我也想不出来了),于是,我们可以这样实现一个矩阵:

int Bmatrix[3][3] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

得到的矩阵:$ \left[ \begin{matrix} 1 & 2 & 3 \ 4 & 5 & 6 \ 7 & 8 & 9 \end{matrix} \right] $ 这样做十分的简单,对于逆置、加法、乘法这些东西两个for循环搞定。但是,过于简易带来的就是效率的低下,这样实现的这些操作,每个的时间复杂度 O(n, m) = n * m, 简直可怕,特别是零元特别多的时候,会执行很多不需要的操作,大大的浪费了时间。因此,这种方法是不可取的。 那么针对稀疏矩阵(非零元较少,零元很多的矩阵),我们该怎么做呢?

稀疏矩阵的三元组顺序表

稀疏矩阵是含有较少非零元的矩阵,对于这一类特殊的矩阵,我们应该压缩矩阵以减少使用的空间,那么如何压缩就成为了我们的待解决的问题。一般来说,对于矩阵的压缩我们有以下两种方法。

  1. 对于多个值相同的元使用同一存储空间
  2. 零元不占存储空间

对于对称矩阵三角矩阵之类重复的值较多的矩阵,我们可以使用第一种压缩方法,而对与稀疏矩阵,我们可以采用第二种压缩方法,这时候,就要用到我们上面说的三元组顺序表了。 根据压缩的概念,我们的三元组表内只存储非零元。其中,三元意味着有三个需要存储的值,分别是行序列序和它本身的值;代表着将一个非零元内各个值的存放在同一组内;顺序表代表着我们使用顺序存储结构来存储这些非零元。 为了更直观的了解何为三元组顺序表,我们举个例子: $$ \left[ \begin{matrix} 2 & 2 & 0 \ 0 & 0 & 6 \ 0 & 8 & 0 \end{matrix} \right] $$ 这里有一个矩阵,它含有较多的非零元,我们采用三元组表来进行压缩。我们按照行优先的规定,一行一行扫描,共得到四个非零元,分别是:

  1. 第一行第一列值为2
  2. 第二行第二列值为2
  3. 第二行第三列值为6
  4. 第三行第二列值为8

用三元组表即:

行(i)

列(j)

值(e)

0

0

0

0

1

1

1

2

2

1

2

2

3

2

3

6

4

3

2

8

注意到,我们的表格的下标为0的地方是不存放任何值的,其作用是为了更符合我们的直觉的一种表示法,第一个非零元放在序号为1的位置,因为在c语言中,序号是以0开始的,这样更符合平常的思考,当然,要是习惯了以0开始,也可以从0开始。 既然我们已经了解何为三元组,那么我们该如何用代码去表示呢?很简单,我们采用如下方法表示

// 非零元
class Triple {
public:
    int row; // 元素行标
    int col; // 元素列标
    int value; // 元素值
};

很容易知道,一个三元组可以唯一确定矩阵的一个非零元,因此,稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。 至于表结构,我们直接采用Triple类型的数组去存储:

const int maxsize = 100;
Triple sqList[maxsize + 1];

为了确定零元的个数和位置,我们需要指定矩阵的行列和非零元的格式,以方便后面的运算。因此,我们再创建一个矩阵类,用于存放矩阵的行列数和三元组以及非零元的个数。

class TsMatrix {
    static const int maxsize = 100;
public:
    int rows = 0; // 矩阵行数,默认为0
    int cols = 0; // 矩阵列数,默认为0
    int noneZeroNumber = 0; // 非零元个数,默认为0
    Triple sqList[maxsize + 1];
}

将这些数据置于public中,方便我们在外部对矩阵进行二元运算。 这里没有按照书上的一样使用结构体,而使用了C++的类,但其实效果是差不多的。 既然已经有了矩阵以及其三元组的表示,在进行运算之前,我们先要完成一个必要的步骤——矩阵的输入

矩阵的输入

如何输入一个矩阵呢,先思考,矩阵有哪些特征?

  1. 行数
  2. 列数
  3. 元素值
  4. 元素值对应的位置

因此,我们只要输入一个矩阵的行数和列数以及其非零元的三元组即可。 代码如下:

int initMatrix () {
    cout << "请输入矩阵的行数和列数: " << endl;
    cin >> rows >> cols;
    int preRow = 0, preCol = 0;
    while (true) {
        int row, col, value;
        cout << "请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): ";
        cin >> row >> col >> value;
        if (row && col && value) {
            if ((row > preRow || (row == preRow && col > preCol)) && isScope(row, col)) {
                noneZeroNumber++;
                preRow = row;
                preCol = col;
                sqList[noneZeroNumber] = {
                        row, col, value
                };
            } else {
                cout << "你的输入有误,请重新输入!" << endl;
            }
            if (preRow == rows && preCol == cols) {
                break; // 已经输完最后一个位置,自动结束
            }
            continue;
        }
        break;
    }
    return 0;
}

以上代码,有某些特别之处:

  1. 设置了preRowpreCol两个变量,用于存储上一个输入的三元组的行列值

  2. 不需要用户输入非零元的个数,可自行生成,简化了操作,降低出错率,输入0 0 0即可结束矩阵的输入

  3. 增加了矩阵输入三元组的校验,由于三元组是行优先的,因此后输入的三元组的行列值不应该比先输入的行列值更前,因此我们采用:

    if ((row > preRow || (row == preRow && col > preCol)) && isScope(row, col))
来判断其后输入的三元组的位置是否合法,其中`isScope()`的作用是判断输入三元组的行列值是否超出矩阵的行列数,也是对位置的校验。

    bool isScope(int row, int col) {
        return (row > 0 && row <= rows && col > 0 && col <= cols);
    }
  1. 若输入三元组合法,则加入三元组表中,同时非零元数自增,同时更新preRowpreCol的值

这样,我们就完成了一个矩阵的输入,当然,为了后续代码的验证,我们需要实时输出矩阵来检测我们代码的正确性,因此,我们还需要完成一个输出函数。

矩阵的输出

为了更加符合我们通常的阅读习惯,我给矩阵的输出进行了格式化,用到了头文件<iomanip>,按照三元组表进行输出,不在三元组表内的位置则输出0,代码如下:

int output () {
    cout << endl;
    int index = 1;
    for (int i = 1; i <= rows; i++) {
        cout << "| ";
        for (int j = 1; j <= cols; j++) {
            if (sqList[index].row == i && sqList[index].col == j) { // 判断是否为三元组表内的三元组
                cout << right << setw(3) << sqList[index].value << " "; // 右对齐格式化输出
                index++;
            } else {
                cout << right << setw(3) << 0 << " ";
            }
        }
        cout << "|" << endl;
    }
    cout << endl;
    return 0;
}

输入输出都完成了,就开始实现矩阵的运算吧~

矩阵的运算

转置

对于转置的方法我们在上面已经说过了,显然,一个稀疏矩阵的转置矩阵仍然是稀疏矩阵,分析原矩阵和转置矩阵之间的差异我们可以得出以下转置步骤

  1. 将矩阵的行列值相互交换
  2. 将每个三元组中的i和j相互交换
  3. 重排三元组之间的次序

前两步是很简单做到的,关键是第三步,我们给出如下一种方法: 按照转置矩阵中三元组的次序,依次在原矩阵中找到相应的三元组进行转置,即按照原矩阵的列序来进行转置。因此,我们在原矩阵内对每一列进行扫描,若扫描到三元组,则将其按先扫描到先放入的原则,放入转置矩阵的三元组表内。具体算法如下:

int transpose (TsMatrix &T) { // 矩阵的逆置
    T.cols = rows;
    T.rows = cols;
    T.noneZeroNumber = noneZeroNumber;
    if (T.noneZeroNumber) {
        int index = 1;
        for (int col = 1; col <= cols; col++) {
            for (int nz = 1; nz <= noneZeroNumber; nz++) {
                if (sqList[nz].col == col) {
                    T.sqList[index] = {
                        sqList[nz].col, sqList[nz].row, sqList[nz].value
                    };
                    index++;
                }
            }
        }
    }
    return 0;
}

很简单,没有复杂的逻辑。接下来看另一种运算——加法。

加法

矩阵的加法,原理以及限制上面已经说过了,还是先上代码,再来详细分析:

int add (TsMatrix T, TsMatrix &result) {
    if (!canAdd(T)) {
        cout << "矩阵结构有误,不能相加,请重新输入:" << endl;
        return -1;
    }
    result.rows = rows;
    result.cols = cols;
    Triple temp;
    int index = 1;
    int i = 1;
    if (noneZeroNumber && T.noneZeroNumber) {
        while (index <= noneZeroNumber && i <= T.noneZeroNumber) {
            if (isPrePosition(sqList[index], T.sqList[i])) {
                result.push(sqList[index]);
                index++;
            } else if (isSamePosition(sqList[index], T.sqList[i])) {
                temp = {
                    sqList[index].row, sqList[index].col, sqList[index].value + T.sqList[i].value
                };
                result.push(temp);
                index++;
                i++;
            } else {
                result.push(T.sqList[i]);
                i++;
            }
        }
        while (index <= noneZeroNumber) {
            result.push(sqList[index]);
            index++;
        }
        while (i <= T.noneZeroNumber) {
            result.push(T.sqList[i]);
            i++;
        }
    }
    return 0;
}

canAdd()是我定义的一个检测函数,检测两个相加的矩阵的行列值是否满足相加的条件

bool canAdd (TsMatrix T) {
    return T.rows == rows && T.cols == cols;
}

对于矩阵的加法,对于两个矩阵中的三元组,由于其三元组表均是行优先有序的,因此有如下几种情况:

  1. 被加数矩阵未完成运算的三元组在加数矩阵未完成运算的三元组之前
  2. 被加数矩阵未完成运算的三元组的位置与加数矩阵未完成运算的三元组位置相同
  3. 被加数矩阵三元组表的所有三元组均完成了运算,此时加数矩阵的三元组表还有三元组未完成运算。
  4. 加数矩阵三元组表的所有三元组均完成了运算,此时被加数矩阵的三元组表还有三元组未完成运算。

因此,我们需要分情况讨论: 对于第一种情况,我们只需要将被加数矩阵的三元组推入结果矩阵,并且记录被加数矩阵中已经完成运算的个数,由此可以得到下一个需要进行比较操作的三元组。 对于第二种情况,我们需要定义一个新的中间三元组,用来存放当前运算中的被加数矩阵三元组以及加数矩阵三元组的行列值以及值相加之后的结果,将其中间三元组推入结果矩阵,再记录被加数矩阵和加数矩阵以及完成运算的个数,由此可以得到两个矩阵中下一个需要进行比较的三元组。 对于第三、四种情况,我们只需要把剩下的三元组推入结果矩阵三元组表即可。 最后,最难的也就是乘法了。

乘法

在上面说的乘法算法中,不论乘数矩阵和被乘数矩阵中相对应的值是否为0,都要进行一次乘法运算,而实际上,这两者有一个值为0的时候,其乘积也为0,因此,在对稀疏矩阵进行匀速那时,应该免去这种无效操作,换句话说,为了求得结果矩阵中元素的值,只需要在被乘数矩阵M的三元组表M.sqlist和乘数矩阵N的三元组表N.sqlist中找到相应的各对元素(即M.sqlist中的colN.sqlist中的row相等的各对元素)相乘即可,为此,我们需要在N.sqlist中找到某一行的所有非零元,那么如何实现呢? 为了实现它,我们引入一个新的概念——带有行逻辑链接的三元组表。 如图: $$ \left[ \begin{matrix} 0 & 2 \ 1 & 0 \ -2 & 4 \ 0 & 0 \end{matrix} \right] $$ 对于这样一个矩阵,他的行逻辑链接为:

row

1

2

3

4

rpos[row]

1

2

3

5

行逻辑链接(rpos)是一个顺序表,存储着每一行的第一个非零元在三元组表中的第一个位置,根据它,我们不但可以获得每一行的第一个非零元在三元组表中的序号,也可以知道每一行最后一个非零元在三元组表的中的序号。在非最后一行中,我们只需要通过rpos[row+1]-1就能得到row行的最后一个元素在三元组表中的序号,在最后一行中,最后一个非零元在三元组表中的序号显然就等于非零元的个数了。 为了求得每个稀疏矩阵的行逻辑链接,我写了一个设置rpos的函数:

int setRpos () {
    int temp[rows + 1];
    for (int n = 0; n <= rows; n++) { // 初始化
        temp[n] = 0;
    }
    for (int i = 1; i <= noneZeroNumber; i++) {
        if (temp[sqList[i].row]) {
            continue;
        } else {
            temp[sqList[i].row] = i;
            rpos[sqList[i].row] = i;
        }
    }
    return 0;
}

这里利用了桶排序哈希表去重的思想,拟定一个数组,若其值存在则继续下一次的比较。 从前面的乘法的介绍我们知道,对于结果矩阵的某个元素,其值是一个累加的和,同时,两个稀疏矩阵的乘积不一定是稀疏矩阵,反之,即使两个矩阵的每个分量的值不为0,其累加值仍可能为0,因此结果矩阵中的元素是否为非零元,只有在求和得其累加和之后才能知道,因此我们先求和,再压缩。 大致步骤如下:

初始化结果矩阵Q;
if ( Q是非零矩阵 ) { // 逐行求积
    for (arow = 1; arow <= M[行数(rows)]; arow++) {
        ctemp[] = 0; // 累加器清零
        计算Q中第arow行的积并存入ctemp[]中;
        将ctemp[]中的非零元压缩存储到Q.sqlist中;
    }
}

具体算法如下:

int multiple (TsMatrix T, TsMatrix &result) {
    if (!canMultiple(T)) {
        cout << "矩阵结构有误,不能相乘,请重新输入:" << endl;
        return -1;
    }
    // 初始化
    result.rows = rows;
    result.cols = T.cols;
    result.noneZeroNumber = 0;
    int ctemp[T.cols + 1];
    if (rows * T.cols == 0) {
        return -1;
    }
    for (int arow = 1; arow <= rows; arow++) { // 处理被乘矩阵的每一行
        // 累加器清零
        int arow_end, rcol;
        for (int i = 1; i <= T.cols; i++) {
            ctemp[i] = 0;
        }
        if (arow < rows) {
            arow_end = rpos[arow + 1];
        } else {
            arow_end = noneZeroNumber + 1;
        }
        if (rpos[arow] > 0)
            for (int i = rpos[arow]; i < arow_end; i++) { // 对当前行每一个非零元
                int brow_end;
                int brow = sqList[i].col; // 找到对应元在乘数矩阵中的行号
                if (brow < T.rows) {
                    brow_end = T.rpos[brow + 1];
                } else {
                    brow_end = T.noneZeroNumber + 1;
                }
                if (T.rpos[brow] > 0)
                    for (int j = T.rpos[brow]; j < brow_end; j++) {
                        rcol = T.sqList[j].col; // 乘积元素在结果矩阵中的列号
                        ctemp[rcol] += sqList[i].value * T.sqList[j].value;
                    }
            }

        for (rcol = 1; rcol <= result.cols; rcol++) { // 压缩存储该行非零元
            if (ctemp[rcol]) {
                if (++result.noneZeroNumber > maxsize) {
                    return -1;
                }
                result.sqList[result.noneZeroNumber] = {arow, rcol, ctemp[rcol]};
            }
        }
    }
    result.setRpos();
    return 0;
}

这一段代码与书上大致相同,但对于我写的,书上的代码有错误,进行了长达几个小时的断点调试,找到了问题所在:当矩阵中某一行没有非零元时,rpos[arow]rpos[brow]的值为0,使其进入了循环并且参与运算,但当没有非零元的时候,是无需进行运算而直接置零的,因此,书上没有判断这两个情况,导致运行错误。我们要在用到这两个值之前加上两个判断:

if (rpos[arow] > 0)
...
if (T.rpos[brow] > 0)
...

大功告成,最后,为了更加方便的进行调试,我写了选择函数和面板函数作为菜单,进行运算。

int menu () {
    cout << endl << " **** Menu **** " << endl << endl;
    cout << "(1) 矩阵逆置. " << endl;
    cout << "(2) 矩阵相加. " << endl;
    cout << "(3) 矩阵相乘. " << endl;
    cout << "(0) Quit. " << endl << endl;
    return choose();
}

int choose () {
    int e = 0;
    cout << "请选择你要使用的功能: ";
    cin >> e;
    return e;
}

源代码

main.cpp

// main.cpp

#include <iostream>
#include <iomanip>
#include "TsMatrix.h"
using namespace std;

int choose ();
int menu ();

int main() {
    while (int i = menu()) {
        switch (i) {
            case 1: {
                cout << setw(15) << right << "矩阵的逆置" << endl;
                TsMatrix m, result;
                m.initMatrix();
                m.transpose(result);
                cout << endl << "****************" << endl;
                m.output();
                cout << "逆置 ——>" << endl;
                result.output();
                cout << "****************" << endl;
                break;
            }

            case 2: {
                cout << setw(15) << right << "矩阵的加法" << endl;
                TsMatrix Addend, Augend, result; // 加数,被加数
                cout << "第一个矩阵(被加数)" << endl;
                Augend.initMatrix();
                cout << "第二个矩阵(加数)" << endl;
                Addend.initMatrix();
                if (Augend.add(Addend, result) == -1) {
                    continue;
                };
                cout << endl << "****************" << endl;
                Augend.output();
                cout << "  +  " << endl;
                Addend.output();
                cout << "  =  " << endl;
                result.output();
                cout << "****************" << endl;
                break;
            }

            case 3: {
                cout << setw(15) << right << "矩阵的乘法" << endl;
                TsMatrix multiplier, Faciend, result; // 乘数矩阵,被乘数矩阵
                cout << "第一个矩阵(被乘数矩阵)" << endl;
                Faciend.initMatrix();
                cout << "第二个矩阵(乘数矩阵)" << endl;
                multiplier.initMatrix();
                if(Faciend.multiple(multiplier, result) == -1) {
                    continue;
                };
                cout << endl << "****************" << endl;
                Faciend.output();
                cout << "  ✖️  " << endl;
                multiplier.output();
                cout << "  =  " << endl;
                result.output();
                cout << "****************" << endl;
                break;
            }

            default: {
                cout << "输入有误,请重新输入!" << endl;
            }
        }
    }
    return 0;
}

int menu () {
    cout << endl << " **** Menu **** " << endl << endl;
    cout << "(1) 矩阵逆置. " << endl;
    cout << "(2) 矩阵相加. " << endl;
    cout << "(3) 矩阵相乘. " << endl;
    cout << "(0) Quit. " << endl << endl;
    return choose();
}

int choose () {
    int e = 0;
    cout << "请选择你要使用的功能: ";
    cin >> e;
    return e;
}

TsMatrix.h

// TsMatrix.h

//
// Created by wingsico on 2017/12/15.
//

#ifndef ARRAY_TSMATRIX_H_H
#define ARRAY_TSMATRIX_H_H

#include <iostream>
#include "Triple.h"
#include <iomanip>

using namespace std;
class TsMatrix {
    static const int maxsize = 100;
private:
    bool canAdd (TsMatrix T) {
        return T.rows == rows && T.cols == cols;
    }

    bool canMultiple (TsMatrix T) {
        return cols == T.rows;
    }

    bool isSamePosition (Triple m1, Triple m2) {
        return (m1.row == m2.row && m1.col == m2.col);
    }

    bool isPrePosition (Triple m1, Triple m2) { // 判断m1的排列位置是否在m2的前面
        return (m1.row < m2.row) || (m1.row == m2.row && m1.col < m2.col);
    }

    bool isScope(int row, int col) {
        return (row > 0 && row <= rows && col > 0 && col <= cols);
    }

public:
    int rows = 0; // 矩阵行数
    int cols = 0; // 矩阵列数
    int noneZeroNumber = 0; // 非零元个数
    int rpos[maxsize + 1]; // 各行第一个非零元的位置表
    Triple sqList[maxsize + 1];

    int initMatrix () {
        cout << "请输入矩阵的行数和列数: " << endl;
        cin >> rows >> cols;
        int preRow = 0, preCol = 0;
        while (true) {
            int row, col, value;
            cout << "请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): ";
            cin >> row >> col >> value;
            if (row && col && value) {
                if ((row > preRow || (row == preRow && col > preCol)) && isScope(row, col)) {
                    noneZeroNumber++;
                    preRow = row;
                    preCol = col;
                    sqList[noneZeroNumber] = {
                            row, col, value
                    };
                } else {
                    cout << "你的输入有误,请重新输入!" << endl;
                }
                if (preRow == rows && preCol == cols) {
                    break;
                }
                continue;
            }
            break;
        }
        setRpos();
        return 0;
    }

    int setRpos () {
        int temp[rows + 1];
        for (int n = 0; n <= rows; n++) { // 初始化
            temp[n] = 0;

        }
        for (int i = 1; i <= noneZeroNumber; i++) {
            if (temp[sqList[i].row]) {
                continue;
            } else {
                temp[sqList[i].row] = i;
                rpos[sqList[i].row] = i;
            }
        }
        return 0;
    }

    int transpose (TsMatrix &T) { // 矩阵的逆置
        T.cols = rows;
        T.rows = cols;
        T.noneZeroNumber = noneZeroNumber;
        if (T.noneZeroNumber) {
            int index = 1;
            for (int col = 1; col <= cols; col++) {
                for (int nz = 1; nz <= noneZeroNumber; nz++) {
                    if (sqList[nz].col == col) {
                        T.sqList[index] = {
                                sqList[nz].col, sqList[nz].row, sqList[nz].value
                        };
                        index++;
                    }
                }
            }
        }
        return 0;
    }

    int add (TsMatrix T, TsMatrix &result) {
        if (!canAdd(T)) {
            cout << "矩阵结构有误,不能相加,请重新输入:" << endl;
            return -1;
        }
        result.rows = rows;
        result.cols = cols;
        Triple temp;
        int index = 1;
        int i = 1;
        if (noneZeroNumber && T.noneZeroNumber) {
            while (index <= noneZeroNumber && i <= T.noneZeroNumber) {
                if (isPrePosition(sqList[index], T.sqList[i])) {
                    result.push(sqList[index]);
                    index++;
                } else if (isSamePosition(sqList[index], T.sqList[i])) {
                    temp = {
                            sqList[index].row, sqList[index].col, sqList[index].value + T.sqList[i].value
                    };
                    result.push(temp);
                    index++;
                    i++;
                } else {
                    result.push(T.sqList[i]);
                    i++;
                }
            }
            while (index <= noneZeroNumber) {
                result.push(sqList[index]);
                index++;
            }
            while (i <= T.noneZeroNumber) {
                result.push(T.sqList[i]);
                i++;
            }
        }
        return 0;
    }

    int multiple (TsMatrix T, TsMatrix &result) {
        if (!canMultiple(T)) {
            cout << "矩阵结构有误,不能相乘,请重新输入:" << endl;
            return -1;
        }
        // 初始化
        result.rows = rows;
        result.cols = T.cols;
        result.noneZeroNumber = 0;
        int ctemp[T.cols + 1];
        if (rows * T.cols == 0) {
            return -1;
        }
        for (int arow = 1; arow <= rows; arow++) { // 处理被乘矩阵的每一行
            // 累加器清零
            int arow_end, rcol;
            for (int i = 1; i <= T.cols; i++) {
                ctemp[i] = 0;
            }

//            result.rpos[arow] = result.noneZeroNumber + 1
            if (arow < rows) {
                arow_end = rpos[arow + 1];
            } else {
                arow_end = noneZeroNumber + 1;
            }
            if (rpos[arow] > 0)
                for (int i = rpos[arow]; i < arow_end; i++) {
                    int brow_end;
                    int brow = sqList[i].col;
                    if (brow < T.rows) {
                        brow_end = T.rpos[brow + 1];
                    } else {
                        brow_end = T.noneZeroNumber + 1;
                    }
                    if (T.rpos[brow] > 0)
                        for (int j = T.rpos[brow]; j < brow_end; j++) {
                            rcol = T.sqList[j].col;
                            ctemp[rcol] += sqList[i].value * T.sqList[j].value;
                        }
                }

            for (rcol = 1; rcol <= result.cols; rcol++) {
                if (ctemp[rcol]) {
                    if (++result.noneZeroNumber > maxsize) {
                        return -1;
                    }
                    result.sqList[result.noneZeroNumber] = {arow, rcol, ctemp[rcol]};
                }
            }
        }
        result.setRpos();
        return 0;
    }

    int push (Triple e) {
        sqList[++noneZeroNumber] = e;
        return 0;
    }

    int output () {
        cout << endl;
        int index = 1;
        for (int i = 1; i <= rows; i++) {
            cout << "| ";
            for (int j = 1; j <= cols; j++) {
                if (sqList[index].row == i && sqList[index].col == j) {
                    cout << right << setw(3) << sqList[index].value << " ";
                    index++;
                } else {
                    cout << right << setw(3) << 0 << " ";
                }
            }
            cout << "|" << endl;
        }
        cout << endl;
        return 0;
    }
};
#endif //ARRAY_TSMATRIX_H_H

Triple.h

//
// Created by wingsico on 2017/12/15.
//

#ifndef ARRAY_TRIPLE_H
#define ARRAY_TRIPLE_H
class Triple {
public:
    int row; // 元素行标
    int col; // 元素列标
    int value; // 元素值
};
#endif //ARRAY_TRIPLE_H

运行结果

/Users/wingsico/CLionProjects/array/cmake-build-debug/array

 **** Menu **** 

(1) 矩阵逆置. 
(2) 矩阵相加. 
(3) 矩阵相乘. 
(0) Quit. 

请选择你要使用的功能: 1
矩阵的逆置
请输入矩阵的行数和列数: 
3 3
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 1 1 2
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 1 2 1
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 2 2 1
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 2 3 3
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 3 2 2
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 3 1 2
你的输入有误,请重新输入!
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 3 3 3

****************

|   2   1   0 |
|   0   1   3 |
|   0   2   3 |

逆置 ——>

|   2   0   0 |
|   1   1   2 |
|   0   3   3 |

****************

 **** Menu **** 

(1) 矩阵逆置. 
(2) 矩阵相加. 
(3) 矩阵相乘. 
(0) Quit. 

请选择你要使用的功能: 2
矩阵的加法
第一个矩阵(被加数)
请输入矩阵的行数和列数: 
2 2
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 1 1 1
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 2 2 4
第二个矩阵(加数)
请输入矩阵的行数和列数: 
2 2
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 1 2 3
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 2 1 2
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 2 2 1

****************

|   1   0 |
|   0   4 |

  +  

|   0   3 |
|   2   1 |

  =  

|   1   3 |
|   2   5 |

****************

 **** Menu **** 

(1) 矩阵逆置. 
(2) 矩阵相加. 
(3) 矩阵相乘. 
(0) Quit. 

请选择你要使用的功能: 3
矩阵的乘法
第一个矩阵(被乘数矩阵)
请输入矩阵的行数和列数: 
3 4
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 1 1 2
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 1 2 1
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 2 3 3
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 3 1 2
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 3 3 3
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 3 4 5
第二个矩阵(乘数矩阵)
请输入矩阵的行数和列数: 
4 2
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 1 1 1
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 2 2 2
请输入该矩阵非零元的行、列位置以及值(输入[0 0 0]结束输入): 4 2 4

****************

|   2   1   0   0 |
|   0   0   3   0 |
|   2   0   3   5 |

  ✖️  

|   1   0 |
|   0   2 |
|   0   0 |
|   0   4 |

  =  

|   2   0 |
|   0   6 |
|   2  26 |

****************

 **** Menu **** 

(1) 矩阵逆置. 
(2) 矩阵相加. 
(3) 矩阵相乘. 
(0) Quit. 

请选择你要使用的功能: 0

Process finished with exit code 0

思考

在上面我们使用的转置算法是依靠双重循环完成的,其时间复杂度为O(cols * noneZeroNumber),即和原矩阵的列数以及非零元的个数的乘积成正比。对于一般的矩阵转置算法,时间复杂度为O(cols * rows),当非零元的个数与矩阵元素总数同一个数量级时,我们之前的算法的时间复杂度就为O(rows * cols^2)了,因此,上面的算法只适用于非零元较少的情况,那么我们如何改进矩阵转置算法,使得其在非零元较多的情况下也能快速完成运算呢? 如果能预先确定矩阵中每一列(即转置矩阵每一行)的第一个非零元在转置矩阵三元组表中应有的位置,那么在对原矩阵三元组表中的三元组一次作转置时,就能直接放到转置矩阵的三元组表中恰当的位置上去。 为了确定这些位置,在转置前,应该先求得每一列中非零元的个数,进而球的每一列的第一个非零元在转置矩阵三元组表中应有的位置。 因此,我们设置额外两个变量,用于存储每一列中非零元的个数以及每一列中第一个非零元在转置矩阵三元组表中恰当的位置。 显而易见的,如下的计算代码成立:

int cpot[maxsize + 1];
int num[maxsize + 1];
...

cpot[1] = 1;
cpot[col] = cpot[col - 1] + num[col - 1];

具体代码如下:

int fastTranspose (TsMatrix &result) {
    // 转置矩阵初始化
    result.cols = cols;
    result.rows = rows;
    result.noneZeroNumber = noneZeroNumber;

    if (result.noneZeroNumber) {
        int num[maxsize + 1] = {}; // 矩阵每一列中非零元的个数
        int cpot[maxsize + 1] = {}; // 矩阵每一列中第一个非零元在转置矩阵的三元组表中的位置

        for (int col = 1; col <= cols; col++) {
            num[col] = 0; // 非零元个数初始化
        }

        for (int n = 1; n <= noneZeroNumber; n++) {
            ++num[sqList[n].col]; // 每一列含非零元的个数
        }

        cpot[1] = 1; // 初始化列逻辑首位置,以1开始

        for (int col = 2; col <= cols; ++col) {
            cpot[col] = cpot[col - 1] + num[col - 1]; // 求矩阵中每一列非零元个数
        }

        for (int p = 1; p <= noneZeroNumber; p++) {
            int col = sqList[p].col;
            int q = cpot[col];

            result.sqList[q].row = sqList[p].col;
            result.sqList[q].col = sqList[p].row;
            result.sqList[q].value = sqList[p].value;

            ++cpot[col];
        }
    }
}

其空间复杂度为O(2(cols + noneZeroNumber)).

总结

这一次尝试了新的数据类型:class,第一次使用,很多东西还不了解,但感觉比结构体更加清晰,更加模块化,同时,我还尝试了写入头文件,也去了解了一些头文件的写法规则,感觉受益颇多。当写到矩阵的乘法,那个地方其实耗时特别久,用我那不成熟的调试调试了很多次,不过最终还是找到了错误的地方并解决了,还是挺开心的,再接再厉吧。

普通二叉树

对于普通的二叉树,假设n为总结点数,n0为度为0的结点(叶子结点)数,n1为度为1的结点数,n2为度为2的结点数。m为树的总度数。 有如下一般的数量关系

// 二叉树只含有度数为0,1,2的结点,因此总结点数等于他们的和
n = n0 + n1 + n2
// 无需解释吧,m为总度数
0 * n0 + 1 * n1 + 2 * n2 = m
// 除了根结点之外,每一个结点的上方都对应着一个度,因此总度数比总结点数少1
m = n - 1
// 综合上面的三个式子
n0 = n2 + 1

满二叉树

设深度为h,设n为总结点数,k为分支结点数,m为叶子结点数。 深度:树的最大层数; 叶子结点:度为0的结点; 分支结点:非叶子结点,即度不为零的结点。 则有如下的数量关系:

m = 2 ^ (h - 1);

n = 1 + 2 + 4 + … + 2 ^ (h - 1) = 2 ^ h - 1;

k = n - m = 2 ^ (h - 1) - 1;

k = m - 1;

n = 2m - 1;

n = 2k + 1;

栈这个东西,说简单也简单,就是一种数据结构,只是与顺序表,链表什么的不同,它遵循的是LIFO(后进先出)原则,阿这不是很简单么,只要时刻记住这一点就好了,只能从结构的一端进入和同一端出来就好了,这两个操作分别称为入栈出栈。可以把它比喻成一筒薯片,它是只有一边有盖子,称之为栈顶,它有一个金属的底部,防止薯片从底下漏出来了,称之为栈底。

## 基于栈结构的中缀表达式求值

栈这个东西,说简单也简单,就是一种数据结构,只是与顺序表,链表什么的不同,它遵循的是LIFO(后进先出)原则,阿这不是很简单么,只要时刻记住这一点就好了,只能从结构的一端进入和同一端出来就好了,这两个操作分别称为入栈出栈。可以把它比喻成一筒可比克薯片,它是只有一边有盖子,称之为栈顶,它有一个金属的底部,防止薯片从底下漏出来了,称之为栈底。如果底部破了,薯片从底部漏了出来,称之为栈下溢;如果薯片装的过满了从顶部溢出来掉地上了,称之为栈上溢。关于这两个概念应该很好理解,但是这不是今天的重点,暂且不理它。 关于栈的概念应该大致清楚了,因为标题的缘故我再稍稍提一下队列。队列很好理解,从字面意思上我们就好理解了,就像排队一样,比如坐火车前去自动取票机取票,你得等你前面的人取完票你才能取票,当然队列里的数据元素都是遵纪守法的好公民,不存在插队现象(特意去搜了一下,栈应该是不存在自身插队的问题的),这就是FIFO(先进先出)原则,队列在遵循这个原则产生了多种变种比如双端队列、链队列、循环队列等。诶又扯远了,现在就正式开始吧。

Thinking

本次应用实例是一个 基于栈结构的中缀表达式求值的一个程序,先不提实验本身,先搞清楚什么是中缀表达式,以及前缀和后缀表达式才是当务之急。 在表达式表示中,我们依照运算符相对运算数的位置不同,把这三个表达式分为:

  • 中缀表达式
  • 前缀表达式(波兰式)
  • 后缀表达式(逆波兰式)
中缀表达式

举例:

(3 + 4) * 5 - 6

概念:中缀表达式的运算符以中缀形式处于运算数的中间。

前缀表达式

举例:

- * + 3 4 5 6

概念:前缀表达式的运算符位于运算数之前。

后缀表达式

举例:

3 4 + 5 * 6 -

概念:后缀表达式的运算符位于运算数之间。 对于中缀表达式,不用过多的解释,这个是我们日常使用的表达方式,一眼就能看出答案为29。但是对于不了解的人来说,后面两个可能就不太看得懂了,其实,根据概念我们就可以大概猜出来了。由于加减乘除都是双运算数运算符,我们对于一个运算符要找出两个运算数与之搭配。先来看更简单易懂的后缀表达式(逆波兰式)求值,始终记住双运算数运算符

  1. 从左到右取出第一个运算符前两个运算数 3 4
  2. 取出该运算符 +
  3. 将两个运算数和运算符按照中缀表达式结合 3 + 4
  4. 将使用了的运算符和运算数去除,将得到的结果放回原表达式 7 5 * 6 -
  5. 重复1~4,扫描的起始位置更改为之前运算符+所在位置
  6. 直到表达式中运算符被使用完毕,最后的到的运算数就是最终的值 29

接下来看稍微复杂一点的前缀表达式(波兰式),由于部分复杂,我将采用图示法。

  1. 表达式从右向左扫描,遇到数字则把数字压入栈中,直到遇到非数字的运算符 +, 得到一个数字栈 3 4 5 6

示意图1-w400 2. 将栈顶元素出栈作为第一个运算数a a = 3, 再执行一次出栈操作拿到栈顶元素作为第二个运算数b b = 4,用~代表之前拿到的第一个运算符+,执行式子 a ~ b = 3 + 4 = 7 示意图2-w400 3. 将运算结果7再次压栈,将~ +丢弃,从之前+所在的位置继续向左扫描 示意图3-w400 4. 重复 1-3 步骤,直到扫描到最左边无运算符,停止运算,最后栈中剩下的数字就是求值的最后结果 29


通过我以上的描述,应该可以较明确的解释前缀、中缀、后缀表达式如何计算它们,下面给出一个更加复杂的前中后缀表达式,应该也很好计算。

中缀:1 + ( ( 2 + 3 ) × 4 ) - 5
前缀:- + 1 × + 2 3 4 5
后缀:1 2 3 + 4 × + 5 -

答案均为 16 经过上面的解释,不难看出,中缀和后缀表达式是比较好被计算机来解析并运算的,虽然人的大脑很容易理解与分析中缀表达式,但对计算机来说中缀表达式却是很复杂的,因此计算表达式的值时,通常需要先将中缀表达式转换为前缀或后缀表达式,然后再进行求值。 但是!我们先把转换表达式的方法放到最后来说,我们这里使用另一种简单直观、广为使用的方法来求解中缀表达式——算符优先算法

算符优先算法

什么是算符优先算法呢?简单来说:

算符优先算法是根据运算优先关系的规定来实现对表达式的编译或解释执行的

举个例子,我们从小学就学过了四则运算的规则:

1. 先乘除后加减
2. 从左算到右
3. 先算括号内再算括号外

所以对于以下式子,我们可以很快给出计算顺序然后得出正确的答案:

4 + 2 * 3 - 10 / 5

(1) 4 + 2 * 3 - 10 / 5
(2) 2 * 3 = 6
(3) 4 + 6 - 10 / 5
(4) 10 - 10 / 5
(5) 10 / 5 = 2
(6) 10 - 2
(7) 8

为了下面更好的理解一些术语词,先放上一段术语介绍: -- 任何一个表达式都是由操作数、运算符和界限符组成的,我们称它们为单词。一般地,操作数既可以是常数也可以是被说明为变量或常量标识符;运算符可以分为算术运算符、关系运算符和逻辑运算符3类;基本界限符有左右括号和表达式结束符等等。 我们把运算符和界限符统称为算符,它们构成的集合命名为OP -- 很容易看出,像 + - * / 为运算符, # ( ) 为界限符(#为表达式结束符),则OP为这样一个集合

['+', '-', '*', '/', '(', ')', '#']

那么我们如何让计算机在运算中判断两个相继出现的算符ß1和ß2之间的优先关系呢? 通过算符优先级表运算优先级表 PS: 纵轴符号为运算符ß1,横轴符号为运算符ß2 ß1 代表运算符栈顶元素,ß2 代表输入的算符 > 代表ß1优先级高于ß2 = 代表ß1优先级等于ß2 < 代表ß1优先级低于ß2 可以看到,表中有内容为空的单元格,这是因为表达式中不允许他们相继出现,一旦有这种情况,我们可以把它当作出现了错误的表达式,在下面的讨论中我们假定所输入的表达式不会出现语法错误,关于这个表的具体使用方法,我们在下面的讨论中会提到。 磨刀不误砍柴功,在我们正式开始编码之前,举出一些问题并想到解决办法会让我们的编程思路更加清晰。

  • 如何读取输入的中缀表达式
  • 如何实现算符优先算法
    • 如何寄存运算数和运算符
    • 如何使用算符优先级表判断运算符优先级
    • 如何实现多位数字和小数的存储
    • 如何判断输入的字符是否为数字

有一些问题需要随着我们深入编码才会逐渐浮现出来,所以在下面再提出并解决吧~现在,就来正式开始编码之旅

Coding!!

先来解决上面已经列出来的问题吧!

如何读取输入的中缀表达式?

针对这个问题,书上给出了一种方式,使用getchar(),一开始我也确实是使用这种方法的,但后面暴露了一些问题:

  • 每次只能读取一位字符,比如输入10只能分开读取为1,0,导致难以判断是多位数字还是个位数字
  • 还有一个问题到后面再提,这里先mark一下

于是我放弃了使用getchar(),决定使用一个字符数组来存储我所输入的中缀表达式,初始代码如下:

int main() {
    char express[STACK_INIT_SIZE]; // 存储中缀表达式
    int result; // 存储运算结果
    cout << "输入中缀运算式: ";
    cin >> express; // 直接用cin读取中缀表达式
    result = MidExpression_Eval(express); // 这是定义的解析中缀表达式的函数
    cout << express << '=' << result << endl; // 输出等式
    return 0;
}

上面的STACK_INIT_SIZE是我一开始在程序头部定义的一个常数:

const int STACK_INIT_SIZE = 100;

用途除了初始化存储中缀表达式的数组的内存空间、还用于初始化栈,会在下面说到。 针对这个问题,以上代码其实很明显的暴露了一些问题:

  • 运算中免不了有除法,所以会出现有小数的情况
  • 每次输入运算符都要自己手动在末尾加入运算结束符#,很麻烦
  • 在输出等式的时候,会将运算结束符也输出,即会出现1+3*2/5#=2.2的情况

解决方法很简单:

  1. int result 写成 float result,实在不放心还能写成 double result

  2. 在输入的时候不输入 #,在代码中将 # 添加到字符数组的最后面

    ...
    express[strlen(express)] = '#'; // 一定要放在下一句的前面
    result = MidExpression_Eval(express);
`strlen()` 的功能就是返回数组内实际所占的长度,不记录`\0`,这里 就不过多的描述了。 举个例子就明白了:

    char test[100] = {'2', '+', '3', '*', '4'};
    cout << strlen(test); // 5
    test[strlen(test)] = '#' // 相当于 test[5] = '#'
    cout << test; // 2+3*4#
  1. 通过上面的方法,我们免去了输入中缀表达式的结束符#,但是我们实际上express的内容仍带有 #,所以,我们在输出等式之前,可以先把结束符去除:

    result = MidExpression_Eval(express);
    express[strlen(express) - 1] = '\0'; // 必须放在上面那个式子的后面
    cout << express << '=' << result << endl;
解释一下,由于在解决2里面将 `#` 加了express内,会使`expresss` 的长度增加1,也就是`strlen(express)` 的值会比原来大1,因此 `#` 的位置就在 `express[strlen(express) - 1]`,把这个位置的字符替换成 `\0`,因为 `cout` 在输出字符数组的时候会截止于 `\0`

三个问题都解决了,最后代码清单:

int main() {
    char express[STACK_INIT_SIZE]; // 存储中缀表达式
    float result;
    cout << "输入中缀运算式: ";
    cin >> express;
    express[strlen(express)] = '#';
    result = MidExpression_Eval(express);
    express[strlen(express) - 1] = '\0';
    cout << express << '=' << result << endl;
    return 0;
}

但是这样真的好了吗? (😏笑) 其实上面还有一个问题,暂时还没有暴露出来。在这里就提前说了吧! 注意到我们的中缀表达式字符数组只是定义了但没有初始化,一开始我也觉得应该没有什么问题,但直到我把所有程序完成执行输出的时候这个问题才暴露了出来: cout << express 并没有在预期的位置(设置’\0’的地方)停止输出,而是在后面的一些的位置停止,导致输出了一些乱码。这是为什么呢? 在数组初始化之前,数组里的每一个数据单元的内容都是不确定的,如果我们不进行初始化的话,就会导致数组未赋值的区域内容不确定,就有可能出现上述情况,因此,我们做出一个改进,即初始化express数组:

char express[STACK_INIT_SIZE] = {};

这样就解决了不在预期停止输出的bug。 好了,接下去下一个大问题。


如何实现算符优先算法

算法思想

  1. 首先置运算数栈为空栈,表达式起始符 # 作为运算符栈的栈底元素
  2. 依次读入表达式中的每一个字符,若是运算数则进运算数栈,若是运算符则和运算符栈中的栈顶运算符比较优先级后作相应操作,直至整个表达式求值完毕(即运算符栈的栈顶元素和当前读入的字符均为 #

如何寄存运算符和运算数

我的自我对算符优先的认识(没有具体考证,待指正。): 算符优先算法的求解过程跟后缀表达式求值过程十分相似,均是使用 压栈_, _入栈_, _栈外运算 等操作完成的。 因此,我们需要使用 来存储我们的运算数运算符,因此我们需要声明、定义和初始化栈,版本1的代码如下:

typedef struct Sqstack
{
  char *base, *top; // 栈顶和栈底指针
  int stacksize; // 栈的内存大小
} Sqstack0, Sqstack1; // 运算数栈1 / 运算符栈0

...
// 在某个函数内
Sqstack0 OPTR; // 运算符栈
Sqstack1 OPND; // 运算数栈

只声明了一个栈类型,但定义了两个结构体变量,分别用来存储运算数和运算符,这样做有一个好处:

  • 只需要写一个初始化栈、入栈、出栈、获取栈顶元素函数

但是相比于它所带来的缺点,这个优点可以忽略了:

  • 运算符和运算数都用同一个类型的栈,其内部的指针均为字符类型,对于运算数会产生许多麻烦的事情,比如:
    • 对于多位数字,无法存入数字类型,且作为字符也只能一个个存,且转换成数字很麻烦
    • 从运算数数栈中取出的是字符,无法直接参与运算

解决方案: 使用两个不同的栈分别存储运算数和运算符:

typedef struct /* 运算符栈 */
{
    char *base, *top;
    int stacksize;
} SqStack;

typedef struct /* 运算数栈 */
{
    int *base, *top;
    int stacksize;
} SqStack1;

上面对于不同的栈指定了不同的指针类型,但运算数栈的指针类型真的正确吗?想一想看,这个栈是用来寄存运算数的,而在运算过程中可能会产生浮点类型的数字,因此我们要改成:

typedef struct /* 运算数栈 */
{
    float *base, *top;
    int stacksize;
} SqStack1;

如何判断一个字符是否为数字

答: ASCII码 众所周知,字符在内部是以 ASCII码 来存储的,数字0~9都是使用连续的 ASCII码 表示的,且有一个更重要的是,字符之间是可以比较大小的,比较的就是 ASCII码 的大小,因此,我们可以据此实现判断一个字符是否为数字的方法:

bool isNumber(char c) {
    return (c >= '0' && c <= '9'); // 是数字返回 true,不是则返回 false
}

如何实现多位数字以及小数的存储

来看一个式子:

6 + 12 * 3 / 9 // 10

按照我们的算法思想,首先先使用上面写的 isNumber(char c) 函数,判断该字符是否为一个数字,如果是,我们需要先把它转换成真正的数字,比如说第一个遇到了字符 '6',我们可以这样把它转换成数字:

...
int num;
num = c - '0'; // num 为 6

记住,字符也是可以进行运算的(用ASCII码),查 ASCII码表 就可以知道,字符 '6'ASCII码 为 64,'0'ASCII码 为 48,则两个字符相减刚好为数字 6, 这样就将字符转换成了数字。 但是,当我们遇到 12 的时候又会出现什么问题呢,12 会被拆分成 '1', '2',如果我们不经过任何处理就压入运算数栈的话是会出问题的,那么该如何解决呢?代码如下:

...
i = 0
theChar = express[i]; // 拿到表达式的第一个值
while (theChar != '#' || GetTop(Op_char) != '#') { // 判断表达式是否结束
    char numbers[20]; // 用于存储多位数字
    int j = 0; // 用于存储数字数组下标,方便增加位数, 同时也可以记录数字数组的长度
    while (isNumber(theChar)) { // 若是数字,则循环读取
        numbers[j] = theChar;
        i++;
        j++;
        theChar = express[i];
    }

    if (j > 0) { // 若数字数组长度大于0,则循环数组求多位数字的值并压入运算数栈
        float sum = 0;
        for (int k = 0; k < j; k++) {
            sum += (numbers[k] - '0') * pow(10, j - 1 - k); // 将字符转换成对应的数字
        }
        Push1(Op_float, sum);
    }  else { ... }; // 若不是数字则执行else里的操作
}

关于除了处理多位数字的代码,上面都有详细的注释,这里着重解释多位数字的存储。 首先我们定义了字符数组,分配了20个内存单元,因为我们读入的数字不管是 int类型还是 float 类型进行四则运算一般不超过这个长度;同时,使用一个变量 j 来存储数字数组下标,方便增加位数, 同时也可以记录数字数组的长度,还能通过判断是否为0来辨别是运算数还是运算符。 若扫描到某一位为数字,不会直接将其压入运算符栈中,而是会继续获取下一位,直到获取到非数字时,while 才会跳出循环,进行数字位数(j)的判断。若是多位数字,则循环遍历存储着多位数字的数组 numbers[],将其转换成真正的数字。 for 循环里面的那句语句如何理解呢?举个例子,假设:

char numbers[20] = {'1', '2', '3'}

我们知道这是一个三位数字,值为123,那么如何根据其下标转换成数字呢? 我们上面提到了如何将单个字符转换成单个数字,所以 numbers[k] - '0'就很好理解,pow() 函数是一个求次方的函数, pow(10, 2) 是求10的二次方,观察我假设的这个字符数组,我们可以获得三个信息:

  1. 长度j为3
  2. 对应下标k为 0, 1, 2
  3. 值为 123

其次,123 可以拆分成 1 * 10^2 + 2 * 10^1 + 3 * 10^0,所以答案一目了然,10 的幂可以由公式 j - k - 1(数组长度 - 当前数字字符下标 - 1)求出, 所以转换公式为

(numbers[k] - '0') * pow(10, j - 1 - k)

运算结束后,将累加得到的数字 sum 压入运算数栈,大功告成。 且慢,如果数字是小数怎么办?同样的思路,我们来将之前的代码改进一下:

i = 0
theChar = express[i]; // 拿到表达式的第一个值
while (theChar != '#' || GetTop(Op_char) != '#') {
    char numbers[10]; // 用于存储多位数字
    int j = 0; // 用于存储数字数组下标,方便增加位数, 同时也可以记录数字数组的长度
    while (isNumber(theChar) || theChar == '.') { // 若是数字或小数点,则循环读取
        numbers[j] = theChar;
        i++;
        j++;
        theChar = express[i];
    }

    if (j > 0) { // 若数字数组长度大于0,则循环数组求多位数字的值并压入运算数栈
        float sum = 0;
        int dot = getIndex(numbers, '.'); // 若无小数点则返回-1
        for (int k = 0; k < j; k++) {
            if (numbers[k] == '.') {
                continue;
            }
            if (dot != -1) {
                if (k < dot) {
                    sum += (numbers[k] - '0') * pow(10, j - 1 - k - dot - 1); // 将字符转换成对应的多位数字
                } else if (k > dot) { // 若没有小数点,这个块不执行
                    sum += (numbers[k] - '0') * pow(10, dot - k);
                }
            } else {
                sum += (numbers[k] - '0') * pow(10, j - 1 - k);
            }

        }
        Push1(Op_float, sum);
    } else {...} // 若不是数字则执行else里的操作
}

小数转换的思路就不多说了,和上面是一样的,用小数点所在的位置减去小数点后面的数字的位置得到的就是其10的幂的值。 但是,这里面还是有一些要小心的陷阱:

  • j 会因为含有小数点而增加长度,因此不能再使用 j - 1 - k 来确定整数部分乘以10的幂的值了, 应该将长度j减去小数点占的一个元素再减去小数点所在的下标dot
  • 区分小数点前后的转换规则,若 k < dot 执行整数部分转换, 若 k > dot 执行小数部分转换

除此之外,里面增加了一个新的函数 getIndex(numbers, '.'),是为了寻找小数点,找到了则返回小数点的下标,没有找到则返回 -1,根据下标是否等于 -1 判断是否是一个小数。来看这个函数的内部实现:

int getIndex(char ops[], char e) {
    for (int i = 0; i < 7; i++) {
        if (e == ops[i]) {
            return i;
        }
    }
    return -1;
}

ok,这个问题也解决了,下面解决最让人疑惑的部分。


如何使用算符优先级表判断运算符优先级

算符优先级表我之前已经给出了,对于这样一个表,第一反应就是将它转换成二维数组,行代表输入的字符,列代表运算符栈顶元素:

const char priority[7][7] = {
        {'>', '>', '<', '<', '<', '>', '>'}, // +
        {'>', '>', '<', '<', '<', '>', '>'}, // -
        {'>', '>', '>', '>', '<', '>', '>'}, // *
        {'>', '>', '>', '>', '<', '>', '>'}, // /
        {'<', '<', '<', '<', '<', '=', ' '}, // (
        {'>', '>', '>', '>', ' ', '>', '>'}, // )
        {'<', '<', '<', '<', '<', ' ', '='}  // #
};

对于这张表,我们需要做什么呢,在上面介绍这张表的时候,已经给出了一些关于 '>', '=', '<' 的具体含义,我们要做的就是根据输入的字符运算符栈顶元素来从这张表中获取它们的优先级比较。 具体做法: 我们先创建一个运算符全集数组,用来对应优先级表的第一行和第一列的元素符元素(看之前的那张图):

// 与比较符号优先级二维数组对应的操作符全集
char OP[] = {'+', '-', '*', '/', '(', ')', '#'};

有了这个,我们只需要找出输入的字符在这个数组中对应的下标 i以及运算符栈顶元素在这个数组中对应的下标 j,就可以通过

priority[i][j]

来获取 运算符栈顶元素输入的算符 之间的优先关系。用一个十分精简的函数 Precede 实现获取其优先关系:

char Precede(char top, char c) {
    // top 为运算符栈顶元素,c为输入的算符
    return priority[getIndex(OP, top)][getIndex(OP, c)];
}

其中使用了 getIndex() 辅助函数。 这个函数我们有三个可能的返回值:

  • < 栈顶元素优先级低,将输入的算符压入运算符栈,因为栈的LIFO原则,越靠近栈顶的元素会有更高的优先级去进行运算,之后继续读取下一个字符。

  • = 优先级相等,除了 '#''#'之间,就只有 '('')'了,但是 '#' 是不可能出现在这一层函数的,它会在最外部的 while 循环中判断。所以这里的作用就是将运算符栈处于栈顶位置的 '('脱去,并读取下一个字符,以便其他算符的运算

  • ‘>’ 栈顶元素优先级高,将优先处理栈顶元素:将运算符栈顶元素取出,同时取出两次运算数栈顶元素,将其组合成中缀表达式进行运算,将运算结果再重新压入运算数栈内,达到优先运算的预期要求(此时无需读取下一个字符,因为输入的字符还未使用)

实现的代码如下:

switch (Precede(GetTop(Op_char), theChar)) {
    case '<': // 栈顶元素优先级比此时的取值更低
        Push(Op_char, theChar); // 压入运算符栈
        theChar = express[++i]; // 使读取的位置后移,并取到下一个字符
        break;
    case '=':
        char x;
        Pop(Op_char, x); // 脱括号并读取下一个字符
        theChar = express[++i];
        break;
    case '>': // 出栈并将运算结果入栈
        char theta;
        float a, b;
        Pop(Op_char, theta);
        Pop1(Op_float, b);
        Pop1(Op_float, a);
        Push1(Op_float, Operate(a, theta, b));
    default:
        break;
};

theChar 来用保存当前读取的字符,Op_char 是定义并经过初始化的运算符栈, Op_float 是定义并经过初始化的运算数栈,PushPop 是对运算符栈入栈出栈Push1Pop1 是对运算数栈入栈出栈。它们对应的代码如下:

SqStack Op_char; // 声明运算符栈
SqStack1 Op_float; // 声明运算数栈
char theChar; // 记录目前读取表达式的字符

InitStack(Op_char); // 初始化运算符栈
Push(Op_char, '#'); // 将最低优先级的'#'起始符压入操作数栈

InitStack1(Op_float); // 初始化运算数栈

...
void InitStack(SqStack &s) { // 初始化运算符栈
    s.base = (char *) malloc(STACK_INIT_SIZE * sizeof(char));
    s.top = s.base;
    s.stacksize = STACK_INIT_SIZE;
}

void Push(SqStack &s, char e) { // 将运算符压入运算符栈
    if (s.top - s.base >= s.stacksize) {
        s.base = (char *) realloc(s.base, (s.stacksize + STACK_INCREMENT) * sizeof(char));
        s.top = s.base + s.stacksize;
        s.stacksize += STACK_INCREMENT;
    }
    *s.top++ = e;
}

void Pop(SqStack &s, char &e) { // 将运算符栈顶元素出栈
    if (s.top != s.base)
        e = *--s.top;
}

void InitStack1(SqStack1 &s) { // 初始化运算符栈
    s.base = (float *) malloc(STACK_INIT_SIZE * sizeof(float));
    s.top = s.base;
    s.stacksize = STACK_INIT_SIZE;
}

void Push1(SqStack1 &s, float e) { // 将运算数压入运算数栈
    if (s.top - s.base >= s.stacksize) {
        s.base = (float *) realloc(s.base, (s.stacksize + STACK_INCREMENT) * sizeof(float));
        s.top = s.base + s.stacksize;
        s.stacksize += STACK_INCREMENT;
    }
    *s.top++ = e;
}

void Pop1(SqStack1 &s, float &e) { // 将运算数栈顶元素出栈
    if (s.top != s.base)
        e = *--s.top;
}

这上面的代码都是对栈的基本操作,就不详细解释了。 除此之外,之前的代码里还有一个 Operate() 函数,其作用就是实现双操作符的运算的,返回的是运算的结果,代码如下:

float Operate(float a, char x, float b) {
    float result = 0;
    switch (x) {
        case '+':
            result = a + b;
            break;
        case '*':
            result = a * b;
            break;
        case '-':
            result = a - b;
            break;
        case '/':
            result = a / b;
            break;
        default:
            break;
    }
    return result;
}

由于代码简单,没有什么技术含量,也不详细解释了。 = 至此,我们已经把提出的所有的问题解决了,下面附上源代码:

#include <iostream>
#include <cmath>

using namespace std;
// 定义栈类型
typedef struct /* 运算符栈 */
{
    char *base, *top;
    int stacksize;
} SqStack;

typedef struct /* 运算数栈 */
{
    float *base, *top;
    int stacksize;
} SqStack1;

// 定义所使用的常量集
const int STACK_INIT_SIZE = 100;
const int STACK_INCREMENT = 10;
/* 用于比较符号优先级的全局二维数组 */
const char priority[7][7] = {
        {'>', '>', '<', '<', '<', '>', '>'}, // +
        {'>', '>', '<', '<', '<', '>', '>'}, // -
        {'>', '>', '>', '>', '<', '>', '>'}, // *
        {'>', '>', '>', '>', '<', '>', '>'}, // /
        {'<', '<', '<', '<', '<', '=', ' '}, // (
        {'>', '>', '>', '>', ' ', '>', '>'}, // )
        {'<', '<', '<', '<', '<', ' ', '='}  // #
};
// 与比较符号优先级二维数组对应的操作符全集
char OP[] = {'+', '-', '*', '/', '(', ')', '#'};

// 函数预定义
// 操作结果:初始化运算符栈
void InitStack(SqStack &s);

// 操作结果:得到运算符栈的栈顶元素
char GetTop(SqStack &s);

// 操作结果:对运算符栈进行压栈操作
void Push(SqStack &s, char e);

// 操作结果:对运算符栈进行出栈操作
void Pop(SqStack &s, char &e);

// 操作结果:初始化运算数栈
void InitStack1(SqStack1 &s);

// 操作结果:得到运算数栈的栈顶元素
float GetTop1(SqStack1 &s);

// 操作结果:对运算数栈进行压栈操作
void Push1(SqStack1 &s, float e);

// 操作结果:对运算数栈进行出栈操作
void Pop1(SqStack1 &s, float &e);

// 操作结果:判断一个字符是否是数字
bool isNumber(char c);

// 操作结果:计算中缀表达式的值
float MidExpression_Eval(char Express[]);

// 操作结果:计算表达式axb,并返回结果
float Operate(float a, char x, float b);

// 操作结果:获取操作符在全集操作符中的位置,并返回下标,此函数为辅助函数
int getIndex(char ops[], char e);


char Precede(char top, char c);
// 操作结果:获取算符优先级关系,并返回具体优先级符号,如'<','>'等


int main() {
    char express[STACK_INIT_SIZE] = {}; // 存储中缀表达式
    float result;
    cout << "输入中缀运算式: ";
    cin >> express;
    express[strlen(express)] = '#';
    result = MidExpression_Eval(express);
    express[strlen(express) - 1] = '\0';
    cout << express << '=' << result << endl;
    return 0;
}

// 函数实现
void InitStack(SqStack &s) { // 初始化运算符栈
    s.base = (char *) malloc(STACK_INIT_SIZE * sizeof(char));
    s.top = s.base;
    s.stacksize = STACK_INIT_SIZE;
}

char GetTop(SqStack &s) { // 获取运算符栈的栈顶元素
    if (s.top != s.base) {
        return *(s.top - 1);
    };
}

void Push(SqStack &s, char e) { // 将运算符压入运算符栈
    if (s.top - s.base >= s.stacksize) {
        s.base = (char *) realloc(s.base, (s.stacksize + STACK_INCREMENT) * sizeof(char));
        s.top = s.base + s.stacksize;
        s.stacksize += STACK_INCREMENT;
    }
    *s.top++ = e;
}

void Pop(SqStack &s, char &e) { // 将运算符栈顶元素出栈
    if (s.top != s.base)
        e = *--s.top;
}

void InitStack1(SqStack1 &s) { // 初始化运算符栈
    s.base = (float *) malloc(STACK_INIT_SIZE * sizeof(float));
    s.top = s.base;
    s.stacksize = STACK_INIT_SIZE;
}

float GetTop1(SqStack1 &s) { // 获取运算数栈的栈顶元素
    if (s.top != s.base) {
        return *(s.top - 1);
    }
}

void Push1(SqStack1 &s, float e) { // 将运算数压入运算数栈
    if (s.top - s.base >= s.stacksize) {
        s.base = (float *) realloc(s.base, (s.stacksize + STACK_INCREMENT) * sizeof(float));
        s.top = s.base + s.stacksize;
        s.stacksize += STACK_INCREMENT;
    }
    *s.top++ = e;
}

void Pop1(SqStack1 &s, float &e) { // 将运算数栈顶元素出栈
    if (s.top != s.base)
        e = *--s.top;
}

bool isNumber(char c) {
    return (c >= '0' && c <= '9');
}

float Operate(float a, char x, float b) {
    float result = 0;
    switch (x) {
        case '+':
            result = a + b;
            break;
        case '*':
            result = a * b;
            break;
        case '-':
            result = a - b;
            break;
        case '/':
            result = a / b;
            break;
        default:
            break;
    }
    return result;
}

int getIndex(char ops[], char e) {
    for (int i = 0; i < 7; i++) {
        if (e == ops[i]) {
            return i;
        }
    }
    return -1;
}

char Precede(char top, char c) {
    return priority[getIndex(OP, top)][getIndex(OP, c)];
}


float MidExpression_Eval(char express[]) {
    SqStack Op_char; // 声明运算符栈
    SqStack1 Op_float; // 声明运算数栈
    int i = 0; // 记录表达式读取位置
    char theChar; // 记录目前读取表达式的字符

    InitStack(Op_char); // 初始化运算符栈
    Push(Op_char, '#'); // 将最低优先级的'#'起始符压入操作数栈

    InitStack1(Op_float); // 初始化运算数栈
    theChar = express[i]; // 拿到表达式的第一个值
    while (theChar != '#' || GetTop(Op_char) != '#') {
        char numbers[10]; // 用于存储多位数字
        int j = 0; // 用于存储数字数组下标,方便增加位数, 同时也可以记录数字数组的长度
        while (isNumber(theChar) || theChar == '.') { // 若是数字或小数点,则循环读取
            numbers[j] = theChar;
            i++;
            j++;
            theChar = express[i];
        }

        if (j > 0) { // 若数字数组长度大于0,则循环数组求多位数字的值并压入运算数栈
            float sum = 0;
            int dot = getIndex(numbers, '.'); // 若无小数点则返回-1
            for (int k = 0; k < j; k++) {
                if (numbers[k] == '.') {
                    continue;
                }
                if (dot != -1) {
                    if (k < dot) {
                        sum += (numbers[k] - '0') * pow(10, j - 1 - k - dot - 1); // 将字符转换成对应的多位数字
                    } else if (k > dot) { // 若没有小数点,这个块不执行
                        sum += (numbers[k] - '0') * pow(10, dot - k);
                    }
                } else {
                    sum += (numbers[k] - '0') * pow(10, j - 1 - k);
                }

            }
            Push1(Op_float, sum);
        } else {
            switch (Precede(GetTop(Op_char), theChar)) {
                case '<': // 栈顶元素优先级比此时的取值更低
                    Push(Op_char, theChar); // 压入运算符栈
                    theChar = express[++i]; // 使读取的位置后移,并取到下一个字符
                    break;
                case '=':
                    char x;
                    Pop(Op_char, x);
                    theChar = express[++i];
                    break;
                case '>':
                    char theta;
                    float a, b;
                    Pop(Op_char, theta);
                    Pop1(Op_float, b);
                    Pop1(Op_float, a);
                    Push1(Op_float, Operate(a, theta, b));
                default:
                    break;
            }
        }
    }
    return GetTop1(Op_float);
}

结束?

看上去我们的代码已经很完善了,其实我们还有一些东西没有处理:

  • 如果输入了错误的中缀表达式?
  • 某些地方的代码可以更加优雅?
  • 大量的中缀表达式验证正确性?

对于第一点,我是假设于使用程序的人都会输入正确的中缀表达式,并没有对错误的中缀表达式进行处理和反馈提示,因此对用户有一些不友好,待改进;其次,像一些for循环,if else语句可以更加精简、优雅,没有对代码进行多次提炼,待改进;这个应用程序没有经过大量、多样的测试来验证其准确性,所以并不能保证其完全正确,待改进。

深入与思考

如何求后缀表达式的值,以及中缀表达式如何转换为后缀表达式?

对于前一个问题,我在 Thinking 里已经描述过了,这里就不再再次阐述,对于后一个问题,有了上面的基础,也是很容易实现的,这里就不用代码描述了,就用文字描述一下大概的思路:

  1. 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
  2. 从左至右扫描中缀表达式;
  3. 遇到操作数时,将其压入S2;
  4. 遇到运算符时,比较其与S1栈顶运算符的优先级:
    1. 如果S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
    2. 否则,若优先级比栈顶运算符的高,也将运算符压入S1;
    3. 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到4-i与S1中新的栈顶运算符相比较;
  5. 遇到括号时:
    1. 如果是左括号“(”,则直接压入S1;
    2. 如果是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将这一对括号丢弃;
  6. 重复步骤25,直到表达式的最右边;
  7. 将S1中剩余的运算符依次弹出并压入S2;
  8. 依次弹出S2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式。

总结

通过这次的程序和记录总结,我学到了很多,其中最值得一提的就是编码方式。 在编写程序的时候,我可以先不管各个功能的具体实现(比如Operate()啊,Pop()啊什么的), 我只需要关注完成这个程序需要什么功能,先写下来,完成一个主函数的逻辑,到后面再去分别实现一个个的辅助函数的逻辑,领悟了这一点对我来说是非常有帮助的,这可以大大的提高我函数式编程的思维。 除此之外,实现一些辅助函数的辅助函数的时候也对我的思维进行了锻炼,比如说精简的Precede(),对多位数字和小数的处理,以及整个中缀表达式求值思维得到了巩固和拓展,对于克服种种难题有满满的成就感。 好了,就这样吧,这应该是我写的最认真的一篇记录了,加油。 = 2017年11月17日凌晨2:28

要实现顺序表和链表,首先我们需要知道的是,何为顺序表何为链表。

顺序表

这个很简单,在JS中,数组就是顺序表的实例,它具有顺序表的一切性质:

  1. 存放在连续的内存当中,物理位置相邻,换句话说,其数据元素都是用一组地址连续的存储单元以此存储在线性表当中;
  2. 只要确定了存储线性表的起始位置,顺序表中任一数据元素都可以随机存取;
  3. 具有线性表的性质(关于线性表,这里不作介绍,可以在这里了解线性表

所以,在JS,要初始化一个空的顺序表是十分简单的:

// 方式一
var ary1 = [] // []
// 方式二
var ary2 = new Array() // []
// 神经病方式
var ary3 = [...''] // []
var ary4 = [...new Set()] // []
var ary5 = [...new Map()] // []
var ary6 = [...new String()] // []
var ary7 = ''.split('') // []
var ary8 = Array.prototype.slice.call('') // []
// 终极神经病方式
var obj = {}
var ary9 = [...obj[Symbol.iterator]] // []

既然是自己实现顺序表,自然不能使用js数组中自带的方法啦,一般来说,顺序表有以下几个基本方法:

  1. createList()
  2. initList(L)
  3. getLength(L)
  4. insertList(L, i, e)
  5. deleteList(L, i , e)
  6. getListElem(L, i)
  7. getElemIndex(L, e)

So, 接下来一个个实现吧~


 //createList
function createList():any[] {
  var array = new Array() // []
  return array
}

// initList(L)
function initList(list: any[]): number[] {
  if (list instanceof Array) {
    var length = 15 // 由于js本身不能自己输入值,所以采用自己赋值来初始化一个顺序表
    for (let i = 0; i < length; i++) { list[i] = i + 1 } return list 
  }
} 

// getLength(L) 
function getLength(list: number[]): number{ 
  let len: number = 0; 
  while(L[len] !== undefined) { // 循环遍历每一个数据元素, 一个不为空则计数器加一 
    len++ 
  }
  return len 
} 

// insertList(L, i, e) 
function insertList(list: number[], index:number, item: number): number[] {
  let i: number
  let len = getLength(list)
  for (i = len - 1; i >= index - 1; i--){
     list[i+1] = list[i] // 位置index之后的元素(包括index)全部往后移一个单元
  }
  list[index - 1] = item
  return list
}

// deleteList(L, i)
function deleteList(list: number[], index: number): number {
  if (index > getLength(list) + 1 || index < 1) {
    return -1
  }
  let i: number = index - 1
  let len: number = getLength(list)
  let e = list[i]
  for (; i < len; i++){
    list[i] = list[i + 1] // index之后的每一个元素往前移一个单元
  } 
  list.length-- // 长度减1
  return e 
} 

// getListElem 
function getListElem(list: number[], index: number):number {
  if (index > getLength(list) + 1 || index < 1) {
    return -1
  }
  return list[index - 1]
}

// getElemIndex(L, e)
function getIndex(list: number[], value: number): number {
  let i: number = 0
  for (; i < getLength(list); i++) {
    if (list[i] === value) {
      return i
    }
  }
}

最后再用一个test函数测试:

function test():void {
  let sqList = createList()
  console.log('创建空顺序表:' + sqList)
  initList(sqList)
  console.log('初始化一个数字类型顺序表:' + sqList)
  let elem = getListElem(sqList, 5)
  console.log('获取第五个元素:' + elem)
  let index = getListIndex(sqList, 6)
  console.log('获取值为6的游标:' + index)
  insertList(sqList, 4, 999)
  console.log('在第四个位置插入999:' + sqList)
  let e = deleteList(sqList, 4)
  console.log('删除第四个位置的元素:' + sqList, '被删除的元素:' + e)
  console.log('表长为:' + getLength(sqList))
  console.log('所有元素为:')
  consAll(sqList) // 输出所有元素
}
test()

一个简单的顺序表就完成了~,接下来介绍链表。

链表

先介绍以下何为链表 链表也是线性表中的一元,它也是一个连续的表,不过相比于顺序表,它不要求物理位置上相邻,但要求的是逻辑位置上相邻,因此他没有顺序表所具有的弱点——删除、插入等需要移动大量的数据元素,但是也失去了顺序表随机存储的优点。我们先来看一下链表的结构: 链表 从上图可以清晰的看出,对于一个数据元素,我们这里把它叫做结点好了,一个结点(Node)中包含两个域,一个是存储自身信心的数据域,另一个是指向下一个结点的指针域,由于js里没有指针,那么我暂且称之为链域,指向的是该结点的下一个结点。从上图我们还发现了一个head结点,我们把它称之为 头指针,他的数据域可以不存储任何数据,也可以存储像表长等信息,其链域中存储的是指向链表的第一个结点的链。可能现在会对头指针的存在产生一个疑惑,那么我举个例子就明白了,试想一下,如果没有头指针,我们如何在第一个结点前再插入一个结点呢?这个操作很简单,就是把你新创建的结点的链域指向第一个结点,但是如果你不是插入到链表的最前面呢?你要先创建一个结点,然后让想插入的那个位置的前一个结点的链域指向你新创建的结点,再让你的链域指向你想插入的位置的那个结点。发现了吗?插入第一个和插入中间其他位置的操作是不相同的,为了简化和统一像这样的操作,于是引入头指针。链表的最后一个结点之后没有结点的存在,因此让他的链指向NULL 在传统语言如c/c++中,因为有指针的存在,可以很明确的创建一个链表,而js中是没有指针的(this应该不算吧),那我们要如何去实现一个链表的结点呢?一开始想到用对象Object实现,但是对象复制有一些麻烦,于是转而选择了类function,看以下代码:

function LNode() :void{
  this.data = null;
  this.next = null;
}

用公用属性data当作结点的数据域,用公有属性next当作链域,当新建一个结点的时候只需要 new LNode()即可,比较方便,当然,也可以使用es6的class,代码如下:

class LNode {
  constructor() {
    this.data = null;
    this.next = null;
  }
}

由于typescirpt用的有一些生疏,以及class用的不太熟练,先用es5实现那些方法。 代码如下:

function LNode() :void{
  this.data = null;
  this.next = null;
}

function createLink(head: any, n: number): void{
  let i: number;
  head.data = n
  for (i = n; i > 0; i--) {
    let newNode = new LNode()
    newNode.data = Math.floor(Math.random() * 10 + 1)
    newNode.next = head.next
    head.next = newNode
  }
}

function getElem(LinkList: any, i: number): number {
  if (!LinkList.next) {
    return
  }
  let p: any = LinkList.next
  let j: number = 1
  while (p && j < i) { p = p.next ++j } if (!p || j > i) {
    return
  }
  return p.data
}

function getIndexs(LinkList: any, value: number): number[] {
  if (!LinkList.next) {
    return
  }

  let p: any = LinkList.next
  let indexs: number[] = new Array()
  let len = 0
  let i: number = 1
  while (p) {
    if (p.data === value) {
      indexs[len] = i
      len++
    }
    p = p.next
    i++
  }

  return indexs
}

function insertElem(LinkList: any, pos: number, e: number): void {
  if (!LinkList.next) {
    return
  }

  let p: any = LinkList
  let i: number = 0

  while (p && i < pos - 1) { p = p.next i++ } if (!p || i > pos - 1) {
    return
  }

  let s = new LNode()
  s.data = e
  s.next = p.next
  p.next = s
  LinkList.data++
}

function consAll(LinkList: any): void {
  let list: String = ''
  let p: any = LinkList.next
  while (p) {
    list += p.data + ', '
    p = p.next
  }
  console.log(list)
}

function deleteElem(LinkList: any, i: number): number {
  if (!LinkList.next) {
    return
  }

  let p: any = LinkList.next
  let j: number = 1
  let e: number
  let q

  while (p && j < i - 1) { p = p.next ++j } if (!p || j > i - 1) {
    return 
  }

  q = p.next
  p.next = q.next
  // 由于js的垃圾回收机制,不需要手动释放内存
  LinkList.data--
  return e
}

function getLenth(LinkList: any): number{
  if (!LinkList.next) {
    return 0
  }
  let p = LinkList.next
  let j = 0
  while (p) {
    p = p.next
    j++
  }
  return j
  // 由于我把表长存在头结点的data中,所以可以直接 return LinkList.data
}

function test(): void {
  var L = new LNode()
  createLink(L, 10)
  consAll(L)
  console.log(getIndexs(L, 5))
  console.log(getElem(L, 4))
  insertElem(L, 3, 999)
  consAll(L)
  deleteElem(L, 7)
  consAll(L)
  console.log(getLenth(L))
}

test()

结语

用js实现数据结构比C/C++更容易,为了更加靠近,我在这里使用了一部分typescript,最近还学习了kmp算法,快排,栈,图,队列,广度优先算法,狄克斯特拉算法等等,将在今后的博客一一列出。

参考资料

《数据结构》 严蔚敏 (PS: 这本书。。不好)

前言

大二了,学校开了一门数据结构的课,在学习过程中,发现自己对好多C/C++的知识有点忘却了,然后想到自己这一年基本上都在学习Javascript,所以何不用JS来学数据结构呢?


路要一步步走,饭要一口口吃,我需要一步步从基本的开始学习,加油!以后该主题的博文均放置在以下板块内。

文章链接

顺序表、链表的JS实现: [http://wingsico.org/2017/11/10/squence_link/ ‎](http://wingsico.org/2017/11/10/squence_link/ ‎)