用指针处理链表(二)

4建立动态链表

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

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

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

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

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

图 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函数后建立了一个单向动态链表*/

}

请注意:

(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类型了，而不是指针类型了。

(5)n是结点个数。

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

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