基本数据结构及其运算课件

1、基本数据结构及其运算1第第2章章 基本数据结构及其运算基本数据结构及其运算2.1 数据结构的基本概念2.2 线性表及其顺序存储结构2.3 线性链表及其运算2.4 树与二叉树基本数据结构及其运算22.3 线性链表及其运算线性链表及其运算2.3.1 线性链表的基本概念2.3.2 线性链表的基本运算2.3.3 循环链表基本数据结构及其运算32.3.1 线性链表的基本概念线性链表的基本概念1.线性链表线性链表线性表的链式存储结构称为线性链表。基本数据结构及其运算4基本数据结构及其运算5基本数据结构及其运算6基本数据结构及其运算7基本数据结构及其运算8依次输出线性链表中的各结点值输入：线性链表的存储空间

2、V(1：m)、NEXT(1：m)； 线性链表的头指针HEAD。输出：依次输出线性链表中各结点的值。 PROCEDURE PRTLL(HEAD) jHEAD WHILE (j0) DO OUTPUT V(j) ； jNEXT(j) RETURN基本数据结构及其运算9 struct 结构体名 数据成员表； struct 结构体名 *指针变量名； 例如 struct node char name10； /*数据域*/ char sex； /*数据域*/ struct node *next； /*指针域*/ 基本数据结构及其运算10#include stdlib.h/* malloc 函数需要包含头文

3、件stdlib.h*/struct node /*定义结点类型*/ int d； /*数据域*/ struct node *next； /*指针域*/main() struct node *p； /*定义该类型的指针变量p*/ p=(struct node *)malloc(sizeof(struct node)； /*申请分配结点存储空间*/ free(p)； /*释放结点存储空间*/基本数据结构及其运算11#include stdlib.h#include stdio.hstruct node /*定义结点类型*/ int d； struct node *next； main() int

4、x； struct node *head， *p， *q； headNULL； /*置链表空*/ qNULL； scanf(“%d”， &x)； /*输入一个正整数*/基本数据结构及其运算12 while(x0) /*若输入值大于0*/ p(struct node *)malloc(sizeof(struct node)；/*申请一个结点*/ pdx； pnextNULL； /*置当前结点的数据域和指针域*/ if(headNULL) headp；/*若链表空，则将头指针指向当前结点p*/ else qnextp； /*将当前结点链接在最后*/ qp； /*置当前结点为链表最后一个结点

5、*/ scanf(%d， &x)； phead； while(p!NULL) /*从链表第一个结点开始打印各结点元素值，并删除*/ printf(%5d， pd)； /*打印当前结点中的数据*/ qp；ppnext；free(q)；/*删除当前结点并释放该结点空间*/ printf(n)；基本数据结构及其运算13双向链表基本数据结构及其运算142.带链的栈带链的栈基本数据结构及其运算15可利用栈及其运算基本数据结构及其运算16将结点送回可利用栈输入：可利用栈栈顶指针TOP（默认）；送回可利用栈的结点序号p。输出：结点p入栈后的可利用栈栈顶指针TOP（默认）。 PROCEDURE DIS

6、POSE(p) NEXT(p)TOP； TOPp RETURN从可利用栈取得一个结点输入：可利用栈的栈顶指针TOP（默认）。输出：退栈后的可利用栈栈顶指针TOP（默认）；存放取得结点序号 的变量p。 PROCEDURE NEW(p) pTOP； TOPNEXT(TOP) RETURN基本数据结构及其运算17带链栈的入栈运算输入：带链栈的栈顶指针top；入栈的元素值x。输出：元素x入栈后的带链栈栈顶指针top。 PROCEDURE PUSHLL(top，x) NEW(p) 从可利用栈取得一个新结点 V(p)x 置新结点数据域 NEXT(p)top 置新结点指针域 topp 改变栈顶指针 RETU

7、RN基本数据结构及其运算18#include stdlib.hstruct node /*定义结点类型*/ ET d； /*数据元素类型*/ struct node *next； ；pushll(top，x)ET x； struct node *top； struct node *p； p(struct node *)malloc(sizeof(struct node)； pdx； pnext*top；/*置新结点的数据域与指针域*/ *topp； /*改变栈顶指针*/ return；基本数据结构及其运算19带链栈的退栈运算输入：带链栈的栈顶指针top。输出：退栈后的带链栈栈顶指针top；存放

8、退出结点元素 值的变量y。 PROCEDURE POPLL(top，y) yV(top) 取出栈顶元素值 ptop top=NEXT(p) 改变栈顶指针 DISPOSE(p) 被删除结点送回可利用栈 RETURN基本数据结构及其运算20#include stdlib.hstruct node /*定义结点类型*/ ET d； /*数据元素类型*/ struct node *next； ；popll(top，y)ET y； struct node *top； struct node *p； y*topd； /*取出栈顶元素值*/ p*top； *toppnext； /*改变栈顶指针*/ free

9、(p)； return； /*释放被删除结点后返回*/基本数据结构及其运算213.带链的队列带链的队列基本数据结构及其运算22带链队列的入队运算输入：带链队列的队尾指针rear；入队的新元素x。输出：元素x入队后的带链队列队尾指针rear。 PROCEDURE ADDLL(rear，x) NEW(p) 从可利用栈取得一个新结点p V(p)x 置新结点的数据域 NEXT(p)0 置新结点的指针为空 NEXT(rear)p 最后一个结点的指针指向新结点 rearp 改变队尾指针 RETURN基本数据结构及其运算23#include stdlib.hstruct node /*定义结点类型*/ ET

10、 d； /*数据元素类型*/ struct node *next； ；addll(rear，x)ET x； struct node *rear； struct node *p； p(struct node *)malloc(sizeof(struct node)； pdx； pnextNULL； /*置新结点的数据域与指针域*/ *rearnextp； /*置最后一个结点的指针指向新结点*/ *rearp； /*改变队尾指针*/ return；基本数据结构及其运算24带链队列的退队运算输入：带链队列的排头指针front。输出：退队后的带链队列排头指针front；存放退出结点 值的变量y。 PR

11、OCEDURE DELLL(front，y) y=V(front) 取出排头元素值 pfront frontNEXT(front) 改变排头指针 DISPOSE(p) 释放删除的结点 RETURN基本数据结构及其运算25#include stdlib.hstruct node /*定义结点类型*/ ET d； /*数据元素类型*/ struct node *next； ；delll(front，y)ET y； struct node *front； struct node *p； y*frontd； /*取出排头元素值*/ p*front； *frontpnext； /*改变排头指针*/ fr

12、ee(p)； /*释放被删除结点*/ return；基本数据结构及其运算262.3.2 线性链表的基本运算线性链表的基本运算(1)在线性链表中包含指定元素的结点之前插入 一个新元素。(2)在线性链表中删除包含指定元素的结点。(3)将两个线性链表按要求合并成一个线性链表。(4)将一个线性链表按要求进行分解。(5)逆转线性链表。(6)复制线性链表。(7)线性链表的排序。(8)线性链表的查找。基本数据结构及其运算271.在线性链表中查找指定元素在线性链表中查找指定元素在非空线性链表中寻找包含元素x的前一个结点p输入：非空线性链表头指针HEAD；被寻找元素x。输出：非空线性链表中包含元素x的前一个结点

13、p。PROCEDURE LOOKST(HEAD，x，p)pHEADWHILE (NEXT(p)0)and(V(NEXT(p)x) DO pNEXT(p)RETURN基本数据结构及其运算28struct node /*定义结点类型*/ ET d； /*数据元素类型*/ struct node *next； ；struct node *lookst(head，x)ET x； struct node *head； struct node *p； phead； while(pnext!NULL)&(pnext)d)!x) ppnext； return(p)；基本数据结构及其运算292.线性链表

14、的插入线性链表的插入 在链式存储结构下的线性表中 插入一个新元素。基本数据结构及其运算30可利用栈与线性链表基本数据结构及其运算31(1)从可利用栈取得一个结点，设该结点号为p。 并置结点p的数据域为插入的元素值b，即V(p)b。(2)在线性链表中寻找包含元素x的前一个结点q。基本数据结构及其运算32(3)将结点p插入到结点q之后： 使结点p指向包含元素x的结点，即 NEXT(p)NEXT(q) 使结点q的指针域内容改为指向结点p，即 NEXT(q)p基本数据结构及其运算33线性链表的插入输入：线性链表的头指针HEAD；插入位置处的前一个结 点值x；插入的新元素b。输出：插入后的线性链表。PR

15、OCEDURE INSLST(HEAD，x，b)1. NEW(p)2. V(p)b3. IF (HEAD0) THEN HEADp； NEXT(p)0； RETURN 4. IF (V(HEAD)x) THEN NEXT(p)HEAD； HEADp； RETURN 5. LOOKST(HEAD，x，q)6. NEXT(p)NEXT(q)； NEXT(q)p7. RETURN基本数据结构及其运算34#include stdlib.hstruct node /*定义结点类型*/ ET d； struct node *next； ；inslst(head，x，b)ET x，b；struct node

16、 *head； struct node *p， *q； p(struct node *)malloc(sizeof(struct node)； pdb； /*置结点的数据域*/ if (*headNULL) /*链表为空*/ *headp；pnextNULL；return； if (*headd)x) /*在第一个结点前插入*/ pnext*head；*headp；return； qlookst(*head，x)；/*寻找包含元素x的前一个结点q*/ pnextqnext；qnextp；/*结点p插到结点q之后*/ return；基本数据结构及其运算353.线性链表的删除线性链表的删除 在链式

17、存储结构下的线性表中 删除包含指定元素的结点。基本数据结构及其运算36可利用栈与线性链表基本数据结构及其运算37(1)寻找包含元素x的前一个结点q。 则包含元素x的结点序号pNEXT(q)。(2)将结点q后的结点p删除，即 NEXT(q)NEXT(p)。基本数据结构及其运算38(3)将包含元素x的结点p送回可利用栈。基本数据结构及其运算39线性链表的删除输入：线性链表的头指针HEAD；需删除的元素x。输出：删除后的线性链表。PROCEDURE DELST(HEAD，x)1. IF (HEAD0) THEN “This is a empty list!”； RETURN 2. IF (V(HEA

18、D)x) THEN pNEXT (HEAD)；DISPOSE(HEAD)；HEADp； RETURN 3. LOOKST(HEAD，x，q)4. IF (NEXT(q)0) THEN “No this node in the list!”；RETURN 5. pNEXT(q)； NEXT(q)NEXT(p)6. DISPOSE(p)7. RETURN基本数据结构及其运算40#include stdlib.hstruct node /*定义结点类型*/ ET d； struct node *next； ；delst(head，x)ET x；struct node *head； struct no

19、de *p， *q； if (*headNULL) /*链表为空*/ printf(This is a empty list!n)；return； if (*headd)x) /*删除第一个结点*/ p*headnext；free(*head) ；*headp；return； qlookst(*head，x) ；/*寻找包含元素x的前一个结点q*/ if (qnextNULL) /*链表中没有包含元素x的结点*/ printf(No this node in the list!n)；return； pqnext ；qnextpnext； /*删除结点p*/ free(p) ； /*释放结点p*

20、/ return；基本数据结构及其运算412.3.3 循环链表循环链表(1)在循环链表中增加了一个表头结点， 其数据域为任意或根据需要来设置， 指针域指向线性表第一个元素的结点。 循环链表的头指针指向表头结点。(2)循环链表中最后一个结点的指针域不空， 而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。基本数据结构及其运算42(1)在循环链表中，只要指出表中任何一个结点的位置， 就可以从它出发访问到表中其他所有的结点。(2)空表与非空表的运算统一。基本数据结构及其运算43在头指针为HEAD的循环链表中寻找包含元素x的前一个结点输入：循环链表的头指针HEAD；被寻找的元素x。输出

21、：循环链表中包含元素x的前一个结点p。PROCEDURE LOOKCST(HEAD，x，p)pHEADWHILE (NEXT(p)HEAD)and(V(NEXT(p)x) DO pNEXT(p)RETURN基本数据结构及其运算44#include stdlib.hstruct node /*定义结点类型*/ ET d； struct node *next； ；struct node *lookcst(head，x)ET x； struct node *head； struct node *p； phead； while(pnext!head)&(pnext)d)!x) ppnext；

22、return(p)；基本数据结构及其运算45在头指针为HEAD的循环链表中包含元素x的结点前插入新元素b输入：循环链表的头指针HEAD；插入位置处的前一个结 点值x；插入的新元素b。输出：插入后的循环链表。PROCEDURE INSCST(HEAD，x，b)NEW(p) 从可利用栈取得一个新结点pV(p)b 置新结点p的数据域（插入的元素值b）LOOKCST(HEAD，x，q) 寻找循环链表中包含元素x的前一个结点qNEXT(p)NEXT(q)；NEXT(q)p 将新结点p插入到结点q之后RETURN基本数据结构及其运算46#include stdlib.hstruct node /*定义结点

23、类型*/ ET d； struct node *next； ；inscst(head，x，b)ET x，b；struct node *head； struct node *p， *q； p(struct node *)malloc(sizeof(struct node)； pdb； /*置结点的数据域*/ qlookcst(head，x) ；/*寻找包含元素x的前一个结点q*/ pnextqnext ；qnextp；/*结点p插入到结点q后*/ return；基本数据结构及其运算47在头指针为HEAD的循环链表中删除包含元素x的结点输入：循环链表的头指针HEAD；需删除的元素x。输出：删除后的

24、循环链表。PROCEDURE DELCST(HEAD，x)LOOKCST(HEAD，x，q) 寻找包含元素x的前一个结点qIF (NEXT(q)HEAD) THEN 循环链表中没有该结点 “No this node in the list!”；RETURN pNEXT(q)；NEXT(q)NEXT(p)删除结点q后的结点DISPOSE(p) 将被删除的结点p送回可利用栈RETURN基本数据结构及其运算48#include stdlib.hstruct node /*定义结点类型*/ ET d； struct node *next； ；delcst(head，x)ET x；struct node

25、 *head； struct node *p， *q； qlookcst(head，x) ；/*寻找包含元素x的前一个结点q*/ if (qnextNULL) /*链表中没有包含元素x的结点*/ printf(No this node in the list!n)；return； pqnext ；qnextpnext； /*删除结点p*/ free(p) ； /*释放结点p*/ return；基本数据结构及其运算492.4 数数 组组2.4.1 数组的顺序存储结构2.4.2 规则矩阵的压缩2.4.3 一般稀疏矩阵的表示基本数据结构及其运算502.4.1 数组的顺序存储结构数组的顺序存储结构1.

26、二维数组以行为主的顺序存储二维数组以行为主的顺序存储基本数据结构及其运算512.二维数组以列为主的顺序存储二维数组以列为主的顺序存储基本数据结构及其运算522.4.2 规则矩阵的压缩规则矩阵的压缩1.下三角矩阵的压缩存储下三角矩阵的压缩存储基本数据结构及其运算53用长度为n(n1)/2的一维数组B，一行接一行存放A中下三角部分的元素。基本数据结构及其运算54用长度为n(n1)/2的一维数组B，一列接一列存放A中下三角部分的元素。基本数据结构及其运算55基本数据结构及其运算562.对称矩阵的压缩存储对称矩阵的压缩存储基本数据结构及其运算573.三对角矩阵的压缩存储三对角矩阵的压缩存储基本数据结构

27、及其运算58用一个长度为3n2的一维数组B存放三条对角线上的元素基本数据结构及其运算59基本数据结构及其运算602.4.3 一般稀疏矩阵的表示一般稀疏矩阵的表示1. 稀疏矩阵的三列二维数组表示稀疏矩阵的三列二维数组表示基本数据结构及其运算61(1)非零元素所在的行号i；(2)非零元素所在的列号j；(3)非零元素的值V。即每一个非零元素可以用下列三元组表示： （i，j，V）基本数据结构及其运算62（1，3，3）（1，8，1）（3，1，9）（4，5，7）（5，7，6）（6，4，2）（6，6，3）（7，3，5）基本数据结构及其运算63（7，8，8）（1，3，3）（1，8，1）（3，1，9）（4，5，

28、7）（5，7，6）（6，4，2）（6，6，3）（7，3，5）基本数据结构及其运算64基本数据结构及其运算65POS(k)表示稀疏矩阵A中第k行的第一个非零元素 （如果有的话）在三列二维数组B中的行号；NUM(k)表示稀疏矩阵A中第k行中非零元素的个数。 POS(1)2 POS(k)POS(k1)NUM(k1) ， 2km基本数据结构及其运算66构造POS与NUM向量输入：与稀疏矩阵A对应的三列二维数组B。输出：POS与NUM向量。PROCEDURE POSNUM(B，POS，NUM)tB(1，3) 非零元素个数mB(1，1) 稀疏矩阵行数FOR k1 TO m DO NUM(k)0 置NUM向

29、量初值FOR k2 TO t1 DO NUM(B(k,1)NUM(B(k,1)1设置NUM向量POS(1)2FOR k2 TO m DO POS(k)POS(k1)NUM(k1) 设置POS向量RETURN基本数据结构及其运算67struct ab int i；/*稀疏矩阵A的行数或非零元素所在的行号*/ int j；/*稀疏矩阵A的列数或非零元素所在的列号*/ ET v；/*稀疏矩阵A中非零元素个数（用ET类型表示的整数）或非零元素值*/ ；posnum(b，pos，num)struct ab b ；int *pos， *num； int k，m，t； mb0.i； t(int)(b0.v)

30、； for (k0； km； k) numk0； for (k1； kt； k) numbk.inumbk.i1； pos01； for (k1; km； k) poskposk1numk1； return；基本数据结构及其运算682.十字链表十字链表基本数据结构及其运算69用十字链表表示稀疏矩阵的结构特点(1)稀疏矩阵的每一行与每一列均用带表头结点的循环链 表表示。(2)表头结点中的行域与列域的值均置为0 （即row0，col0）。(3)行、列链表的表头结点合用，且这些表头结点通过值 域（即val）相链接，并再增加一个结点作为它们的 表头结点H，其行、列域值分别存放稀疏矩阵的行数 与列数。只

31、要给出头指针H的值，便可扫描到稀疏矩阵中的任意一个非零元素。基本数据结构及其运算70基本数据结构及其运算71基本数据结构及其运算722.5 树与二叉树树与二叉树2.5.1 树的基本概念2.5.2 二叉树及其基本性质2.5.3 二叉树的存储结构2.5.4 二叉树的遍历2.5.5 穿线二叉树2.5.6 表达式的线性化基本数据结构及其运算732.5.1 树的基本概念树的基本概念基本数据结构及其运算74基本数据结构及其运算75基本数据结构及其运算76基本数据结构及其运算77(1)表达式中的每一个运算符在树中对应 一个结点，称为运算符结点。(2)运算符的每一个运算对象在树中为该运 算符结点的子树（在树中

32、的顺序为从左 到右）。(3)运算对象中的单变量均为叶子结点。基本数据结构及其运算78a*(bc/d)e*hg*f(s，t，xy)基本数据结构及其运算79a*(bc/d)e*hg*f(s，t，xy)基本数据结构及其运算80树链表中的结点结构基本数据结构及其运算812.5.2 二叉树及其基本性质二叉树及其基本性质基本数据结构及其运算821.什么是二叉树什么是二叉树 (1)非空二叉树只有一个根结点； (2)每一个结点最多有两棵子树，且分别称为该结 点的左子树与右子树。基本数据结构及其运算832.二叉树的基本性质二叉树的基本性质性质性质1 1 在二叉树的第k层上，最多有2k1(k1)个 结点。性质性质

33、2 2 深度为m的二叉树最多有2m1个结点。性质性质3 3 在任意一棵二叉树中，度为0的结点 （即叶子结点）总是比度为2的结点多一个。性质性质4 4 具有n个结点的二叉树，其深度至少为 log2n1 其中log2n表示取log2n的整数部分。基本数据结构及其运算843.满二叉树与完全二叉树满二叉树与完全二叉树(1) 满二叉树基本数据结构及其运算85(2)完全二叉树基本数据结构及其运算86基本数据结构及其运算87性质性质5 5 具有n个结点的完全二叉树的深度为log2n1。性质性质6 6 设完全二叉树共有n个结点。如果从根结点开始， 按层序（每一层从左到右）用自然数1，2，n 给结点进行编号，则

34、对于编号为k(k1，2，n) 的结点有以下结论： (1)若k1，则该结点为根结点，它没有父结点； 若k1，则该结点的父结点编号为INT(k/2)。 (2)若2kn，则编号为k的结点的左子结点编号为2k； 否则该结点无左子结点（显然也没有右子结点）。 (3)若2k1n，则编号为k的结点的右子结点编号 为2k1；否则该结点无右子结点。基本数据结构及其运算882.5.3 二叉树的存储结构二叉树的存储结构1.二叉链表二叉链表 #include stdlib.h struct btnode /*定义结点类型*/ ET d； /*数据域*/ struct btnode *lchild； /*左指针域*/

35、struct btnode *rchild； /*右指针域*/ ；基本数据结构及其运算89基本数据结构及其运算90基本数据结构及其运算91基本数据结构及其运算922.二叉链表的生成二叉链表的生成(1)输入根结点值；(2)若左子树不空，则输入左子树，否则输入一个结束符；(3)若右子树不空，则输入右子树，否则输入一个结束符。 例如， FCADBEGHP其中表示结束符基本数据结构及其运算93二叉链表的生成输入：二叉链表的头指针BT为空；根结点标志k0。输出：二叉链表的头指针BT。PROCEDURE CREATBT(BT，k)INPUT b IF b结束符 THEN 输入的不是结束符 NEW(p) 取

36、一个新结点 V(p)b； L(p)0； R(p)0 置新结点的值域为b及左右指针域 IF k0 THEN BTp 若是第一个值，则置二叉链表头指针 IF k1 THEN L(BT)p 链接到左子树 IF k2 THEN R(BT)p 链接到右子树 CREATBT(p，1) 输入左子结点值 CREATBT(p，2) 输入右子结点值 RETURN基本数据结构及其运算94#include stdio.h”#include stdlib.h”struct btnode int d； struct btnode *lchild； struct btnode *rchild； ；struct btnode

37、 *creatbt(bt，k)struct btnode *bt；int k； int b； struct btnode *p， *t； printf(input b ：)； scanf(%d，&b)；基本数据结构及其运算95 if (b!0) /*输入的不是结束符*/ p(struct btnode *)malloc(sizeof(struct btnode)； pdb； plchildNULL； prchildNULL； if (k0) tp；/*若是第1个值，则置二叉链表头指针*/ if (k1) btlchildp； /*链接到左子树*/ if (k2) btrchildp；

38、/*链接到右子树*/ creatbt(p，1)； /*输入左子结点值*/ creatbt(p，2)； /*输入右子结点值*/ return(t)/*返回二叉链表头指针*/基本数据结构及其运算962.5.4 二叉树的遍历二叉树的遍历1.前序遍历前序遍历(DLR)若二叉树为空，则结束返回。否则：(1)访问根结点；(2)前序遍历左子树；(3)前序遍历右子树。基本数据结构及其运算97输入：二叉链表的头指针BT。输出：以BT为头指针的二叉链表的前序序列。 PROCEDURE PRETRAV(BT) IF BT0 THEN OUTPUT V(BT) PRETRAV(L(BT) PRETRAV(R(BT)

39、RETURN基本数据结构及其运算98#include stdio.hstruct btnode int d；struct btnode *lchild；struct btnode *rchild；pretrav(bt)struc btnode *bt； if (bt !NULL) printf(%dn，btd)； pretrav(btlchild)； pretrav(btrchild)； return；基本数据结构及其运算992.中序遍历中序遍历(LDR)若二叉树为空，则结束返回。否则：(1)中序遍历左子树；(2)访问根结点；(3)中序遍历左子树。基本数据结构及其运算100输入：二叉链表的头指

40、针BT。输出：以BT为头指针的二叉链表的中序序列。 PROCEDURE INTRAV(BT) IF BT0 THEN INTRAV(L(BT) OUTPUT V(BT) INTRAV(R(BT) RETURN基本数据结构及其运算101#include stdio.hstruct btnode int d；struct btnode *lchild；struct btnode *rchild；intrav(bt)struc btnode *bt； if (bt !NULL) intrav(btlchild)； printf(%dn，btd)； intrav(btrchild)； return；基

41、本数据结构及其运算1023.后序遍历后序遍历(LRD)若二叉树为空，则结束返回。否则：(1)后序遍历左子树；(2)后序遍历左子树；(3)访问根结点。基本数据结构及其运算103输入：二叉链表的头指针BT。输出：以BT为头指针的二叉链表的后序序列。 PROCEDURE POSTRAV(BT) IF BT0 THEN POSTRAV(L(BT) POSTRAV(R(BT) OUTPUT V(BT) RETURN基本数据结构及其运算104#include stdio.hstruct btnode int d；struct btnode *lchild；struct btnode *rchild；pos

42、trav(bt)struc btnode *bt； if (bt !NULL) postrav(btlchild)； postrav(btrchild)； printf(%dn，btd)； return；基本数据结构及其运算1052.5.5 穿线二叉树穿线二叉树1.穿线二叉树的概念穿线二叉树的概念基本数据结构及其运算1062.穿线二叉树的构造穿线二叉树的构造基本数据结构及其运算107基本数据结构及其运算108 struct btnode ET d； /*数据域*/ int lflag； /*左标志域*/ int rflag； /*右标志域*/ struct btnode *lchild；/*左

43、指针域*/ struct btnode *rchild；/*右指针域*/ 基本数据结构及其运算109(1)若上次访问到的结点的右指针为空，则 将当前访问到的结点序号的负值填入；(2)若当前访问到的结点的左指针为空，则 将上次访问到的结点序号的负值填入。基本数据结构及其运算110构造中序穿线二叉树输入：二叉链表的头指针BT；h0。输出：在二叉链表中加中序线索。PROCEDURE INTHREAD(BT，h)IF BT0 THEN INTHREAD(L(BT)，h) IF (h0)and(R(h)0) THEN R(h)BT； Rflag(h)1 IF L(BT)0 THEN L(BT)h； Lf

44、lag(BT)1 hBT INTHREAD(R(BT)，h) RETURN基本数据结构及其运算111 struct btnode ET d； /*数据域*/ int lflag； /*左标志域*/ int rflag； /*右标志域*/ struct btnode *lchild； /*左指针域*/ struct btnode *rchild； /*右指针域*/ ；基本数据结构及其运算112 inthread(bt，h) struct btnode *bt， *h； if (bt!NULL) inthread(btlchild，h)； if (btlchildNULL) btlchild*h；

45、 btlflag1； if (*h!NULL)&(*h)rchildNULL) (*h)rchildbt； (*h)rflag1； *hbt； inthread(btrchild，h)； return； 基本数据结构及其运算1133.穿线二叉树的遍历穿线二叉树的遍历从二叉树的根结点开始，沿左链找到叶子结点，该叶子结点即为中序序列的第一个结点。然后从中序序列的第一个结点开始扫描，依次找出中序序列中的后件。其规则如下： 若当前结点的右标志值为1，则当前结点的指针值为其后件 的存储序号； 若当前结点的右指针值不空，则沿右子树的左链进行搜索， 直到发现某个结点的左标志值为1且左指针值不空为止，

46、该 结点即为当前结点的后件。基本数据结构及其运算114中序穿线二叉树的遍历输入：二叉链表的头指针BT。输出：中序遍历序列。PROCEDURE INTHTRAV(BT)IF BT0 THEN RETURNhBTWHILE (Lflag(h)0) DO hL(h) 沿左链找到第一个结点OUTPUT V(h) 输出第一个结点基本数据结构及其运算115WHILE (R(h)0) DO IF (Rflag(h)1) THEN hR(h) ELSE hR(h) WHILE (Lflag(h)0)and(L(h)0) DO hL(h) OUTPUT V(h) RETURN基本数据结构及其运算116struc

47、t btnode int d； /*数据域，假设为整型*/ int lflag； /*左标志域*/ int rflag； /*右标志域*/ struct btnode *lchild；/*左指针域*/ struct btnode *rchild；/*右指针域*/ ；基本数据结构及其运算117inthtrav(bt)struct btnode *bt； struct btnode *h； if (btNULL) return； hbt； while (hlflag0) hhlchild； printf(%dn，hd)；基本数据结构及其运算118 while (hrchild!NULL) if (

48、hrflag1) hhrchild； else hhrchild； while (hlflag0)&(hlchild!NULL) hhlchild； printf(%dn，hd)； return；基本数据结构及其运算1192.5.6 表达式的线性化表达式的线性化1.有序树的二叉树表示有序树的二叉树表示将有序树转化成二叉树的原则：(1)有序树T中的结点与二叉树BT中的结点一一对应；(2)有序树T中某个结点N的第一个子结点（即最左边的子 结点）N1，在二叉树BT中为对应结点N的左子结点；(3)有序树T中某个结点N的第一个子结点以后的其他子结 点，在二叉树BT中被依次链接成一串起始于N1的右

49、子结点。基本数据结构及其运算120a*(bc/d)e*hg*f(s，t，xy)基本数据结构及其运算121基本数据结构及其运算1222.表达式的线性化表达式的线性化(1)将表达式用有序树表示，即构造表达式树。(2)将表达式树化为二叉树。(3)对相应的二叉树进行中序遍历，其遍历序列即为表达 式的波兰表示式。基本数据结构及其运算123表达式 a*(bc/d)e*hg*f(s，t，xy)的波兰表示式为 a b c d / * e h * g s t x y f * 基本数据结构及其运算1242.6 图图2.6.1 图的基本概念2.6.2 图的存储结构2.6.3 图的遍历基本数据结构及其运算1252.6

50、.1 图的基本概念图的基本概念基本数据结构及其运算126基本数据结构及其运算1272.6.2 图的存储结构图的存储结构1.关联矩阵关联矩阵长度为n的一维数组D(1：n)存放图中各数据结点的信息。n阶的二维数组R(1：n，1：n)存放图中各结点的关联息。其中二维数组R称为图的关联矩阵。在关联矩阵R中，每一个元素R(i，j) (1in，1jn)的定义为基本数据结构及其运算128基本数据结构及其运算129基本数据结构及其运算130基本数据结构及其运算131基本数据结构及其运算1322.求值矩阵求值矩阵基本数据结构及其运算133基本数据结构及其运算1343.邻接表邻接表（“顺序索引链接”存储结构）基本

51、数据结构及其运算135基本数据结构及其运算136基本数据结构及其运算137struct node /*单链表中结点结构*/ int num；/*图中结点编号*/ ET1 val；/*求值函数*/ struct node *next；/*指针域*/ ；struct gpnode /*顺序存储空间中结点结构*/ ET data； /*结点值*/ struct node *link；/*指针域*/ ；基本数据结构及其运算138图邻接表的构造输入：图的结点数n；依次存放图中结点值的数组D(1：n)。输出：邻接表顺序存储空间的首地址。PROCEDURE CREATGP(D，n)定义DATA(1：n)，L

52、INK(1：n) 建立顺序存储空间FOR k0 TO n DO DATA(k)Dk； LINK(k)0 INPUT m，v /*输入图中第k个结点的后件信息*/ WHILE (m0) DO /*输入后件信息未结束*/ NEW(p) /*分配单链表结点*/ NUM(p)m； VAL(p)v；NEXT(p)LINK(k)；LINK(k)p INPUT m，v /*继续输入后件信息*/ RETURN基本数据结构及其运算1392，63（回车）3，95（回车）4，84（回车）1，1（回车）（结点A的后件）1，63（回车）3，49（回车）4，44（回车）5，37（回车）1，1（回车） （结点B的后件）1，

53、95（回车）2，49（回车）1，1（回车）（结点C的后件）1，84（回车）2，44（回车）5，35（回车）1，1（回车）（结点D的后件）2，37（回车）4，35（回车）1，1（回车）（结点E的后件）基本数据结构及其运算140#include stdio.h #include stdlib.hstruct node /*单链表中结点结构*/ int num； /*图中结点编号*/ int val； /*求值函数*/ struct node *next； /*指针域*/ ；struct gpnode /*顺序存储空间中结点结构*/ char data； /*结点值*/ struct node *l

54、ink； /*指针域*/ ；基本数据结构及其运算141struct gpnode *creatgp(d，n)/*该函数返回顺序存储空间的首地址*/int n；char d； struct gpnode *head； struct node *p； int k，m，v； head(struct gpnode *)malloc(n*sizeof(struct gpnode)； for (k0；kn；k) /*依次对图中的每一个结点建立链接所有后件的单链表*/ (headk)datadk； /*置顺序存储空间的结点值*/ (headk)linkNULL；/*置顺序存储空间结点指针域为空*/ prin

55、tf(input linked list of %c :n，dk)； scanf(“%d%d”，&m，&v)； /*输入图中第k个结点的后件信息*/基本数据结构及其运算142 while (m0) /*输入后件信息未结束*/ p(struct node *)malloc(sizeof(struct node)； pnumm； pvalv；/*后件结点号与求值函数值*/ pnext(headk)link；/*新结点指针指向头结点*/ (headk)linkp； /*将新结点链接到单链表链头*/ scanf(%d%d，&m，&v)；/*继续输入后件信息*/ retu

56、rn(head)；/*返回顺序存储空间的首地址*/基本数据结构及其运算1434.邻接多重表邻接多重表基本数据结构及其运算1442.6.3 图的遍历图的遍历1.纵向优先搜索法纵向优先搜索法从图中某一结点作为当前结点，然后进行以下过程：(1)处理或输出当前结点，记录当前结点的查访标志。(2)若当前结点有后件结点，则取第一个后件结点。 若该后件结点未被查访过，则以该后件结点为当 前结点用纵向优先搜索法进行查访。已被访问过结点未被访问过结点k1k0)k(MARK基本数据结构及其运算145纵向优先搜索法遍历图的递归算法输入：图中结点数n；邻接表顺序存储空间DATA(1：n) 与LINK(1：n)；单链表

57、的存储空间NUM与NEXT。输出：遍历序列。PROCEDURE DFSGP(DATA，LINK，n，NUM，NEXT)定义标志数组MARK(1：n)FOR k1 TO n DO MARK(k)0 标志数组初始化k1FOR k1 TO n DODFS(DATA，LINK，k，MARK) IF MARK(k)0 THEN DFS(DATA，LINK，k，MARK)RETURN基本数据结构及其运算146PROCEDURE DFS(DATA，LINK，k，MARK，NUM，NEXT) OUTPUT DATA(k) 处理或输出当前结点值MARK(k)1 记录当前结点的查访标志pLINK(k) 当前结点的

58、第一个后件结点WHILE (p0) DO 存在后件结点 kNUM(p) 后件结点的结点编号 IF MARK(k)0 THEN 该后件结点未被查访过 DFS(DATA，LINK，k，MARK，NUM，NEXT) pNEXT(p) 下一个后件结点 RETURN基本数据结构及其运算147#include stdlib.h#include “stdio.h”struct node /*单链表中结点结构*/ int num； /*图中结点编号*/ int val； /*求值函数*/ struct node *next；/*指针域*/ ；struct gpnode /*顺序存储空间中结点结构*/ char

59、 data； /*结点值*/ struct node *link； /*指针域*/ ；基本数据结构及其运算148dfsgp(head，n)struct gpnode *head；int n； int k，*mark； markmalloc(n*sizeof(int)；/*定义标志数组空间*/ for (k0； kn； k) markk0；/*标志数组初始化*/ k1； /* for (k1； kn； k) */ dfs(head，k，mark)； /* if (markk10) dfs(head，k，mark)；*/ printf(n)； free(mark)； /*释放标志数组空空间*/ r

60、eturn；基本数据结构及其运算149static dfs(head，k，mark) /*递归函数*/struct gpnode *head；int k，*mark； struct node *p； printf(%c，(headk1)data)；/*输出当前结点值*/ markk11；/*记录当前结点的查访标志*/ p(headk1)link； /*当前结点的第一个后件结点*/ while (p!NULL) /*还存在后件结点*/ if (mark(pnum)10) /*该后件结点未被查访过*/ dfs(head，pnum，mark)；/*递归调用*/ ppnext；/*下一个后件结点*/ return；基本数据结构及其运算150纵向优先搜索法遍历图的非递归算法输入：图中的结点数n；邻接表的顺序存储空间DATA(1：n