C语言链表详解PPT课件.ppt

1第十一章 链表2结构的概念与应用3依上图有7个结点(x1,y1)(x1,y1)(x2,y2)(x2,y2)(x6,y6)(x6,y6)(x7,y7)(x7,y7)411.7 用指针处理链表链表是程序设计中一种重要的动态数据结构，它是动态地进行存储分配的一种结构。动态性体现为：n链表中的元素个数可以根据需要增加和减少，不像数组，在声明之后就固定不变；n元素的位置可以变化，即可以从某个位置删除，然后再插入到一个新的地方；512491249 A A13561356 B B14751475 C C10211021 D DNullNull1、链表中的元素称为“结点”，每个结点包括两个域：数据域和指针域；2、单向链表通常由一个头指针（head)，用于指向链表头；3、单向链表有一个尾结点，该结点的指针部分指向一个空结点(NULL)。Head 1249 1356 1475 1021结点里的指针是存放下一个结点的地址6链表中结点的定义q链表是由结点构成的，关键是定义结点;q链表的结点定义打破了先定义再使用的限制,即可以用自己定义自己；q递归函数的定义也违反了先定义再使用；这是C语言程序设计上的两大特例7链表的基本操作对链表的基本操作有：（1）创建链表是指，从无到有地建立起一个链表，即往空链表中依次插入若干结点，并保持结点之间的前驱和后继关系。（2）检索操作是指，按给定的结点索引号或检索条件，查找某个结点。如果找到指定的结点，则称为检索成功；否则，称为检索失败。（3）插入操作是指，在结点ki-1与ki之间插入一个新的结点k，使线性表的长度增1，且ki-1与ki的逻辑关系发生如下变化：插入前，ki-1是ki的前驱，ki是ki-1的后继；插入后，新插入的结点k成为ki-1的后继、ki的前驱.8（4）删除操作是指，删除结点ki，使线性表的长度减1，且ki-1、ki和ki+1之间的逻辑关系发生如下变化：删除前，ki是ki+1的前驱、ki-1的后继；删除后，ki-1成为ki+1的前驱，ki+1成为ki-1的后继.(5)打印输出9一个指针类型的成员既可指向其它类型的结构体数据，也可以指向自己所在的结构体类型的数据991019910189.589.59910399103909099107991078585numScorenextnext是struct student类型中的一个成员，它又指向struct student类型的数据。换名话说：next存放下一个结点的地址1011.7.2 简单链表#define NULL 0struct student long num;float score;struct student *next;main()struct student a,b,c,*head,*p;a.num=99101;a.score=89.5;b.num=99103;b.score=90;c.num=99107;c.score=85;head=&a;a.next=&b;b.next=&c;c.next=NULL;p=head;do printf(%ld%5.1fn,p-num,p-score);p=p-next;while(p!=NULL);建立和输出一个简单链表各结点在程序中定义，不是临时开辟的，始终占有内容不放，这种链表称为“静态链表”11 11.7.3 处理动态链表所需的函数C 语言使用系统函数动态开辟和释放存储单元1.malloc 函数 函数原形：void*malloc(unsigned int size);作用：在内存的动态存储区中分配 一个 长度为size的连续空间。返回值：是一个指向分配域起始地址的指针（基本类型void）。执行失败：返回NULL12函数原形:void*calloc(unsigned n,unsigned size);作用：在内存动态区中分配 n个 长度为size的连续空间。函数返回值：指向分配域起始地址的指针执行失败：返回null主要用途：为一维数组开辟动态存储空间。n 为数组元素个数，每个元素长度为size2.calloc 函数133.free 函数函数原形：void free(void*p);作用：释放由 p 指向的内存区。P:是最近一次调用 calloc 或 malloc 函数时返回的值。free 函数无返回值动态分配的存储单元在用完后一定要释放，否则内存会因申请空间过多引起资源不足而出现故障。14结点的动态分配ANSI C 的三个函数(头文件 malloc.h)void*malloc(unsigned int size)void*calloc(unsigned n,unsigned size)void free(void*p)C+的两个函数new 类型（初值）delete 指针变量 /*表示释放数组，可有可无）*/使用 new 的优点：可以通过对象的大小直接分配，而不管对象的具体长度是多少（p340 例14.10）1511.7.4 建立动态链表基本方法:三个结点（头结点head、尾结点 NULL 和待插入结点 P）第一步：定义头结点head、尾结点 p2 和待插入结点p1，待插入的结点数据部分初始化；第二步：该结点被头结点、尾结点同时指向。P1=p2=(struct student*)malloc(LEN);头指针部分为空，head=NULL;第三步：重复申请待插入结点空间，对该结点的数据部分赋值（或输入值），将该结点插入在最前面，或者最后面（书上在尾部插入）.P2-next=P1;P2=P1;最后:P2-next=NULL;*head,*p1,*p2使用malloc(LEN)P2-next=NULL;1611.7.4 建立动态链表991019910189.589.5headP1p21.任务是开辟结点和输入数据2.并建立前后相链的关系待插入的结点p1数据部分初始化,该结点被头结点head、尾结点p2同时指向.17图11.14991019910189.589.5headp299103991039090p1991019910189.589.5headp299103991039090p1(a)(b)p1重复申请待插入结点空间，对该结点的数据部分赋值（或输入值）P2-next 指向p1新开辟的结点。18图11.14head991019910189.589.5p1p299103991039090(c)P2指向新结点p2=p119图11.15991019910189.589.5991019910189.589.5p299107991078585p1head991019910189.589.5991019910189.589.5p299107991078585p1head(a)(b)20 图11.169910399103909099107991078585p20 00 0p1head991019910189.589.59910399103909099107991078585NULLNULLp20 00 0p1head991019910189.589.521例11.8 建立一个有3名学生数据的单向动态链表#define NULL 0#define LEN sizeof(struct student)struct studentlong num;float score;struct student*next;int n;struct student*creat(void)struct student*head;struct student*p1,*p2;n=0;p1=p2=(struct student*)malloc(LEN);scanf(%1d,%f,&p1-num,&p1-score);head=NULL;结构体类型数据的长度，sizeof是“字节数运算符”定义指针类型的函数。带回链表的起始地址开辟长度为LEN的内存区P1,p2是指向结构体类型数据的指针变量，强行转换成结构体类型假设头指向空结点22续while(p1-num!=0)n=n+1;/*n 是结点的个数*/if(n=1)head=p1;else p2-next=p1;p2=p1;p1=(struct student*)malloc(LEN);scanf(%1d,%f,&p1-num,&p1-score);p2-next=NULL;return(head);/返回链表的头指针算法：p1指向新开的结点:p1=(stuct student*)malloc(LEN);p1的所指向的结点连接在p2所指向结点后面，用p2-next=p1来实现。p2 指向链表中最后建立的结点，:p2=p1;头指针指向p1结点P1开辟的新结点链到了p2的后面P1继续开辟新结点给新结点赋值此2311.7.5 输出链表链表遍历1.单向链表总是从头结点开始的；2.每访问一个结点，就将当前指针向该结点的下一个结点移动：p=p-next;3.直至下一结点为空 P=NULL24图 11.18headp PPNULLNULL25void print(struct student*head)struct student*p;printf(nNow,These%d records are:n,n);p=head;if(head!=NULL)do printf(%ld%5.lfn,p-num,p-score);p=p-next;while(p!=NULL);2611.7.6 对链表的删除操作删除结点原则：不改变原来的排列顺序，只是从链表中分离开来，撤消原来的链接关系。两种情况：1、要删的结点是头指针所指的结点则直接操作；2、不是头结点，要依次往下找。另外要考虑：空表和找不到要删除的结点27链表中结点删除需要由两个临时指针：P1:判断指向的结点是不是要删除的结点（用于寻找）；P2:始终指向P1的前面一个结点；28图11.19ABDECABDEC(a)(B)29图11.209910199101headp199103991039910799107NULLNULL（a）(b)9910199101head99103991039910799107NULLNULLp2p1原链表P1指向头结点P2指向p1指向的结点。P1指向下移一个结点。30图11.209910199101head99103991039910799107NULLNULLp19910199101head99103991039910799107NULLNULLp2p1(c)(d)经判断后，第1个结点是要删除的结点，head指向第2个结点，第1个结点脱离。经P1找到要删除的结点后使之脱离。31struct student*del(struct student*head,long num)struct student *p1,*p2;if(head=NULL)printf(nlist null!n);goto end;p1=head;while(num!=p1-num&p1-next!=NULL)p2=p1;p1=p1-next;if(num=p1-num)if(p1=head)head=p1-next;else p2-next=p1-next;printf(delete:%ldn,num);n=n-1;else printf(%ld not been found!n,num);end:return(head);找到了没找到3211.7.7 对链表的插入操作插入结点：将一个结点插入到已有的链表中插入原则：1、插入操作不应破坏原链接关系2、插入的结点应该在它该在的位置实现方法：应该有一个插入位置的查找子过程共有三种情况：1、插入的结最小2、插入的结点最大3、插入的结在中间33 操 作 分 析同删除一样，需要几个临时指针：P0:指向待插的结点;初始化：p0=数组stu;P1:指向要在P1之前插入结点；初始化:p1=head;P2:指向要在P2之后插入结点；插入操作：当符合以下条件时：p0-num 与 p1-num 比较找位置if(p0-nump1-num)&(p1-next!=NULL)则插入的结点不在p1所指结点之前；指针后移，交给p2；p1=p1-next;p2=p1;则继续与 p0 指向的数组去比，直到（p1-next!=NULL)为止。否则有两种情况发生：if(head=p1)head=p0;p0-next=p1插到原来第一个结点之前；else p2-next=p0;p0-next=p1;插到 p2 指向的结点之后；还有另外一种情况：插到最后的结点之后；p1-next=p0;p0-next=NULL;34图11.229910199101headp199103991039910799107NULLNULL（a）9910299102p035图11.229910199101head99103991039910799107NULLNULL9910299102p0p2p1(b)36struct student insert(struct student*head,struct student*stud)struct student*p0,*p1,*p2;p1=head;p0=stud;if(head=NULL;)head=p0;p0-next=NULL;else while(p0-nump1-num)&(p1-next!=NULL)p2=p1;p1=p1-next;if(p0-numnum)if(head=p1)head=p0;else p2-next=p0;p0-next=p1;else p1-next=p0;p0-next=NULL;n=n+1;return(head);原来的链表是空表P0指向要插的结点使p0指向的结点作为头结点使p2指向刚才p1指向的结点插到原来第一个结点之前插到p2指向的结点之后插到最后的结点之后链接375 5head6 610101515null12128 8课堂举例：已有一个如图所示的链表；它是按结点中的整数域从小到大排序的，现在要插入一个结点，该结点中的数为10待插入结点此结点已插入链表38分析：按三种情况1、第一种情况，链表还未建成（空链表），待插入结点p实际上是第一个结点。这时必然有head=null。只要让头指针指向 p 就可以了。语句为6nullheadphead=p;p-next=null;2、第二种情况，链表已建成，待插入结点 p 的数据要比头结点的数据还要小，这时有(p-num)num)当然p结点要插在head结点前。396head8512nullheadpp-next=head;head=p;语句为null403、第三种情况，链表已建成，待插入结点 p 的数据比头结点的数据大，需要找到正确的插入位置。这时，可以借助两个结构指针r 和 g，利用循环比较来找到正确位置。然后将结点 p 插入到链表中正确的位置。参见下面的图示416head81213nullp15gr说明：这种情况下，p 结点已经与链表的第一个结点比较过了，所以从链表的下一个结点开始比较。138，继续比较。426head81213nullp15gr说明：1312，继续比较。436head81213p15grnull说明：13next=p;p-next=g;44/结构7.c#include/预编译命令#include/内存空间分配#define null 0/定义空指针常量#define LEN sizeof(struct numST)/定义常量，表示结构长度struct numST/结构声明int num;/整型数struct numST*next;/numST结构指针;参考程序45/被调用函数insert()，两个形参分别表示链表和待插入的结点void insert(struct numST*phead,struct numST*p)/函数体开始struct numST*q,*r;/定义结构指针q,rif(*phead)=null)/第一种情况，链表为空*phead=p;/链表头指向preturn;/完成插入操作，返回else/链表不为空/第二种情况，p结点num值小于链表头结点的num值if(*phead)-num p-num)/将p结点插到链表头部 p-next=*phead;/将p的next指针指向链表头(*phead)*phead=p;/将链表头赋值为p return;/返回46/第三种情况，循环查找正确位置r=*phead;/r赋值为链表头q=(*phead)-next;/q赋值为链表的下一个结点while(q!=null)/利用循环查找正确位置/判断当前结点num是否小于p结点的numif(q-num num)r=q;/r赋值为q，即指向q所指的结点q=q-next;/q指向链表中相邻的下一个结点else/找到了正确的位置break;/退出循环/将p结点插入正确的位置r-next=p;p-next=q;2024/2/27 周二4748/被调用函数，形参为ST结构指针，用于输出链表内容void print(struct numST*head)int k=0;/整型变量，用于计数struct numST*r;/声明r为ST结构指针r=head;/r赋值为head，即指向链表头 while(r!=null)/当型循环，链表指针不为空则继续/循环体开始k=k+1;/计数加1printf(%d%dn,k,r-num);r=r-next;/取链表中相邻的下一个结点/循环体结束49void main()/主函数开始/函数体开始struct numST*head,*p;/ST型结构指针head=null;/分配两个ST结构的内存空间，用于构造链表head=(struct numST*)malloc(LEN);head-next=(struct numST*)malloc(LEN);/为链表中的两个结点中的num赋值为5和10head-num=5;head-next-num=10;head-next-next=null;/链表尾赋值为空/构造一个结点p，用于插入链表p=(struct numST*)malloc(LEN);p-num=8;p-next=null;insert(&head,p);/调用create函数建立链表，print(head);/调用print函数，输出链表内容/主函数结束50说明：函数insert()的第一个形参为struct numST*类型，即“指针的指针”。调用时送入的实参是链表头指针的地址，即程序中的&head。这样对head的修改才会在函数返回后仍有效。如果形参为struct numST*，则传入的为指针，当函数返回后，head无法改变。5111.8 共用体 构造类型之二联合在同一存储单元里，根据需要放不同类型的数据，使用覆盖技术。5211.8.1 概念单元起始地址：1000。三个变量（数据）占用同一单元：1000 1003浮点型（浮点型（4 byte）字符型（字符型（1 byte）整型（整型（2Byte）53共用体变量的定义格式（一般形式）：union 联合类型名 成员列表 变量列表；11.8.2 共用体变量的引用方式同结构类型变量的引用格式：变量名.成员名54格式与结构类型的定义和变量声明形式上类似，但实质上有区别：1.结构类型的长度=各成员的长度和；各成员占独立的存储单元，不共享；2.联合类型的长度为成员中长度的最大者，各成员共享长度最大的存储单元；5511.8.3 共用体类型数据的特点56struct int num;char name10;char sex;char job;union int class;char position10;category;person2;main()int n,i;for(i=0;i2;i+);scanf(%d，%s，%c，%c”,&personi.num,personi.name,&personi.sex,&personi.job);57 if(personi.job=s)scanf(%d,&personi.category.class);else if(personi.job=t)scanf(%s,personi.category.position);else printf(input error!);printf(n);printf(no.name sex job class/positionn);for(i=0;iSun、Sat最大。（4）枚举元素的值也是可以人为改变的：在定义时由程序指定。例如，如果enum weekdays Sun=,Mon,Tue,Wed,Thu,Fri,Sat；则Sun=，Mon=，从Tue=2开始，依次增。62/*file1.c文件1*/main()extern enter-string(char str80);extern delete-string(char str,char ch);extern print-string(char str);char c;char str80;enter_string(str);scanf(%c,&c);delete_string(str,c);print_string(str);/*file2.c 文件2*/#includeenter_string(char str80)gets(str);63for(i=0;i2;i+)if(personi.job=s)printf(%-6d%-10s%-3c%-3c%-6dn,personi.num,personi.name,personi.sex,personi.job,personi.category.class);else printf(%-6d%-10s%-3c%-3c%-6sn,personi.num,personi.name,personi.sex,personi.job,personi.category.position);6411.10 用typedef 为类型定义新名字 除可直接使用提供的标准类型和自定义的类型（结构、共用、枚举）外，也可使用typedef定义已有类型的别名。该别名与标准类型名一样，可用来定义相应的变量。定义已有类型别名的方法如下：（1）按定义变量的方法，写出定义体；（2）将变量名换成别名；（3）在定义体最前面加上typedef。6511.10 用typeded 为类型定义新名字任何已有的类型可以重新命名typedef long integer;/将 long 重新命名为 integer，使得 integer 和 long 同等使用 可以和新类型定义一起定义名字typedef int ARR10;/定义了一个数组名 ARR，它是具有10个元素的整型数组类型typedef struct int num;float score;S;/*定义结构体别名为S*/STUDENT stu1;66讨论：typedef 和#define说明：（1）用typedef只是给已有类型增加个别名，并不能创造个新的类型。就如同人一样，除学名外，可以再取一个小名（或雅号），但并不能创造出另一个人来。（2）typedef与#define有相似之处，但二者是不同的：前者是由编译器在编译时处理的；后者是由编译预处理器在编译预处理时处理的，而且只能作简单的字符串替换。67struct TMint x,y;/结构TM的成员，x,y为整数型struct TM next/结构TM的成员，属TM型下面的表是马的跳步方案，从左下角跳到右上角结点n1n2n3n4n5n6n7xy00122443647284结构体与共体例子688 84 4NULLNULL为空地址下面是形成链表的一个参考程序2 24 4&n41 12 2&n30 00 0&n2&n1head69/结构1.c#include/预编译命令#define null 0/定义空指针常量struct TM/定义结构TMint x,y;/整型变量x,ystruct TM next;/指向TM结构的指针;void main()/主函数/主函数开始 int i;/声明整型变量 /声明TM结构n1n7,结构指针head,p struct TM n1,n2,n3,n4,n5,n6,n7,head,p;70/分别对TM结构n1n7中的x,y赋值 n1.x=0;n1.y=0;n2.x=1;n2.y=2;n3.x=2;n3.y=4;n4.x=4;n4.y=4;n5.x=6;n5.y=4;n6.x=7;n6.y=2;n7.x=8;n7.y=4;/head赋值为n1，即head指向n1 head=&n1;/n1n7构成链表 n1.next=&n2;n2.next=&n3;n3.next=&n4;n4.next=&n5;n5.next=&n6;n6.next=&n7;/n7的next指针赋值为空指针 n7.next=null;71p=head;/p赋值为head，即p指向head所指的内容i=1;/i赋值为1do/直到型循环/循环体开始/输出结点信息printf(结点%d:x=%d,y=%dn,i,p-x,p-y);p=p-next;/p指向下一个结点 i=i+1;/计数加1 while(p!=null);/未到达链表尾部，则继续循环/主函数结束72用结构数组，利用键盘输入结点中的数据。重点看scanf(“%d”,&a);ni.x=a;结构数组，数组中的元素为结构类型的数据，如n8/结构2.c#include/预编译命令#define null 0/定义空指针常量struct TM/定义TM结构int x,y;/整型变量x,ystruct TM*next;/指向TM结构的指针;73void main()/主函数/主函数开始 int i,a,b;/声明整型变量i,a,b /声明TM型结构数组n8，TM结构指针head,p struct TM n8,*head,*p;for(i=1;i=7;i=i+1)/循环/循环体开始 printf(输入n%d的xn,i);/提示输入第i个结构的x值 scanf(%d,&a);/输入a ni.x=a;/将a的值赋给结构ni的元素x printf(输入n%d的yn,i);/提示输入第i个结构的y值 scanf(%d,&b);/输入b ni.y=b;/将b的值赋给结构ni的元素y/循环体结束74head=&n1;/链表头部指向n1for(i=1;ix,p-y);p=p-next;/p指向相邻的下一个结点 i=i+1;/计数i加1 while(p!=null);/未到链表尾部，则继续循环/主函数结束75下面的程序与上面的程序区别仅在scanf(“%d”,&(ni.x);去替换scanf(“%d”,&a);ni.x=a;/结构3.c#include/预编译命令#define null 0/定义空指针常量struct TM/定义TM结构int x,y;/整型变量x,ystruct TM*next;/指向TM结构的指针;76void main()/主函数/主函数开始 int i,a,b;/声明整型变量i,a,b /声明TM型结构数组n8，TM结构指针head,p struct TM n8,*head,*p;for(i=1;i=7;i=i+1)/循环/循环体开始 printf(输入n%d的xn,i);/提示输入第i个结构的x值 scanf(%d,&(ni.x);/输入ni.x printf(输入n%d的yn,i);/提示输入第i个结构的y值 scanf(%d,&(ni.y);/输入ni.y/循环体结束77head=&n1;/链表头部指向n1for(i=1;inum赋值为1，让指针域赋值为null。之后让链头指针head指向第1个结点。利用指针q记住这个结点，以便让指针p去生成下面的结点。（2）利用一个计数循环结构，做出第2个结点到第nn个结点。并将相邻结点一个接一个链接到一起。（3）最后一个结点要和头结点用下一语句链接到一起tail=q;tail-next=head;headtailq855、删结点的函数select(int mm)mm为形式参数，从1至m报数，凡报到mm者删除其所在的结点。设计两个指针p和q。一开始让q指向链表的尾部q=tail。让p指向q的下一个结点。开始时让p指向1#猴所在的结点。用一个累加器x，初始时x=0，从1#猴所在结点开始让x=x+1=1，如果mm是1的话，1#猴所在的p结点就要被删除。有三条语句printf(“被删掉的猴子号为%d号n”,p-num);q-next=p-next;free(p);1 1head2 28 8tailqp演示86这里free(p)是释放p结点所占用的内存空间的语句。如果mm不是1而是3，程序会在do-while循环中，让x加两次1，q和p一起移动两次，p指向3#所在结点，q指向2#所在结点，之后仍然用上述三条语句删去3#所在的结点。1 1head2 28 8qp3 34 4q ppq演示87这个do-while循环的退出条件是q=q-next。即当只剩下一个结点时才退出循环。当然猴王非其莫属了。这时，让头指针head指向q，head是全局变量，在主程序最后输出猴王时要用head-num。参考程序如下：7 7headq88#include/预编译命令#include/内存空间分配#define null 0/定义空指针常量/定义常量，表示结构长度#define LEN sizeof(struct mon)struct mon/结构声明int num;/整型数，用于记录猴子号struct mon*next;/mon结构指针;struct mon*head,*tail;/mon结构指针，全局变量89void create(int nn)/被调用函数/函数体开始 int i;/整型变量i，用于计数struct mon*p,*q;/声明mon结构指针p，q/为p分配内存空间p=(struct mon*)malloc(LEN);p-num=1;/初始化p结点num域为1p-next=null;/初始化p结点next域为空head=p;/链表头指针head赋值为pq=p;/q赋值为p90for(i=2;inum=i;/初始化p结点num域为i，表示猴子号q-next=p;/将p结点加到链表尾部q=p;/让q指向链表尾部结点p-next=null;/链表尾部指向空/循环体结束tail=q;/链表尾tail-next=head;/链表尾部指向链表头，/形成循环链表/函数体结束91/被调用函数select，mm表示结点删除间隔void select(int mm)/函数体开始int x=0;/声明整型值x，并初始化为0struct mon*p,*q;/声明结构指针p，qq=tail;/q赋值为tail，指向循环链表尾部 do/直到型循环，用于循环删除指定间隔的结点/循环体开始p=q-next;/p赋值为q相邻的下一个结点x=x+1;/x加1if(x%mm=0)/x是否整除mm，/表示是否跳过指定间隔/输出被删掉的猴子号printf(被删掉的猴子号为%d号n,p-num);q-next=p-next;/删除此结点free(p);/释放空间else q=p;/q指向相邻的下一个结点pwhile(q!=q-next);/剩余结点数不为1，则继续循环head=q;/head指向结点q，q为链表中剩余一个结点/函数体结束92void main()/主函数开始/函数体开始int n,m;/声明整型变量n,mhead=null;/初始化head为空 printf(请输入猴子数n);/提示信息scanf(%d,&n);/输入待插入结点数据printf(请输入间隔mn);/提示信息scanf(%d,&m);/输入间隔 create(n);/调用函数create建立循环链表select(m);/调用函数select，找出剩下的猴子printf(猴王是%d号n,head-num);/输出猴王/函数体结束2024/2/27 周二93