C 和 C++ 支持 4 种基本数据类型（整型、浮点型、字符型、布尔型）和 3 种复合型数据类型（数组、指针、结构）。复合类型的数据对于数据结构至关重要，因为从某种程度上来说数据量的多少和数据结构的好坏决定了程序的复杂程度和程序结构的好坏。而数据结构基本可以抽象成数据对象之间的联系，其中，结构适合描述数据对象，指针适合描述数据对象之间的联系，数组适合描述同类型对象之间的特殊联系（有序连续存放）。数据结构一般分为线性结构和非线性结构。
本实训项目的主要目标是通过构建线性表来学习和掌握 C 和 C++ 中使用结构和指针构建复杂数据结构的方法。主要内容包括顺序、逆序以及排序构建线性表，查找指定元素，删除指定结点，求线性表的长度，栈，队列和集合。

总共包括以下关卡。

第1关顺序构建线性表

本关任务：按照数据输入的顺序构建一个线性表。即如果输入的3个结点数据分别为1、2、3，则构建的线性表包含3个结点，且从前往后的结点数据分别为1、2、3。
为了完成本关卡任务，你需要掌握：

线性表的特性；
线性表的一般操作；
线性表的表示方法。
线性表（linear list）是一种数据结构，是由 n 个具有相同特性的数据元素构成的序列。

线性表中元素的个数 n 即为线性表的长度，当 n = 0 时称为空表。线性表的相邻元素之间存在着序偶关系。

如用（ a[0] ，…… ，a[i-1] ，a[i] ，a[i+1] ，…… ，a[n-1] ）表示一个线性表，则称 a[i-1] 是 a[i] 的前驱，a[i+1] 是 a[i] 的后继。

线性表的特性

线性表中必存在唯一的一个“第一元素”；

线性表中必存在唯一的一个“最后元素” ；

除最后一个元素之外，均有唯一的后继；

除第一个元素之外，均有唯一的前驱。

线性表的一般操作

将线性表变为空表；

返回线性表的长度，即表中元素个数；

获取线性表某位置的元素；

定位某个元素在线性表中的位置；

在线性表中插入一个元素；

删除某个元素；

判断线性表是否为空；

遍历输出线性表的所有元素；

线性表排序。
线性表可以用链表来实现。链表是通过指针链接在一起的一组数据项（结点）。

链表的每个结点都是同类型的结构，该结构中一般包含两类信息：

数据域，存储业务相关的数据（如财务系统的数据域为财务信息，车辆管理系统的业务信息为车辆信息）；

指针域，用于构建结点的链接关系。单链表的实现只需要一个指针。

由于数据域跟线性表的构建无关（靠指针域就够了），所以本关所有程序的实现中线性表的数据域都只有一个整数。

单链表的形式如下：

如上图所示，该单链表共包含了4个结点，4个结点的数据域分别是28、52、2、96。每个结点还包含一个指针，指向下一个结点。最后一个结点的指针域置为“NULL”，表示后面没有结点了。

第一个结点的地址存放在一个指针变量 head 中（ head 指向链表第一个结点， head 本身不是一个结点）。访问该单链表只需要知道 head 的值就可以了，因为通过 head 可以访问到第一个结点，通过第一个结点的指针域可以访问第二个结点 …… 直到访问链表中所有的结点。
要实现上述链表，只需要定义如下结构：

// 定义结点结构
struct node
{int data;     // 数据域node * next;     // 指针域，指向下一个结点
};

如下程序可以构建上述图中链表（其中：每个结点都是 node 类型的一个结构变量，head 则是node*类型的指针）：

node a, b, c, d, *head;
head = &a;     // 让 head 指针指向结点 a
a.data = 28;     // 给 a 的数据域赋值
a.next = &b;     // 让 a 的指针域指向结点 b
b.data = 52;  b.next = &c;     // 给 b 的数据域赋值，并让 b 的指针域指向结点 c
c.data = 2;  c.next = &d;     // 给 c 的数据域赋值，并让 c 的指针域指向结点 d
d.data = 96;  d.next = NULL;     // 给 d 的数据域赋值，并将 d 的指针域置为 NULL，表示后面没有节点。

很显然，这样写程序比较麻烦，而且在不知道有多少结点的情况下也根本无法处理。怎么可以解决这个问题呢？

C 和 C++ 的内存动态分配方法可以很好的解决这个问题。C++ 提供了两种动态分配内存的方法：

C 语言提供的 malloc 和 free 函数，代码如下：

node *t = (node *)malloc(sizeof(node));
t->data = 2;
free(t);

sizeof 是一个运算符，sizeof(node)用于计算并返回一个 node 类型变量所占内存空间的大小（字节数）；

malloc(int n)用于申请动态分配 n 个字节大小的数据空间，并返回该空间的首地址；

(node )是类型转换运算符，malloc 函数返回的地址是void类型，转换成node类型后赋值给指针变量 t（ t 的类型是node）。

所以上面第一条语句执行后，指针 t 指向一块动态分配的内存空间，该空间大小为一个 node 类型变量的大小。

第二条语句通过指针 t 访问该空间（当作 node 变量）的数据域 data，给它赋值为2。free 函数用于释放 t 指向的动态分配空间（不需要该空间后再释放）。
C++ 扩展的 new 和 delete 运算符，代码如下：

node *t = new node;
t->data = 2;
delete t;

那么使用动态内存分配的方法实现上述的单链表的代码如下：

node *head, *t, *p;
t = new node;     // 动态分配一个 node 结点的空间，并让 t 指向它
head = t;     // 该结点是第一个结点，让 head 指向它
t->data = 28;     // 给第一个结点的数据域赋值
p = new node;     // 动态分配第二个 node 结点的空间，并让 p 指向它
t->next = p;     // 修改第一个结点的指针域为第二个结点的地址（第一个结点的指针域指向第二个结点）
p->data = 52;     // 给第二个结点的数据域赋值
t=p;     // 让 t 指向最后一个结点
p = new node;     // 动态分配第三个 node 结点的空间，并让 p 指向它（ p 不再指向第二个结点了）
t->next = p;     // 修改第二个结点的指针域为第三个结点的地址（第二个结点的指针域指向第三个结点）
p->data = 2;     // 给第三个结点的数据域赋值
t = p;     // 让 t 指向最后一个结点
p = new node;     // 动态分配第四个 node 结点的空间，并让 p 指向它（ p 不再指向第三个结点了）
t->next = p;     // 修改第三个结点的指针域为第四个结点的地址（第三个结点的指针域指向第四个结点）
p->data = 96;     // 给第四个结点的数据域赋值
p->next = NULL;     // 给第四个结点的指针域置为 NULL，表示后面没有结点了

上述程序语句虽然好像变多了，程序也好像变复杂了，但细读会发现这段程序可以很方便地改成循环，这样处理后其实是使得程序更简单了，并且适用于任意多个结点的情况。

改成循环后，单链表里面可能包含0个或多个结点，如果包含多个结点，则下面程序中的语句可以让指针 t 指向链表的最后一个结点，具体代码如下：

node *t = head; // t 指向第一个结点
// 如果 t->next 不为 NULL，即后面还有结点
while(t->next != NULL)
{
t = t->next; // 把 t 指向结点的指针域（下一个结点地址）赋值给 t，t 指向下一个结点
}
// 循环结束时，t->next 为 NULL，即 t 指向的结点后面没有结点了。

完整代码解析

#include "linearList.h"node *insertTail(node *h, node *t)
{// 请在此添加代码，补全函数insertTail/********** Begin *********/if(h == NULL) // 空链表单独处理{t->next = NULL; // 链表尾指针置为NULLreturn t; // 返回第一个结点的地址（即链表头指针）}// 非空链表的情况node *p = h;// 让p指向最后一个结点while(p->next){p = p->next;}p->next = t; // 让最后一个结点的指针域指向结点tt->next = NULL; // 链表尾指针置为NULLreturn h;  // 返回第一个结点的地址（即链表头指针）/********** End **********/
}

第2关逆序构建线性表

相关知识

在介绍如何将一个结点插入到一个链表头部之前，我们先假设该链表头指针为 head，则 head 中存放着链表当前头结点的地址。

如果要将指针变量 t 指向的新结点插入到链表头部，其实只需要将原来的头结点的地址存入 t 指向结点的指针域（也就是让 t 指向结点的指针域指向原来的头结点），然后 t 指向的新结点就成了新的头结点了。那么，如何将原来的头结点的地址存入 t 指向结点的指针域？

t 指向结点的指针域可以用t->next访问，原来头结点的地址在 head 中，所以下面的语句可以实现这个功能：

t->next = head;

又由于新结点（ t 指向的结点）是新的头结点，其地址必须存入头指针 head 中，而 t 指向结点的地址存放在指针变量 t 中，所以下面的语句可以实现这个功能：
head = t;

完整代码解析

#include "linearList.h"node * insertHead(node *h, node *t)
{// 请在此添加代码，补全函数insertHead/********** Begin *********/t->next = h->next;h->next=t;return t;/********** End **********/
}

第3关排序构建线性表

本关任务：补全 insertSort 函数，实现将一个结点按结点数据 data 从小到大的顺序插入到一个有序链表中。根据插入结点 data 的大小，插入点可能是链表头、尾或者中间某个位置。
为了完成本关卡，你需要掌握：

如何找到插入点；
如何插入结点。
以上两点也是实现本关任务的两个关键步骤。
插入点的定位可以使用两个指针（ p 和 q ），定位步骤如下图所示：

上图中链表有4个结点，则共有5个可能的插入点。

用两个指针首先定位第一个插入点（ step1 ，p 为 NULL ，q 指向第一个结点），如果插入结点的 data 小于 q 指向结点的 data ，则就是该插入点（两个指针指向的结点之间），否则两个指针一起往后移动（ step2 ）；定位第二个插入点，判断条件依然是插入结点的 data 是否小于 q 指向的结点的 data，是则就是该插入点，否则两个指针往后平移（ step3 ）；定位第三个插入点，…… ，直到最后当 q 指针为“NULL”时，说明插入结点的 data 比链表中所有数据都大，则插入点应该是链尾（第五个插入点）。插入点的定位操作可以很容易地用循环实现。

定位好插入点后，当 p 为“NULL”时，插入点是链表头部；当 q 为“NULL”时，插入点是链表尾部；否则，插入点为 p 和 q 指向的两个结点之间。
上述定位好插入点后，接下来是插入结点。对于头部插入和尾部插入的内容前两关已做过介绍，本关只介绍中间插入的情况，即将 t 指向的结点插入到 p 和 q 指向的两个结点之间。

这种情况只需要让 p 指向结点的指针域指向 t 指向的结点， t 指向结点的指针域指向 q 指向的结点即可。具体参见下面代码：

p->next = t;
t->next = q;

完整代码解析

#include "linearList.h"node * insertSort(node *h, node *t)
{// 请在此添加代码，补全函数insertSort/********** Begin *********/node *p = NULL, *q = h;  // 定位第一个插入点：链首// 查找插入点while(q && q->data < t->data){// 两个指针并行后移p = q;q = q->next;}// 插入链首if(p == NULL){t->next = h;return t;}// 插入链尾if(q == NULL){p->next = t;t->next = NULL;}// 插入p、q之间t->next = q;p->next = t;return h;/********** End **********/
}

第4关查找元素

本关任务：补全 search 函数，实现在一个链表中搜索包含指定数据的结点。如果链表中有多个结点包含该数据，则返回第一个。

相关知识
遍历列表元素
在线性表中查找特定元素是线性表的常用操作之一。由于链表结点都是动态内存分配得到的，在内存中不是连续存储，没法使用二分法之类的算法来实现信息检索，但可以使用顺序查找的方法。

顺序查找需要遍历整个链表，逐个检查每个结点是否满足条件。下面 printList 函数则可以遍历链表元素。

// 函数printList：输出链表，每个数据之间用一个空格隔开
// 参数：h-链表头指针
void printList(node *h)
{cout << "List:";while(h){    // h 为真，即 h 指向的结点存在，则输出该结点的数据cout << " " << h->data;     // 输出结点数据h=h->next;     // 将该结点的指针域赋值给 h，h 就指向了下一个结点}cout << endl; // 输出换行符
}

完整代码解析

#include "linearList.h"node * search(node * h, int num)
{// 请在此添加代码，补全函数search/********** Begin *********/while(h){// h为真，即h指向的结点存在if(h->data == num){return h;} h = h->next;  // 将该结点的指针域赋值给h，h就指向了下一个结点}return NULL; // 没找到包含num的结点/********** End **********/
}

第5关删除指定位置的结点

本关任务：补全 delAt 函数，实现根据指定位置删除链表中对应的结点。
线性表的结点是有序号的，包含 n 个结点的线性表从链头到链尾的结点序号分别为0、1、…… 、n−1。删除线性表指定位置的操作也是常用的功能。

结点的删除可以根据结点位置的不同分为三种情况：删除链首结点、删除链尾结点、删除中间结点。

回答以下几个问题，解决本关问题就不难了：

删除链首结点后，原来序号为1的结点成为新的链首结点，链表头指针也应该存储该结点的地址，该结点的地址原来存放在哪？

删除链尾结点后，原来序号为n−2的结点成为新的链尾结点，该结点的指针域也应该置为“NULL”，表示链表的结束。怎么访问序号为n−2的结点的指针域？

删除中间结点只需要将其前面结点的指针域修改为其后面结点的地址即可。例如删除序号为i的结点，需要将序号为i−1的结点的指针域修改为序号为i+1的结点地址。怎么访问序号为i−1的结点的指针域？序号为i+1的结点地址存放在哪？

完整代码解析

#include "linearList.h"node * delAt(node * h, int i)
{// 请在此添加代码，补全函数delAt/********** Begin *********/
if(h==NULL){return h;
}
if(i==0){node *temp=h;h=h->next;free(temp);return h;
}
node *current=h;
int count=0;
while(current->next!=NULL&&count<i-1){current=current->next;count++;
}
if(current->next==NULL){return h;
}
node *temp=current->next;
current->next=current->next->next;
if(temp->next==NULL){current->next=NULL;
}
free(temp);
return h;/********** End **********/
}

第6关删除包含特定数据的结点

本关任务：补全 delHas 函数，实现删除链表中包含特定数据的结点，如果有多个这样的结点，只删除第一个。

删除链表的结点时，有时候不知道结点在哪，只知道结点数据的特征，如删除成绩低于60的学生结点、删除学号为20160903的学生等。

提示程序是可以凑出来的，之前已经完成了一些函数，有些函数的功能这里可以借鉴。例如 delAt 可以删除某个序号的结点，本关可以先搜索链表，查找包含数据 n 的第一个结点的序号，找到了则调用 delAt 函数删除它。

也可以用另外一种方法，结合 search 函数和 delAt 函数的部分功能，使用指针对要删除的结点进行定位，定位后根据结点位置（指针信息可以反映出要删除的结点在链首、链中或者链尾），然后直接删除。

完整代码解析

#include "linearList.h"node * delHas(node * h, int n)
{// 请在此添加代码，补全函数delHas/********** Begin *********/
node *p=NULL;
node *c=h;
while(c!=NULL){if(c->data==n){if(p==NULL){h=c->next;}else{p->next=c->next;}free(c);break;}p=c;c=c->next;
}
return h;/********** End **********/
}

第7关线性表长度

本关任务：编写 listLength 函数来求线性表的长度。

温馨提示：建议在开始你的任务前，先仔细阅读右侧“文件目录”下提供的 step7/linearList.h 和 step7/test.cpp 两个文件，对整个程序有一个全面的了解，再动手完成任务！

完整代码解析

#include "linearList.h"int listLength(node * h)
{// 请在此添加代码，补全函数listLength/********** Begin *********/
int c=0;
node *p=h;
while(p!=NULL){c++;p=p->next;
}
return c;/********** End **********/
}

第8关线性表应用一：栈

本关任务：用前面已经实现的线性表来实现一个整数栈（栈里的数据是整数）。共需要补全三个函数（也是栈的基本功能）：判断栈空的 empty 函数、压栈的 push 函数和弹栈的 pop 函数。

栈（ stack ）又名堆栈，是一种功能受限的线性表，具有先进后出的特性。

其限制为仅允许在线性表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。

向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；

从一个栈删除元素又称作出栈、弹栈或退栈，它是把栈顶元素删除掉，使其下面的元素成为新的栈顶元素。

接下来首先声明结构类型：

// 定义结点结构
struct node
{int data;     // 数据域node * next;     // 指针域，指向下一个结点
};
typedef node * intStack;  // 定义类型别名，intStack 即相当于 node*

定义 intStack 是为了使程序的可读性更好一些。因为本关是用线性表实现栈，而访问一个线性表其实只需要一个链表头指针就可以了，intStack 实际上就是node*类型，所以后面可以这样声明栈 sk ：

intStack sk = NULL;     // 声明栈 sk，并初始化为空栈（空线性表）

实际上 sk 就是一个node*类型的指针，用它可以访问一个线性表，也就可以看成一个栈了。

完整代码解析

#include "mstack.h"
// 函数empty：判断栈sk是否为空
// 参数：sk-栈
// 返回值：true-sk为空，false-sk不为空
bool empty(intStack sk)
{// 请在此添加代码，补全函数empty/********** Begin *********/return sk == NULL;/********** End **********/
}
// 函数pop：弹栈
// 参数：sk-栈，传引用，弹栈可能会改变sk的值
// 返回值：弹栈的弹出的整数，如果栈空，返回-1
int pop(intStack &sk)
{// 请在此添加代码，补全函数pop/********** Begin *********/if (sk == NULL) {return -1;}int value = sk->data;intStack temp = sk;sk = sk->next;delete temp;return value;/********** End **********/
}
// 函数push：压栈，将整数n压入栈sk中
// 参数：sk-栈，传引用，压栈会改变sk的值，n-要压栈的整数
// 返回值：无，采用链表实现栈，只要还有内存，压栈都会成功
void push(intStack &sk, int n)
{// 请在此添加代码，补全函数push/********** Begin *********/intStack newNode = new node;newNode->data = n;newNode->next = sk;sk = newNode;/********** End **********/
}

第9关线性表应用二：队列

本关任务：用前面已经实现的线性表来实现一个整数队列（队列里的数据是整数）。共需要补全三个函数（也是队列的基本功能）：判断队列空的 queueEmpty 函数、入列的 enQueue 函数和出列的 deQueue 函数。
队列是一种功能受限的线性表，具有先进先出的特性。队列仅允许从一头出列（这一头称为队列头），从另外一头入列（队列尾）。

入列操作是将结点插入到队列尾（该结点称为新的队列尾）；

出列操作是从队列头删除头结点，并获取删除节点的数据（原头结点的后继结点为新的头结点）。

接下来首先声明结构类型：

// 定义结点结构
struct node
{int data;     // 数据域node * next;     // 指针域，指向下一个结点
};
typedef node * intQueue;  // 定义类型别名，intQueue 即相当于 node*

定义 intQueue 是为了使程序的可读性更好一些。因为本关是用线性表实现队列，而访问一个线性表其实只需要一个链表头指针就可以了，intQueue 实际上就是node*类型，所以后面可以这样声明队列 iq ：

intQueue iq = NULL;  // 声明队列 iq，并初始化为空队列（空线性表）

实际上 iq 就是一个node*类型的指针，用它可以访问一个线性表，也就可以看成一个队列。

完整代码解析

#include "mqueue.h"// 函数queueEmpty：判断队列iq是否为空
// 参数：iq-整数队列
// 返回值：true-队列iq为空，false-iq不为空
bool queueEmpty(intQueue iq)
{// 请在此添加代码，补全函数queueEmpty/********** Begin *********/ return iq == NULL;/********** End **********/
}
// 函数enQueue：将整数num入列到iq
// 参数：iq-整数队列，传引用，入列有可能改变队列头指针，num-入列的整数
// 返回值：无，只要还有内存，入列总会成功
void enQueue(intQueue &iq, int num)
{// 请在此添加代码，补全函数enQueue/********** Begin *********/intQueue newNode = new node;newNode->data = num;newNode->next = NULL;if (iq == NULL) {iq = newNode;} else {intQueue tail = iq;while (tail->next != NULL) {tail = tail->next;}tail->next = newNode;}/********** End **********/
}
// 函数deQueue：出列
// 参数：iq-整数队列，传引用，出列有可能改变队列头指针
// 返回值：出列结点的数据，如果队列为空，返回-1
int deQueue(intQueue &iq)
{// 请在此添加代码，补全函数deQueue/********** Begin *********/if (iq == NULL) {return -1;}int value = iq->data;intQueue temp = iq;iq = iq->next;delete temp;return value;/********** End **********/
}

第10关线性表应用三：集合

本关任务：使用线性表实现集合的表示及操作。具体需要补全三个函数：计算集合并集的 unionSet 函数、计算集合交集的 intersection 函数和向集合中添加元素的 addElement 函数。

集合是数学中一个基本概念，它是集合论的研究对象。朴素集合论中，集合的定义就是“一堆东西”，集合里的“东西”，称为元素。

下面介绍几个集合的知识点：

集合中的元素是无序的，对于任意的集合S1和S2，S1=S2当且仅当对于任意的对象a，都有若a∈S1，则a∈S2；若a∈S2，则a∈S1；

集合中的元素互不相同，空集合是没有任何元素的集合；

集合的并集定义为：A∪B=x∣x∈A或x∈B。例如，A={1，3，5}，B={1，2，5} ，则A∪B= {1，2，3，5} ；

集合的交集定义为：A∩B=x∣x∈A且x∈B。例如， A= {1，3，5}，B={1，2，5} ，则A∩B= {1，5} 。

接下来首先声明结构类型：

// 定义结点结构
struct node
{int data;     // 数据域node * next;     // 指针域，指向下一个结点
};
typedef node * intSet;     // 定义类型别名，intSet 即相当于 node*

上述结构类型的声明中定义 intSet 是为了使程序的可读性更好一些。因为本关是用线性表实现集合，而访问一个线性表其实只需要一个链表头指针就可以了， intSet 实际上就是node*类型，所以后面可以这样声明集合 a ：

intSet a=NULL;     // 声明集合 a，并初始化为空集合（空线性表）

在右侧编辑器中的Begin-End之间补充代码，完成 unionSet、intersection 、addElement 三个函数，以实现集合的三个功能。具体要求如下：

函数 unionSet 计算并返回集合 a 和 b 的并集。参数 a 和 b 是两个集合，返回值为 a 和 b 的并集。

函数 intersection 计算并返回集合 a 和 b 的交集。参数 a 和 b 是两个集合，返回值为 a 和 b 的交集。

函数 addElement 将元素 num 加入到集合 is 中，如果 is 中已经存在 num 了，则不需要加入，不存在则加入。参数 is 是一个集合，num 是要加入到 is 中的元素。

温馨提示：可以使用线性表已有的功能来实现这些函数。具体提供的函数请从“文件目录”中查看step10/LinearList.cpp、step10/LinearList.h、step10/mset.h和step10/test.cpp。

完整代码解析

#include "mset.h"// 函数unionSet：求集合a和b的并集
// 参数：a-集合，b-集合
// 返回值：集合（集合a和b的并集）
intSet unionSet(intSet a, intSet b)
{// 请在此添加代码，补全函数unionSet/********** Begin *********/intSet result = NULL;intSet current = a;// 将集合a中的元素添加到结果集合中while (current != NULL) {addElement(result, current->data);current = current->next;}current = b;// 将集合b中的元素添加到结果集合中while (current != NULL) {addElement(result, current->data);current = current->next;}return result;/********** End **********/
}
// 函数intersection：求集合a和b的交集
// 参数：a-集合，b-集合
// 返回值：集合（集合a和b的交集）
intSet intersection(intSet a, intSet b)
{// 请在此添加代码，补全函数intersection/********** Begin *********/
intSet result = NULL;intSet currentA = a;// 遍历集合a，检查元素是否也在集合b中while (currentA != NULL) {intSet currentB = b;bool found = false;while (currentB != NULL) {if (currentA->data == currentB->data) {found = true;break;}currentB = currentB->next;}if (found) {addElement(result, currentA->data);}currentA = currentA->next;}return result;/********** End **********/
}
// 函数addElement：在集合is中增加元素num
// 参数：is-集合，num-要增加的元素
// 返回值：无
void addElement(intSet &is, int num)
{// 请在此添加代码，补全函数addElement/********** Begin *********/intSet current = is;bool exists = false;// 检查元素是否已存在于集合中while (current != NULL) {if (current->data == num) {exists = true;break;}current = current->next;}// 如果元素不存在，则添加到集合中if (!exists) {intSet newNode = new node;newNode->data = num;newNode->next = is;is = newNode;}/********** End **********/
}