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

前言

老实说,串这一章学的并不好,感觉只了解相关概念,在我的印象中

串 == 字符串

而在C/C++语言中,字符串又可用

char chs[100]; // 字符数组
string str; // 字符串

两种(简单)方法表示,结构上均与线性表无异,区别只在于串的数据对象被约束为字符集。但在操作上,串与线性表是存在较大差别的。 在线性表的基本操作中,大多以“单个元素”作为操作对象,例如查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等。 而在串的基本操作中,通常以“串的整体”作为操作对象,例如在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。 但如何实现一个串,如何实现一个符合情景的串是一个令我头疼的问题。如果在程序设计语言中,串只是作为输入或输出的常量出现,则只需存储此串的串值,即字符序列即可。但在多数非数值处理的程序中,串也以变量的形式出现。(这个非数值处理有点不太明白,串不都是字符类型吗?不是均为非数值吗?)

串的表示方法

定长顺序存储表示

类似线性表的顺序存储结构,用一组地址连续的存储单元存储串值得字符序列,给定一个预定义的大小,为每个定义的串变量分配一个固定长度的存储区,可以用如下代码描述:

const int MAXSIZE = 255;
typedef char sstring[MAXSIZE + 1];

串的实际长度可以在预定义长度内随意,超过定义的长度就会被截断。在上面的代码中,我们设置了一个常量MAXSIZE,同时自定义了一个数据类型sstring[],注意,我们定义的字符串预定义长度为MAXSIZE + 1,这是为了方便串操作,我们将串的长度存储在0号数据单元,当然,这也不是必须的,在c语言中,我们可以使用strlen()来获取字符数组char chs[]的真实长度,用str.length()来获取字符串的长度。 这个为最简单也最常用的一种串的结构,也是我们这次实验需要用到的结构。接下来简要介绍一下另外两种串的表示方法(对于我来说不是很熟悉)

堆分配存储表示

对于第一种表示方法,会有一些问题:

1. 操作的时间复杂度基于串的长度,效率较低
2. 在一些操作中出现串值序列的长度超过上界时,约定使用截尾法处理,也就是说会导致一些串值丢失的情况

为了解决这些问题,我们采取不限制串的最大长度,而采用动态分配串值的存储空间 我们仍以一组地址连续的存储单元存放串值字符序列,但他们的存储空间是在程序执行过程中动态分配而得。在C语言中,存在一个称之为“堆”的自由存储区,并由C怨言的动态分配函数malloc()free()来管理。利用malloc()来为每一个新产生的串分配一块实际船厂所需的存储空间。其代码表示如下:

typedef struct {
    char *ch; // 若是非空串,则按串长分配存储区,否则ch为 NULL
    int length; // 串长
}

由于堆分配存储结构的串既有顺序存储结构的特点,处理方便,操作中对串长又没有任何限制,更加的灵活,因此在串处理的应用程序中也经常被选用。

串的块链存储表示

既然线性表中有链式的表示方法,那么在串中也可以采用链表方式存储串值。

const int CHUNKSIZE = 80; // 自定义大小
typedef struct Chunk {
    char ch[CHUNKSIZE];
    struct Chunk *next;
}

typedef struct {
    Chunk *head, *tail; // 头尾指针
    int curlen; // 串的当前长度
}LString

由代码很容易看出,一个块由数据域(字符数组)和指向下一个块的指针组成,同时LString表示的是字符串,其头指针指向其串首地址,还可以增设一个尾指针用来指向最后一个结点,并给出当前串的长度curlen,我们把这种串结构称作为块链结构,设置尾指针还有一个目的,是为了标语进行联结操作,但需要注意的是联结时需要处理第一个串尾的无效字符块链结构的串虽然对一些串操作比较方便,但不如前两种灵活,它占用内存大,且操作复杂,使用频率较少。


介绍完这三种表示方法,该进入我们今天的主题——文本编辑

串应用——文本编辑

想到大一上学期,C语言的课程比较紧凑,于是对于课本后面的知识没有好好巩固,对于文件处理方面的知识非常模糊,于是先整理了一下C++文件与流的一些知识要点。


到目前为止,我们已经使用了 iostream 标准库,它提供了 cin 和 cout 方法分别用于从标准输入读取流和向标准输出写入流。 那么我们如何对文件进行输入和输出呢?这就需要用到 C++ 中另一个标准库 fstream,它定义了三个新的数据类型: ofstream 该数据类型表示输出文件流,用于创建文件并向文件写入信息。 ifstream 该数据类型表示输入文件流,用于从文件读取信息。 fstream 该数据类型通常表示文件流,且同时具有 ofstream 和 ifstream 两种功能,这意味着它可以创建文件,向文件写入信息,从文件读取信息。 因此,要在 C++ 中进行文件处理,必须在 C++ 源代码文件中包含头文件 <iostream><fstream>

打开文件

在从文件读取信息或者向文件写入信息之前,必须先打开文件。ofstreamfstream 对象都可以用来打开文件进行写操作,如果只需要打开文件进行读操作,则使用 ifstream 对象。 下面是 open() 函数的标准语法,open() 函数是 fstream、ifstream 和 ofstream 对象的一个成员。

void open(const char *filename, ios::openmode mode);

在这里,open() 成员函数的第一参数指定要打开的文件的名称和位置,第二个参数定义文件被打开的模式ios::app 追加模式。所有写入都追加到文件末尾。 ios::ate 文件打开后定位到文件末尾。 ios::in 打开文件用于读取。 ios::out 打开文件用于写入。 ios::trunc 如果该文件已经存在,其内容将在打开文件之前被截断,即把文件长度设为 0。 可以把以上两种或两种以上的模式结合使用。例如,如果想要以写入模式打开文件,并希望截断文件,以防文件已存在,那么可以使用下面的语法:

ofstream outfile;
outfile.open("file.dat", ios::out | ios::trunc );


类似地,如果想要打开一个文件用于读写,可以使用下面的语法:
fstream  afile;
afile.open("file.dat", ios::out | ios::in );

####关闭文件 当 C++ 程序终止时,它会自动关闭刷新所有流,释放所有分配的内存,并关闭所有打开的文件。但程序员应该养成一个好习惯,在程序终止前关闭所有打开的文件。 下面是 close() 函数的标准语法,close() 函数是 fstreamifstreamofstream 对象的一个成员。

void close();

####写入文件 在 C++ 编程中,我们使用流插入运算符( << )向文件写入信息,就像使用该运算符输出信息到屏幕上一样。唯一不同的是,在这里使用的是 ofstreamfstream 对象,而不是 cout 对象。 ####读取文件 在 C++ 编程中,我们使用流提取运算符( >> )从文件读取信息,就像使用该运算符从键盘输入信息一样。唯一不同的是,在这里您使用的是 ifstreamfstream 对象,而不是 cin 对象。


有了以上的知识,对于读写文件的话还是信手拈来的。接下来,我们来看看实验要求

1. 要求建立一个文本文件,每个单词子串不包含空格且不跨行,单词子串由字符序列构成,且区分大小写;
2. 统计给定单词子串在文本文件中出现的总次数;
3. 检索输出某个单词子串出现在文本中的行号、在该行中出现的次数以及位置。

一个个来分析,对于第一个,不包含空格也就是不存在类似hello world这样的字符串,字符串不跨行意味着每一行只有一个字符串,区分大小写的话意义不大,因为读取的和比较的时候是肯定区分大小写的。所以,我们使用如下函数来创建一个文本文件并读入字符串:

#include <iostream>
#include <fstream> // 文件流

const int maxsize = 10000; // 预定义字符串最大长度
typedef char sstring[maxsize]; // 自定义字符数组类型
void createTextFile ();
...
void createTextFile () {
    sstring data; // 声明一个sstring类型的变量,存储输入的字符,包含换行符以及空格
    int i = 0; // 用于标记当前读入的字符在字符数组的位置
    char temp; // 存储中间变量,读入当前字符值

    ofstream outfile; // 定义一个写入变量
    outfile.open("test.txt"); // 执行打开文件方法,打开一个当前路径下的"test.txt"文件

    cout << "Write some strings to this file, if you want to stop, input a '#': " << endl;
    while (true) {
        if ((temp = getchar()) != '#') { // 以#号结束输入
            data[i++] = temp; // 存入字符数组中
            continue; // 继续下一次读入
        }
        break; // 结束输入
    }
    getchar(); // important 坑
    outfile << data << endl; // 将数据写入文件中
    outfile.close(); // 关闭对文件的访问
}

在代码中,我们使用

typedef char sstring[maxsize];

来定义一个字符数组类型而不是unsigned char,这么做的目的是为了后面的读取文件使格式保持一致,在后面会说到。 同时,在注释中标记important的代码

  ...
}
getchar();

为什么要在结束输入之后调用这个方法呢?原因在于:当我们输入#之后,字符数组剩余的部分的内容不确定,如果没有getchar()他将会得到一些乱码导致文件编码存在问题以及读取文件存在问题。我们使用getchar()来获取缓冲区的字符,避免将这些字符写入文件中去。(有待考证) 写入之后,我们就是需要读取文件的内容了。对于实验的要求,采用整行读取会较为方便,即使用getline()函数,读取是较为简单的,但是我们如何存储读取的数据呢?我们知道,读取的每一行的数据均为一个字符串,因此我们需要一个结构来存储每一个字符串。我第一反应就是字符串数组,这是在别的语言里非常常见的,但在c语言中,char chs[]只能存储字符串,无法使用它来存储多个字符串,所以,我想到了使用另一个类型 —— **string 使用string,我们需要引入头文件 #include <string>,我们可以这样定义一个字符串数组:

string content[maxsize];
...
content[0] = "my world";
content[1] = "your name";
...

因此,我们可以每读取一行,将该行的字符串存入字符串数组中去,同时,由于读取的内容几乎在每个函数内都需要使用,为了避免每次调用函数都需要传参的麻烦,我们将读取的内容存在全局的字符串数组内,代码如下:

const int maxsize = 10000;
int lineNumber = 0;
string content[maxsize]; // 字符串数组,存储文件内容

void getFileContent() {
    sstring data; // 字符数组
    int index = 0; // 存储当前字符串存入数组的下标
    ifstream infile("test.txt"); // 读取文件
    while (infile.getline(data, maxsize)) { // 逐行读取
        content[index++] = data;
    }
    lineNumber = index; // 内容的行数
}

因为我们的content用于全局,所以我们无需穿参,在函数内直接对content进行修改。再设置了一个全局的变量 lineNumber 用于存储读取文件的行数,对后面的匹配要求做铺垫。 读写存储操作均完成了,我们来看下一个要求,需要统计子串在字符串出现的总次数,思路很简单,我们对每一行进行匹配,若匹配成功则计数器加一,同时要注意一行可能会有多个匹配的子串,所以一行需要进行多次匹配。 那么在统计次数之前,我们需要完成一个更重要的工作,如何进行匹配?也就是判断子串是否在主串内以及如何定位到子串在主串的位置,这样的操作我们通常称为模式匹配。 通过模式匹配,我们将返回子串的第一个字符在主串中的下标。举个例子:

sstring sMain = "abbbcbc";
sstring sChild = "bc";

则子串在主串的位置为1,那么如何实现匹配呢? 我们指定两个指针,一个指针 i 指向主串首个字符,一个指针 j 指向子串首个字符,逐个字符比较。当字符相等的时候, ij 同时后移,匹配下一个字符;当字符不相等时, j 回到子串的首个字符的位置, i 则回溯到之前匹配到子串的第一个字符的位置的下一个位置。当 j 后移到子串之后的位置时,说明子串已经完全匹配,则此时 i 的指向为子串的最后一个字符在主串的位置的后一个位置。我们需要返回子串的位置,则需要找到匹配到的子串的首字符在主串中的位置,只需要将 i 后移子串长度个单位就可以了。具体实现如下:

int getLength (sstring s) {
    return strlen(s);
}

int getIndex (string s, sstring t, int pos) {
    // 返回子串t在主串s中第pos个字符之后的位置。
    // 1 <= pos <= sLen
    // 匹配失败返回0
    int i = pos - 1, j = 0, sLen = s.length(), tLen = getLength(t);
    while (i < sLen && j < tLen) {
        if (s[i] == t[j]) { // 相等则主、子串指针均后移
            i++;
            j++;
        } else {
            i = i - j + 1; // 主串指针回溯
            j = 0; // 子串指针重新指向子串首字符
        }
    }
    if (j == tLen) {
        return i - tLen + 1; // 返回子串在主串的首位置
    }
    return 0; // 没匹配到则返回0
}

注意,这个函数 getIndex() 返回的是位置而不是下标,也就是是从1开始的,所以使用的时候要注意,它作为一个辅助函数,来实现我们两个主要功能的。 先来看计数功能,统计子串在主串中出现的总次数,在先前,我们已经将字符串存入了字符串数组,数组的每一个元素代表着每一行的字符串。因此我们需要便利这个字符串数组,对其每一个字符串进行匹配,得到最终的匹配个数:

void wordCount () {
    sstring queryStr; // 搜索的子串
    int i = 0; // 记录第几行
    int count = 0; // 计数
    cout << "输入你要计数的字符串: ";
    cin >> queryStr;
    while (i < lineNumber) {
        int index = 1;
        while (true) {
            index = getIndex(content[i], queryStr, index) + 1; // 多次匹配
            if (index - 1 == 0) {
                break;
            }
            count++; // 匹配成功计数器加一
        }
        i++; // 换行,对下一行进行匹配
    }
    cout << count << endl;
}

相应的,对于子串的定位,功能上感觉和计数有部分重合,代码如下:

void strFind () {
    sstring s;
    int index = 1;
    cout << "输入要定位的字符串: ";
    cin >> s;
    for (int i = 0; i < lineNumber; i++) {
        int count = 0; // 计数器,记录每一行子串出现的次数
        while (true) {
            index = getIndex(content[i], s, index) + 1;
            if (index - 1 != 0) {
                count++;
                printf("字符串 %s 在第 %d 行,第 %d 列.\n", s, i + 1, index - 1);
                continue;
            }
            break;
        }
        printf("在第%d行共出现了%d次\n", i + 1, count);
    }
}

问题汇总

  1. using namespace std; 的位置 我发现,这一句代码不能放在定义全局变量 string 的下面,如果在下面的话,将产生一个报错:

    Error: unknown type name 'string'; did you mean 'std::string'?
意味着string是包含在命名空间std中的。
  1. 何时使用 getFileContent() 这个函数的作用是读取指定文件内容,并存入全局的字符串数组中去。当第一次使用该程序时,指定文件还未创建,因此读取得到的是空字符串,当我们执行完写入操作后,需要再次执行该函数将内容存入全局字符串数组。因此,需要在刚进入主函数时调用以及完成写入操作之后调用一次。

总结和改进

关于这次实验,我更改了实验内容所提供的

typedef unsigned char sstring[maxsize];

而使用了

typedef char sstring[maxsize];

只是为了函数的参数格式化,但其中区别未深入了解。同时,为了方便加入了string类型的数据,并不是很好的完全符合实验,而且对于引用参数和指针参数的理解还有些偏差,导致调试过程中出现许多的问题,需要自己仔细的再进行学习。 对于函数 strfind()wordCount() ,这两个函数有一些公共的部分,应该是可以把它独立出来作为一个单独的函数来调用,将会简洁许多。

程序源代码

#include <fstream>
#include <iostream>
#include <string>

using namespace std;
const int maxsize = 10000;
string content[maxsize]; // 字符串数组,存储文件内容
int lineNumber = 0;
typedef char sstring[maxsize];

void createTextFile ();
void wordCount ();
void strFind ();
void getFileContent();
int getIndex (string s, sstring t, int pos);
int choose ();
int getLength (sstring s);

int main () {
    bool t = true;
    getFileContent();
    while (t) {
        switch (choose()) {
            case 1: {
                createTextFile();
                getFileContent(); // 创建完之后需要重新调用一次content
                cout << endl;
                break;
            }
            case 2: {
                wordCount();
                cout << endl;
                break;
            }
            case 3: {
                strFind();
                cout << endl;
                break;
            }
            case 0: {
                t = false;
                cout << "成功退出" << endl;
                break;
            }
            default: {
                cout << "输入有误,请重新输入" << endl;
            }
        }
    }
    return 0;
}

void createTextFile () {
    sstring data;
    int i = 0;
    char temp;

    ofstream outfile;
    outfile.open("test.txt");

    cout << "Write some strings to this file, if you want to stop, input a '#': " << endl;
    while (true) {
        temp = getchar();
        if (temp != '#') {
            data[i++] = temp;
        } else {
            break;
        }
    }
    getchar();
    outfile << data << endl;
    outfile.close();
}

int choose () { // 菜单函数
    int c;
    cout << "\t文本编辑系统菜单🈳️" << endl << endl;
    cout << "\t1. 创建文本文件" << endl;
    cout << "\t2. 文件单词计数" << endl;
    cout << "\t3. 文件单词定位" << endl;
    cout << "\t0. exit" << endl;
    cout << "请输入你的选择: ";
    cin >> c;
    cin.ignore();
    return c;
}

void getFileContent() {
    sstring data; // 字符数组
    int index = 0; // 存储当前字符串存入数组的下标
    ifstream infile("test.txt"); // 读取文件
    while (infile.getline(data, maxsize)) { // 逐行读取
        content[index++] = data;
    }
    lineNumber = index; // 内容的行数
}

int getIndex (string s, sstring t, int pos) {
    // 返回子串t在主串s中第pos个字符之后的位置。
    // 1 <= pos <= sLen
    // 匹配失败返回0
    int i = pos - 1, j = 0, sLen = s.length(), tLen = getLength(t);
    while (i < sLen && j < tLen) {
        if (s[i] == t[j]) { // 相等则主、子串指针均后移
            i++;
            j++;
        } else {
            i = i - j + 1; // 主串指针回溯
            j = 0; // 子串指针重新指向子串首字符
        }
    }
    if (j == tLen) {
        return i - tLen + 1; // 返回子串在主串的首位置
    }
    return 0; // 没匹配到则返回0
}

int getLength (sstring s) {
    return strlen(s);
}

void wordCount () {
    sstring queryStr; // 搜索的子串
    int i = 0; // 记录第几行
    int count = 0; // 计数
    cout << "输入你要计数的字符串: ";
    cin >> queryStr;
    while (i < lineNumber) {
        int index = 1;
        while (true) {
            index = getIndex(content[i], queryStr, index) + 1; // 多次匹配
            if (index - 1 == 0) {
                break;
            }
            count++; // 匹配成功计数器加一
        }
        i++; // 换行,对下一行进行匹配
    }
    cout << count << endl;
}

void strFind () {
    sstring s;
    int index = 1;
    cout << "输入要定位的字符串: ";
    cin >> s;
    for (int i = 0; i < lineNumber; i++) {
        int count = 0; // 计数器,记录每一行子串出现的次数
        while (true) {
            index = getIndex(content[i], s, index) + 1;
            if (index - 1 != 0) {
                count++;
                printf("字符串 %s 在第 %d 行,第 %d 列.\n", s, i + 1, index - 1);
                continue;
            }
            break;
        }
        printf("在第%d行共出现了%d次\n", i + 1, count);
    }
}
C++

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