C语言链表(能看得懂的)PPT.ppt

Click to edit Master title,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,1,第十一章 链表,2,例：跳马。依下图将每一步跳马之后的位置,(x,y),放到一个,“,结点,”,里，再用,“,链子穿起来,”,，形成一条链，相邻两结点间用一个指针将两者连到一起。,结构的概念与应用,3,依上图有,7,个结点,(x1,y1),(x2,y2),(x6,y6),(x7,y7),为了表示这种既有数据又有指针的情况，引入结构这种数据类型。,4,11.7,用指针处理链表,链表是程序设计中一种重要的动态数据结构，它是动态地进行存储分配的一种结构。,动态性体现为：,链表中的元素个数可以根据需要增加和减少，不像数组，在声明之后就固定不变；,元素的位置可以变化，即可以从某个位置删除，然后再插入到一个新的地方；,5,1249,A,1356,B,1475,C,1021,D,Null,1,、链表中的元素称为,“,结点,”,，每个结点包括两个域：,数据域和指针域；,2,、单向链表通常由一个头指针（,head),，用于指向链表头；,3,、单向链表有一个尾结点，该结点的指针部分指向一个空结点,(NULL),。,Head 1249 1356 1475 1021,结点里的指针是存放下一个结点的地址,6,链表中结点的定义,链表是由结点构成的，关键是定义结点,;,链表的结点定义打破了先定义再使用的限制,即可以用自己定义自己；,递归函数的定义也违反了先定义再使用；,这是,C,语言程序设计上的两大特例,7,链表的基本操作,对链表的基本操作有：,（,1,）,创建链表是,指，从无到有地建立起一个链表，即往空链表中依次插入若干结点，并保持结点之间的前驱和后继关系。,（,2,）,检索操作,是指，按给定的结点索引号或检索条件，查找某个结点。如果找到指定的结点，则称为检索成功；否则，称为检索失败。,（,3,）,插入操作,是指，在结点,k,i-1,与,k,i,之间插入一个新的结点,k,使线性表的长度增,1,，且,k,i-1,与,k,i,的逻辑关系发生如下变化：,插入前，,k,i-1,是,k,i,的前驱，,k,i,是,k,i-1,的后继；插入后，新插入的结点,k,成为,k,i-1,的后继、,k,i,的前驱,.,8,（,4,）,删除操作,是指，删除结点,k,i,，使线性表的长度减,1,，且,k,i-1,、,k,i,和,k,i+1,之间的逻辑关系发生如下变化：,删除前，,k,i,是,k,i+1,的前驱、,k,i-1,的后继；删除后，,k,i-1,成为,k,i+1,的前驱，,k,i+1,成为,k,i-1,的后继,.,(5),打印输出,9,一个指针类型的成员既可指向其它类型的结构体数据，也可以指向自己所在的结构体类型的数据,99101,89.5,99103,90,99107,85,num,Score,next,next,是,struct student,类型中的一个成员，它又,指向,struct student,类型,的数据。,换名话说：,next,存放下一个结点的地址,10,11.7.2,简单链表,#define NULL 0,struct 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.next=,b.next=,c.next=NULL;,p=head;,do,printf(%ld%5.1fn,p-num,p-score);,p=p-next,;while(,p!=NULL,);,例,11.7,建立和输出一个简单链表,各结点在程序中定义，不是临时开辟的，始终占有内容,不放,，这种链表称为,“,静态链表,”,11,11.7.3,处理动态链表所需的函数,C,语言使用系统函数,动态,开辟和释放存储单元,1.malloc,函数,函数原形：,void*malloc(unsigned int size);,作用：,在内存的动态存储区中分配,一个,长度为,size,的连续空间。,返回值：,是一个指向分配域起始地址的指针（基本类型,void,）。,执行失败：,返回,NULL,12,函数原形,:,void*calloc(unsigned n,unsigned size);,作用：,在内存动态区中分配,n,个,长度为,size,的连续空间。,函数返回值,：指向分配域起始地址的指针,执行失败：返回,null,主要用途,：为一维数组开辟动态存储空间。,n,为数组元素个数，每个元素长度为,size,2.calloc,函数,13,3.free,函数,函数原形：,void freevoid,*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,）,15,11.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;,16,11.7.4,建立动态链表,99101,89.5,head,P1,p2,1,.,任务是开辟结点和输入数据,2.,并建立前后相链的关系,待插入的结点,p1,数据部分初始化,该结点被头结点,head,、尾结点,p2,同时指向,.,17,图,11.14,99101,89.5,head,p2,99103,90,p1,99101,89.5,head,p2,99103,90,p1,(a),(b),p1,重复申请待插入结点空间，对该结点的数据部分赋值（或输入值）,P2-next,指向,p1,新开辟的结点。,18,图,11.14,head,99101,89.5,p1,p2,99103,90,(c),P2,指向新结点,p2=p1,19,图,11.15,99101,89.5,99101,89.5,p2,99107,85,p1,head,99101,89.5,99101,89.5,p2,99107,85,p1,head,(a),(b),20,图,11.16,99103,90,99107,85,p2,0,0,p1,head,99101,89.5,99103,90,99107,85,NULL,p2,0,0,p1,head,99101,89.5,21,例,11.8,建立一个有,3,名学生数据的单向动态链表,#define NULL 0,#define LEN sizeof(struct student),struct student,long 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,结构体类型数据的长度，,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,p2-next=NULL;return(head);/,返回链表的头指针,算法：,p1,指向新开的结点,:,p1=(stuct student*)malloc(LEN);,p1,的所指向的结点连接在,p2,所指向结点后面，用,p2-next=p1,来实现。,p2,指向链表中最后建立的结点，,:,p2=p1;,头指针指向,p1,结点,P1,开辟的新结点链到了,p2,的后面,P1,继续开辟新结点,给新结点赋值此,23,11.7.5,输出链表,链表遍历,1.,单向链表总是从头结点开始的；,2.,每访问一个结点，就将当前指针向该结点的下一个结点移动：,p=p-next,;,3.,直至下一结点为空,P=NULL,24,图,11.18,head,p,P,P,NULL,25,例题,9,void print(struct student*head),struct studentp,;,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,);,26,11.7.6,对链表的删除操作,删除结点原则：,不改变原来的排列顺序，只是从链表中分离开来，撤消原来的链接关系。,两种情况：,1,、要删的结点是头指针所指的结点则直接操作；,2,、不是头结点，要依次往下找。,另外要考虑：空表和找不到要删除的结点,27,链表中结点删除,需要由两个临时指针：,P1:,判断指向的结点是不是要删除的结点（用于寻找）；,P2:,始终指向,P1,的前面一个结点；,28,图,11.19,A,B,D,E,C,A,B,D,E,C,(a),(B),29,图,11.20,99101,head,p1,99103,99107,NULL,（,a,）,(b),99101,head,99103,99107,NULL,p2,p1,原链表,P1,指向头结点,P2,指向,p1,指向的结点。,P1,指向下移一个结点。,30,图,11.20,99101,head,99103,99107,NULL,p1,99101,head,99103,99107,NULL,p2,p1,(c),(d),经判断后，第,1,个结点是要删除的结点，,head,指向第,2,个结点，第,1,个结点脱离。,经,P1,找到要删除的结点后使之脱离。,31,例 题,10,struct 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);,找到了,没找到,32,11.7.7,对链表的插入操作,插入结点：将一个结点插入到已有的链表中,插入原则：,1,、插入操作不应破坏原链接关系,2,、插入的结点应该在它该在的位置,实现方法：,应该有一个插入位置的查找子过程,共有三种情况：,1,、插入的结最小,2,、插入的结点最大,3,、插入的结在中间,33,操 作 分 析,同删除一样，需要几个临时指针：,P0:,指向待插的结点,;,初始化：,p0=,数组,stu;,P1:,指向要在,P1,之前插入结点；初始化,:p1=head;,P2:,指向要在,P2,之后插入结点；,插入操作：当符合以下条件时：,p0-num,与,p1-num,比较找位置,if(p0,-,num,p1,-,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.22,99101,head,p1,99103,99107,NULL,（,a,）,99102,p0,35,图,11.22,99101,head,99103,99107,NULL,99102,p0,p2,p1,(b),36,例 题,11,struct 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,指向的结点之后,插到最后的结点之后,链接,37,5,head,6,10,15,null,12,8,课堂举例：,已有一个如图所示的链表；,它是按结点中的整数域从小到大排序的，现在要插入一个结点，该结点中的数为,10,待插入结点,此结点已插入链表,38,分析：,按三种情况,1,、第一种情况，链表还未建成（空链表），待插入结点,p,实际上是第一个结点。这时必然有,head=null,。只要让头指针指向,p,就可以了。语句为,6,null,head,p,head=p;,p-next=null;,2,、第二种情况，链表已建成，待插入结点,p,的数据要比头结点的数据还要小，这时有,(,p-num)num),当然,p,结点要插在,head,结点前。,39,6,head,8,5,12,null,head,p,p-next=head;,head=p;,语句为,null,40,3,、第三种情况，链表已建成，待插入结点,p,的数据比头结点的数据大，需要找到正确的插入位置。这时，可以借助两个结构指针,r,和,g,，利用循环比较来找到正确位置。然后将结点,p,插入到链表中正确的位置。,参见下面的图示,41,6,head,8,12,13,null,p,15,g,r,说明：,这种情况下，,p,结点已经与链表的第一个结点比较过了，所以从链表的下一个结点开始比较。,138,，继续比较。,42,6,head,8,12,13,null,p,15,g,r,说明：,1312,，继续比较。,43,6,head,8,12,13,p,15,g,r,null,说明：,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,r,if(*phead)=null)/,第一种情况,，链表为空,*phead=p;/,链表头指向,p,return;/,完成插入操作，返回,else/链表不为空,/,第二种情况,，,p结点num值小于链表头结点的num值,if(*,p,head)-num p-num),/将p结点插到链表头部,p-next=*,p,head;/将p的next指针指向链表头(*,p,head),*,p,head=p;,/将链表头赋值为p,return;,/返回,46,/,第三种情况,，循环查找正确位置,r=*,p,head;/r赋值为链表头,q=(*,p,head)-next;/q赋值为链表的下一个结点,while(q!=null),/,利用循环查找正确位置,/判断当前结点num是否小于p结点的num,if(q-num num),r=q;/r赋值为q，即指向q所指的结点,q=q-next;/q指向链表中相邻的下一个结点,else/找到了正确的位置,break;/退出循环,/将p结点插入正确的位置,r-next=p;,p-next=q;,47,/被调用函数，形参为ST结构指针,，用于输出链表内容,void print(struct numST*head),int k=0;/整型变量，用于计数,struct numST*r;/声明r为ST结构指针,r=head;/r赋值为head，即指向,链表头,while(r!=null)/当型循环，链表指针不为空,则继续,/循环体开始,k=k+1;/计数加1,printf(%d%dn,k,r-num);,r=r-next;,/,取链表中相邻的下一个结点,/循环体结束,48,void main()/主函数开始,/函数体开始,struct numST*head,*p;/ST型结构指针,head=null;,/分配两个ST结构的内存空间，用于构造链表,head=(struct numST*)malloc(LEN);,head-next=(struct numST*)malloc(LEN);,/为链表中的两个结点中的num赋值为5和10,head-num=5;,head-next-num=10;,head-next-next=null;/链表尾赋值为空,/构造一个结点p，用于插入链表,p=(struct numST*)malloc(LEN);,p-num=8;,p-next=null;,insert(,/调用create函数建立链表，,print(head);/调用print函数，输出链表内容,/主函数结束,49,说明：,函数,insert(),的第一个形参为,struct numST*,类型，即“指针的指针”。调用时送入的实参是链表头指针的地址，即程序中的,&head,。这样对,head,的修改才会在函数返回后仍有效。如果形参为,struct numST*,，则传入的为指针，当函数返回后，,head,无法改变。,50,11.8,共用体,构造类型之二,联合,在同一存储单元里，根据需要放不同类型的数据，,使用覆盖技术。,51,11.8.1,概念,单元起始地址：,1000,。三个变量（数据）占用同一单元：,1000,1003,浮点型（,4 byte,）,字符型（,1 byte,）,整型（,2Byte,）,52,共用体变量的定义,格式（一般形式）：,union,联合类型名,成员列表,变量列表；,11.8.2,共用体变量的引用方式,同结构类型变量的引用格式：,变量名,.,成员名,53,格式与结构类型的定义和变量声明形式上类似，但实质上有区别：,结构类型的长度,=,各成员的长度和；各成员占独立的存储单元，不共享；,联合类型的长度为成员中长度的最大者，各成员共享长度最大的存储单元；,54,11.8.3,共用体类型数据的特点,虽然同一内存单元内可以存放不同类型（同一地址）、不同长度的数据，但任一时刻，只有一种类型数据（最后赋值的）起作用；其它的都没有意义；,不能对共用体变量整体赋值，也不能对其初始化。,共用变量不可作为函数的参数，但可以通过指针指向；,共用体类型可以和结构类型,/,数组类型互为基类型；,p289,55,例 题,12,struct,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,”,56,if(personi.job=s),scanf(%d,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,开始，依次增。,61,例 题,13,/*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,delete_string(str,c);print_string(str);,/*file2.c,文件,2*/,#include,enter_string(char str80),gets(str);,62,续,for(i=0;ix,p-y);,p=p-next;/p,指向下一个结点,i=i+1;/,计数加,1,while(p!=null);/,未到达链表尾部，则继续循环,/,主函数结束,71,用结构数组，利用键盘输入结点中的数据。重点看,scanf(,“,d,”,ni.x=a;,结构数组，数组中的元素为结构类型的数据，如,n8,/,结构,2.c,#include/预编译命令,#define null 0/定义空指针常量,struct TM/定义TM结构,int x,y;/整型变量x,y,struct TM*next;,/指向TM结构的指针,;,72,void 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,ni.x=a;,/将a的值赋给结构ni的元素x,printf(输入n%d的yn,i);/提示输入第i个结构的y值,scanf(%d,/输入b,ni.y=b;,/将b的值赋给结构ni的元素y,/循环体结束,73,head=/链表头部指向n1,for(i=1;ix,p-y);,p=p-next;/p指向相邻的下一个结点,i=i+1;/计数i加1,while(p!=null);,/未到链表尾部，则继续循环,/主函数结束,74,下面的程序与上面的程序区别仅在,scanf(“%d”,去替换,scanf(“%d”,ni.x=a;,/,结构,3.c,#include/预编译命令,#define null 0/定义空指针常量,struct TM/定义TM结构,int x,y;/整型变量x,y,struct TM*next;,/指向TM结构的指针,;,75,void 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,printf(输入n%d的yn,i);/提示输入第i个结构的y值,scanf(%d,/输入ni.y,/循环体结束,76,head=/链表头部指向n1,for(i=1;inum,赋值为,1,，让指针域赋值为,null,。之后让链头指针,head,指向第,1,个结点。利用指针,q,记住这个结点，以便让指针,p,去生成下面的结点。,（,2,）利用一个计数循环结构，做出第,2,个结点到第,nn,个结点。并将相邻结点一个接一个链接到一起。,（,3,）最后一个结点要和头结点用下一语句链接到一起,tail=q;tail-next=head;,head,tail,q,84,5,、删结点的函数,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,head,2,8,tail,q,p,演示,85,这里,free(p),是释放,p,结点所占用的内存空间的语句。如果,mm,不是,1,而是,3,，程序会在,do-while,循环中，让,x,加两次,1,，,q,和,p,一起移动两次，,p,指向,3#,所在结点，,q,指向,2#,所在结点，之后仍然用上述三条语句删去,3#,所在的结点。,1,head,2,8,q,p,3,4,q,p,p,q,演示,86,这个,do-while,循环的退出条件是,q=q-next,。即当只剩下一个结点时才退出循环。当然猴王非其莫属了。这时，让头指针,head,指向,q,，,head,是全局变量，在主程序最后输出猴王时要用,head-num,。,参考程序如下：,7,head,q,87,#include/,预编译命令,#include/,内存空间分配,#define null 0/,定义空指针常量,/,定义常量，表示结构长度,#define LEN sizeof(struct mon),struct mon/,结构声明,int num;/,整型数，用于记录猴子号,struct mon*next;/mon,结构指针,;,struct mon*head,*tail;/mon,结构指针，全局变量,88,void create(int nn)/被调用函数,/函数体开始,int i;/整型变量i，用于计数,struct mon*p,*q;/声明mon结构指针p，q,/为p分配内存空间,p=(struct mon*)malloc(LEN);,p-num=1;/初始化p结点num域为1,p-next=null;/初始化p结点next域为空,head=p;/链表头指针head赋值为p,q=p;/q赋值为p,89,for(i=2;inum=i;/初始化p结点num域为i，表示猴子号,q-next=p;/将p结点加到链表尾部,q=p;/让q指向链表尾部结点,p-next=null;/链表尾部指向空,/循环体结束,tail=q;/链表尾,tail-next=head;,/链表尾部指向链表头，,/,形成循环链表,/函数体结束,90,/,被调用函数,select,，,mm,表示结点删除间隔,void select(int mm),/,函数体开始,int x=0;,/声明整型值,x,，并初始化为,0,struct mon*p,*q;,/,声明结构指针,p,，,q,q=tail;,/q,赋值为,tail,，指向循环链表尾部,do,/,直到型循环，用于循环删除指定间隔的结点,/,循环体开始,p=q-next;,/p,赋值为,q,相邻的下一个结点,x=x+1;,/x,加,1,if(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,为链表中剩余一个结点,/,函数体结束,91,void main(),/主函数开始,/函数体开始,int n,m;,/声明整型变量n,m,head=null;/初始化head为空,printf(请输入猴子数n);/提示信息,scanf(%d,/输入待插入结点数据,printf(请输入间隔mn);/提示信息,scanf(%d,/输入间隔,create(n);/调用函数create建立循环链表,select(m);,/调用函数select，找出剩下的猴子,printf(猴王是%d号n,head-num);/输出猴王,/函数体结束,