链表的基本概念.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,9.4 链表,9.4.1 链表的基本概念,例：在铁路的中转站，有10个集装箱待运。每,个集装箱上有如下五项说明：,箱号（比如,AZ81920）,货物名称（比如 苹果）,重量（比如 10吨）,发货地点（比如 山东）,到货地点（比如 广东）,1,2,如何在程序中来描述该列火车？,如何来描述火车头？,如何来描述每一个集装箱？,如何来描述各节车厢之间的链接关系？,3,DX11089,玩具,5吨,从上海,到深圳,CY20011,电饭锅,8吨,从上海,到湖南,AZ81920,花生,10吨,从山东,到广东,head,结点2,需要引入一种新的数据结构：,链表,。链表中的,每一个元素称为一个“,结点,”，每个结点都应该,包括两部分：一为用户需要使用的实际数据；,二为下一个结点的起始地址。另外，链表还有,一个头指针,head，,指向链表的首结点。,结点1,结点3,4,如何来实现链表结构？显然要用到结构体数据,类型。定义如下的结构体类型：,struct,Train_tag,struct Train_tag*next;,char Num8;,char Name10;,int,Weight;,char From20;,char To20;,数据域,指针域,5,9.4.2 对链表的操作,1.创建静态链表,在程序中定义一组结构体变量或一个结构体,数组，然后用它们来作为链表的结点，把它,们链接成一个链表的形式。,优点：不必去关心内存的分配与释放。,缺点：需要事先知道链表结点的个数。,6,DX11089,玩具,5吨,从上海,到深圳,CY20011,电饭锅,8吨,从上海,到湖南,AZ81920,花生,10吨,从山东,到广东,NULL,head,结点2,结点1,结点10,struct Train_tag,charNum8;/*,集装箱编号*/,charName10;/*,货物名称*/,intWeight;/*,货物重量*/,charFrom20;/*,发货地点*/,charTo20;/*,到货地点*/,struct Train_tag *next;/*,指向下一结点*/,array10,*head;,7,void Create(),int i;,head =/*,链表的头指针*/,for(i =0;i 10;i+),输入,arrayi,的各个成员变量的值；,if(i next=p，,把第一个结点的,next,指针去指向它，从而建立两个结点之间的链接关系。最后再把,q,指向新的结点。如下图：,head,q,p,DX11089,玩具,5吨,从上海,到深圳,图 链表的第二个结点建成,CY20011,电饭锅,8吨,从上海,到湖南,q,14,head,q,DX11089,玩具,5吨,从上海,到深圳,第三个结点加入链表的过程：,CY20011,电饭锅,8吨,从上海,到湖南,q,p,CZ21026,苹果,8吨,从山东,到福建,15,链表创建过程的结束：如果用户输入的,Weight,等于 0，意味着链表创建过程的结束，此时指针,q,所指向的就是链表的最后一个结点，所以要把该结点的,next,指针赋值为,NULL，,即执行,q-next=NULL，,表示这里已是链尾，后面不会再连结点。如下图：,head,DX11089,玩具,5吨,从上海,到深圳,CY20011,电饭锅,8吨,从上海,到湖南,q,NULL,AZ81920,花生,10吨,从山东,到广东,16,void Create(),int Weight;,head =p =q =NULL;,while(1),printf(,输入货物重量：);,scanf(%d,if(Weight Weight =Weight;,输入该结点的其他信息；,if(head =NULL)head =p;/,新建的是首结点,else q-next =p;/,不是首结点,q =p;/q,指向当前尾结点,if(head !=NULL)q-next =NULL;,17,3.访问链表,在创建好一个链表之后，可以依次地访问该,链表当中的各个结点的数据。,void Display(),struct Train_tag *p;,p =head;,while(p !=NULL),printf(%s,%s,%d,%s,%sn,p-Num,p-Name,p-Weight,p-From,p-To);,p =p-next;,18,4.删除链表结点,假设列车现在到达长沙站，因此需要把到货,地点为湖南的车厢（假设有且仅有一节），,从列车上摘下来，然后列车继续向南行驶。,这里就需要用到链表结点的删除技术。,19,head,DX11089,玩具,5吨,从上海,到湖南,CY20011,电饭锅,8吨,从上海,到深圳,NULL,AZ81920,花生,10吨,从山东,到广东,情形一、待删除的是首结点,p,head =p-next;,20,DX11089,玩具,5吨,从上海,到深圳,CY20011,电饭锅,8吨,从上海,到湖南,AZ81920,花生,10吨,从山东,到广东,情形二、待删除的不是首结点,p,q,q-next,=p-next;,21,void Delete(),struct Train_tag *p,*q;,if(head =NULL)printf(,空链表);,return;,p =head;,while(p !=NULL)&strcmp(p-To,湖南),q =p;,p =p-next;/,把指针,p,往后移动一个结点,if(p !=NULL)&!strcmp(p-To,湖南),if(p =head),head =p-next;/,删除的是首结点,else,q-next =p-next;/,删除的是中间结点,22,5.插入链表结点,原则：,插入操作不应破坏原有链接关系；,需要插入的这个结点应该把它放在合适的位置上，也就是说，应该有一个插入位置的查找过程。,23,3,head,4,7,10,NULL,8,6,先看下面一个简单的例子：,已有一个如图所示的链表。它是按结点中的货物重量从小到大排序的。现在要插入一个新的结点，该结点的货物重量为7吨。,24,定义：,struct Train_tag *head;/,头指针,struct Train_tag *p;/,链表当前结点,struct Train_tag *q;/,链表上一结点,struct Train_tag *pNode;/,待插入的结点,25,NULL,head,DX11089,玩具,5吨,从上海,到湖南,pNode,head =pNode;,第一种情况：链表为空，即,head=NULL,待插入的,pNode,结点就是链表中的第一个结点。,26,pNode-next =head;,head =pNode;,第二种情况：,pNode,结点的,Weight,值小于等于链表首结点的,Weight,值，即,pNode,-Weight Weight,这时要将,pNode,结点插入到首结点的前面，即,执行以下两条语句：,27,这种情况如下图,5,10,4,NULL,15,NULL,head,pNode,pNode-next =head;,head =pNode;,28,第三种情况：,即,pNode,结点的,Weight,要大于首结点的,Weight,值，这时肯定地说,pNode,结点要插入到首结点之,后，但究竟插入到哪里需要先找到正确的位置。,我们设指针,q,和指针,p,分别指向相邻的两个结点，,q,在前,p,在后（即,q,更靠近首结点）。,首先让,q=head，,让,p=head-next，,然后让它们,顺序往后移动，每次移动一个结点。当着满足：,q-Weight Weight Weight,时，,pNode,就插在,q,与,p,之间。,29,5,10,12,NULL,15,NULL,head,pNode,移动指针：,q =p;,p =p-next;,p,q,p,q,插入结点：,pNode-next =p;,q-next =pNode;,30,void Insert(struct Train_tag *pNode),struct Train_tag *p,*q;,/,第一种情形，链表为空,if(head =NULL),head =pNode;,return;,/,第二种情形，新结点的,Weight,小于等于首结点,if(pNode-Weight Weight),pNode-next =head;,head =pNode;,return;,31,/第三种情形，循环地查找正确的插入位置,q =head;p =head-next;,while(p !=NULL),if(pNode-Weight Weight),break;,else,q =p;,p =p-next;,/,将,pNode,结点插入在正确的位置(,q,和,p,之间),pNode-next =p;,q-next =pNode;,32,while(p !=NULL),if(pNode-Weight Weight),break;,else,q =p;,p =p-next;,如果新结点的,Weight,大于所有结点？,在这种情形下，当循环语句结束后，指针,q,是,指向链表的尾结点，而指针,p=NULL。,33,5,10,17,NULL,15,NULL,head,pNode,q,插入结点：,pNode-next =p;,q-next =pNode;,p,NULL,NULL,34,6.链表的释放,对于静态链表，它们所占用的内存空间是由系统自动来分配和释放的；,对于动态链表，必须由程序员自己来进行内存的分配与释放。,35,void Destroy(),struct Train_tag *p,*q;,p =head;,while(p !=NULL),q =p;,p =p-next;,free(q);,head,DX11089,玩具,5吨,从上海,到深圳,CY20011,电饭锅,8吨,从上海,到湖南,CZ21026,苹果,8吨,从山东,到福建,p,q,p,q,p,q,head =NULL;,36,9.4.3 环形链表,环形链表：一种特殊的链表，其尾结点的,next,指针，又指向了链表的首结点，从而形,成了一个圆环。,从环形链表的任何一个结点出发，都可以遍,历整个的链表。,37,学校给高一（三）班分配了一个名额，去参加奥运会的开幕式。每个人都争着要去，可是名额只有一个，怎么办？班长想出了一个办法，让班上的所有同学围成一圈，按照顺时针方向进行编号。然后随便选定一个数,m，,并且从1号同学开始按照顺时针方向依次报数，1,2,m，,凡报到,m,的同学，都要主动退出圈子。然后不停地按顺时针方向逐一让报出,m,者出圈，最后剩下的那个人就是去参加开幕式的人。,问题描述：,38,1,2,3,4,5,6,7,8,3,6,1,5,2,8,4,退出圈子的顺序：,演示：,n=8,m=3,起始位置,幸运儿！,39,定义一个名为,STUDENT,的结构体类型,struct STUDENT int number;/,表示同学的编号,struct STUDENT *next;/,指向下一位同学,struct STUDENT *head,*tail,*p,*prev;,int n,m,i,j;,数据结构,40,模块1：输入学生的个数,n,和不吉利的数字,m,然后验证它们的有效性；,模块2：创建一个环形链表，模拟众同学围成 一圈的情形；,模块3：进入循环淘汰环节，模拟从1到,m,报数,让,n-1,个同学逐一退出圈子的过程；,模块4：输出结果。,基本思路,41,模块2，创建,环形,链表,（1）动态地为每一个结点分配内存空间，并 顺序地进行编号；,（2）把各个结点按照编号顺序链接成一条环 形链表；,（3）用,head,指向链表的第一个结点，用,tail,指向链表的最后一个结点。,42,模块2，创建,环形,链表,1,2,n,head,tail,tail,3,tail,tail,43,模块3，循环淘汰环节,1,2,n,3,tail,prev,4,head,prev,prev,p,假设,m=3,44,参考程序,：,略,45,END,46,