第11章_程序设计基础

第十一章链表内容要点链表的概念链表的建立过程链表结点的插入与删除循环链表–动态数据结构，可表示顺序访问的线性数据集–结点（node）：物理上不相邻，逻辑上的相邻关系由指针维持。–表头（head）、表尾（tail）–单链表、双链表、循环链表11.1链表的概念data1data2datanNULL……headtail单链表：data1datanNULL……headtail空的头结点：不存放数据，只用作表头。双链表：datan-1data1NULLdata2……NULLdatanheadtaildata1data2datan……head循环链表：【任务11.1】生成一份有序的节目预告单，节目列表有如下三项：1、节目名称（ActName）新闻联播幸运52足球之夜佳片有约实话实说……2、节目主持人（director）3、播放时间长度（Mtime）可以将每个节目单独放在一个结构里，用一个指针把两个结构连在一起，一天的节目形成一条链表。用头指针head指向链表的第一个结点：节目2节目nNULLhead头指针节目1#includeiostreamusingnamespacestd;structActList{//数据域charActName[20];//节目名为字符数组chardirector[20];//主持人为字符数组intMtime;//节目长度以分钟计//指针域ActList*next;//指向ActList结构的指针};ActList*head;//链表的头指针11.2链表的建立过程ActList*Create()//建立节目链表{ActList*p=NULL;//指向待插入的结点ActList*q=NULL;//用于在其后插入结点head=NULL;//一开始链表为空intTime;//节目时长,为0则退出cout输入节目时长:;cinTime;while(Time!=0){p=newActList;//分配内存空间给p结点p-Mtime=Time;cout输入节目名称:;cinp-ActName;cout输入主持人:;cinp-director;if(head==NULL)head=p;elseq-next=p;q=p;cout\n输入节目时长:;cinTime;}if(head!=NULL)q-next=NULL;returnhead;}voiddisplayList(ActList*head)//显示节目列表{cout“\n显示节目列表\n\n;while(head!=NULL)//指针head不空则输出{couthead-Mtimeendlhead-ActNameendlhead-directorendlendl;head=head-next;}}intmain(){displayList(Create());return0;}charActName[20];数据域chardirector[20];intMTime;ActList*next;指针域结点程序说明：(1)程序开头为结构定义，在这里称这样的结构为一个结点。这个结点包含两个域——数据域和指针域：数据域装有节目的信息，指针域装的是下一个结点的地址。(2)定义指向结构的头指针head：ActList*head;head=NULL;//初值为NULL(3)定义Create函数，返回指向ActList结构的指针：ActList*Create()①定义ActList*p=NULL;//指向待插入的结点ActList*q=NULL;//用于在其后插入结点②提示“输入节目时长”，Time为0则退出。③while(Time!=0)循环完成建立链表的工作。p=newActList;给p结点分配内存空间④if(head!=NULL)q-next=NULL;//标明链尾return(head);//返回链表的头指针head(4)定义displayList函数显示节目列表。head=head-next;使头指针不断后移，将整个链表从头至尾输出。(5)主程序调用displayList(Create());相当于displayList(head)①只要Time不为0，就将结点加到链表里。链表的建立过程归纳如下：p=newActList;ppheadqpheadq头结点建好qphead第二个结点建好headqp……headqp…NULL尾结点建好构造单链表的方法反向生成：将每个新结点插入到表头head=newActList;headnext=NULL;for(…;…;…){p=newActList;inputData(p);//输入数据到新结点pnext=headnext;headnext=p;}正向生成：将每个新结点链接到表尾while(…){p=newActList;if(head==NULL)head=p;elseq-next=p;q=p;}datandata1NULL……head11.3链表结点的插入•顺序存储结构中元素的插入–根据插入位置的不同，需要移动部分数据–平均需要移动一半长度的数据•链式存储结构中元素的插入–不需要移动元素，只需要修改链表指针•元素插入位置–表头、表尾、表中插入原则：不应破坏原链接关系（不能把链表弄“断”了）插入的结点应在适当位置链表表头插入datanextheaddatanextdatanextdatanext1.pnext=headp2.head=ppnext=head;head=p;nextheaddatanextdatanextdatanext1.pnext=headnextp2.headnext=ppnext=headnext;headnext=p;链表表尾插入q=head;while(qnext!=NULL)q=qnext;qnext=p;nextheaddatanext2.qnext=pp1.qdatanextdatanext链表表中插入nextheaddatanextxnextdatanext2.pnext=qnextp3.qnext=p1.qq=head;while(qnextdata!=x)q=qnext;pnext=qnext;qnext=p;将结点p插在值为x的结点之前5head61015null128例：已有一个按结点中整数域从小到大排序的链表，现在要插入一个结点，该结点中的整数为10。#includeiostreamusingnamespacestd;structnumST{intnum;//整型数numST*next;//numST结构指针};voidinsert(numST*&pHead,numST*pNode){structnumST*q,*r;if(pHead==NULL)//第一种情况，链表为空{pHead=pNode;return;}if(pNode-num=pHead-num)//第二种情况{pNode-next=pHead;pHead=pNode;return;}//第三种情况，循环查找正确位置r=pHead;//r赋值为链表头q=pHead-next;//q赋值为链表的下一个结点while(q!=NULL){if(pNode-numq-num){r=q;q=q-next;}elsebreak;}r-next=pNode;pNode-next=q;}voidprint(numST*pHead){intk=0;numST*r=pHead;while(r!=NULL){cout.width(2);k=k+1;coutk:r-numendl;r=r-next;}}intmain(){numST*pMHead=NULL;numST*pMNode=NULL;pMHead=newnumST;pMHead-next=newnumST;pMHead-next-next=newnumST;pMHead-num=5;pMHead-next-num=10;pMHead-next-next-num=15;pMHead-next-next-next=NULL;//链表尾赋值为空//构造一个结点pMNode，用于插入链表pMNode=newnumST;pMNode-num=12;pMNode-next=NULL;insert(pMHead,pMNode);print(pMHead);//与new对应，用delete释放空间……return0;}程序说明：(1)主程序建立了一条链表：(2)构造一个结点pMNode，数据域放12。(3)调用insert函数插入pMNode结点：insert(pMHead,pMNode);(4)调用print函数，从pMHead开始输出整个链表内容。5pMHead1015NULL传值和传引用的区别：传值：主程序中的调用语句为：insert(pMHead,pMNode);被调用函数为：voidinsert(numST*pHead,numST*pNode);pMHeadpMNode实际参数形式参数pNodepHead当实参pMHead赋给形参pHead后，pHead就指向了已存在的链表：51015NULLpHeadpMHead5pMHead1015NULLpHead4这时原来主函数中的pMHead就不起作用了，而是子函数中的pHead起作用。假设插入结点pNode的数据域为4，应将pNode插到pHead之前：用传值，新插入的结点并没有被包含进去。传引用：主程序中的调用语句为：insert(pMHead,pMNode);被调用函数为：voidinsert(numST*&pHead,numST*pNode);numST*&pHead声明pHead为numST结构指针的引用。主程序中的实参为头指针pMHead的引用，传给被调用函数的pHead，子函数中对pHead的操作就等价于对pMHead的操作。insert函数：pHead是pMHead的引用，指向链表头；pNode指向待插入结点。第一种情况：pHead==NULL链表为空，待插入的pNode结点就是链表中的第一个结点：pHead=pNode;第二种情况：pNode-num=pHead-num这时要将pNode结点插到头结点的前面：pNode-next=pHead;pHead=pNode;5pHead10415NULLpNodeNULL第三种情况：pNode-numpHead-numpNode结点要插到头结点之后，需要找到插入位置。设指针r和q分别指向相邻的两个结点，r在前q在后。当满足r-numpNode-num=q-num时，pNode就插在r与q之间。5pHead1012pNode15NULLNULLqrpHead==NULLTFTFpNode-num=pHead-num第2种情况：pNode结点中的数据小于头结点中的数据。将pNode结点插入到表头前，然后返回主函数。即pNode-next=pHead;pHead=pNode;return;第3种情况：pNode结点中的数据大于等于头结点中的数据。定义两个指针r和q，让r指向表头，让q指向相邻的下一个结点，即r=pHead;q=pHead-next;进入循环查找该插入的位置。第1种情况：链表为空。让链表头pHead指向pNode结点，之后返回主函数。即pHead=pNode;return;TFpNode-numq-numwhile(q!=NULL)当q指向不空pNode结点中的数据大于q结点中的数据。让r与q同时后移一步r=q;q=q-next;pNode结点中的数据小于等于q结点中的数据。找到了正确的插入位置，退出循环。找到了pNode结点正确的插入位置。包括两种情况（1）q