1 前言
上次我们讲到单链表的存储和一些简单的算法，今天我们来学习一下单链表的初始化和销毁操作。
2 详述
2.1 单链表的整表创建
思路：
·声明一结点p和计数器变量i;
·初始化一空链表L；
·让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
·循环：
生成一新结点赋值给p；
随机生成一数字赋值给p的数据域p->data；
将p插入到头结点与前一新结点之间。
如图：
实现代码如下：
/*随机产生n个元素的值，建立带头结点的单链线性表L（头插法）*/
void CreateListHead(LinkList *L,int n)
{
LinkList p;
int i;
srand(time(0)); /*初始化随机数种子*/
*L = (LinkList) malloc (sizeof(Node));
(*L)->next = NULL; /*先建立一个带头结点的单链表*/
for(i = 0;i<n;i++)
{
p = (LinkList) malloc (sizeof(Node)); /*生成新结点*/
p->data = rand()%100+1; /*随机生成100以内的数字*/
p->next = (*L)->next;
(*L)->next = p; /*插入到表头*/
}
}
还有一种尾插法，比较符合我们的思路，代码实现：
/*随机产生n个元素的值，建立带头结点的单链表L（尾插法）*/
void CreateListTail(LinkList *L,int n)
{
LinkList p,r;
int i;
srand(time(0));
*L = (LinkList) malloc(sizeof(Node));
r = *L; /*r指向尾部的结点*/
for (i = 0;i<n;i++)
{
p = (Node *) malloc(sizeof(Node)); /*生成新结点*/
p->data = rand()%100+1; /*随机生成100以内的数字*/
r->next = p; /*将尾端结点的指针指向新结点*/
r = p; /*将当前的新节点指向传给r结点*/
}
r->next = NULL; /*表示当前链表结束*/
}
解释：
r->next = p图解:
r = p图解：
2.2 单链表的整表删除
思路：
·声明一结点p和q；
·将第一个结点赋值给p；
·循环
将下一个结点赋值给q；
释放p；
将q赋值给p。
实现算法：
/*初始条件：顺序线性表L已存在，操作结果：将L重置为空表*/
Status ClearList(LinkList *L)
{
LinkList p,q;
p = (*L)->next; /*p指向第一个结点*/
while(p) /*没到表尾*/
{
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL; /*头结点指针域为空*/
return OK;
}
2.3 单链表结构与顺序结构存储结构优缺点
2.4 其它类型的链表
2.4.1 静态链表
有些高级语言没有指针，这时候我们要让数组的元素由两个数据域组成，data和cur，数据域data用来存放数据元素；游标cur相当于存放单链表的next指针，存放该元素的后继在数组中的下标。我们把这种数组描述的链表叫做静态链表。
2.4.2 循环链表
将单链表中终端结点的指针由空指针改为指向头结点，就使得整个单链表形成一个环。这种头尾相接的单链表成为单循环链表，简称循环链表（cirular linked list）。
2.4.3 双向链表
双向链表(double linked list)是在单链表中的每个结点中，再设置一个指向其前驱结点的指针域。
2.5 总结
用下图简单的来介绍一下线性表部分的内容：
3 结语
以上是所有内容，希望对大家有所帮助。