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

算法与数据结构复习 2013秋季 l属于程序设计的一个重要内容，训练如何对数据信息进行抽象。 算法与数据结构的主要内容 l对数据信息进行抽象，从逻辑关系上，可以得到四大类数据结 构： 集合 线性结构（线性表、栈、队列、串、数组） 树形结构 图状结构或网状结构 l对应四种逻辑关系，均可以采用两种存储结构进行物理存储： 顺序存储结构 链式存储结构（指针型链表、数组型静态链表） l对应四种逻辑关系，均可以设计出具体的操作方法 结构的初始化、销毁，数据的查找、插入、删除、比较等 l对四种逻辑关系的操作方法进行了具体的编程实现，也例举了 它们的一些具体应用。 多项式的表示和操作 离散事件系统模拟 递归程序的实现 文本编辑系统的设计 霍夫曼编码方法 判定树的构造 最短路径、关键路径、拓扑排序 l对于集合结构，研究了两种重要操作，即排序和查找 第一章 绪论 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 pab xs 例如：在线性链表两个数据元素a和b间插入x, 已知p指针指向a。 s-next = p-next; p-next = s; status listinsert_l(linklist j = 0; while (p +j if (!p | ji-1) return error; /指定的插入位置超界； s = ( linklist) malloc ( sizeof (lnode) ); s-data = e; s-next = p-next; p-next = s; return ok; 第三章 栈和队列 1、栈的表示和实现 栈的概念、特点、表示和实现（顺序存储结构）； 栈的初始化、取栈顶元素、元素的入栈、出栈算法，47页 ； 2、栈的应用 数制转换算法，算法3.1； 求解n阶hanoi塔问题的递归过程和算法，算法3.5； 3、队列的定义、特点 链队列的表示和实现、元素的插入和删除算法； 循环队列的表示和实现、元素的插入和删除算法； 离散事件模拟过程、算法、运行结果，算法3.7； 顺序栈 typedef struct selemtype * base; selemtype * top; intstacksize; sqstack; 栈的存储结构 status push(sqstack s.top = s.base + s.stacksize; s.stacksize += stackincrement; * s.top + + =e; /先将元素压入堆栈，后移动指针； return ok; status pop(sqstack /堆栈为空； e = *- -s.top; /先移动指针,再将元素弹出堆栈； return ok; 栈顶指针top等于栈底指 针base时，栈是空栈。 top 1 2 3 4 5 0 进栈 a 栈满 b c d e f 非空栈的栈顶指针 始终指向栈顶元素 的下一个位置。 top top top top top top 出栈 1 2 3 4 5 0a b c d e f top top top top=base 栈空 top top top=base 1 2 3 4 5 0 栈空 basetop=base 先把元素压入堆栈 ，再移动指针。 先移动指针，再把 栈顶元素弹出。 n只能在栈顶进行数据元素的入栈和出栈操作 。 status enqueue (linkqueue if (!p) exit (overflow); /存储分配失败 p-data = e; p-next = null; q.rear-next = p; q.rear = p; return ok; / 结点类型 typedef struct qnode qelemtype data; struct qnode *next; qnode, * queueptr; / 链队列类型 typedef struct queueptr front; / 队头指针 queueptr rear; / 队尾指针 linkqueue; status dequeue (linkqueue p = q.front-next; e = p-data; q.front-next = p-next; if (q.rear = = p) q.rear = q.front; /防止队尾指针丢失； delete (p); return ok; #define maxqsize 100 /最大队列长度 typedef struct qelemtype *base; / 动态分配存储空间 int front; / 头指针，若队列不空，指向队列头元素; int rear; / 尾指针，若队列不空，指向队列尾元素的下一个位置; sqqueue; 0 m-1 1 front rear . . status enqueue (sqqueue if (q.rear+1) % maxqsize = q.front) return error; /队列满 q.baseq.rear = e; q.rear = (q.rear+1) % maxqsize; return ok; status dequeue (sqqueue 否则返回error if (q.front = q.rear) return error; e = q.baseq.front; q.front = (q.front+1) % maxqsize; return ok; 第四章 串 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.3 4、树和森林 树的存储结构（孩子兄弟表示法） 森林和二叉树的转换 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(1j1，则 其双亲是i/2 ； (2)如果2in，则结点i无左孩子；如果2in，则其左孩子是 2i； (3)如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩 子是2i+1； 性质4： 证明：设深度为k，根据性质2和完全二叉树的定义： 2k-1-1lchild); pop(s, p); /完成循环，最后入栈的是一个空指针 ； if (!stackempty(s) pop(s, p); if (! visit(p-data) return error; push(s, p-rchild); return ok； a b cd ef g p i p-a (1) a b cd ef g p i p-a p-b (2) a b cd ef g pi p-a p-b p-c (3) p=null a b cd ef g i p-a p-b 访问：c(4) p a b cd ef g i p-a 访问：c b (5) a b cd ef g i p-a p-d 访问：c b p (6) a b cd ef g i p-a p-d p-e 访问：c b p (7) a b cd ef g i p-a p-d 访问：c b e p (8) a b cd ef g i p-a p-d p-g 访问：c b e p=null (9) a b cd ef g i p-a 访问：c b e g d p (11) a b cd ef g i p-a p-f 访问：c b e g d p (12) a b cd ef g i p-a p-d 访问：c b e g p (10) a b cd ef g i p-a 访问：c b e g d f p=null (13) a b cd ef g i 访问：c b e g d f a p (14) a b cd ef g i 访问：c b e g d f a p=null (15) 森林与二叉树的转换 树与二叉树可以通过二叉链表作为媒介实现二者间的 映射关系。 森林与二叉树同样可以通过二叉链表作为媒介实现二 者间的映射关系。 a cbe d 树 a b c de 二叉树 a b c d e a b c d e a b c d e 对应 存储 存储 解释 解释 构造huffman树的方法huffman算法 构造huffman树的步骤 1、根据给定的n个权值w1,w2,wn，构造n棵 只有根结点的二叉树，第i棵树的权值为wi；形成 一个森林。 2、在森林中选取两棵根结点权值最小的树作左右 子树，构造一棵新的二叉树，置新二叉树根结点 权值为其左右子树根结点权值之和,并在森林中删 除这两棵树，同时将新得到的二叉树加入森林中 ； 3、重复上述两步直到只含一棵树为止，这棵树即 赫夫曼树。 例 a 7 b 5 c 2 d 4 a 7 b 5 c 2 d 4 6 a 7 b 5 c 2 d 4 6 11 a 7 b 5 c 2 d 4 6 11 18 例 w=5, 29, 7, 8, 14, 23, 3, 11 51429 7823 3 11 14297823 11 35 8 87 15 142923 35 811 11 35 8 19142923 87 15 11 35 8 192923 14 87 15 29 29 14 87 15 29 11 35 8 19 23 42 11 35 8 19 23 42 29 14 87 15 29 58 100 11 35 8 19 23 42 29 14 87 15 29 58 第七章 图 1、图的定义和术语 2、图的存储结构 数组表示法 邻接表 十字链表 邻接多重表 采用邻接矩阵表示法，构造无向网g，算法7.2 采用十字链表表示法，构造有向图g，算法7.3 3、图的遍历 深度优先搜索的过程和算法，算法7.4、 7.5 广度优先搜索的过程和算法，算法7.6 4、图的连通性问题 最小生成树的概念、普里姆算法、克鲁斯卡尔算法思想 普里姆算法，算法7.9 5、有向无环图及其应用 拓扑排序的概念和算法，算法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 65 4 3 2 6 5 1 3 5 6 6 4 2 5 1 3 1 1 6 3 1 4 1 6 4 3 1 4 2 1 1 6 4 3 2 1 4 2 5 1 65 4 3 2 1 4 2 5 3 方法二：克鲁斯卡尔(kruskal)算法 算法思想： 1、设连通网n=(v,e)，令最小生成树的初始状态为只有n个 顶点而无边的非连通图t=(v,)，每个顶点自成一个连通 分量; 2、在e中选取代价最小的边，若该边依附的顶点落在t中不同 的连通分量上，则将此边加入到t中；否则，舍去此边，选 取下一条代价最小的边; 3、依此类推，直至t中所有顶点都在同一连通分量上为止。 例 1 65 4 3 2 6 5 1 3 5 6 6 4 2 5 1 65 4 3 2 1 2 3 4 5 最短路径 如果用带权的有向图表示一个交通运输网，图中： 顶点表示城市； 边表示城市间的交通联系； 权表示此线路的长度或沿此线路运输所花的时间或费用等； 如何寻找最短路径？即寻找从某顶点出发，沿图的边到达另一顶 点所经过的路径中，各边上权值之和最小的一条路径； 问题的提出 迪杰斯特拉(dijkstra)算法思想 按路径长度的递增顺序，依次产生最短路径; 假设图中所示为从源点到其余各点之间的最短路径，在其中必有 一条相对最短的路径； 源点 a 在相对最短的路径上，必定只含一条弧且权值最小。因此，只 要在所有从源点出发的弧中查找权值最小者，可得相对最短路径; 长度次短的路径可能有两种情况: 它可能是从源点直接到该点的路径; 也可能是，从源点到a, 再从a到该点； 其余依次类推，直至求出源点到各顶点的全部最短路径。 从某个源点到其余各顶点的最短路径 假设 distk 表示当前所求得的从源点到k的最短路径，显然， distk = 或 = + ； 求最短路径步骤: 首先，令s=v0，t=其余顶点，v0到t中顶点对应的路径长度： 若存在，为弧上的权值； 若不存在，为； 其次，从t中选取一个与v0路径长度最小的顶点j，加入s； 对t中顶点的路径长度进行修改：若加进j作中间顶点，从v0到vi 的路径长度比不加j时的路径短，则修改此路径长度。 重复上述步骤，直到s中包含所有顶点，即s=v为止。 13 8 30 32 v2 13 - 13 30 32 v1 - - 13 30 22 20 v3 - - - 19 22 20 v4 终点 从v0到各终点的最短路径及其长度 v1 v2 v3 v4 v5 v6 vj - - - - 21 20 v6 5 1 6 4 3 2 0 8 5 62 30 13 7 17 32 9 第九章 查找 概念：关键字 1、静态查找表 顺序表的查找，算法9.1 有序表的查找，算法9.2 索引顺序表的查找算法思想 上述三种查找方式的平均查找长度 判定树的概念与结构特点 2、动态查找表 二叉排序树的特性以及查找、插入、删除算法， 9.5(b)、9.6、9.8 平衡二叉树的概念 b-树和b+树的概念 b-树