（中职）C语言程序设计模块十一电子课件.pptx

《（中职）C语言程序设计模块十一电子课件.pptx》由会员分享，可在线阅读，更多相关《（中职）C语言程序设计模块十一电子课件.pptx（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、头结点外的其他结点称为数据结点，第1数据结点也称为首结点。通常只对存放实际数据的数据结点进行编号（从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;

3、/*数据域*/struct LNode*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;/*定义了一个链表结构类别名N

4、ODE*/NODE*p,*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；”

5、意为把常值3赋给p指向的下一结点的数据域。“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】学生成绩链表头结

6、点为第1个数据结点。#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），用于动态获取内存空间

7、*/11.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;jsco

8、rej=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-next;/

10、*关键语句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个结点，输入/输出数据如下：11.2单

11、链表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 LNode*ne

12、xt;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;for(j=0;jsc

13、orej=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单链表的建立尾插法printf(n

14、ametclasstChinesetMathstEnglisetProfessialn);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()!=n)p=(struct Node*)

16、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单链表的建立头插法头插法创建链表示意图如图11-4所示。图11-4头插法创建链表示意图

17、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)/*在以h为头结点的链表中实现逆序*/Node*p,*t;p=h;/*关

18、键语句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;/*返回头结点，此时的h已不是原链表的头结点了*/11.2单链表11.2.

19、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.2单链表11.2.3单链表结点逆置单链表逆置实现原理如图11-5所示。图1

20、1-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=(NODE*)malloc(sizeof(NODE);11.2单链表11.2.4单链表结点查

21、询、插入和删除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,int score）/*在以h为头的链表中查找值等于score的结点*/NODE*p;int i=0;/*

22、头为空，标号为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()int n,score;NODE*q;printf(Input you want to create p

23、oint:);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单链表结点查询、插入和删除2.单链表结点插入【例11-4】在一个头为第1数据结点的单链表中的指定位置插入一个新的结点。#inc

24、lude#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,*t;p=(NODE*)malloc(sizeof(NODE);printf(Please input name,class,da

25、ta:);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：其他情况的统一插入法*/p-next=t-next;t-next=p;printf(The new order is:n);printf(N

26、ametClasstScoren);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);printf(Input you want to insert place:);scanf(%d,&i);c=insert(h,i);pri

27、ntf(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 and score:Lily 3 624Input you want to insert place:2Please input name,c

28、lass，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数据结点的链表中删除指定位置的结点。#include#include#include typedef struct LNodechar name10;int class

29、;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单链表结点查询、插入和删除if(t=NULL）return 0;if(i=1)h=h-next;elsep=t-next;t-next=p-next;printf(The ne

30、w 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,&n);q=create(n);printf(Input you want to delete jd:);scanf(%d,&i);c=delnode(h,i);if(c

31、=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:Lucy 2 65Input name,class and score:Lily 3 67Input you want to delete jd:3The new order is:N

32、ameClassScoreJack 2 56Lucy 2 65return 1-Delete succesful!11.2单链表11.2.4单链表结点查询、插入和删除结点删除示意图如图11-7所示。图11-7结点删除示意图11.2单链表11.2.5单链表的排序【例11-6】用尾插法建立一个简单的链表,并将链表中的数据按升序输出到显示器上。程序的思路是：遍历链表，找到最小结点；把找到的结点放入有序链表；把找到的结点从原链表中删除。循环执行这三个步骤直到工作完成。#include#include typedef struct LNode int data;struct LNode*next;Nod

33、e;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=p;t-next=NULL;return h;/*-创建排序函数-*/Node*line(Node*h)/*在以h为头结点的链表中排序*/11.2单链表11.2.5单链表的排序Node*top;/*

34、排序后有顺序链表的表头指针*/Node*p_tail;/*排序后有顺序链表的表尾指针*/Node*pmin_before;/*保留数值最小的结点的前驱结点的指针*/Node*pmin;/*用于存储最小结点*/Node*p;/*当前比较的结点*/top=NULL;/*新表头指针赋空值*/while(h!=NULL)/*在while里要循环完成三个步骤*/*第一个步骤，遍历，找到最小结点*/for(p=h,pmin=h;p-next!=NULL;p=p-next)/*关键语句1：循环遍历原链表*/if(p-next-datadata）/*如果p指向的下一个结点的数据域小于当前数据域值*/pmin_

35、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_tail=pmin;/*第三步骤:根据判断安排该结点离开原链表*/if(pmin=h)/*关键语句4：如果找到的最小结点就是第一个结点*/h=h-next;/*删除第一个结点：第二个结点代替第一个结点*/elsepmin_b

36、efore-next=pmin-next;/*关键语句5：最小结点后面的那个结点（跳过最小结点）直接保存到最小结点之前的那个结点*/*while外循环结束处*/if(top!=NULL)11.2单链表11.2.5单链表的排序p_tail-next=NULL;/*得到有序链表top(头指针),给最后一个结点的next域赋空*/h=top;/*把新链表头指针转换为h*/return h;int main()int n;Node*q;printf(Input you want to create point:);scanf(%d,&n);q=create(n);printf(Output old o

37、rder: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 create point:5Input number:9 1 4 7 3Output old order:91473Output new order:1347911.2单链表11.2.5单链表的排序链表排序三步法图示如图11-8所示。图

38、11-8链表排序三步法图示11.3双 向 链 表双向链表的建立单向链表只能单向下指，只有一个方向，双向链表则不然，双向链表具有三部分：（1）前驱指针域：该指针域存放前一结点的地址。（2）数据域。（3）后继指针域：存放下一结点的地址。相对于单向链表，双向链表多了一个指针域：前驱指针域，如图11-所示。图11-9双向链表11.4循 环 链 表循环链表与单链表的操作方法仅有细微的差别。（1）在创建链表时，最后一个结点的指针域保存的是头结点地址(不再是空值)。（2）若头不为空，输出时先输出首结点；若头为空，正常输出。（3）循环遍历链表结点时的判断值不再以NULL为条件，而是以不等于链表的头指针为条件。

39、循环链表图示如图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 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=

40、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;printf(The result is:);printf(%d,q-data);/*关键语句2：头为第一数据结点，先输头*/q=q-next;/*关键语句3：指针移到第2结点位置*/while(q!=h)/*关键语句4*/printf(%d,q-data)

41、;q=q-next;（1）结构体数组各成员在内存中是连续存储的，即其地址是连续的，因而方便查询，但是不方便插入和移动。（2）链表各结点是离散存储的，方便移动和插入，但不方便查询。11.5链表和结构体数组的区别11.5链表和结构体数组的区别【例11-8】结构体中的指针成员。struct nodeint n;struct node*next;x=10,x+1,20,x+0,*p=x;（1）上面定义了一个结构体数组x和一个指向该数组的结构体指针p。（2）该结构体数组有2个成员，一个是int型的n，另一个是结构体自身指针next。（3）结构体数组初始化是：x0=10,x+1，即其指针指向第2个元素；x

42、1=20,x+0，即其指针指向第1个元素。那么：“printf(%d,p-next-next-n);”应该输出多少呢？p-next指向x+1，即x1；p-next-next指向x+0，即x0;故:p-next-next-n指向第1个元素的10，输出10。这里很容易把其误认为链表形式，其实为结构体数组。初学者应注意此类情况。11.5链表和结构体数组的区别【例11-9】统计相同的单词数。每个单词由空格、“n”或“t”分隔。单词长度不超过20个字符,以“stop”结束输入。该程序只统计从键盘输入的相同的单词数,相同的单词不能重复获取节点空间。#include#include typedef stru

43、ct nodeint count;char data20;struct node*next;STYPE;STYPE*h;STYPE*create()char str20;STYPE*t,*s,*p;11.5链表和结构体数组的区别h=NULL;printf(Input string(end by stop):n);while(1)scanf(%s,str);if(strcmp(str,stop)=0)break;/*通过stop结束串的输入,输入时注意单词之间的分隔*/p=h;while(p!=NULL&strcmp(p-data,str)!=0)/*第1次,因为p为NULL,不执行该循环。第2

44、次输入,开始循环,边输入边统计:输入的串和放在结点data成员里的串进行比较*/p=p-next;/*如果上面的串相同，结点停止下移，执行下面的if*/if(p!=NULL)/*第1次输入单词,p为NULL,执行else;第2次输入,如果不相同,指针下移,下一个结点是空的,又执行else把新单词放入新建结点。如果是相同的串,节点不会下移,该结点为有值结点,不为空,计算自增*/11.5链表和结构体数组的区别p-count+;elses=(STYPE*)malloc(sizeof(STYPE);s-count=1;/*第1次输入的单词,计数1*/strcpy(s-data,str);/*把输入的单

45、词放入data中*/s-next=NULL;/*给该结点指针域赋空每个新节点指针域都要赋空*/if(h=NULL)h=s;t=s;elset-next=s;t=s;return h;void disp(STYPE*p)if(p=NULL)printf(NULL n);else11.5链表和结构体数组的区别while(p!=NULL)printf(%s(%d)n,p-data,p-count);p=p-next;printf(n);int main()STYPE*p;p=create();printf(Output the lb:n);disp(p);p=h;while(p!=NULL)printf(%s,p-data);p=p-next;LOGO