数据结构复习汇编课件

数据结构

韩萍muziq@数据结构韩萍数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。数据结构分为逻辑结构和存储结构（物理结构）数据结构(DataStructure)：是相互之间存在一种数据的逻辑结构：数据元素之间的逻辑关系，分：集合——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图或网概念及术语数据的逻辑结构：概念及术语数据的存储结构数据的逻辑结构在计算机存储设备中的映射，分：顺序存储结构、链式存储结构。顺序存储：以相对的存储位置表示逻辑关系

链式存储以以附加指针表示后继关系a1a2a3a2

a1概念及术语数据的存储结构顺序存储：a1a2a3a2a§１．2算法和算法分析算法概念

对特定问题求解步骤的一种描述，是指令的有限序列，每条指令表示一个或多个操作。算法应具备的特性：（2）

确定性：指令具有确切的含义，相同的输入有相同的输出。（1）有穷性：对合法的输入值在执行有穷步之后结束。（3）可行性：所有操作可经已实现的基本运算执行有限次来实现（4）

输入：0个或多个（5）

输出：一个或多个§１．2算法和算法分析算法概念

对（2）可读性：便于阅读和交流

（3）健壮性：能够对输入的非法数据作出反应和处理

（4）效率与低存储量需求：效率指算法的执行时间；存储量需求指算法执行过程中所需要的最大存储空间。算法设计的要求（1）正确性：算法应满足具体问题的需求。

a.程序不含语法错误

b.对于几组输入可得满足要求的结果

c.对于精心选择的几组典型、苛刻、带有刁难性的输入数据可得满足要求的结果

d.对一切合法的输入数据都能得出产生要求的结果

（2）可读性：便于阅读和交流

（3）健壮性：能够对输入算法效率的度量算法的时间效率主要由两个因素决定：l所需处理问题的数据量大小，数据量大，所花费的时间就多；l在解决问题的过程中，基本操作的执行次数时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数，T(n)=O(f(n))

好的算法应该能够在数据量n增长的同时，函数T(n)的增长速度比较缓慢。算法效率的度量

常见函数的增长率常见函数的增长率一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。总时间由一个常数(即零次多项式)来限界。一个时间为O(n2)的算法由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。关系为:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指数时间的关系为：O(2n)<O(n!)<O(nn)一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的

第二章数据结构复习汇编课件线性表：是n≥0个性质相同的数据元素的有限序列。线性表可记作（a1,a2,…,an

）n≥0基本操作： 建立、存取、插入、删除、检索、分解、排序等。

线性表：是n≥0个性质相同的数据元素的有限序列。线性表可记作

(a1,…,ai-1,ai,…,an)改变为

(a1,…,ai-1,e,ai,…,an)a1a2

…ai-1ai

…ana1a2

…ai-1

…aiean表的长度加1基本运算在线性表第i（1≤i≤n+1）个位置上插入元素e(a1,…,ai-1,ai,…,an)改变为a注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是l.elem[i-1]。statusinsert_sq(Sqlist&L，elemtypee，inti){if(i<1||i>L.length+1)//检查i值是否合理

returnERROR; if(L.length>=ListSize)//判断是否溢出

exit(overflow);for(j=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j];//腾出第i个位置

L.elem[i-1]=e; //插入

L.length++; //当前表长加1returnOK;}注意：C语言中的数组下标从“0”开始，因此，若L是Sqlis

这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环的元素后移语句上，所需移动元素的次数不仅依赖于表的长度，而且还与插入位置有关。

i位置 移动次数

1 n 2 n-1 ︰ ︰ i n-i+1 n+1 0平均移动次数：时间复杂度：O（n）这里的问题规模是表的长度，设它的值为n。该算法的时间

(a1,…,ai-1,ai,ai+1,…,an)改变为

(a1,…,ai-1,ai+1,…,an)ai+1…an表的长度减1a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

在线性表中删除第i（1≤i≤n）个元素，使(a1,…,ai-1,ai,ai+1,…,anstatusdelete_sq(Sqlist&L,inti,elemtype&e){if(i<1||i>L.length)//检查i值是否合理

returnERROR; e=L.elem[i-1];//C下标从0开始

for(j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j];//删除

L.length--; returnOK;}statusdelete_sq(Sqlist&L,int该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。

i位置 移动次数

1 n-1 2 n-2 ︰ ︰ i n-i n 0平均移动次数：时间复杂度：O（n）该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和第三章栈和队列栈和队列也可以被称作为操作受限的线性表。第三章栈和队列栈和队列也可以被称作为操作受限的线性表。思考：假设有A,B,C三个元素进S栈的顺序是A,B,C，写出所有可能的出栈序列。CBAACBABCCABBACBCA思考：假设有A,B,C三个元素进S栈的顺序是A,B,C，CB栈属于加了限制条件的线性结构；栈是后进先出的线性表；进栈和出栈只能从栈顶进行；栈中的元素个数可以是0（空栈）；栈的元素的个数不能是无穷多个；每个栈中的元素的类型相同.栈的特性栈属于加了限制条件的线性结构；栈的特性队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。3.2队列(

Queue)

3.2.1队列的定义及其运算队列（queue）是一种只允许在一端进行插入，而在另一端进行定义允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,FirstInFirstOut)a0

a1

a2

an-1frontrear定义a0a1a2an依次123456删除两个元素之后的头元素是？依次123456删除两个元素之后的头第四章串

零个或多个字符组成的有限序列。一般记S=‘a1a2....an’其中，S是串名，单引号括起的字符序列是串值；

2、串长

串中所包含的字符个数

3、空串长度为零的串，它不包含任何字符。

1、串4、空格串由一个或多个空格组成的串，其长度为串中空格字符的个数。

第四章串零个或多个字符组成的有限第五章数据结构复习汇编课件§5.3广义表的定义一、广义表（GeneralList）广义表中的元素即可以是单个元素（称为原子）也可以是广义表（称为子表）。一般表示：LS=(a1,a2,…,an

)习惯上广义表名用大写字母，原子用小写字母当LS非空时，a1称为LS

的表头（head），其余元素组成的表（a2,…,an

）称为表尾（tail）。§5.3广义表的定义例：A=() B=(e)C=(a,(b,c,d))D=(A,B,C)E=(a,E)F=(a,b,(c,(d)))广义表特点：允许递归，可共享子表元素不仅有先后次序，而且有层次关系元素的层次：是包括该元素的括号对数表深：广义表中元素的最大层次例：广义表的存储结构（通常用链式）广义表的扩展线性链表存储typedefstructglnode{ inttag;//0原子结点；1子表结点

union{ atomtypeatom;//原子结点的值域

structglnode*hp;//子表表头指针

} structglnode*next;//下一元素指针}*glist;广义表的存储结构（通常用链式）例：A=();B=(e);C=(a,(b,c,d));D=(A,B,C);E=(a,E)

都设一附加表头结点1^^A1^B0e^1^C0a1^0b0c0d^1^1^11^D1^0a1^E例：A=();B=(e);C=(a,(b,c,d));作业练习求下列广义表操作的结果：GetHead【(p,h,w)】；GetTail【(b,k,p,h)】；GetHead【((a,b),(c,d))】；GetTail【((a,b),(c,d))】；GetHead【GetTail【((a,b),(c,d))】】GetTail【GetHead【((a,b),(c,d))】】GetHead【GetTail【GetHead【((a,b),(c,d))】】】GetTail【GetHead【GetTail【((a,b),(c,d))】】】作业练习求下列广义表操作的结果：第六章数据结构复习汇编课件ABCDEFGHK例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A二叉树的遍历层次序列：ABECFDG

HKABCDEFGHK例如：先序序列：中序序列：后序序列：AB5.3.2根据二叉树的遍历构造二叉树3结点的5棵二叉树的3种遍历序列如表所示。存在情况:ABCABCABCABCCAB5.3.2根据二叉树的遍历构造二叉树3结点的5棵二叉树的3种因此，对3种遍序序列有结论：（1）由先序遍历序列和中序遍历序列能够唯一确定一棵二叉树。（2）由后序遍历序列和中序遍历序列能够唯一确定一棵二叉树。（3）由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。因此，对3种遍序序列有结论：例如：已知二叉树BT的后序遍历序列为：CBEHGIFDA，中序遍历序列为：BCAEDGHFI，请构造这棵二叉树T。ABCDEFGHIADEFGHIBCFGHIABCDEGHABCDEFIABCDEFHGI由中序遍历序列和后序遍历序列构造二叉树的过程示意例如：已知二叉树BT的后序遍历序列为：CBEHGIFDA，中平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：(1)左、右子树都是平衡二叉树；(2)左、右子树高度差的绝对值<=1。若把左子树与右子树高度之差称为结点x的平衡因子(balancefactor)，用bf(x)表示。则由平衡二叉树定义知:Bf(x)=x左子树深度-x右子树深度1.平衡二叉树的定义平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：191000065504741853060727842-330-202141853060727842-1110010a.非平衡二叉树b.平衡二叉树所有结点的平衡因子只能取-1，0，1三个值之一。91000065504741853060727842-3306.2堆排序堆是一棵顺序存储的完全二叉树，若每个结点的关键字都不小（大）于其孩子结点的关键字，则称为大（小）根堆。9683381127912368547243053916.2堆排序堆是一棵顺序存储的完全二叉树，若每个结点的关堆排序的基本思想是：首先，按堆的定义将R[1..n]调整为堆（这个过程称为初始建堆），交换R[1]和R[n]；然后，将R[1..n-1]调整为堆，交换R[1]和R[n-1]；如此反复进行，直到交换了R[1]和R[2]为止。堆排序的基本思想是：首先，按堆的定义将R[1..n]调整为堆6.3.1哈夫曼树的定义设二叉树具有n个带权值的叶子结点，那么从根结点到各个叶子结点的路径长度li与相应结点权值wi的乘积的和，称为二叉树的带权路径长度，记作：

WPL=1×3+3×3+2×2+4×1=20。6.3.1哈夫曼树的定义设二叉树具有n个带权值的叶子结点6.3.2哈夫曼树的构造（1）由给定的n个权值{W1,W2,…,Wn}构造n棵只有一个叶子结点的二叉树，从而得到一个二叉树的集合F={T1,T2,…,Tn}。（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，新二叉树根结点的权值为其左、右子树根结点权值之和。6.3.2哈夫曼树的构造（1）由给定的n个权值{W1,W（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中。（4）重复（2）、（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。注：如此建造的二叉树，没有度为1的结点。如有n个叶子，必有m=2n-1个结点。（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的9例如:已知权值W={5,6,2,9,7}5627527697671395279例如:已知权值W={5,6,2,9,7}567139527952716671329WPL=(6+7+9)*2+(5+2)*3=22*2+7*3=44+21=65注意：1.只算叶子2.分层计算3.路径长为层数减167139527952716671329WPL=(6+7+9

快速远距传输电文时，为使电文尽量短，采用不等长编码，且使用频高的字符用较短的码。并且使任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。

利用赫夫曼树可以构造出一种最优前缀编码使所传电文的总长度最短,这种编码就是赫夫曼编码。6.3.3赫夫曼编码快速远距传输电文时，为使电文尽量短，采用不等

例：已知某通信息流只用8种字符，出现频率为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计赫夫曼编码。设W=(5,29,7,8,14,23,3,11),n=8,则m=15.351123714291111111000000080010010110011301117111081111例：已知某通信息流只用8种字符，出现频率为0.05，0.2哈夫曼树和编码的代码实现序号权重父号左子右子172193246532637218109101112131415W={7,19,2,6,32,3,21,10}N=8m=2*8-1=159953610101194111117181212281011131340271414601251515100131410010210300000400015016000017118001112345678哈夫曼树和编码的代码实现序号权重父号左子右子17219324第7章图

7.1图的基本概念

7.1.1图的定义图是一种非线性结构,它比树形结构更复杂.图中的数据元素之间是多对多关系,每一个元素都可能与其他元素有关.图是由一个非空的顶点集合和一个描述顶点之间关系即边（或者弧）的集合组成.第7章图

7.1图的基本概念

7.1.1图7.2图的存储结构

7.2.1邻接矩阵邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是n阶方阵定义A：若G是网，则邻接矩阵可定义为：7.2图的存储结构

7.2.1邻接矩阵邻接矩阵是表Aij={0(i,j)VR1(i,j)VRBACDFE例如:矩阵的元素为ABCDEFABCDEF无向图----对称矩阵，半存即可，节省空间。每行(列)数字和即是顶点的度Aij={0(i,j)VR1(i,j)VRBAC有向图的邻接矩阵为非对称矩阵ABECDABCDEABCDE行和为出度列和为入度有向图的邻接矩阵为非对称矩阵ABECDABCDEABCDE行有向网的邻接矩阵为非对称矩阵ABECDABCDEABCDE1217315有向网的邻接矩阵为非对称矩阵ABECDABCDEABCDE17.3.2深度优先搜索深度优先搜索的基本思想是：从图G中某个顶点vi出发，访问vi，然后选择一个与vi相邻且没被访问过的顶点v访问，再从v出发选择一个与v相邻且未被访问的顶点vj访问，依次继续。7.3.2深度优先搜索深度优先搜索的基本思想是：如果当前已访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点w，从w出发按同样方法向前遍历。直到图中所有顶点都被访问。如果当前已访问过的顶点的所有邻接顶点都已被访问，则回退到已被

从图中某个顶点V0

出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有都被访问到。为确定每一个结点是否被访问，必须设置访问标志。一、连通图的深度优先搜索遍历从图中某个顶点V0出发，访问此顶点，然后依次achdekf8234570FFFFFFFFF012345678TTTTTTTachdkfeachkfed访问标志:访问次序:例如:achdkfeachdekf8234570FFFF7.4最小生成树在一个无向连通图G中，如果取它的全部顶点和一部分边构成一个子图G'，即：V(G')=V(G)和E(G')E(G)若边集E(G‘)中的边，既将图G中的所有顶点连通，又不形成回路，则称子图G'是原图G的一棵生成树。产生最小生成树主要有两个算法，即普里姆算法和克鲁斯卡尔算法。7.4最小生成树在一个无向连通图G中，如果取它的全部顶点7.4.2

普里姆算法普里姆(Prim)算法的思路是：假设G=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空。7.4.2普里姆算法普里姆(Prim)算法的思路是：假设算法开始时，首先从V中任取一个顶点（假定取v0），将它并入U中，此时U={v0}，然后只要U是V的真子集（即UV），就从那些其一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短（即权值最小）边，假定为(vi,vj)，其中vi∈U，vj∈V-U，并把该边(vi,vj)和顶点vj分别并入T的边集TE和顶点集U。算法开始时，首先从V中任取一个顶点（假定取v0），将它并入UV0V3V5V2V1V46453821756V01V2closedge

i12345AdjvexLowcostV0V1V2V3V4V5V0V1V2V3V4V5v06v01v070v25v26v2440V5v55v5220V350V1v1330V41+4+2+5+3=15例如：UV-UV0V3V5V2V1V46453821756V01V2clo7.7AOE网与关键路径若在带权的有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销（如该活动所需的时间），则称此带权的有向图为用边表示活动的网络，简称AOE网（ActivityOnEdgenetwork）。7.7AOE网与关键路径若在带权的有向图中，以顶点表示事在一个表示工程的AOE网中，应该不存在回路，网中仅存在一个入度为0的顶点（事件），称为开始顶点（源点），它表示了整个工程的开始；网中也仅存在一个出度为0的顶点（事件），称为结束顶点（汇点），它表示整个工程的结束。在一个表示工程的AOE网中，应该不存在回路，网中仅存在一个入在寻找关键活动时所用到的几个参量的定义：（1）事件vk的最早发生时间（2）事件vk的最迟发生时间（3）活动ai的最早开始时间（4）活动ai的最迟开始时间在寻找关键活动时所用到的几个参量的定义：因AOV网中的活动可以并行，故工程完成的最短时间为从源点到汇点的最长路径(关键路径)。abcdefghk64521187244例如:“关键活动”是：关键路径上的活动，权值增加

将使有向图上的最长路径的长度增加。源点汇点6174关键路径a-b-e-h-k因AOV网中的活动可以并行，故工程完成的最短时间为从源点到汇把从源点到顶点j的最长路径长度叫做事件(顶点)的最早发生时间ve(j);它是可能发生的最早时间。把从顶点k到汇点的最短路径长度叫做事件(顶点)的最迟发生时间vl(k).它是在不推迟工期的前提下最迟必须开始的时间。把从源点到顶点j的最长路径长度叫做事件(顶点)的最早发生

事件发生时间的计算公式:ve(源点)=0;ve(k)=Max{ve(j)+dut(<j,k>)}例如：

ve(k)=18,ve(h)=14,ve(f)=7;vl(汇点)=ve(汇点);vl(j)=Min{vl(k)–dut(<j,k>)}例如:vl(k)=18,vl(h)=14,vl(f)=10。事件发生时间的计算公式:设第i条弧为<j,k>则对第i项活动言,“活动(弧)”的最早开始时间e(i)e(i)=ve(j);e(<h,k>)=14;e(<f,h>)=7;“活动(弧)”的最迟开始时间l(i)l(i)=vl(k)–dut(<j,k>);l(<h,k>)=14;e(<f,h>)=10。jkdut设第i条弧为<j,k>则对第i项活动言,jk

什么是“关键活动”？该活动的最早开始时间

=该活动的最迟开始时间<h,k>在关键路径上,e(h,k)=l(h,k),<f,h>不在关键路径上e(f,h)=7,l(f,h)=10

，推迟开始或延迟3天均不影响工期。什么是“关键活动”？该活动的最早开始时间<h,k>在关键abcdefghk6452118724400000000064571157151418181818181818181818161486610807拓扑有序序列:a-d-f-c-b-e-h-g-kabcdefghk6452118724400000000060645771514181814161078660000645777151414160236688710064577151418181416107866000064

算法的实现要点:显然，求ve的顺序应该是按拓扑有序的次序;

而求vl的顺序应该是按拓扑逆序的次序;因为拓扑逆序序列即为拓扑有序序列的逆序列，因此应该在拓扑排序的过程中，另设一个“栈”记下拓扑有序序列。算法的实现要点:显然，求ve的顺序应该是按拓扑有序的次序;8.2二分查找所谓有序表,即表中的各元素按关键字的值升序(或降序)存放。折半查找又称二分查找,是查找有序表的简单、有效的常用方法。基本思想：设低高端指针为L、H,则选取中间记录M=(L+H)/2,将其关键字与给定关键字k进行比较,若相等,则查找成功；8.2二分查找所谓有序表,即表中的各元素按关键字的否则,若k值比表中关键字值大,则令L=M+1,H不变,在表的后半部分继续对右子表进行折半查找；若k值比表中关键字值小,则令H=M-1,L不变,继续对左子表进行折半查找。每进行一次比较,要么找到要查找的元素,要么将查找的范围缩小一半。如此递推,直到查找成功或把要查找的范围缩小为空（查找失败）。否则,若k值比表中关键字值大,则令L=M+1,H不变,在表的LHMK=210123456789102.指针：L=0H=4M=[(L+H)/2]=2HM3.指针：L=3H=4M=[(L+H)/2]=3LM查找过程构成描述折半查找的判定树，当前的M作根，左子表的M作为左子树的根，右子表的M作为右子树的根，…

，若n=11，则判定树如下。可看出中序遍历判定树与表序相同，其查找次数恰好等于层数。528036914710L=0,H=10M=5L=6,H=10M=8L=0,H=4M=2L=0,H=1M=0L=9,H=10M=9L=3,H=4M=3L=6,H=7M=6L=1,H=1M=1L=4,H=4M=4L=7,H=7M=7L=10,H=10M=10例:5,13,19,21,37,56,64,75,80,88,92）LHMK=21012例:5,13,19,21,37,56,64,75,80,88,92）1.指针：L=0H=10M=[(L+H)/2]=5LHMK=850123456789102.指针：L=6H=10M=[(L+H)/2]=8M3.指针：L=9H=10M=[(L+H)/2]=9L4.指针：L=9H=8H<L失败LM不难看出：如果把建造的描述折半查找的判定树中所有结点的空指针域上加一个指向称为外部结点的方形结点的指针。则失败时必指向外部指针，所以比较次数也不会超过层数。528036914710<02-35-68-90-13-46-79-101-24-57-8>10例:5,13,19,21,37,56,64,75,80,88

折半查找算法intBinSearch(LineListR[],intn,KeyTypek){intlow=0,hight=n-1,mid;while(low<=hight){mid=(low+hight)/2;if(k==R[mid].key)returnmid;elseif(k<R[mid].key)hight=mid-1;elselow=mid+1;}return-1;}//Search_Bin折半查找算法算法分析：在二分查找过程中，关键字与k每比较一次查找范围就缩小一半。因为比较次数等于元素所在层数h，而h层最多有2h-1个元素，设有序表中元素个数为n，则有则二分查找的最大查找长度为：算法分析：在二分查找过程中，关键字与k每比较一次查找范围就缩二分查找的平均查找长度为O(log2n)，比顺序查找速度快。因故课本错误，请照此修改p168中二分查找的平均查找长度为O(log2n)，比顺序查找速度快。7.5哈希表查找

7.5.1哈希表查找的基本概念哈希表查找的思想，它通过对元素的关键字值进行某种运算，直接求出元素的地址，即使用关键字到地址的直接转换方法，而不需要反复比较。因此，哈希表查找法又叫杂凑法或散列法。7.5哈希表查找

7.5.1哈希表查找的基本概念哈用一个函数H把数据集中的n个结点的关键字唯一地转换成0..m-1范围内的数值，即对任意结点的关键字ki，有：0≤H(ki)≤m-1（0≤i≤n-1）H(ki)是表与元素关键字之间映射关系的函数，称为哈希函数。构造哈希函数和建立解决冲突的方法是两个主要任务。用一个函数H把数据集中的n个结点的关键字唯一地转换成0..m假定某教室有35个座位，哈希法则要限定学生所坐的位置应与其学号的末两位相同，则学号为0601605的学生应坐编号为5的座位。这样我们要找某个学生时只需根据其学号的末两位到相应座位上去找即可，不必一一比较了。在这个例子里，学生好比记录，学号则为关键字，对关键字进行的操作----哈希函数则是取其末两位，用以确定记录的位置。假定某教室有35个座位，哈希法则要限定学生所坐的位置应与其学不同的关键字可能得到同一哈希地址，这种现象称冲突。具有同一地址的关键字称作同义词。应该尽可能地避免冲突的发生。总之，哈希表就是根据设定的哈希函数和处理冲突的方法将一组关键字映像到一个有限的连续地址上，并以此地址作为存储地址的表。这一映像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。不同的关键字可能得到同一哈希地址，这种现象称冲突。具有同一地7.5.2哈希函数的构造方法一个好的哈希函数能将给定的数据集均匀地映射到给定的地址区间中。构造哈希函数的常用方法：1.直接定值法H(ki)=a*ki+b,例如按序号的若干倍加上一个常数存储。7.5.2哈希函数的构造方法2.数字分析法取关键字中某些取值较分散的数字位作为散列地址。再如取下列各元素的第6位和第7位：{100011211，100011322，100011413，100011556，100011613，100011756，100011823}的散列地址分别是：12，13，14，15，16，17，18。2.数字分析法3.除留余数法H（k）=kmodm,如学号后两位。4.平方取中法取关键字平方的中间几位。5.折叠法把关键字分割成位数相同的几段，求叠加和，舍去进位。例如书号0-442-20586-4折叠5864+0224+04=60923.除留余数法7.5.3哈希冲突的解决方法在哈希表中，虽然冲突很难避免，但发生冲突的可能性却有大有小。这主要与三个因素有关：（1）与装填因子有关。（2）与所采用的哈希函数有关。（3）与哈希冲突函数有关。n-已填，m-空间7.5.3哈希冲突的解决方法在哈希表中，虽然冲突很难避免几种常用的解决哈希冲突的方法：1．开放地址法（1）线性探测再散列（2）二次探测再散列（3）随机探测再散列2．链地址法^^几种常用的解决哈希冲突的方法：^^3.性能分析查找成功时的平均查找长度是指查找到表中已有表项的平均探查次数，它是找到表中各个已有表项的探查次数的平均值。而查找不成功的平均查找长度是指在表中查找不到待查的表项，但找到插入位置的平均探查次数，它是表中所有可能散列的位置上要插入新元素时为找到空位置的探查次数的平均值。3.性能分析表7.2列出了用几种不同的方法解决冲突时哈希表的平均查找长度。从中可以看到，哈希表的平均查找长度不是对象个数n的函数，而是装填因子的函数。因此，在设计哈希表时可选择控制哈希表的平均查找长度。表7.2列出了用几种不同的方法解决冲突时哈希表的平均查找长度8.4.2快速排序快速排序是由冒泡排序改进而得的，它的基本思想是：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录放入最终位置后，整个数据区间被此记录分割成两子区间。所有关键字比该记录关键字小的放置在前子区间中，所有比它大的放置在后子区间中，并把该记录排在这两个子区间的中间，这个过程称为一趟快速排序。8.4.2快速排序快速排序是由冒泡排序改进而得的，它的基之后对所有的两个子区间分别重复上述过程，直至每个子区间内只有一个记录为止。简而言之，每趟排序使表的第一个元素入终位，将数据区间一分为二，对于子区间按递归方式继续这种划分，直至划分的子区间长为1。快速排序算法的时间复杂度是O(nlog2n),而且快速排序是不稳定的。之后对所有的两个子区间分别重复上述过程，直至每个子区间内只有[273813[49]76976549]图示一次划分过程。方括号表示无序区，方框表示基准，它未参加真正的交换，只是在划分完成时才将它放入正确的位置上。初始关键字[[49]38659776132749]ijj向左扫描j第一次交换后[273865977613[]49]iji向右扫描i第二次交换后[2738[]9776136549]jij向左扫描j第三次交换后

[2738139776[]6549]]iji向右扫描i第四次交换后

[273813[]76976549]j向左扫描定位jij[273813[49]76976初始关键字：[49386597761327]一趟排序后：[273813]49[769765]二趟排序后：[13]27[38]49[65]76[97]三趟排序后：13273849[65]7697最后结果：13273849657697初始关键字：[493865977613数据结构

韩萍muziq@数据结构韩萍数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。数据结构分为逻辑结构和存储结构（物理结构）数据结构(DataStructure)：是相互之间存在一种数据的逻辑结构：数据元素之间的逻辑关系，分：集合——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图或网概念及术语数据的逻辑结构：概念及术语数据的存储结构数据的逻辑结构在计算机存储设备中的映射，分：顺序存储结构、链式存储结构。顺序存储：以相对的存储位置表示逻辑关系

链式存储以以附加指针表示后继关系a1a2a3a2

a1概念及术语数据的存储结构顺序存储：a1a2a3a2a§１．2算法和算法分析算法概念

对特定问题求解步骤的一种描述，是指令的有限序列，每条指令表示一个或多个操作。算法应具备的特性：（2）

确定性：指令具有确切的含义，相同的输入有相同的输出。（1）有穷性：对合法的输入值在执行有穷步之后结束。（3）可行性：所有操作可经已实现的基本运算执行有限次来实现（4）

输入：0个或多个（5）

输出：一个或多个§１．2算法和算法分析算法概念

对（2）可读性：便于阅读和交流

（3）健壮性：能够对输入的非法数据作出反应和处理

（4）效率与低存储量需求：效率指算法的执行时间；存储量需求指算法执行过程中所需要的最大存储空间。算法设计的要求（1）正确性：算法应满足具体问题的需求。

a.程序不含语法错误

b.对于几组输入可得满足要求的结果

c.对于精心选择的几组典型、苛刻、带有刁难性的输入数据可得满足要求的结果

d.对一切合法的输入数据都能得出产生要求的结果

（2）可读性：便于阅读和交流

（3）健壮性：能够对输入算法效率的度量算法的时间效率主要由两个因素决定：l所需处理问题的数据量大小，数据量大，所花费的时间就多；l在解决问题的过程中，基本操作的执行次数时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数，T(n)=O(f(n))

好的算法应该能够在数据量n增长的同时，函数T(n)的增长速度比较缓慢。算法效率的度量

常见函数的增长率常见函数的增长率一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。总时间由一个常数(即零次多项式)来限界。一个时间为O(n2)的算法由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。关系为:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指数时间的关系为：O(2n)<O(n!)<O(nn)一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的

第二章数据结构复习汇编课件线性表：是n≥0个性质相同的数据元素的有限序列。线性表可记作（a1,a2,…,an

）n≥0基本操作： 建立、存取、插入、删除、检索、分解、排序等。

线性表：是n≥0个性质相同的数据元素的有限序列。线性表可记作

(a1,…,ai-1,ai,…,an)改变为

(a1,…,ai-1,e,ai,…,an)a1a2

…ai-1ai

…ana1a2

…ai-1

…aiean表的长度加1基本运算在线性表第i（1≤i≤n+1）个位置上插入元素e(a1,…,ai-1,ai,…,an)改变为a注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是l.elem[i-1]。statusinsert_sq(Sqlist&L，elemtypee，inti){if(i<1||i>L.length+1)//检查i值是否合理

returnERROR; if(L.length>=ListSize)//判断是否溢出

exit(overflow);for(j=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j];//腾出第i个位置

L.elem[i-1]=e; //插入

L.length++; //当前表长加1returnOK;}注意：C语言中的数组下标从“0”开始，因此，若L是Sqlis

这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环的元素后移语句上，所需移动元素的次数不仅依赖于表的长度，而且还与插入位置有关。

i位置 移动次数

1 n 2 n-1 ︰ ︰ i n-i+1 n+1 0平均移动次数：时间复杂度：O（n）这里的问题规模是表的长度，设它的值为n。该算法的时间

(a1,…,ai-1,ai,ai+1,…,an)改变为

(a1,…,ai-1,ai+1,…,an)ai+1…an表的长度减1a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

在线性表中删除第i（1≤i≤n）个元素，使(a1,…,ai-1,ai,ai+1,…,anstatusdelete_sq(Sqlist&L,inti,elemtype&e){if(i<1||i>L.length)//检查i值是否合理

returnERROR; e=L.elem[i-1];//C下标从0开始

for(j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j];//删除

L.length--; returnOK;}statusdelete_sq(Sqlist&L,int该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。

i位置 移动次数

1 n-1 2 n-2 ︰ ︰ i n-i n 0平均移动次数：时间复杂度：O（n）该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和第三章栈和队列栈和队列也可以被称作为操作受限的线性表。第三章栈和队列栈和队列也可以被称作为操作受限的线性表。思考：假设有A,B,C三个元素进S栈的顺序是A,B,C，写出所有可能的出栈序列。CBAACBABCCABBACBCA思考：假设有A,B,C三个元素进S栈的顺序是A,B,C，CB栈属于加了限制条件的线性结构；栈是后进先出的线性表；进栈和出栈只能从栈顶进行；栈中的元素个数可以是0（空栈）；栈的元素的个数不能是无穷多个；每个栈中的元素的类型相同.栈的特性栈属于加了限制条件的线性结构；栈的特性队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。3.2队列(

Queue)

3.2.1队列的定义及其运算队列（queue）是一种只允许在一端进行插入，而在另一端进行定义允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,FirstInFirstOut)a0

a1

a2

an-1frontrear定义a0a1a2an依次123456删除两个元素之后的头元素是？依次123456删除两个元素之后的头第四章串

零个或多个字符组成的有限序列。一般记S=‘a1a2....an’其中，S是串名，单引号括起的字符序列是串值；

2、串长

串中所包含的字符个数

3、空串长度为零的串，它不包含任何字符。

1、串4、空格串由一个或多个空格组成的串，其长度为串中空格字符的个数。

第四章串零个或多个字符组成的有限第五章数据结构复习汇编课件§5.3广义表的定义一、广义表（GeneralList）广义表中的元素即可以是单个元素（称为原子）也可以是广义表（称为子表）。一般表示：LS=(a1,a2,…,an

)习惯上广义表名用大写字母，原子用小写字母当LS非空时，a1称为LS

的表头（head），其余元素组成的表（a2,…,an

）称为表尾（tail）。§5.3广义表的定义例：A=() B=(e)C=(a,(b,c,d))D=(A,B,C)E=(a,E)F=(a,b,(c,(d)))广义表特点：允许递归，可共享子表元素不仅有先后次序，而且有层次关系元素的层次：是包括该元素的括号对数表深：广义表中元素的最大层次例：广义表的存储结构（通常用链式）广义表的扩展线性链表存储typedefstructglnode{ inttag;//0原子结点；1子表结点

union{ atomtypeatom;//原子结点的值域

structglnode*hp;//子表表头指针

} structglnode*next;//下一元素指针}*glist;广义表的存储结构（通常用链式）例：A=();B=(e);C=(a,(b,c,d));D=(A,B,C);E=(a,E)

都设一附加表头结点1^^A1^B0e^1^C0a1^0b0c0d^1^1^11^D1^0a1^E例：A=();B=(e);C=(a,(b,c,d));作业练习求下列广义表操作的结果：GetHead【(p,h,w)】；GetTail【(b,k,p,h)】；GetHead【((a,b),(c,d))】；GetTail【((a,b),(c,d))】；GetHead【GetTail【((a,b),(c,d))】】GetTail【GetHead【((a,b),(c,d))】】GetHead【GetTail【GetHead【((a,b),(c,d))】】】GetTail【GetHead【GetTail【((a,b),(c,d))】】】作业练习求下列广义表操作的结果：第六章数据结构复习汇编课件ABCDEFGHK例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A二叉树的遍历层次序列：ABECFDG

HKABCDEFGHK例如：先序序列：中序序列：后序序列：AB5.3.2根据二叉树的遍历构造二叉树3结点的5棵二叉树的3种遍历序列如表所示。存在情况:ABCABCABCABCCAB5.3.2根据二叉树的遍历构造二叉树3结点的5棵二叉树的3种因此，对3种遍序序列有结论：（1）由先序遍历序列和中序遍历序列能够唯一确定一棵二叉树。（2）由后序遍历序列和中序遍历序列能够唯一确定一棵二叉树。（3）由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。因此，对3种遍序序列有结论：例如：已知二叉树BT的后序遍历序列为：CBEHGIFDA，中序遍历序列为：BCAEDGHFI，请构造这棵二叉树T。ABCDEFGHIADEFGHIBCFGHIABCDEGHABCDEFIABCDEFHGI由中序遍历序列和后序遍历序列构造二叉树的过程示意例如：已知二叉树BT的后序遍历序列为：CBEHGIFDA，中平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：(1)左、右子树都是平衡二叉树；(2)左、右子树高度差的绝对值<=1。若把左子树与右子树高度之差称为结点x的平衡因子(balancefactor)，用bf(x)表示。则由平衡二叉树定义知:Bf(x)=x左子树深度-x右子树深度1.平衡二叉树的定义平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：191000065504741853060727842-330-202141853060727842-1110010a.非平衡二叉树b.平衡二叉树所有结点的平衡因子只能取-1，0，1三个值之一。91000065504741853060727842-3306.2堆排序堆是一棵顺序存储的完全二叉树，若每个结点的关键字都不小（大）于其孩子结点的关键字，则称为大（小）根堆。9683381127912368547243053916.2堆排序堆是一棵顺序存储的完全二叉树，若每个结点的关堆排序的基本思想是：首先，按堆的定义将R[1..n]调整为堆（这个过程称为初始建堆），交换R[1]和R[n]；然后，将R[1..n-1]调整为堆，交换R[1]和R[n-1]；如此反复进行，直到交换了R[1]和R[2]为止。堆排序的基本思想是：首先，按堆的定义将R[1..n]调整为堆6.3.1哈夫曼树的定义设二叉树具有n个带权值的叶子结点，那么从根结点到各个叶子结点的路径长度li与相应结点权值wi的乘积的和，称为二叉树的带权路径长度，记作：

WPL=1×3+3×3+2×2+4×1=20。6.3.1哈夫曼树的定义设二叉树具有n个带权值的叶子结点6.3.2哈夫曼树的构造（1）由给定的n个权值{W1,W2,…,Wn}构造n棵只有一个叶子结点的二叉树，从而得到一个二叉树的集合F={T1,T2,…,Tn}。（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，新二叉树根结点的权值为其左、右子树根结点权值之和。6.3.2哈夫曼树的构造（1）由给定的n个权值{W1,W（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中。（4）重复（2）、（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。注：如此建造的二叉树，没有度为1的结点。如有n个叶子，必有m=2n-1个结点。（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的9例如:已知权值W={5,6,2,9,7}5627527697671395279例如:已知权值W={5,6,2,9,7}567139527952716671329WPL=(6+7+9)*2+(5+2)*3=22*2+7*3=44+21=65注意：1.只算叶子2.分层计算3.路径长为层数减167139527952716671329WPL=(6+7+9

快速远距传输电文时，为使电文尽量短，采用不等长编码，且使用频高的字符用较短的码。并且使任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。

利用赫夫曼树可以构造出一种最优前缀编码使所传电文的总长度最短,这种编码就是赫夫曼编码。6.3.3赫夫曼编码快速远距传输电文时，为使电文尽量短，采用不等

例：已知某通信息流只用8种字符，出现频率为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计赫夫曼编码。设W=(5,29,7,8,14,23,3,11),n=8,则m=15.351123714291111111000000080010010110011301117111081111例：已知某通信息流只用8种字符，出现频率为0.05，0.2哈夫曼树和编码的代码实现序号权重父号左子右子172193246532637218109101112131415W={7,19,2,6,32,3,21,10}N=8m=2*8-1=159953610101194111117181212281011131340271414601251515100131410010210300000400015016000017118001112345678哈夫曼树和编码的代码实现序号权重父号左子右子17219324第7章图

7.1图的基本概念

7.1.1图的定义图是一种非线性结构,它比树形结构更复杂.图中的数据元素之间是多对多关系,每一个元素都可能与其他元素有关.图是由一个非空的顶点集合和一个描述顶点之间关系即边（或者弧）的集合组成.第7章图

7.1图的基本概念

7.1.1图7.2图的存储结构

7.2.1邻接矩阵邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是n阶方阵定义A：若G是网，则邻接矩阵可定义为：7.2图的存储结构

7.2.1邻接矩阵邻接矩阵是表Aij={0(i,j)VR1(i,j)VRBACDFE例如:矩阵的元素为ABCDEFABCDEF无向图----对称矩阵，半存即可，节省空间。每行(列)数字和即是顶点的度Aij={0(i,j)VR1(i,j)VRBAC有向图的邻接矩阵为非对称矩阵ABECDABCDEABCDE行和为出度列和为入度有向图的邻接矩阵为非对称矩阵ABECDABCDEABCDE行有向网的邻接矩阵为非对称矩阵ABECDABCDEABCDE1217315有向网的邻接矩阵为非对称矩阵ABECDABCDEABCDE17.3.2深度优先搜索深度优先搜索的基本思想是：从图G中某个顶点vi出发，访问vi，然后选择一个与vi相邻且没被访问过的顶点v访问，再从v出发选择一个与v相邻且未被访问的顶点vj访问，依次继续。7.3.2深度优先搜索深度优先搜索的基本思想是：如果当前已访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点w，从w出发按同样方法向前遍历。直到图中所有顶点都被访问。如果当前已访问过的顶点的所有邻接顶点都已被访问，则回退到已被

从图中某个顶点V0

出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有都被访问到。为确定每一个结点是否被访问，必须设置访问标志。一、连通图的深度优先搜索遍历从图中某个顶点V0出发，访问此顶点，然后依次achdekf8234570FFFFFFFFF012345678TTTTTTTachdkfeachkfed访问标志:访问次序:例如:achdkfeachdekf8234570FFFF7.4最小生成树在一个无向连通图G中，如果取它的全部顶点和一部分边构成一个子图G'，即：V(G')=V(G)和E(G')E(G)若边集E(G‘)中的边，既将图G中的所有顶点连通，又不形成回路，则称子图G'是原图G的一棵生成树。产生最小生成树主要有两个算法，即普里姆算法和克鲁斯卡尔算法。7.4最小生成树在一个无向连通图G中，如果取它的全部顶点7.4.2

普里姆算法普里姆(Prim)算法的思路是：假设G=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空。7.4.2普里姆算法普里姆(Prim)算法的思路是：假设算法开始时，首先从V中任取一个顶点（假定取v0），将它并入U中，此时U={v0}，然后只要U是V的真子集（即UV），就从那些其一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短（即权值最小）边，假定为(vi,vj)，其中vi∈U，vj∈V-U，并把该边(vi,vj)和顶点vj分别并入T的边集TE和顶点集U。算法开始时，首先从V中任取一个顶点（假定取v0），将它并入UV0V3V5V2V1V46453821756V01V2closedge

i12345AdjvexLowcostV0V1V2V3V4V5V0V1V2V3V4V5v06v01v070v25v26v2440V5v55v522