数据结构2016h

1、数据结构数据结构题型题型(1)p基本概念基本概念40n选择2x15n判断1x10p简答简答10 x3=30p给定数据实例，运行相关算法，得出结果，分析效率，例如p霍夫曼编码霍夫曼编码p快速快速/ /堆排序算法堆排序算法p三种哈希算法的实例运行三种哈希算法的实例运行p根据根据二叉树遍历结果画出树（前序中序求后序等）二叉树遍历结果画出树（前序中序求后序等）p二叉树和森林的转换二叉树和森林的转换p拓扑拓扑排序排序题型题型(2)p算法设计题算法设计题10 x3=30n常见题型p遍历一维数组，两位数组：查找或转置遍历一维数组，两位数组：查找或转置p链表操作（转置链表操作（转置/ /合并合并/ /拆分）拆

2、分）p二叉树（复制，相等二叉树（复制，相等，求高度，求高度, ,求子孙数。使用求子孙数。使用简单递归算简单递归算法）法）第一章第一章 绪论绪论学习数据结构的意义学习数据结构的意义p是为研究和解决如何有效地组织和处理是为研究和解决如何有效地组织和处理非数值数据非数值数据而而产生的理论、技术和方法。产生的理论、技术和方法。p是计算机科学中的一门综合性的专业基础课。是计算机科学中的一门综合性的专业基础课。 涉及计算机软件、硬件以及数学等涉及计算机软件、硬件以及数学等基本术语基本术语p数据数据 被计算机加工处理的对象。p数据元素数据元素（记录记录、表目表目） 数据的基本单位，是数据集合中的一个有意义的

3、个体。p数据项数据项 一个数据元素可由若干个数据项数据项组成。 组合项组合项年 月 日学 号姓 名班 号性别出生日期入学成绩原子项原子项基本基本术语术语2 2p数据对象数据对象 是性质相同的数据元素的集合，是数据的一个子集。 学号 姓名 班号 性别 出生日期 入学成绩 001 刘影 01 女 19840417 623 002 李恒 01 男 19831211 679 003 陈诚 02 男 19840910 638 p数据结构数据结构 具有结构的数据元素的集合。它包括数据元素的逻辑结构逻辑结构、存储结构（物理结构）存储结构（物理结构）和相适应的运算运算。数据元素（以班级学生关系为例）(1)集合

4、结构集合结构 数据元素除了“属于同一集合”的联系之外，没有其它的关系。(2)线性结构线性结构 数据元素之间存在一对一的关系。(3)树型结构树型结构 数据元素之间存在一对多的关系。(4)图状结构图状结构或网状结构网状结构 数据元素之间存在多对多的关系。成员关系长幼关系管理关系朋友关系四种基本的逻辑结构四种基本的逻辑结构数据的逻辑结构数据的逻辑结构存储结构存储结构：数据的逻辑结构在计算机中如何表示。p数据元素的映象数据元素的映象 用二进制位(bit)的位串表示数据元素。 每个数据元素的映象称为每个数据元素的映象称为结点结点 每个数据项的映象称为每个数据项的映象称为数据域数据域p关系的映象关系的映象

5、两种基本方法及其组合使用。两种基本方法及其组合使用。n顺序映象顺序映象：以相对的存储位置表示关系以相对的存储位置表示关系n链式映象链式映象：以附加信息：以附加信息( (指针指针) )表示关系表示关系p注意：数据的逻辑结构和存储结构的关系n可以用数组等线形存储的方式存储逻辑上的树形结构可以用数组等线形存储的方式存储逻辑上的树形结构n也可以用树状的复杂的存储结构来存储逻辑上的集合关系以达也可以用树状的复杂的存储结构来存储逻辑上的集合关系以达到提高检索速度的目的到提高检索速度的目的数据的存储结构数据的存储结构 数据的逻辑结构+运算的定义-面向用户，需求分析 （抽象数据类型） 概念层 数据的存储结构+

6、运算的实现-面向计算机 实现层数据的逻辑结构与存储结构数据的逻辑结构与存储结构算法和算法分析算法和算法分析p正确性（最重要的标准）n算法应满足具体问题的需求算法应满足具体问题的需求n对于典型的、苛刻而带有刁难性的一组对于典型的、苛刻而带有刁难性的一组有效输入有效输入得到正确的得到正确的结果结果p健壮性（鲁棒性）n算法应具有容错处理。当输入算法应具有容错处理。当输入非法数据非法数据时，算法应对其作出时，算法应对其作出反应，而不是产生莫名其妙或随机的输出结果反应，而不是产生莫名其妙或随机的输出结果p可读性n算法应该好读。以有利于阅读者对程序的理解和维护算法应该好读。以有利于阅读者对程序的理解和维护

7、p高效性：时间复杂度n算法执行占用的算法执行占用的CPU时间，随问题规模时间，随问题规模n的变化函数的变化函数p高效性：空间复杂度n算法执行占用的内存总量，随问题规模算法执行占用的内存总量，随问题规模n的变化函数的变化函数评价算法优劣的基本标准评价算法优劣的基本标准时间复杂度时间复杂度pnn问题规模，一般为数据的输入量问题规模，一般为数据的输入量pf(n)n算法中基本操作重复执行的次数算法中基本操作重复执行的次数频度频度n是问题规模是问题规模n n的某个函数的某个函数p算法的时间量度、时间复杂度算法的时间量度、时间复杂度n算法中各语句的频度之和算法中各语句的频度之和T(n)nT(n)=O(f(

8、n)n随问题规模的增大，执行时间的增长率和随问题规模的增大，执行时间的增长率和f(n)的增长率相同的增长率相同时间复杂度曲线时间复杂度曲线p常见的时间复杂度： O(1), O(log2n), O(n), O(n log2n), O(n2), O(n3), O(2n)pO(1)data=x) L2 = p-next; p-next = NULL; break; else p = p-next; p将单向链表（头为L）断裂成两个单链表，截掉元素x之后的部分生成为链表L2。第三章第三章 栈和队列栈和队列插入和删除操作受限的线性表插入和删除操作受限的线性表p栈和队列都是线性表线性表，只是在操作上做了限

9、制操作上做了限制p栈（stack）n后进先出后进先出(LIFO:Last In First Out)的线性表的线性表n表头端称为栈底（表头端称为栈底（bottom）n表尾端称为栈顶（表尾端称为栈顶（top）n插入和删除都在栈顶进行插入和删除都在栈顶进行p队列（queue）n先进先出先进先出(FIFO:First In First Out)的线性表的线性表n表头端称为队头（表头端称为队头（front）n表尾端称为队尾（表尾端称为队尾（rear）n插入在队尾进行，而删除则在队头进行插入在队尾进行，而删除则在队头进行栈的定义和基本操作栈的定义和基本操作 栈的基本操作栈的基本操作nInitStack(

10、&s)初始化堆栈nStackEmpty(s)判断堆栈是否空npush(s, e)将元素e压入堆栈npop(s, &e)弹出栈顶元素栈的存储结构栈的存储结构p存储方式n顺序表方式（常用）顺序表方式（常用）n链表方式链表方式p顺序表方式的堆栈类型定义#define STACK_SIZE 128ElemType stackSTACK_SIZE;int top;p栈的应用栈的应用n函数调用（函数调用（CPU内置堆栈操作）内置堆栈操作）n递归（函数自己调用自己的一种特殊函数调用。直接递归，递归（函数自己调用自己的一种特殊函数调用。直接递归，间接递归）间接递归）队列队列队列的定义队列的定义

11、p 队列是一种特殊的线性表p 限定插入和删除操作分别在表的两端进行p 具有先进先出(FIFOFirst In First Out)的特点。队列的操作队列的操作p 主要操作n 增加（入队）增加（入队） EnQueue(Q, e);n 删除（出队）删除（出队） DeQueue(Q, &e);n 判断队列是否为空判断队列是否为空 QueueEmpty(Q)p 其他操作n 初始化队列初始化队列InitQueue(Q)n 获取队列长度获取队列长度 QueueLength(Q)n 清除队列中的所有元素清除队列中的所有元素 ClearQueue(Q)队列的队列的存储结构和实现存储结构和实现p 链表方

12、式p 顺序表方式两维数组的遍历两维数组的遍历p统计整形数组AMN中非零元素的个数n = 0;for (i = 0; i M; i+) for (j = 0; j N; j+) if (aij != 0) n+;printf(“n=%dn”, n);第六章第六章 树和二叉树树和二叉树树的定义和基本术语树的定义和基本术语树的定义树的定义p树是一类重要的非线性数据结构，是以分支关系定义的层次结构；p树是n(n0)个结点的有限集，非空树满足：n有且仅有一个特定的称之为有且仅有一个特定的称之为(root)的结点；的结点；n除根以外的其余结点可分为除根以外的其余结点可分为m(0 mlchild); Pre

13、order(t-rchild); void Inorder(BiTree t) if (t) Inorder(t-lchild); visit(t); Inorder(t-rchild); void Postorder(BiTree t) if (t) Postorder(t-lchild); Postorder(t -rchild); visit( t ); 遍历二叉树的递归算法遍历二叉树的递归算法判断两个二叉树是否相等类似的其他递归式二叉树算法类似的其他递归式二叉树算法(1)交换二叉树的左右子树计算二叉树高度二叉树拷贝计算二叉树的平衡因子计算二叉树的节点个数类似的其他递归式二叉树算法类似的

14、其他递归式二叉树算法(2)求二叉树中的节点数目（每个节点有counter域记录该二叉树中的节点数目）typedef struct Node TElemType data； int counter; struct Node*lchild； struct Node*rchild； *BitTree；int count(BiTree t) int nl, nr; if (t = NULL) return 0; nl = count(t-lchild); nr = count(t-rchild); t-counter = nl + nr + 1; return t-counter;树和森林树和森林树的

15、存储结构树的存储结构: :孩子兄弟表示法孩子兄弟表示法p孩子兄弟表示法ABCDEFGABCEFGD森林与二叉树的转换森林与二叉树的转换p转换原则n按孩子兄弟表示法进行转换按孩子兄弟表示法进行转换(左为长子，左为长子，右右为弟为弟)。p树与二叉树的转换DE森林与二叉树的相互转换森林与二叉树的相互转换赫夫曼树及其应用赫夫曼树及其应用赫夫曼树及其应用赫夫曼树及其应用p赫夫曼树n最优树；最优树；n是一类带权路径长度最短的树；是一类带权路径长度最短的树；n路径长度路径长度p指树中两个结点间路径上所含有的分支数目。n树的路径长度树的路径长度p指从树根到每一结点的路径长度之和。n带权路径长度带权路径长度p指

16、结点的路径长度与该结点的权之积。赫夫曼树赫夫曼树树的带权路径长度n树中所有叶子结点的带权路径长度；树中所有叶子结点的带权路径长度；p最优二叉树或赫夫曼树。nWPL 最小的二叉树。最小的二叉树。结点到根的路径长度权值其中：记作：kknkkklwlwwpl1赫夫曼树的构造赫夫曼树的构造p根据给定的n个权值w1,w2,.wn构成n棵二叉树的集合F=T1,T2,.,Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空；p在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。p在F中删除这两棵树，同时将新得到的二叉

17、树加入F中；p重复2和3，直到F中只含一棵树为止；p这棵树就是赫夫曼树；p赫夫曼树的性质赫夫曼树的性质 所有节点的度要么为所有节点的度要么为0，要么为，要么为2； 叶子个数叶子个数=非叶子结点个数非叶子结点个数 + 1； 子树也是赫夫曼树；子树也是赫夫曼树； 权权值越大的值越大的节点离根越近节点离根越近 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 231487152929148715291135819234211358192342291487

18、15295811358192342291487152958100赫夫曼树构造赫夫曼树构造举例举例1 1赫夫曼编码的特点赫夫曼编码的特点n不等长编码不等长编码 赫夫曼编码是不等长编码n前缀编码前缀编码 赫夫曼编码是赫夫曼编码是前缀编码前缀编码，即任一编码，即任一编码另一字符编码另一字符编码的前缀的前缀n发送过程（编码）发送过程（编码） 根据由赫夫曼树得到的编码表根据由赫夫曼树得到的编码表 送出字符数据送出字符数据n接收过程（解码）接收过程（解码） 按左按左0、右、右1的规定，从根结点走到一个叶结点，完成一个的规定，从根结点走到一个叶结点，完成一个字符的译码。反复此过程，直到接收数据字符的译码。反

19、复此过程，直到接收数据结束结束第七章第七章 图图图的定义图的定义和术语和术语(1)(1)p图Gn由两个集合由两个集合V(G)和和E(G)组成，记作组成，记作G=(V,E) n其中其中V(G)是顶点的非空有穷集合，是顶点的非空有穷集合，E(G)是边的有穷集合，是边的有穷集合，而边是顶点的无序对或有序对。而边是顶点的无序对或有序对。 112323423图的基本术语图的基本术语(2)(2)p顶点(vertex)n数据元素所构成的结点通常称为顶点。数据元素所构成的结点通常称为顶点。p弧弧(arc)n若两个顶点间有关系若两个顶点间有关系E ，则称，则称为一条弧。为一条弧。p弧头(又称终端点)n若若为一条

20、弧，则顶点为一条弧，则顶点 y 称为弧头。称为弧头。p弧尾(又称初始点)n若若为一条弧，则顶点为一条弧，则顶点 x 称为弧尾。称为弧尾。p边边(Edge)n无向图中两条弧无向图中两条弧和和可用一条边可用一条边(x,y)来表示来表示 。图的基本图的基本术语术语(3)(3)p顶点的度顶点的度（degree）n无向图：与顶点相关联的无向图：与顶点相关联的边边数称为该顶点的度数称为该顶点的度n有向图：分为入度和出度有向图：分为入度和出度 p顶点的入度（indegree）n以顶点为头的弧数称为该顶点的入度以顶点为头的弧数称为该顶点的入度 。p顶点的出度（outdegree）n以顶点为尾的弧数称为该顶点的

21、出度以顶点为尾的弧数称为该顶点的出度 。p路径（path）n由顶点由顶点vi经过一系列边和顶点到达顶点经过一系列边和顶点到达顶点vj所得到的顶点序列。所得到的顶点序列。p回路（loop-又称环环 cycle）n起点和终点为同一顶点的路径称为回路。起点和终点为同一顶点的路径称为回路。ABCEFD图的基本图的基本术语术语(4)(4)p简单路径n(路径的顶点路径的顶点)序列中顶点不重复出现的路径。序列中顶点不重复出现的路径。p简单回路(简单环) n除路径起点和终点相同外，其余顶点均不相同的回路。除路径起点和终点相同外，其余顶点均不相同的回路。p权(weight)n有些图的边或弧具有一定的大小，称之为

22、权。有些图的边或弧具有一定的大小，称之为权。p网网n带权值的图又称为网或网络。带权值的图又称为网或网络。ABCEFD图的基本图的基本术语术语(5)(5)p子图n由图的部分顶点和边组成的新图称为原图的子图。由图的部分顶点和边组成的新图称为原图的子图。p生成子图生成子图n由图的由图的全部顶点和全部顶点和部分边部分边组成的子图称为原图的生成子图。组成的子图称为原图的生成子图。p邻接点n若边若边(vi,vj)E，则，则 vi与与vj互为邻接点。互为邻接点。图的基本图的基本术语术语(6)(6)p有向图n若若E ，并不总有，并不总有E，则称此图为有向图，则称此图为有向图p无向图n若若E ，总有，总有E，则

23、称此图为无向图，则称此图为无向图p完全图n具有具有 n*(n-1)/2条边的无向图称为完全图条边的无向图称为完全图。p有向完全图n具有具有 n*(n-1)条弧的有向图称为有向完全图。条弧的有向图称为有向完全图。图的基本术语图的基本术语(7)(7)p生成树n连通图的连通图的极小连通生成子图极小连通生成子图称为原图的生成树。称为原图的生成树。p生成森林n由多棵有向树构成的有向图的生成子图称为生成森林。由多棵有向树构成的有向图的生成子图称为生成森林。p最小代价生成树n连通网中由最小权值的边构成的生成树。连通网中由最小权值的边构成的生成树。拓扑排序拓扑排序p拓扑排序n由某集合上的一个由某集合上的一个偏

24、序偏序得到该集合上的一个得到该集合上的一个全序全序pAOV 网(Activity On Vertex)n有向有向边边表示两个活动间的表示两个活动间的次序关系次序关系n顶点顶点表示表示活动活动n这类图又称为顶点活动图，简称这类图又称为顶点活动图，简称 AOV 图图n如用顶点表示课程，用弧表示某些课程是其它课程的如用顶点表示课程，用弧表示某些课程是其它课程的先修课，则拓扑排序就是求在同时只能学习一门课程先修课，则拓扑排序就是求在同时只能学习一门课程时的学习次序时的学习次序拓扑排序的算法步骤拓扑排序的算法步骤1.扫描图中每个顶点，将入度为零的顶点入队列；2.从队列中取出一个顶点输出，并将其所有邻接点

25、的入度减 1 ，若入度减为零，则将该邻接点入队列 3.反复执行步骤 2，直至所有顶点的入度均为零p若该有向图是有环图，则不存在拓扑排序有环图，则不存在拓扑排序，就不可能输出全部顶点；否则就可以输出全部顶点。此特点可用来判断一个有向图是否存在回路。C1C2C3C6C4C5C7C8C9C10C1C2C3C4C5C6C7C8C9C10C2C1C3C4C5C6C7C8C9C10C1C2C4C3C5C6C7C8C9C10C2C1C4C3C5C6C7C8C9C10C1C2C5C4C3C6C7C8C10C9拓扑排序结果：第九章第九章 查找查找基本概念基本概念p查找表n由同一类型的数据元素构成的集合；由同一类

26、型的数据元素构成的集合；n静态查找表静态查找表p对查找表的查找仅是以查询为目的，不改动查找表中的数据。n动态查找表动态查找表p可以在查找表中插入不存在的记录，或删除某个已存在的记录。p关键字n数据元素（或记录）的某个数据项，能用来标识一个数据元素。数据元素（或记录）的某个数据项，能用来标识一个数据元素。p查找n指定某个值，在查找表中确定是否存在一个记录，该记录的关键指定某个值，在查找表中确定是否存在一个记录，该记录的关键字等于给定值字等于给定值。基本概念（续）基本概念（续）p查找成功n查找表中存在满足查找条件的记录。查找表中存在满足查找条件的记录。p查找不成功n查找表中不存在满足查找条件的记录

27、。查找表中不存在满足查找条件的记录。p平均查找长度ASL查找方法时效的度量n为确定记录在查找表中的位置，需将关键字和给定值比较次数的为确定记录在查找表中的位置，需将关键字和给定值比较次数的期望值。期望值。n查找成功时的查找成功时的ASL计算方法：计算方法：pn：记录的个数ppi：查找第i个记录的概率，( 不特别声明时认为等概率 pi =1/n )pci：找到第i个记录所需的比较次数动态动态查找表查找表折半查找折半查找只有有序表才能用折半查找的方法只有有序表才能用折半查找的方法p将给定值与中间的记录进行比较；p若找到则查找成功；p否则若给定值比中间记录小，则对前一半子表进行折半查找，反之则对后一

28、半子表进行折半查找。p若在查找过程中，遇到查找子表的上界小于下界，则表示查找失败动态查找表平衡二叉树动态查找表平衡二叉树p平衡二叉树平衡二叉树n平衡二叉树又称平衡二叉树又称 AVL AVL 树，它具有如下性质：树，它具有如下性质：p或者为空树，或者为空树，p或者根结点的左、右子树也均为平衡二叉树，或者根结点的左、右子树也均为平衡二叉树，且左、右子树的树高之差的绝对值不超过且左、右子树的树高之差的绝对值不超过1 1。n平衡平衡因子因子bfbfp结点的左子树高度减去右子树高度的值称为该结点的左子树高度减去右子树高度的值称为该结点的平衡因子。结点的平衡因子。p平衡二叉树也可以这样定义：平衡二叉树是所

29、平衡二叉树也可以这样定义：平衡二叉树是所有结点的平衡因子的绝对值均小于有结点的平衡因子的绝对值均小于2 2的二叉树。的二叉树。结点的平衡因子为结点的平衡因子为 1 1、1 1、0 0p查找算法的效率O(log2n）哈希表哈希表p哈希表n一个有限的连续地址空间，用以容纳按哈希地址存储的记录。一个有限的连续地址空间，用以容纳按哈希地址存储的记录。p哈希函数n记录的存储位置与它的关键字之间存在的一种对应关系。记录的存储位置与它的关键字之间存在的一种对应关系。n Loc(ri)=H(keyi)p冲突n不同的两个关键字经过哈希函数运算后所得到的散列地址相同不同的两个关键字经过哈希函数运算后所得到的散列地

30、址相同n理想情况下没有冲突，查找复杂度理想情况下没有冲突，查找复杂度O(1)n一般考虑哈希表，冲突是不可避免发生的；一般考虑哈希表，冲突是不可避免发生的；p同义词n在同一地址出现冲突的各关键字。在同一地址出现冲突的各关键字。 p哈希(散列)地址n根据设定的哈希函数根据设定的哈希函数H(key)和处理冲突的方法确定的记录的存储位置。和处理冲突的方法确定的记录的存储位置。p装填因子n=记录数记录数/哈希表长度哈希表长度n1 必然冲突， 1也有可能冲突哈希函数的构造方法哈希函数的构造方法p直接定址法：nH(key)=a*key+b，a、b为常数；为常数；p数字分析法n分析关键字，找出其中几位数字作散

31、列地址（例如：指针值）分析关键字，找出其中几位数字作散列地址（例如：指针值）p除留余数法nH(key)=key % p （求余数）（求余数）np可以选用素数，更有利于可以选用素数，更有利于“散列散列”，少冲突，少冲突p伪随机数法n选取一个用关键字作为种子的伪随机数发生器生成散列地址选取一个用关键字作为种子的伪随机数发生器生成散列地址解决冲突的常见三种方法解决冲突的常见三种方法p线性再探测线性再探测法法p链地址法链地址法n散列表设立指针，将所有散列地址为此位置的关键字散列表设立指针，将所有散列地址为此位置的关键字记录用单链表形式存储起来；记录用单链表形式存储起来；p公共溢出区法公共溢出区法n建立

32、公共溢出区，将所有发生冲突的关键字记录存储建立公共溢出区，将所有发生冲突的关键字记录存储到公共溢出区中去到公共溢出区中去 有一组关键字序列（38、59、125、168、216、719、455、20），用函数 H(key) = key % 10 将其按顺序散列到散列表 HT(0:9) 中，分别用三种方法解决冲突：线性再探测法、链地址法、公共溢出区法，画出这三种方法建立的散列表，并分别求在等概率情况下查找成功和不成功的平均查找长度。例：例：0123456789 3859125 216168 71945520ASL成功 = = = 281683+3+3+1+1+3+1+1ASL不成功 = = = 4

33、.61046104+3+2+1+1+9+8+7+6+51、168 168719719455 4552020ASL成功 = = 81181+1+2+1+1+2+1+2ASL不成功 = = = 1.81018102+1+1+1+1+3+2+1+3+32、01234567893859125216201687194550123456789 3859125 216168 719 45520ASL成功 = = 81481+1+1+1+1+2+3+4ASL不成功 = = = 31030105+1+1+1+1+5+5+1+5+53、012345 公共溢出区：168 719455719455 455第十章第十章 内部排序内部排序基本概念基本概念p排序