4建立动态链表

所谓建立动态链表是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据,并建立起前后相链的关系。

例11.8 写一函数建立一个有3名学生数据的单向动态链表。

先考虑实现此要求的算法(见图11.12)。

设3个指针变量:head、pl、p2,它们都是用来指向 struct student类型数据的。先用malloc函数开辟第一个结点，并使p1、p2指向它。然后从键盘读入一个学生的数据给p1所指的第一个结点。我们约定学号不会为零，如果输入的学号为0,则表示建立链表的过程完成,该结点不应连接到链表中。先使 head 的值为NULL(即等于0),这是链表为“空”时的情况(即head 不指向任何结点，链表中无的结点作为第一个结点)到表尾)的结点连接

结点),当建立第一个结点就使head指向该结点。

如果输入的pl->num不等于0,则输入的是 第一个结点数据(n=1),令head=p1,即把p1的值赋给 head,也就是使head也指向新开辟的结点(图11.13)。p1所指向的新开辟的结点就成为链表中第一个结点。然后再开辟另一个结点并使p1指向它,接着输入该结点的数据(见图11.14(a))。如果输入的pl->num≠0,则应链入第2个结点(n=2),由于n≠1,则将p1 的值赋给p2-> next，此时p2指向第一个结点,因此执行“p2->next=pl”就将新结点的地址赋给第一个结点的next成员，使第一个结点的next成员指向第二个结点(见图11.14 (b))。接着使p2=p1,也就是使p2指向刚才建立的结点,见图11.14(c)。接着再开辟一个结点并使p1指向它，

图 11.13 并输入该结点的数据(见图11.15(a)),在第三次循环中,由于n=3(n≠1),又将p1 的值赋给p2->next,也就是将第3个结点连接到第2个结点之后,并使p2=p1,使p2指向最后一个结点(见图11.15(b))。

再开辟一个新结点,并使P指向它，输入该结点的数据(见图11.16(a))。由于p1 ->num的值为0,不再执行循环,此新结点不应被连接到链表中。此时将NULL 赋给p2 ->next,见图11.16(b)。建立链表过程至此结束,p1最后所指的结点未链人链表中,第3个结点的next成员的值为NULL,它不指向任何结点。虽然p1指向新开辟的结点,但从链表中无法找到该结点。

建立链表的函数可以如下:

#include <malloc.h>

#define NULL 0

#define LEN sizeof (struct student)

struct student

{long num;

float score;

struct student * next ;

};

int n; /*n为全局变量,本文件模块中各函数均可使用它*/

struct student * creat(void)

/*定义函数。此函数带回一个指向链表头的指针*/

{struct student * head ;

struct student * p1, * p2;

n=0;

p1=p2=(struct student *) malloc(LEN); /*开辟一个新单元*/

scanf (" %ld,%f",&p1->num,&p1->score);

head=NULL:

while(p1->num! =0)

{n=n+1;

if(n==1)head=p1;

else p2->next=p1;

p2=p1;

P1= (struct student *)malloc(LEN);

scanf("%ld,%f" ,&p1->num,&p1->score);

}

p2->next=NULL;

return(head);

}

函数首部在括弧内写void,表示本函数没有形参,不需要进行数据传递。可以在 main 函数中调用creat函数:

main()

{

...

creat(); /*调用 creat函数后建立了一个单向动态链表*/

}

调用 creat函数后，函数的值是所建立的链表的第一个结点的地址(请查看return语句)。

请注意:

(1)第1行为#define 命令行,令 NULL代表0,用它表示“空地址”。第2行令LEN代表struct student类型数据的长度,sizeof是“求字节数运算符”。

(2)第9行定义一个creat函数,它是指针类型,即此函数带回一个指针值，它指向一个struct student类型数据。实际上此creat函数带回一个链表起始地址。

(3) malloc(LEN)的作用是开辟一个长度为LEN的内存区,LEN已定义为sizeof(struct student),即结构体struct student的长度。malloc带回的是不指向任何类型数据的指针(void *)。而p1、p2 是指向 struct student类型数据的指针变量,因此必须用强制类型转换的方法使指针的基类型改变为struct student类型,在malloc(LEN)之前加了“(struct student*)”,它的作用是使malloc返回的指针转换为指向struct student类型数据的指针。注意“*”号不可省略,否则变成转换成struct student类型了，而不是指针类型了。

(4)最后一行return后面的参数是head(head已定义为指针变量,指向struct student类型数据)。因此函数返回的是head 的值,也就是链表的头地址。

(5)n是结点个数。

(6)这个算法的思路是让p1指向新开的结点,p2指向链表中最后一个结点,把p1所指的结点连接在p2所指的结点后面,用“p2->next=p1”来实现。

我们对建立链表过程做了比较详细的介绍,读者如果对建立链表的过程比较清楚的话,对下面介绍的删除和插入过程也就比较容易理解了。