期末数据结构复习的一点笔记

选择 2*10 填空 1*20 主要形式为概念题和计算题 算法应用题 二叉树序遍历、哈夫曼树、最短路、最小生成树、拓扑序、关键路径 画图解决问题+概述算法思路+复杂度分析 程序填空题 二叉树序遍历、拓扑排序、堆排序 暂未包含： 程序阅读&程序设计

1

2

3

4

5

6

7

8

9

10

11

12

13

数据，对客观事物的符号表示，图像声音等。

数据元素是数据的基本单位，如学生记录。

数据项是不可分割的最小单位，如姓名学号。

数据对象是具有相同性质的数据元素的集合。

数据结构是互相之间存在关系的数据元素的集合。数据结构={D、R}构成。

数据结构三要素：逻辑结构、存储结构、数据运算 （罗村树）

逻辑结构分4类：线性，树，图，集合。

逻辑结构包括线性（线性表、栈、队列）和非线性（树、图、集合）结构。线性结构的特点：所有成员处于一个序列，有且仅有一个直接前驱和后继。

存储结构包括顺序、链式、索引、散列存储。 （顺联锁伞）

算法的五个特征：有穷性、确定性、可行性、输入、输出 （有缺课出入）

线性表

按照存储结构的不同，分为顺序存储和链式存储分为2类。 1、顺序表（vector） 定义：由相同类型的数据元素构成。 每个元素有且仅有一个前驱和后继。 特点：由一组地址连续的存储单元依次存储。 2、链表 单链表：一个指针指向后继节点。 双链表：两个指针指向前驱和后继节点。 循环链表：没有指向null，判空条件为next指针等于头指针。

1

2

3

4

5

6

7

8

9

10

11

12

栈和队列

操作受限的线性表 1、栈 后进先出，可以顺序和链式存储。 共享栈，即对顶栈。 2、队列 先进先出，可以顺序和链式存储。 循环队列：fr==ed

1

2

3

4

5

6

7

8

9

10

串

有多个字符组成的有限序列。 串是一种特殊的线性表，特殊性体现在数据元素可以是字符。 1、模式匹配算法： 简单匹配，求子串在主串中的位置 改进匹配：KMP算法及优化 2、矩阵的压缩存储： 对称矩阵，上下三角矩阵等 对称矩阵，下三角放入一位数组 B[n(n+1)/2]中，Aij对应i(i-1)/2+j-1或者代换aij=aji 上三角矩阵（含常量c），n(n+1)/2+1。aij=（n+n-i+2）(i-1)/2+(j-i)

1

2

3

4

5

6

7

8

9

10

11

12

树的基本概念（选择题）

节点的度：节点的孩子个数。 树的度：树中节点的最大度数。

树中节点数 = 总度数+1。（重要）

总度数 = 边数的2倍。 （重要）

树的深度是从上往下的，高度是从下往上的，值都一样。

度为m的树中，第i层上最多有m^i-1个节点。

高度为h的m叉树中，最多有(m^h-1)/(m-1)个节点

有序树左右节点无法互换。

二叉树概念（选择题）：

父节点编号为i/2。

叶子节点个数 = 度为2的节点数+1，即n0=n2+1。

证明， 因为n = n1+2*n2+1， 且n=n0+n1+n2。

第k层有2^k-1个节点。

存储方式

顺序存储：构造成完全二叉树，用0填空，层次存入数组。

链式存储：指向左右孩子指针。

遍历：先序，中序，后序，层次（大题）

树转二叉树：在兄弟节点间加跟线，根节点只保留第一个孩子的连线。

森林转二叉树，每棵树都先转二叉树，然后兄弟节点连线，保留第一跟，顺时针转45度。

几种特殊的树（大题）

二叉排序树，左子树<根节点<右子树。

中序遍历为从小到大排序。

哈夫曼树

节点带权路径长度，为任意结点到根的总和。

树的带权路径长度，为所有叶节点的带权路径长度之和。

图的基本概念（选择题）

无向完全图边数 = n*(n-1)/2， 有向图不需要除2。有向带权图又称为网。

度数总和 = 边数的两倍。

存储结构

邻接矩阵， 邻接表，十字链表，邻接多重表。判断条件。

图的遍历

DFS，BFS，求遍历序列。 一次dfs，连通图。

图的应用（大题）

最小生成树

Prim：去掉所有的边，任选一个顶点。选点（与当前点集最近，不构成回路）。重复直到联通即可。

Kruskal：去掉所有的边。 选边（边权最小，不构成回路）。重复直到图联通。

最短路

Dijkstra：将点集分为在最短路中的和不在的。每次去不在的中找距离最近的加入最短路加入最短路，并用其去松弛其余边。

拓扑排序

AOV网，顶点表示活动，边表示活动顺序。

每次从AOV网中选择一个没有前驱的顶点输出，并删除该顶点和所有以它为起点的有向边。

关键路径

AOE网，顶点表示事件，有向边表示活动，边上权值表示活动开销。

关键路径：从开始点到结束点的所有路径中，具有最大路径长度的路径。关键活动为关键路径上的活动，即有向边。

事件vk的最早发生时间为最大前驱。 ve(k) = MAX{ve(j)+weight(vj,vk)};，vj为前驱。

事件vk的最迟发生时间为最小前驱。vl(k) = MIN{vl(j)-weight(vj,vk)};，vj为前驱。

活动的最早开始时间e(i) = 为起点的最早发生时间

活动的最晚开始时间l(i) = 终点的最迟发生事件 — 活动所需时间。

求关键路径：求出所有点的最早开始时间和最晚发生时间。再求出所有活动的最早和最晚发生时间。 额差d()=l()-e()。 d()=0的为关键路径。

查找的考点

查找

查找表（查找结构）：用于查找的数据集合。

关键字：数据元素中某个数据项的值，可以标识一个数据元素。主关键字可以唯一标识。

平均查找长度：所有查找过程中进行关键字比较次数的平均值。 A S L = ∑ i = 1 n P i C i ASL=\sum_{i=1}^nP_iC_i ASL=∑i=1n Pi Ci

Pi为查找第i个元素的概率（一般每个元素都相等，即1/n），Ci为找到第i个元素需要的比较次数。

顺序查找的平均查找长度为 ：成功 = ∑ i = 1 n 1 n ( n − i + 1 ) = n + 1 2 \sum_{i=1}^n\frac{1}{n}(n-i+1) = \frac{n+1}{2} ∑i=1n n1 (n−i+1)=2n+1 ， 失败 = n+1。

折半查找的平均查找长度为：成功 = n + 1 n l o g 2 ( n + 1 ) − 1 \frac{n+1}{n}log_2(n+1)-1 nn+1 log2 (n+1)−1。

折半查找比较次数，可以画出判定树，看路过几个节点。

散列表

一种散列存储方法。

散列函数Hash(key) = Addr。把两个不同关键词映射到同一地址称为同义词。

（1）直接定址法： H(key) = a*key+b。（2）除留余数法： H(key) = key%p。

散列冲突的处理方法 & 构造散列表：（大题）

（1）开放定址法：线性探测法di=0,1,2。平方探测法di=0^2,。再散列法di=hash2(key)

查找不成功的平均查找长度 = 查找次数（1+13+12+。。2） / 散列后的地址个数（13）=7

（2）拉链法： 存放到线性链表中。 ^符号表示后继指针为空。

散列表的查找长度取决于3个因素：散列函数，冲突处理方法，装填因子。

装填因子a = 表中记录数n / 散列表长度m。 a越大，记录越满，冲突可能性越大。

排序的考点：

排序的概念

稳定性， 相对位置保持不变。

内部排序：元素全部在内存中。基于比较和移动。外部排序需要外存。

插入排序

直接插入排序：假设已经排好序，插入即可。

希尔排序：把相隔某个增量的记录组成一个子表，对各个子表进行直接插入排序。整体基本有序后，整体直接插入。

空间O(1)，时间不确定，不稳定。一般初始是稳定的，优化后不稳定。

e.g，取增量d=5，组成多个子表，各排一次。再取d=3，再排一次。最后取增量d=1，即整体插入排序。

交换排序

冒泡排序。优化后快速排序。

选择排序：

简单选择排序。优化后堆排序。

堆指的是：根节点比左右节点小或大的二叉树。

构造大根堆：默认序列是二叉树。

归并排序

基数排序（基于关键字的各位大小）

先分配：先按照个位进行分类，构造链表。

再收集：按照顺序写到一起。

以此类推，操作十位和百位，最后就有序了。

给生日排序，基数排序是比较快的。

数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。