算法与数据结构 期末考试复习.ppt

算法与数据结构复习,2013秋季,属于程序设计的一个重要内容，训练如何对数据信息进行抽象。,算法与数据结构的主要内容,对数据信息进行抽象，从逻辑关系上，可以得到四大类数据结构：集合线性结构（线性表、栈、队列、串、数组）树形结构图状结构或网状结构,对应四种逻辑关系，均可以采用两种存储结构进行物理存储：顺序存储结构链式存储结构（指针型链表、数组型静态链表）,对应四种逻辑关系，均可以设计出具体的操作方法结构的初始化、销毁，数据的查找、插入、删除、比较等,对四种逻辑关系的操作方法进行了具体的编程实现，也例举了它们的一些具体应用。多项式的表示和操作离散事件系统模拟递归程序的实现文本编辑系统的设计霍夫曼编码方法判定树的构造最短路径、关键路径、拓扑排序,对于集合结构，研究了两种重要操作，即排序和查找,第一章 绪论,1、基本概念和术语“数据结构”课程的研究内容及在计算机科学中的地位；数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型；逻辑结构和物理结构、顺序存储结构和链式存储结构；2、抽象数据类型的表示和实现 三元组表示法；熟悉类c语言的语法；3、算法和算法分析 算法的定义和5个重要特性；算法设计的4个要求及含义；算法效率的度量 渐进时间复杂度的概念；简单算法的时间复杂度的估算；,第二章 线性表,1、线性表的类型定义 线性结构 线性表的定义及特性2、线性表的顺序表示和实现 线性表的动态分配顺序存储结构 线性表插入、删除算法，算法2.4、2.5 插入、删除算法的平均时间复杂度的估算3、线性表的链式表示和实现 线性链表的概念 线性单链表的存储结构和创建、插入、删除、合并算法 循环链表的概念、特点 双向链表的存储结构和插入删除算法，算法2.18、2.19,4、一元多项式的表示与相加算法,typedef struct PNode float coef；/系数 int expn；/指数 struct PNode*next；PNode，PLinkList；相加算法要求读懂、理解，算法2.23,例如：在线性链表两个数据元素a和b间插入x,已知p指针指向a。,s-next=p-next;,p-next=s;,Status ListInsert_L(LinkList,第三章 栈和队列,1、栈的表示和实现栈的概念、特点、表示和实现（顺序存储结构）；栈的初始化、取栈顶元素、元素的入栈、出栈算法，47页；2、栈的应用 数制转换算法，算法3.1；求解n阶Hanoi塔问题的递归过程和算法，算法3.5；3、队列的定义、特点链队列的表示和实现、元素的插入和删除算法；循环队列的表示和实现、元素的插入和删除算法；离散事件模拟过程、算法、运行结果，算法3.7；,顺序栈typedef structSElemType*base;SElemType*top;intstacksize;SqStack;,栈的存储结构,Status Push(SqStack,栈顶指针top等于栈底指针base时，栈是空栈。,进栈,A,栈满,B,C,D,E,F,非空栈的栈顶指针始终指向栈顶元素的下一个位置。,出栈,栈空,先把元素压入堆栈，再移动指针。,先移动指针，再把栈顶元素弹出。,只能在栈顶进行数据元素的入栈和出栈操作。,Status EnQueue(LinkQueue,/结点类型 typedef struct QNode QElemType data;struct QNode*next;QNode,*QueuePtr;,/链队列类型typedef struct QueuePtr front;/队头指针 QueuePtr rear;/队尾指针 LinkQueue;,Status DeQueue(LinkQueue,#define MAXQSIZE 100/最大队列长度typedef struct QElemType*base;/动态分配存储空间 int front;/头指针，若队列不空，指向队列头元素;int rear;/尾指针，若队列不空，指向队列尾元素的下一个位置;SqQueue;,Status EnQueue(SqQueue,Status DeQueue(SqQueue,第四章 串,1、串类型的定义、表示和实现 定长顺序存储表示 堆分配存储表示 串的块链存储表示 串的抽象数据类型定义,串和串的基本概念串(String)是零个或多个字符组成的有限序列。一般记作S=a1 a2 a3 an，其中S是串名，单引号括起来的字符序列是串值；ai(1in)可以是字母、数字或其它字符；串中所包含的字符个数称为串的长度。空串(Empty String)是长度为零的串，它不包含任何字符。空白串(Blank String)是由一个或多个空格组成的串。注意：空串和空白串不同，例如和分别表示长度为1的空白串和长度为0的空串。,定长顺序存储表示#define MAXSTRLEN 255/用户可在255以内定义串长typedef unsigned char SStringMAXSTRLEN+1;/0号单元存放串的长度(PASCAL风格)堆分配存储表示typedef struct char*ch;/若是非空串，则按串长分配存储区，否则ch为NULL;int length;/串长度;HString;,串的块链存储表示#define CHUNKSIZE 80/可由用户定义的块大小;typedef struct Chunk/结点结构;char chCUNKSIZE;struct Chunk*next;Chunk;typedef struct/串的链表结构;Chunk*head,*tail;/串的头和尾指针;int curlen;/串的当前长度;LString;,第六章 树和二叉树,1、树的定义及基本术语 树的抽象数据类型表述 基本术语2、二叉树的定义、性质和存储结构 二叉树的抽象数据类型表述 二叉树的性质1、2、3、4 二叉树的存储结构（顺序存储结构和链式存储结构）3、二叉树的遍历与构造 算法6.1、6.2、6.34、树和森林 树的存储结构（孩子兄弟表示法）森林和二叉树的转换5、赫夫曼树的定义、构造方法及其应用（判定树、赫夫曼编码）算法6.12,抽象数据类型定义,ADT Tree 数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R=H,H是如下二元关系：(1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；(2)若D-root，则存在D-root的一个划分D1，D2,Dm(m0)，对任意jk(1j，km)有DjDk=，且对任意的i(1im)，惟一存在数据元素xiDi,有H;,(3)对应于D-root的划分，H-,有惟一的一个划分H1,H2,Hm(m0)，对任意jk(1j，km)有HjHk=，且对任意的i(1im)，Hi是Di上的二元关系，(Di，Hi)是一颗符合本定义的树，称为根root的子树。,基本术语(1)结点(node)表示树中的元素，包括数据项及若干指向其子树的分支;(2)结点的度(degree)结点拥有的子树数量;(3)叶子(leaf)度为0的结点；(4)孩子(child)结点子树的根称为该结点的孩子；(5)双亲(parents)孩子结点的上层结点叫该结点的双亲；(6)兄弟(sibling)同一双亲的孩子；(7)树的度一棵树中各结点的度的最大值；(8)结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层；(9)深度(depth)树中结点的最大层次数；(10)森林(forest)m(m0)棵互不相交的树的集合；,二叉树性质,证明：用归纳法证明之:i=1时，只有一个根结点，结论成立；假设对所有j(1ji)命题成立，即第j层上至多有 个 结点，那么，第i-1层至多有 个结点；因为二叉树每个结点的度至多为2，则 第i层上最大结点 数是第i-1层的2倍，即。故命题得证。,证明：由性质1，可得深度为k 的二叉树最大结点数是：,性质1：,性质2：深度为k的二叉树至多有 个结点(k1)。,性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2 的结点数为n2，则n0=n2+1。,证明：n1为二叉树T中度为1的结点数；因为：二叉树中所有结点的度均小于或等于2 所以：其结点总数n=n0+n1+n2；又因为二叉树中，除根结点外，其余结点都只有一个 分支进入；设B为分支总数，则n=B+1；又因为分支由度为1和度为2的结点射出，则B=n1+2n2，于是，n=B+1=n1+2n2+1=n0+n1+n2；故n0=n2+1成立。,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有：(1)如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是i/2；(2)如果2in，则结点i无左孩子；如果2in，则其左孩子是2i；(3)如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1；,性质4：,证明：设深度为K，根据性质2和完全二叉树的定义：2k-1-1n2k-1 或者 2k-1n2k；K-12nK；因为K为整数，故性质4成立。,Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType),中序遍历二叉树T的非递归算法,InitStatck(S);Push(S,T);/借助于堆栈，根指针进栈,while(!StackEmpty(S),while(GetTop(S,p),Pop(S,p);/完成循环，最后入栈的是一个空指针；,if(!StackEmpty(S),Pop(S,p);if(!Visit(p-data)return ERROR;,Push(S,p-rchild);,return OK；,森林与二叉树的转换,树与二叉树可以通过二叉链表作为媒介实现二者间的映射关系。,森林与二叉树同样可以通过二叉链表作为媒介实现二者间的映射关系。,构造Huffman树的方法Huffman算法,构造Huffman树的步骤,1、根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，第i棵树的权值为wi；形成一个森林。2、在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和,并在森林中删除这两棵树，同时将新得到的二叉树加入森林中；,3、重复上述两步直到只含一棵树为止，这棵树即赫夫曼树。,例 w=5,29,7,8,14,23,3,11,第七章 图,1、图的定义和术语2、图的存储结构 数组表示法 邻接表 十字链表 邻接多重表 采用邻接矩阵表示法，构造无向网G，算法7.2 采用十字链表表示法，构造有向图G，算法7.33、图的遍历 深度优先搜索的过程和算法，算法7.4、7.5 广度优先搜索的过程和算法，算法7.6,4、图的连通性问题 最小生成树的概念、普里姆算法、克鲁斯卡尔算法思想 普里姆算法，算法7.95、有向无环图及其应用 拓扑排序的概念和算法，算法7.12 关键路径的概念和算法，算法7.13、7.14 AOV-网和AOE-网的概念 6、最短路径 最短路径的概念 从某一源点到其余各顶点的最短路径，迪杰斯特拉算 法，算法7.15,构造最小生成树的方法方法一：普里姆(Prim)算法1、算法思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合；2、初始令U=u0,(u0V),TE=；3、在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0)；4、将(u0,v0)并入集合TE，同时v0并入U；5、重复上述操作直至U=V为止，则T=(V,TE)为N的最小生成树；,1,方法二：克鲁斯卡尔(Kruskal)算法算法思想：1、设连通网N=(V,E)，令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连通分量;2、在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边;3、依此类推，直至T中所有顶点都在同一连通分量上为止。,最短路径,如果用带权的有向图表示一个交通运输网，图中：顶点表示城市；边表示城市间的交通联系；权表示此线路的长度或沿此线路运输所花的时间或费用等；如何寻找最短路径？即寻找从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径；,问题的提出,迪杰斯特拉(Dijkstra)算法思想,按路径长度的递增顺序，依次产生最短路径;,假设图中所示为从源点到其余各点之间的最短路径，在其中必有一条相对最短的路径；,源点,a,在相对最短的路径上，必定只含一条弧且权值最小。因此，只要在所有从源点出发的弧中查找权值最小者，可得相对最短路径;长度次短的路径可能有两种情况:它可能是从源点直接到该点的路径;也可能是，从源点到a,再从a到该点；其余依次类推，直至求出源点到各顶点的全部最短路径。,从某个源点到其余各顶点的最短路径,假设 Distk 表示当前所求得的从源点到k的最短路径，显然，Distk=或=+；,求最短路径步骤:首先，令S=V0，T=其余顶点，V0到T中顶点对应的路径长度：若存在，为弧上的权值；若不存在，为；其次，从T中选取一个与V0路径长度最小的顶点j，加入S；对T中顶点的路径长度进行修改：若加进j作中间顶点，从V0到Vi的路径长度比不加j时的路径短，则修改此路径长度。重复上述步骤，直到S中包含所有顶点，即S=V为止。,1383032V2,13-133032V1,-13302220V3,-192220V4,-2120V6,第九章 查找,概念：关键字1、静态查找表 顺序表的查找，算法9.1 有序表的查找，算法9.2 索引顺序表的查找算法思想 上述三种查找方式的平均查找长度 判定树的概念与结构特点2、动态查找表 二叉排序树的特性以及查找、插入、删除算法，9.5(b)、9.6、9.8 平衡二叉树的概念 B-树和B+树的概念 B-树的查找算法，算法9.13,3、哈希表哈希表的概念哈希函数的构造方法直接定址法除留余数法处理冲突的方法开放定址法链地址法哈希表的查找过程,1B-树的定义,B-树是一种 平衡 的 多路 查找 树：,平衡树的特性,树中所有叶子结点均不带信息，且在树中的同一层次上;根结点或为叶子结点，或至少含有两棵子树;其余所有非叶结点均至少含有m/2棵子树，至多含有 m 棵子树;,在 m 阶的B-树上，每个非终端结点可能含有：n 个关键字 Ki（1 in）nm n 个指向记录的指针 Di（1in）n+1 个指向子树的指针 Ai（0in）;,多叉树的特性,非叶结点中的多个关键字均自小至大有序排列，即：K1 K2 Kn;且 Ai-1 所指子树上所有关键字均小于Ki;Ai 所指子树上所有关键字均大于Ki;非终端结点中包含的信息：(n,A0,K1,A1,K2,Kn,An),查找树的特性,一棵4阶B-树,B+树的结构特点：,每个中间结点中含有 n 个关键字和 n 个指向记录的指针；,2B+树:是B-树的一种变型,每个中间结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值；,所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 m/2和 m 之间，包括m/2和 m。并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点；,数据库中的非簇索引和簇索引,57,第10章 排序排序的概念、稳定排序、排序算法的时间复杂度极限O(nlogn)各种排序方法的基本思想、过程、性能，给出一个序列，能够手工推演出各趟排序结果。直接插入排序、表插入排序、希尔排序快速排序堆排序归并排序基数排序,本文观看结束！,谢 谢欣 赏！,祝各位身体健康！万事如意！,