数据结构(C语言描述)课件.ppt

《数据结构(C语言描述)课件.ppt》由会员分享，可在线阅读，更多相关《数据结构(C语言描述)课件.ppt（178页珍藏版）》请在三一办公上搜索。

1、数据结构辅导,李青山西安电子科技大学http:/202.117.118.45/faculty/029-8820-4611,课程内容框架,数 据 结 构,基础数据结构,应用数据结构,栈,队列,线性表,线性结构,非线性结构,串,查找,内部排序,外部排序,文件,动态存管理储,数组,广义表,树,二叉树,图,基本概念,1.2基本概念和术语,数据、数据元素、数据项、数据对象结构*集合：松散的关系*线性结构：一对一的关系*树形结构：一对多的关系*网状结构：多对多的关系数据结构Data_Structure=（D，S）,数据结构的分类,1.2基本概念和术语（续）,逻辑结构：数据元素之间的逻辑关系（本来的关系）存

2、储结构：数据结构在计算机中的映象。包括数据元素的表示和关系的表示两个方面。分类：*顺序存储结构*链式存储结构描述方式：用高级语言中的“数据类型”来描述,算法,1.3算法和算法分析,内涵:是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。特性:*有穷性：有穷步+有穷时间/每一步*确定性：指令的语义无二义性*可行性：算法能用基本操作完成*输入：零个或多个输入*输出：一个或多个输出,算法设计的要求,1.3算法和算法分析（续）,正确性（Correctness）可读性（Readablity）健壮性（Robustness）高时间效率与低存储量需求,算法时间效率的度量,1.

3、3算法和算法分析（续）,算法时间效率度量的基本做法在算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。一般而言，这个基本操作是最深层循环内的语句中的原操作。算法时间复杂度 T(n)=O(f(n)称为算法的渐近时间复杂度，简称时间复杂度。,算法存储空间的度量,1.3算法和算法分析（续）,算法存储空间度量的基本做法用程序执行中需要的辅助空间的消耗作为存储空间度量的依据，是问题规模n的函数。而程序执行中本身需要的工作单元不能算。算法空间复杂度 S(n)=O(f(n)称为算法的空间复杂度。,2.线性表3.栈、队列和串,第一部分 线性数据结构,线性数据结构

4、的特点,2.1线性表的逻辑结构,在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素；存在唯一的一个被称作“最后一个”的数据元素；除第一个之外，集合中的每一个数据元素均只有一个前驱；除最后一个之外，集合中每一个数据元素均只有一个后继。,基本概念和术语,2.1线性表的逻辑结构（续）,线性表：n个数据元素的有限序列（线性表中的数据元素在不同环境下具体含义可以不同，但在同一线性表中的元素性质必须相同）。表长：线性表中元素的个数n(n=0)。空表：n=0时的线性表称为空表。位序：非空表中数据元素 ai 是此表的第 i 个元 素，则称 i 为 ai 在线性表中的位序。,线性表的抽象数据类型定

5、义,2.1线性表的逻辑结构（续）,ADT List 数据对象：D=ai|ai属于ElemSet,i=1,2,n,n=0数据关系：R1=|ai-1,ai属于D,i=2,3,n,基本操作：InitList(&L)DestroyList(&L)ClearList(&L)ListLength(L)GetElem(L,i,&e)初始条件：L存在；1=i=ListLength(L)操作结果：用e返回L中第i个 数据元素的值 ADT List,LocateElem(L,e,compare()初始条件：L存在；compare()是判定条件 操作结果：返回第1个与e满足关系compare()的 数据元素位序，若

6、不存在，则返回0ListInsert(&L,i,e)初始条件：L存在；1=i=ListLength(L)+1 操作结果：第i个位置之前插入元素e，长度加1ListDelete(&L,i,&e)初始条件：L存在；非空；1=i=ListLength(L)操作结果：删除第i个元素，e返回值，长度减1,顺序表-线性表的顺序存储,2.2线性表的顺序存储结构,内涵：线性表的顺序存储指用一组地址连续的存储单元依次存储线性表的数据元素。这称为顺序表。特点：*存储单元地址连续（需要一段连续空间）*逻辑上相邻的数据元素其物理位置也相邻*随机存取*存储密度为大（100%）,顺序表的随机存取,2.2线性表的顺序存储结

7、构（续）,对线性表L,设每个元素占k个存储单元，则有：递推关系：LOC(ai+1)=LOC(ai)+k任一元素ai+1的存储位置：LOC(ai)=LOC(a1)+(i-1)*k(其中1=i=ListLength(L),顺序表上插入运算的实现,2.2线性表的顺序存储结构（续）,（a1，ai,ai+1,an)表长为n,Status ListInsert_Sq(SqList 第四步：插入；/ListInsert_Sq,（a1，ai-1,e，ai,an)表长为n+1,顺序表上删除运算的实现,2.2线性表的顺序存储结构（续）,（a1，ai,ai+1,an)表长为n,Status ListDelete_S

8、q(SqList&L,int i,ElemType&e)第一步：判断参数是否合法合理，否则出错；第二步：在物理空间中找到删除位置；第三步：删除；第四步：删除后的善后工作/ListDelete_Sq,（a1，ai-1,ai+1,an)表长为n-1,顺序表优缺点分析,2.3线性表的链式存储结构,优点：*不需要额外空间来存储元素之间的关系*可以随机存取任一元素,缺点：*插入和删除运算需要移动大量元素*需要一段连续空间*预先分配足够大的空间*表的容量难以扩充,链表-线性表的链式存储,2.3线性表的链式存储结构（续）,内涵：线性表的链式存储指用任意的存储单元存放线性表中的元素，每个元素与其前驱和（或）后

9、继之间的关系用指针来存储。这称为链表。,术语：*结点*数据域*指针域*头指针*头结点,分类：*单链表*循环链表*双向链表*双向循环链表*静态链表,单链表,2.3线性表的链式存储结构（续）,单链表中，如果每个结点中只包含一个指域，称这种链表为线性链表或单链表。单链表可由头指针唯一确定。,单链表的数据类型描述,用高级语言中的指针类型描述线性表的链式存储,/-用结构指针描述-typedef struct LNodeElemTypedata/数据域struct LNode*next/指针域 Lnode,*LinkList,2.3线性表的链式存储结构（续）,单链表上插入运算的实现,2.3线性表的链式存储

10、结构（续）,（a1，ai,ai+1,an)表长为n,（a1，ai-1,e，ai,an)表长为n+1,S=(LinkList)malloc(sizeof(LNode),s-next=p-next;p-next=s,单链表上删除运算的实现,2.3线性表的链式存储结构（续）,（a1，ai,ai+1,an)表长为n,（a1，ai-1,ai+1,an)表长为n-1,free(q),p-next=p-next-next,2.线性表3.栈、队列和串,教学内容-第三章,栈、队列和串是特殊的线性表,3.1 栈、队列和串的逻辑结构,栈和队列是操作受限的线性表栈和队列的“操作受限”指操作位置受限串的特殊性在于线性表

11、中数据元素只能是字符串一般以子串为操作单位栈、队列和串具有一般线性表共性的特点特殊的线性表反而应用面更宽,栈的基本概念和术语,3.1 栈、队列和串的逻辑结构（续）,栈（Stack）：限定仅在表尾进行插入或删除操作的线性表。栈顶（top）：插入或删除的表尾端。栈底（bottom）：表头端。空栈：空表。,栈的操作特点：后进先出（Last In First Out-LIFO）,栈的抽象数据类型定义,3.1 栈、队列和串的逻辑结构（续）,ADT Stack 数据对象：D=ai|ai属于ElemSet,i=1,2,n,n=0数据关系：R1=|ai-1,ai属于D,i=2,3,n/a1 为栈底，an 栈顶

12、,基本操作：InitStack(&S)DestroyStack(&S)StackEmpty(S)ClearStack(&S)StackLength(S)GetTop(S,&e)初始条件：S存在,非空；操作结果：用e返回S的栈顶元素,Push(&S,e)初始条件：S存在 操作结果：插入元素e为新的栈顶元素，长度加 1Pop(&S,&e)初始条件：S存在；非空 操作结果：删除S的栈顶元素，e返回值，长度 减1ADT Stack,队列的基本概念和术语,3.1 栈、队列和串的逻辑结构（续）,队列（Queue）：限定仅在表的一端进行插入，而另一端进行删除操作的线性表。队尾（rear）：允许插入的一端。队

13、头（front）：允许删除的一端。空队：空表。,队列操作特点：先进先出（First In First Out-FIFO）,队列的抽象数据类型定义,3.1 栈、队列和串的逻辑结构（续）,ADT Queue 数据对象：D=ai|ai属于ElemSet,i=1,2,n,n=0数据关系：R1=|ai-1,ai属于D,i=2,3,n/a1 为队头，an 队尾,基本操作：InitQueue(&Q)DestroyQueue(&Q)ClearQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)初始条件：Q存在,非空；操作结果：用e返回Q的栈顶元素,EnQueue(

14、&Q,e)初始条件：Q存在 操作结果：插入元素e为新的队尾元素，长度加 1DelQueue(&S,&e)初始条件：Q存在；非空 操作结果：删除Q的对头元素，e返回值，长度 减1ADT Queue,串的基本概念和术语,3.1 栈、队列和串的逻辑结构（续）,串（String）：由零个或多个字符组成的有限序列。S=a1a2an串名、串值串长空串、空格串子串：串中任意连续的字符组成的子序列主串：字符在串中的位置、子串在串中的位置串相等,串的操作特点：一般以子串整体为单位,串的抽象数据类型定义,3.1 栈、队列和串的逻辑结构（续）,ADT Sring 数据对象：D=ai|ai属于CharacterSet

15、,i=1,2,n,n=0数据关系：R1=|ai-1,ai属于D,i=2,3,n,基本操作：StrAssign(&T,chars)StrCopy(&T,S)StrEmpty(S)StrLength(S)SubString(&Sub,S,pos,len)初始条件：S存在,1=pos=StrLength(S),0=len=StrLength(S)-pos+1；操作结果：,Index(S,T,pos)StrInsert(&S,pos,T)初始条件：S存在,1=pos=StrLength(S)+1 操作结果：在串S的第pos个字符之前插入串TStrDelete(&S,pos,len)初始条件：S存在,1

16、=pos=StrLength(S)-len+1 操作结果：从串S中删除第pos个字符起长度为 len 的子串ADT String,栈的顺序存储,3.2 栈、队列和串的存储结构,/-动态分配-#define STACK_INIT_SIZE 100/空间初始分配量#define STACKINCREMENT 10/空间分配增量typedef struct sElemType*basesElemType*topintstacksize/当前分配的存储容量 SqStack,Status Push(SqStack/Push,顺序栈上的入栈,3.2 栈、队列和串的存储结构（续）,Status Pop(Sq

17、Stack/Pop,顺序栈上的出栈,3.2 栈、队列和串的存储结构（续）,栈的链式存储-链栈,3.2 栈、队列和串的存储结构（续）,typedef struct ElemTypedatastruct Lnode*next Lnode,*StackPtr,typedef struct StackPtr top StackPtr base LinkStack,链栈上的入栈与出栈,3.2 栈、队列和串的存储结构（续）,链栈上的入栈与出栈与单链表上元素插入删除操作类似插入删除位置都在栈顶处，不花费查找时间栈空的判断,队列的顺序存储-循环队列（一）,3.2 栈、队列和串的存储结构（续）,一般顺序存储的队

18、列特点：队空条件：front=rear队满条件：rear=MAXSIZE队满条件下的队满为假满（假溢出）（真满时：rear=MAXSIZE,front=0）,/-动态分配-#define MAXSIZE 100/最大队列长度typedef struct QElemType*baseintfront/指向队头元素当前位置intrear/指向队尾元素下一个位置 SqQueue,队列的顺序存储-循环队列（二),3.2 栈、队列和串的存储结构（续）,循环队列特点：队空条件：*front=rear（方式一）*标志域+（front=rear）（方式二）队满条件：*(rear+1)%MAXSIZE=fron

19、t（方式一）*标志域+（front=rear）（方式二）队满条件下的队满为真满,队列的顺序存储-循环队列（三),3.2 栈、队列和串的存储结构（续）,队列的顺序存储-循环队列（四),3.2 栈、队列和串的存储结构（续）,Status EnQueue(SqQueue/EnQueue,Status InitQueue(SqQueue/InitQueue,Status DeQueue(SqQueue/DeQueue,队列的链式存储-链队列（一）,3.2 栈、队列和串的存储结构（续）,typedef struct QElemTypedatastruct QNode*next QNode,*QueueP

20、tr,typedef struct QueuePtr rear QueuePtr front LinkQueue,Status EnQueue(LinkQueue/EnQueue,Status InitQueue(LinkQueue/InitQueue,Status DeQueue(LinkQueue/DeQueue,队列的链式存储-链队列（二）,3.2 栈、队列和串的存储结构（续）,串的顺序存储（一）,3.2 栈、队列和串的存储结构（续）,/-串的定长顺序存储表示-#define MAXSTRLEN 255/最大串长度typedef unsigned char SStringMAXSTRLE

21、N+1/0号单元存放串的长度,串顺序存储的特点：连续存储单元静态分配串操作中的原操作一般为“字符序列的复制”截尾法处理串值序列的上越界,Status SubString(SString/SubString,串的顺序存储（二）,3.2 栈、队列和串的存储结构（续）,Status Concat(SString&T,SString S1,SString S2)/Concat,一般算法,3.3 串的模式匹配算法,int Index(SString S,SString T,int pos)/返回子串T在主串S中第pos个 i=pos;j=1;/字符之后的位置。若不存在，while(i T0)return

22、 i T0;else return 0;/Index算法时间复杂度：T(n)=O(n*m),逻辑函数为 Index(S,T,pos)S=a1a2aianT=t1t2tjtm 一般而言，mn算法思路：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，继续逐个比较后续字符，否则从主串的下一个字符起再重新和模式的字符比较之。,3.3 串的模式匹配算法（续）,第一趟 主串：a b a b c a b c a c b a b/i=3模式串：a b c/j=3,第二趟 主串：a b a b c a b c a c b a b/i=2模式串：a/j=1,第三趟 主串：a b a b c a b c

23、 a c b a b/i=7模式串：a b c a c/j=5,第四趟 主串：a b a b c a b c a c b a b/i=4模式串：a/j=1,第五趟 主串：a b a b c a b c a c b a b/i=5模式串：a/j=1,第六趟 主串：a b a b c a b c a c b a b/i=11模式串：a b c a c/j=6,模式串T=abcac,改进算法-思路,3.3 串的模式匹配算法（续）,KMP算法思路：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，继续逐个比较后续字符。当一趟匹配过程中出现字符比较不等时，不回朔i指针，而是利用已经得到的“部分

24、匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。优点：在匹配过程中，主串的跟踪指针不回朔 时间效率达到T(n)=O(n+m),如何理解“部分匹配”？主串：a c a b a a c a a b c a c模式串：a c a a b,改进算法-原理,3.3 串的模式匹配算法（续）,设主串S=s1s2sisn,模式串T=t1t2tjtm,在匹配过程中，当主串中第i个字符与模式串中第j个字符“失配”时（si不等于tj），将模式串“向右滑动”，让模式串中第k（kj）个字符与si对齐继续比较。这时有：t1t2tk-1=si-k+1si-k+2si-1-(1),而由部分匹配成功的结果可

25、知：t1t2tj-1=si-j+1si-j+2si-1-(2),由(2)式可以推知：tj-k+1tj-k+2tj-1=si-k+1si-k+2si-1-(3),由(1)式与(3)式可以推知：t1t2tk-1=tj-k+1tj-k+2tj-1-(4),令nextj=k，表示当模式串中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。根据其语义，定义如下：0当j=1时/相当于主串中i指针推进一个位置Nextj=Max k|1kj 且 t1t2tk-1=tj-k+1tj-k+2tj-1/1其他情况,改进算法-Next函数定义,3.3 串的模式匹配算法（续）,设主

26、串S=s1s2sisn,模式串T=t1t2tjtm,Next函数值仅取决于模式串本身的结构而与相匹配的主串无关,j 1 2 3 4 5 6 7 8 模式串 a b a a b c a cnextj 0 1 1 2 2 3 1 2,j 1 2 3 4 5 6 7 8 模式串 a b a a b c a cnextj,保证得到第一个“配串”,改进算法-匹配过程,3.3 串的模式匹配算法（续）,第一趟 主串：a c a b a a b a a b c a ca a b c/i=2模式串：a b/j=2,next2=1,第二趟 主串：a c a b a a b a a b c a ca a b c/i

27、=2模式串：a/j=1,next1=0,第三趟 主串：a c a b a a b a a b c a ca a b c/i=8模式串：a b a a b c/j=6,next6=3,第四趟 主串：a c a b a a b a a b c a ca a b c/i=14模式串：(a b)a a b c a c/j=9,j 1 2 3 4 5 6 7 8 模式串 a b a a b c a cnextj 0 1 1 2 2 3 1 2,int Index_KMP(SString S,SString T,int pos)/返回子串T在主串S中第pos个字符之后的位置。若不存在,函数值为0 i=po

28、s;j=1;while(i T0)return i T0;else return 0;/Index_KMP算法时间复杂度：T(n)=O(n+m),改进算法-KMP算法,3.3 串的模式匹配算法（续）,4.数组5.广义表6.树和二叉树7.图,第二部分 非线性数据结构,4.数组5.广义表6.树和二叉树7.图,教学内容-第六章,6.1树的逻辑结构,基本概念和术语,树：树T是n个结点的有限集。非空树中：（1）有且只有一个特定的称为根(Root)的结点；（2）当n1时，其余结点可分为m(m0)各互不相交 的有限集T1,T2,Tm,其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。树的结点

29、：一个数据元素和指向其子树的分支。结点的度：结点拥有的子树数。终端结点（或叶子）：度为0的结点。非终端结点（或分支结点、或内部结点）：度不为0的结点。树的度：树内各结点的度的最大值。（结点的）孩子：结点的子树的根。,6.1树的逻辑结构（续）,树的性质及树的表示,树的性质：递归性层次性,树的表示形式：树形表示集合嵌套表示广义表形式表示凹入表示,6.2树的存储结构（续）,孩子兄弟表示法（二叉链表）,/-树的二叉链表（孩子-兄弟）存储表示-typedef struct CSNodeElemTypedata;/树结点数据域struct CSNode*firstchild,*nextsibling;CS

30、Node,*CSTree;,6.3二叉树的逻辑结构,二叉树的描述性定义及其基本形态,二叉树：二叉树BT是n个结点的有限集。非空二叉树中：（1）有且只有一个特定的称为根(Root)的结点；（2）当n1时，其余结点可分为2个互不相交 的有限集BTL,BTR,BTL,BTR分别又是一棵二叉树，BTL称为根的左子树；BTR称为根的右子树。二叉树的基本形态：五种：空二叉树；仅有根结点的二叉树；右子树为空的二叉树；左、右子树均不为空的二叉树；左子树为空的二叉树。,6.3二叉树的逻辑结构（续）,二叉树的数学性质,性质1：在二叉树的第i层上至多右2i-1个结点(i=1);性质2：深度为k的二叉树至多有2k 1

31、个结点(k=1);性质3：二叉树T，若叶子结点数为n0,度为2的结点数为n2，则有n0=n2+1;,性质1：证明 i=1时，显然有2i-1=20=1；假设对于所有的j，1=ji，第j层上至多有2j-1 个结点，则当j=i时，由假设知2i-1 层上至多右2i-2,而二叉树的每个结点的度至多为2，故在第i层上 最大结点数为i-1层上最大结点数的2倍，即2*2i-2=2i-1。证毕,性质3：证明 n=n0+n1+n2 n=B+1 B=n1+2n2所以：n0=n2+1 证毕,性质4：证明 假设深度为k，由性质2以及完全二叉树定义有：2k-1 1 n=2k 1 推出 2k-1=n 2k k 1=以2为底

32、的n的对数 k 由于k是整数，所以结论成立。证毕,6.4二叉树的存储结构,顺序存储,具体做法：利用完全二叉树的性质，元素之间的关系隐含在元素的编号中，所以采用顺序存储后，完全二叉树中结点的存储位置为其编号所在的位置。对于一般二叉树，若采用顺序存储，须先增加虚结点以补成虚完全二叉树，对此虚完全二叉树的存储对应该二叉树的顺序存储。,/-二叉树的顺序存储表示-#define MAX_TREE_SIZE100typedefTElemTypeSqBiTreeMAX_TREE_SIZE;/0号单元存放根结点SqBiTree bt;,6.4二叉树的存储结构（续）,顺序存储,6.4二叉树的存储结构（续）,二叉

33、链表存储,/-二叉树的二叉链表存储表示-typedef struct BiTNodeTElemTypedata;/数据域struct BiTNode*lchild,*rchild;BiTNode,*BiTree;,6.4二叉树的存储结构（续）,三叉链表存储,/-二叉树的三叉链表存储表示-typedef struct BiTNodeTElemTypedata;/数据域struct BiTNode*lchild,*rchild，*parent;BiTNode,*BiTree;,6.4二叉树的存储结构（续）,（二叉）线索链表存储,/-二叉树的二叉线索链表存储表示-typedefenum Link,T

34、hread PointerTag;/Link=0;Thread=1typedef struct BiThrNodeTElemTypedata;/数据域struct BiThrNode*lchild,*rchild;/左、右孩子指针PointerTagLTag，Rtag;/左、右标志 BiThrNode,*BiThrTree;,6.4二叉树的存储结构（续）,（二叉）线索链表存储,6.5二叉树的遍历及线索化,遍历二叉树,在二叉树中查找具有某种特征的结点需要对结点进行访问（处理、输出等）操作二叉树上许多复杂操作的基础是对其遍历,遍历(Traversing)：按照某条路径访问每个结点,使得每个结点均被

35、访问一次，而且仅被访问一次。,遍历本质：结点之间非线性关系线性化的过程两种思路：*只要保证每个结点都被访问到一次；*遍历过程中易于实现关于结点的复杂操作,层次遍历法,递归遍历法：先序、中序、后序,6.5二叉树的遍历及线索化（续）,遍历二叉树的方法,先序遍历(PreOrderTraverse)：DLR;若二叉树为空，则空操作（递归基础）；否则：访问根结点；先序遍历左子树；先序遍历右子树。中序遍历(InOrderTraverse)：LDR;若二叉树为空，则空操作（递归基础）；否则：中序遍历左子树；访问根结点；中序遍历右子树。后序遍历(PostOrderTraverse)：LRD;若二叉树为空，则空

36、操作（递归基础）；否则：后序遍历左子树；中序遍历右子树；访问根结点。,层次遍历(LevelOrderTraverse)：从上到下，自左至右按照层次遍历。,层次遍历：A,B,I,C,D,J,K,E,F,G,H,先序遍历：A,B,C,D,E,F,G,H,I,J,K,中序遍历：C,B,E,D,G,F,H,A,J,I,K,后序遍历：C,E,G,H F,D,B,J,K,I,A,Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)/中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit if(T)if(InOrderTraverse(

37、T-lchild,Visit)if(Visit(T-data)if(InOrderTraverse(T-rchild,Visit)return OK;else return ERROR;/当访问失败时，出错 elsereturn OK;/一次递归访问终止 InOrderTraverse/算法时间复杂度：O(n),6.5二叉树的遍历及线索化（续）,中序遍历的算法,Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType e)/中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit InitStack(S);Push(S,T);/根

38、指针入栈 While(!StackEmpty(S)while(GetTop(S,p)InOrderTraverse/算法时间复杂度：O(n),Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType e)/中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit InitStack(S);p=T;While(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;/根指针入栈,遍历左子树else/根指针退栈，访问根结点，遍历右子树 Pop(S,p);if(!Visit(p-data)return ERR

39、OR/访问出错 p=p-rchild);/else/while return OK;InOrderTraverse/算法时间复杂度：O(n),6.5二叉树的遍历及线索化（续）,二叉树遍历的典型应用,已知二叉树的前序遍历序列和中序遍历序列，或者已知二叉树的后序遍历序列和中序遍历序列，可以唯一确定这棵二叉树。,Step1:判定根，由PostOrder知根为A；,Step2:判定左子树元素集合，由InOrder知为C B E D G F H,InOrder:C B E D G F H A J I KPostOrder:C E G H F D B J K I A,Step3:判定右子树元素集合，由In

40、Order知为J I K,Step4:分别对左、右子树元素集合按照中序和后序序列递归进行Step1-Step3，直到元素集合为空。,6.5二叉树的遍历及线索化（续）,线索二叉树,遍历本质是结点之间非线性关系线性化的过程遍历后的元素之间的某种线性关系一般隐藏在遍历规则下需要多次对同一棵树遍历时，如何提高效率？在二叉链表结构中增加线索域，显式描述遍历后的线索关系节省线索域空间，充分利用二叉链表中空的n+1个指针域线索链表：二叉树的存储结构，结点结构定义见前面。线索：指向结点前驱和后继的指针，叫做线索。线索二叉树：加上线索的二叉树。线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程。,线索二叉树

41、上遍历的过程，就是根据线索和遍历规则不断找当前结点后继结点的过程。,6.5二叉树的遍历及线索化（续）,线索二叉树上的中序遍历,InOrder:C B E D G F H A J I K,设当前结点指针为p，其前驱结点为q，后继结点指针为s,则有：,求结点p的后继：1.若 p-rtag=1 则 s=p-rchild;2.若p-rtag=0 s为p的右子树的中序遍历序列的第一个结点，即右子树最左下结点,求结点p的前驱：1.若 p-ltag=1 则 q=p-lchild;2.若p-rtag=0 q为p的左子树的中序遍历序列的第一个结点，即左子树最右下结点,6.6树、森林与二叉树的转换,森林与树相互递

42、归定义,森林：m棵互不相交的树的集合。树：树是一个二元组Tree=(root，F),root是根，F是m(m0)棵树的森林，F=T1,T2,Tm其中Ti=(ri，Fi)称为根的第i棵子树；当m!=0时，在树根和其子树森林之间存在下列关系：RF=|i=1,2,m,m0,6.6树、森林与二叉树的转换（续）,树与二叉树的转换,目的：利用二叉树运算来简化树和森林上的运算；依据：树与二叉树具有相同的二叉链表存储结构；,6.6树、森林与二叉树的转换（续）,6.6树、森林与二叉树的转换（续）,6.7二叉树的应用,哈夫曼树(Huffman Tree),结点之间路径长度：树中两个结点之间的分支构成这两个结点的路

43、径，路径上的分支数目为路径长度。树的路径长度：树根到每个结点的路径长度之和。结点的带权路径长度：该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和，记为：WPL=w1k1+w2k2+wiki+wnkn。最优二叉树（哈夫曼树）：设n个权值w1,w2,wn,构造一棵有n个叶子结点的二叉树，每个叶子结点带权wi,则其中带权路径长度WPL最小的二叉树称为最优二叉树（哈夫曼树）。,6.7二叉树的应用（续）,哈夫曼算法(Huffman Algorithmic),输入：n个权值w1,w2,wn；输出：一棵哈夫曼树算法：步骤一：根据给定的n个权值w1,w2,wn

44、构成n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树Ti 中只有一个带权为wi 的根结点，其左右子树均为空。步骤二：在F中选取两棵根结点的权值最小的树作为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。步骤三：在F中删除这两棵树，同时将新得到的二叉树加入F中。步骤四：重复步骤二与三，直到F只含有一棵树为止。,给定权的集合:15,3,14,2,6,9,16,17,6.7二叉树的应用（续）,哈夫曼算法(Huffman Algorithmic),15,3,14,2,6,9,16,17,15,5,14,6,9,16,17,15,11,14,9,16,17

45、,15,14,20,16,17,29,20,16,17,29,20,33,49,33,82,9,6,WPL=(2+3)*5+6*4+(9+14+15)*3+(16+17)*2=229,6.7二叉树的应用（续）,哈夫曼编码(Huffman Code),等长编码：每个被编码对象的码长相等。优点：码长等长，易于解码；缺点：被编码信息总码长较大，尤其是当存在 许多不常用的被编码对象时前缀编码：任一个被编码对象的编码都不是另一个 被编码对象的编码的前缀。优点：当存在被编码对象使用概率不同时，被 编码信息总码长可以减小；缺点：码长不等长，不易于解码,6.7二叉树的应用（续）,哈夫曼编码(Huffman C

46、ode)-前缀编码,利用二叉树来设计二进制的前缀编码：被编码对象出现在二叉树的叶子结点。约定左分支表示字符“0”，右分支表示字符“1”，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点对应对象的编码。,a(00)b(010)c(0110)d(0111)e(10)f(11),这种编码的译码过程从根开始。沿着某条分支走到叶子结点时，走过的二进制字符串即译为该叶子结点对应的对象。然后循环扫描总编码后的字符串。,6.7二叉树的应用（续）,哈夫曼编码与译码,利用哈夫曼算法可以得到总码长最短的二进制前缀编码，即为哈夫曼编码。设某次编码应用中不同被编码对象有n种，以此n种被编码对象出现的频

47、率作权，构造出的哈夫曼树即为这n种对象的编码树，由此可得到其二进制的前缀编码。,假定用于通讯的电文如下，现在要对其编码，采用哈夫曼编码。写出编码后的二进制串。电文：castcatssatatatasa,c(110)a(0)s(111)t(10),Set=c,a,s,tW=2,7,4,5,电文编码：11001111011001011111101001001001110,4.数组5.广义表6.树和二叉树7.图,教学内容-第七章,ADT Graph 数据对象：V=具有相同性质的数据元素数据关系：R:R=VRVR=|v,w属于V且P(v,w),是从v到w的一条弧，谓词P(v,w)定义了弧 的意义或信息

48、 基本操作：P:CreateGraph(BFSTraverseGraph(G,v,Visit()ADT Graph,7.1图的逻辑结构,图的抽象数据类型,7.1图的逻辑结构（续）,基本概念和术语,顶点(Vertex)、弧(Arc)、有向图(Digraph)、边(Edge)、无向图(Undigraph)、完全图(Completed graph)、有向完全图、稀疏图(Sparse graph)、权(Weight)、网(Network)、子图(Subgraph)、邻接点(Adjacent)、（顶点的）度(Degree)、（顶点的）入度(InDegree)、（顶点的）出度(OutDegree)、（顶点

49、之间）路径(Path)、（顶点之间）路径长度、回路或环(Cycle)、简单路径、简单回路（简单环）、（顶点之间）连通、连通图(Connected Graph)、连通分量(Connected Component)、强连通图、强连通分量、（连通图的）生成树：（有向图的）生成森林,7.2树的存储结构（续）,数组表示法,7.2图的存储结构（续）,邻接表-图的链式存储,基本思路：对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。每个表结点由三个域组成：邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置；链域(nextarc)指示下一条边或弧

50、的结点；数据域(info)存储和边或弧相关的信息。头结点由两个域组成：链域(firstarc)指向链表中第一个结点；数据域(data)存储顶点vi信息。头结点以顺序结构形式存取，以便随机访问任一顶点的链表。,7.2图的存储结构（续）,7.2图的存储结构（续）,邻接表-图的链式存储,邻接表的优点：边（或弧）稀疏时，节省空间；和边（或弧）相关的信息较多时，节省空间；容易求得当前顶点的第一个邻接点、下一个邻接点。,对有向图，也可建立逆向邻接表，即对每个顶点建立一个链接以该顶点为头的弧的表。,7.3图的遍历,遍历图,在图中查找具有某种特征的结点需要对结点进行访问（处理、输出等）操作图的遍历算法是求解图