本系列收藏夹 https://cowlevel.net/collection/3932815
爱发电！https://afdian.net/@kingfeng

数据结构

数据结构，其意义在于“组织数据的方式”，他或许是购物清单，或许是一张记录货物位置的仓库清单，又或许是一张你家城市的地图。
需要注意的是，数据结构并不是某种语言所提供的特定功能，而是独立于语言外的一些技巧，也就是说并不会因为某种语言不支持或者有其他替代品而无法使用某些特定数据结构，但出于效率考虑，或许这些替代品拥有更好的性能。

顺序表

概念

一张作文纸，上面有一个个小方块用来让你填入一个个文字，这些文字实际是相连的 即“物理类上相邻”同时，每个文字与其周围的文字在关系上是前后关系，即“逻辑上相连”。其名字中的“顺序”并不代表其是“有序的”而是描述表元素之间的关系。（顺序表当然有序，因为顺序表是有序表的一种）

功能

如图所示，一个简单的表

1 4 15 6 3 8 20 58

这个表提供了诸多信息，例如

• 第四个数是6
• 第五个数是3
• 第四个数字6后面是第五个数字3

我想这些信息你甚至都不需要经过思考就可以从中获取到，毕竟这就是我们使用表的最基本的功能 但将其数据化后，你或许有些新的发现

首先，他提供了一个连续数字对应一个特定序列的方法，就像一个编好号码的购物清单

1、西红柿
2、黄瓜
3、洋葱
4、鸡胸肉
5、料酒

在编号之后，程序就可以使用一个不断自我增加的循环来定位这些信息。而不需要单独为每个信息定制一个变量，在人工的写一系列判断语句来确定所指定的变量。

其次，其具有顺序性，这使得其可以存储一些有顺序的东西，例如排好序的一系列数字，或是一串字符"Hello World"而不会丢失其顺序。

最后，其还是一个包，就像是杂乱无章的笔记本，你可以随你喜欢的把东西一股脑的放进去

使用

在程序之中，我们会使用两种方法来表示顺序表中的元素，我会详细讲明这两种方式

下标式

如同语言中的第x行第y个一样，我们可以使用下标来标记，就像a[3][4]，但需要注意的是，在程序中是从0开始计数的，也就是a[0]是实际上的第一个元素。

偏移式

如同我们在指路时所使用的，右数x个，y个路口之后，程序同样可以使用一个偏移，用类似 *(a+9)或者 *(a+10)来表示顺序表中某个位置的数据

数组

C++包含有两个数组，分别是内置数组，和std::Array，我们会在接触类以后再仔细学习std::Array或者类似的标准库函数，现在我们仅把范围限定在内置数组上。

声明

当你需要在C中声明一个数组，你需要遵循如下格式

类型 数组名[数组大小]

其中，类型为数组中数据的类型，而数组大小则为该类型数据的数量。在声明之后，我们应对数组进行一次初始化。

//int arr[]; 错误，未写明大小
int arr[10]; //正确，但未初始化，其内容是随机的
int arr[] = {1, 2, 3} //C语言会根据初始化内容自动识别大小，但这个大小在后续程序中无法变更
int arr[10] = {1} //进行了初始化，arr[0] 为1, 其余被自动初始化0

使用花括号的这种方法，仅可被用在声明语句之中，在赋值时无法被使用

读取

下标式

前文中的下标表示表中元素的方法，实际上就是数组的下标表示格式。
其具体形式为 数组名[下标（从0开始）]

偏移式

偏移式表示为 (数组名 + 偏移量（从0开始）) 在此处，程序所理解的数组名实际上是数组所在空间的起始位置，将其进行偏移一定数量个内存，并使用表达式符号中 取地址中的值 运算，来达到读取该处内容的目的

危险

不管是下标还是偏移，C语言实际上不会检查是否存在越界现象，即在声明语句中声明了a[3]，理论上数组a实际所控制的范围是a[0], a[1], a[2]，但C语言允许你访问a[3]的内容，其内容是在连续的内存中紧挨着数组a存储的变量，如果由于编程者的失误，导致程序在a[3]的位置写入了数据，编译器并不会回报错误，但这会导致程序的bug

数组与表的关系

或许你可以理解为，编程语言与某个特定数据结构的关系。
我前文中说过，数据结构是一种储存数据的技巧，其并非与某个编程语言或某个编程特性挂钩。

就如本次的内容-顺序表举例，如果你作为编程者，需要存储的只是数个标志位，就像我们课题中所需要的-连续十道题中有六道题目回答正确，你可以选择用一个布尔数组，你同样也可以使用一个大于10位的类型比如int，并编写程序识别其各个二进制位的值，并将其作为一个“ 数组 ” 来操作。我如此举例并不代表这样做会使得程序更加优秀，而只是作为一个例子来阐述数据结构与编程语言的关系

特点

• V 结构简单
• V 线性化一系列数据
• V 效率更高
• X 存在危险性
• X 不可扩容，容量预先设定

操作

新建一个源代码文件，初始化其中的几个数字，这将作为我们这阶段的示例。

声明

数组的大小是固定的，因此再多数情况下，编程者需要为其预留数个空位，并记录其已经使用的数量。
我们可以使用 define 指令来定义一个全局的最大值，以方便修改和记录数组最大值。

#include <cstdio>
#define ARRAY_MAX 10
int main()
{
    int a[ARRAY_MAX] = {0, 1, 2, 3, 4, 5};
}

我会在后续的《预编译指令》部分详细说明这样写的具体格式与特点。
C语言的规范中支持使用变量来声明数组大小，但完全不推荐这样做，因为这样做会使得错误几率急剧上升。
不论你使用什么方法声明数组，你都可以通过sizeof来计算数组的容量

sizeof(a)/sizeof(int)

其中，a为数组名，int为数组的元素数据类型

由于数组本身无法扩容，很多情况下我们需要为后续的数据预留空位，并使用一个变量来记录数组已经存储的数量

#include <cstdio>
int main()
{
    int a[10] = {0, 1, 2, 3, 4, 5};
    int a_last = 5;//用以记录数组已存储的最后一个数
    int i; //用以循环
}

这同样并不是必须的，你也可以自行规定一个数组的“结束标记”来表明数组已存储的内容结束于此。

遍历

我们通常使用循环来遍历一个数组，对于我们示例中的数组通常使用

for(i=0; i <= a_last; i++){
    printf("%d ", a[i]);
}

使用一个for循环，每次循环会输出 a[i] 的数据，i从0循环到我们存储的最后一个数 a_last
你可以再main的最后保留这段代码，来确认其他操作对数组的变化

增加

在尾部增加

if(a_last < (sizeof(a) / sizeof(int) - 1)){ 
    /* sizeof(a) / sizeof(int) 为数组的容量
     * 因为数组是从0 计算的，一个容量为 10 的数组其最大下标为 9
     * 因此 sizeof(a) / sizeof(int) - 1 为 a_last 的最大下标
     * 这时， a_last 需要小于这个值，数组之后才有空间插入新值 
     */
    a_last += 1;
    a[a_last] = 10;
    // 在末尾加入一个新数 10
}

其结果为 0 1 2 3 4 5 10
如果你希望在数组存储满的时候显示一条消息来提示这个错误，可以在if后面加入else块并显示对应错误信息

插入

在插入一个元素的时候，且需要保留原有顺序的时候（如果我们的数组不需要顺序，那为什么不把新元素放在末尾呢？），我们需要遍历数组并将插入点以后的所有数据向后移，假设我们要在三号下标插入一个11

if(a_last < (sizeof(a) / sizeof(int) - 1)){ 
    // 我们同样需要确保插入的数字不会超过最大值
    a_last += 1;
    for(i=a_last; i>3; i--){
        // 我们需要把包括3在内的所有数字向后移一
        a[i] = a[i-1];
    }
    a[3] = 11;
}

删除

在末尾删除

我们需要做的是和在末尾增加相反的操作，即 a_last -= 1，但相对的，if内的条件判断也需要修改，判断a_last 有没有超过下界，即有没有超过0

在中间删除

与插入类似，操作同样是相反的，即从删除点下标循环至 a_last -1 并把其后一位的内容向前挪一格

更为聪明的删除技巧

当你的数组是无顺序的，你可以直接将处在末尾的数据与将要被删除的数据交换，并剔除交换后的末尾

a[3] = a[a_last];
a_last -= 1;

这会改变数组的顺序，但其操作速度远高于在中间删除的操作

修改

修改

我们可以直接修改某个元素的值

交换

我们需要一个中间变量来储存这个值,以完成交换

temp = a[0];
a[0] = a[1];
a[1] = temp;

交换两个普通变量的操作与此相同

查询

查询（已知下标求值）

我们可以直接通过下标来读取数组中某个元素的值

搜索（已知值求下标）

我们需要循环整个数组，直到找到我们要的值，亦即循环起始于0，结束于找到目标，或数组循环完成

for(i=0; i<=a_last && a[i]!=10; i++)
      //从0循环至 a_last 而且当a[i]的值等于10时结束循环
    ; //循环体为空，这个分号可以直接写在for同行，如果忘记分号for会循环执行其后紧跟第一条语句
printf("%d \n", i);
    //如果i时在for循环内声明的，根据C语言的规范i只会存活在for循环内部，若我们需要i作为循环结果，需要在for循环外声明i

这个例子仅仅展示了确定数字，若希望搜索的数据具有某种特征（如字符串的搜索）可以把条件判断作为循环体，并在适当时刻使用break语句跳出循环，多个搜索结果亦可使用一个新的数组进行存储。

最后，我的程序看起来象是这样

#include <cstdio>
int main()
{
    int a[10] = {0, 1, 2, 3, 4, 5};
    int a_last = 5;//用以记录数组已存储的最后一个数
    int i;
//在末尾增加数字 10
    if(a_last < (sizeof(a) / sizeof(int) - 1)){ 
        /* sizeof(a) / sizeof(int) 为数组的容量
        * 因为数组是从0 计算的，一个容量为 10 的数组其最大下标为 9
        * 因此 sizeof(a) / sizeof(int) - 1 为 a_last 的最大下标
        * 这时， a_last 需要小于这个值，数组之后才有空间插入新值 
        */
        a_last += 1;
        a[a_last] = 10;
        // 在末尾加入一个新数 10
    }else{
        puts("Array is full");
    }

//在3号下标插入11
    if(a_last < (sizeof(a) / sizeof(int) - 1)){ 
        // 我们同样需要确保插入的数字不会超过最大值
        a_last += 1;
        for(i=a_last; i>3; i--){
            // 我们需要把包括3在内的所有数字向后移一
            a[i] = a[i-1];
        }
        a[3] = 11;
    }
//删除3号下标内的数据
    a[3] = a[a_last];
    a_last -= 1;
//查询 10的下标
    for(i=0; i<=a_last && a[i]!=10; i++)
        //从0循环至 a_last 而且当a[i]的值等于10时结束循环
        ; //循环体为空，这个分号可以直接写在for同行，如果忘记分号for会循环执行其后紧跟第一条语句
    printf("%d \n", i);

//输出整个数组
    for(i=0; i <= a_last; i++){
        printf("%d ", a[i]);
    }
}

课题

我们已经讲述完成了数组的基本操作，打开我们的数字加减法测验程序，并为其加入

连续十道题中需至少正确六道才可完成测验

我们首先需要一个个“评分”数组，我决定使用布尔类型，容量为10的数组，并令其不断循环记录，即第11个题目会覆盖第1个题目的评分，来记录“连续十个分数”

也因此，我们需要增加一个变量统计一共进行了多少个题目，和一个变量统计一共有多少题目是正确的

    bool mark[10]={};
    int count_problem=0;
    int count_mark=0;

然后我们需要修改循环结束的条件，其本来结束于循环十次后，将其修改，为结束于count_mark >= 6 即 count_mark < 6时继续循环 while(count_mark < 6 ){}

我们要做的事情还有两个，分别是将每道题的结果记录进评分数组中，以及通过一个遍历mark数组的循环来更新count_mark的值

提示： 你可以通过count_problem 与10 取余，来将一个0~N范围的数字对应为0~9的数组使用的下标，记得在每道新题目的末尾更新，使得count_problem增加1

在评论里交流你的答案把！