C++语言程序设计

在某一类数据集合中，依据数据成员之间的关系的不同，可把数据结构分为两大类：线性结构和非线性结构。线性结构中各个数据成员一次排列在一个线性序列中，如数组和链表等；非线性结构中，每个数据成员可能与零个或多个其它数据成员之间发生关系，如树和图。
用数组来存放数据的时候，需要事先确定数组的长度，并分配连续的内存空间。因而不能动态地分配内存，不能改变数组的大小。而链表是一种非连续存放的重要的线性数据结构，它可以对存储空间进行动态的分配。比如我们要对一个公司员工数据进行记录，由于公司的人事可能会经常地变动，涉及到员工人数的增减。如果用数组来存放员工的记录，当员工人数发生变化的时候，数组的大小很难做到相应的变化。如果人数减少，数组会有剩余空间，但人数增加，原来的数组大小可能不够，就必须重新开数组。这样就会产生浪费空间或增加维护负担等问题。如果改用链表来存放员工的数据，就不会产生这些问题，因为链表对存储空间的分配是动态的。
链表是由一些列的结点组成，每一个结点包含数据和指向下一结点的指针。每一个结点占用一块存储单元，当要在链表中增加一个结点时，可动态地为该结点分配一个存储单元；当要在链表中删除一个结点时，也可释放该结点的存储单元。下图是一个简单的链表示意图：

| 图8-3

该链表由3个结点组成，其中每个结点都分为两个域，一个是数据域（即图中的大写字母A、B、C），存放各种实际的数据，如学号num、姓名name、性别sex和成绩score等。另一个域为指针域，存放下一结点的首地址。比如第一个结点的指针域存放的地址是1475，就是第二个结点的首地址。链表中的每一个结点都是同一种结构类型。
另外，每个链表都有一个头指针head，它存放的是链表头结点的首地址。我们就可以通过链表的head指针找到链表的头结点，然后通过该结点的指针域找到一个结点的首地址，从而可以找到该链表的所有结点。需要注意的是：最后一个结点的指针域为NULL，据此，我们可以判断一个链表是否结束。下面是一个学生结构的实例：
struct stu
{
int num;
int score;
stu *next;
}
前两个成员组成数据域，后一个成员next是指针域，它是一个指向stu类型结构的指针变量。
对链表的主要操作有以下几种：
1. 建立链表；
2. 结构的查找与输出；
3. 插入一个结点；
4. 删除一个结点；
下面对每一种操作具体进行讲解。