简单链表的定义和使用

10.4.1　简单链表的定义和使用

链表主要是动态的存储数据。链表中可以包含若干个结点即元素，每个结点最少包含两部分内容：数据和下一个结点的地址。通过结点的地址信息将各结点连接起来。在链表结构中，只要知道了第一个结点的地址就可以访问链表中的其他结点。

链表有一个“头指针”变量，图中以head表示，它存放一个地址，该地址指向一个元素。head指向第一个结点；第一个结点又指向第二个结点……直到最后一个结点，该结点不再指向其他结点，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。

可以看到链表中各结点在内存中可以不是连续存放的。要找某一结点，必须先找到上一个结点，根据它提供的下一结点地址才能找到下一个结点。如果不提供“头指针”（head），则整个链表都无法访问。链表如同一条铁链一样，一环扣一环，中间是不能断开的。打个通俗的比方：幼儿园的老师带领孩子出来散步，老师牵着第一个小孩的手，第一个小孩的另一只手牵着第二个孩子……这就是一个“链”，最后一个孩子有一只手空着，他是“链尾”。要找这个队伍，必须先找到老师，然后顺序找到每一个孩子。

可以看到，这种链表的数据结构，必须利用指针变量才能实现，即一个结点中应包含一个指针变量，用它存放下一结点的地址。

用结构体变量作链表中的结点是最合适的。一个结构体变量含若干成员，这些成员可以是数值类型、字符类型、数组类型，也可以是指针类型。我们用这个指针类型成员来存放下一个结点的地址。通常链表结点可以定义如下的结构体类型：

其中成员num和score用来存放结点中的有用数据（用户需要用到的数据），next是指针类型的成员，它指向struct student类型数据（这就是next所在的结构体类型）。一个指针类型的成员既可以指向其他类型的结构体类型的数据。现在，next是struct student类型中的一个成员，它又指向struct student类型的数据。用这种方法就可以建立链表，如图10-2所示。

图10-2

图10-2中每一个结点都属于struct student类型，它的成员next存放下一结点的地址，程序设计人员可以不必具体知道各结点的地址，只要保证下一个结点的地址放到前一结点的成员next中即可。

注意：上面只是定义了一个struct student类型，并未实际分配存储空间。只有定义了变量才分配内存单元。

下面通过一个例子来说明如何建立和输出一个简单链表。

【例10-5】建立一个如图10-2所示的简单链表，它由3个学生数据的结点组成。输出各结点中的数据。

程序运行结果：

开始时使head指向a结点，a.next指向b结点，b.next指向c结点，这就构成链表关系。“c.next=NULL”的作用是使c.next不指向任何有用的存储单元。在输出链表时要借助p，先使p指向a结点，然后输出a结点中的数据，“p=p－>next”是为输出下一个结点做准备。p－>next的值是b结点的地址，因此执行“p=p－>nxet”后p就指向b结点，所以在下一次循环时输出的是b结点中的数据。

上述例子是比较简单的，所有结点都是在程序中定义的，不是临时开辟的，也不能用完后释放，这种链表称为“静态链表”。