吴文虎程序设计基础第2版PPT第13

1、12链表插入结点链表插入结点原则：原则：1、插入操作不应破坏原链接关系、插入操作不应破坏原链接关系2、插入的结点应该在它该在的位置。应该、插入的结点应该在它该在的位置。应该有一个插入位置的查找子过程。有一个插入位置的查找子过程。3head先看下面一个简单的例子：先看下面一个简单的例子：已有一个如图所示的链表。已有一个如图所示的链表。它是按结点中的整数域从小到大排序的。现在要插它是按结点中的整数域从小到大排序的。现在要插入一个结点，该节点中的数为入一个结点，该节点中的数为10。待插入结点待插入结点此结点已插入链表此结点已插入链表4/ 11-2.cpp#include / 预编译命令预编译命令us

2、ing namespace std;struct numST/ 结构声明结构声明int num;/ 整型数整型数struct numST *next;/ 指指向向numST结构结构的指针的指针; / numST 是有一个数据域是有一个数据域 num 和一个指针域和一个指针域 next 的结构的结构参考程序参考程序5/ 被调用函数被调用函数insert()，两个形参分别表示链表和待插入的结点，两个形参分别表示链表和待插入的结点void insert (numST *&pHead, numST *pNode) / pHead 声明为引用声明为引用/ 函数体开始函数体开始struct num

3、ST *q,*r;/ 定义结构指针定义结构指针q,rif ( pHead = NULL )/ 第一种情况第一种情况，链表为空，链表为空pHead = pNode;/ 链表头指向链表头指向pNodereturn;/ 完成插入操作，返回完成插入操作，返回/ 链表不为空链表不为空6789/ 第三种第三种情况情况，循环查找正确位置，循环查找正确位置r = pHead;/ r赋值为链表头赋值为链表头q = pHead-next;/ q赋值为链表赋值为链表头的下一个结点头的下一个结点while (q!=NULL) / 利用循环查找正确位置利用循环查找正确位置/ 判断判断pNode结点的结点的num 是否是

4、否大于结点的大于结点的num if ( pNode-num q-num ) / 大于了大于了 r = q; / r 指向指向q所指的结点所指的结点q = q-next; / q指向链表中相邻的下一个结点指向链表中相邻的下一个结点 else / 小于小于等于了，等于了，找到了正确的位置找到了正确的位置 break; / 退出循环退出循环 r-next = pNode; / 将将pNode结点插入正确的位置结点插入正确的位置pNode-next = q;1011/ 被调用函数，形参为被调用函数，形参为ST结构指针结构指针，用于输出链表内容用于输出链表内容void print(struct numS

5、T *pHead) int k=0; / 整型变量，用于计数整型变量，用于计数struct numST * r=pHead;/ 声明声明r为为numST结构指针结构指针 / r 指向指向链表头链表头while(r !=NULL)/ 当型循环，链表指针不为空当型循环，链表指针不为空则则继续继续/ 循环体开始循环体开始k=k+1;/ 计数加计数加1coutk“:”numnext;/ 取链表中相邻的下一个结点取链表中相邻的下一个结点/ 循环体结束循环体结束12void main()/ 主函数开始主函数开始/ 函数体开始函数体开始numST *pMHead=NULL; / ST型结构指针型结构指针nu

6、mST *pMNode =NULL; / 初始化初始化pMHead为为NULL / 分配分配3个个ST结构的内存空间，用于构造链表结构的内存空间，用于构造链表pMHead = new numST;head-next = new numST;head-next-next = new numST; / 为链表中的为链表中的3个结点中的个结点中的num赋值为赋值为5、10和和15pMHead-num = 5;pMHead-next-num = 10;pMHead-next-next-num = 15;pMHead-next-next-next = NULL; / 链表尾赋值为空链表尾赋值为空 / 构

7、造一个结点构造一个结点pMNode，用于插入链表，用于插入链表pMNode = nuw numST;pMNode-num = 12;pMNode-next =NULL;insert(pMHead, pMNode);/ 将结点将结点pMNode插入链表插入链表print(pMHead); / 调用调用print函数，输出链表内容函数，输出链表内容/ 主函数结束主函数结束1314下面用赋值语句往这下面用赋值语句往这3个空间中放个空间中放num数据。最后的数据。最后的一个结点为队尾，在其指针域存放一个结点为队尾，在其指针域存放NULL。（4）pMhead-num=5;（5）pMhead-next-n

8、um=10;（6）pMhead-next-next-num=15;（7）pMhead-next-next-next=NULL;做了这做了这4条之后形成了一条链表如下：条之后形成了一条链表如下：pMhead该链表的头结点由该链表的头结点由PMhead所指向。所指向。153、构造一个结点、构造一个结点pMNode，在该结点的数据域放，在该结点的数据域放12，再插入链表再插入链表（1）pMNode=new numST; pMNode 12（2）pMNode-num=12; （3）pMNode-next=NULL; NULL4、调用、调用insert函数来插入函数来插入pMNode结点。结点。语句为语

9、句为 insert( pMHead, pMNode );意思是以将意思是以将pMNode插入到以插入到以pMHead为队头的链表为队头的链表中。这里在调用时，是用中。这里在调用时，是用pMHead作为实参，属于作为实参，属于传传值调用值调用。16这里要讲传址调用和传值调用的区别这里要讲传址调用和传值调用的区别（1）如果是传值调用）如果是传值调用主程序中的调用语句为主程序中的调用语句为 insert(pMHead, pMNode);被调用函数为被调用函数为void insert( munST *pHead, numST*pNode);pMHeadpMNode实际参数实际参数形式参数形式参数pNo

10、depHead17当着实际参数当着实际参数pMHead赋给了形式参数赋给了形式参数pHead之后，之后，pHead就指向了已经存在了的链表，见下图。就指向了已经存在了的链表，见下图。pHead这时原来的主程序中的头指针就不再起作用了。而是这时原来的主程序中的头指针就不再起作用了。而是pHead起作用。假如现在起作用。假如现在pNode中的数据为中的数据为4小于小于5，应该将应该将pNode插入到插入到pHead所指向的结点前，如下图所指向的结点前，如下图pMHead18pMHeadpHead被调用函数无法改变被调用函数无法改变pMHead，这时，这时pMHead不再是头不再是头结点的指针了。如

11、果被调用函数返回结点的指针了。如果被调用函数返回pHead，主函数，主函数只能表示只能表示pMHead为头指针的三个结点，新插入的结为头指针的三个结点，新插入的结点并没有包含进去。要想将新的插入到最前面的结点并没有包含进去。要想将新的插入到最前面的结点包含进去，就必须用传址调用。点包含进去，就必须用传址调用。19（2）如果是传引用调用）如果是传引用调用主程序中的调用语句为主程序中的调用语句为 insert(pMHead,pMNode);被调用函数为被调用函数为void insert( munST *&pHead, numST*pNode); 与传值调用函数比较与传值调用函数比较 voi

12、d insert( munST *pHead, numST*pNode);2021在主函数中在主函数中pMHead为头指针，在被调用的子函数为头指针，在被调用的子函数中中pHead为头指针的别名，两者指向同一个单元，只为头指针的别名，两者指向同一个单元，只不过分别叫不同的名罢了。当然在子函数中无论插入不过分别叫不同的名罢了。当然在子函数中无论插入什么结点都会让什么结点都会让pHead指向链表的头。自然返回到主指向链表的头。自然返回到主函数后函数后pMHead也会是指向同一链表的头。也会是指向同一链表的头。从这个例子中读者可以领会到传值调用与传引用调从这个例子中读者可以领会到传值调用与传引用调用

13、的区别。用的区别。5、这样在子函数做插入结点的过程中，头指针的改变也、这样在子函数做插入结点的过程中，头指针的改变也能反映到主函数中来。调用能反映到主函数中来。调用print函数，从函数，从pMHead开开始输出整个链表的内容。始输出整个链表的内容。22下面我们来研究下面我们来研究insert函数函数前提是主程序已将两个实参传给了前提是主程序已将两个实参传给了insert函数的两个形参，函数的两个形参，这时这时pHead是是pMHead的引用，的引用，pNode所指向的就是待所指向的就是待插入的一个结点。事先定义两个结构指针插入的一个结点。事先定义两个结构指针q和和r。第一种情况：第一种情况：

14、pHead=NULL，说明主程序传过来的头指针为空，说明主程序传过来的头指针为空，即链表为空，一个结点都不存在。这时待插入的即链表为空，一个结点都不存在。这时待插入的pNode结点就是链表中的第一个结点。执行如下两条结点就是链表中的第一个结点。执行如下两条语句语句pHead=pNode; / 将表头指针指向将表头指针指向pNode结点结点 return; / 返回主程序返回主程序在主程序中必然头指针在主程序中必然头指针pMHead指向指向pNode结点。结点。23第二种情况：第二种情况：pNode结点的结点的num值小于链表头结点的值小于链表头结点的num值，即值，即 pHead-numpNo

15、de-num。这时要将。这时要将pNode结点插结点插入到头结点的前面，要执行如下三条语句入到头结点的前面，要执行如下三条语句pNode-next=pHead; / 在在p结点的指针域赋以链头的地址值结点的指针域赋以链头的地址值pHead=pNode; / 将头结点指针将头结点指针pHead指向指向pNode结点结点return; / 返回主程序返回主程序这种情况如下图这种情况如下图pHeadpHeadpNodenull24第三种情况：第三种情况：前两种情况，无论遇到哪一种，都会返回主程序。只要不返回就前两种情况，无论遇到哪一种，都会返回主程序。只要不返回就是这第三种情况，即是这第三种情况，即

16、pNode结点的结点的num大于头指针所指向的结点大于头指针所指向的结点的的num值。这时肯定地说值。这时肯定地说pNode结点要插入到头结点之后，究竟结点要插入到头结点之后，究竟要插到哪里需要找到应该插入的位置。我们设指针要插到哪里需要找到应该插入的位置。我们设指针r和指针和指针q，分，分别指向相邻的两个结点，别指向相邻的两个结点，r在前在前q在后，当着满足在后，当着满足r-num num num时，时，p就插在就插在r与与q之间。我们看图之间。我们看图headpqrnullqr25一开始让一开始让 r=pHead，让，让 q=pHead-next(1) 当指针当指针q为空指针时，说明原链表

17、中只有一个结点，为空指针时，说明原链表中只有一个结点，即即r指向的结点，这时只要将指向的结点，这时只要将p结点接在结点接在r之后即可。之后即可。执行执行r-next=pNode;pNode-next=q;(2) 如果如果q!=NULL，说明起码有两个结点在链表中，接，说明起码有两个结点在链表中，接着要判着要判pNode结点的结点的num值是否大于值是否大于q结点的结点的num值。值。如果是大，则说明如果是大，则说明pNode应插在应插在q之后而不是之前，之后而不是之前，这时让这时让 r 和和 q 指针同时后移一步，即指针同时后移一步，即r=q;q=q-next;26执行执行(2)在在q !=

18、NULL的情况下，如果的情况下，如果pNode-numnum了，了，说明这时找到了正确的插入位置，退出说明这时找到了正确的插入位置，退出while循环，循环，将将pNode结点插入到结点插入到 r 后，后，q 前即可。使用的语句为前即可。使用的语句为在下面我们画出该算法的结构框图在下面我们画出该算法的结构框图r-next=pNode;pNode-next=q;27 (*phead)=null T F T F (*phead)-nump-num 第第 2 种情况：种情况： p 结点中的数据小于头结点中的数据。 将结点中的数据小于头结点中的数据。 将 p结点插入到表头前，然后返回主函数。即结点插入

19、到表头前，然后返回主函数。即 p-next=*phead; *phead=p; return; 第第 3 种情况：种情况： p 结点中的数据大于等于头结点中的数据。定义两个指针结点中的数据大于等于头结点中的数据。定义两个指针r 和和 q，让，让 r 指向表头，让指向表头，让 q 指向相邻的下一个结点，即指向相邻的下一个结点，即 r=*phead; q= (*phead)-next; 进入循环进入循环查找查找该该插入的位置。插入的位置。 第第 1 种情种情况： 链表为况： 链表为空。 让链表空。 让链表 头头 *phead指向指向 p 结结点， 之后返点， 之后返回主函数。回主函数。即即 *ph

20、ead=p; return; T F q-numnum while(q!=null) 当当 q 指向不空指向不空 p 结点中的数据大于结点中的数据大于 q 结点中结点中的数据。让的数据。让 r 与与 q 同时后移一同时后移一步步 r=q; q=q-next; p 结点中的数据小结点中的数据小于等于于等于 q 结点中结点中的数据。 找到了正的数据。 找到了正确的插入位置， 退确的插入位置， 退出循环。出循环。 找到了找到了 p 结点正确的插入位置。包括两种情况（结点正确的插入位置。包括两种情况（1）q 指指向空，向空， r 指向队尾结点； （指向队尾结点； （2） r-numnumnum。这两种

21、情况都需将这两种情况都需将 p 插入到插入到 r 后后 q 前，即前，即 r-next=p; p-next=q; 28作业作业1、按下表顺序输入某班的一个学习小组的成员表、按下表顺序输入某班的一个学习小组的成员表希望你将学习小组形成一个链表，每人一个结点。结希望你将学习小组形成一个链表，每人一个结点。结点中有四个成员：姓名、出生年、出生月。指针。点中有四个成员：姓名、出生年、出生月。指针。在链表中生日大者在前，小者在后。在链表中生日大者在前，小者在后。建成链表后输出该链表。建成链表后输出该链表。292、一年后钱亮同学调至其它学习小组，希望你编程从、一年后钱亮同学调至其它学习小组，希望你编程从原

22、链表中删除钱亮所在结点，之后输出该链表。原链表中删除钱亮所在结点，之后输出该链表。提示：原链表如下：提示：原链表如下：head查找待删除的结点的位置，要从链头找起。查找待删除的结点的位置，要从链头找起。(1)如果是链头结点，即有如果是链头结点，即有head-name=待删者待删者name这时只要做这时只要做head=head-next;即可即可(2)如果不是链头结点，要设两个指针如果不是链头结点，要设两个指针r和和q，初始时让，初始时让r=head; q=head-next;30(3)只要只要q!=null，就比较，就比较q-name是否为待删者的是否为待删者的name？如果是则让？如果是则让

23、 r-next=q-next; 如不是，就如不是，就让让r与与q同时后移一步，即同时后移一步，即 r=q; q=q-next; 然后转然后转向向(3)(4)如果发现如果发现q已是已是null，又未找到待删结点，则输出，又未找到待删结点，则输出该人不在这个表中的信息。该人不在这个表中的信息。在原链表中一旦查到钱亮所在结点位置在原链表中一旦查到钱亮所在结点位置q，让，让r-next = q-next;意味着将孙参所在结点指向钱亮的指针，不再指意味着将孙参所在结点指向钱亮的指针，不再指向钱亮，而指向武陆向钱亮，而指向武陆31二二 叉叉 树树32链表结构是利用结构中的指针域将每个结点链接起来，链表结构

24、是利用结构中的指针域将每个结点链接起来，形似链条，属于线性结构数据。形似链条，属于线性结构数据。下面介绍一种非线性结构的东西，下面介绍一种非线性结构的东西，二叉树二叉树。先看下例：先看下例：结点结点1结点结点2结点结点4结点结点6结点结点7结点结点5结点结点3root33在图中在图中 （1）外形象一棵倒立的树）外形象一棵倒立的树 （2）最上层有一个）最上层有一个“根结点根结点”，指针，指针root指向根结点。指向根结点。 （3）每个结点都是一个结构，一个成员是整型数据，两）每个结点都是一个结构，一个成员是整型数据，两个成员是指针，分为左指针个成员是指针，分为左指针L和右指针和右指针R。 （4）

25、根结点的左指针指向左子树；右指针指向右子树。）根结点的左指针指向左子树；右指针指向右子树。 （5）左子树或右子树本身又是一棵二叉树，又有它们自）左子树或右子树本身又是一棵二叉树，又有它们自己的左子树和右子树，己的左子树和右子树，这是递归定义的，因此，在处理时常可用递归算法。这是递归定义的，因此，在处理时常可用递归算法。34二叉树的遍历二叉树的遍历树的遍历是指访遍树中的所有结点。树的遍历是指访遍树中的所有结点。对比看遍历一个单链表，从表头开始按一个对比看遍历一个单链表，从表头开始按一个方向从头到尾就可遍历所有结点。对二叉树方向从头到尾就可遍历所有结点。对二叉树来说就没有这样简单了，因为对树或是对

26、子来说就没有这样简单了，因为对树或是对子树都存在根（或子树的根）和左子树、右子树都存在根（或子树的根）和左子树、右子树，先遍历谁？由之产生了三种不同的方法：树，先遍历谁？由之产生了三种不同的方法：351、前序法：、前序法：1.1 先访问根结点；先访问根结点；1.2 遍历左子树；遍历左子树；1.3 遍历右子树；遍历右子树；2、中序法：、中序法：2.1 遍历左子树；遍历左子树；2.2 访问根；访问根；2.3 遍历右子树；遍历右子树；3、后序法、后序法3.1 遍历左子树；遍历左子树；3.2 遍历右子树；遍历右子树；3.3 访问根；访问根；36我们就以中序法为例研究如何遍历二叉树。仍然采用我们就以中序

27、法为例研究如何遍历二叉树。仍然采用递归算法。令指针递归算法。令指针p指向二叉树的根结点指向二叉树的根结点定义树的结构定义树的结构struct TREEint data;struct TREE *L, *R;定义定义p为为TREE结构的指针结构的指针struct TREE *p;让让LNR(P)为对以为对以p为根的树作中序遍历的子函数。可为根的树作中序遍历的子函数。可得出如下图所示的递归算法与或结点图得出如下图所示的递归算法与或结点图37A LNR(p)中序遍历p结中序遍历p结点为根的二叉树点为根的二叉树B什么都不做什么都不做Cp!=nullp=nullDLNR(p-L)中序遍历p的左子树中序遍

28、历p的左子树E访问p结点访问p结点FLNR(p-R)中序遍历p的右子树中序遍历p的右子树图2图238该图说明如下：该图说明如下：1、A结点表示中序遍历结点表示中序遍历p结点为根的二叉树，函数为结点为根的二叉树，函数为LNR(p)。该结点为。该结点为“或或”结点，有两个分支。当结点，有两个分支。当p为空时，为空时，A取取B结点，什么都不做；当结点，什么都不做；当p不空时，说不空时，说明树存在（起码有一个根），有结点明树存在（起码有一个根），有结点C。2、C结点为一个结点为一个“与与”结点，要依次做相关联的三件结点，要依次做相关联的三件事情：事情：2.1 D结点：中序遍历结点：中序遍历p的左子树，

29、函数为的左子树，函数为LNR(p-L);2.2 E结点：直接可解结点，访问结点：直接可解结点，访问p结点（比如输出结点（比如输出p结点数据域中的值）。结点数据域中的值）。2.3 F结点：中序遍历结点：中序遍历p的右子树，函数为的右子树，函数为LNR(p-R)393、比较、比较LNR(p)与与LNR(p-L)及及LNR(p-R)可以看出，可以看出，都是同一个函数形式，只不过代入了不同的参数，都是同一个函数形式，只不过代入了不同的参数，从层次和隶属关系看，从层次和隶属关系看，p是父结点的指针，而是父结点的指针，而p-L和和p-R是子结点的指针，是子结点的指针，p-L是左子树的根，是左子树的根，p-

30、R是是右子树的根。右子树的根。下面请大家做一个练习，依图下面请大家做一个练习，依图2画画“与或与或”图将图图将图1所所示的二叉树用中序遍历，将所访问到的结点数据输示的二叉树用中序遍历，将所访问到的结点数据输出。如图出。如图34041二叉树的建立二叉树的建立建立二叉树的过程是一个建立二叉树的过程是一个“插入插入”过程，下面我们用过程，下面我们用一个例子来讲解这一过程。一个例子来讲解这一过程。我们想建立这样一棵二叉树，树中的每一个结点有一我们想建立这样一棵二叉树，树中的每一个结点有一个整数数据名为个整数数据名为data，有两个指针：左指针，有两个指针：左指针L，右指，右指针针R，分别指向这个结点的

31、左子树和右子树，显然，分别指向这个结点的左子树和右子树，显然可以用如下名为可以用如下名为TREE的结构来描述这种结点：的结构来描述这种结点：struct TREEint data;struct TREE *L, *R;42对二叉树最重要的是根，它起定位的作用，因此，首先对二叉树最重要的是根，它起定位的作用，因此，首先建立的是根结点。也就是说，如果从键盘输入数据来建建立的是根结点。也就是说，如果从键盘输入数据来建立二叉树，第一个数据就是这棵树的根的数据，之后再立二叉树，第一个数据就是这棵树的根的数据，之后再输入的数据，每一个都要与根中的数据作比较，以便定输入的数据，每一个都要与根中的数据作比较，

32、以便定该数据所在接点的插入位置。假定我们这里依然用图该数据所在接点的插入位置。假定我们这里依然用图1的中序遍历的方式。即如果待插入结点的数据比根结点的中序遍历的方式。即如果待插入结点的数据比根结点的数据小，则将其插至左子树，否则插入右子树。的数据小，则将其插至左子树，否则插入右子树。定义一个递归函数定义一个递归函数void insert(struct TREE *&pRoot, struct TREE *pNode) 其中，指针其中，指针pNode指向含有待插入数据的结点。指向含有待插入数据的结点。pRoot为树的根结点指针的别名。为树的根结点指针的别名。insert函数可理解为将函数

33、可理解为将pNode结点插入到结点插入到 pRoot 所指向的树中。所指向的树中。43insert(pRoot, pNode)可用下列与或结点图来描述可用下列与或结点图来描述insert(proot,p)将结点p插入根结点将结点p插入根结点*proot=p; return;*proot=p; return;返回返回C根结点不空，根结点不空，树已存在树已存在根结点为空根结点为空*proot=nullp-datadatainsert(&(*proot)-R),p);将p结点插入右子树将p结点插入右子树图3图3p-data (*proot)-datainsert(&(*proot)-L),p);将p结点插入左子树将p结点插入左子树44注意在上图中注意在上图中pRoot是被调用函数的形参。从前面对它是被调用函数的形参。从前面对它的定义看，的定义看，pRoot是指针的引用，实际上是指向二叉是指针的引用，实际上是指向二叉树根结点的指针的别名。如下图。因此，在主程序调树根结点的指针的别名。如下图。因此，在主程序调用用insert函数时，函数时，根结点根结点实参实参(pRoot)实