数据结构之线性表的链式存储[3]

链表的每个元素构成一个结点结点定义如下

Typedef struct node{

DataType data; /*每个元素数据信息*/

struct node *next; /*存放后继元素的地址*/

} LNode*LinkList;

定义头指针变量

LinkList H;

上面定义的LNode是结点的类型LinkList是指向LNode类型结点的指针类型 H为头指针变量指向单链表的第一个结点如图(b)所示当单链表为空时H= NULL如图(a)所示

为了方便操作单链表一般在单链表的第一个结点之前加一个称为头结点的附加结点如图(c)所示头结点的设置会给单链表操作带来方便当然用户也可以在附加结点的数据域中存放一些与整个单链表相关的信息(如单链表长度等)指针域中存放的是第一个数据结点的地址空表时指针域为空(NULL)注意在这种情况下以H>next等于 NULL表示单链表为空如图(d)所示

声明在以后的算法中若不作特别说明链表是指采用带头结点的链表形式在链表的示意图中通常规定用符号∧表示NULL

[] [] [] []