Blog - wingsico

前言

历经好多时间= =,终于完成了一个小项目,再次更新了一些我的移动端知识,之前总是对概念有些不清晰,先梳理一下。

像素

概念

CSS像素(CSS Pixel)

CSS代码中的逻辑像素,是一个抽象的东西,实际并不存在。

设备独立像素(Device Independent Pixel)

与设备无关的逻辑像素,可以通过虚拟程序来设置,包含了CSS像素

设备像素(Device Pixel)

物理像素,设备能控制显示的最小单位,类似1920 * 1080像素分辨率这种的。

关系

设备像素与设备独立像素

对于PC页面:在未缩放的情况下,1设备像素 === 1设备独立像素,若缩放为200%时,可以说 2设备像素 === 1设备独立像素对于移动端页面: 根据设备不同有一些差异,其引起差异的原因主要在于一个被称之为ppi(pixel per inc)的东西。

PPI

从名字上就知道是 每英寸设备有多少像素,这里的像素指的是设备像素,即物理像素,其数值越高,每英寸设备里的像素就越高,画面也就越清晰。 计算方式为: PPI计算 像苹果的Retina屏的ppi就比较高,所以清晰度很高。 还有一个很重要的概念就是dpr(device pixel ratio)

DPR

设备像素比,这个设备像素比就是物理像素独立像素,独立像素之前说到,包含着CSS像素,所以dpr即提供了一个我们代码中的像素与设备实际像素之间的一个转换关系。 计算公式:

dpr = 设备像素 / 设备独立像素

像苹果手机的dpr一般为2,即意味着1长度的设备像素里有2长度的设备独立像素,换做面积来算的话就是1设备像素包含着4设备独立像素,即成平方关系,所以清晰明了,dpr越高,屏幕清晰度也越高,与ppi有些相似,用一张图看看: DPR 大概需要了解的就这些,我在实际运用中用到的也就如下几点:

  1. dpr
  2. px
  3. device-width (屏幕宽度)

运用

对于dpr,一般用于两个地方,一个是字体大小,一个是背景图片大小 对于字体,也是用px堆起来的,因此dpr也会影响到字体的显示,当dpr较大时,为了同比例显示字体大小,就会去检测其dpr的值,根据dpr的不同来设置不同比例的字体大小,可以用如下一段sass的混合宏来适配字体显示:

@mixin font-dpr($font-size) {
  font-size: $font-size / 2;
  [data-dpr="2"] & {
    font-size: $font-size;
  }
  [data-dpr="3"] & {
    font-size: $font-size * 3 / 2;
  }
}

这里有个data-dpr,即根据dpr不同来应用不同的字体样式,此外,这里将传入的字体大小除以2,这是因为一般设计给的视觉稿都是iphone6的二倍稿,因此,为了显示正常字体大小,将其标注的字体大小除以二,再根据dpr来适配字体大小。 移动端运用到图片几乎是必然的,一般设计师会给出两种图片,一种为@2x图,一种为@3x图,不过这个主要是用来出来高清屏下图片较为高清的显示,对于普通的安卓机,dpr一直都是1,意义不大,用普通的@2x图即可达到高清的显示,但是对于ios系统,存在dpr为2、dpr为3的情况,为了图片的一个等比例缩放,我们根据dpr的不同来使用不同倍数的图片以达到与标准屏幕一致的感受。同样的,我们也可以使用sass的混合宏来适配背景图片:

@mixin bg-image($url) {
  background-image: url($url + "@2x.png");
  @media (-webkit-min-device-pixel-ratio: 3), (min-device-pixel-ratio: 3) {
    background-image: url($url + "@3x.png");
  }
}

除这两点之外,我暂时没有用到dpr其他的使用方法。

布局适配

布局和适配其实我一直难以分辨这两个概念,我就把它罗列在一起吧。 为了达到想要的效果,我的历程如下:

  1. meta 设置 viewport -> width=device-width…
  2. rem布局
  3. flex-box
  4. flexible.js
  5. 视口单位vw,vh
  6. calc计算
  7. calc + 视口单位
  8. calc + 视口单位 + 媒体查询
  9. 百分比布局
  10. 删除 6、7、8, 9 重归flexible
  11. 加上媒体查询,适配特殊机型,如 Nexus 5X

妈耶心好累,布局适配改改改改好头疼,不过还好都解决了。

meta

<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, minimum-scale=1, user-scalable=no">

这行代码作用是设置理想视口,什么是视口?什么又是理想视口,要说明这个,对于viewport就要讲很多了。 这里有一个链接,我觉得写的很好,很多内容都非常清晰的表达了出来: 移动端之viewport

rem布局

rempxem均是常用的单位,他们都是相对长度单位,在不同的地方我们需要配合起来使用。

px

px(Pixel) 是相对于屏幕分辨率而言的一个单位,一般我们对于pc均会使用px作为单位,同时,一些固定大小、长度的我们同样使用px作为单位,这个也是我们上面说到的CSS像素,包含在设备独立像素内。

em

em是一个相对与其父元素的字体大小的一个单位,举个例子

<style lang="scss">
    .parent {
        font-size: 18px;
        .child {
            font-size: 2em; // 18 * 2 = 36px
            .grandson {
                font-size: 0.5em; // 36 * 0.5 = 18px
            }
        }
    }
</style>

这个单位对于一整块整体变换有很好的效果,比如我们有一个按钮,当我们想要整体放大一个按钮的时候,不需要去改变每一个字体的大小,设置em之后可以只改变其父级元素的字体大小来达到整体缩放的效果。

rem

为了移动端而生的单位,同样是一个相对单位,与em不同的是,rem是相对于html根元素的字体大小,举个例子:

<style lang="scss">
    html {
        font-size: 10px;
        .parent {
            font-size: 2rem; // 10 * 2 = 20px
            .child {
                font-size: 4rem; // 10 * 4 = 40px
                .grandson {
                    font-size: 1.6rem; // 10 * 1.6 = 16px
                }
            }
        }
    }
</style>

有了这样一个单位,对于我们移动端上的适配来说,绝对是一大助力,我们可以使用rem来适配不同分辨率的屏幕。 现在假设我们有一张750的设计稿,我们把设计稿分成一百份,把每十份当做一个1rem,即设置:

html {
    font-size: 75px; // 750 / 100 * 10 = 75px
}

那么我们在需要一个150*150的div时,我们可以使用

.box {
    width: 2rem;
    height: 2rem;
}

当我们的屏幕不同的时候,我们只需动态的更改根元素的字体大小即可。那么如何动态更改根元素的字体大小呢?在CSS3有一个新增的媒体查询,可以帮我们检测设备相关信息并根据这些信息使用不同的样式。

@media/媒体查询

这里有相关的资料:MDN媒体查询 上面只是介绍了一些概念的东西,那么我们如何去使用媒体查询在我们的移动端适配上呢? 待续. 更新时间2017年12月23日10:35:14

前言

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

  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;

前言

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

串 == 字符串

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

前言

之前那一觉睡的有点久啊嘿嘿,废话少说,直接开始进入正题吧,实现Linux的定时服务。

准备工作

自己的电脑是Mac OS,命令跟linux差不多吧,但是定时任务也不应该在自己的电脑上跑吧,因为自己的电脑总会关的,服务也会停止的。所以我选择了我的博客所在的服务器,这个是linux centos系统。这个是我在腾讯云花一元/月领的(现在这个活动已经结束啦),ok,自动签到js脚本和服务器都有了,可以开始我们的任务了。

start!

首先,服务器上还没有我们的脚本,我们需要把我们的脚本上传到服务器里,怎么上传呢? 在mac os里(may linux里也有),进入我们脚本所在目录:

➜ ~ cd ~/my-github/nodejs/util
➜ ~ scp checkin.js root@wingsico.org:/home/checkin.js
password:
ok

这样就上传到我们服务器的/home目录下,并将文件命名为checkin.js 可以通过ssh进入服务器查看一下,很好,/home目录下已经有我们的脚本文件checkin.js了,先尝试运行一波:

[root@VM_48_13_centos ~/home]# node checkin.js
[root@VM_48_13_centos ~]# cd /var/spool/mail/
[root@VM_48_13_centos mail]# nano root
// 翻到最后一行
OK {“msg”:”\u83b7\u5f97\u4e86 96 MB\u6d41\u91cf.”,”ret”:1}

签到成功了,ok,那么我们就开始写定时服务。

定时服务

在linux中我们使用crontab这个命令来管理定时任务,我们可以使用crontab –help(其实是靠输入错误来弹出相关提示…)来查看相关命令:

usage: crontab [-u user] file
crontab [-u user] [ -e | -l | -r ]
(default operation is replace, per 1003.2)
-e (edit user’s crontab)
-l (list user’s crontab)
-r (delete user’s crontab)
-i (prompt before deleting user’s crontab)
-s (selinux context)

为了更好的运行脚本,我们写一个shell脚本来运行js脚本:

#!/bin/sh
/root/.nvm/versions/node/v8.7.0/bin/node /home/checkin.js

发现了吗?我们这里没有直接用node来运行js脚本,因为shell脚本运行的环境不同,不能直接通过node来运行js脚本,我们使用which node来找到node的运行的源文件,保存在统一目录下,命名为checkin.sh,接下来我们在定时任务里就可以直接运行这个脚本就好了,现在来编辑定时任务了,输入crontab -e,添加

10 09 * * * sudo bash /home/checkin.sh &

前面的参数的含义就是 每天的9点10分,这个命令就是在每天9点10分运行一次checkin.sh脚本,记得加sudo,不然会在日志中提示权限不够。好了,之后输入:

[root@VM_48_13_centos ~]# /sbin/service crond start

开启定时服务~之后如果修改crontab的话使用

[root@VM_48_13_centos ~]# /sbin/service crond restart

即可~

起因

曾在大一的时候就听田大佬写了一个每日自动签到的脚本,觉得很牛逼,不过现在看起来确实和当初田大佬说的那样简单>,<,话不多说,直接开始吧。

准备工作

首先这个签到是我学校的一个工作室的内部网站的签到。一开始认为只需要登录了就算签到了(大一不了解的时候),现在知道了,其浏览器上的流程大概是: 打开登录页面 ——> 输入账号密码 ——> 点击登录 ——> 登录成功&自动完成签到; 其内部实现为: 输入网址 ——> 发送get请求 ——> 拿到返回的html并展示 ——> 输入账号密码 ——> 将账号密码放在请求体内通过post请求发送到对应的登录api ——> 拿到对应api所返回的数据(这里我们只需要token) ——> 对签到的api发送一个post请求,将token放入请求头中发送 ——> 签到成功. 那么如何实现以上操作呢?

实现

首先,打开us.ncuos.com(我们内部的网站), f12打开chrome debugger tools,点击network,钩上presever log,然后输入账号密码,点击登录,成功之后右边就会出现一堆请求,我们找到Name为login的包,找到这几项 这里标清楚了请求的url,method和请求体的类型,根据这三个我们可以很简单的写一个模拟登录来拿到对应的token:

var request = require('request') // 引入request包

var contents = {
  username: '613*****',
  password: '******',
  remember_me: false
} // 请求体,目前为一个对象

var options = {
  url: 'http://us.ncuos.com/api/user/login', // 请求的url
  method: 'POST', // 请求的方式 post
  headers: { // 设置请求头
    'Content-Type': 'application/json; charset=utf-8'
  },
  body: JSON.stringify(contents) // 对象JSON化
}

// 发送一个请求,
request(options, (error, response, body) => {
  if (!error && response.statusCode == 200) {
    var token = response.headers.authorization // 响应头里存储着token
    console.log(token)
  }
})

ok,是不是很简单呢,这样我们就拿到了token,就可以为所欲为了啊嘎嘎,比如爬个帖子内容啥的!哦不,回归正题,签到签到,我们再次回到浏览器,我们登录之后还请求了一些别的数据,比如Name为checkin的就是我们要找的签到的api, 由于这个接口是没有请求体的,所以我们不需要类似上面的contents了,只需要在登录之后再发送一个post请求,设置好请求头就可以了,由于代码比较短,就直接放在登录成功后的if语句内:

request(options, (error, response, body) => {
  if (!error && response.statusCode == 200) {
    var token = response.headers.authorization // 响应头里存储着token
    var params = {
      "url": 'http://us.ncuos.com/api/checkin', // 请求url
      "method": 'POST', // 请求方式
      "headers": { // 请求头
        "Content-Type": "Application/json", // 请求体格式
        "Authorization": token // auth token授权
      }
    }
    request(params, (error, response, body) => {
      if (!error && response.statusCode == 200) {
        console.log(body) // 打印出响应体
      } else {
        console.log(error)
      }
    })
  }
})

写好了之后,保存为checkin.js, 执行node checkin.js,发现打印出来的是null,什么情况,为了查看原因,我们将签到请求做出一些修改:

request(params, (error, response, body) => {
  console.log(response.statusCode, response.statusMessage)
  if (!error && response.statusCode == 200) {
    console.log(body) // 打印出响应体
  } else {
    console.log(error)
  }
})

发现打印了 400,forbidden,null,再打印了一下整个response,发现在error里有更加详细的一个报错:

body: ‘{“error”: “InvalidData”, “message”: “invalid json content”, “status”: 400}’ } ‘{“error”: “InvalidData”, “message”: “invalid json content”, “status”: 400}’

很容易看出,error为非法json格式内容。wtf?啥情况,我这个根本不需要请求体啊,为什么还来个这个错误呢,于是走上了漫漫排查之路。

debugger

我首先先尝试了一下console.log(params),发现headers里的Authorization少了引号: 难道是这个的原因吗?然后我尝试了各种方法还是不能将引号加上,不过JSON.stringify(params) 之后是有引号的,所以觉得不是这个问题。苦思冥想无果之后,求助了一下学长,把情况说清楚之后,学长给出了一个尝试建议: 把headers里面的’Content-Type’去掉试试,去掉之后,我靠真的就成功了。之后探其原因是设置请求头中多余地规定了请求体的格式,但是你并没有也不需要发送请求体(对于这个api),但设置了这个请求头之后就强制的要求了你的格式,所以导致上面的报错信息,非法的content。为了验证这个想法,我把Content-type重新加上,写了一个json格式的请求体,里面数据随便填,果然也成功了!至此,我们的这个签到脚本就完成了。最终代码如下:

var http = require('http')
var request = require('request')

var contents = {
  username: 'username',
  password: 'password',
  remember_me: false
}

var options = {
  url: 'http://us.ncuos.com/api/user/login',
  method: 'POST',
  headers: {
    'Content-Type': 'application/json; charset=utf-8'
  },
  body: JSON.stringify(contents)
}


request(options, (error, response, body) => {
  if (!error && response.statusCode == 200) {
    var token = response.headers.authorization
    var params = {
      "url": 'http://us.ncuos.com/api/checkin',
      "method": 'POST',
      "headers": {
        "Authorization": token
      }
    }
    request(params, (error, response, body) => {
      if (!error && response.statusCode == 200) {
        console.log(body)
      } else {
        console.log(error)
      }
    })
  }
});

但是这样每天我们还是需要去自己执行一下这个脚本,还是不如自己手动去登录一下签到呢,所以等下我们就要实现的是 Linux服务器定时任务,可以每日定时执行这个脚本,就可以每日自动签到了,这个留到下一篇博客讲吧~先去睡觉~

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

顺序表

这个很简单,在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/ ‎)

勾起我有想法去写这样一个文章,一是因为我从来没有总结过this的用法,也经常对这个概念有些模糊;二是在学习ES6的时候,被一个简单的例子给弄懵了,感觉自己之前学的好像是假的?例子如下:

var doSomething = () => {
  console.log(this)
}

var obj = {  }

doSomething() // 很明显,打印的是Window对象

var doAnother = doSomething.bind(obj)
doAnother() // Window

doSomething.call(obj) // Window
doSomething.apply(obj) // Window

这下我就很懵逼了,在我之前的认知中this是这样的:

在函数内部时,this指向的是函数运行时所在的上下文,
且通过bind/call/apply可以改变函数内部的this指向,指向其第一个参数(type => Object).

这让我很慌,于是将代码改成了这样:

var doSomething = function () {
  console.log(this)
}

var obj = {  }

doSomething() // Window

var doAnother = doSomething.bind(obj)
doAnother() // obj

doSomething.call(obj) // obj
doSomething.apply(obj) // obj

诶,这个时候又很正常,跟我的理解来看没有偏差,于是认定是箭头函数的关系。 于是去阮一峰看了一下箭头函数的相关描述,又参考了另外几篇博客以及一些例子之后,我觉得自己已经弄得比较明白了,关于上面那题,容我先卖个关子,这篇博客主要目的不在于解决这个问题,而更多的是为了彻底理清this在各种情况以及在普通函数和箭头函数之间表现的差别。所以,我们一步步从简单的开始。


理解this

什么是this呢?很久以前,大概刚学js没多久,我知道js不像c/c++,他是没有指针的,但我记得有人跟我说过,this就相当于一个指针,且这个指针是根据其所处的执行环境不同而指向不同,且

this永远指向的都是一个对象

这条性质决定了我们如何使用this,在定义类中,也就是构造器函数中,我们通常使用this.xxx来定义公共实例变量。在使用对象的时候,我们也经常使用obj.xxx来使用其属性,从用法上来看,点操作符一般只存在于对象中,也可以从侧面再说明this指向的就是一个对象。我们来举个例子来说明:

function Person(name) {
  this.name = name
  console.log(this, typeof this)
}

var jack = new Person('jack') // Person { name: "jack" } "object"

除此之外,还要理解的就是一个概念就是:

在绝大多数情况下,在普通函数内部,this的指向由函数执行的环境决定。
也就是说,this在函数执行期间才被绑定到调用该函数时所处的上下文中,而不是声明时候所处的上下文。

可能上面这句话还不是特别好理解,那么我来举几个例子:

function fn() {
  console.log(this)
}

function wtf() {
  fn()
}

fn() // Window
wtf() // Window

可能有人又会有疑问了: 直接调用fn()很容易理解,因为调用fn所处的上下文为Window对象,所以打印Window,但是调用wtf时,fn明明在wtf的内部调用的啊,为什么不指向wtf呢? 这很容易理解,我们来把上述函数更改一下

function wtf() {
  console.log(this === window) // true
  console.log(window.fn === fn) // true
  window.fn() // Window
  fn() // Window
}

这下就很清晰易懂了,在wtf函数内部调用fn(),他的实际执行上下文仍然为Window对象。 我们再来看一个例子:

// 作为普通函数调用时,this必须指向一个对象。那就是全局对象(在浏览器内是Window对象)。
var getA = function() {
  console.log(this.a)  
}

window.a = 1
getA() // a

// 作为对象属性调用时,this指向的就是该对象
var obj = {
  a: 2,
  getA: function() {
    console.log(this.a)
  }
}
obj.getA() // 2 

var getOtherA = obj.getA // 这里将 function() { console.log(this.a) } 赋给了getOtherA,但它的执行环境仍是全局环境中,其this指向Window
getOtherA() // 1

根据以上的例子我们可以总结出:

在普通函数内部,this总是指向其执行环境上下文中,即要关注该函数的直接调用位置,再换种说法,即关注函数是如何调用的


那么,我们都有哪些调用方法呢?

一、函数调用


来看一个简单的例子介绍函数调用:

function hello(name) {
  return 'Hello ' + name
}

var message = hello('world')
console.log(message) // "hello world"

这样一个函数名加上一个左开括号加上一个逗号分隔的参数表达式再加上一个右开括号,就会执行该函数对象的函数调用。 还有一个高级的是IIFE,立即调用的函数表达式

var message = (function(name) {
  return 'hello ' + name
})('world)
console.log(message) // "hello world"

IIFE也是一个函数调用:第一对括号(function(name) {…})是一个表达式,它计算为一个函数对象,后跟一对带括号的’world’参数:(‘world’)。 理解了函数调用,我们再来看一下this在函数调用中的指向情况:

function test() {
  console.log(this === window)
  this.number = 20
  var number = 30
}

test()
console.log(window.number) // 20

这里的test()为js的函数调用,在执行期间,js将函数内部的this绑定到了全局对象上,即window 所以我们可以用一句话总结:

this在函数直接调用中总指向全局对象,全局对象是由执行环境决定的,在浏览器里,他是window对象

再举个例子,更深的理解这句话:

var obj = {
  name: 'jack',
  action: 'hello',
  doIt: function() {
    console.log(this === obj)
    function strConcat() {
       console.log(this === obj)
       return this.action + ' ' +this.action
    }
    return strConcat()
  }
}

var msg = obj.doIt() // true, false
console.log(msg) // "hello jack"

调用obj.doIt时,由于他是方法调用(在后面会说),显然doIt函数的上下文是obj对象,strConcat函数是doIt里面定义的,你可能会想它和doIt一样,this也指向obj。 其实不然,我们在看我们的那句话,函数调用的this指向全局对象,而在这里就是window,即使外部函数doIt有着obj作为函数对象,在这里也不会影响strConcat中this的指向。

函数调用的常见陷阱this是被认为在内部函数中与外部函数相同。
正确的应该是内部函数的上下文仅依赖于调用,而不依赖于外部函数的上下文。