C语言链表专题复习

1、链表专题复习数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了 灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不 能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要 30个元 素大小的数组，有时需要50个数组元素的大小，难于统一。我们只能够根据可 能的最大需求来定义数组，常常会造成一定存储空间的浪费。我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。 链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储 就向系统要求申请存储空间，决不构成对存储区的浪费。链表是一种复杂的数据结构，其数据之间的相互关系使链表分成

2、三种：单链表、循环链表、双向链表，下面只介绍单向链表。741单链表单链表有一个头节点h e a d，指向链表在内存的首地址。链表中的每一个节点 的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据） 和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表 是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头 找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要 从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为 空，写作为N U L L。图7 - 3还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，

3、其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既 可以连续分配地址，也可以跳跃式分配地址。看一下链表节点的数据结构定义：struct nodeint num;struct node *p;在链表节点的定义中，除一个整型的成员外，成员p是指向与节点类型完全相同的指针。在链表节点的数据结构中，非常特殊的一点就是结构体内的指针域的数据类型 使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。?单链表的创建过程有以下几步：1）定义链表的数据结构。2 ）创建一个空表。3 ）利用m a I Io c （）函数向系统申请分配一个节点。4 ) 将新节点的指针成员赋值为

4、空。若是空表，将新节点连接到表头；若是非空 表，将新 节点接到表尾。5 ) 判断一下是否有后续节点要接入链表，若有转到 3 ) ，否则结束。? 单链表的输出过程有以下几步1) 找到表头。2) 若是非空表，输出节点的值成员，是空表则退出。3 ) 跟踪链表的增长，即找到下一个节点的地址。4) 转到 2 )。 下列是用尾插法创建链表 新开辟的节点总是插在表末例 7-5 创建一个存放正整数 (输入负数时做结束标志) 的单链表， 并打印输出#include / 包* 含 ma l l o c ()的头文件 */#include struct node /* 链表节点的结构 * /int num;stru

5、ct node *next; ;m a i n ( )struct node *creat(); / * 函数声明 * /void print();struct node *head; / * 定义头指针 * / head=NULL;/* 建一个空表 */ head=creat(head);/* 创建单链表 */ print(head);/* 打印单链表 */*/struct node*creat(structnode*head) 函/数*返回的是与节点相同类型的指针 */struct node*p1,*p2; p1=p2=(structnode*)malloc(sizeof(structno

6、de); 申请/*新节点 */ scanf(%d,&p1-num);/* 输入节点的值 */ p1-next=NULL;/* 将新节点的指针置为空 */ while(p1-num0)/* 输入节点的数值大于 0*/if(head=NULL)head=p1;/* 空表，接入表头 */ elsep2-next=p1;/* 非空表，接到表尾 */ p2=p1;p1=(structnode*)malloc(sizeof(structnode); 申/请*下一个新节点 */ scanf(%d,&p1-num);/* 输入节点的值 */return head;/* 返回链表的头指针 */*/ void p

7、rint(struct node*head)输/*出以head为头的链表各节点的值*/struct node *temp;temp=head;/*取得链表的头指针*/ while(temp!=NULL)/* 只要是非空表 */ printf(%6d,temp-num);/*输出链表节点的值 */temp=temp-next;/* 跟踪链表增长 */在链表的创建过程中，链表的头指针是非常重要的参数。因为对链表的输出和 查找都要从链表的头开始，所以链表创建成功后，要返回一个链表头节点的地 址，即头指针。运行左睜豊.10.124 NULL申馆新节点！第三步.P2-dUtJELp 1第四步,申诣新节点

8、：NULL若数值盂如 则结束：否第三步若泉空晝，将捕节直接，录头:head下列是用头插法创建链表新开辟的结点总是作为表头结点 程序清单位：#i nclude 4的创建过程用国示如下: 第_步 第二步.#i nclude struct node int num;struct node *n ext; ;struct node *creat(struct node *head) struct node *top; /*top为新开辟的结点 */top=(struct node *)malloc(sizeof(struct no de);scanf( “ %d，&top-num);while(top

9、-num=0)top- next=head; /*原来的第一个结点接在新开辟的结点后面*/ head=top; /* 新开辟结点作表头结点，也就是说插在表头 */ top=(struct node *)malloc(sizeof(struct node);scanf( “%d” ,&top-num); return head; 7.4.2 单链表的插入与删除 在链表这种特殊的数据结构中，链表的长短需要根据具体情况来设定，当需要 保存数据时向系统申请存储空间，并将数据接入链表中。对链表而言，表中的 数据可以依此接到表尾或连结到表头，也可以视情况插入表中；对不再需要的 数据，将其从表中删除并释放其

10、所占空间，但不能破坏链表的结构。这就是下 面将介绍的链表的插入与删除。1. 链表的删除在链表中删除一个节点，用图 7 - 4描述如下：例 7-6 创建一个学生学号及姓名的单链表， 即节点包括学生学号、 姓名及指向 下一个节点的指针，链表按学生的学号排列。再从键盘输入某一学生姓名，将 其从链表中删除。首先定义链表的结构：从图 7 - 4 中看到，从链表中删除一个节点有三种情况，即删除链表头节点、删 除链表的中间节点、删除链表的尾节点。题目给出的是学生姓名，则应在链表 中从头到尾依此查找各节点，并与各节点的学生姓名比较，若相同，则查找成 功，否则，找不到节点。由于删除的节点可能在链表的头，会对链表

11、的头指针 造成丢失，所以定义删除节点的函数的返回值定义为返回结构体类型的指针。 struct node *delet(struct node *head,char *pstr)/*he a d 为头指针，删除 ps t r 所在节点 */struct node *temp,*p;t e m p = h e a d ; / * 链表的头指针 * /if (head=NULL) / * 链表为空 * /printf(nList is null!n);else /*非空表* /t e m p = h e a d ;while (strcmp(temp-str,pstr)!=0&temp-next!=

12、NULL)/ * 若节点的字符串与输入字符串不同，并且未到链表尾 * /p = t e m p ;t e m p = t e m p - n e x t ; / * 跟踪链表的增长，即指针后移 * /if(strcmp(temp-str,pstr)=0 ) / * 找到字符串 * /if(temp=head) / * 表头节点 * /printf(delete string :%sn,temp-str);h e a d = h e a d - n e x t ;f r e e ( t e m p ) ; / * 释放被删节点 * /e l s ep-next=temp-next; /* 表中节

13、点 */printf(delete string :%sn,temp-str);f r e e ( t e m p ); else printf(nno find string!n);/*没找到要删除的字符串 */r e t u r n ( h e a d ) ; / *返回表头指针* /2. 链表的插入首先定义链表的结构：struct int num; /*学生学号* /char str20; /* 姓名 * /struct node *n ext;在建立的单链表中，插入节点有三种情况，如图7 - 5所示在衾:申情入节点pl” pine巧1= p-ZTKjt=p2:lmdf5NULLIwnd

14、4pl单横袁中插入节点插入的节点可以在表头、表中或表尾。假定我们按照以学号为顺序建立链表， 则插入的节点依次与表中节点相比较，找到插入位置。由于插入的节点可能在 链表的头，会对链表的头指针造成修改，所以定义插入节点的函数的返回值定 义为返回结构体类型的指针。节点的插入函数如下：struct node *insert(head,pstr,n) / * 插入学号为 n、姓名为 p s t r 的节点 * / struct node *head; / * 链表的头指针 * /char *pstr;int n; struct node *p1,*p2,*p3;p1=(struct node*)mall

15、oc(sizeof(struct node) 分;配/* 一个新节点 */s t r c p y ( p 1 - s t r , p s t r ) ; / * 写入节点的姓名字串* /p 1 - n u m = n ; / * 学号 * /p 2 = h e a d ;if (head=NULL) / * 空表* /head=p1; p1-next=NULL;/ * 新节点插入表头 * /e l s e /* 非空表 * /while(np2-num&p2-next!=NULL)/ * 输入的学号小于节点的学号，并且未到表尾 * /p 3 = p 2 ;p 2 = p 2 - n e x t

16、 ; / * 跟踪链表增长 * /if (nnum) / * 找到插入位置 * /if (head=p2) / * 插入位置在表头 * /h e a d = p 1 ;p 1 - n e x t = p 2 ;e l s e /* 插入位置在表中 * /p 3 - n e x t = p 1 ;p 1 - n e x t = p 2 ;e l s e /* 插入位置在表尾 * /p 2 - n e x t = p 1 ;p 1 - n e x t = N U L L ;r e t u r n ( h e a d ) ; / * 返回链表的头指针 * / 3. 实例例 7 - 7 创建包含学号、

17、姓名节点的单链表。其节点数任意个，表以学号为序，低学号 的在前，高学号的在后，以输入姓名为空作结束。在此链表中，要求删除一个 给定姓名的节点，并插入一个给定学号和姓名的节点。# include stdlib.h# include malloc. hstruct node /* 节点的数据结构 * /int num;char str20;struct node *next; ;main( )/ * 函数声明 * /struct node *creat();struct node *insert();struct node *delet(); void print( );struct node *

18、head; char str20;int n;head=NULL; /* 做空表 * /head=creat (head); / * 调用函数创建以 head 为头的链表 * / p r i n t ( h e a d ) ；/ *调用函数输出节点 * / printf(n input inserted num,name:n);gets(str); /* 输入学号 * / n=atoi (str);gets(str); /* 输入姓名 * / head=insert (head, str, n); 将/* 节点插入链表 */ print (head) ； / * 调用函数输出节点 */ pri

19、ntf(n input deleted name:n);gets(str); /* 输入被删姓名 * / head=delet(head,str); / 调* 用函数删除节点 */ print (head); /* 调用函数输出节点 * / r e t u r n ;/ * * * 创建链表 * * * * * * * * * * * * / struct node *creat(struct node *head) char temp30;struct node *pl,*p2; pl=p2=(struct node*) malloc(sizeof(struct node);printf (

20、input num, name: n;) printf(exit:double times Enter!n);g e t s ( t e m p ) ; gets (p1-str); pl-num=atoi (temp);p l - n e x t = N U L L ; while (strlen (pl-str)0 if (head=NULL) head=pl ；else p2-next=p1;P 2 = p l ；pl=(struct node *)malloc(sizeof(struct node); printf (input num, name: n);printf(exit:do

21、uble times Enter!n);g e t s ( t e m p ) ; gets(pl -str);p1-num=atoi (temp);p1 - n e x t = N U L L ;return head; / * * * * * * * * * *插入节点 * * * * * * * * * * /struct node *insert (head, pstr,n); struct node *head;char *pstr;int n; struct node *pl,*p2,*p3;p1=(struct node*)malloc(sizeof(struct node);

22、strcpy (p1-str, pstr);p 1 - n u m = n ;p 2 = h e a d ;i f ( h e a d = = N U L L )h e a d = p l ; p l - n e x t = N U L L ;e l s ewhile (np2-num&p2-next!=NULL)p 3 = P 2p 2 = p 2 - n e x t ;if (nnum)if (head=p2)h e a d = p l ;p l - n e x t = p 2 ;elsep 3 - n e x t = p l ;p l - n e x t = p 2 ;elsep 2 -

23、 n e x t = p l ;p l - n e x t = N U L L ; r e t u r n ( h e a d ) ; / * * * * * 删除节点 * * * * * * * * * * * * * /struct node *delet (struct node *head, char *pstr) struct node *temp,*p; t e m p = h e a d ; if (head=NULL) printf(nList is null!n); elset e m p = h e a d ;while (strcmp(temp-str,pstr)!=O&

24、temp-next!=NULL)p = t e m p ;t e m p = t e m p - n e x t ,i f ( s t r c m p ( t e m p - s t r , p s t r ) = = 0 )if (temp= head)h e a d = h e a d - n e x t ;f r e e ( t e m p ) ;elsep-next =temp-next; printf(delete string :%sn,temp-str);f r e e ( t e m p ) ; else printf(nno find string!n); return(he

25、ad); / * * * * * * * * * * 链表各节点的输出 * * * * * * * * * * / void print (struct node *head)struct node *temp;t e m p = h e a d ;while (temp!=NULL)p r i n t f ( n % d - - - - % s n , t e m p - n u m， t e m p - s t r ) ；t e m p = t e m p - n e x t ； r e t u r n ;带头结点与不带头结点链表的区别： 题目中没说明，就当不带头结点，除非明确规定了带头结点。 带头结点的链表的第一个结点没有数据域，只有指针域。例如要计算链表中所 有结点数据的和，应定义一个指向结构体结点的指针，指向链表的第一个含数 据的结点，给它赋值时，应是 struct node *p=head-next;其中 head 为链表的头指针。因为头结点不含数据，头结点指向的结点才开始带数据。如果是不带头结点的链表，第一 个结点就含数据，因此，给它赋值时，应是 struct node *p=head; 附：常见算法用链表实现1. 查找算法 例：如果有如下链表结构：struct st