[计算机软件及应用]链表-c--PPT课件

第11章链表,教学目标,链表的概念建立链表中指针的运用插入删除结点的思路与双指针作用建立循环链表的思路,链表属于动态数据结构，可以类比成一“环”接一“环”的链条，这里每一“环”视作一个结点，结点串在起形成链表。,11.1举例说明链表的概念,【任务11.1】某电视台希望王小二同学为他们编一个程序。该程序可以将节目串在一起，形成一份有序的节目预告。节目列表有如下三项,1、节目名称包括新闻联播（CCTVNews）祖国各地（Motherland）体育之窗（Sports）学校见闻（College）电影展播（Movie）2、节目主持人（Director）3、播放时间长度（Time）,我们可以将每一个节目单独放在一个结构里，用一个指针把两个结构连在一起，一天的节目形成一条链表。用一个所谓的头指针head指向链表的第一个结点。如下图所示,head,头指针,下面的程序是建立链表的过程。,11.2建立链表的过程,/*/*程序名：11_1.cpp*/*作者：wuwh*/*编制时间：2002年11月26日*/*主要功能：链表*/*#includeusingnamespacestd;structActList/定义一个名为ActList结构charActName20;/节目名为字符数组chardirector20;/主持人为字符数组intMtime;/节目长度为分钟ActList*next;/指向ActList结构的指针;,ActList*head;/链头指针ActList*Create()/定义一个指向AcitList结构/的指针函数，名为CreateActList*p=NULL;/指针，指向个待插入的结点ActList*q=NULL;/指针，用于在其后插入结点head=NULL;/一开始链表为空intTime;/节目时长，如为0则退出,/以下是给新结点输入节目信息coutTime;while(Time!=0)/当该节目的时长不为0时，将其/纳入链表中p=newActList;/分配内存空间给p结点p-Mtime=Time;/让Time赋给p结点的结构成员Mtimecoutp-ActName;/输入节目名称coutp-director;/输入主持人,if(head=NULL)/head为空，要插入第一个head=p;/结点，让头指针指向结点pelse/否则不是头结点，应将p结点q-next=p;/插入到q结点的后面q=p;/q指向当前最后一个结点coutTime;/输入下一个节目时长/一旦跳出while循环，说明有一个节目时长为0if(head!=NULL)q-next=NULL;/让q所指的最后一个结点的指针域为空说明这已是链尾了return(head);/返回头指针,voiddisplayList(ActList*head)coutMtimeActNamedirectornext;,intmain()/主函数开始/调用子函数displaList()/调用时的实参为Create()函数的返回值displayList(Create();return0;/主函数结束,说明1、先从主函数说起主函数只有一条语句displayList(Create();这是调用子函数displayList，该子函数的形参为ActList*head是一个指向ActList结构的名为head的指针变量。在主函数调用displayList时所用的实际参数来自运行Create()函数的返回值。从Create()的定义ActList*Create()看出Create()函数的返回值应该是一个指向ActList的指针。主函数在调用子函数时，又遇到该函数的实参又是调用另一个函数之后的返回值。看起来的确显得复杂，但是我们耐心分析之后，感到并不难。,2、程序开头为结构定义。在这里我们称这样的一个结构为一个结点。这个结点包含两个域：数据域和指针域,结点,数据域中装有节目的信息，而指针域装的是指向另一个结点的地址。显然这是为形成链表而专门设置的。,3、在定义Create函数之前，先定义了一个指向结构的头指针head，即ActList*head;4、定义Create函数，该函数可返回指向ActList结构的指针，即ActList*Create()分析这个函数的功能可分如下4块,定义ActList*p=NULL;ActList*q=NULL;head=NULL;intTime;定义了两个指向结构ActList的指针p和q，并初始化为空，即未指向任何地址。同时让头指针head也为空。再定义一个临时变量Time，是一个整型数。,提示“输入节目时长”，之后用键盘输入，用了下面两句：coutTime;这部分程序语句是为下面的while循环做准备的。如果Time不为0，才做下面的内容。,while(Time!=0)循环在当循环的循环体内完成建立链表的过程。首先给p结点分配内存空间。这个内存空间的大小要根据p结点的定义（p结点是ActList结构）来确定。接着下面就是几个赋值语句p-MTime=Time;coutp-ActName;/用键盘输入节目名称coutp-director;/用键盘输入主持人,接着是一个分支语句if(head=NULL)head=p;这是说如果头指针为空，表示链表还是空的，这时p结点就是第一个结点。让head指向p结点。之后让q=p;这是让q指向刚进入链表的结点，让p再去指向待加入的结点。如果p结点已不是第一个结点了，head必不为NULL，因此要走else分支，即elseq-next=p;,将此时的p结点放到q所指向的结点后面。之后让q=p;即让q指向刚进入链表的结点，腾出p去指向下一个待加入的结点。接下来输入下一个节目时长，coutTime;至此，while语句的循环体结束。当Time值不为0，就会有结点加入链表，继续执行循环体。一旦Time为0，则会跳出while循环。,执行两条语句if(head!=NULL)q-next=NULL;return(head);第一条是说，如果head不空说明链表已建成，这时q一定是最后一个结点，将该结点的指针域置成空，以表明它是链尾。,第二条return(head);将这条链表的头指针head返回。这件事意味着执行完Create函数后得到head指针所指向的地址，这个地址就是链表中的第一个结点的地址。这时对主函数而言displayList(Create()就是dispalyList(head)调用dsplayList(head)就会将整个链表从头至尾输出。,1、定义ActList结构，结构中包含数据域和指针域。将一个结构看作一个结点。2、定义一个指向结构的指针head，准备用来指向链表的第一个结点。3、定义一个指向ActList结构的指针函数，起名为Create函数，该函数返回的是创建好的链的头指针head。下面是Create函数所要做的事情：定义指向ActList结构的两个指针p和q，定义后立即初始化为NULL，即不指向任何地址。再让头指针head为NULL，也是不指向任何地址，表示该链表尚未建立，一个结点也没有。然后定义一个中间变量“节目时长Time”，当Time为0时，建立链表的过程应该结束。,建立链表的过程可归纳为如下三个步骤,下面程序的构思是，只要Time不为0，就要构建链表。构建的思路是将一个一个的结点加至链表里来。首先给p找一个能够指向的内存空间，我们说这是给p结点分配一片内存空间。如下图,建立链表的过程可归纳为如下三个步骤,p,然后，通过键盘往这个空间中装入与节目有关的信息。装完之后判断一下head为空否，如为空则p结点为第一个结点，让head指向p结点就完成了有一个结点的链表。之后让q赋值为p，即使让q指针去指向刚加入链表的结点，将p指针腾出来去做下一个结点的工作。,head,p,q,图链表的第一个结点建成,当Time不为0，p又被分配了内存空间，形成了第二个结点，装入节目信息后，判断head不再为空，说明前面已有结点在链表中，这时要将第二个结点放到q所指向的结点的后面。执行q-next=p之后就完成了。之后再将q指针移到第二个结点上，将p指针腾出来去做下一个结点的工作。,head,p,q,指针移到第二个结点上，将p指针腾出来去做下一个结点的工作。,head,q,第三个结点加入链表的过程为,head,q,p,最末一个结点连至链表的尾部之后，要在q指针所指向的最后一个机诶但的指针域加上一个NULL，表示这里是链尾了，后面再也不连结点了。,head,q,练习,1、按下表顺序输入某班的一个学习小组的成员表：,将学习小组形成一个链表，每人一个结点。结点中有4个成员：姓名、出生年、出生月、指针。建成链表后输出该链表。,链表结点的插入,链表结点的插入,原则：插入操作不应破坏原链接关系插入的结点应该在它该在的位置。应该有一个插入位置的查找子过程,head,先看下面一个简单的例子：已有一个如图所示的链表。它是按结点中的整数域从小到大排序的。现在要插入一个结点，该节点中的数为10。,待插入结点,此结点已插入链表,/*/*程序名：7_20.cpp*/*作者：wuwh*/*编制时间：2002年12月3日*/*主要功能：链表插入结点*/*#include/预编译命令structnumST/结构声明intnum;/整型数numST*next;/numST结构指针;,参考程序,/被调用函数insert()，两个形参分别表示链表和待插入的结点voidinsert(numST*/返回,/第三种情况，循环查找正确位置r=pHead;/r赋值为链表头q=pHead-next;/q赋值为链表的下一个结点while(q!=NULL)/利用循环查找正确位置/判断pNode结点的num是否大于当前结点numif(pNode-numq-num)r=q;/r赋值为q，即指向q所指的结点q=q-next;/q指向链表中相邻的下一个结点else/找到了正确的位置break;/退出循环/将pNode结点插入正确的位置r-next=pNode;pNode-next=q;,/被调用函数，形参为numST结构指针，用于输出链表内容voidprint(numST*pHead)intk=0;/整型变量，用于计数numST*r=pHead;/声明r为numST结构指针，/并赋值为pHead，即指向链表头while(r!=NULL)/当型循环，链表指针不为空则继续/循环体开始cout.width(2);/设置输出的序号k所占的宽度k=k+1;coutnumnext;/取链表中相邻的下一个结点/循环体结束/函数体结束,voidmain()/主函数开始/函数体开始numST*pMHead=NULL;/numST型结构指针，链表头numST*pMNode=NULL;/numST型结构指针，要插入的结点/两个指针均初始化为空/分配3个numST结构的内存空间，用于构造链表pMHead=newnumST;pMHead-next=newnumST;pMHead-next-next=newnumST;/为链表中的3个结点中的num赋值为5、10和15pMHead-num=5;pMHead-next-num=10;pMHead-next-next-num=15;pMHead-next-next-next=NULL;/链表尾赋值为空/构造一个结点p，用于插入链表pMNode=newnumST;pMNode-num=12;pMNode-next=NULL;insert(pMHead,pMNode);/调用insert函数将结点pMNode插入链表print(pMHead);/调用print函数，输出链表内容/与new对应，用delete释放空间/主函数结束,1、定义两个numST型结构指针*pMHead，*pMNode，并初始化pMHead和pMNode为NULL;2、分配3个numST结构的内存空间，用于构造链表（1）pMHead=newnumST;（2）pMHead-next=newnumST;（3）pMHead-next-next=newnumST;,先看主函数,pMHead,这3个numST结构的内存空间如上图所示。,pMHead-next,pMHead-next-next,下面用赋值语句往这3个空间中放num数据。最后的一个结点为队尾，在其指针域存放NULL。（4）pMHead-num=5;（5）pMHead-next-num=10;（6）pMHead-next-next-num=15;（7）pMHead-next-next-next=NULL;做了这4条之后形成了一条链表如下：,pMHead,该链表的头结点由pMHead所指向。,3、构造一个结点pMNode，在pMNode结点的数据域放12，再插入链表（1）pMNode=newnumST;（2）pMNode-num=12;（3）pMNode-next=NULL;4、调用insert函数来插入pMNode结点。语句为insert(pMHead,pMNode);意思是以将pMNode插入到以pMHead为队头的链表中。但这里在调用时，用pMHead作为实参，传递的是引用，而非传值。所以在函数体内对pHead的修改，就等价于对pMHead的操作。,这里要讲传值和传引用的区别,（1）如果是传值调用主程序中的调用语句为insert(pMHead,pMNode);被调用函数为voidinsert(munST*pHead,numST*pNode);,pMHead,pMNode,实际参数,形式参数,pNode,pHead,当着实际参数pMHead赋给了形式参数pHead之后，pHead就指向了已经存在了的链表，见下图。,pHead,这时原来的主函数中的头指针pMHead就不再起作用了，而是子函数中的pHead起作用。假如现在pNode中的结点数据为4小于5，应该将pNode插入到pHead所指向的结点前，如下图,pMHead,pMHead,pHead,被调用函数无法改变主函数的pMHead。虽然在子函数内pHead被修改，指向了含有四个结点的链表头，但当函数返回后，主函数中的pMHead仍然指向链表后面的三个结点，新插入的结点并没有包含进去。所以要想将新的插入到最前面的结点包含进去，就必须用传址或传引用。,pHead,（2）如果是传引用调用主程序中的调用语句为insert(pMHead,pMNode);被调用函数为voidinsert(munST*先看numST*/将表头指针指向p结点return;/返回主程序,在主程序中必然头指针pMHead指向pMNode结点。,第二种情况：pNode结点的num值小于等于链表头结点的num值，即pNode-numnum这时要将pNode结点插入到头结点的前面，要执行如下三条语句,pNode-next=pHead;/在pNode结点的指针域/赋以头结点的地址值pHead=pNode;/将头结点指针pHead/指向pNode结点return;/返回主程序,这种情况如下图（演示）,pHead,pNode,NULL,第三种情况：前两种情况，无论遇到哪一种，都会返回主程序。只要不返回就是这第三种情况，即pNode结点的num大于等于头指针所指向的结点的num值。这时肯定地说pNode结点要插入到头结点之后，究竟要插到哪里需要找到应该插入的位置。我们设指针r和指针q，分别指向相邻的两个结点，r在前q在后。,当着满足r-numnumnum时，pNode就插在r与q之间。（演示）,pHead,pNode,NULL,一开始让r=pHead，让q=pHead-next(1)当指针q为空指针时，说明原链表中只有一个结点，即r指向的结点，这时只要将pNode结点接在r之后即可。执行,r-next=pNode;pNode-next=q;,(2)如果q!=NULL，说明起码有两个结点在链表中，接着要判pNode结点的num值是否大于q结点的num值。如果是大，则说明pNode应插在q之后而不是之前，这时让r和q指针同时后移一步，即,r=q;q=q-next;,执行(2)在q!=NULL的情况下，如果pNode-numnum说明这时找到了正确的插入位置，退出while循环，将pNode结点插入到r后，q前即可。使用的语句为,在下面我们画出该算法的结构框图,r-next=pNode;pNode-next=q;,作业1、按下表顺序输入某班的一个学习小组的成员表,希望你将学习小组形成一个链表，每人一个结点。结点中有四个成员：姓名、出生年、出生月。指针。在链表中生日大者在前，小者在后。建成链表后输出该链表。,2、一年后钱亮同学调至其它学习小组，希望你编程从原链表中删除钱亮所在结点，之后输出该链表。提示：原链表如下：,head,查找待删除的结点的位置，要从链头找起。(1)如果是链头结点，即有head-name=待删者name这时只要做head=head-next;即可(2)如果不是链头结点，要设两个指针r和q，初始时让r=head;q=head-next;,(3)只要q!=NULL，就比较q-name是否为待删者的name？如果是则让r-next=q-next;如不是，就让r与q同时后移一步，即r=q;q=q-next;然后转向(3)(4)如果发现q已是NULL，又未找到待删结点，则输出该人不在这个表中的信息。在原链表中一旦查到钱亮所在结点位置q，让r-next=q-next;意味着将孙参所在结点指向钱亮的指针，不再指向钱亮，而指向武陆,11.3.2链表结点的删除,voiddel(numST*,/第三种情况，链表非空且删除的不是表头结点，/需要从表头起查找要删除结点q=p-next;while(q!=NULL)if(q-num=num)/q结点就是要删除的结点p-next=q-next;/将q结点从链表中去掉deleteq;/删除结点并释放空间return;if(q-numnum)/不存在要删除的结点return;p=q;q=q-next;/while/del,作业1、按下表顺序输入某班的一个学习小组的成员表,希望你将学习小组形成一个链表，每人一个结点。结点中有四个成员：姓名、出生年、出生月。指针。在链表中生日大者在前，小者在后。建成链表后输出该链表。,2、一年后钱亮同学调至其它学习小组，希望你编程从原链表中删除钱亮所在结点，之后输出该链表。提示：原链表如下：,head,查找待删除的结点的位置，要从链头找起。(1)如果是链头结点，即有head-name=待删者name这时只要做head=head-next;即可(2)如果不是链头结点，要设两个指针r和q，初始时让r=head;q=head-next;,(3)只要q!=NULL，就比较q-name是否为待删者的name？如果是则让r-next=q-next;如不是，就让r与q同时后移一步，即r=q;q=q-next;然后转向(3)(4)如果发现q已是NULL，又未找到待删结点，则输出该人不在这个表中的信息。在原链表中一旦查到钱亮所在结点位置q，让r-next=q-next;意味着将孙参所在结点指向钱亮的指针，不再指向钱亮，而指向武陆,11.4循环链表,任务11.2猴子选大王。n只猴子围成一圈，顺时针方向从1到n编号。之后从1号开始沿顺时针方向让猴子从1，2，m依次报数，凡报到m的猴子，都让其出圈，取消候选资格。然后不停地按顺时针方向逐一让报出m者出圈，最后剩下一个就是猴王。,起始位置,猴王,1,2,3,4,5,6,7,8,3,6,1,5,2,8,4,猴子被淘汰的顺序,演示：n=8,m=3,说明：如图1所示有8只猴子围成一圈，m=3。从1#猴的位置开始，顺时针1至3报数，第一个出圈的是3#；第二个出圈的是6#，第3个出圈的是1#；第4个出圈的是5#；第5个是2#，第6个是8#；第7个是4#。最后剩下一个是7#，它就是猴王。我们用循环链表来模拟这个选择过程。,1、定义一个名为mon的结构structmonintnum;/整数，表示猴子的编号mon*next;/指针，指向相邻的下一只猴子;2、将链表的头指针head定义为全局变量。mon*head;3、主函数用键盘输入猴子数n，输入数m，调用函数create建立一个循环链表，模拟众猴围成一圈的情况。该函数的实参为n。调用函数select，模拟1至m报数，让n-1只猴子逐一出列的过程。即在具有n个结点的循环链表按报数m删除结点的过程。该函数的实参为m，最后输出猴王的编号。,4、建立循环链表的函数create(intnn)其中nn为形式参数。要从编号1到编号nn。思路是（1）先做第1个结点，让其中的数据域p-num赋值为1，让指针域赋值为NULL。之后让链头指针head指向第1个结点。利用指针q记住这个结点，以便让指针p去生成下面的结点。（2）利用一个计数循环结构，做出第2个结点到第nn个结点。并将相邻结点一个接一个链接到一起。（3）最后一个结点要和头结点用下一语句链接到一起tail=q;tail-next=head;,head,tail,q,5、删结点的函数select(intmm)mm为形式参数，从1至mm报数，凡报到mm者删除其所在的结点。设计两个指针p和q。一开始让q指向链表的尾部q=tail。让p指向q的下一个结点。开始时让p指向1#猴所在的结点。用一个累加器x，初始时x=0，从1#猴所在结点开始让x=x+1=1，如果mm是1的话，1#猴所在的p结点就要被删除。有四条语句：,coutnumnext=p-next;deletep;p=NULL;,head,tail,q,p,演示,空指针,这里deletep是释放p结点所占用的内存空间的语句。如果mm不是1而是3，程序会在do-while循环中，让x加两次1，q和p一起移动两次，p指向3#所在结点，q指向2#所在结点，之后仍然用上述四条语句删去3#所在的结点。,head,q,演示,这个do-while循环的退出条件是q=q-next。即当只剩下一个结点时才退出循环。当然猴王非其莫属了。这时，让头指针head指向q，head是全局变量，在主程序最后输出猴王时要用head-num。,参考程序如下：,head,q,/*/*程序名：7_22.cpp*/*作者：wuwh*/*编制时间：2002年12月11日*/*主要功能：猴子选大王*/*#include/预编译命令structmonkey/结构声明intnum;/整型数,用于记录猴子号monkey*next;/monkey结构指针;monkey*head,*tail;/monkey结构指针，全局变量,voidcreate(intnn)/被调用函数/函数体开始inti;/整型变量i，用于计数monkey*p,*q;/声明monkey结构指针/为p分配内存空间p=newmonkey;p-num=1;/初始化p结点num域为1p-next=NULL;/初始化p结点next域为空head=p;/链表头指针head赋值为pq=p;/q赋值为p,for(i=2;inum=i;/初始化p结点num域为i，表示猴子号q-next=p;/将p结点加到链表尾部q=p;/让q指向链表尾部结点p-next=NULL;/链表尾部指向空/循环体结束tail=q;/链表尾tail-next=head;/链表尾部指向链表头/函数体结束,/被调用函数select，mm表示结点删除间隔voidselect(intmm)/函数体开始intx=0;/声明整型值x，并初始化为0monkey*p,*q;/声明结构指针p，qq=tail;/q赋值为tail，指向循环链表尾部do/直到型循环，用于循环删除指定间隔的结点/循环体开始p=q-next;/p赋值为q相邻的下一个结点x=x+1;/x加1if(x%mm=0)/x是否整除mm，/表