第10章 基本数据结构
本章重点
· 栈
· 队列
· 链表
在前面的章节中讲解了C语言的基础知识、数组、指针、流程控制等，在C语言中还有一些基本的数据结构，如栈、队列和链表，这些数据结构有着自己的特性，合理利用这些数据结构可以在程序中起到事半功倍的效果，本章将针对这些基本的数据结构进行详细地讲解。
栈
在现实生活中经常会完成一些"后进先出"的动作，例如一群人排队等一个电梯，当电梯门打开后，排在队首的人先进入电梯，排在队末的人最后进入电梯，当电梯停止时，后进入电梯的人就会先下去，先进入电梯的人后下去。在C语言中有一种数据结构也满足这种"后进先出"的原则，该数据结构就是栈，栈中可以加入元素也可以弹出元素，这些元素在存取的过程中会满足"后进先出"的原则。接下来将针对栈进行详细地讲解。
10.1.1 定义栈
在C语言中可以用数组来模拟栈。数组的开头（下标为0的元素）被称为栈底，再利用另外一个指针指向数组的末尾，被称为栈顶：
#include <stdio.h>
#define STACK_SIZE1000
int head, tail;//栈底和栈顶
int stack[STACK_SIZE];//int类型的数组用来实现栈
int main()
{
head = 0;
tail = 0;
return 0;
}
下面来逐行分析这个程序：
第2行定义了宏STACK_SIZE，并将它的值定为1000。这是本节中栈的默认大小；
第3行定义了两个全局变量head和tail，分别指向栈底和栈顶；
第4行定义了一个全局的int类型数组stack，它的长度为STACK_SIZE。接下来将用这个数组来模拟栈上的操作。
第7到8行在进入main函数之后，将head和tail都初始化为指向数组的第0个元素。
在栈这一节中，约定tail指向栈中即将加入的新元素的位置，即栈中已有元素的下标为0，1，2到tail-1。按照这样的约定，当head和tail的值都指向第0个元素时，这个栈就是空的。
10.1.2 向栈中加入新元素
push函数实现了向栈中加入新元素的操作，它的定义如下：
void push(int element)
{
stack[tail] = element;
tail ;
}
其中，参数element是要加入栈中的新元素。根据此前的约定，tail指向的是新元素加入的位置，因此stack[tail]用来保存要加入的值element。
新元素加入完毕后，栈的长度增加一，tail的值也需要更新。tail 负责把tail的值移向下一个元素，也就是接下来新元素要加入的位置。
10.1.3 弹出栈中元素
pop函数实现了弹出栈顶元素的操作，它的定义如下：
int pop()
{
tail--;
return stack[tail];
}
pop函数不接受任何参数，它返回一个int类型的数，这个数正是当前栈顶的元素。为了实现pop函数的功能，首先将tail自减，此时tail被挪到了栈中的最后一个元素，随后将这个元素返回。注意pop函数调用之后栈的长度也减一，因此tail自减之后恰好指向的就是pop之后新元素加入栈时的位置。
10.1.4 查看栈顶元素
有的时候程序只是想查看栈顶的元素，并根据查看的结果来决定是否需要将这个元素弹出栈。peek函数实现了这个功能，它的定义如下：
int peek()
{
return stack[tail - 1];
}
由于tail指向了栈顶的后一个元素，因此栈顶元素的下标是tail-1，peek函数返回这个下标对应的元素。请注意比较peek函数和pop函数的区别：两个函数的返回元素其实是一样的，但是pop函数在返回栈顶元素的同时还修改了tail的值，而peek函数仅仅返回栈顶元素，栈底的位置并没有被修改。
10.1.5 清空栈
由于一个栈为空的条件是tail=head=0，因此清空栈的操作非常简单：
void cleanStack()
{
tail = head;
}
注意到在栈中head的值自始至终为0，cleanStack函数实际上将tail的值设为了0。另一个值得留意的地方是清空一个栈并没有必要将栈中的所有元素统统pop一遍，或者将这些元素都设为0，只要将tail移到栈底就足够了。
10.1.6 打印栈中元素
为了更加方便直观地观察栈的行为，这里提供一个用于打印栈中所有元素的函数
void printStack()
{
for (int i = head; i < tail; i )
{
printf("%d ", stack[i]);
}
printf("\n");
}
如前所述栈中的元素下标从head开始，到tail-1结束，printStack利用一个for循环将这些元素都打印出来，以方便观察栈的当前状态。
到此为止，一个最基本的栈就完成了。为了更加直观地展示栈后进先出的特点，如例程10-1所示：
例程 10‑1 实现一个栈
1 #include <stdio.h>
2 #define STACK_SIZE1000
3 int head, tail;//栈底和栈顶
4 int stack[STACK_SIZE];//int类型的数组用来实现栈
5 void push(int element)
6 {
7 stack[tail] = element;
8 tail ;
9 }
10 int pop()
11 {
12 tail--;
13 returnstack[tail];
14 }
15 void cleanStack()
16 {
17 tail = head;
18 }
19 int peek()
20 {
21 return stack[tail - 1];
22 }
23 void printStack()
24 {
25 for (int i = head; i < tail; i )
26 {
27 printf("%d ", stack[i]);
28 }
29 printf("\n");
30 }
31 int main()
32 {
33 head = 0;
34 tail = 0;
35 printStack();
36 push(3);
37 push(5);
38 push(12);
39 printStack();
40 printf("pop %d\n", pop());
41 printStack();
42 printf("peek %d\n", peek());
43 printStack();
44 return 0;
45 }
程序的运行结果如图10-1所示：
图 10‑1 实现一个简单的栈
例程10-1中包含了前面实现的所有函数，接下来逐行分析main函数中的程序，看看这个程序对栈都做了什么：
第33到34行：初始化栈，将head和tail都设为0，即指向栈底；
第35行：打印当前栈中的元素。由于此时是一个空栈，打印的结果应该也为空；
第36行：向栈中插入一个元素3；
第37行：向栈中插入一个元素5；
第38行：向栈中插入一个元素12。此时栈中的元素应该是3、5和12。
第39行：打印当前栈中的元素；
第40行：从栈中弹出一个元素，由于此时栈顶为12，因此打印出的结果应该也是12，同时栈中的元素变为3和5；
第41行：打印当前栈中元素；
第42行：利用peek查看当前栈顶元素，此时栈顶元素为5。由于peek并不会弹出栈顶元素，因此栈中的元素依然为3和5；
第43行：打印栈中元素。
以上的程序实现了一个基本的栈，从图10-1的程序运行结果中可以看出栈后进先出的特点。在后面还将会介绍如何利用栈的这一特点解决实际问题。
队列
队列与栈的"后进先出"原则正好相反，它是满足"先进先出"的原则，也就是先进入队列的元素会先出队列。这就好像现实生活中排队买火车票一样，先排队的人自然能先买到票，也先离开队列。接下来将针对队列进行详细地讲解。
10.1.7 定义队列
和栈类似，队列也可以用C中的数组来实现，如例程10-2所示：
例程 10‑2 定义队列
46 #include <stdio.h>
47 #define QUEUE_SIZE1000
48 int head, tail;//队首和队尾
49 int queue[QUEUE_SIZE];//int类型的数组用来实现队列
50 int main()
51 {
52 head = 0;
53 tail = 0;
54 return 0;
55 }
程序的运行结果如图10-2所示：
图 10‑2 定义一个队列
队列的初始化过程和栈几乎完全一样。例程10-2中定义了一个int类型的队列queue，队列的长度为QUEUE_SIZE。在main函数中将队首和队尾的位置都初始化为0。和栈一样，我们约定tail指向的是队尾之后的一个位置，而head指向的是队首元素的位置。
10.1.8 进入队列
enQueue函数实现了向队列中加入一个元素的作用，它的定义如下所示：
void enQueue(int element)
{
queue[tail] = element;
tail ;
}
这里可以将enQueue和栈中的push函数进行比较：由于都是从尾部加入元素，enQueue的实现和栈中的push函数完全一样。
10.1.9 离开队列
deQueue函数实现了从队列中删除一个元素的作用。和栈中的pop函数不同的是，离开队列发生在队首而不是队尾，因此deQueue函数和pop函数完全不同，以下是它的实现：
int deQueue()
{
head ;
return queue[head - 1];
}
在deQueue函数中首先将head的位置向后挪一位，这是deQueue之后head应该在的位置。随后，队首的元素现在的下标变成了head-1，deQueue函数返回这个下标的对应元素值，实现从队首弹出元素的功能。
10.1.10 清空队列
cleanQueue函数实现了清空一个队列的功能。和栈一样，清空一个队列也只需要把head和tail重新设为0即可。cleanQueue的实现和前面的cleanStack完全一样。
void cleanQueue()
{
tail = head = 0;
}
10.1.11 打印队列中元素
printQueue函数实现了打印队列中元素的功能，由于队列中元素的下标从head开始，到tail-1结束，和栈完全一样，因此printQueue的实现也和栈完全一样：
void printQueue()
{
for (int i = head; i < tail; i )
printf("%d ", queue[i]);
printf("\n");
}
至此一个简单的队列就完成了，和栈一样，下面的实例直观地展示了队列先进先出的特点，如例程10-3所示：
例程 10‑3 实现一个队列
56 #include <stdio.h>
57 #define QUEUE_SIZE1000
58 int head, tail;//队首和队尾
59 int queue[QUEUE_SIZE];//int类型的数组用来实现队列
60 void enQueue(int element)
61 {
62 queue[tail] = element;
63 tail ;
64 }
65 int deQueue()
66 {
67 head ;
68 return queue[head - 1];
69 }
70 void cleanQueue()
71 {
72 tail = head = 0;
73 }
74 void printQueue()
75 {
76 for (int i = head; i < tail; i )
77 printf("%d ", queue[i]);
78 printf("\n");
79 }
80 int main()
81 {
82 head = 0;
83 tail = 0;
84 printQueue();
85 enQueue(3);
86 enQueue(5);
87 enQueue(12);
88 printQueue();
89 printf("deQueue %d\n", deQueue());
90 printQueue();
91 printf("deQueue %d\n", deQueue());
92 printQueue();
93 return 0;
94 }
程序的运行结果如图10-3所示：
图 10‑3 实现一个简单的队列
例程10-3中包含了本节中所有的函数。逐行分析main函数中的程序，看看程序对队列都做了什么：
第27到28行：将head和tail都初始化为0，指向队首；
第29行：打印当前队列中的元素。由于队列刚刚被初始化，打印的结果应该是一个空队列；
第30行：向队列中插入元素3；
第31行：向队列中插入元素5；
第32行：向队列中插入元素12；
第33行：打印队列中元素。此时队列中的元素按顺序依次是3、5和12；
第34行：利用deQueue函数取出队首的元素3并打印，此时队列中的元素按顺序依次是5和12；
第35行：打印队列中元素，此时的打印结果应该是5和12；
第36行：再次利用deQueue取出队首的5，此时队列中只有12；
第37行：打印队列中元素，此时只有12。
关于队列要牢牢把握队列先进先出的特点，本章之后会介绍如何充分利用队列的这一特点解决实际问题。
结构体
前面的章节中已经介绍了int，char，float等基本数据类型，有的时候这些基本数据类型不能满足程序员的需求，比如想要表示数学中的复数，就需要实部和虚部两个double类型；想要表示空间中的一个点就需要x，y和z三个坐标；想要表示学校的一个学生，就至少需要一个表示姓名的字符串和一个int类型的学号。C语言允许定义自己的数据类型，这种自定义的新数据类型就是结构体。
10.1.12 定义结构体
结构体的定义需要遵循下面的语法格式：
struct 结构体名
{
成员1的类型 变量名;
成员2的类型 变量名;
…
成员n的类型 变量名;
};
下面是几个结构体定义的例子：
一、学生
struct Student
{
char name[50];
int studentID;
};
Student结构体中定义了两个成员：一个是char类型的数组name，用来保存学生的姓名（字符串形式）；第二个是int类型的学号studentID。
二、点
struct Point
{
double x;
double y;
double z;
};
Point就是程序中新定义的数据类型，它包含了三个double类型的数，分别表示x，y和z坐标的值。定义了Point之后，就可以像int，float等基本数据类型一样去声明Point类型的变量。
三、栈
struct Stack
{
int head;
int tail;
int size;
int *stack;
};
本章第一节中的栈也可以定义成结构体的形式。在Stack结构体中包含四个成员变量：栈底head，栈顶tail，栈的大小size，以及一个int*类型的指针stack，用来实现栈。
四、队列
本章第二节的队列也可以定义成结构体的形式，其定义和栈完全一样：
struct Queue
{
int head;
int tail;
int size;
int *queue;
};
这是因为在前面的例子中，栈和队列都是基于数组并且利用两个下标来实现的。队列结构体中也包含四个成员变量：队首head，队尾tail，队列的大小size，以及一个int*类型的指针queue用来实现队列。
10.1.13 定义结构变量
定义了结构体之后就可以向定义基本数据类型int，double等的变量一样去定义一个结构体类型的变量。结构体变量的定义语法如下所示：
struct 结构体名 结构变量名;
类似的，也可以定义结构体数组：
struct 结构体名 结构体数组名[数组长度];
以上一节中的Stack为例：
struct Stack s;
这里定义了一个Stack类型的变量，它的名字是s，s里面包含了一个整数head，一个整数tail，一个整数size和一个整型指针stack。
定义结构变量之后的下一个问题就是如何初始化结构变量。结构体变量的初始化实际上是结构体中各个成员变量的初始化过程。它的语法是：
struct 结构体名 结构变量名={成员变量1初值, 成员变量2初值,…,成员变量n初值};
给定结构体中所有变量的初值，结构体会用这些初值对所有成员变量分别进行初始化。以下是一些实例：
一、初始化Student
struct Student student = {"Zhang San", 20140100};
这里定义了一个Student类型的变量，变量名为student，student中包含一个char数组name用来存储学生的名字，name被初始化为Zhang San。student中还包含了一个int类型的学号，在这里被初始化为20140100。
二、初始化Point
struct Point p[2] = {{1.0, 2.0, -1.0}, {0.0, 0.0, 0.0}};
变量p是结构体类型Point的数组，数组的长度为2，p中包含了两个元素p[0]和p[1]。p[0]中包含三个double类型的浮点数x，y和z，它们分别被初始化为了1.0，2.0和-1.0；p[1]中同样包含三个浮点数x，y和z，它们被初始化为了0.0，0.0和0.0。
三、初始化Stack
struct Stack s = {0, 0, 1000, NULL};
Stack类型的变量s中包含4个成员，其中int类型的head和tail被分别初始化为了0和0，int类型的长度size被初始化为了1000，int类型的指针stack被初始化为NULL。
四、初始化Queue
struct Queue q = {0, 0, 1000, NULL};
Queue类型的变量q中包含4个成员，其中int类型的head和tail被分别初始化为了0和0，int类型的长度size被初始化为了1000，int类型的指针queue被初始化为NULL。
10.1.14 结构体与指针
既然基本数据类型可以有对应的指针，结构体类型作为一种新的数据类型，也应该可以有自己的指针。事实确实如此。结构体指针的定义和使用方式和一般的指针并无太大差别，比如：
定义一个Student类型的指针：
struct Student *p = NULL;
这个指针被初始化为NULL。
指向现有的结构体变量：
struct Student s = {"Zhang San", 20140100};
struct Student *p = &s;
这里首先定义了一个结构体变量s，并用字符串Zhang San和学号20140100去初始化它。随后定义了一个Student类型的指针p，并利用取地址&将s的地址赋值给p，p成为了指向Student类型的变量s的指针。
动态声明结构体数组：
//num是一个int类型的变量，表示数组长度
struct Student *p = (struct Student *)malloc(sizeof(struct Student) * num);
这里num是一个int类型的变量，假定num的值只有在运行时才能确定，Student类型的指针p分配了长度为num的一个结构体数组，数组中的每个元素都是一个Student类型的结构体变量，整个要分配的内存大小就是Student的大小乘以数量num。
10.1.15 访问成员变量
结构体中的数据都是保存在成员变量中的，因此要想真正使用结构体光赋值还是远远不够的，还需要知道如何去访问结构体中的每一个成员变量。访问成员变量的方法可以分为两类：
通过结构变量访问：
如果已经在程序中定义好了一个结构变量，那么通过"结构变量名.成员变量名"就可以访问相应的成员变量。如例程10-4所示：
例程 10‑4 通过结构变量访问成员
95 #include <stdio.h>
96 #include <stdlib.h>
97 struct Student
98 {
99 char name[50];
100 int studentID;
101 };
102 int main()
103 {
104 struct Student s[2] = {{"Zhang San", 20140000}, {"Li Si", 20140001}};
105 for (int i = 0; i < 2; i )
106 {
107 printf("%s %d\n", s[i].name, s[i].studentID);
108 }
109 return 0;
110 }
程序的运行结果如图10-4所示：
图 10‑4 通过结构变量访问成员
在例程10-4中，main函数里定义了一个结构体数组s，它的长度为2，两个数组成员s[0]和s[1]被分别初始化。此时通过s[0].name可以访问到s[0]中的char数组name，通过s[0].studentID可以访问到s[0]中的int类型成员变量studentID。程序中利用一个for循环将两个数组成员的姓名和学号分别输出。
通过结构体指针访问：
如果程序中有一个指向某个结构体变量的指针，那么可以利用"指针名->成员变量名"的方法来访问成员变量，如例程10-5所示：
例程 10‑5 通过结构变量访问成员
111 #include <stdio.h>
112 #include <stdlib.h>
113 struct Student
114 {
115 char name[50];
116 int studentID;
117 };
118 int main()
119 {
120 struct Student s = {"Zhang San", 20140000};
121 struct Student *p = &s;
122 printf("%s %d\n", s.name, s.studentID);
123 printf("%s %d\n", p->name, p->studentID);
124 return 0;
125 }
程序的运行结果如图10-5所示：
图 10‑5 通过指针访问成员变量
在例程10-5中，main函数里首先声明了一个Student类型的结构变量s，并将s初始化为Zhang San，学号为20140000。接下来main函数里声明了Student类型的指针p，并将p指向s的地址。随后的两条printf语句比较了两种访问方式：通过s.name访问学生名，以及通过p->name访问学生名。由于p指向了s，因此这两种访问方法访问的都是s中的char数组name，类似的情况也出现在s中的int变量studentID上。
链表
前面讲解的栈和队列都可以用数组实现，在数组中访问元素非常迅速，但是在数组的任意位置插入和删除元素时所有元素整体后移或前移一位，非常麻烦。为此C语言中还提供了一种数据结构——链表，链表中的每一个元素都使用引用的方式来记住它的前一个元素和后一个元素，从而可以将所有的元素彼此连接起来。因此当插入一个新元素时，只需要修改元素之间的这种引用关系即可，非常方便，但是访问元素相对来说较慢。接下来将针对链表进行详细地讲解。
10.1.16 定义链表
链表的定义分为两部分，首先定义一个链表的表头：
struct Head
{
int length;
struct Node* first;
};
这是一个Head类型的结构体，它包含了两个成员，一个是int类型的变量length，用来表示整个链表的长度；第二个成员是一个指针，指向Node类型的变量。Node的定义如下所示：
struct Node
{
int val;
struct Node *next;
};
Node是这个链表中真正的元素，类似于数组当中的元素。Node中包含两个成员：首先是int类型的变量val，用来保存数据；其次是一个指针next，它指向一个新的Node变量。
整个链表就是由一系列指针和结构体构成的蛇形结构：从Head开始指向链表的第一个Node，第一个Node指向第二个Node，第二个Node指向第三个Node，以此类推。直到某一个Node的next指针为NULL了，链表终止。
在下面的例程中，main函数里首先定义了一个Head类型的指针h，并申请了一块内存。目前h链表为空，在初始化的时候将链表的长度初始化为0，first指针初始化为NULL，如例程10-6所示：
例程 10‑6 定义链表
126 #include <stdio.h>
127 #include <stdlib.h>
128 struct Head
129 {
130 int length;
131 struct Node* first;
132 };
133 struct Node
134 {
135 int val;
136 struct Node *next;
137 };
138 int main()
139 {
140 struct Head *h = (struct Head*)malloc(sizeof(struct Head));
141 h->length = 0;
142 h->first = NULL;
143 free(h);
144 return 0;
145 }
程序的运行结果如图10-6所示：
图 10‑6 定义一个链表
逐行解释main函数中的程序：
第15行：利用malloc函数申请一块大小为Head的内存，初始化一个链表指针；
第16行：将Head中的链表长度设为0；
第17行：将Head中的first指针设为NULL；
第18行：回收内存，释放申请的Head内存。
10.1.17 访问元素
和数组元素类似，这里约定链表中Node的下标也是从0开始的，即紧随在Head之后的Node下标为0。整个链表中的元素下表范围是0到length-1。访问元素的函数getNode定义如下：
struct Node* getNode(struct Head* head, int id)
{
if (id < 0 || id >= head->length)
return NULL;
struct Node* p = head->first;
int i = 0;
while (i < id)
{
p = p->next;
i ;
}
return p;
}
getNode函数的输入是一个Head指针head，以及将要访问的元素下标id。getNode函数返回一个Node类型的指针，指向链表中下标为id的Node。
如果id不在0到length-1的范围之内，getNode返回NULL。否则，函数会初始化一个指针p指向链表中下标为0的Node，并初始化当前Node的下标i为0。随后函数利用while循环来寻找下标为id的Node。在当前循环中，如果i还没有到id，那么就将指针p更新到p的下一个Node，并将i的值加1，直到i指向id为止。
10.1.18 插入元素
在链表中插入元素采用如下的规则：如果插入位置的下标id在0到length-1的范围之内，那么就插入到元素id之前，即插入后新元素的下标应当为id。如果下标id=length，那么就将元素插入到链表末尾。其他任何情况下对链表都不作改动：
void addNode(struct Head* head, int val, int id)
{
if (id < 0 || id > head->length)
return;
if (id == 0)
{
struct Node* p = head->first;
head->first = (struct Node*)malloc(sizeof(struct Node));
head->first->val = val;
head->first->next = p;
}
else
{
struct Node* p = getNode(head, id - 1);
struct Node* q = p->next;
p->next = (struct Node*)malloc(sizeof(struct Node));
p->next->val = val;
p->next->next = q;
}
head->length ;
}
addNode函数接受一个Head指针，将要插入的值val，以及要插入的位置id。如果id超出了范围，就直接返回不做任何改动；否则，根据id的值分别进行处理：如果id为0，意味着新的Node要插入在Head和第一个Node之间，程序在if中进行处理；否则直接使用getNode获得id-1处的Node，利用该Node的next指针将val插入到它身后。
10.1.19 删除元素
删除元素和插入元素类似，要求删除元素的id必须在0到length-1的范围之内，否则不做处理：
void deleteNode(struct Head* head, int id)
{
if (id < 0 || id >= head->length)
return;
if (id == 0)
{
struct Node* p = head->first;
head->first = p->next;
free(p);
}
else
{
struct Node* p = getNode(head, id - 1);
struct Node* q = p->next;
p->next = q->next;
free(q);
}
head->length--;
}
deleteNode和addNode的流程类似，都是首先检验id是否在有效范围之内，如果在的话，再根据id的值是否为0分情况讨论，选择是直接从head开始删除还是从id-1的位置开始删除。
10.1.20 释放链表
释放链表的函数destroyLinkedList定义如下。它负责释放链表中所有Node所占用的内存。
void destroyLinkedList(struct Head *head)
{
struct Node* p = head->first;
while (p)
{
head->first = p->next;
free(p);
p = head->first;
}
head->length = 0;
}
destroyLinkedList的执行过程实际上是在不断地删除链表的第一个Node，直到所有Node都被删除为止。
10.1.21 打印链表
打印链表的函数定义如下：
void printLinkedList(struct Head *head)
{
struct Node* p = head->first;
for (int i = 0; i < head->length; i )
{
printf("%d ", p->val);
p = p->next;
}
printf("\n");
}
printLinkedList函数的输入参数包括一个head指针，由于我们知道链表中所有Node的数量，因此可以利用一重for循环遍历所有Node，分别输出Node中存储的val值即可。
至此一个简单的链表就算是完成了。下面的程序可以用来上面这些链表函数的实现是否正确，如例程10-7所示：
例程 10‑7 实现链表
146 #include <stdio.h>
147 #include <stdlib.h>
148 struct Head
149 {
150 int length;
151 struct Node* first;
152 };
153 struct Node
154 {
155 int val;
156 struct Node *next;
157 };
158 struct Node* getNode(struct Head* head, int id)
159 {
160 if (id < 0 || id >= head->length)
161 return NULL;
162 struct Node* p = head->first;
163 int i = 0;
164 while (i < id)
165 {
166 p = p->next;
167 i ;
168 }
169 return p;
170 }
171 void addNode(struct Head* head, int val, int id)
172 {
173 if (id < 0 || id > head->length)
174 return;
175 if (id == 0)
176 {
177 struct Node* p = head->first;
178 head->first = (struct Node*)malloc(sizeof(struct Node));
179 head->first->val = val;
180 head->first->next = p;
181 }
182 else
183 {
184 struct Node* p = getNode(head, id - 1);
185 struct Node* q = p->next;
186 p->next = (struct Node*)malloc(sizeof(struct Node));
187 p->next->val = val;
188 p->next->next = q;
189 }
190 head->length ;
191 }
192 void deleteNode(struct Head* head, int id)
193 {
194 if (id < 0 || id >= head->length)
195 return;
196 if (id == 0)
197 {
198 struct Node* p = head->first;
199 head->first = p->next;
200 free(p);
201 }
202 else
203 {
204 struct Node* p = getNode(head, id - 1);
205 struct Node* q = p->next;
206 p->next = q->next;
207 free(q);
208 }
209 head->length--;
210 }
211 void printLinkedList(struct Head *head)
212 {
213 struct Node* p = head->first;
214 for (int i = 0; i < head->length; i )
215 {
216 printf("%d ", p->val);
217 p = p->next;
218 }
219 printf("\n");
220 }
221 void destroyLinkedList(struct Head *head)
222 {
223 struct Node* p = head->first;
224 while (p)
225 {
226 head->first = p->next;
227 free(p);
228 p = head->first;
229 }
230 head->length = 0;
231 }
232 int main()
233 {
234 struct Head *h = (struct Head*)malloc(sizeof(struct Head));
235 h->length = 0;
236 h->first = NULL;
237 addNode(h, 1, 0);
238 //1
239 printLinkedList(h);
240 addNode(h, 2, 1);
241 //1 2
242 printLinkedList(h);
243 addNode(h, 4, 1);
244 //1 4 2
245 printLinkedList(h);
246 addNode(h, 5, 2);
247 //1 4 5 2
248 printLinkedList(h);
249 deleteNode(h, 2);
250 //1 4 2
251 printLinkedList(h);
252 deleteNode(h, 1);
253 //1 2
254 printLinkedList(h);
255 destroyLinkedList(h);
256 //
257 printLinkedList(h);
258 free(h);
259 return 0;
260 }
程序的运行结果如图10-7所示：
图 10‑7 实现链表
根据本节中各个函数的定义，main函数中每一个printLinkedList之前都用注释给出了链表中预期的值。
union共同体
本章最后要介绍union，也叫做共同体。union是一种特殊的数据类型，它允许多个成员使用同一块内存。灵活地使用union可以减少程序所使用的内存。
10.1.22 定义共同体
定义和使用共同体的方法和结构体十分类似，也需要首先定义共同体内部的成员类型。首先来看union的定义语法：
union 名称
{
变量类型1 变量名1;
变量类型2 变量名2;
变量类型3 变量名3;
...
};
union的定义方法和结构体很类似，但是需要注意的是，union中所有的变量名实际上共用同一块内存。下面对例程的分析将会揭示这一点，如例程10-8所示：
例程 10‑8 使用union
261 #include <stdio.h>
262 union Data
263 {
264 int i;
265 int j;
266 };
267 int main()
268 {
269 union Data d;//定义了一个union
270 d.i = 15;
271 printf("%d\n", d.i);
272 printf("%d\n", d.j);
273 d.j = 23;
274 printf("%d\n", d.i);
275 printf("%d\n", d.j);
276 printf("%p\n", &d.i);
277 printf("%p\n", &d.j);
278 return 0;
279 }
程序的运行结果如图10-8所示：
图 10‑8 使用union
在刚刚的例程中，main函数里首先定义了一个union Data变量，名称为d，在union Data中包含两个int类型的变量i和j，main函数里首先对i进行赋值，并利用printf打印出i和j的值。由于i和j数据类型完全一样，占用同一块4个字节的内存，因此对i赋值也就相当于对j进行了赋值，可以预料到两者打印的结果应该是一样的。
随后程序对j进行赋值。同样地，由于i和j只占用相同的一段内存，因此对j赋值为23就会将这块4个字节内存上原有的值15覆盖，这是通过i和j访问到这块内存的值都是23，因此接下来两次printf的值应该也是一致的。
最后，利用printf打印出了i和j的内存地址。根据union的定义，打印的结果应该完全相同。
在上面的例程中，union里面包含的是两个相同类型的数据，union中也可以包含不同类型的成员变量，如例程10-9所示：
例程 10‑9 union中包含不同类型的成员
280 #include <stdio.h>
281 union Data
282 {
283 int i;
284 unsigned int u;
285 };
286 int main()
287 {
288 union Data d;//定义一个union变量
289 d.u = 0xffffffff;
290 printf("size(d) = %d\n", size(d));
291 printf("%u\n", d.u);
292 printf("%d\n", d.i);
293 return 0;
294 }
程序的运行结果如图10-9所示：
图 10‑9 union中包含不同类型的成员
上面的程序中定义了一个union类型Data，但是Data中包含了两个不同类型的成员变量：unsigned int类型的u和int类型的i。在main函数中首先将u赋值为0xffffffff，这是unsigned int能够表示的最大数，它在内存中的形式是：
1111 1111 1111 1111 1111 1111 1111 1111
当程序通过d.i的形式来访问这段内存时，i的值也是0xffffffff，但是由于i的类型是int，根据前面的知识，这个值对应的有符号整数应该是-1，所以可以预计main函数中第二次printf的结果应该是-1。
一般地，在union中不同类型的成员共享同一块内存，它们底层的二进制表示都是一样的，但是不同的成员会根据自己的类型将这一块内存中的值解读为不同的内容。
10.1.23 使用不同长度的成员
上面的两个例程中union包含的成员大小都是一样的（尽管在第二个例子中数据类型不一样），因此对于union成员共用的内存大小没有什么疑义。如果union中包含了不同大小的成员，那么union所占用的内存大小取决于最长的成员所使用的内存，并且所有成员的首字节对齐。如例程10-10所示：
例程 10‑10 union包含不等长成员
295 #include <stdio.h>
296 #include <string.h>
297 union Data
298 {
299 char ch;
300 char str[4];
301 };
302 int main()
303 {
304 union Data d;//定义union变量
305 strcpy(d.str, "ABC");
306 printf("%s\n", d.str);
307 printf("%c\n", d.ch);
308 return 0;
309 }
程序的运行结果如图10-10所示：
图 10‑10 union包含不等长成员
在例程10-10中，union内包含了两个不等长的数据成员：成员ch的类型是char，占用1个字节；成员str是一个字符串，长度为4个char，占用4个字节。此时union的大小是字符串的大小4个字节，并且ch和str的首字节对齐，即ch和str的第一个字符占用同样位置的内存。
在main函数里首先将str的值赋为一个长度为3的字符串ABC。根据上面的分析，此时字符ch的值应该和str[0]的值一致，因此第二个printf的预期输出应该是字符A。
可以看到printf的输出支持上面的分析。这个例子从侧面揭示了union中包含不同长度的数据成员时它们在内存中的位置关系。
数据结构应用实例
本节将通过两个例子介绍如何使用栈和队列解决实际问题。逆波兰表达式求值的例子利用到了栈后进先出的特点，而为像素点染色的例子利用了队列先进先出的特点。在解决实际问题时，要根据问题本身的要求和特性选择合适的数据结构，以达到事半功倍的效果。
10.1.24 逆波兰表达式求值
数学书上通常将代数运算表达式表示成"操作数 操作符 操作数"的形式，比如3 4表示加法运算，它的两个操作数分别是3和4；5 * 2表示乘法运算，它的两个操作数分别是5和2。逆波兰表达式是将操作数按顺序依次放在操作符之前的表达式，如3 4在逆波兰表达式中就是3 4 ，而5 * 2在逆波兰表达式中是5 2 *。一个稍微复杂一些的例子是四则运算的混合：
3 4 * 5 – 2
在逆波兰表达式中，4 * 5首先被表示成4 5 *：
3 4 5 * - 2
加法运算3 4 5 *的两个操作数现在分别是3和4 5 *，它的逆波兰表达式为3 4 5 * ：
3 4 5 * - 2
最后减法的操作数分别是3 4 5 * 和2，因此该四则运算最终的逆波兰表达式为：
3 4 5 * 2 –
给定上述逆波兰表达式，可以在只遍历输入数据一次的情况下，利用栈求得逆波兰表达式的值，在上面的例子中，这个值等于21。解决逆波兰表达式的思路是：从左到右遍历逆波兰表达式中的所有字符，如果遇到一个操作数，就将操作数压入一个操作数栈；如果遇到一个操作符，就将操作数栈最上端的两个操作数弹出，利用操作符进行计算，并将计算结果压栈。这时，计算结果就成为了未来操作符的操作数。当整个逆波兰表达式被处理完之后，栈中只剩下唯一的一个元素，这个元素就是最后一个操作符对应的结果，也就是整个逆波兰表达式的值，如例程10-11所示：
例程 10‑11 逆波兰表达式求值
310 #include <stdio.h>
311 #define STACK_SIZE1000
312 int head, tail;
313 int stack[STACK_SIZE];
314 void push(int element)
315 {
316 stack[tail] = element;
317 tail ;
318 }
319 int pop()
320 {
321 tail--;
322 returnstack[tail];
323 }
324 void cleanStack()
325 {
326 tail = head;
327 }
328 int peek()
329 {
330 return stack[tail - 1];
331 }
332 void printStack()
333 {
334 for (int i = head; i < tail; i )
335 printf("%d ", stack[i]);
336 printf("\n");
337 }
338 int main()
339 {
340 head = 0;//栈底
341 tail = 0;//栈顶
342 char RPN[20] = "345* 2-";//逆波兰表达式
343 int i = 0;//字符串下标
344 int op1, op2;//操作数
345 while (RPN[i] != 0)
346 {
347 if (RPN[i] >= '0' && RPN[i] <= '9')
348 {
349 push(RPN[i] - '0');
350 }
351 else
352 {
353 op2 = pop();
354 op1 = pop();
355 switch (RPN[i])
356 {
357 case ' ':
358 push(op1 op2);
359 break;
360 case '-':
361 push(op1 - op2);
362 break;
363 case '*':
364 push(op1 * op2);
365 break;
366 case '/':
367 push(op1 / op2);
368 break;
369 default:
370 printf("输入错误！\n");
371 }
372 }
373 i ;
374 }
375 printf("%d\n", pop());
376 return 0;
377 }
程序的运行结果如图10-11 所示：
图 10‑11 逆波兰表达式求值
例程10-11中的程序相对比较复杂，这里来逐行解释main函数中的代码（main函数之前的代码和此前栈一节中的代码一致）：
第31到32行：定义了栈底和栈顶指针；
第33行：定义了要求值的逆波兰表达式；
第34行：定义了用来访问逆波兰表达式每个字符的下标。接下来的while循环将会遍历表达式中的每个字符；
第35行：定义了两个操作数；
第36行：进入while循环。在while循环中会依次访问字符串表达式的每一个字符，并根据字符是操作符还是操作数进行不同的处理；
第38到41行：如果字符是一个操作数，就将这个操作数压入栈中；
第42行：进入else，这时字符本身是一个操作符。
第44到45行：对于操作符，将栈中的最上面两个元素弹出，作为操作符使用的两个操作数；
第46行：进入switch。针对不同的操作符进行不同的处理；
第48到50行：如果操作符是加法，将两个操作数相加，并将结果压入栈中；
第51到53行：如果操作符是减法，将两个操作数相加，并将结果压入栈中；
第54到56行：如果操作符是乘法，将两个操作数相加，并将结果压入栈中；
第57到59行：如果操作符是除法，将两个操作数相加，并将结果压入栈中；
第60到61行：如果操作符不满足上述情况，则提示输入错误；
第64行：将下标加1，访问下一个字符；
第66行：此时已经跳出了while函数之外，即处理完了所有的操作符和操作数。如果一切正确，现在栈中应该只有一个元素，并且这个元素是处理最后一个操作符时得到的结果——整个逆波兰表达式的值。将这个值输出；
10.1.25 为像素点染色
在使用画图程序时经常会选择某种颜色，然后在一个封闭图形内部点一下鼠标，就可将图形内染上同一种颜色。在已知封闭图形边界和鼠标位置的情况下，如何将所有处于图形内部的像素点染上同一种颜色？更加具体的描述是：给定一个只包含0和1的二维数组，用1表示封闭图形的边界，0表示底色。给定一个大于1的整数（表示某一种特定颜色），以及一个二维坐标（保证在图形内部），将二维数组中处在这个封闭图形中的元素都赋值为这种颜色。
首先，给定的像素当然应该被染色。将这个像素染色完毕之后，下一步应该是查看这个像素的四个邻居，如果它们是0，那意味着这些邻居还在图形内部，也应该被染色；如果它们有1，那么意味着像素已经接近了图形边界，有些邻居不需要染色了。对于4个邻居中为0的像素，这个过程应该不断进行下去，即它们也应该检查它们的邻居，如果有为0的，就将它染色，并继续检查它的邻居，直到将边界内的所有像素染色完成。
上述过程可以用队列来实现：在队列中保存探查到的尚未染色且在内部的点，只要队列非空，就开始处理队首的像素，将它染色，并检查它的邻居。如果它的邻居当中有像素点尚未染色，且还没有加入到队列中，就将这个像素加入到队列中来。下面是例程的实现，如例程10-12所示：
例程 10‑12 为像素点染色
378 #include <stdio.h>
379 #define QUEUE_SIZE100
380 #define SIZE 8
381 struct Pos
382 {
383 int i;
384 int j;
385 };
386 int head, tail;
387 struct Pos queue[QUEUE_SIZE];
388 void enQueue(struct Pos element)
389 {
390 queue[tail] = element;
391 tail ;
392 }
393 struct Pos deQueue()
394 {
395 head ;
396 return queue[head - 1];
397 }
398 int main()
399 {
400 head = 0;//队首
401 tail = 0;//队尾
402 int image[SIZE][SIZE] = {{0, 0, 0, 0, 0, 0, 0, 0},
403 {0, 0, 1, 1, 0, 0, 0, 0},
404 {0, 1, 0, 0, 1, 0, 0, 0},
405 {0, 1, 0, 0, 1, 1, 1, 0},
406 {0, 1, 0, 0, 0, 0, 1, 0},
407 {0, 1, 0, 0, 0, 0, 1, 0},
408 {0, 0, 1, 1, 1, 1, 1, 0},
409 {0, 0, 0, 0, 0, 0, 0, 0}};//要染色的图片
410 for (int i = 0; i < SIZE; i )
411 {
412 for (int j = 0; j < SIZE; j )
413 {
414 if (image[i][j] != 0)
415 printf("%d ", image[i][j]);
416 else
417 printf(" ");
418 }
419 printf("\n");
420 }
421 printf("\n");
422 struct Pos start = {2, 2};
423 enQueue(start);
424 int color = 2;
425 int inQueue = 3;
426 while (head != tail)
427 {
428 struct Pos p = deQueue();
429 image[p.i][p.j] = color;
430 struct Pos neighbor;
431 if (p.i > 0)
432 {
433 neighbor.i = p.i - 1;
434 neighbor.j = p.j;
435 if (image[neighbor.i][neighbor.j] == 0)
436 {
437 enQueue(neighbor);
438 image[neighbor.i][neighbor.j] = inQueue;
439 }
440 }
441 if (p.i < SIZE - 1)
442 {
443 neighbor.i = p.i 1;
444 neighbor.j = p.j;
445 if (image[neighbor.i][neighbor.j] == 0)
446 {
447 enQueue(neighbor);
448 image[neighbor.i][neighbor.j] = inQueue;
449 }
450 }
451 if (p.j > 0)
452 {
453 neighbor.i = p.i;
454 neighbor.j = p.j - 1;
455 if (image[neighbor.i][neighbor.j] == 0)
456 {
457 enQueue(neighbor);
458 image[neighbor.i][neighbor.j] = inQueue;
459 }
460 }
461 if (p.j < SIZE - 1)
462 {
463 neighbor.i = p.i;
464 neighbor.j = p.j 1;
465 if (image[neighbor.i][neighbor.j] == 0)
466 {
467 enQueue(neighbor);
468 image[neighbor.i][neighbor.j] = inQueue;
469 }
470 }
471 }
472 for (int i = 0; i < SIZE; i )
473 {
474 for (int j = 0; j < SIZE; j )
475 {
476 if (image[i][j] != 0)
477 printf("%d ", image[i][j]);
478 else
479 printf(" ");
480 }
481 printf("\n");
482 }
483 return 0;
484 }
程序的运行结果如图10-12所示：
图 10‑12 为像素点染色
逐行讲解main函数中的程序：
第23到24行：定义了队首和队尾，并将它们初始化为0，即一个空队列；
第25到32行：定义了一张要染色的图片。这个图片以二维数组的形式来表示，每一个元素的值是0或者1，表示像素点的颜色；
第33到44行：利用for循环将图片打印在控制台上；
第45行：利用Pos结构体定义了一个起点像素。接下来要将和这个像素向连通的区域（相同颜色的像素）染上新的颜色；
第46行：将起点像素加入到队列中去。目前队列中只有一个元素；
第47行：定义了要染上的新颜色2；
第48行：定义了一个标签，用来表示像素点是否已经在队列中。这是因为一个像素点A可能是好几个像素点B、C和D的邻居，如果像素B、C和D都已经在队列中了，那么就会多次访问A，如果不加区别，A就会被重复加入到队列中。因此程序中需要一个标签来表明A像素是否处于已经加入队列的状态；
第49行：进入while循环，开始从队首处理队列中的像素点；
第51行：将队首的元素p取出，这是本次while循环将要处理的像素点；
第52行：取出元素后要做的第一件事：将这个像素染色；
第53行：定义了一个新的Pos结构体neighbor，用来表示要处理的像素的邻居。接下来的程序朝四个方向分别检查四个邻居的状态；
第54到63行：如果p的行号大于0，那么p存在一个上方的邻居。检查这个邻居的颜色是否和p一样（p的颜色是0），如果一致，那么这个元素也需要被染色。将这个元素加入到队列中，并将图中这个元素的颜色标记为已经在队列中；
第64到73行：处理p下方的邻居；
第74到83行：处理p左侧的邻居；
第84到93行：处理p右侧的邻居；
第95到105行：利用printf打印染色之后的图片；
第106行：返回。
在例程中，像素点一共有4种可能的状态：0表示底色，1表示边界， color表示要上的颜色，inQueue表示像素点已经在队列中，等待被处理（处理完之后像素点的值从inQueue变成color）。inQueue可以避免同一个像素点被反复加入到队列中。
本章小结
本章主要讲解了C语言中的基本数据结构，其中包括栈、队列、链表，还讲解结构体以及共同体等，通过本章的学习可以掌握C语言中的基本数据结构，以及在实际开发中的应用。
