Question

《数据结构》笔记

Answer 1

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的一门学科

四类基本数据结构： 集合，线性，树，图

数据类型： 一组性质相同的值的集合以及这个集合上的操作的一组总称

抽象数据类型：指一个数学模型以及定义在该模型上的一组操作

算法：对特定问题求解步骤的一种描述，指令的有限序列

算法的五个特性：有穷性，确定性，可行性，0个或多个输入，1个或多个输出

算法的设计要求：正确性，可读性，健壮性，高效率，低存储

时间复杂度的计算：只考虑 基本操作（可以这么理解：最深那一层括号中的语句都属于基本操作） ，即基本操作的重复次数是问题规模n的某个函数f(n)，记作：T(n) = O(f(n))

频度： 基本操作的执行次数

加工型操作：会修改元素

引用型操作：只用不改

线性表： n个数据元素的有限序列

4个唯一：

存储方式

本章涉及到的一些存储结构

栈： 限定在表尾进行插入或删除操作的线性表，后进后出

这里的表尾即是栈顶，表头是栈底

队列： 限定在表的一端插入，另一端删除的线性表，先进先出

插入的一端称为队尾，删除的一端称为队头

本章涉及到的一些存储结构：

串：0个或多个字符组成的有限序列

串相等：两个串长度相等且各个对应位置的字符都相等

子串：由串中 任意个连续的 字符组成的子序列

kmp算法：next数组要解决的时当模式串失配的时候，该指向的位置

next数组的求法

nextval数组的求法

数组：具有 相同类型 的数据元素的集合

两种顺序存储方式：

稀疏矩阵：在m x n的矩阵中有t个非零元素，令 L = t/(m x n)，当L <=0.05时称为稀疏矩阵

广义表： n个元素的有限序列，每一个元素可能是原子，也可能是一个子表

本章涉及到的一些存储结构：

遍历二叉树：巡访二叉树中的结点，使得每一个结点均被访问且仅被访问过一次

线索二叉树：根据遍历二叉树的方法，使用结点的空闲位置，指出前驱结点或后缀结点，实质是在遍历的过程中用线索取代空指针

哈夫曼树： 带权路径长度最短的二叉树

本章涉及到的一些存储结构：

图是由顶点的 有穷非空 集合和顶点之间边的集合组成的

边：无向图中的连线

弧：有向图中的连线

无向完全图：任意两顶点都存在边的无向图，含有n个顶点的无向完全图有n(n-1)/2条边

有向完全图：任意两顶点都存在方向互为相反的两条弧，有n个顶点的有向完全图有n(n-1)条边

权：与边或弧相关的数

网：带权的图

子图：顶点和边各自的子集

在无向图或者有向图中，边的数目总和 = 度的总和/2

连通：如果说从顶点a到顶点b有路径，则称a和b是连通的

连通图：图中任意两个顶点都是连通的

连通图至少有n-1条边，当边的数目小于n-1，则此图一定是非连通图

强连通图：任意两个顶点都连通的有向图

生成树：所有顶点均由边连接在一起但 不存在回路 的图

图的各种存储结构 ：

图的遍历 ：

最小生成树：在一个无向网中，使得各边权数之和最小的那棵生成树

构造最小生成树的两个算法：

最短路径问题：

有向无环图：有向图中不存在环，简称DAG图

AOV网：用DAG图表示一个工程，顶点表示活动

拓扑排序：找到做事的先后顺序

AOE网：顶点表示事件，弧表示活动，弧的权表示活动持续时间

静态查找：只查找

动态查找：查找后插入或者删除

散列表，Hash Table，又称为哈希表，特点：数据元素的关键字与其存储地址直接相关，关键字通过哈希函数（散列函数）确定存储地址

解决冲突：链地址法

内部排序：待排序的所有记录全部放置在内存中

外部排序：待排序的记录个数太多，需要使用到外存