补充内容_单向链表

《补充内容_单向链表》由会员分享，可在线阅读，更多相关《补充内容_单向链表（58页珍藏版）》请在金锄头文库上搜索。

1、补充内容：单向链表信息工程系8.6 用指针处理单向链表通过组合使用结构和指针创建强大的数据结构（此节将讨论一种使用结构和指针的技巧，即单向链表）这不仅因为它非常有用，而且许多用于操纵链表的技巧也适用于其它数据结构（如队列、栈等）。8.6.1 链表的概述链表的概念链表：（linked list）就是一些包含数据的独立数据结构（通常称为节点）的集合。也就是说链表就是一种数据结构，是一组结点（node）的集合序列。链表中的每个节点通过链或指针连接在一起。程序通过指针访问链表中的节点。通常节点是动态分配（内存单元）的。链表概述（谭浩强）链表是一种常见的重要 的数据结构。它是动态地进 行存储分配的一种结

2、构。下图表示最简单的一种链表(单 向链表)的结构。链表的构成链表有一个“头指针”变量，图中以 head表示，它存放一个地址。该地址指 向一个元素。链表中每一个元素称为“结 点”，每个结点都应包括两个部分：一为 用户需要用的实际数据，二为下一个结点 的地址。可以看出，head指向第一个元 素；第一个元素又指向第二个元素直 到最后一个元素，该元素不再指向其他元 素，它称为“表尾”，它的地址部分放一个 “NULL”(表示“空地址”)，链表到此结束 。链表中的结点前面介绍的结构体类型，用它 作链表中的结点是最合适的。 struct student int num；float score；struct

3、student *next； ；8.6.2 处理动态链表所需的函数1malloc函数其函数原型为void *malloc(unsigned int size);其作用是在内存的动态存储区中分配 一个长度为size的连续空间。malloc函数n此函数的返回值是一个指向分配域起始地址的指针(基类型为void)。n如果此函数未能成功地执行（例如内存空间不足），则其返回空指针（NULL） 。2 calloc函数其函数原型为void *calloc(unsigned n, unsigned size); 其作用是在内存的动态区存储中分配n个长度为 size的连续空间。函数返回一个指向分配域起 始地址的指

4、针；如果分配不成功，返回NULL。用calloc函数可以为一维数组开辟动态存储空 间，n为数组元素个数，每个元素长度为size。3 free函数其函数原型为void free(void *p);其作用是释放由p指向的内存区， 使这部分内存区能被其他变量使 用。p是调用calloc或malloc函数 时返回的值。free函数无返回值 。8.6.3 建立动态链表所谓建立动态链表是指在程序执行过程中从无到有地建 立起一个链表，即一个一个地 开辟结点和输入各结点数据， 并建立起前后相链的关系。例 写一函数建立一个有3名学生 数据的单向动态链表。谭浩强教材中的图10.13谭浩强教材中的图10.14谭浩强

5、教材中的图10.15谭浩强教材中的图10.16建立链表的函数可以如下：#define NULL 0 #define LEN sizeof(struct student) struct student long num;int score;struct student *next; ;int n; /*n为全局变量，本模块中各函 数均可使用它*/struct student *creat(void)/*定义函数。此函 数带回一个指向链表头的指针*/ struct student *head；struct student *p1，*p2；n=0；p1=p2=( struct student *)

6、malloc(LEN)；/*开辟一个新单元*/scanf(“%ld,%d “,if(n=1) head=p1;else p2-next=p1;p2=p1;p1=(struct student *)malloc(LEN);scanf(“%ld,%d “, p2-next=NULL;return(head); 在main函数中调用creat函数：main( ) struct student *head;head=creat( ); /*调用creat函数 后建立了一个单向动态链表*/说明n (1) 第1行为#define宏定义 命令行，设置符号常量（或称宏 名）NULL代表0，用它表示“空地 址”

7、。第2行设置LEN代表struct student类型数据的长度，sizeof 是“求字节数运算符”。说明n (2) 第9行定义一个creat函数，即struct student *creat(void)它是指针类型，即此函数返回一个指 针值，它指向一个struct student类 型数据。实际上此creat函数带回一个 链表起始地址。说明n (3) malloc(LEN)的作用是开辟一个长度为LEN的 内存区，LEN已定义为sizeof(struct student)，即 结构体struct student的长度。malloc带回的是不指 向任何类型数据的指针(void *类型)。而p1、

8、p2是指 向struct student类型数据的指针变量，因此必须用 强制类型转换的方法使指针的基类型改变为struct student类型，在malloc(LEN)之前加了“(struct student *)”，它的作用是使malloc返回的指针转换 为指向struct student类型数据的指针。注意“*”号不 可省略，否则变成转换成struct student类型了，而 不是指针类型了。说明(4) 最后一行return后面的参数是head(head已定义为指针变量，指向struct student类型数据)。因此函数返回的是head的值，也就是链表的头地址。(5) n是结点个数。说

9、明(6) 这个算法的思路是让p1指向新开的结点，p2指向链表中最后一个结点，把p1所指的结点连接在p2所指的结点后面，用“p2-next=p1”来实现。8.6.4 输出链表将链表中各结点的数据依次 输出。首先要知道链表第一个结点 的地址，也就是要知道head的 值。然后设一个指针变量p，先 指向第一个结点，输出p所指的 结点，然后使p后移一个结点， 再输出。直到链表的尾结点。例 编写一个输出链表的函数print 。void print(struct student *head) struct student *p;printf(“nNow，These %d records are:n“, n)

10、;p=head;if(head!=NULL) do printf(“%ld %dn“, p- num, p-score);p=p-next; while(p!=NULL); 算法可用下图表示谭浩强教材中的图10.18在main函数中调用print函数：main( ) struct student *head; long num;head=creat( ); /*调用creat函数 后建立了一个单向动态链表*/print(head);printf(“input deldte num:”);scanf(“%ld”, del(head, num);print(head);n head的值由实参传过来

11、，也就是将已有的链表的头指针传给被调用的函数，在print函数中从head所指的第一个结点出发顺序输出各个结点。8.6.5 对链表的删除操作谭浩强教材中的图10.19例 写一函数以删除动态链表中指 定的结点。以指定的学号作为删除结点的标志。例如，输入99103表示要求删除学号 为99103的结点。解题的思路是这样的：从p指向的第一 个结点开始，检查该结点中的num值是否 等于输入的要求删除的那个学号。如果相 等就将该结点删除，如不相等，就将p后移 一个结点，再如此进行下去，直到遇到表 尾为止。谭浩强教材中的图10.20结点的删除预删除的结点，还要区分两 种情况：要删的是第一个结点 (p1的值等

12、于head的值，如图 10.20(a)那样)，则应将p1-next 赋给head。见图10.20(c)。 如 果要删除的不是第一个结点，则将 p1-next赋给p2-next，见图 10.20(d)。此题的算法删除结点的函数del如下：struct student *del(struct student *head,long num) struct student *p1, *p2;if (head=NULL) printf(“nlist null!n“);return (head);p1=head;while(num!=p1-num p1=p1-next; /*p1后移一个结 点 */if(

13、num=p1-num) /* 找到了 */ if(p1=head) head=p1-next; /* 若p1指向的是首结点，把第二个结点地 址赋予head */else p2-next=p1-next; /*否则将下一结点地址赋给前一结点地址 */printf(“delete：%ldn“, num);n=n-1; else printf(“%ld not been found!n“, num); /* 找不到该结点 */return(head); 8.6.6 对链表的插入操作对链表的插入是指将一个结点插 入到一个已有的链表中。为了能做到正确插入，必须解决 两个问题： 怎样找到插入的位置； 怎样

14、实现插入。谭浩强教材中的图10.22谭浩强教材中的图10.23例 插入结点的函数insert如下。struct student *insert(struct student *head, struct student *stud) struct student *p0, *p1, *p2;p1=head； /* 使p1指向第一个结点 */p0=stud； /*使p0指向要插入的结点 */if(head=NULL) /*原来的链表是空表*/ head=p0; p0-next=NULL; /*使p0指向的结点作为头 结点*/else while(p0-nump1-num) /*使p2指向刚才p1指

15、向的结点*/p1=p1-next; /*p1后移一个结点*/if(p0-numnum) if(head=p1) head=p0; /*插 到原来第一个结点之前 */else p2-next=p0; /*插到p2指向的结点之后 */p0-next=p1；else p1-next=p0; p0-next=NULL; /* 插到最后的结点之后 */n=n+1; /* 结点数加1 */return(head); 函数参数是head和stud。stud也是一 个指针变量，从实参传来待插入结点的地址 给stud。语句p0=stud的作用是使p0指向 待插入的结点。函数类型是指针类型，函数 值是链表起始地址head。8.6.7 对链表的综合操作main( ) struct student *head, stu;long del-num;printf(“input records:n“);head=creat( ); /* 创建链表，返回头指针 */print(head); /* 输出全部结点 */printf(“input the deleted number:“);scanf(“ %ld “ , /*输入要删除的学号 */head=del(head, del