《数据结构复习题.ppt》由会员分享，可在线阅读，更多相关《数据结构复习题.ppt（136页珍藏版）》请在三一办公上搜索。
1、江志英信息学院计算机系jiangzy,总 复 习,数据结构,数据结构概论,数据结构,数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科数据结构是对数据元素之间的逻辑关系、数据的存储方式以及对数据的操作的抽象描述。,抽象数据类型(Abstract Data Type 简称ADT),ADT：是指一个数学模型以及定义在此数学模型上的一组操作。数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。,
2、ADT的描述方法,抽象数据类型可用（D，S，P）三元组表示。其中：D 是数据对象；S 是 D 上的关系集；P 是对 D 的基本操作集。ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,算法和算法分析,算法：是为了解决某类问题而规定的一个有限长的操作序列。复杂度对度量值的阶的评估。设某函数f(x)，若存在另一函数g(x)，满足当x趋近于无穷时，limf(x)/g(x)趋近于一个非的常数，则称f(x)的度为O(g(x)。算法复杂度一般分为时间复杂度和空间复杂度。,习题判断题,（1）数据项是数据基本单位（）（2）数据的逻辑结
3、构是指各数据元素之间的逻辑关系，是用户按使用需要建立的（）（3）数据的物理结构是指数据在计算机内实际的存储形式（）,（1）错误（2）对（3）对,习题选择题,（1）算法的计算量的大小称为计算的.a)现实性 b)难度 c)复杂性 d)效率（2）数据结构被形式定义为（D，S），其中D 是 的有限集合，S 是D 上的 有限集合。a)算法 b)数据元素 c)数据操作 d)逻辑结构 e)操作f)映象 g)存储 h)关系（3）在数据结构中，从逻辑上可以把数据结构分成。a)动态结构和静态结构 b)紧凑结构和非紧凑结构 c)线性结构和非线性结构 d)内部结构和非内部结构（4）算法的时间复杂度取决于.a)问题的规
4、模 b)待处理数据的初态 c)问题的规模和待处理数据的初态,习题选择题,（1）算法的计算量的大小称为计算的 c。a)现实性 b)难度 c)复杂性 d)效率（2）数据结构被形式定义为（D，S），其中D 是 b 的有限集合，S 是D 上的 h 有限集合。a)算法 b)数据元素 c)数据操作 d)逻辑结构 e)操作f)映象 g)存储 h)关系（3）在数据结构中，从逻辑上可以把数据结构分成 c。a)动态结构和静态结构 b)紧凑结构和非紧凑结构 c)线性结构和非线性结构 d)内部结构和非内部结构（4）算法的时间复杂度取决于 a。a)问题的规模 b)待处理数据的初态 c)问题的规模和待处理数据的初态,线性
5、表,线性表,线性表的定义和特点 定义 n（0）个数据元素的有限序列，记作（a1,a2,an）ai 是表中数据元素，n 是表长度。,除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。,特点,顺序表,顺序表的定义和特点 定义 将线性表中的元素相继存放在一个连续的存储空间中。可利用一维数组描述存储结构 特点 线性表的顺序存储方式 遍历 顺序访问,可以随机存取,25 34 57 16 48 09,0 1 2 3 4 5,data,顺序表的插入,int Insert(SeqList/插入成功,顺序表的删除,int Delete(SeqLis
6、t/表中没有 x,应用1：集合 并运算,void Union(SeqList,应用2：集合 交运算,void Intersection(SeqList/未找到在A中删除它,链表（Linked List）,链接表是线性表的链接存储表示单链表静态链表 循环链表（顺序存储模拟链式结构）双向链表,链表（Linked List）,单链表的存储映像,free,(a)可利用存储空间,a0,a2,a1,a3,free,first,(b)经过一段运行后的单链表结构,单链表的定义,typedef char ListData;typedef struct node/链表结点 ListData data;/结点数据域
7、 struct node*link;/结点链域 ListNode;typedef ListNode*LinkList;LinkList first;/链表头指针,单链表的插入,第一种情况：在第一个结点前插入 newnode-link=first;first=newnode;第二种情况：在链表中间插入 newnode-link=p-link;p-link=newnode；第三种情况：在链表末尾插入 newnode-link=p-link;p-link=newnode；,int Insert(LinkList,newnode-data=x;if(first=NULL|i=1)/插在表前 newno
8、de-link=first;first=newnode;else/插在表中或末尾 newnode-link=p-link;p-link=newnode;return 1;,删除第一种情况:删除表中第一个元素第二种情况:删除表中或表尾元素,在单链表中删除含ai的结点,ai-1,ai,ai+1,删除前,int Delete(LinkList,if(p=NULL|p-link=NULL)printf(“无效的删除位置!n”);return 0;else/删除表中或表尾元素 q=p-link;/重新链接 p-link=q-link;free(q);/删除q return 1;,单链表清空,void C
9、lear(LinkList first)/删去链表中除表头结点外的所有其他结点 ListNode*q;while(first-link!=NULL)q=first-link;first-link=q-link;/将表头结点后第一个结点从链中摘下 free(q);/释放它,习题,例1.已知单链表的结构定义如下：struct ListNode int data;struct ListNode*next;typedef ListNode*LinkList;请编写算法（写出算法代码），将指定的带头结点的单链表转为逆序。参考算法代码形式如下：int ReverseLinkList(LinkList A)
10、.,参考代码如下：int ReverseLinkList(LinkList A)if(A=NULL)return 0;ListNode*p=A-next;A-next=NULL;while(p!=NULL)ListNode*q=p;p=p-next;q-next=A-next;A-next=q;return 1;,例2.已知顺序结构线性表的结构定义如下，且表中的元素按非降序排列：struct SList int bufferMAXLENGTH;int tablelen;请编写高效算法，删除表中的重复元素。如，若原表为(1,1,2,3,3,3,4,5,5)，经过算法处理后，表为(1,2,3,4,
11、5)。参考算法代码形式如下：int PackSList(SList&L).,参考代码如下：int PackSList(SList,栈和队列,定义 只允许在一端插入和删除的线性表；允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。特点 后进先出(LIFO),栈(Stack),栈的抽象数据类型,ADT Stack/对象:由数据类型为StackData的元素构成 int Push(stack*S,StackData x);/进栈 int Pop(stack*S,StackData/判栈满否,#define StackSize 100typedef char StackData;
12、typedef struct/顺序栈定义 StackData dataStackSize;/栈数组 int top;/栈顶指针 SeqStack;,栈的数组表示 顺序栈,0 1 2 3 4 5 6 7 8 9 StackSize-1,top(栈空),data,int StackEmpty(SeqStack*S)/判断栈是否空？空则返回1，否则返回0 return S-top=-1;int StackFull(SeqStack*S)/判断栈是否满？满则返回1，否则返回0 return S-top=StackSize-1;void InitStack(SeqStack*S)/置空栈 S-top=-
13、1;,int Push(SeqStack*S,StackData x)/若栈满返回0,否则新元素 x 进栈并返回1 if(StackFull(S)return 0;S-data+S-top=x;/加入新元素 return 1;int Gettop(SeqStack*S,StackData,int Pop(SeqStack*S,StackData,栈的链接表示 链式栈,链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作,top,typedef int StackData;typedef struct node StackData data;/结点数据 struc
14、t node*link;/结点链指针 StackNode;typedef struct StackNode*top;/栈顶指针 LinkStack;,链式栈(LinkStack)的定义,链式栈操作的实现,void InitStack(LinkStack*S)S-top=NULL;int Push(LinkStack*S,StackData x)StackNode*p=(StackNode*)malloc(sizeof(StackNode);p-data=x;p-link=S-top;S-top=p;return 1;,int StackEmpty(LinkStack*S)return S-to
15、p=NULL;int Pop(LinkStack*S,StackData,int GetTop(LinkStack*S,StackData,定义队列是只允许在一端删除，在另一端插入的线性表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,First In First Out),a0 a1 a2 an-1,front,rear,队列(Queue),队列的抽象数据类型,ADT Queue/对象:由数据类型为QueueData的元素构成 int EnQueue(Queue*Q,QueueData x);/进队 int DeQueue(Queue*Q,Q
16、ueueData/判队满否,顺序队列,#define QueueSize 50;typedef int QueueData;typedef struct QueueData dataQueueSize;int rear,front;SeqQueue;void InitQueue(SeqQueue*Q)Q-front=Q-rear=-1;,队列的进队和出队原则,进队时队尾指针先进一 rear=rear+1，再将新元素按 rear 指示位置加入。出队时队头指针先进一 front=front+1，再将下标为 front 的元素取出。队满时再进队将溢出出错；队空时再出队将队空处理。解决办法之一：将队列
17、元素存放数组首尾相接，形成循环(环形)队列。,队列存放数组被当作首尾相接的表处理。队头、队尾指针加1时从QueueSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:front=(front+1)%QueueSize;队尾指针进1:rear=(rear+1)%QueueSize;队列初始化：front=rear=0;队空条件：front=rear;队满条件：(rear+1)%QueueSize=front,循环队列(Circular Queue),void InitQueue(SeqQueue*Q)Q-rear=Q-front=0;int QueueEmpty(SeqQueu
18、e*Q)return Q-rear=Q-front;int QueueFull(SeqQueue*Q)return(Q-rear+1)%QueueSize=Q-front;,循环队列操作的实现,int EnQueue(SeqQueue*Q,QueueData x)if(QueueFull(Q)return 0;Q-rear=(Q-rear+1)%QueueSize;Q-dataQ-rear=x;return 1;int DeQueue(SeqQueue*Q,QueueData,int GetFront(SeqQueue*Q,QueueData,队列的链接表示 链式队列,队头在链头，队尾在链尾。
19、链式队列在进队时无队满问题，但有队空问题。队空条件为 front=NULL,front,rear,链式队列的定义typedef int QueueData;typedef struct node QueueData data;/队列结点数据 struct node*link;/结点链指针 QueueNode;typedef struct QueueNode*rear,*front;LinkQueue;,void InitQueue(LinkQueue*Q)Q-rear=Q-front=NULL;int QueueEmpty(LinkQueue*Q)return Q-front=NULL;int
20、 GetFront(LinkQueue*Q,QueueData,链式队列主要操作的实现,int EnQueue(LinkQueue*Q,QueueData x)QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode);p-data=x;p-link=NULL;if(Q-front=NULL)/空,创建第一个结点 Q-front=Q-rear=p;else Q-rear=Q-rear-link=p;return 1;,int DeQueue(LinkQueue*Q,QueueData,队列的应用举例 逐行打印二项展开式(a+b)i 的系数,杨辉三角形(Pa
21、scals triangle),分析第 i 行元素与第 i+1行元素的关系,从前一行的数据可以计算下一行的数据,0 1 1 0,从第 i 行数据计算并存放第 i+1 行数据,1 2 1 0 1 3 3 1 0 1 4 6,s=0 t=1 t=2 t=1 t=0 t=1 t=3 t=3 t=1 t=0 t=1,s+t s=t s=t s=t s=t s=t s=t s=t s=t,s+t s+t s+t s+t s+t s+t s+t s+t,#include queue.hvoid YANGVI(int n)Queue q;/队列初始化 InitQueue(q);EnQueue(q,1);En
22、Queue(q,1);int s=0,t;,利用队列打印二项展开式系数的程序,for(int i=1;i=n;i+)/逐行计算 printf(“n”);EnQueue(q,0);for(int j=1;j=i+2;j+)/下一行 DeQueue(q,递归的概念,递归的定义 若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程以下三种情况常常用到递归方法。定义是递归的 数据结构是递归的 问题的解法是递归的,例题,例1.请写出二叉树前序遍历的递归算法代码非递归算法代码。,参考递归算法代码int PreTraverse(B
23、iTree T)if(T!=NULL)Visit(T);PreTraverse(T-lchild);PreTraverse(T-rchild);return 0;,参考非递归算法代码int PreTraverse(BiTree T)Stack S;InitStack(S);if(T=NULL)return 0;Push(S,T);while(!EmptyStack(S)Pop(S,T);Visit(T);if(T-rchild!=NULL)Push(S,T-rchild);if(T-lchild!=NULL)Push(S,T-lchild);return 1;,例2.已知入栈序列为1 2 3
24、4 5 6，能否得到出栈序列3 4 2 1 6 5？若能，请设计操作序列（P表示入栈动作，Q表示出栈动作），若不能，请说明原因。,操作序列为：PPPQPQQQPPQQ,串和数组,例题,请用改进KMP算法计算下面两个模式串的nextval值（写出结果nextval值即可）：kkmmppkkmmnextvanext,解：,next,next,特殊矩阵的压缩存储,特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。对称矩阵三对角矩阵,树和二叉树,二叉树遍历,中序遍历结果：a+b*c-d-
25、e/f前序遍历结果：-+a*b-c d/e f后序遍历结果：a b c d-*+e f/-,-,-,/,+,*,a,b,c,d,e,f,二叉树的计数,例,前序序列 ABHFDECKG 和中序序列 HBDFAEKCG,求构造的二叉树。,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树?由二叉树的后序序列和中序序列可唯一地确定一棵二叉树?由二叉树的前序序列和后序序列可唯一地确定一棵二叉树?,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。由二叉树的后序序列和中序序列可唯一地确定一棵二叉树。由二叉树的前序序列和后序序列不可唯一地确定一棵二叉树。,前序序列 ABHFDECKG 中序序列 HBDF
26、AEKCG,C,G,E,H,T1 T2 T3,A,F,B,D,I,J,K,A,F,G,H,K,T1 T2 T3,B,C,D,E,I,J,3 棵树的森林,各棵树的二叉树表示,森林的二叉树表示,森林与二叉树的对应关系,树的遍历,深度优先遍历 先根次序遍历 后根次序遍历广度优先遍历,C,G,A,B,D,E,F,例.已知二叉树中度为2的结点个数为n2，度为1的结点个数为n1，度为0的结点个数为n0。请证明：n2=n0-1。,参考证明如下：设结点数为n，则，除根结点外，每个结点有唯一的父结点，因此总分支数为n-1，因此可得：n=n2+n1+n0n2*2+n1*1+n0*0=n-1综合上述两式，可得n2=
27、n0-1,例.已知一组字符及其权值如下：a:35,b:9,c:19,d:27,e:81,f:14,g:21,h:12,i:25,j:5,k:11,l:8请构造相应的哈夫曼树，画出结果哈夫曼树即可。,参考答案如下：a:35,b:9,c:19,d:27,e:81,f:14,g:21,h:12,i:25,j:5,k:11,l:8,a/35,b/9,c/19,d/27,f/14,g/21,h/12,i/25,j/5,k/11,l/8,e/81,给出二叉树，画出对应的中序线索化二叉树。,图,图的要点,图的存储结构邻接矩阵邻接表结构图的遍历深度优先搜索广度优先搜索最小生成树有向无环图的关键路径最短路径,邻
28、接表结构,例1：写出右图的的邻接矩阵或邻接表。,邻接矩阵,解：邻接矩阵如下,邻接矩阵,邻接表结构,解：邻接表结构如下,图的深度优先搜索,例2：写出其深度优先遍历序。,深度优先遍历序：afedgbc,图的广度优先搜索,例3：写出其广度优先遍历序。,广度优先遍历序：afgedbc,例4：已知一个用邻接表存储的有向图如下，请画出图，并写出该图的深度优先遍历序和广度优先遍历序。,0,1,2,3,4,5,6,7,8,2,3,0,6,1,0,5,0,6,7,9,5,6,9,2,9,8,9,5,8,最小生成树,例5 MST性质证明设无向图N=(V,E),U是顶点V的一个非空子集。若(u,v)是一条具有最小权
29、值的边，其中uU,vV-U，则必存在一棵包含边(u,v)的最小生成树。,MST性质,证明：设N的任何一棵最小生成树都不包含(u,v)，T是一棵最小生成树。,将边(u,v)加入到T中时，由生成树的定义，T必存在一条包含(u,v)的闭合回路。,T上必存在另一条边(u,v)，其中uU,vV-U，且u和u之间，v和v之间均有路径相通。,删去边(u,v)，可消去回路，同时得到另一棵生成树T。,由于(u,v)的代价不高于(u,v)，则T的代价不高于T，T是包含(u,v)的一棵最小生成树，与假设矛盾,最小生成树(Prim算法),E1：任取一个顶点构成U=v0，viV-U；构造向量cost0n-1和adj0n
30、-1，costi表示顶点vi到U的最短边的长度，adji表示顶点vi到U的最短边在U中邻接点的下标；初始时，生成树T为空集。,E2：重复n-1次E21：从V-U中选出cost值最小的顶点vk，将边加入到生成树T中，然后将vk并入U中；E22：修正V-U中各顶点的cost值和adj值；,例6：已知连通网如下图所示，请用Prim算法计算出该连通网的最小生成树（写出计算过程）。,最小生成树(Kruskal算法),E1：将所有的边按权值排序；E2：设每个顶点为一个独立的点集，生成树T为空集；E3：依序扫描每一条边，直到已输出n-1条边：E31：若vi、vj不在同一点集中，则将该边加入生成树T中，并合并
31、这两个点集；否则舍弃该边；,例7：已知连通网如下图所示，请用Kruskal算法计算出该连通网的最小生成树（写出计算过程）。,关键路径,关键路径的计算E1：依拓扑序计算各顶点的最早发生时间ve；E2：依逆拓扑序计算各顶点的最迟发生时间vl；E3：计算每条弧的最早开始时间e和最迟开始时间l，若e等于l，则输出该弧（关键弧）；,例.已知有向无环图如下所示，计算该图的关键路径，并写出计算过程和结果。,0,1,2,3,4,5,6,7,8,5,19,12,17,4,2,7,15,10,6,7,6,参考答案如下：,拓扑序,最短路径,从指定起点到其他各顶点的最短路径（Dijkstra算法）每一对顶点之间的最短
32、路径（Floyd算法）,Dijstra算法,E1：初始化辅助向量D和集合S；Di表示从始点v0到终点vi的较短路径的长度。S为最短路径的终点集合。E2：循环n-1次：E21：从V-S中选择最小的Dj；E22：将vj并入S中;E23：对V-S中的各顶点vi的已知较短路径进行修正：,Dijstra算法,例10：已知带权邻接矩阵：,求v0到其余各点的最短路径。,Floyd算法,E1：初始化从vi到vj的目前已知较短路径为从vi到vj的直达弧；E2：对每两顶点对(vi,vj)依次计算P(i,k,j)，k=0n-1，计算规则为：,P(i,k,j)=min(P(i,k-1,k)+P(k,k-1,j),P(
33、i,k-1,j),例10：已知有向网如下图所示，请用Floyd算法计算各顶点间的最短路径（写出计算过程）。,Floyd算法,例11：已知某带权有向图如下，请用Floyd算法计算图中各顶点间的最短路径，并写出计算过程。,1,2,3,0,1,1,2,3,4,5,P(i,j,0),P(i,j,-),P(i,j,1),P(i,j,2),P(i,j,3),结果如下：,查找和排序,顺序查找,顺序查找（Sequential Search）：又叫线性查找，是最基本的查找技术查找过程：从表中第一个（或最后一个）记录开始，按顺序逐个进行记录的关键字和给定值比较，若某讴歌记录的关键字和给定值相等，则查找成功。如果表
34、中所有记录都比较完后仍未找到，则查找失败,顺序表查找优化,监视哨ASL分析查找成功：ASL=(n+1)/2查找不成功：ASL=(n+1)顺序查找：ASL=1/2*(n+1)/2+1/2*(n+1)=(n+1),折半查找,折半查找（Binary Search）又称为二分查找，要求线性表：记录的关键码有序（通常从小到大）线性表必须采用顺序存储基本思想：取中间记录作为比较对象：若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续二分查找若给定值大于中间记录的关键字，则在中间记录的右半区继续二分查找不断重复上述查找，直到查找成功或所有查找区域无记录，查找失
35、败,折半查找算法实现,性能分析：时间复杂度：O(logn)ASL=log2(n+1)1,二叉搜索（排序）树,二叉排序树（Binary Sort Tree），又称为二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树：若左子树不为空，则左子树上所有节点的值均小于它 的根结点的值若右子树不为空，则右子树上所有节点的值均小于它的根节点的值左、右子树也均为二叉排序树,n 个结点的二叉搜索树的数目【例】3 个结点的二叉搜索树,1,2,2,1,3,3,1,3,2,1,2,3,1,2,3,123 132 213 231 312 321,输入数据 53,78,65,17,87,09,81,15 创建二叉搜
36、索树,平衡二叉树（AVL）,平衡二叉树（Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree）一种二叉排序树每个节点的左子树、右子树的高度差不超过 1平衡因子（Balance Factor）节点的左子树深度减去右子树深度的值，简称BF,失衡：在左子树D上插入新结点使其高度增1，导致结点A的平衡因子增到-2，造成不平衡。为使树恢复平衡，从A沿插入路径连续取3 个结点A、B和D，它们处于一条方向为L的直线上，需要做右单旋转。以结点B为旋转轴，将结点A顺时针旋转,LL型,失衡：在子树E中插入新结点，该子树高度增1
37、导致结点A的平衡因子变成+2，出现不平衡。沿插入路径检查三个结点A、C和E。它们处于方向为L的直线上，需做左单旋转。以结点C为旋转轴，让结点A逆时针旋转。,RR型,LR型,RL型,16,16,例，输入关键码序列为 16,3,7,11,9,26,18,14,15，创建平衡二叉树的过程。,0,3,16,3,-1,0,7,0,1,-2,左右双旋,7,3,16,0,0,0,7,3,11,0,-1,1,7,3,16,16,11,9,0,-1,-2,右单旋,3,7,16,9,0,0,0,1,3,7,11,26,9,16,11,0,1,1,2,2,18,18,0,3,16,3,-1,0,16,0,2,右左双
38、旋,7,3,9,0,0,0,18,26,11,-1,7,3,26,16,11,9,-1,左单旋,9,7,16,14,0,0,1,7,11,26,26,9,1,1,11,15,18,2,3,18,16,-2,左右双旋,7,3,0,0,0,11,7,14,9,-1,16,15,0,1,11,26,26,14,1,-2,9,散列（哈希）方法,散列方法：在表项存储位置与其关键码之间建立一个确定的对应函数关系Hash()，使每个关键码与结构中一个唯一存储位置相对应：Address Hash(Rec.key)在搜索时,先对表项的关键码进行函数计算,把函数值当做表项的存储位置,在结构中按此位置取表项比较。若
39、关键码相等,则搜索成功。否则失败。在存放表项时,依相同函数计算存储位置,并按此位置存放。,冲突及解决策略,散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上，这就产生了冲突常用冲突解决策略开放定址法（线性探测、二次探测、随机探测)二次散列链表法公共溢出区,设一组记录的关键字为：PV1031,TI1104,PV0301,TI0103,PV0012,TI1205存储表为L0.9定义H(key)为key的后四位之和模除10。探测序列为：+1,-1,+2,-2,+3,-3,.,H(PV1031)=5H(TI1104)=6H(
40、PV0301)=4H(TI0103)=4H(PV0012)=3H(TI1205)=8,PV1031,TI1104,PV0301,TI0103,PV0012,TI1205,设一组记录的关键字为：PV1031,TI1104,PV0301,TI0103,PV0012,TI1205存储表为L0.9定义H1(key)为key的后四位之和模除10，定义H2(key)为key的后四位的值模除10。,H1(PV1031)=5H1(TI1104)=6H1(PV0301)=4H2(TI0103)=3H2(PV0012)=2H1(TI1205)=8,PV1031,TI1104,PV0301,TI0103,PV001
41、2,TI1205,设一组记录的关键字为：PV1031,TI1104,PV0301,TI0103,PV0012,TI1205链式存储表为L0.9定义H(key)为key的后四位之和模除10。,H(PV1031)=5H(TI1104)=6H(PV0301)=4H(TI0103)=4H(PV0012)=3H(TI1205)=8,设一组记录的关键字为：PV1031,TI1104,PV0301,TI0103,PV0012,TI1205存储表为L0.9定义H(key)为key的后四位之和模除10。探测序列为：+1,-1,+2,-2,+3,-3,.,H(PV1031)=5H(TI1104)=6H(PV030
42、1)=4H(TI0103)=4H(PV0012)=3H(TI1205)=8,PV1031,TI1104,PV0301,TI0103,PV0012,TI1205,基本表,公共溢出区,装填因子,哈希表的装填因子：=（表中填入的记录数）/（哈希表的长度）标志哈希表的装满程度越小，发生冲突的可能性越小越大，发生冲突的可能性越大不论表的长度有多大,我们总能选择一个合适的装填因子,以把ASL限制在一定范围内。需要装填的记录数是确定的，可以通过扩大哈希表的长度，来降低装填因子，从而避免冲突，减少平均查找长度（ASL），提升查找效率,例.已知一组记录的关键字（0213,2122,0173,2014,5503）
43、，散列表的表长为5，存贮下标为04，请设计一个散列函数，无冲突地将所有记录放入散列表中。,参考答案如下：设关键字key为k0k1k2k3，定义散列函数如下：H(k0k1k2k3)=(k0+k2)%5H(0213)=1,H(2122)=4,H(0173)=2,H(2014)=3H(5503)=0,直接插入排序折半插入排序冒泡排序简单选择排序快速排序堆排序二路归并排序,排序代码要求,37,一次快速排序划分过程,37,33,20,25,89,60,49,68,待排序序列：36,38,22,63,39,21,16,47,98,52,19,70,建堆,排序,THE END,Thank YOU ALL,计算机系 江志英,
