12 链表插入结点.ppt

第1页：第十二讲链表插入结点封面

本页为第十二讲 链表插入结点章节封面，本讲讲解链表中插入结点、传值与传址调用的区别，以及二叉树的建立与遍历。

第2页：链表插入结点原则

链表插入结点原则：

1. 插入操作不应破坏原链接关系
2. 插入的结点应该在它该在的位置。应该有一个插入位置的查找子过程

第3页：插入结点的示例

先看下面一个简单的例子：已有一个如图所示的链表。它是按结点中的整数域从小到大排序的。现在要插入一个结点，该结点中的数为 10。

• 原链表：head → 5 → 6 → 10 → 15 → null
• 图中另标出待插入值 12 与 8 的示意位置，插入后结点被接到正确位置

说明：源文件该页以图形为主，数值呈粘连状态，上表文字依据前后页（链表值 5、6、10、15 与待插入值 12、8）整理，建议对照原图核对。

第4页：结构7.c的定义部分

//结构7.c #include <stdio.h>#include <malloc.h>#define null 0#define LEN sizeof(struct numST)struct numST{ int num; struct numST *next;};

参考程序。

第5页：insert函数的前两种情况

//被调用函数insert()，两个形参分别表示链表和待插入的结点 void insert (struct numST **phead, struct numST *p) { struct numST *q,*r; if ((*phead)==null) { *phead = p; return; } else { if ((*phead)->num>p->num ) { p->next = *phead; *phead = p; return; }

第6页：insert函数的第三种情况

 r = *phead; q = (*phead)->next; while (q!=null) { if (q->num < p->num) { r = q; q = q->next; } else break; } r->next = p; p->next = q; } }

第7页：结构7.c的print函数

//被调用函数，形参为ST结构指针，用于输出链表内容 void print(struct numST *head) { int k=0; struct numST * r; r=head; while(r != null) { k=k+1; printf("%d %d\n",k,r->num); r=r->next; }}

第8页：结构7.c的主函数

void main(){ struct numST *head, *p; head = null; head = (struct numST *) malloc(LEN); head->next = (struct numST *) malloc(LEN); head->next->next= (struct numST *) malloc(LEN); head->num = 5; head->next->num = 10; head->next->next->num = 15; head->next->next->next= null; p = (struct numST *) malloc(LEN); p->num =12; p->next = null; insert(&head, p); print(head);} 
第9页：主函数的内存分配
先看主函数：
定义两个 ST 型结构指针 *head、*p，并让 head=null
分配 3 个 ST 结构的内存空间，用于构造链表：
head=(struct numST*) malloc(LEN);
head->next=(struct numST*) malloc(LEN);
head->next->next=(struct numST*) malloc(LEN);
这 3 个 ST 结构的内存空间如上图所示，分别由 head、head->next、head->next->next 指向。
第10页：给链表结点赋值
下面用赋值语句往这 3 个空间中放 num 数据。最后的一个结点为队尾，在其指针域存放 null。
(4) head->num=5; (5) head->next->num=10; (6) head->next->next->num=15; (7) head->next->next->next=null;
做了这 4 条之后形成了一条链表如下：
head → 5 → 10 → 15 → null
该链表的头结点由 head 所指向。
第11页：构造待插入结点
3、构造一个结点 p，在 p 结点的数据域放 12，再插入链表：
(1) p=(struct numST*) malloc(LEN); (2) p->num=12; (3) p->next=null;
4、调用 insert 函数来插入 p 结点。语句为 insert(&head,p);，意思是将 p 插入到以 head 为队头的链表中。但这里在调用时，不是用 head 作为实参，而是用 &head 作为实参，属于传址调用，而非传值调用。
第12页：传值调用的形式
这里要讲传址调用和传值调用的区别。
（1）如果是传值调用，主程序中的调用语句为 insert(head,p);
void insert(struct munST *phead, struct numST*p);
实际参数为 head 与 p，形式参数为 phead 与 p。
第13页：传值调用的局限
当实际参数 head 赋给了形式参数 phead 之后，phead 就指向了已经存在了的链表，见下图：
phead → 5 → 10 → 15 → null
这时原来的主程序中的头指针就不再起作用了，而是 phead 起作用。假如现在 p 中的结点数据为 4 小于 5，应该将 p 插入到 phead 所指向的结点前。
第14页：传值调用无法改变head
图示：head 与 phead 之间的对比，待插入结点值为 4。
被调用函数无法改变 head，这时 head 不再是头结点的指针了。如果被调用函数返回 head，主函数只能表示 head 为头指针的三个结点，新插入的结点并没有包含进去。
要想将新插入到最前面的结点包含进去，就必须用传址调用。
第15页：传址调用的形式
（2）如果是传址调用，主程序中的调用语句为 insert(&head,p);
void insert(struct munST **phead, struct numST*p);
先看 struct numST **phead 是说定义 (*phead) 为指向 numST 结构的指针。*phead 是指向 numST 结构的指针，phead 又是指向 *phead 这个指针的指针。
phead=&head
第16页：实参地址传给形参
主程序中的实参为链表头指针 head 所在的地址值，传给被调用函数的 phead 指针变量中，起到了让 phead 也指向 head 的目的。
&head → phead → head
第17页：传址调用的效果
在主函数中 head 为头指针，在被调用的子函数中 phead 为头指针的地址，head 和 *phead 是同一个单元，只不过分别叫不同的名罢了。当然在子函数中无论插入什么结点都会让 *phead 指向链表的头。自然返回到主函数后，head 也会是指向同一链表的头。
从这个例子中读者可以领悟到传值调用与传址调用的区别。
5、这样在子函数做插入结点的过程中，头指针的改变也能反映到主函数中来。调用 print 函数，从 head 开始输出整个链表的内容。
第18页：insert函数的第一种情况
下面我们来研究 insert 函数。前提是主程序已将两个实参传给了 insert 函数的两个形参，这时 *phead=head，p 所指向的就是待插入的一个结点。事先定义两个结构指针 q 和 r。
第一种情况：*phead==null，说明主程序传过来的头指针为空，即链表为空，一个结点都不存在。这时待插入的 p 结点就是链表中的第一个结点。只要执行如下两条语句即可：
*phead=p;return; 
第19页：insert函数的第二种情况
第二种情况：p 结点的 num 值小于链表头结点的 num 值，即 (*phead)->num > p->num。这时要将 p 结点插入到头结点的前面，要执行如下三条语句：
p->next=*phead;*phead=p;return; 
第20页：insert函数的第三种情况
第三种情况：前两种情况，无论遇到哪一种，都会返回主程序。只要不返回就是这第三种情况，即 p 结点的 num 大于头指针所指向的结点的 num 值。这时肯定地说 p 结点要插入到头结点之后，究竟要插到哪里需要找到应该插入的位置。
我们设指针 r 和指针 q，分别指向相邻的两个结点，r 在前 q 在后，当满足 r->num < p->num < q->num 时，p 就插在 r 与 q 之间。
head → 5 → 10 → 12 → 15 → null ↑ ↑ r q
第21页：查找插入位置的两条分支
一开始让 r=*phead，让 q=*phead->next：
当指针 q 为空指针时，说明原链表中只有一个结点，即 r 指向的结点，这时只要将 p 结点接在 r 之后即可。执行 r->next=p;p->next=q;
如果 q!=null，说明起码有两个结点在链表中，接着要判 p 结点的 num 值是否大于 q 结点的 num 值。如果是大，则说明 p 应插在 q 之后而不是之前，这时让 r 和 q 指针同时后移一步，即 r=q;q=q->next;
第22页：找到位置后插入
执行（2），在 q!=null 的情况下，如果 p->num<=q->num 了，说明这时找到了正确的插入位置，退出 while 循环，将 p 结点插入到 r 后、q 前即可。使用的语句为：
r->next=p; p->next=q;
在下面我们画出该算法的结构框图。
第23页：作业一：学习小组链表
作业
1、按下表顺序输入某班的一个学习小组的成员表。希望你将学习小组形成一个链表，每人一个结点。结点中有四个成员：姓名、出生年、出生月、指针。在链表中生日大者在前，小者在后。建成链表后输出该链表。
第24页：学习小组输入数据表
学习小组成员输入表
姓名
出生年
出生月
郑琪
1982
6
武陆
1983
4
周芜
1983
5
李思
1982
9
孙参
1983
2
钱亮
1983
3
赵达
1983
1
说明：源文件该页姓名、年份与月份三行文字呈粘连状态，上表为按列对齐还原的结果，建议对照原图核对。
第25页：作业二：删除钱亮结点
2、一年后钱亮同学调至其它学习小组，希望你编程从原链表中删除钱亮所在结点，之后输出该链表。
提示：原链表如下（按生日由大到小排列）：
李思 1982 年 9 月（head 所指向的头结点）
郑琪 1982 年 6 月
孙参 1983 年 2 月
钱亮 1983 年 3 月
武陆 1983 年 4 月
周芜 1983 年 5 月
赵达 1983 年 1 月
查找待删除结点的位置，要从链头找起。
说明：源文件该页文字与链表图高度粘连，上述顺序为依据姓名与年月数据整理的结果，建议对照原图核对。
第26页：删除结点的四种情形
如果是链头结点，即有 head->name==待删者name，这时只要做 head=head->next; 即可
如果不是链头结点，要设两个指针 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;，意味着将孙参所在结点指向钱亮的指针，不再指向钱亮，而指向武陆。
第27页：二叉树章节
本页为二叉树章节标题页，由链表这一线性结构转入二叉树这一非线性结构。
第28页：二叉树的结构
链表结构是利用结构中的指针域将每个结点链接起来，形似链条，属于线性结构数据。下面介绍一种非线性结构的东西，二叉树。
先看下例：图中共有 7 个结点（结点 1 至结点 7），数据分别为 6、9、5、7、3、8、4，每个结点含一个整型数据与左指针 L、右指针 R，根结点由 root 指向，叶子结点的左右指针为 null。
说明：源文件该页为二叉树图形，结点数值与指针关系呈粘连状态，上表文字为依据图形整理，建议对照原图核对。
第29页：二叉树的特点
在图中：
外形象一棵倒立的树
最上层有一个“根结点”，指针 root 指向根结点
每个结点都是一个结构，一个成员是整型数据，两个成员是指针，分为左指针 L 和右指针 R
根结点的左指针指向左子树；右指针指向右子树
左子树或右子树本身又是一棵二叉树，又有它们自己的左子树和右子树，……这是递归定义的，因此，在处理时常可用递归算法
第30页：二叉树的遍历
二叉树的遍历——树的遍历是指访遍树中的所有结点。
对比看遍历一个单链表，从表头开始按一个方向从头到尾就可遍历所有结点。对二叉树来说就没有这样简单了，因为对树或是对子树都存在根（或子树的根）和左子树、右子树，先遍历谁？由之产生了三种不同的方法：
第31页：三种遍历方法
1、前序法
1.1 先访问根结点；1.2 遍历左子树；1.3 遍历右子树
2、中序法
2.1 遍历左子树；2.2 访问根；2.3 遍历右子树
3、后序法
3.1 遍历左子树；3.2 遍历右子树；3.3 访问根
第32页：中序遍历的递归算法
我们就以中序法为例研究如何遍历二叉树。仍然采用递归算法。令指针 p 指向二叉树的根结点。
struct TREE { int data; struct TREE *L, *R; }; struct TREE *p; 
第33页：中序遍历的与或图
本页为中序遍历二叉树的与或结点图：A 结点表示中序遍历以 p 结点为根的二叉树，函数为 LNR(p)，该结点为“或”结点，当 p 为空时取 B 结点（什么都不做），当 p 不空时进入 C 结点；C 为“与”结点，依次包含 D、E、F 三件事。
第34页：与或图的说明
该图说明如下：
1、A 结点表示中序遍历 p 结点为根的二叉树，函数为 LNR(p)。该结点为“或”结点，有两个分支。当 p 为空时，A 取 B 结点，什么都不做；当 p 不空时，说明树存在（起码有一个根），有结点 C。
2、C 结点为一个“与”结点，要依次做相关联的三件事情：
2.1 D 结点：中序遍历 p 的左子树，函数为 LNR(p->L)
2.2 E 结点：直接可解结点，访问 p 结点（比如输出 p 结点数据域中的值）
2.3 F 结点：中序遍历 p 的右子树，函数为 LNR(p->R)
第35页：递归关系的层次
3、比较 LNR(p) 与 LNR(p->L) 及 LNR(p->R) 可以看出，都是同一个函数形式，只不过代入了不同的参数，从层次和隶属关系看，p 是父结点的指针，而 p->L 和 p->R 是子结点的指针，p->L 是左子树的根，p->R 是右子树的根。
下面请大家做一个练习，依图 2 画“与或”图，将图 1 所示的二叉树用中序遍历，将所访问到的结点数据输出，如图 3。
第36页：中序遍历的练习结果
中序遍历的练习结果示例：
当 p 为空时：什么都不做
访问结点 1：输出 3
依此递归下去，即可按中序顺序输出二叉树各结点的数据。
第37页：二叉树结点结构
二叉树的建立——建立二叉树的过程是一个“插入”过程，下面我们用一个例子来讲解这一过程。
我们想建立这样一棵二叉树，树中的每一个结点有一个整数数据名为 data，有两个指针：左指针 L，右指针 R，分别指向这个结点的左子树和右子树，显然可以用如下名为 TREE 的结构来描述这种结点：
struct TREE { int data; struct TREE *L, *R; }
第38页：建立二叉树的思路
对二叉树最重要的是根，它起定位的作用，因此，首先建立的是根结点。也就是说，如果从键盘输入数据来建立二叉树，第一个数据就是这棵树的根的数据，之后再输入的数据，每一个都要与根中的数据作比较，以便确定该数据所在结点的插入位置。
假定我们这里依然用图 1 的中序遍历的方式。即如果待插入结点的数据比根结点的数据小，则将其插至左子树，否则插入右子树。
void insert(struct TREE **proot, struct TREE *p)
其中，指针 p 指向含有待插入数据的结点。proot 为树的根指针的地址。insert 函数可理解为将 p 结点插入到 *proot 所指向的树中。
第39页：insert函数的与或图
insert(proot, p) 可用下列与或结点图来描述：先判断根结点是否为空，为空则把 p 作为根；不为空则比较 p 结点数据与根结点数据的大小，分别递归插入左子树或右子树。
第40页：proot形参的含义
注意在上图中 proot 是被调用函数的形参。从前面对它的定义看，proot 是指针的指针，实际上是指向二叉树根结点的指针的指针，或者说是指向二叉树根结点的指针的地址。
因此，在主程序调用 insert 函数时，实参为 &root，形参为 proot 与 p。下面是建立二叉树的参考程序。
第41页：二叉树程序的定义部分
#include <stdio.h>#include <malloc.h>#define null 0#define LEN sizeof(struct TREE)struct TREE{ int data; struct TREE *L,*R;};
第42页：insert函数的递归实现
//被调用函数insert，将结点插入二叉树 void insert (struct TREE **proot, struct TREE* p) { if (*proot==null) { *proot = p; return; } else { if (p->data <= (*proot)->data) insert( &((*proot)->L), p); else insert( &((*proot)->R), p); } } 
第43页：print函数与main前段
//被调用函数，形参为TREE结构指针，输出二叉树内容 void print(struct TREE *root) { if (root == null) return; print(root->L); printf("%d",root->data); print(root->R);}void main(){ struct TREE *root, *p; int temp; root = null; p = null; printf("请输入待插入结点的数据\n"); printf("如果输入-1表示插入过程结束\n"); scanf("%d",&temp); 
第44页：主函数的输入循环
while(temp !=-1){ p = (struct TREE *) malloc(LEN); p->data = temp; p->L = p->R = null; insert( &root, p ); printf("请输入待插入结点的数据\n"); printf("如果输入-1表示插入过程结束\n"); scanf("%d",&temp);}if (root==null) printf("这是一棵空树。\n");else print(root);} 
第45页：第十二讲结束页
本页为第十二讲 链表插入结点的结束页，本讲内容至此结束。