链表-c++。ppt

程序设计基础第11章链表程序设计基础第11章链表教学目标链表的概念建立链表中指针的运用插入删除结点的思路与双指针作用建立循环链表的思路程序设计基础第11章链表链表属于动态数据结构，可以类比成一“环”接一“环”的链条，这里每一“环”视作一个结点，结点串在起形成链表。程序设计基础第11章链表11.1举例说明链表的概念程序设计基础第11章链表【任务11.1】某电视台希望王小二同学为他们编一个程序。该程序可以将节目串在一起，形成一份有序的节目预告。节目列表有如下三项1、节目名称包括新闻联播（CCTVNews）祖国各地（Motherland）体育之窗（Sports）学校见闻（College）电影展播（Movie）2、节目主持人（Director）3、播放时间长度（Time）程序设计基础第11章链表我们可以将每一个节目单独放在一个结构里，用一个指针把两个结构连在一起，一天的节目形成一条链表。用一个所谓的头指针head指向链表的第一个结点。如下图所示节目2节目nNULLhead头指针节目1下面的程序是建立链表的过程。程序设计基础第11章链表11.2建立链表的过程程序设计基础第11章链表//************************************//*程序名：11_1.cpp*//*作者：wuwh*//*编制时间：2002年11月26日*//*主要功能：链表*//************************************#includeiostreamusingnamespacestd;structActList//定义一个名为ActList结构{charActName[20];//节目名为字符数组chardirector[20];//主持人为字符数组intMtime;//节目长度为分钟ActList*next;//指向ActList结构的指针};程序设计基础第11章链表ActList*head;//链头指针ActList*Create()//定义一个指向AcitList结构{//的指针函数，名为CreateActList*p=NULL;//指针，指向个待插入的结点ActList*q=NULL;//指针，用于在其后插入结点head=NULL;//一开始链表为空intTime;//节目时长，如为0则退出程序设计基础第11章链表//以下是给新结点输入节目信息cout输入节目时长：;cinTime;while(Time!=0)//当该节目的时长不为0时，将其{//纳入链表中p=newActList;//分配内存空间给p结点p-Mtime=Time;//让Time赋给p结点的结构成员Mtimecout输入节目名称：;//提示信息cinp-ActName;//输入节目名称cout输入主持人：;//提示信息cinp-director;//输入主持人程序设计基础第11章链表if(head==NULL)//head为空，要插入第一个head=p;//结点，让头指针指向结点pelse//否则不是头结点，应将p结点q-next=p;//插入到q结点的后面q=p;//q指向当前最后一个结点cout\n输入节目时长：;cinTime;//输入下一个节目时长}//一旦跳出while循环，说明有一个节目时长为0if(head!=NULL)q-next=NULL;//让q所指的最后一个结点的指针域为空说明这已是链尾了return(head);//返回头指针}程序设计基础第11章链表voiddisplayList(ActList*head){cout显示节目列表\n;while(head!=NULL)//当指针head不空，则输出{couthead-Mtimeendlhead-ActNameendlhead-directorendlendl;head=head-next;}}程序设计基础第11章链表intmain()//主函数开始{//调用子函数displaList()//调用时的实参为Create()函数的返回值displayList(Create());return0;}//主函数结束程序设计基础第11章链表说明1、先从主函数说起主函数只有一条语句displayList(Create());这是调用子函数displayList，该子函数的形参为ActList*head是一个指向ActList结构的名为head的指针变量。在主函数调用displayList时所用的实际参数来自运行Create()函数的返回值。从Create()的定义ActList*Create()看出Create()函数的返回值应该是一个指向ActList的指针。主函数在调用子函数时，又遇到该函数的实参又是调用另一个函数之后的返回值。看起来的确显得复杂，但是我们耐心分析之后，感到并不难。程序设计基础第11章链表2、程序开头为结构定义。在这里我们称这样的一个结构为一个结点。这个结点包含两个域：数据域和指针域intMTime;charActName[20];数据域chardirector[20]ActList*next;指针域结点数据域中装有节目的信息，而指针域装的是指向另一个结点的地址。显然这是为形成链表而专门设置的。程序设计基础第11章链表3、在定义Create函数之前，先定义了一个指向结构的头指针head，即ActList*head;4、定义Create函数，该函数可返回指向ActList结构的指针，即ActList*Create()分析这个函数的功能可分如下4块程序设计基础第11章链表①定义ActList*p=NULL;ActList*q=NULL;head=NULL;intTime;定义了两个指向结构ActList的指针p和q，并初始化为空，即未指向任何地址。同时让头指针head也为空。再定义一个临时变量Time，是一个整型数。程序设计基础第11章链表②提示“输入节目时长”，之后用键盘输入，用了下面两句：cout“输入节目时长”;cinTime;这部分程序语句是为下面的while循环做准备的。如果Time不为0，才做下面的内容。程序设计基础第11章链表③while(Time!=0)循环在当循环的循环体内完成建立链表的过程。首先给p结点分配内存空间。这个内存空间的大小要根据p结点的定义（p结点是ActList结构）来确定。接着下面就是几个赋值语句p-MTime=Time;cout“输入节目名称：”;//提示cinp-ActName;//用键盘输入节目名称cout“输入主持人：”;//提示cinp-director;//用键盘输入主持人程序设计基础第11章链表接着是一个分支语句if(head==NULL)head=p;这是说如果头指针为空，表示链表还是空的，这时p结点就是第一个结点。让head指向p结点。之后让q=p;这是让q指向刚进入链表的结点，让p再去指向待加入的结点。如果p结点已不是第一个结点了，head必不为NULL，因此要走else分支，即elseq-next=p;程序设计基础第11章链表将此时的p结点放到q所指向的结点后面。之后让q=p;即让q指向刚进入链表的结点，腾出p去指向下一个待加入的结点。接下来输入下一个节目时长，cout“\n输入节目时长：”;cinTime;至此，while语句的循环体结束。当Time值不为0，就会有结点加入链表，继续执行循环体。一旦Time为0，则会跳出while循环。程序设计基础第11章链表④执行两条语句if(head!=NULL)q-next=NULL;return(head);第一条是说，如果head不空说明链表已建成，这时q一定是最后一个结点，将该结点的指针域置成空，以表明它是链尾。程序设计基础第11章链表第二条return(head);将这条链表的头指针head返回。这件事意味着执行完Create函数后得到head指针所指向的地址，这个地址就是链表中的第一个结点的地址。这时对主函数而言displayList(Create())就是dispalyList(head)调用dsplayList(head)就会将整个链表从头至尾输出。程序设计基础第11章链表1、定义ActList结构，结构中包含数据域和指针域。将一个结构看作一个结点。2、定义一个指向结构的指针head，准备用来指向链表的第一个结点。3、定义一个指向ActList结构的指针函数，起名为Create函数，该函数返回的是创建好的链的头指针head。下面是Create函数所要做的事情：①定义指向ActList结构的两个指针p和q，定义后立即初始化为NULL，即不指向任何地址。再让头指针head为NULL，也是不指向任何地址，表示该链表尚未建立，一个结点也没有。然后定义一个中间变量“节目时长Time”，当Time为0时，建立链表的过程应该结束。建立链表的过程可归纳为如下三个步骤程序设计基础第11章链表①下面程序的构思是，只要Time不为0，就要构建链表。构建的思路是将一个一个的结点加至链表里来。首先给p找一个能够指向的内存空间，我们说这是给p结点分配一片内存空间。如下图建立链表的过程可归纳为如下三个步骤p程序设计基础第11章链表②然后，通过键盘往这个空间中装入与节目有关的信息。装完之后判断一下head为空否，如为空则p结点为第一个结点，让head指向p结点就完成了有一个结点的链表。之后让q赋值为p，即使让q指针去指向刚加入链表的结点，将p指针腾出来去做下一个结点的工作。headpq图链表的第一个结点建成程序设计基础第11章链表当Time不为0，p又被分配了内存空间，形成了第二个结点，装入节目信息后，判断head不再为空，说明前面已有结点在链表中，这时要将第二个结点放到q所指向的结点的后面。执行q-next=p之后就完成了。之后再将q指针移到第二个结点上，将p指针腾出来去做下一个结点的工作。headpq程序设计基础第11章链表指针移到第二个结点上，将p指针腾出来去做下一个结点的工作。headq第三个结点加入链表的过程为headqp程序设计基础第11章链表最末一个结点连至链表的尾部之后，要在q指针所指向的最后一个机诶但的指针域加上一个NULL，表示这里是链尾了，后面再也不连结点了。headqNULL程序设计基础第11章链表练习1、按下表顺序输入某班的一个学习小组的成员表：姓名赵达钱亮孙参李思周芜武陆郑琪出生年月19831983198319821983198319821329546将学习小组形成一个链表，每人一个结点。结点中有4个成员：姓名、出生年、出生月、指针。建成链表后输出该链表。程序设计基础第11章链表链表结点的插入程序设计基础第11章链表链表结点的插入原则：插入操作不应破坏原链接关系插入的结点应该在它该在的位置。应该有一个插入位置的查找子过程程序设计基础第11章链表5head61015null128先看下面一个简单的例子：已有一个如图所示的链表。它是按结点中的整数域从小到大排序的。现在要插入一个结点，该节点中的数为10。待插入结点此结点已插入链表程序设计基础第11章链表//************************************//*程序名：7_20.cpp*//*作者：wuwh*//*编制时间：2002年12月3日*//*主要功能：链表插入结点*//************************************#includeiostream.h//预编译命令structnumST//结构声明{intnum;//整型数numST*next;//numST结构指针};参考程序程序设计基础第11章链表//被调用函数insert()，两个形参分别表示链表和待插入的结点voidinsert(numST*&pHead,numST*pNode){//函数体开始structnumST*q,*r;//定义结