所以创建单链表的过程就是一个动态生成链表的过程。
即从“空表”的初始状态起,依次建立各元素结点,并逐个插入链表。
单链表整表创建的算法思路:
- 声明一指针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是二级头指针,*L是一级头指针,开辟头结点的空间(malloc返回的是void类型指针)
*L = (LinkList)malloc(sizeof(Node));
/* 先建立一个带头结点的单链表 */
(*L)->next = NULL;//头结点指针域置空,头结点和首结点断开
for (i = 0; i < n; i++)
{
/* 生成新结点指针 */
p = (LinkList)malloc(sizeof(Node));
/* 随机生成100以内的数字 */
p->data = rand() % 100 + 1;
//头插
//新结点指向头结点,后继优先
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为指向尾部的结点 */
r = *L;
//r是指针
for (i = 0; i < n; i++)
{
/* 生成新结点 */
p = (Node *)malloc(sizeof(Node));
/* 随机生成100以内的数字 */
p->data = rand() % 100 + 1;
/* 将表尾终端结点的指针指向新结点 *///p变为新的尾结点
r->next = p;
/* 将当前的新结点定义为表尾终端结点 */
r = p;
//如例子:q = p->next;//p的后继结点换名为q结点
//将p的名字换元为r,等待后面新的p结点,r会随着循环不断地变化结点
}
/* 表示当前链表结束 */
r->next = NULL;
}
注意L与r的关系,L是指整个单链表,而r是指向尾结点的变量,r会随着循环不断地变化结点,而L则是随着循环增长为一个多结点的链表。
这里需解释一下,r->next=p;的意思,其实就是将刚才的表尾终端结点r的指针指向新结点p,如图3-9-2所示,当中①位置的连线就是表示这个意思。
图3-9-2
r->next=p;这一句应该还好理解,
我以前很多学生不理解的就是后面这一句r=p;是什么意思?请看图3-9-3。
图3-9-3
它的意思,就是本来r是在a i-1 元素的结点,可现在它已经不是最后的结点了,现在最后的结点是a i ,所以应该要让将p结点这个最后的结点赋值给r。此时r又是最终的尾结点了。
循环结束后,那么应该让这个节点的指针域置空,因此有了“r->next=NULL;”,以便以后遍历时可以确认其是尾部。