《数据结构(C语言描述).ppt》由会员分享，可在线阅读，更多相关《数据结构(C语言描述).ppt（178页珍藏版）》请在金锄头文库上搜索。
1、1DS/SSDS/SS数据结构辅导李青山西安电子科技大学http:/202.117.118.45/faculty/029-8820-46112DS/SSDS/SS课程内容框架数 据 结 构基础数据结构应用数据结构栈队列线性表线性结构 非线性结构串查找内部排序外部排序文件动态存管理储数组广义表 树二叉树 图3DS/SSDS/SS基本概念1.2基本概念和术语数据、数据元素、数据项、数据对象结构*集合：松散的关系*线性结构：一对一的关系*树形结构：一对多的关系*网状结构：多对多的关系数据结构Data_Structure=（D，S）4DS/SSDS/SS数据结构的分类1.2基本概念和术语（续）逻辑结构
2、：数据元素之间的逻辑关系（本来的关系）存储结构：数据结构在计算机中的映象。包括数据元素的表示和关系的表示两个方面。分类：*顺序存储结构*链式存储结构描述方式：用高级语言中的“数据类型”来描述5DS/SSDS/SS算法1.3算法和算法分析内涵: 是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。特性:*有穷性：有穷步+有穷时间/每一步*确定性：指令的语义无二义性*可行性：算法能用基本操作完成*输入：零个或多个输入*输出：一个或多个输出6DS/SSDS/SS算法设计的要求1.3算法和算法分析（续）正确性（Correctness）可读性（Readablity）健壮性
3、（Robustness）高时间效率与低存储量需求7DS/SSDS/SS算法时间效率的度量1.3算法和算法分析（续）算法时间效率度量的基本做法在算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。一般而言，这个基本操作是最深层循环内的语句中的原操作。算法时间复杂度 T(n)=O (f(n) 称为算法的渐近时间复杂度，简称时间复杂度。8DS/SSDS/SS算法存储空间的度量1.3算法和算法分析（续）算法存储空间度量的基本做法用程序执行中需要的辅助空间的消耗作为存储空间度量的依据，是问题规模n的函数。而程序执行中本身需要的工作单元不能算。算法空间复杂度
4、S(n)=O (f(n) 称为算法的空间复杂度。9DS/SSDS/SS2.线性表3.栈、队列和串第一部分 线性数据结构10DS/SSDS/SS线性数据结构的特点2.1线性表的逻辑结构在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素；存在唯一的一个被称作“最后一个”的数据元素；除第一个之外，集合中的每一个数据元素均只有一个前驱；除最后一个之外，集合中每一个数据元素均只有一个后继。11DS/SSDS/SS基本概念和术语2.1线性表的逻辑结构（续）线性表：n个数据元素的有限序列（线性表中的数据元素在不同环境下具体含义可以不同，但在同一线性表中的元素性质必须相同）。表长：线性表中元素的
5、个数n(n=0)。空表：n=0时的线性表称为空表。位序：非空表中数据元素 ai 是此表的第 i 个元 素，则称 i 为 ai 在线性表中的位序。12DS/SSDS/SS线性表的抽象数据类型定义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) 操
6、作结果：用e返回L中第i个 数据元素的值 ADT ListLocateElem(L,e,compare() 初始条件：L存在； compare()是判定条件 操作结果：返回第1个与e满足关系compare()的 数据元素位序，若不存在，则返回0ListInsert(&L, i ,e) 初始条件：L存在；1=i=ListLength(L)+1 操作结果：第i个位置之前插入元素e，长度加1ListDelete(&L, i ,&e) 初始条件：L存在；非空；1=i=ListLength(L) 操作结果：删除第i个元素，e返回值，长度减1查找删除插入13DS/SSDS/SS顺序表-线性表的顺序存储2.
7、2线性表的顺序存储结构内涵： 线性表的顺序存储指用一组地址连续的存储单元依次存储线性表的数据元素。这称为顺序表。特点： * 存储单元地址连续（需要一段连续空间） * 逻辑上相邻的数据元素其物理位置也相邻 * 随机存取 * 存储密度为大（100%）14DS/SSDS/SS顺序表的随机存取2.2线性表的顺序存储结构（续） 对线性表L,设每个元素占k个存储单元，则有：递推关系： LOC(ai+1)=LOC(ai )+k任一元素ai+1的存储位置： LOC(ai)=LOC(a1 )+(i-1)*k (其中1= i next=p-next;p-next=s22DS/SSDS/SS单链表上删除运算的实现2
8、.3线性表的链式存储结构（续）删除q（a1， ai, ai+1, an) 表长为nListDelete(&L, i ,&e)（a1， ai-1, ai+1, an) 表长为n-1free(q)ai-1aiLai+1pp-next=p-next-nextai-1aiLai+1p23DS/SSDS/SS2.线性表3.栈、队列和串教学内容-第三章24DS/SSDS/SS栈、队列和串是特殊的线性表3.1 栈、队列和串的逻辑结构栈和队列是操作受限的线性表栈和队列的“操作受限”指操作位置受限串的特殊性在于线性表中数据元素只能是字符串一般以子串为操作单位栈、队列和串具有一般线性表共性的特点特殊的线性表反而应
9、用面更宽25DS/SSDS/SS栈的基本概念和术语3.1 栈、队列和串的逻辑结构（续）栈（Stack）：限定仅在表尾进行插入或删除操作的线性表。栈顶（top） ：插入或删除的表尾端。栈底（bottom） ：表头端。空栈：空表。栈的操作特点：后进先出（Last In First Out-LIFO）26DS/SSDS/SS栈的抽象数据类型定义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 栈顶基本操作：InitSta
10、ck(&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出栈（删除）入栈（插入）27DS/SSDS/SS队列的基本概念和术语3.1 栈、队列和串的逻辑结构（续）队列（Queue）：限定仅在表的一端进行插入，而另一端进行删除操作的线性表。队尾（
11、rear） ：允许插入的一端。队头（front）：允许删除的一端。空队：空表。队列操作特点：先进先出（First In First Out-FIFO）28DS/SSDS/SS队列的抽象数据类型定义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
12、,&e) 初始条件：Q存在,非空； 操作结果：用e返回Q的栈顶元素 EnQueue(&Q,e) 初始条件：Q存在 操作结果：插入元素e为新的队尾元素，长度加 1DelQueue (&S, &e) 初始条件：Q存在；非空 操作结果：删除Q的对头元素，e返回值，长度 减1ADT Queue出队（删除）入队（插入）29DS/SSDS/SS串的基本概念和术语3.1 栈、队列和串的逻辑结构（续）串（String）：由零个或多个字符组成的有限序列。S=a1a2an串名、串值串长空串、空格串子串：串中任意连续的字符组成的子序列主串：字符在串中的位置、子串在串中的位置串相等串的操作特点：一般以子串整体为单位3
13、0DS/SSDS/SS串的抽象数据类型定义3.1 栈、队列和串的逻辑结构（续）ADT Sring 数据对象：D=ai | ai属于CharacterSet, 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)StrInser
14、t(&S,pos,T) 初始条件：S存在,1=pos=StrLength(S)+1 操作结果：在串S的第pos个字符之前插入串TStrDelete(&S,pos,len) 初始条件：S存在,1=pos= S.stacksize) S.base = (SElemTupe *) realloc ( S.base,(S.stacksize +STACKINCERMENT) * sizeof (Selemtype);if (!S.base) exit (OVERFLOW); / 存储分配失败S.top = S.base + S.stacksize;S.stacksize =+ STACKINCERME
15、NT; *S.top+ = e; return OK; / Push入栈a1aia2basetopa1eaia2basetop顺序栈上的入栈3.2 栈、队列和串的存储结构（续）33DS/SSDS/SSStatus Pop(SqStack &S,SElemType &e) if(S.top = S.base) return error; e = * -S.top; return OK; / Pop出栈a1ai-1a2basetopa1aiai-1a2basetop顺序栈上的出栈3.2 栈、队列和串的存储结构（续）34DS/SSDS/SS栈的链式存储-链栈3.2 栈、队列和串的存储结构（续）bas
16、etoptypedef struct ElemTypedatastruct Lnode*next Lnode,* StackPtran-1a1antypedef struct StackPtr top StackPtr base LinkStack35DS/SSDS/SS链栈上的入栈与出栈3.2 栈、队列和串的存储结构（续）链栈上的入栈与出栈与单链表上元素插入删除操作类似插入删除位置都在栈顶处，不花费查找时间栈空的判断36DS/SSDS/SS队列的顺序存储-循环队列（一）3.2 栈、队列和串的存储结构（续）a1aia2front一般顺序存储的队列特点：队空条件：front = rear队满条件
17、：rear = MAXSIZE队满条件下的队满为假满（假溢出） （真满时：rear = MAXSIZE, front = 0）rear37DS/SSDS/SS/-动态分配-#define MAXSIZE 100 /最大队列长度typedef struct QElemType*baseintfront/指向队头元素当前位置intrear / 指向队尾元素下一个位置 SqQueue队列的顺序存储-循环队列（二)3.2 栈、队列和串的存储结构（续）38DS/SSDS/SS循环队列特点：队空条件：*front = rear（方式一）*标志域 + （front = rear） （方式二）队满条件：*(r
18、ear+1) % MAXSIZE = front （方式一）*标志域 + （front = rear） （方式二）队满条件下的队满为真满队列的顺序存储-循环队列（三)3.2 栈、队列和串的存储结构（续）39DS/SSDS/SS队列的顺序存储-循环队列（四)3.2 栈、队列和串的存储结构（续）Status EnQueue(SqQueue &Q,QElemType e) if(Q.rear+1) % MAXSIZE = = Q.front) return ERROR; Q.baseQ.rear = e; Q.rear = (Q.rear +1) % MAXSIZE; return OK; / En
19、QueueStatus InitQueue(SqQueue &Q) Q.base=(QElemType *)malloc(MAXSIZE * sizeof(QElemType); if (! Q.base) exit(overflow); Q.front = Q.rear = 0 ; return OK; / InitQueueStatus DeQueue(SqQueue &Q,QElemType &e) if(Q.rear= = Q.front) return ERROR; e = Q.baseQ.front; Q.front = (Q.front +1) % MAXSIZE; return
20、 OK; / DeQueue40DS/SSDS/SS队列的链式存储-链队列（一）3.2 栈、队列和串的存储结构（续）typedef struct QElemTypedatastruct QNode*next QNode,* QueuePtra2ana1typedef struct QueuePtr rear QueuePtr front LinkQueueq.rear.front41DS/SSDS/SSStatus EnQueue(LinkQueue &Q,QElemType e) p = (QueuePtr) malloc (sizeof (Qnode); if (!p) exit(over
21、flow); p-data = e;p-next = NULL; Q.rear-next = p;Q.rear = p; return OK; / EnQueueStatus InitQueue(LinkQueue &Q) Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (! Q.front) exit(overflow); Q.front-next = NULL ; return OK; / InitQueueStatus DeQueue(LinkQueue &Q,QElemType &e) if(Q.rear= = Q.front
22、) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = =p) Q.rear = Q.front; free(p); return OK; / DeQueue队列的链式存储-链队列（二）3.2 栈、队列和串的存储结构（续）42DS/SSDS/SS串的顺序存储（一）3.2 栈、队列和串的存储结构（续）/-串的定长顺序存储表示-#define MAXSTRLEN 255 /最大串长度typedef unsigned char SStringMAXSTRLEN+1/0号单元存放串的长度串顺序存
23、储的特点：连续存储单元静态分配串操作中的原操作一般为“字符序列的复制”截尾法处理串值序列的上越界43DS/SSDS/SSStatus SubString(SString &Sub,SString S, int pos, int len) if(pos S0 | len S0 pos +1) return ERROR; Sub1.len = Spos.pos+len-1; Sub0 =len; return OK; / SubString串的顺序存储（二）3.2 栈、队列和串的存储结构（续）Status Concat(SString &T,SString S1, SString S2) / Co
24、ncat44DS/SSDS/SS一般算法3.3 串的模式匹配算法int Index(SString S,SString T, int pos) /返回子串T在主串S中第pos个 i = pos;j = 1; /字符之后的位置。若不存在， while (i= s0 & j T0) return i T0; else return 0; / Index算法时间复杂度：T(n) = O(n*m)逻辑函数为 Index(S,T,pos)S = a1a2aianT = t1t2tjtm 一般而言，mn算法思路： 从主串S的第pos个字符起和模式的第一个字符比较之，若相等，继续逐个比较后续字符，否则从主串
25、的下一个字符起再重新和模式的字符比较之。45DS/SSDS/SS3.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 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
26、模式串： 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= abcac46DS/SSDS/SS改进算法-思路3.3 串的模式匹配算法（续）KMP算法思路： 从主串S的第pos个字符起和模式的第一个字符比较之，若相等，继续逐个比较后续字符。当一趟匹配过程中出现字符比较不等时，不回朔i指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。优点： 在匹配过程中，主串的跟踪指针不回朔 时间效率达到T(n) = O(n+m)如何理解“部分匹配”？主串： a c a
27、b a a c a a b c a c模式串： a c a a b 47DS/SSDS/SS改进算法-原理3.3 串的模式匹配算法（续）设主串S=s1s2sisn, 模式串T= t1t2tjtm 在匹配过程中，当主串中第i个字符与模式串中第j个字符“失配”时（si不等于tj），将模式串“向右滑动”，让模式串中第k（kj）个字符与si对齐继续比较。这时有： t1t2tk-1 = si-k+1si-k+2si-1 -(1)而由部分匹配成功的结果可知： t1t2tj-1 = si-j+1si-j+2si-1-(2)由(2)式可以推知： tj-k+1tj-k+2tj-1 = si-k+1si-k+2s
28、i-1 -(3)由(1)式与(3)式可以推知：t1t2tk-1 = tj-k+1tj-k+2tj-1 -(4) 48DS/SSDS/SS 令nextj = k，表示当模式串中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。根据其语义，定义如下： 0当j = 1时 /相当于主串中i指针推进一个位置Nextj = Max k | 1kj 且 t1t2tk-1 = tj-k+1tj-k+2tj-1 / 1其他情况改进算法-Next函数定义3.3 串的模式匹配算法（续）设主串S=s1s2sisn, 模式串T= t1t2tjtm Next函数值仅取决于模式串本身的
29、结构而与相匹配的主串无关 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保证得到第一个“配串”49DS/SSDS/SS改进算法-匹配过程3.3 串的模式匹配算法（续）第一趟 主串： a c a b a a b a a b c a c a a b c /i =2模式串： a b/j =2, next2=1第二趟 主串： a c a b a a b a a b c a c a a b c /i =2模式串： a/j =1, next1=0第三趟
30、 主串： a c a b a a b a a b c a c a 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 c a 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 250DS/SSDS/SSint Index_KMP(SString S,SString T, int pos) /返回子串T在主串S中第pos个字符之后的位置。若不存在,函数值为0
31、i = pos;j = 1; while (i= s0 & j T0) return i T0; else return 0; / Index_KMP算法时间复杂度：T(n) = O(n+m)改进算法-KMP算法3.3 串的模式匹配算法（续）51DS/SSDS/SS4.数组5.广义表6.树和二叉树7.图第二部分 非线性数据结构52DS/SSDS/SS4.数组5.广义表6.树和二叉树7.图教学内容-第六章53DS/SSDS/SS6.1树的逻辑结构基本概念和术语树：树T是n个结点的有限集。非空树中：（1）有且只有一个特定的称为根(Root)的结点；（2）当n1时，其余结点可分为m(m0)各互不相交
32、 的有限集T1,T2,Tm,其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。树的结点：一个数据元素和指向其子树的分支。结点的度：结点拥有的子树数。终端结点（或叶子）：度为0的结点。非终端结点（或分支结点、或内部结点） ：度不为0的结点。树的度：树内各结点的度的最大值。（结点的）孩子：结点的子树的根。54DS/SSDS/SS6.1树的逻辑结构（续）树的性质及树的表示树的性质：递归性层次性树的表示形式：树形表示集合嵌套表示广义表形式表示凹入表示55DS/SSDS/SSdatafirstchild nextsibling结点6.2树的存储结构（续）孩子兄弟表示法（二叉链表）/-树的
33、二叉链表（孩子-兄弟）存储表示-typedef struct CSNodeElemTypedata;/树结点数据域struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;56DS/SSDS/SS6.3二叉树的逻辑结构二叉树的描述性定义及其基本形态二叉树：二叉树BT是n个结点的有限集。非空二叉树中：（1）有且只有一个特定的称为根(Root)的结点； （2）当n1时，其余结点可分为2个互不相交 的有限集BTL,BTR, BTL,BTR分别又是一棵二叉树， BTL称为根的左子树； BTR称为根的右子树。 二叉树的基本形态：五种：空二叉树；仅有
34、根结点的二叉树；右子树为空的二叉树；左、右子树均不为空的二叉树；左子树为空的二叉树。57DS/SSDS/SS6.3二叉树的逻辑结构（续）二叉树的数学性质性质1：在二叉树的第i层上至多右2i-1个结点(i=1);性质2：深度为k的二叉树至多有2k 1个结点(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层上最大结点数
35、的2倍，即2* 2i-2 = 2i-1 。 证毕性质3：证明 n = n0 + n1 + n2 n = B+1 B = n1 + 2n2所以： n0 = n2 + 1 证毕性质4：具有n个结点的完全二叉树的深度为：以2为底的n的对数值取下整+1；性质5：n个结点的完全二叉树结点按照层序编号，则对任一结点i(1=i1，则其双亲是结点(i/2)取下整；(2)如果2in,则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点 2i；(3)如果如果2i+1n,则结点i无右孩子；否则其右孩子是结点 2i+1。满二叉树：深度为k且有2k 1个结点的二叉树;完全二叉树：深度为k，有n个结点的二叉树，当且仅
36、当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。性质4：证明 假设深度为k，由性质2以及完全二叉树定义有： 2k-1 1 n =2k 1 推出 2k-1 = n 2k k 1 = 以2为底的n的对数 lchild,Visit) if(Visit(T-data) if(InOrderTraverse(T-rchild,Visit)return OK; else return ERROR; /当访问失败时，出错 elsereturn OK; /一次递归访问终止 InOrderTraverse / 算法时间复杂度：O(n)6.5二叉树的遍历及线索化（续）中序遍历
37、的算法Status InOrderTraverse1(BiTree T, Status (* Visit) (TElemType e) /中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit InitStack(S); Push(S,T); /根指针入栈 While (!StackEmpty(S) while (GetTop(S,p) &p) Push (S,p-lchild); /向左走到尽头Pop(S,p)/空指针退栈if (! StackEmpty(S) /访问结点，向右一步 Pop(S,p);if (!Visit(p-data) return ERROR /访问出错 Push
38、(S,p-rchild); /if /while return OK; 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
39、(p-data) return ERROR /访问出错 p = p-rchild); /else /while return OK; InOrderTraverse / 算法时间复杂度：O(n)68DS/SSDS/SS6.5二叉树的遍历及线索化（续）二叉树遍历的典型应用 已知二叉树的前序遍历序列和中序遍历序列，或者已知二叉树的后序遍历序列和中序遍历序列，可以唯一确定这棵二叉树。EABCDFIJHGKStep1:判定根，由PostOrder知根为A；Step2:判定左子树元素集合，由InOrder知为C B E D G F H InOrder: C B E D G F H A J I KPost
40、Order: C E G H F D B J K I AStep3:判定右子树元素集合，由InOrder知为J I KStep4:分别对左、右子树元素集合按照中序和后序序列递归进行Step1-Step3，直到元素集合为空。69DS/SSDS/SS6.5二叉树的遍历及线索化（续）线索二叉树遍历本质是结点之间非线性关系线性化的过程遍历后的元素之间的某种线性关系一般隐藏在遍历规则下需要多次对同一棵树遍历时，如何提高效率？在二叉链表结构中增加线索域，显式描述遍历后的线索关系节省线索域空间，充分利用二叉链表中空的n+1个指针域线索链表：二叉树的存储结构，结点结构定义见前面。线索：指向结点前驱和后继的指针
41、，叫做线索。线索二叉树：加上线索的二叉树。线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程。 线索二叉树上遍历的过程，就是根据线索和遍历规则不断找当前结点后继结点的过程。70DS/SSDS/SS6.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的右子树的中序遍历序列的第一个结点，即右子树最左下结点EABCDFIJHGK求结点p的前驱：1.若 p-ltag =
42、 1 则 q = p-lchild;2.若p-rtag = 0 q为p的左子树的中序遍历序列的第一个结点，即左子树最右下结点71DS/SSDS/SS6.6树、森林与二叉树的转换森林与树相互递归定义森林：m棵互不相交的树的集合。树：树是一个二元组Tree = (root，F),root是根，F是m(m0)棵树的森林，F =T1,T2,Tm其中Ti = (ri，Fi) 称为根的第i棵子树；当m != 0时，在树根和其子树森林之间存在下列关系：RF = | i = 1,2,m, m0 72DS/SSDS/SS6.6树、森林与二叉树的转换（续）树与二叉树的转换目的：利用二叉树运算来简化树和森林上的运算
43、；依据：树与二叉树具有相同的二叉链表存储结构 ；EABCDFIABDECIF73DS/SSDS/SSEABCDFIJHGKABDECIFKJGH6.6树、森林与二叉树的转换（续）74DS/SSDS/SSEABCDFIJHGKEABCDFHGKIJ6.6树、森林与二叉树的转换（续）75DS/SSDS/SS6.7二叉树的应用哈夫曼树(Huffman Tree)结点之间路径长度：树中两个结点之间的分支构成这两个结点的路径，路径上的分支数目为路径长度。树的路径长度：树根到每个结点的路径长度之和。结点的带权路径长度：该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径
44、长度之和，记为：WPL = w1k1 + w2k2 + wiki + wnkn。最优二叉树（哈夫曼树）：设n个权值w1, w2, wn ,构造一棵有n个叶子结点的二叉树，每个叶子结点带权wi,则其中带权路径长度WPL最小的二叉树称为最优二叉树（哈夫曼树） 。76DS/SSDS/SS6.7二叉树的应用（续）哈夫曼算法(Huffman Algorithmic)输入： n个权值w1, w2, wn ；输出：一棵哈夫曼树算法：步骤一： 根据给定的n个权值w1, w2, wn 构成n棵二叉树的集合F =T1, T2 , Tn ，其中每棵二叉树Ti 中只有一个带权为wi 的根结点，其左右子树均为空。步骤二
45、：在F中选取两棵根结点的权值最小的树作为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。步骤三：在F中删除这两棵树，同时将新得到的二叉树加入F中。步骤四：重复步骤二与三，直到F只含有一棵树为止。77DS/SSDS/SS给定权的集合: 15,3,14,2,6,9,16,176.7二叉树的应用（续）哈夫曼算法(Huffman Algorithmic)15,3,14,2,6,9,16,1715,5,14,6,9,16,1715,11,14,9,16,1715,14,20,16,1729,20,16,1729,20,3349,3382949616178232
46、5141511202933WPL =(2+3)*5+6*4+(9+14+15)*3+(16+17)*2 = 22978DS/SSDS/SS6.7二叉树的应用（续）哈夫曼编码(Huffman Code)等长编码：每个被编码对象的码长相等。优点：码长等长，易于解码；缺点：被编码信息总码长较大，尤其是当存在 许多不常用的被编码对象时前缀编码：任一个被编码对象的编码都不是另一个 被编码对象的编码的前缀。优点：当存在被编码对象使用概率不同时，被 编码信息总码长可以减小；缺点：码长不等长，不易于解码79DS/SSDS/SS6.7二叉树的应用（续）哈夫曼编码(Huffman Code)-前缀编码 利用二叉树
47、来设计二进制的前缀编码： 被编码对象出现在二叉树的叶子结点。约定左分支表示字符“0”，右分支表示字符“1”，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点对应对象的编码。baedcf0000011111a(00)b(010)c(0110)d(0111)e(10)f(11) 这种编码的译码过程从根开始。沿着某条分支走到叶子结点时，走过的二进制字符串即译为该叶子结点对应的对象。然后循环扫描总编码后的字符串。80DS/SSDS/SS6.7二叉树的应用（续）哈夫曼编码与译码 利用哈夫曼算法可以得到总码长最短的二进制前缀编码，即为哈夫曼编码。 设某次编码应用中不同被编码对象有n种，以
48、此n种被编码对象出现的频率作权，构造出的哈夫曼树即为这n种对象的编码树，由此可得到其二进制的前缀编码。 假定用于通讯的电文如下，现在要对其编码，采用哈夫曼编码。写出编码后的二进制串。电文：castcatssatatatasac(110)a(0)s(111)t(10)Set = c,a,s,tW =2,7,4,5电文编码：11001111011001011111101001001001110518711642000111csat81DS/SSDS/SS4.数组5.广义表6.树和二叉树7.图教学内容-第七章82DS/SSDS/SSADT Graph 数据对象：V=具有相同性质的数据元素数据关系：R
49、: R=VRVR = | v,w属于V且P(v,w), 是从v到w的一条弧，谓词P(v,w)定义了弧 的意义或信息 基本操作：P: CreateGraph(&G,V,VR); DFSTraverseGraph(G,v,Visit(); ; BFSTraverseGraph(G,v,Visit() ADT Graph7.1图的逻辑结构图的抽象数据类型83DS/SSDS/SS7.1图的逻辑结构（续）基本概念和术语 顶点(Vertex)、弧(Arc)、有向图(Digraph)、边(Edge)、无向图(Undigraph)、完全图(Completed graph)、有向完全图、稀疏图(Sparse g
50、raph)、权(Weight)、网(Network)、子图(Subgraph)、邻接点(Adjacent)、（顶点的）度(Degree)、 （顶点的）入度(InDegree)、（顶点的）出度(OutDegree)、（顶点之间）路径(Path)、（顶点之间）路径长度、回路或环(Cycle)、简单路径、简单回路（简单环）、 （顶点之间）连通、连通图(Connected Graph)、连通分量(Connected Component)、强连通图、强连通分量、（连通图的）生成树：（有向图的）生成森林84DS/SSDS/SS 0 1 0 1 0 1 0 1 0 1 G1.arcs = 0 1 0 1 1
51、 1 0 1 0 0 0 1 1 0 0 7.2树的存储结构（续）数组表示法V3V1V2V5V4G1V1V2V4V3G2 0 1 1 0 0 0 0 0G2.arcs = 1 0 0 1 1 1 1 085DS/SSDS/SS7.2图的存储结构（续）邻接表-图的链式存储基本思路： 对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。每个表结点由三个域组成：邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置；链域(nextarc)指示下一条边或弧的结点；数据域(info)存储和边或弧相关的信息。头结点由两个域组成：链域(firstar
52、c)指向链表中第一个结点；数据域(data)存储顶点vi信息。 头结点以顺序结构形式存取，以便随机访问任一顶点的链表。Adjvexnextarcinfodatafirstarc表结点头结点86DS/SSDS/SS7.2图的存储结构（续）V10V21V32V43V54212042031431V3V1V2V5V4G1V1V2V4V3G2V10V32V21V433003230V10V21V32V43302212087DS/SSDS/SS7.2图的存储结构（续）邻接表-图的链式存储邻接表的优点：边（或弧）稀疏时，节省空间；和边（或弧）相关的信息较多时，节省空间； 容易求得当前顶点的第一个邻接点、下一个
53、邻接点。 对有向图，也可建立逆向邻接表，即对每个顶点建立一个链接以该顶点为头的弧的表。88DS/SSDS/SS7.3图的遍历遍历图在图中查找具有某种特征的结点需要对结点进行访问（处理、输出等）操作图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础 图的遍历(Traversing Graph)：从图的某一个顶点出发，按照某条路径访问每个结点,使得每个结点均被访问一次，而且仅被访问一次。遍历本质：结点之间非线性关系线性化的过程遍历思路： *深度优先：类似于树的先根遍历； *广度优先：类似于树的层次遍历。89DS/SSDS/SS7.3图的遍历（续）深度优先搜索遍历思路： 从图的某个顶
54、点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。 这是一个递归算法，遍历过程中，当某个顶点的所有邻接点都被访问到后，需要“回朔”，即沿着调用的逆方向回退到上一层顶点，继续考察该顶点的下一个邻接点。Boolean visitedMAX;/访问标志数组Status (*VisitFunc) (int v);/函数变量Void DFSTraverse(Graph G,Status (*Visit)(int v) Visi
55、tFunc = Visit； /使用全局变量VisitFunc，使DFS不必设函数指针参数 for (v =0; vG.vexnum; +v) visitedv = FALSE; /标志数组初始化 for (v =0; vG.vexnum; +v) if (!visitedv) DFS(G,v); Status DFS (Graph G, int v) /从第v个顶点出发递归地深度优先遍历图G，对每个元素调用函数Visit visitedv = TRUE;VisitFunc(v); /访问第v个顶点 for ( w =FirstAdjVex(G,v); w; w =NextAdjVex(G,v
56、,w)if (!visitedw) DFS(G,w); / 算法时间复杂度与存储结构相关邻接矩阵存储:T(n)=O(n2);邻接表存储:T(n)=O(n+e)90DS/SSDS/SS7.3图的遍历（续）深度优先搜索V12V9V10V11V1G3V3V6V2V8V5V4V7一种DFS遍历序列： V1 , V2 , V4 , V8 , V5 , V3 , V6 , V7 , V9 , V10 , V12 , V11 当存储结构和算法确定后，遍历序列唯一。91DS/SSDS/SS7.3图的遍历（续）广度优先搜索遍历思路： 从图的某个顶点v出发，访问此顶点，然后依次访问v的未被访问的邻接点，然后从这些
57、邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。 一层层遍历。如何保证上层次序先于下层次序？保证“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问？可以通过队列来控制实现。Boolean visitedMAX;/访问标志数组Void BFSTraverse(Graph G,Status (*Visit)(int v) for (v =0; vG.vexnum; +v) vi
58、sitedv = FALSE; /标志数组初始化 InitQueue(Q);/置空的辅助队列 for (v =0; vG.vexnum; +v) if (!visitedv) visitedv = TRUE;Visit (v); EnQueue(Q,u); While(!QueueEmpty(Q) DeQueue(Q,u); for ( w =FirstAdjVex(G,u); w; w =NextAdjVex(G,u,w) if (!visitedw) Visitedw =TRUE; Visit(w); Enqueue(Q,w); /while if / 算法时间复杂度与存储结构相关邻接矩阵
59、存储:T(n)=O(n2);邻接表存储:T(n)=O(n+e)92DS/SSDS/SS7.3图的遍历（续）广度优先搜索V12V9V10V11V1G3V3V6V2V8V5V4V7一种BFS遍历序列： V1 , V2 , V3 , V4 , V5 , V6 , V7 , V8 , V9 , V10 , V12 , V11 当存储结构和算法确定后，遍历序列唯一。93DS/SSDS/SS7.4图的应用无向图的连通分量无向图的生成树连通网的最小生成树有向无环图的拓扑排序有向无环图的关键路径有向网的最短路径典型应用94DS/SSDS/SS7.4图的应用（续）无向图的连通分量思路：利用遍历图的算法求解无向图
60、的连通性。方法：利用图的遍历（DFS与BFS均可）算法，对连通图，从任一定点出发遍历，可访问到所有顶点；对非连通图，需从多个顶点出发进行遍历，每一次从一个新的起始点出发遍历得到的顶点序列恰为其各个连通分量中的顶点集。最终求得一个无向图的所有连通分量。95DS/SSDS/SS7.4图的应用（续）无向图的生成树思路： 利用遍历图的算法求解无向连通图的生成树和无向非连通图的生成森林。方法： 对连通图G，设E(G)为连通图G中所有边的集合，则从图中任一顶点出发遍历图时，必将E(G)分为两个集合T(G)和B(G)，其中T(G)是遍历图过程中历经边的集合；B(G)是剩余边的集合。T(G)和图G中所有顶点一
61、起构成连通图G的极小连通子图，它是连通图的一棵生成树。根据遍历方法，生成树分为DFS生成树和BFS生成树。 对无向非连通图，每个连通分量对应一个生成树，形成生成森林。V12V9V10V11V1G3V3V6V2V8V5V4V796DS/SSDS/SSV12V9V10V11V1G3V3V6V2V8V5V4V77.4图的应用（续）无向图的生成树97DS/SSDS/SS7.4图的应用（续）连通网的最小生成树问题： 用连通网表示的网络上如何构造代价最小的通信网。 对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都是一个通信网。一个生成树的代价就是树上各边的代价之和，表示着通信网上总通信耗费量。
62、使通信网上总通信耗费量最小的问题就是求解最小生成树的问题，即如何构造连通网的最小代价生成树 思路： 利用最小生成树的MST性质。方法： *普里姆(prim)算法； *克鲁斯卡尔(kruskal)算法。最小生成树的MST性质： 假设N = (V,E)是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中u属于U,v属于V-U，则必存在一棵包含边(u,v)的最小生成树。证明: （反证法） 假设N = (V,E)的任何一棵最小生成树都不含边(u,v) 。设T是连通网上的一棵最小树，当将边(u,v) 加入到T中时，由生成树的定义，T中必存在一条包含(u,v) 的回路
63、。另一方面，由于T是生成树，则在T上必存在另一条边(u,v) ，其中u属于U,v属于V-U，且u和u，v和v之间均有路径相通。删去边(u,v)，便可消除上述回路，同时得到另一棵生成树T。因为(u,v)的代价不高于(u,v)，则T的代价亦不高于T，T是一棵包含(u,v)的最小生成树。矛盾! 98DS/SSDS/SS7.4图的应用（续）连通网的最小生成树-prim算法输入：连通网N = (V, E)，最小生成树边的集合TE =空集输出：一棵最小生成树T = (V, TE)步骤： step1.初始：U =u0(u0属于V),TE = ； step2.在所有u属于U，v属于V U的边(u,v)中找一条
64、代价最小的 边(u0, v0 )并入集合TE，同时v0 并入U； step3.重复step2，直至 U = V为止 最后TE中有n-1条边， T = (V, TE)即为N的一棵最小生成树。效率： T(n) = O(n2)，与e无关（其中n为网中结点个数， e为边的个数）99DS/SSDS/SS7.4图的应用（续）连通网的最小生成树-prim算法V16V4V6V2V5V3635515642U =v1 , V-U=v2, v3, v4, v5, v6, TE= U =v1, v3 , V-U=v2, v4, v5, v6, TE= (v1, v3)U =v1, v3 ,v6 , V-U=v2, v
65、4, v5, TE= (v1, v3 ), (v3, v6 ) U =v1, v3 ,v6 , v4 , V-U=v2, v5, TE= (v1, v3 ), (v3, v6 ) , (v4, v6 ) U =v1, v3 ,v6 , v4 , v2 , V-U=v5, TE= (v1, v3 ), (v3, v6 ) , (v4, v6 ) , (v2, v3 ) U =v1, v3 ,v6 , v4 , v2 , v5 , V-U=, TE = (v1, v3 ),(v3, v6 ),(v4, v6 ),(v2, v3 ),(v2, v5 ) 100DS/SSDS/SS7.4图的应用（续）
66、连通网的最小生成树-kruskal算法输入：连通网N = (V, E)，最小生成树边的集合TE =空集输出：一棵最小生成树T = (V, TE)步骤： step1.初始：只有n个顶点而无边的非连通图T = (V,TE=)； step2.在E中选择代价最小的边，若该边依附的顶点落在T中不同 的连通分量上，则将此边加入到T的TE集合中，否则舍去此 边而选择下一条代价最小的边； step3.重复step2，直至 T中所有顶点都在同一个连通分量上为止 效率： T(n) = O(eloge)，与n无关（其中n为网中结点个数， e为边的个数）101DS/SSDS/SS7.4图的应用（续）连通网的最小生成树
67、-kruskal算法V16V4V6V2V5V3635515642V =v1,v2, v3, v4, v5, v6, TE= V =v1,v2, v3, v4, v5, v6, TE= (v1, v3)V =v1,v2, v3, v4, v5, v6, TE= (v1, v3 ), (v4, v6 ) V =v1,v2, v3, v4, v5, v6, TE= (v1, v3 ), (v4, v6 ) , (v2, v5 ) V =v1,v2, v3, v4, v5, v6, TE= (v1, v3 ), (v4, v6 ) , (v2, v5 ) , (v3, v6 ) V =v1,v2, v
68、3, v4, v5, v6,TE = (v1, v3 ),(v3, v6 ),(v4, v6 ),(v2, v3 ),(v2, v5 ) 102DS/SSDS/SS7.4图的应用（续）有向无环图(DAG)：一个无环的有向图。其作用：*描述含有公共子式的表达式*描述一项工程或系统的进行过程#工程能否顺利进行；#工程完成所必需的最短时间拓扑排序(Topological Sort) ：由某个集合上的一个偏序得到该集合上的一个全序的操作。这个全序称为拓扑有序(Topological Order)。AOV-网：用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的图(Activity On
69、Vertex Network)。AOE-网：顶点表示事件，弧表示活动，权表示活动持续时间的带权有向无环图称为边表示活动的网(Activity On Edge )有向无环图中基本概念103DS/SSDS/SS7.4图的应用（续） 为了工程能进行，其对应的AOV-网中不应该存在环。检测的办法有：*DFS遍历：从有向图某个顶点v出发，在遍历结束之前如果出现从顶点u到顶点v的回边，由于u在生成树上是v的子孙，则有向图中必定存在包含顶点v和u的环。*拓扑排序：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV-网中必定不存在环。有向无环图的拓扑排序104DS/SSDS/S
70、S7.4图的应用（续）有向无环图的拓扑排序算法输入：AOV-网输出：包含全部顶点的一个拓扑序列或者部分顶点的序列（存在环）步骤： step1.在图中选取一个没有前驱的顶点且输出之； step2.在图中删除该顶点和所有以它为尾的弧； step3.重复step1、step2，直至 全部顶点均已输出，或者当前图中不存在无前驱的顶点为止（存在环）。 逻辑上：拓扑序列不唯一；物理上：拓扑序列唯一105DS/SSDS/SS7.4图的应用（续）有向无环图的拓扑排序算法V1V2V3V4V5V6V10V32V21V4341214V54V65334V1V2V3V4V5V3V4V5V2V3V5V2V2V5V2020
71、124351032 120011 00106DS/SSDS/SS7.4图的应用（续）有向无环图的关键路径AOE-网描述工程，有两个问题需要解决：*完成整项工程至少需要多少时间？*那些活动是影响工程进度的关键？V1V2V3V4V5V6a4=3a1=3a8=1a3=2a2=2a5=4a6=3a7=2 8个活动、6个事件的AOE-网， v1 表示整个工程开始， v6 表示整个工程结束。事件v4 表示活动a3 和a5 已经完成， 活动a7 可以开始107DS/SSDS/SS源点：唯一的一个入度为零的点汇点：唯一的一个出度为零的点关键路径：路径长度（路径上各活动持续时间之和）最长的路径。这也是完成工程所
72、需要的最短时间。事件vi 最早发生时间ve(i)：从源点到vi的最长路径长度。活动ai的最早开始时间e(i) :为活动ai ()弧的弧尾事件ve(j)事件vi 最迟发生时间vl(i)：不推迟整个工程完成的前提下事件vi必须开始的时间。活动ai的最迟开始时间l(i) :不推迟整个工程完成的前提下活动ai必须进行的时间。关键活动： l(i) = e(i) 的活动称为关键活动。关键路径上的所有活动都是关键活动。要求工程最少需要完成时间、要加快工程进度，只能考察和改进关键活动，它们是影响工程进度的关键。7.4图的应用（续）108DS/SSDS/SS7.4图的应用（续）有向无环图的关键路径算法思路：1.
73、求出AOE-网中的关键活动，即求出l(i) = e(i) 的活动ai () 。2.对活动ai ()，其持续时间为dut()，则有： （1）e(i) = ve(j); （2）l(i) = vl(k) dut()3. （1）从ve(0) =0开始向前递推：ve(j) = Max(i) ve(i) + dut() 属于T, j =1,2,n-1；T是所有以第j个顶点为头的弧的集合 （2）从vl(n-1) = ve(n-1) 开始向后递推：vl(i) = Min(j) vl(j) - dut() 属于S, i =n-2,0；S是所有以第i个顶点为尾的弧的集合输入：AOE-网输出：求出所有关键活动，进而
74、求出所有关键路径步骤： step1.输入e条弧，建立AOE-网的存储结构； step2.从源点v0 出发，令ve0=0,按拓扑有序求其余各顶点的最早发生时间vei(1=i=i=2)； step4.根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足e(s)=l(s)，则为关键活动。 109DS/SSDS/SSV1V2V3V4V5V6a4=3a1=3a8=1a3=2a2=2a5=4a6=3a7=27.4图的应用（续）有向无环图的关键路径示例顶点vevlv100v234v322v466v567v688活动ell-ea1011a2000a3341a4341a
75、5220a6253a7660a8671V1V3V4V6a2=2a5=4a7=2*关键活动的改进可以改进工程进度；*关键活动速度提高要有限度,前提是不能改变关键路径*若网中有多条关键路径，要改进工程进度，必须同时 提高几条关键路径上的关键活动的速度。110DS/SSDS/SS7.4图的应用（续）带权有向图的最短路径源点：路径上的第一个顶点汇点：路径上的最后一个顶点最短路径：*从源点到终点所含边的数目最少的路径。（用BFS边历方法可以求得）*从源点到终点路径上边的权值之和最小的路径。（用Dijkstra算法和Floyd算法可以求得）从某个源点到其余各顶点的最短路径（设源点为v0，终点可以是v1 ,
76、v2 , vn ，则可以求得n条最短路径）每一对顶点之间的最短路径（源点可以为v1 ,v2 , vn ，终点也可以是v1 ,v2 , vn ，源点与终点不能相等，可以求得n(n-1)条最短路径）111DS/SSDS/SSV1V5V2V3V0V410100530102050607.4图的应用（续）某个源点到其余各顶点的最短路径源点终点最短路径路径长度v0v1无v0v2(v0 , v2 )10v0v3(v0 , v4 , v3 )50v0v4(v0 , v4 )30v0v5(v0 , v4 , v3 , v5 )60112DS/SSDS/SS7.4图的应用（续）最短路径算法思路：1.Dijkstr
77、a: 按路径长度递增的次序产生最短路径 。2.用向量Di表示当前所找到的从源点v到每个终点vi 的最短路径的长度。它的初态为：若从v到vi 有弧，则Di为弧上权值；否则为无穷大。这时，长度为Dj = Min(i)Di | vi 属于V的路径就是从v出发的长度最短的一条最短路径。设为(v, vj)。3. 设S为已求得最短路径的终点的集合，则下一条最短路径（设其终点为x）或者是弧(v, x )，或者是中间只经过S中的顶点而最后到达顶点x的路径。即下一条长度次短的最短路径的长度为Dj = Min(i)Di | vi 属于V-S，其中，Di或者是弧(v, vi ) 上的权值，或者是Dk (vi 属于S
78、)和弧(vi, vk )上的权值之和。输入：带权有向图输出：n条最短路径步骤： step1.从源点v出发到图上其余各顶点（终点）vi 可能达到的最短路径长度的初值为：若从v到vi 有弧，Di为弧上权值；否则为无穷大； step2.选择vj ，使得Dj = Min(i)Di | vi 属于V-S， vj 就是当前求得的一条从v出发的最短路径的终点。令S = S U j ； step3.修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。如果Dj +arcsjkDk，则修改Dk =Dj +arcsjk； step4.重复操作step2、step3共n-1次。由此求得从v到图上其余各顶点的最短
79、路径是依路径长度递增的序列。 113DS/SSDS/SS7.4图的应用（续）终点从v0 到各终点的D值和最短路径的求解过程i=1i=2i=3i=4i=5v1无穷大无穷大无穷大无穷大无穷大(无)v210 (v0 , v2 )v3无穷大60 (v0 , v2 , v3 )50 (v0 , v4 , v3 )v430 (v0 , v4 )30 (v0 , v4 )v5100 (v0 , v5 )100 (v0 , v5 )90 (v0 , v4 , v5 )60(v0 , v4 , v3 , v5)vjv2v4v3v5Sv0 , v2 v0 , v2 , v4 v0 , v2 , v3 , v4 v
80、0 , v2 , v3 , v4 , v510 (v0 , v2 )30 (v0 , v4 )50 (v0 , v4 , v3 )60(v0 , v4 , v3 , v5)V1V5V2V3V0V41010053010205060114DS/SSDS/SS7.4图的应用（续）每一对顶点之间的最短路径两种方法：*每次以一个顶点为源点，重复执行Dijkstra算法n次，便 可求得每一对顶点之间最短路径。T(n) = O(n3)*Floyd算法。 T(n) = O(n3)115DS/SSDS/SS第三部分 应用数据结构8.动态存储管理9.查找10.内部排序11.外部排序12.文件116DS/SSDS/
81、SS教学内容-第九章8.动态存储管理9.查找10.内部排序11.外部排序12.文件117DS/SSDS/SS9.1查找的概念和思路 查找表(Search Table)、静态查找表(Static Search Table)、动态查找表(Dynamic Search Table)、查找(Searching)、关键字(Key)、主关键字(Primary Key)、次关键字(Secondary Key)、查找成功(Searching Success)、查找不成功(Searching Failed)、查找成功时平均查找长度： 查找不成功平均查找长度、平均查找长度(Average Search Lengt
82、h)：基本概念和术语118DS/SSDS/SS查找表中元素关系松散，直接在原始查找表中查找的效率很低。查找一般思路：向查找表上依附其他数据结构，使查找表中数据元素之间关系约束增加，从而利于查找过程的进行。根据依附的数据结构不同，可以有不同的查找过程、查找特点和查找性能。依附数据结构的选择取决于问题域特点和查找表本身特性。9.1查找的概念和思路（续）基本思路119DS/SSDS/SS9.2静态查找表顺序表的查找顺序表查找=查找表+线性表+顺序存储线性链表查找=查找表+线性表+链式存储；/-静态查找表存储表示- typedef struct ElemType*elem;/0号单元留空 intlen
83、gth;SSTable;顺序查找120DS/SSDS/SSint Search_Seq(SSTable ST, KeyType key ) /若找到，含数值为该元素在表中的位置，否则为0 ST.elem0.key = key;/ “哨兵” for (i =ST.length; !EQ(ST.elemi.key, key); -i ); /从后往前找 return i ;/找不到，i为0（这也是哨兵的作用所在） Search_Seq顺序查找(Sequential Search)过程： 从表中最后一个元素开始，逐个进行元素的关键字和给定值的比较，若某个元素的关键字和给定值相等，则查找成功，找到所查
84、元素；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查元素，查找不成功 。9.2静态查找表（续）顺序表的查找性能分析:n = ST.length; Pi = 1/n， qi = 1/n （假设的前提）ASLss成功 = nP1+(n-1)P2+2Pn-1+Pn =(n+1)/2ASLss不成功 = （n+1）(q1+q2+qn-1+qn )=n+1顺序查找的优点：*算法简单、适用面广；*对线性关系没有其他要求；*对存储结构没有要求顺序查找的缺点：*平均查找长度大；121DS/SSDS/SS9.2静态查找表（续）有序表的查找有序表查找=查找表+线性表+有序性+顺序存储/-静
85、态查找表存储表示- typedef struct ElemType*elem;/0号单元留空 intlength;SSTable;四种查找方法：*折半查找*顺序查找*斐波那契查找*插值查找122DS/SSDS/SS折半查找(Binary Search)过程： 先确定待查元素所在范围（区间），然后逐步缩小范围直到找到或找不到该元素为止 。具体而言，折半查找是以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，若不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或者查找区间的大小小于零时（表明查找不成功）为止。9.2静态查找表（续）有序表的折半查找int Search_Bin
86、(SSTable ST, KeyType key ) /若找到，含数值为该元素在表中的位置，否则为0 low =1;high = ST.length;/置区间初值 while (low data.key) p =T; return TRUE; /查找成功 else if LT(key,T-data.key) SearchBST(T-lchild, key, T, p); /在左子树查找 else SearchBST(T-rchild, key, T, p);/在右子树中继续查找 /SearchBST BST树上的查找为动态查找，在查找失败时，要在失败的位置插入关键字为待查关键字的数据元素。 查
87、找失败的位置在叶子处，插入位置也在叶子位置，当采用二叉链表存储BST树时，插入新元素时不需要移动其他元素，仅需修改指针即可。32131DS/SSDS/SS9.3动态查找表（续）40358201053023 BST树上建树的过程，就是查找失败时元素不断插入的过程。 初始序列中元素的次序直接决定了BST树的结构。初始序列：20 10 30 23 5 8 35 40空树202010302010233020105233020108201053023358201053023132DS/SSDS/SS9.3动态查找表（续）二叉排序树上结点删除设BST树上被删除结点指针为p，其左、右子树分别表示为PL和PR
88、，其双亲结点指针为f,不失一般性，设*p为*f的左孩子。则有：1.若*p为叶子结点，直接删除;2.若*p只有左子树PL或者只有右子树PR,删除*p后令PL或PR直接成为其双亲结点*f的左子树即可;3.若*p左子树PL和右子树PR均不为空。有两种做法：其一是令*p的左子树为*f的左子树，而*p的右子树为*p中序序列直接前驱*s的右子树；其二是令*p中序序列直接前驱*s替代*p，然后令*s的左子树为*s的双亲*q的右子树。SFCPQCLPRQLSLSFCCLPRSLCLFCSQPRQLSLPL133DS/SSDS/SS9.3动态查找表（续）二叉排序树查找性能分析 BST查找过程中，找到中任何一个元
89、素的过程就是走了一条根结点到与该元素相应的结点的路径，和给定值比较的关键字个数恰为该结点在BST树上的层次数。查找不成功的过程就是走了一条根结点到外部结点的路径，和给定值进行比较的关键字个数等于该路径上内部结点的个数。BST树上查找成功和查找不成功的ASL与BST树的结构有关，而树的结构与初始序列构造有关。即含有n个结点的二叉排序树不唯一。效率最高的情况为BST为一棵平衡二叉树的时候。ASLbst成功 =(1*1+2*2+3*3+4*2)/8=11/48201053023403530-3510-205-88-1040ASLbst不成功 =(1*2+3*4+4*4)/9=10/3134DS/SS
90、DS/SS 由初始序列建立BST树的过程中若因为插入一个结点而导致了当前树不平衡，则应该调整其平衡。这个过程即是BST树初始平衡化过程。在查找过程中，如查找失败，当在失败位置处插入失败元素而引起树的不平衡，也应该调整其平衡。这就是BST平衡化。假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a（即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点），则失去平衡后进行调整有四中情况：1.单向右旋转(LL)：由于在*a的左子树根结点的左子树上插入结点而导致以*a为根的子树失去平衡，则需进行向右一次顺时针旋转操作;2.单向左旋转(RR)：由于在*a的右子树根结点的右子树上插入结点而
91、导致以*a为根的子树失去平衡，则需进行向左一次逆时针旋转操作;3.双向先左后右旋转(LR)：由于在*a的左子树根结点的右子树上插入结点而导致以*a为根的子树失去平衡，则需进行先左旋转后右旋转两次操作;4.双向先右后左旋转(RL)：由于在*a的右子树根结点的左子树上插入结点而导致以*a为根的子树失去平衡，则需进行先右旋转后左旋转两次操作。9.3动态查找表（续）BST树平衡化过程135DS/SSDS/SS初始序列：6 2 1 4 5 3 762152614aLL型aLR型6251437aRL型216534a5217634RR型136DS/SSDS/SS9.3动态查找表（续）哈希表查找哈希表查找=查
92、找表+顺序表+Hash规则基本思想： 在线性表和树结构中，元素在结构中的相对位置是随机的，和元素的关键字之间不存在确定的关系，在这些结构作用下的查找表中查找时需要进行一系列的和关键字的比较（包括“相等”、“不相等”、“大于”、“小于”、“等于”比较)。 哈希表查找的思路是希望不通过比较，一次存取便能得到所查元素。显然，前提是每个关键字和结构中一个唯一的存储位置相对应。这种对应关系为查找提供依据和线索。137DS/SSDS/SS哈希函数(Hash Function)：由关键字到元素存储位置之间的对应关系H称为哈希表函数。它是一个映象，设置灵活，只要使得关键字由此所得的哈希函数值都落在表长允许范围
93、内即可。H: Key - Address；key的哈希函数值记H(key)。冲突(collision)：对不同关键字可能得到同一哈希地址的现象，即key1 != key2，而H(key1)=H(key2)。具有相同函数值的关键字对该哈希函数来说称作同义词(synonym)。哈希表(Hash Table):根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上并以关键字在地址集中的“象”作为元素在表中的存储位置，这种表称为哈希表。这种映象过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址。9.3动态查找表（续）哈希表中基本概念和术语138DS/S
94、SDS/SS直接定址法：数字分析法：平方取中法:折叠法:随机数法:除留余数法：取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即：H(key) = key MOD p p=m 可以对关键字直接取模，也可以在折叠、平方取中等运算后取模。 一般情况下，p取质数或不包含小于20的质因素的合数。9.3动态查找表（续）哈希函数构造方法构造和选取哈希函数的原则：均匀性(Uniform)。若对于关键字集合中的任一个关键字，经哈希函数映象到地址集合中任何一个地址的概率是相等的，则称此类哈希函数为均匀的哈希函数。这种均匀性可以使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。实际中选取
95、哈希函数要考虑的因素包括：*计算哈希函数所需要时间；*关键字长度；*哈系表大小；*关键字分布情况*记录的查找频率139DS/SSDS/SS9.3动态查找表（续）处理冲突的方法 假设哈希表地址集为：0(m-1)，冲突是指由关键字得到的哈希地址为j(0=j=m-1)的位置上已存有记录，则“处理冲突”就是为该关键字的元素找到另一个“空”的哈希地址。在处理冲突的过程中可能得到一个地址序列Hi, i= 1,2,k (Hi属于0.m-1)。在处理冲突过程中，若H1发生冲突，则求H2 ；若H2发生冲突，求H3 ，依次类推，直到Hk不发生冲突为止。 Hk 为元素在表中的地址。140DS/SSDS/SS9.3动
96、态查找表（续）开放定址法： Hi (H(key) + di ) MOD m i=1,2,k(k=m-1)其中：H(key)为哈希函数；m为哈希表表长； di 为增量序列.若：(1)di1,2,3,m-1,称线性探测再散列； (2)di12, -12, 22, 22, +k2 , -k2,称二次探测再散列； (3)di伪随机数序列,称伪随机探测再散列。H(key) = key MOD 11,表中已有关键字17, 60, 29,现哈希关键字为38的元素.012345678910176029线性探测:38H(38)38d1=138d2=238d3=3二次探测:01234567891017602938
97、H(38)38d1=138d2=2避免“二次聚集”线性探测:空间足够 时,可以最终完成二次探测:当m=4j+3的素数时才能完成141DS/SSDS/SS9.3动态查找表（续）再哈希法： Hi RHi (key) i=1,2,k RHi均是不同的哈希函数,即在同义词产生地址冲突时计算另一个哈希函数地址,直到冲突不再发生。 这种方法不容易产生“聚集”，但增加了计算时间公共溢出区法： 设向量HachTable0.m-1为基本表，每个分量存放一个元素，另设向量OverTable0.v为溢出表。所有关键字和基本表中关键字为同义词的元素，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。
98、链地址法： 将所有关键字为同义词的元素存储在同一线性链表中。 用一个指针向量来表示：ChainHashm，凡是哈希地址为i的元素都插入到头指针为ChainHashi的链表中。142DS/SSDS/SS关键字集合：19,14,23,01,68,20,84,27,55,11,10,79, H(key)= key MOD 139.3动态查找表（续）0123465789101112277901145568198420102311143DS/SSDS/SS9.3动态查找表（续）哈希表上的查找及性能哈希表查找过程： 由于哈希表为动态查找表，哈希造表的过程就是查找失败时元素插入的过程(在失败位置)。同样，根
99、据哈希查找特征，哈希表上元素查找过程也类同于哈希造表过程。给定K值，根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有元素，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的方法找“下一地址”，直至哈希表某个位置为“空”或者表中所填元素的关键字等于给定值时为止。 哈希表查找性能取决于三个因素：*哈希函数*处理冲突的方法*装填因子(表中填入元素个数/哈希表表长)144DS/SSDS/SS9.3动态查找表（续）M=16; H(key) = key MOD 13,线性探测处理冲突关键字集合：19,14,23,01,68,20,84,27,55,11,10,
100、790123456789101112131415141012681274553191201843799231111103性能分析:n = 12; m=16， p=13 ASL成功 = (1*6+2+3*3+4+9)/12=2.5ASL不成功 = (1+13 +12+11+10+9+8+7+6+5+4+3+2)/13=7145DS/SSDS/SS0123465789101112277901145568198420102311M=16; H(key) = key MOD 13,链地址法处理冲突关键字集合：19,14,23,01,68,20,84,27,55,11,10,79性能分析:n = 12;
101、 m=16， p=13 ASL成功 = (1*6+2*4+3+4)/12=1.75146DS/SSDS/SS教学内容-第十章8.动态存储管理9.查找10.内部排序11.外部排序12.文件147DS/SSDS/SS10.1排序基本概念排序(Sorting)：将一个数据元素的任意序列重新排成一个按照关键字有序的序列的操作。即:假设n个元素的序列 R1,R2, Rn,相应关键字序列为 K1,K2, Kn。确定1,2,n的一种排列p1,p2, pn,使其相应关键字满足非递减(或非递增)关系K p1=K p2= Kpn , 从而得到一个按关键字有序序列 Rp1,R p2, R pn，这样一个操作过程，就
102、是排序。(排序方法)稳定： Ki 是次关键字。设待排元素序列中， 若KiKj (1=i=n,1=j=n, i != j),且排序前Ri 领先于Rj(即ij),经过该方法排序后序列中Ri 仍然领先于Rj ，则该方法稳定。(排序方法)不稳定： Ki 是次关键字。设待排元素序列中， 若KiKj (1=i=n,1=j=n, i != j),且排序前Ri 领先于Rj(即ij),经过该方法排序后若可能出现序列中Rj 领先于Ri ，则该方法不稳定。内部排序： 待排序元素存放在内存中进行的排序过程。外部排序： 待排序元素个数多，内存中一次不能容纳下，在排序过程中需要对外存进行访问的排序过程。148DS/SSD
103、S/SS10.1排序基本概念（续）排序外部排序内部排序插入排序交换排序选择排序归并排序基数排序按排序依据的不同原则按排序所需的工作量简单排序先进排序基数排序149DS/SSDS/SS10.1排序基本概念（续）待排序元素有三种存储方式： *顺序排序：元素之间的次序关系由存储位置决定，实 现排序必须同时进行关键字比较和元素移动两类操作。 *链表排序：元素之间的次序关系由指针指定，排序中只 进行关键字比较，仅仅修改指针，不进行元素移动。 (为了节省空间，一般用静态链表即可) *地址排序：待排元素在连续单元内，同时另设一个指示 各个元素存储位置的地址向量，排序过程中只进行关键 字比较，不进行实际数据元
104、素移动，而移动地址向量中 这些数据元素的“地址”，形成关键字有序序列 /一般用顺序排序，存储表示如下#define MAXSIZE20typedef intKeyType;/定义关键字类型为整型typedef struct KeyType key/关键字项infoTypeotherinfo/元素其他数据项ElemType；/元素类型typedef struct ElemType rMAXSIZE+1 /r0用作“监视哨”intlength/顺序表长度sqList；/顺序表类型150DS/SSDS/SS10.2插入排序直接插入排序算法思想: 直接插入排序(Straight Insertion S
105、ort)的基本操作是将一个元素插入到已排好序的有序表中,从而得到一个新的、元素数增1的有序表。 第i趟排序过程：在含有i1个元素的有序子序列r1.i-1中插入一个元素ri后，变成含有i个元素的有序子序列r1.i。 整个排序过程共进行n-1趟(即i从2变化到n):先将序列中的第1个元素看成是一个有序的子序列，然后从第2个元素起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。151DS/SSDS/SS383849659776132749*i2i3653849659776132749*i4973849659776132749*i5763849657697132749*i6131338496
106、576972749*i7271327384965769749*i849*1327384949*6576970491234567838659776132749*初始关键字直接插入排序152DS/SSDS/SSVoid InsertSort(SqList &L ) for (i=2; i=L.length; +i) if LT(L.ri.key,L.ri-1.key) L.r0 = L.ri;/监视哨为当前插入元素 for (j = i-1; LT(L.r0.key,L.rj.key); -j)L.rj+1 = L.rj;/元素后移 L.j+1 = L.r0;插入到正确位置 /InsertSort
107、10.2插入排序（续）直接插入排序153DS/SSDS/SS性能分析:时间复杂度T(n)=O(n2) 空间复杂度S(n)=O(1)正序： 比较次数：n-1;元素不移动逆序： 比较次数:(n+2)(n-1)/2;移动次数:(n+4)(n-1)/2稳定性： 直接插入排序方法是稳定的排序方法适用情况： *元素初始序列基本有序； *元素个数少10.2插入排序（续）154DS/SSDS/SS希尔排序算法思想: 希尔排序(Shells Sort)称为“缩小增量排序”，它是从两点出发对直接插入排序进行改进而得到的一种插入排序排序。第一点，元素基本有序时，直接插入排序时间复杂度接近O(n)；第二点，元素个数n
108、很小时，直接插入排序效率也比较高。 希尔排序的基本思想：先将整个待排元素序列分割成若干子序列分别进行直接插入排序（这些子序列要么元素个数少、要么基本有序，从而直接插入排序效率高），待整个序列中的元素“基本有序”时，再对全体元素进行一次直接插入排序。 子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的元素组成一个子序列。这样便于每一趟排序都均匀展开。 排序的趟数就是增量序列的长度。10.2插入排序（续）155DS/SSDS/SS初始关键字希尔排序（增量序列为：5、3、1）0123456789104938659776132749*5504一趟排序结果132749*550449386597
109、76二趟排序结果130449*38274955659776三趟排序结果0413273849*4955657697156DS/SSDS/SSVoid ShellInsert(SqList &L ,int dk) /一趟希尔排序，前后元素位置增量为dk for (i=dk+1; i0<(L.r0.key,L.rj.key); j-=dk)L.rj+dk = L.rj;/元素后移 L.j+dk = L.r0;插入到正确位置 /ShellInsert10.2插入排序（续）Void ShellSort(SqList &L ,int dlta, int t) /按增量序列dlta0.t-1作希尔排序
110、for (k=0; kt; +k) ShellInsert(L,dltak); /ShellSort157DS/SSDS/SS稳定性： 希尔排序方法是不稳定的排序方法增量序列选择： *增量序列中的值没有除1之外的公因子； *最后一个增量值必须等于110.2插入排序（续）性能分析:时间复杂度T(n) =空间复杂度S(n)=O(1)O(n1.5)：增量序列dltak=2t-k+1-1O(n(log2n)2):n趋于无穷大时O(n1.3)：平均情况158DS/SSDS/SS10.3交换排序冒泡排序算法思想: 冒泡排序(Bubble Sort)的基本操作是将两个相邻元素关键字比较，若为逆序，则交换两个
111、元素。 第i趟排序过程：从L.r1到L.rn-i+1依次比较相邻两个元素关键字，并在逆序时交换相邻元素，结果是这n-i+1个元素中关键字最大的元素被交换到第n-i+1的位置上。 整个排序过程共进行k趟(1=kn),判别冒泡排序结束的条件是“在一趟排序过程中没有进行国交换元素的操作”。159DS/SSDS/SS38496576132749*97第一趟结果0491234567838659776132749*初始关键字冒泡排序第二趟结果384965132749*7697第三趟结果3849132749*657697第四趟结果3813274949*657697第五趟结果1327384949*657697
112、第六趟结果1327384949*657697160DS/SSDS/SS性能分析:时间复杂度T(n)=O(n2) 空间复杂度S(n)=O(1)正序： 比较次数：n-1;元素不移动逆序： 比较次数:n(n-1)/2;移动次数:n(n-1)/2稳定性： 冒泡排序方法是稳定的排序方法适用情况： *元素初始序列基本有序； *元素个数较少10.3交换排序（续）161DS/SSDS/SS10.3交换排序（续）快速排序算法思想: 快速排序(Quick Sort)的基本基本思想是,通过一趟排序将待排元素分割成独立的两部分,其中一部分元素的关键字均比另一部分元素的关键字小,则可分别对这两部分元素继续进行排序,以达
113、到整个序列有序。 一趟排序(划分)过程：对待排序列L.rs,L.rs+1,L.rt,任意选取一个元素作为枢轴(pivot),将所有关键字较它小的元素都安置在它的位置之前,将所有关键字较它大的元素都安置在它的位置之后。最后，以该“枢轴”元素最后所落位置作分界线，将序列分割成两个子序列。 整个排序过程共进行的趟数与每一趟排序过程中枢轴元素的选取有关，如果每一趟划分“均匀”，则总趟数可以减到最小。162DS/SSDS/SS快速排序low初始关键字012345678494938659776132749*high一趟排序结果492738134976976549*lowhigh27273813497697
114、6549*lowhigh762738134976976549*76132738二趟排序结果4949*65769749*65769749*13273849low high四趟排序结果49*65769749*13273849163DS/SSDS/SSint Partition(SqList &L ,int low, int high) /一趟快速排序 pivotkey = L.rlow.key/用子表的第一个元素作枢轴元素 L.r0 = L.rlow.key;/将枢轴元素暂存在r0位置处 while (lowhigh)/从表的两端交替地向中间扫描 while (low= pivotkey) -hi
115、gh; L.rlow = L.rhigh; while (lowhigh & L.rlow.key = pivotkey) +low; L.rhigh = L.rlow; L.rlow = L.r0;/枢轴元素到位(此时low=high) retun low; / PartitionVoid QSort(SqList &L ,int low, int high) /完成一次完整的快速排序 if (lowhigh) pivotloc = partition(L, low,high); /将L.rlow.high一分为二 Qsort(L,low,pivotloc-1); Qsort(L, pivo
116、tloc+1, high); /QSort164DS/SSDS/SS性能分析: 平均时间复杂度T(n)=O(knlnn) ,k为常数。 *就平均时间而言，快速排序是目前最好的一种内部排序方法 *若初始序列基本有序，快速排序就蜕变为冒泡排序 *一般选枢轴元素采取“三者取中”法则 一般情况下空间复杂度S(n)=O(log2n),最坏情况下达到O(n)(若改进算法，在一趟排序之后比较分割所得两部分长度，且先对长度短的子序列元素进行快速排序，则栈最大深度可降为O(log2n)稳定性： 快速排序方法是不稳定的排序方法适用情况： *元素初始序列不是基本有序；10.3交换排序（续）165DS/SSDS/SS
117、10.4选择排序简单选择排序算法思想: 简单选择排序(Simple Selection Sort)的基本操作是通过n-i次关键字的比较，从n-i+1个元素中选出关键字最小的元素，并和第i(1=i=n)个元素交换之。 整个排序过程共进行n-1趟(i从1变化至n-1)选择。Void SelectSort(SqList &L) /完成一次完整的简单选择排序 for (i=1; iL.length; +i) /选择第i小的元素，并交换到位 j = SelectMinKey(L,i);/在L.ri . L.length中选择key最小的元素 if (i != j) L.ri 与L.rj交换； /与第i个
118、元素交换 /SelectSort166DS/SSDS/SS1338659776492749*i10491234567838659776132749*初始关键字简单选择排序i21327659776493849*i31327389776496549*i41327384976976549*i51327384949*976576i61327384949*659776i71327384949*657697167DS/SSDS/SS稳定性： 简单选择排序方法是不稳定的排序方法适用情况： *元素个数较少10.4选择排序（续）性能分析:时间复杂度T(n)=O(n2) 空间复杂度S(n)=O(1)正序： 比较次
119、数:n(n-1)/2;元素不移动逆序： 比较次数:n(n-1)/2;移动次数:3(n-1)168DS/SSDS/SS10.4选择排序（续）堆排序堆(Heap)：n个元素的序列k1, k2, kn,当且仅当满足以下关系时，称之为堆。 ki= k2i且ki= k2i且ki= k2i+1. 满足前一约束的堆称之为小顶堆，满足后一约束的堆称之为大顶堆。小顶堆的第一个元素为序列中最小者；大顶堆的第一个元素为序列中最大者。堆可以用完全二叉树来描述描述描述描述(堆的本质仍然是一个序列) 。169DS/SSDS/SS97133849*76276549小顶堆：13, 38, 27, 49*, 76, 65, 4
120、9, 97顺序存储的堆01234567813382749*7665499710.4选择排序（续）170DS/SSDS/SS10.4选择排序（续）堆排序算法思想: 堆排序(Heap Sort)的思路是：下一趟选择排序时尽可能利用上一趟排序过程中已有的比较结果信息，从而提高排序效率。 堆排序完整过程：首先对初始序列建堆；然后，在输出堆顶的最小值之后，使得剩余n-1个元素的序列重新又建成一个堆，则得到n个元素中的次小值。如此反复进行，通过n-1趟，便能得到一个有序序列。 堆排序实现的两个问题：*如何由初始序列建成一个堆；*如何在输出堆顶元素之后，调整剩余元素成为一个新的堆 这两个问题的解决都归结到一
121、个实现：筛选(自堆顶至叶子的调整过程)171DS/SSDS/SS筛选(自堆顶至叶子的调整过程): 输出堆顶元素后,以堆中最后一个元素替代。这时破坏了整个树描述的堆,但其左、右子树仍然是堆，则仅需自上而下进行调整。 首先以堆顶元素和其左、右子树根结点值小者交换 ，若破坏了子树的堆，则进行类似的调整，直至叶子结点。此时堆顶为n-1个元素的最小者。这就是一次调整过程。97133849*7627654901234567813382749*766549979713123413273849*769765491397972749979749172DS/SSDS/SS建堆: 从一个无序序列建堆的过程就是一个反
122、复“筛选”的过程。 将此序列用完全二叉树描述，则最后一个非终端结点是“第(n/2)取下整”个元素，由此，筛选只需从“第(n/2)取下整”个元素开始。 共进行“第(n/2)取下整”次筛选就完成初始建堆过程。49*4938977665132749, 38, 65, 97, 76, 13, 27, 49*0123456784938659776132749*97493849*7665132749*97136597493849*7613652797493849*76136527491349136527134949272749173DS/SSDS/SSVoid HeapSort(HeapType &H)
123、/完成一次完整的堆排序 for (i=H.length/2; i0; -i) HeapAdjust (H, i, H.length); for (i=H.length; i0; -i) H.r1 与H.ri交换; /将堆顶元素和H.r1.i中最后一个元素相互交换 HeapAdjust (H, 1, i-1); /将H.r1.i-1重新调整成大顶堆 /HeapSort ttypedef SqList HeapType; /堆采用顺序表存储表示void HeapAdjust(HeapType &H ,int s, int hm) /一次调整 rc = H.rs; for (j =2*s; j=m;
124、 j *=2) /沿key较大的孩子结点向下筛选 if (jm <(H.rj.key, H.rj+1.key) +j;/j为key较大的元素的下标 if ( !LT(rc.key, H.rj.key) break;/rc应插入在位置s上 H.rs = H.rj;s = j; H.rs = rc;/插入 / HeapAdjust已知H.rs.m中元素的关键字除H.rs.key之外均满足堆的定义，本函数调整H.rs的关键字，使H.rs.m成为一个大顶堆174DS/SSDS/SS稳定性： 堆排序方法是不稳定的排序方法适用情况： *元素个数较多（时间主要耗费在初始建堆和调整新堆时进行的反复筛选上)
125、性能分析:时间复杂度T(n)= O(nlog2n) (最坏情况下) *建立n个元素、深度为h的堆，关键字比较总次数不超过4n; *调整新堆时调用HeapAdjust共n-1次，总共进行的比较次数不 超过2nlog2n次。空间复杂度S(n)=O(1) (元素交换时用)10.4选择排序（续）175DS/SSDS/SS10.5归并排序2-路归并排序算法思想: 归并排序(Merging Sort)的基本操作是“归并”：将两个或两个以上的有序表组合成一个新的有序表。 2-路归并过程：假设初始序列含n个元素，看成n个子序列，两两归并，得到“n/2取上整”个长度为2或为1的有序子序列；再两两归并，如此重复，
126、直至得到一个长度为n的有序序列为止。 整个排序过程共进行log2n趟。每一趟归并调用“(n/(2h)取上整”次核心归并算法，将SR1.n中前后相邻长度为h的有序段进行两两归并，得到前后相邻、长度为2h的有序段，并存放在TR1.n中。交替进行。176DS/SSDS/SSvoid Merge(RcdType SR , RcdType TR , int i, int m, int n) /核心归并算法 /将有序的SRi.m和SRm+1.n归并为有序的TRi.n for (j =m+1, k =i; i=m& j=n; +k) /将SR中元素由小到大地并入TR if LQ(SRi.key,SRj.ke
127、y) TRk = SRi+; else TRk = SRj+; if(j=m) TRk.n = SRi.m;/将剩余的SRi.m复制到TR if(j=n) TRk.n = SRj.n;/将剩余的SRj.n复制到TR / Merge10.5归并排序（续）177DS/SSDS/SS稳定性： 归并排序方法是稳定的排序方法适用情况： *元素个数较多（辅助外排序情况下常用) *n较大时，归并排序所需时间较堆排序省，但辅助空间多性能分析:时间复杂度T(n)= O(nlog2n)空间复杂度S(n)=O(n) (每一趟交替进行)10.5归并排序（续）2-路归并排序178DS/SSDS/SS排序方法时间性能空间性能稳定性适用情况直接插入排序O(n2)O(1)稳定n小;初始序列基本有序希尔排序O(n1.3)O(1)不稳定冒泡排序O(n2)O(1)稳定n小;初始序列基本有序快速排序O(nlog2n)O(log2n)不稳定初始序列无序简单选择排序O(n2)O(1)不稳定n小;初始序列基本有序堆排序O(nlog2n)O(1)不稳定n大;只求前几位2-路归并排序O(nlog2n)O(n)稳定n很大10.7内部排序方法比较
