中职C语言程序设计模块十一课件

1、(中职）C语言程序设计模块十一课件链表模块1111.1链表的基本概念及要点11.1.1链表的基本概念（1）将若干数据项按一定的原则连接起来的表就称为链表。（2）链表中的数据称为结点（或节点）。任何结点都由两部分组成：数据域（data）。指针域（next）。（3）链表的链接原则：前一个结点指向下一个结点，即前一个结点指针域保存下一个结点地址。只有通过前一个结点才能找到下一个结点。头结点（也称头指针）一般不存放有效数据，只保存第1个结点的地址。头结点不存放有效数据，主要是为了方便插入和删除运算的实现。若头结点存放了有效数据，则其为事实上的第1个结点。通常把除头结点外的其他结点称为数据结点，第1数据

2、结点也称为首结点。通常只对存放实际数据的数据结点进行编号（从1开始）。11.1链表的基本概念及要点11.1.1链表的基本概念（4）头结点是链表的起始结点，结点标号为0。11.1链表的基本概念及要点11.1.1链表的基本概念（5）最末结点指针域值为“”，表示其指针值为空（NULL）。（6）结点空间由malloc()函数动态获取并进行结点的创建。（7）头结点是关键点，“抓住”了头结点，就“抓住”了整个链表。链表示意图如图11-1所示。图11-1链表11.1链表的基本概念及要点11.1.2链表结构的定义及内存空间的申请struct LNodeint data;/*数据域*/struct LNode

3、*next;/*指针域*/;struct LNode *p,*t; /*定义了两个链表指针*/p=(struct LNode *)malloc(sizeof(struct LNode);/*申请内存空间*/t=(struct LNode *)malloc(sizeof(structLNode);链表结构（也称结点结构）定义示例。示例1：11.1链表的基本概念及要点11.1.2链表结构的定义及内存空间的申请typedef struct LNodeint data;/*数据域*/struct LNode *next;/*指针域*/NODE;/*定义了一个链表结构类别名NODE*/NODE *p,*

4、t; /*用类别名定义两个链表指针*/p=(NODE *)malloc(sizeof(NODE);/*申请内存空间*/t=(NODE *)malloc(sizeof(NODE);示例2：11.1链表的基本概念及要点11.1.3链表的基本操作要点链表的操作主要靠“-”运算符和指针域来实现。设若有模块11.1.2的示例1和示例2的链表结构，可以做以下简化的理解：（1）左为指针域，右为指向下一个结点：“t-next=p-next;”意为把p指向的下一个结点的地址保存到t的指针域。“p=p-next;”意为指针p下移。（2）当出现双重“-”运算符时：“p-next-data=3；”意为把常值3赋给p指

5、向的下一结点的数据域。“p-next-datadata;”意为p指向的下一结点的数据域值小于t指向结点的数据域值。“p-next-datat-next-data;”意为p指向的下一结点的数据域值大于t指向的下一结点的数据域值。（3）链表操作往往须借助于多个链表指针，单一指针是不可能完成复杂操作的。11.2单链表11.2.1单链表的建立尾插法所谓尾插法，就是把刚创建的结点插入前一结点之后，最后给最末结点指针域赋空值即可。为了便于读者学习、理解，在后面的学习中直接把链表指针称为结点，事实上是指针指向结点。11.2单链表11.2.1单链表的建立尾插法【例11-1】学生成绩链表头结点为第1个数据结点。

6、#include #include struct LNode/*定义链表结构(也可称为结点结构体)，数据域有姓名、班级和成绩*/char name8;int class;int score4; /*语数外加专业4科成绩*/struct LNode *next; /*指针域,指针域存放下一个结点的存储位置(指针)*/;/*创建链表指针函数，返回链表指针，实际上是返回链表的头指针*/struct LNode *create(int n)struct LNode *h,*p,*t; /*链表的创建一般来说需3个链表指针，一个头（如h），一个尾（如t），一个动态指针（如p），用于动态获取内存空间*/1

7、1.2单链表11.2.1单链表的建立尾插法char xm8;/*对应链表结构中的数据域姓名成员*/int clas,a4;/*对应链表结构中的数据域班级和成绩成员*/int i,j;h=NULL;/*关键句1：头指针赋空值*/printf(Please input name,class and 4 score:n);for(i=n;i0;-i)p=(struct LNode *)malloc(sizeof(struct LNode); /*分配内存空间,建立结点*/scanf(%s%d,xm,&clas);for(j=0;jname,xm);p-class=clas;for(j=0;jscor

8、ej=aj;11.2单链表11.2.1单链表的建立尾插法if(h=NULL)/*下面两句为关键语句2*/h=p;/*理解为：如果头为空，就把刚创建的结点转为头结点*/t=p;/*理解为：并把刚创建的结点转为尾结点。可见第1个新结点必须具备双重身份：既为头又为尾。这两句仅执行1次，目的就是创建头结点*/elset-next=p; /*这两句为关键语句3：从第2次创建的结点开始，其地址保存于上一结点指针域*/t=p;/*新建结点又转为尾结点*/t-next=NULL;/*关键语句4：结点创建完毕，给最后一个结点指针域赋空*/return h;/*关键语句5：必须返回头结点*/11.2单链表11.2

9、.1单链表的建立尾插法int main()int n,j;struct LNode *q;/*定义一个链表指针,用于接收函数返回来的值*/printf(Input you want to create point:);scanf(%d,&n);q=create(n);/*调用create()函数,上面函数返回的是头指针值*/printf(nametclasstChinesetMathstEnglisetProfessialn);while(q)printf(%st%dt ,q-name,q-class); /*输出数据域*/for(j=0;jscorej);putchar(n);q=q-nex

10、t; /*关键语句6：指针位移指向下一结点*/printf(n);free(q);11.2单链表11.2.1单链表的建立尾插法Input you want to create point:3Please input name,class and 4 score:Lucy 3 89 87 85 65Jack 3 69 78 95 64Lily 3 87 68 92 91name class Chinese Maths English ProfessionLucy 3 89 87 85 65Jack 3 69 78 95 64Lily 3 87 68 92 91创建3个结点，输入/输出数据如下：1

11、1.2单链表11.2.1单链表的建立尾插法上述链表尾插法创建过程如图11-2所示。创建上面的学生链表时，若要保持头结点数据域为空，应怎么修改呢？【例11-1】是把整个新建的结点转为了头结点，因而头结点成了事实上的第1个数据结点。现在要保持其为空，就不能这样操作，应该把新建的结点地址保存在头结点的指针域，这样就避免了整体转换，头结点有了新建结点的地址，而其数据域仍然为空。图11-2【例11-1】链表尾插法示意图11.2单链表11.2.1单链表的建立尾插法#include #include struct LNodechar name8;int class;int score4;struct LNo

12、de *next;struct LNode *create(int n)struct LNode *h,*p,*t;char xm8;int clas,a4;int i,j;h-next=NULL;/*关键语句1：给头结点指针域赋空*/11.2单链表11.2.1单链表的建立尾插法printf(Please input name,class and 4 score:n);for(i=n;i0;-i)p=(struct LNode *)malloc(sizeof(struct LNode); scanf(%s%d,xm,&clas);for(j=0;jname,xm);p-class=clas;f

13、or(j=0;jscorej=aj;if(h-next=NULL)h-next=p;/*关键语句2：新建结点地址保存到头结点指针域。仅第1次新建时执行*/t=p;11.2单链表11.2.1单链表的建立尾插法elset-next=p; t=p; t-next=NULL;return h;int main()int n,j;struct LNode *q;printf(Input you want to create point:);scanf(%d,&n);q=create(n);q=q-next;/*关键语句3：头结点数据域为空，因而要从第1个数据结点开始*/11.2单链表11.2.1单链表的

14、建立尾插法printf(nametclasstChinesetMathstEnglisetProfessialn);while(q)printf(%st%dt ,q-name,q-class);for(j=0;jscorej);putchar(n);q=q-next;printf(n);11.2单链表11.2.1单链表的建立尾插法头结点为空的尾插法创建过程如图11-3所示。图11-3头结点为空的尾插法创建过程11.2单链表11.2.2单链表的建立头插法所谓头插法，就是把新建结点依次插入前一结点之前，则原头结点变为最末结点，最后建立的结点变为第1结点。这个过程刚好与尾插法是相反的。头插法的结点排

15、列按照堆的从低到高的生长方向，输出时将按从高到低的地址输出，即输入时的反序输出。11.2单链表11.2.2单链表的建立头插法【例11-2】编写一个链表，读入一行字符，每个字符存入一个结点，按输入的顺序建立一个链表的结点序列，然后按相反的顺序输出，并释放全部结点。该题用头插法即可实现：#include #include struct Nodechar ch;struct Node *next;struct Node *h=NULL; /*关键语句1： 头已赋空，将作为最末结点*/struct Node *create()char c;struct Node *p;while(c=getchar(

16、)!=n)p=(struct Node*)malloc(sizeof(struct Node);p-ch=c;11.2单链表11.2.2单链表的建立头插法p-next=h; /*关键语句2：头保存到新建结点指针域*/h=p;/*关键语句3：新建结点转为新的头*/return h;int main()struct Node *q,*t;q=create();printf(The result is:n);while(q)printf(%c ,q-ch);free(q);/如输入 abcde，则输出e d c b aq=q-next;11.2单链表11.2.2单链表的建立头插法头插法创建链表示意图

17、如图11-4所示。图11-4头插法创建链表示意图11.2单链表11.2.3单链表结点逆置所谓单链表结点逆置，指的是把结点倒转，头变尾，尾变头。例如，输入“2 4 1”，输出“1 4 2”。#include #include typedef struct LNode int data;struct LNode *next;Node;/*链表结构类别名，定义类别名，可以省不少事*/ Node *h;/*尾插法链表建立（创建步骤同前，略）*/Node *create(int n)11.2单链表11.2.3单链表结点逆置 /*-创建链表逆置函数-*/Node *reverse(Node *h)/*在以

18、h为头结点的链表中实现逆序*/Node *p,*t;p=h;/*关键语句1：先安排p在头结点位置*/t=p-next;/*关键语句2：再把p指向的下一结点用t来表示*/p-next=NULL;/*关键语句3：把p(此时尚未进入循环,实际就是头结点)的指针域赋空,断掉其与后面结点的连接。事实上,它将变为最后一个结点*/while(t)/*开始循环*/p=t;/*关键语句4：先把t转换为p*/t=t-next;/*关键语句5：t再变为下一结点*/p-next=h;/*关键语句6：把头结点的地址(如100)保存到p的指针域*/h=p;/*关键语句7： 再把p转为新的头结点*/return h;/*返

19、回头结点，此时的h已不是原链表的头结点了*/11.2单链表11.2.3单链表结点逆置int main()int n;Node *q;printf(Input you want to create point:); scanf(%d,&n);q=create(n);q=reverse(q);/*结点逆置*/printf(The result is:);while(q)printf(%d ,q-data);q=q-next; 输入/输出示例：Input you want to create point:5Input number:1 5 6 2 4The result is:4 2 6 5 111

20、.2单链表11.2.3单链表结点逆置单链表逆置实现原理如图11-5所示。图11-5单链表逆置实现原理11.2单链表11.2.4单链表结点查询、插入和删除1.单链表结点查询【例11-3】结点查询实例。在一个头为空的单链表中查询某个数值。找到便输出该结点的位置和查找的值，找不到便提示“Can not find your need!”。#include #include typedef struct LNodeint data;struct LNode *next;NODE;NODE *h;/*建立头为空的链表*/NODE *create(int n)NODE *p,*t;int a,i;h=(NO

21、DE *)malloc(sizeof(NODE);11.2单链表11.2.4单链表结点查询、插入和删除h-next=NULL;printf(Input every data:);for(i=n;i0;-i)p=(NODE *)malloc(sizeof(NODE);scanf(%d,&a);p-data=a;if(h-next=NULL)h-next=p; t=p; elset-next=p; t=p; t-next=NULL;return h;11.2单链表11.2.4单链表结点查询、插入和删除/*-结点查询函数的实现，返回地址，为指针函数-*/void *search(NODE *h,in

22、t score ）/*在以h为头的链表中查找值等于score的结点*/NODE *p;int i=0;/*头为空，标号为0*/p=h;/*借助指针p*/while(p!=NULL&p-data!=score)/*关键语句1：循环条件*/p=p-next; /*关键语句2：指针下移。如果有匹配的值，p将刚好到达这个结点*/i+;11.2单链表11.2.4单链表结点查询、插入和删除if(p-data!=score)printf(Can not find you need!n);elseprintf(Result is:NO.%djd-%d,i,p-data);putchar(n);int main

23、()int n,score;NODE *q;printf(Input you want to create point:);scanf(%d,&n);q=create(n);printf(nInput you want to find score:);scanf(%d,&score);search(h,score);输入/输出如下：Input you want to create point:3Input every data:478 524 586Input you want to find score:524Result is:NO.2jd-52411.2单链表11.2.4单链表结点查询、

24、插入和删除2.单链表结点插入【例11-4】在一个头为第1数据结点的单链表中的指定位置插入一个新的结点。#include #include #include typedef struct LNodechar name10;int class;int data;struct LNode *next;NODE;NODE *h;11.2单链表11.2.4单链表结点查询、插入和删除/*-链表创建函数略-*/ NODE *create(int n)/*-插入一个结点的实现-*/int insert(NODE *h,int i)/*在以h为头的链表中，在第i处插入一个结点*/int j; NODE *p,*

25、t;p=(NODE *)malloc(sizeof(NODE); printf(Please input name,class,data:);scanf(%s%d%d,p-name,&p-clas,&p-data); /*给新结点数据域输入数据*/if(i1)return 0;t=h;/*关键语句1*/j=1;11.2单链表11.2.4单链表结点查询、插入和删除while(t!=NULL&ji-1)/*关键语句2：注意这里条件的变化jnext;j+;if(t=NULL)return 0;if(i=1)/*关键语句3：如果要插在头结点前*/p-next=t;h=p;else/*关键语句4：其他情

26、况的统一插入法*/p-next=t-next;t-next=p;printf(The new order is:n);printf(NametClasstScoren);11.2单链表11.2.4单链表结点查询、插入和删除t=h;/*关键语句5：因为头是首结点，故需从头开始*/while(t)printf(%st%dt%dn,t-name,t-class,t-data);t=t-next;return 1;int main()int n,i,c;NODE *q;printf(Input you want to create point:);scanf(%d,&n);q=create(n);pr

27、intf(Input you want to insert place:);scanf(%d,&i);c=insert(h,i);printf( return %d-Insert successful!n,c);else11.2单链表11.2.4单链表结点查询、插入和删除printf( return %d-Insert fail!n,c);插入示例如下：Input you want to create point:3Input name,class and score:Jack 3 547Input name,class and score:Lucy 3 654Input name,class

28、 and score:Lily 3 624Input you want to insert place:2Please input name,class，data:David 3 586The new order is:NameClassScoreJack3547David3586Lucy3654Lily3624return 1 -Insert successful!11.2单链表11.2.4单链表结点查询、插入和删除结点插入示意图如图11-6所示。图11-6结点插入示意图11.2单链表11.2.4单链表结点查询、插入和删除3.单链表的结点删除【例11-5】在一个头为第1数据结点的链表中删除指

29、定位置的结点。#include #include #include typedef struct LNodechar name10;int class;int data;struct LNode *next; NODE;NODE *h;/*-链表创建函数略-*/ NODE *create(int n)11.2单链表11.2.4单链表结点查询、插入和删除/*-删除一个结点的实现-*/int delnode(NODE *h,int i)NODE *p,*t;int j;if(i1）return 0;t=h;j=1;while(t!=NULL&jnext;j+;11.2单链表11.2.4单链表结点查

30、询、插入和删除if(t=NULL）return 0;if(i=1) h=h-next;elsep=t-next;t-next=p-next;printf(The new order is:n);printf(NametClasstScoren);t=h;while(t)printf(%st%dt%dn,t-name,t-class,t-data);t=t-next;free(p);return 1;11.2单链表11.2.4单链表结点查询、插入和删除ain()int n,i,c;NODE *q;printf(Input you want to create point:);scanf(%d,&

31、n);q=create(n);printf(Input you want to delete jd:);scanf(%d,&i);c=delnode(h,i);if(c=1) printf( return %d-Delete successful!n,c);else printf( return %d-Delete fail!n,c);11.2单链表11.2.4单链表结点查询、插入和删除删除示例如下：Input you want to create point:3Input name,class and score:Jack 2 56Input name,class and score:Luc

32、y 2 65Input name,class and score:Lily 3 67Input you want to delete jd:3The new order is:NameClassScoreJack 2 56Lucy 2 65return 1-Delete succesful!11.2单链表11.2.4单链表结点查询、插入和删除结点删除示意图如图11-7所示。图11-7结点删除示意图11.2单链表11.2.5单链表的排序【例11-6】用尾插法建立一个简单的链表,并将链表中的数据按升序输出到显示器上。程序的思路是：遍历链表，找到最小结点；把找到的结点放入有序链表；把找到的结点从原链

33、表中删除。循环执行这三个步骤直到工作完成。#include #include typedef struct LNode int data;struct LNode *next;Node; Node *h;/*-创建链表-*/Node *create(int n)Node *p,*t; int a,i;11.2单链表11.2.5单链表的排序h=NULL;printf(Input number:);for(i=n;i0;-i)p=(Node *)malloc(sizeof(Node); scanf(%d,&a);p-data=a;if(h=NULL)h=p;t=p;elset-next=p; t=

34、p; t-next=NULL;return h;/*-创建排序函数-*/Node *line(Node *h)/*在以h为头结点的链表中排序*/11.2单链表11.2.5单链表的排序Node *top;/*排序后有顺序链表的表头指针*/Node *p_tail;/*排序后有顺序链表的表尾指针*/Node *pmin_before;/*保留数值最小的结点的前驱结点的指针*/Node *pmin;/*用于存储最小结点*/Node *p;/*当前比较的结点*/top=NULL;/*新表头指针赋空值*/while(h!=NULL)/*在while里要循环完成三个步骤*/*第一个步骤，遍历，找到最小结点

35、*/for(p=h,pmin=h;p-next!=NULL;p=p-next)/*关键语句1：循环遍历原链表*/if(p-next-datadata）/*如果p指向的下一个结点的数据域小于当前数据域值*/pmin_before=p; /*关键语句2：数值最小的结点的前一结点p保存到pmin_before*/pmin=p-next;/*关键语句3：数值最小的结点保存到pmin*/ 11.2单链表11.2.5单链表的排序/*第二步骤，把找到值放入有序链表中，其过程与新建链表一致*/if(top=NULL)top=pmin;p_tail=pmin;elsep_tail-next=pmin;p_tai

36、l=pmin;/*第三步骤:根据判断安排该结点离开原链表*/if(pmin=h)/*关键语句4：如果找到的最小结点就是第一个结点*/h=h-next;/*删除第一个结点：第二个结点代替第一个结点*/elsepmin_before-next=pmin-next; /*关键语句5：最小结点后面的那个结点（跳过最小结点）直接保存到最小结点之前的那个结点*/*while外循环结束处*/if(top!=NULL)11.2单链表11.2.5单链表的排序p_tail-next=NULL;/*得到有序链表top(头指针),给最后一个结点的next域赋空*/h=top;/*把新链表头指针转换为h*/return

37、 h;int main()int n;Node *q; printf(Input you want to create point:);scanf(%d,&n);q=create(n);printf(Output old order:n);while(q)printf(%d,q-data);q=q-next;printf(n);q=line(h);11.2单链表11.2.5单链表的排序printf(Output new order:n);while(q)printf(%d,q-data);q=q-next; printf(n); 输入/输出示例如下：Input you want to crea

38、te point:5Input number:9 1 4 7 3Output old order:91473Output new order:1347911.2单链表11.2.5单链表的排序链表排序三步法图示如图11-8所示。图11-8链表排序三步法图示11.3双 向 链 表双向链表的建立单向链表只能单向下指，只有一个方向，双向链表则不然，双向链表具有三部分：（1）前驱指针域：该指针域存放前一结点的地址。（2）数据域。（3）后继指针域：存放下一结点的地址。相对于单向链表，双向链表多了一个指针域：前驱指针域，如图11-所示。图11-9双向链表11.4循 环 链 表循环链表与单链表的操作方法仅有细

39、微的差别。（1）在创建链表时，最后一个结点的指针域保存的是头结点地址(不再是空值)。（2）若头不为空，输出时先输出首结点；若头为空，正常输出。（3）循环遍历链表结点时的判断值不再以NULL为条件，而是以不等于链表的头指针为条件。循环链表图示如图11-10所示。图11-10循环链表图示11.4循 环 链 表【例11-7】循环链表的创建与输出（头为第1数据结点）。#include #include typedef struct LNodeint data;struct LNode *next; Node;Node *h;Node *create(int n)Node *p,*t;int a;int

40、 i;h=NULL;printf(Input number:);for(i=n;i0;-i)p=(Node *)malloc(sizeof(Node);11.4循 环 链 表scanf(%d,&a);p-data=a;if(h=NULL)h=p;t=p;elset-next=p; t=p;t-next=h; /*关键语句1：创建链表时末结点指针域保存头的地址*/return h;int main()int n;Node *q;printf(Input you want to create point:);scanf(%d,&n);q=create(n);11.4循 环 链 表h=q;print

41、f(The result is:);printf(%d ,q-data); /*关键语句2：头为第一数据结点，先输头*/q=q-next; /*关键语句3：指针移到第2结点位置*/while(q!=h)/*关键语句4*/printf(%d ,q-data);q=q-next;（1）结构体数组各成员在内存中是连续存储的，即其地址是连续的，因而方便查询，但是不方便插入和移动。（2）链表各结点是离散存储的，方便移动和插入，但不方便查询。11.5链表和结构体数组的区别11.5链表和结构体数组的区别【例11-8】结构体中的指针成员。struct nodeint n;struct node *next;x=10,x+1,20,x