链表（初学）

1. n个结点由指针链组成一个链表。链表的结点在存储器中的位置是任意的即逻辑上相邻的数据元素在物理上不一定相邻。

链表的每一个结点有两个区域分别是数据域和指针域。数据域存储的是当前结点的数据值而指针域存储的是下一个结点的存储地址。

2. 单链表是由头指针唯一确定因此单链表可以用头指针的名字来命名。

3. 头指针、头结点、首元结点

4. H表示头指针

5. 如何表示空表

无头结点时头指针为空时表示空表。有头结点时当头结点的指针域为空时表示空表。

6. 头结点的数据域内装的是什么?

头结点的数据域可以为空也可存放线性表长度等附加信息但此结点不能计入链表长度值。

7. 链表的特点

访问时只能通过头指针进入链表并通过每个结点的指针域依次向后顺序扫描其余结点所以寻找第一个结点和最后一个结点所花费的时间不等。链表是顺序存取顺序表是随机存取。

8. 单链表的定义和表示

例如存储学生学号、姓名、成绩的单链表结点类型定义如下:

方式一

方式二

9. 构造一个空表

#define OK 1

typedef int Status

10. 判断链表是否为空