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

数据结构辅导,李青山西安电子科技大学5/faculty/liqingshanqshli029-8820-4611,课程内容框架,数据结构,基础数据结构,应用数据结构,栈,队列,线性表,线性结构,非线性结构,串,查找,内部排序,外部排序,文件,动态存管理储,数组,广义表,树,二叉树,图,基本概念,1.2基本概念和术语,数据、数据元素、数据项、数据对象结构*集合：松散的关系*线性结构：一对一的关系*树形结构：一对多的关系*网状结构：多对多的关系数据结构Data_Structure=（D，S）,数据结构的分类,1.2基本概念和术语（续）,逻辑结构：数据元素之间的逻辑关系（本来的关系）存储结构：数据结构在计算机中的映象。包括数据元素的表示和关系的表示两个方面。分类：*顺序存储结构*链式存储结构描述方式：用高级语言中的“数据类型”来描述,算法,1.3算法和算法分析,内涵:是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。特性:*有穷性：有穷步+有穷时间/每一步*确定性：指令的语义无二义性*可行性：算法能用基本操作完成*输入：零个或多个输入*输出：一个或多个输出,算法设计的要求,1.3算法和算法分析（续）,正确性（Correctness）可读性（Readablity）健壮性（Robustness）高时间效率与低存储量需求,算法时间效率的度量,1.3算法和算法分析（续）,算法时间效率度量的基本做法在算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。一般而言，这个基本操作是最深层循环内的语句中的原操作。算法时间复杂度T(n)=O(f(n)称为算法的渐近时间复杂度，简称时间复杂度。,算法存储空间的度量,1.3算法和算法分析（续）,算法存储空间度量的基本做法用程序执行中需要的辅助空间的消耗作为存储空间度量的依据，是问题规模n的函数。而程序执行中本身需要的工作单元不能算。算法空间复杂度S(n)=O(f(n)称为算法的空间复杂度。,2.线性表3.栈、队列和串,第一部分线性数据结构,线性数据结构的特点,2.1线性表的逻辑结构,在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素；存在唯一的一个被称作“最后一个”的数据元素；除第一个之外，集合中的每一个数据元素均只有一个前驱；除最后一个之外，集合中每一个数据元素均只有一个后继。,基本概念和术语,2.1线性表的逻辑结构（续）,线性表：n个数据元素的有限序列（线性表中的数据元素在不同环境下具体含义可以不同，但在同一线性表中的元素性质必须相同）。表长：线性表中元素的个数n(n=0)。空表：n=0时的线性表称为空表。位序：非空表中数据元素ai是此表的第i个元素，则称i为ai在线性表中的位序。,线性表的抽象数据类型定义,2.1线性表的逻辑结构（续）,ADTList数据对象：D=ai|ai属于ElemSet,i=1,2,n,n=0数据关系：R1=|ai-1,ai属于D,i=2,3,n,基本操作：InitList(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栈、队列和串的逻辑结构,栈和队列是操作受限的线性表栈和队列的“操作受限”指操作位置受限串的特殊性在于线性表中数据元素只能是字符串一般以子串为操作单位栈、队列和串具有一般线性表共性的特点特殊的线性表反而应用面更宽,栈的基本概念和术语,3.1栈、队列和串的逻辑结构（续）,栈（Stack）：限定仅在表尾进行插入或删除操作的线性表。栈顶（top）：插入或删除的表尾端。栈底（bottom）：表头端。空栈：空表。,栈的操作特点：后进先出（LastInFirstOut-LIFO）,栈的抽象数据类型定义,3.1栈、队列和串的逻辑结构（续）,ADTStack数据对象：D=ai|ai属于ElemSet,i=1,2,n,n=0数据关系：R1=|ai-1,ai属于D,i=2,3,n/a1为栈底，an栈顶,基本操作：InitStack(j=1;/字符之后的位置。若不存在，while(iT0)returniT0;elsereturn0;/Index算法时间复杂度：T(n)=O(n*m),逻辑函数为Index(S,T,pos)S=a1a2aianT=t1t2tjtm一般而言，mn算法思路：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，继续逐个比较后续字符，否则从主串的下一个字符起再重新和模式的字符比较之。,3.3串的模式匹配算法（续）,第一趟主串：ababcabcacbab/i=3模式串：abc/j=3,第二趟主串：ababcabcacbab/i=2模式串：a/j=1,第三趟主串：ababcabcacbab/i=7模式串：abcac/j=5,第四趟主串：ababcabcacbab/i=4模式串：a/j=1,第五趟主串：ababcabcacbab/i=5模式串：a/j=1,第六趟主串：ababcabcacbab/i=11模式串：abcac/j=6,模式串T=abcac,改进算法-思路,3.3串的模式匹配算法（续）,KMP算法思路：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，继续逐个比较后续字符。当一趟匹配过程中出现字符比较不等时，不回朔i指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。优点：在匹配过程中，主串的跟踪指针不回朔时间效率达到T(n)=O(n+m),如何理解“部分匹配”？主串：acabaacaabcac模式串：acaab,改进算法-原理,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+2si-1-(3),由(1)式与(3)式可以推知：t1t2tk-1=tj-k+1tj-k+2tj-1-(4),令nextj=k，表示当模式串中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。根据其语义，定义如下：0当j=1时/相当于主串中i指针推进一个位置Nextj=Maxk|10)各互不相交的有限集T1,T2,Tm,其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。树的结点：一个数据元素和指向其子树的分支。结点的度：结点拥有的子树数。终端结点（或叶子）：度为0的结点。非终端结点（或分支结点、或内部结点）：度不为0的结点。树的度：树内各结点的度的最大值。（结点的）孩子：结点的子树的根。,6.1树的逻辑结构（续）,树的性质及树的表示,树的性质：递归性层次性,树的表示形式：树形表示集合嵌套表示广义表形式表示凹入表示,6.2树的存储结构（续）,孩子兄弟表示法（二叉链表）,/-树的二叉链表（孩子-兄弟）存储表示-typedefstructCSNodeElemTypedata;/树结点数据域structCSNode*firstchild,*nextsibling;CSNode,*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的二叉树至多有2k1个结点(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+n2n=B+1B=n1+2n2所以：n0=n2+1证毕,性质4：证明假设深度为k，由性质2以及完全二叉树定义有：2k-11n=2k1推出2k-1=n2kk1data)if(InOrderTraverse(T-rchild,Visit)returnOK;elsereturnERROR;/当访问失败时，出错elsereturnOK;/一次递归访问终止InOrderTraverse/算法时间复杂度：O(n),6.5二叉树的遍历及线索化（续）,中序遍历的算法,StatusInOrderTraverse1(BiTreeT,Status(*Visit)(TElemTypee)/中序遍历二叉树T的非递归算法，对每个数据元素调用函数VisitInitStack(S);Push(S,T);/根指针入栈While(!StackEmpty(S)while(GetTop(S,p)InOrderTraverse/算法时间复杂度：O(n),StatusInOrderTraverse2(BiTreeT,Status(*Visit)(TElemTypee)/中序遍历二叉树T的非递归算法，对每个数据元素调用函数VisitInitStack(S);p=T;While(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;/根指针入栈,遍历左子树else/根指针退栈，访问根结点，遍历右子树Pop(S,p);if(!Visit(p-data)returnERROR/访问出错p=p-rchild);/else/whilereturnOK;InOrderTraverse/算法时间复杂度：O(n),6.5二叉树的遍历及线索化（续）,二叉树遍历的典型应用,已知二叉树的前序遍历序列和中序遍历序列，或者已知二叉树的后序遍历序列和中序遍历序列，可以唯一确定这棵二叉树。,Step1:判定根，由PostOrder知根为A；,Step2:判定左子树元素集合，由InOrder知为CBEDGFH,InOrder:CBEDGFHAJIKPostOrder:CEGHFDBJKIA,Step3:判定右子树元素集合，由InOrder知为JIK,Step4:分别对左、右子树元素集合按照中序和后序序列递归进行Step1-Step3，直到元素集合为空。,6.5二叉树的遍历及线索化（续）,线索二叉树,遍历本质是结点之间非线性关系线性化的过程遍历后的元素之间的某种线性关系一般隐藏在遍历规则下需要多次对同一棵树遍历时，如何提高效率？在二叉链表结构中增加线索域，显式描述遍历后的线索关系节省线索域空间，充分利用二叉链表中空的n+1个指针域线索链表：二叉树的存储结构，结点结构定义见前面。线索：指向结点前驱和后继的指针，叫做线索。线索二叉树：加上线索的二叉树。线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程。,线索二叉树上遍历的过程，就是根据线索和遍历规则不断找当前结点后继结点的过程。,6.5二叉树的遍历及线索化（续）,线索二叉树上的中序遍历,InOrder:CBEDGFHAJIK,设当前结点指针为p，其前驱结点为q，后继结点指针为s,则有：,求结点p的后继：1.若p-rtag=1则s=p-rchild;2.若p-rtag=0s为p的右子树的中序遍历序列的第一个结点，即右子树最左下结点,求结点p的前驱：1.若p-ltag=1则q=p-lchild;2.若p-rtag=0q为p的左子树的中序遍历序列的第一个结点，即左子树最右下结点,6.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,6.6树、森林与二叉树的转换（续）,树与二叉树的转换,目的：利用二叉树运算来简化树和森林上的运算；依据：树与二叉树具有相同的二叉链表存储结构；,6.6树、森林与二叉树的转换（续）,6.6树、森林与二叉树的转换（续）,6.7二叉树的应用,哈夫曼树(HuffmanTree),结点之间路径长度：树中两个结点之间的分支构成这两个结点的路径，路径上的分支数目为路径长度。树的路径长度：树根到每个结点的路径长度之和。结点的带权路径长度：该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和，记为：WPL=w1k1+w2k2+wiki+wnkn。最优二叉树（哈夫曼树）：设n个权值w1,w2,wn,构造一棵有n个叶子结点的二叉树，每个叶子结点带权wi,则其中带权路径长度WPL最小的二叉树称为最优二叉树（哈夫曼树）。,6.7二叉树的应用（续）,哈夫曼算法(HuffmanAlgorithmic),输入：n个权值w1,w2,wn；输出：一棵哈夫曼树算法：步骤一：根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均为空。步骤二：在F中选取两棵根结点的权值最小的树作为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。步骤三：在F中删除这两棵树，同时将新得到的二叉树加入F中。步骤四：重复步骤二与三，直到F只含有一棵树为止。,给定权的集合:15,3,14,2,6,9,16,17,6.7二叉树的应用（续）,哈夫曼算法(HuffmanAlgorithmic),15,3,14,2,6,9,16,17,15,5,14,6,9,16,17,15,11,14,9,16,17,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二叉树的应用（续）,哈夫曼编码(HuffmanCode),等长编码：每个被编码对象的码长相等。优点：码长等长，易于解码；缺点：被编码信息总码长较大，尤其是当存在许多不常用的被编码对象时前缀编码：任一个被编码对象的编码都不是另一个被编码对象的编码的前缀。优点：当存在被编码对象使用概率不同时，被编码信息总码长可以减小；缺点：码长不等长，不易于解码,6.7二叉树的应用（续）,哈夫曼编码(HuffmanCode)-前缀编码,利用二叉树来设计二进制的前缀编码：被编码对象出现在二叉树的叶子结点。约定左分支表示字符“0”，右分支表示字符“1”，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点对应对象的编码。,a(00)b(010)c(0110)d(0111)e(10)f(11),这种编码的译码过程从根开始。沿着某条分支走到叶子结点时，走过的二进制字符串即译为该叶子结点对应的对象。然后循环扫描总编码后的字符串。,6.7二叉树的应用（续）,哈夫曼编码与译码,利用哈夫曼算法可以得到总码长最短的二进制前缀编码，即为哈夫曼编码。设某次编码应用中不同被编码对象有n种，以此n种被编码对象出现的频率作权，构造出的哈夫曼树即为这n种对象的编码树，由此可得到其二进制的前缀编码。,假定用于通讯的电文如下，现在要对其编码，采用哈夫曼编码。写出编码后的二进制串。电文：castcatssatatatasa,c(110)a(0)s(111)t(10),Set=c,a,s,tW=2,7,4,5,电文编码：11001111011001011111101001001001110,4.数组5.广义表6.树和二叉树7.图,教学内容-第七章,ADTGraph数据对象：V=具有相同性质的数据元素数据关系：R:R=VRVR=|v,w属于V且P(v,w),是从v到w的一条弧，谓词P(v,w)定义了弧的意义或信息基本操作：P:CreateGraph(BFSTraverseGraph(G,v,Visit()ADTGraph,7.1图的逻辑结构,图的抽象数据类型,7.1图的逻辑结构（续）,基本概念和术语,顶点(Vertex)、弧(Arc)、有向图(Digraph)、边(Edge)、无向图(Undigraph)、完全图(Completedgraph)、有向完全图、稀疏图(Sparsegraph)、权(Weight)、网(Network)、子图(Subgraph)、邻接点(Adjacent)、（顶点的）度(Degree)、（顶点的）入度(InDegree)、（顶点的）出度(OutDegree)、（顶点之间）路径(Path)、（顶点之间）路径长度、回路或环(Cycle)、简单路径、简单回路（简单环）、（顶点之间）连通、连通图(ConnectedGraph)、连通分量(ConnectedComponent)、强连通图、强连通分量、（连通图的）生成树：（有向图的）生成森林,7.2树的存储结构（续）,数组表示法,7.2图的存储结构（续）,邻接表-图的链式存储,基本思路：对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。每个表结点由三个域组成：邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置；链域(nextarc)指示下一条边或弧的结点；数据域(info)存储和边或弧相关的信息。头结点由两个域组成：链域(firstarc)指向链表中第一个结点；数据域(data)存储顶点vi信息。头结点以顺序结构形式存取，以便随机访问任一顶点的链表。,7.2图的存储结构（续）,7.2图的存储结构（续）,邻接表-图的链式存储,邻接表的优点：边（或弧）稀疏时，节省空间；和边（或弧）相关的信息较多时，节省空间；容易求得当前顶点的第一个邻接点、下一个邻接点。,对有向图，也可建立逆向邻接表，即对每个顶点建立一个链接以该顶点为头的弧的表。,7.3图的遍历,遍历图,在图中查找具有某种特征的结点需要对结点进行访问（处理、输出等）操作图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础,图的遍历(TraversingGraph)：从图的某一个顶点出发，按照某条路径访问每个结点,使得每个结点均被访问一次，而且仅被访问一次。,遍历本质：结点之间非线性关系线性化的过程遍历思路：*深度优先：类似于树的先根遍历；*广度优先：类似于树的层次遍历。,7.3图的遍历（续）,深度优先搜索,遍历思路：从图的某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。这是一个递归算法，遍历过程中，当某个顶点的所有邻接点都被访问到后，需要“回朔”，即沿着调用的逆方向回退到上一层顶点，继续考察该顶点的下一个邻接点。,BooleanvisitedMAX;/访问标志数组Status(*VisitFunc)(intv);/函数变量VoidDFSTraverse(GraphG,Status(*Visit)(intv)VisitFunc=Visit；/使用全局变量VisitFunc，使DFS不必设函数指针参数for(v=0;vG.vexnum;+v)visitedv=FALSE;/标志数组初始化for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);StatusDFS(GraphG,intv)/从第v个顶点出发递归地深度优先遍历图G，对每个元素调用函数Visitvisitedv=TRUE;VisitFunc(v);/访问第v个顶点for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/算法时间复杂度与存储结构相关,邻接矩阵存储:T(n)=O(n2);邻接表存储:T(n)=O(n+e),7.3图的遍历（续）,深度优先搜索,一种DFS遍历序列：V1,V2,V4,V8,V5,V3,V6,V7,V9,V10,V12,V11当存储结构和算法确定后，遍历序列唯一。,7.3图的遍历（续）,广度优先搜索,遍历思路：从图的某个顶点v出发，访问此顶点，然后依次访问v的未被访问的邻接点，然后从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。一层层遍历。如何保证上层次序先于下层次序？保证“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问？可以通过队列来控制实现。,BooleanvisitedMAX;/访问标志数组VoidBFSTraverse(GraphG,Status(*Visit)(intv)for(v=0;vG.vexnum;+v)visitedv=FALSE;/标志数组初始化InitQueue(Q);/置空的辅助队列for(v=0;v=2)；step4.根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足e(s)=l(s)，则为关键活动。,7.4图的应用（续）,有向无环图的关键路径示例,*关键活动的改进可以改进工程进度；*关键活动速度提高要有限度,前提是不能改变关键路径*若网中有多条关键路径，要改进工程进度，必须同时提高几条关键路径上的关键活动的速度。,7.4图的应用（续）,带权有向图的最短路径,源点：路径上的第一个顶点汇点：路径上的最后一个顶点最短路径：*从源点到终点所含边的数目最少的路径。（用BFS边历方法可以求得）*从源点到终点路径上边的权值之和最小的路径。（用Dijkstra算法和Floyd算法可以求得）,从某个源点到其余各顶点的最短路径（设源点为v0，终点可以是v1,v2,vn，则可以求得n条最短路径）每一对顶点之间的最短路径（源点可以为v1,v2,vn，终点也可以是v1,v2,vn，源点与终点不能相等，可以求得n(n-1)条最短路径）,7.4图的应用（续）,某个源点到其余各顶点的最短路径,7.4图的应用（续）,最短路径算法,思路：1.Dijkstra:按路径长度递增的次序产生最短路径。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)和弧(vi,vk)上的权值之和。,输入：带权有向图输出：n条最短路径步骤：step1.从源点v出发到图上其余各顶点（终点）vi可能达到的最短路径长度的初值为：若从v到vi有弧，Di为弧上权值；否则为无穷大；step2.选择vj，使得Dj=Min(i)Di|vi属于V-S，vj就是当前求得的一条从v出发的最短路径的终点。令S=SUj；step3.修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。如果Dj+arcsjkDk，则修改Dk=Dj+arcsjk；step4.重复操作step2、step3共n-1次。由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。,7.4图的应用（续）,10(v0,v2),30(v0,v4),50(v0,v4,v3),60(v0,v4,v3,v5),7.4图的应用（续）,每一对顶点之间的最短路径,两种方法：*每次以一个顶点为源点，重复执行Dijkstra算法n次，便可求得每一对顶点之间最短路径。T(n)=O(n3)*Floyd算法。T(n)=O(n3),第三部分应用数据结构,8.动态存储管理9.查找10.内部排序11.外部排序12.文件,教学内容-第九章,8.动态存储管理9.查找10.内部排序11.外部排序12.文件,9.1查找的概念和思路,查找表(SearchTable)、静态查找表(StaticSearchTable)、动态查找表(DynamicSearchTable)、查找(Searching)、关键字(Key)、主关键字(PrimaryKey)、次关键字(SecondaryKey)、查找成功(SearchingSuccess)、查找不成功(SearchingFailed)、查找成功时平均查找长度：查找不成功平均查找长度、平均查找长度(AverageSearchLength)：,基本概念和术语,查找表中元素关系松散，直接在原始查找表中查找的效率很低。查找一般思路：向查找表上依附其他数据结构，使查找表中数据元素之间关系约束增加，从而利于查找过程的进行。根据依附的数据结构不同，可以有不同的查找过程、查找特点和查找性能。依附数据结构的选择取决于问题域特点和查找表本身特性。,9.1查找的概念和思路（续）,基本思路,9.2静态查找表,顺序表的查找,顺序表查找=查找表+线性表+顺序存储,线性链表查找=查找表+线性表+链式存储；,/-静态查找表存储表示-typedefstructElemType*elem;/0号单元留空intlength;SSTable;,intSearch_Seq(SSTableST,KeyTypekey)/若找到，含数值为该元素在表中的位置，否则为0ST.elem0.key=key;/“哨兵”for(i=ST.length;!EQ(ST.elemi.key,key);-i);/从后往前找returni;/找不到，i为0（这也是哨兵的作用所在）Search_Seq,顺序查找(SequentialSearch)过程：从表中最后一个元素开始，逐个进行元素的关键字和给定值的比较，若某个元素的关键字和给定值相等，则查找成功，找到所查元素；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查元素，查找不成功。,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,顺序查找的优点：*算法简单、适用面广；*对线性关系没有其他要求；*对存储结构没有要求,顺序查找的缺点：*平均查找长度大；,9.2静态查找表（续）,有序表的查找,有序表查找=查找表+线性表+有序性+顺序存储,/-静态查找表存储表示-typedefstructElemType*elem;/0号单元留空intlength;SSTable;,四种查找方法：*折半查找*顺序查找*斐波那契查找*插值查找,折半查找(BinarySearch)过程：先确定待查元素所在范围（区间），然后逐步缩小范围直到找到或找不到该元素为止。具体而言，折半查找是以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，若不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或者查找区间的大小小于零时（表明查找不成功）为止。,9.2静态查找表（续）,有序表的折半查找,intSearch_Bin(SSTableST,KeyTypekey)/若找到，含数值为该元素在表中的位置，否则为0low=1;high=ST.length;/置区间初值while(lowAddress；key的哈希函数值记H(key)。冲突(collision)：对不同关键字可能得到同一哈希地址的现象，即key1!=key2，而H(key1)=H(key2)。具有相同函数值的关键字对该哈希函数来说称作同义词(synonym)。哈希表(HashTable):根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上并以关键字在地址集中的“象”作为元素在表中的存储位置，这种表称为哈希表。这种映象过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址。,9.3动态查找表（续）,哈希表中基本概念和术语,直接定址法：数字分析法：平方取中法:折叠法:随机数法:除留余数法：取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即：H(key)=keyMODpp=m可以对关键字直接取模，也可以在折叠、平方取中等运算后取模。一般情况下，p取质数或不包含小于20的质因素的合数。,9.3动态查找表（续）,9.3动态查找表（续）,处理冲突的方法,假设哈希表地址集为：0(m-1)，冲突是指由关键字得到的哈希地址为j(0=j=m-1)的位置上已存有记录，则“处理冲突”就是为该关键字的元素找到另一个“空”的哈希地址。在处理冲突的过程中可能得到一个地址序列Hi,i=1,2,k(Hi属于0.m-1)。在处理冲突过程中，若H1发生冲突，则求H2；若H2发生冲突，求H3，依次类推，直到Hk不发生冲突为止。Hk为元素在表中的地址。,9.3动态查找表（续）,开放定址法：Hi(H(key)+di)MODmi=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)=keyMOD11,表中已有关键字17,60,29,现哈希关键字为38的元素.,17,60,29,线性探测:,二次探测:,17,60,29,避免“二次聚集”线性探测:空间足够时,可以最终完成二次探测:当m=4j+3的素数时才能完成,9.3动态查找表（续）,再哈希法：HiRHi(key)i=1,2,kRHi均是不同的哈希函数,即在同义词产生地址冲突时计算另一个哈希函数地址,直到冲突不再发生。这种方法不容易产生“聚集”，但增加了计算时间,公共溢出区法：设向量HachTable0.m-1为基本表，每个分量存放一个元素，另设向量OverTable0.v为溢出表。所有关键字和基本表中关键字为同义词的元素，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。,链地址法：将所有关键字为同义词的元素存储在同一线性链表中。用一个指针向量来表示：ChainHashm，凡是哈希地址为i的元素都插入到头指针为ChainHashi的链表中。,关键字集合：19,14,23,01,68,20,84,27,55,11,10,79,H(key)=keyMOD13,9.3动态查找表（续）,9.3动态查找表（续）,哈希表上的查找及性能,哈希表查找过程：由于哈希表为动态查找表，哈希造表的过程就是查找失败时元素插入的过程(在失败位置)。同样，根据哈希查找特征，哈希表上元素查找过程也类同于哈希造表过程。给定K值，根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有元素，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的方法找“下一地址”，直至哈希表某个位置为“空”或者表中所填元素的关键字等于给定值时为止。哈希表查找性能取决于三个因素：*哈希函数*处理冲突的方法*装填因子(表中填入元素个数/哈希表表长),9.3动态查找表（续）,M=16;H(key)=keyMOD13,线性探测处理冲突,关键字集合：19,14,23,01,68,20,84,27,55,11,10,79,性能分析:n=12;m=16，p=13ASL成功=(1*6+2+3*3+4+9)/12=2.5ASL不成功=(1+13+12+11+10+9+8+7+6+5+4+3+2)/13=7,M=16;H(key)=keyMOD13,链地址法处理冲突,关键字集合：19,14,23,01,68,20,84,27,55,11,10,79,性能分析:n=12;m=16，p=13ASL成功=(1*6+2*4+3+4)/12=1.75,教学内容-第十章,8.动态存储管理9.查找10.内部排序11.外部排序12.文件,10.1排序基本概念,排序(Sorting)：将一个数据元素的任意序列重新排成一个按照关键字有序的序列的操作。即:假设n个元素的序列R1,R2,Rn,相应关键字序列为K1,K2,Kn。确定1,2,n的一种排列p1,p2,pn,使其相应关键字满足非递减(或非递增)关系Kp1=Kp2=Kpn,从而得到一个按关键字有序序列Rp1,Rp2,Rpn，这样一个操作过程，就是排序。(排序方法)稳定：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，则该方法不稳定。内部排序：待排序元素存放在内存中进行的排序过程。外部排序：待排序元素个数多，内存中一次不能容纳下，在排序过程中需要对外存进行访问的排序过程。,10.1排序基本概念（续）,排序,10.1排序基本概念（续）,待排序元素有三种存储方式：*顺序排序：元素之间的次序关系由存储位置决定，实现排序必须同时进行关键字比较和元素移动两类操作。*链表排序：元素之间的次序关系由指针指定，排序中只进行关键字比较，仅仅修改指针，不进行元素移动。(为了节省空间，一般用静态链表即可)*地址排序：待排元素在连续单元内，同时另设一个指示各个元素存储位置的地址向量，排序过程中只进行关键字比较，不进行实际数据元素移动，而移动地址向量中这些数据元素的“地址”，形成关键字有序序列,/一般用顺序排序，存储表示如下#defineMAXSIZE20typedefintKeyType;/定义关键字类型为整型typedefstructKeyTypekey/关键字项infoTypeotherinfo/元素其他数据项ElemType；/元素类型typedefstructElemTyperMAXSIZE+1/r0用作“监视哨”intlength/顺序表长度sqList；/顺序表类型,10.2插入排序,直接插入排序,算法思想:直接插入排序(StraightInsertionSort)的基本操作是将一个元素插入到已排好序的有序表中,从而得到一个新的、元素数增1的有序表。第i趟排序过程：在含有i1个元素的有序子序列r1.i-1中插入一个元素ri后，变成含有i个元素的有序子序列r1.i。整个排序过程共进行n-1趟(即i从2变化到n):先将序列中的第1个元素看成是一个有序的子序列，然后从第2个元素起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。,VoidInsertSort(SqList插入到正确位置/InsertSort,10.2插入排序（续）,直接插入排序,稳定性：直接插入排序方法是稳定的排序方法,适用情况：*元素初始序列基本有序；*元素个数少,10.2插入排序（续）,希尔排序,算法思想:希尔排序(ShellsSort)称为“缩小增量排序”，它是从两点出发对直接插入排序进行改进而得到的一种插入排序排序。第一点，元素基本有序时，直接插入排序时间复杂度接近O(n)；第二点，元素个数n很小时，直接插入排序效率也比较高。希尔排序的基本思想：先将整个待排元素序列分割成若干子序列分别进行直接插入排序（这些子序列要么元素个数少、要么基本有序，从而直接插入排序效率高），待整个序列中的元素“基本有序”时，再对全体元素进行一次直接插入排序。子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的元素组成一个子序列。这样便于每一趟排序都均匀展开。排序的趟数就是增量序列的长度。,10.2插入排序（续）,VoidShellInsert(SqList插入到正确位置/ShellInsert,10.2插入排序（续）,VoidShellSort(SqList/ShellSort,稳定性：希尔排序方法是不稳定的排序方法,增量序列选择：*增量序列中的值没有除1之外的公因子；*最后一个增量值必须等于1,10.2插入排序（续）,10.3交换排序,冒泡排序,算法思想:冒泡排序(BubbleSort)的基本操作是将两个相邻元素关键字比较，若为逆序，则交换两个元素。第i趟排序过程：从L.r1到L.rn-i+1依次比较相邻两个元素关键字，并在逆序时交换相邻元素，结果是这n-i+1个元素中关键字最大的元素被交换到第n-i+1的位置上。整个排序过程共进行k趟(1=kn),判别冒泡排序结束的条件是“在一趟排序过程中没有进行国交换元素的操作”。,稳定性：冒泡排序方法是稳定的排序方法,适用情况：*元素初始序列基本有序；*元素个数较少,10.3交换排序（续）,10.3交换排序（续）,快速排序,算法思想:快速排序(QuickSort)的基本基本思想是,通过一趟排序将待排元素分割成独立的两部分,其中一部分元素的关键字均比另一部分元素的关键字小,则可分别对这两部分元素继续进行排序,以达到整个序列有序。一趟排序(划分)过程：对待排序列L.rs,L.rs+1,L.rt,任意选取一个元素作为枢轴(pivot),将所有关键字较它小的元素都安置在它的位置之前,将所有关键字较它大的元素都安置在它的位置之后。最后，以该“枢轴”元素最后所落位置作分界线，将序列分割成两个子序列。整个排序过程共进行的趟数与每一趟排序过程中枢轴元素的选取有关，如果每一趟划分“均匀”，则总趟数可以减到最小。,intPartition(SqList/Partition,VoidQSort(SqList/QSort,性能分析:平均时间复杂度T(n)=O(knlnn),k为常数