数据结构知识点总结

代价：算法消耗的资源量
有效率的：算法能在要求的资源限制内解决问题
比较方法：实证分析、仿真、渐进算法分析
规模：输入量的数目
基本操作：简单算术、简单布尔运算、赋值语句、返回语句、I/O语句
增长率：随输入规模增加，算法代价的增长速率，即复杂度
情况：最佳、最差、平均情况
上限：对T(n)，若存在c和n，使当n>n0时，有T(n)<=cf(n)，则T(n)在O(f(n))中
结构性开销：并非真正数据的附加信息
数据结构：数据的存储(物理结构)+数据间的逻辑关系+基本操作(初、插、增、删、查)
抽象数据类型：元素集合(对象)+元素关系(集合、线、树、网)+基本操作(初、增、删、查、插)
数据结构是抽象数据类型的实现
问题解决顺序：问题描述，问题分析(对象，功能，显示)，抽象类型(对象，关系，操作)，详细设计(输入，处理，输出)，物理实现，算法分析
回答顺序：问题描述，算法思想，算法步骤，算法分析
阐述一：这个算法在(最优/最差/平均)情况下的增长率的上限在O(n)中
阐述二：对于问题的锁在(最优/最差/平均)情况下的输入，只要输入规模足够大，该算法总能在cf(n)步内完成
四条原则：
f(n)在O(g(n))中，g(n)在O(h(n))中，则f(n)在O(h(n))中
f(n)在O(kg(n))中，k>0，则f(n)在O(g(n))中
f1(n)在O(g1(n))中，f2(n)在O(g2(n))中，则f1+f2在O(max(g1(n),g2(n)))中
f1(n)在O(g1(n))中，f2(n)在O(g2(n))中，则f1f2在O(g1(n)g2(n))中
已知T(n)求复杂度，如T(n)=c1n^2+c2n，n>1:
c1n^2+c2n<=c1n2+c2n^2<=(c1+c2)n2，取c=c1+c2，有T(n)<=cn^{2，有T(n)在O(n}2)中
c1n^2+c2n>=c1n2，取c=c1，有T(n)>=cn^{2，T(n)在Ω(n}2)中
上下限相等的时候，可用θ(n)表示
线性表：最简单最常见的线性结构，有多个类型相同的元素按线性关系组成有限序列
用’|'表示当前位置，即栅栏
顺序表是在计算机内存中以数组形式保存的线性表。用一组地址连续的存储单元一次存储线性表中的各个元素（即数组），很难在表头或表中插入元素
链表是利用指针，有一系列称为表的结点的对象组成的。结点是一个独立的对象
顺序表每一个元素都没有浪费空间，链表每一个元素都要附加一个指针；顺序表的大小需实现固定，链表大小没有限制
前驱：ai-1，后继ai+1
栈：在一段执行插入和删除的线性表，后进先出
队列：在一段插入，一段删除的线性表，先进先出
树：一种动态的、非线性的、可描述结构层次特性的数据结构
结点：数据元素+若干指向子树的分支
结点的度：分支的个数
树的度：树中所有结点的度的最大值
将树转化为二叉树：左子节点是原树中最左子节点，右子节点是右侧兄弟节点，森林的话从左往右依次是根节点的右子节点
层次：设根节点的层次为1，第i层为i+1
路径：由根到该节点所经分支和节点构成
结点的路径长度：根到该节点的路径上的分支数目
树的路径长度：每个节点路径长度之和
树的深度：树中叶子节点所在的最大层次
树的高度：从根节点到树中最深节点的路径长度，=深度-1
二叉树：一个根节点+两棵二叉树
满二叉树：每个分支节点桥有两个子节点且所有叶子结点在同一层
完全二叉树：每一层从左到右连续填充
非空满二叉树的叶子结点数等于其分支节点数+1
树的顺序表示法：所有空节点(包括叶结点的子节点)画出，进行前序遍历
树的表示：根(T1,T2,T3)用逗号隔开
遍历：顺着某一条路径寻访结点，每个节点均一次且仅一次
层次遍历：从上向下，从左到右
前序遍历：先根节点，再左子树，再右子树
中序遍历：先左子树，再根节点，再右子树
后序遍历：先左子树，再右子树，再根节点
BST：二叉搜索树，左子树<根节点<右子树，中序遍历得到递增序列
BST删除最值：最小值，将最小值结点的右孩子赋值给最小值父节点的左孩子；最大值：将最大值结点的左孩子赋值给最大值父节点的右孩子；一般值：将右子树中的最小值赋给删除结点
堆：完全二叉树，要么根最小，要么根最大，通过先建立任意一颗完全二叉树，再交换元素得到，用于得到递增递减数列或最小最大值
堆插入：在最后一个元素后一个位置插入，然后交换
堆删除：与最后一个元素交换位置，删除，然后交换
字符编码：对字母和符号进行二进制代码的编码
前缀编码：没有编码是另一个的前缀
编码长度：字符的频数(权值)乘二进制编码的位数
Huffman树：中间节点不存储数据的最优(满)二叉树，没有度数为1的点
Huffman树的构建：贪心算法，先得到n个叶子树，按权值大小排一列，拿走前两棵作为新树放入队列，重复直到仅有一棵树
线索：指向前驱和后继(遍历方式决定)结点的指针
线索化：对二叉树进行某种次序遍历并加上线索叫线索化，实质是将二叉树结点中的空指针域填上相应节点的前后地址
线索化步骤：先加上一个头结点，在进行一次中序遍历，每次保存前面的地址
等价对：两个节点之间存在通路
重量权衡规则：将结点较少的根指向结点较多的树的根
路径压缩：查找一个节点x的时候，将从根节点到x的所有节点的父指针指向根节点
解决步骤：先写出所有的结点，按照节点的等价关系写出箭头，根据两个规则进行化简，注意题目要求，并查对的指向性不改变
图：可用G=(V,E)表示，V为顶点集合，E为边集合。图分为有向图，无向图，完全图，标号图，带权图，无环图
路径：顶点序列V1,V2,…,Vn的边都存在，则称其为一条长为n-1的路径，若路径上的各顶点各不相同，则称为简单路径。路径长度为所包含的边数（或边权数之和 ）；若一条路径将某个顶点连到它本身，且长度大于3，则称为回路
连通：无向图中任意一个顶点到其他顶点至少存在一条路径。最大连通子图称为连通分量
邻接矩阵：通过一个一维数组（编号+标号）表示点，和一个二维数组（邻接矩阵）表示边，矩阵中元素为边的权值，左起右终，越密集越高效
邻接表：通过一个一维数组（编号+标号）表示点，和一个以链表为元素的数组，数组中为编号而非标号（邻接表）表示边
逆邻接表：通过一个一维数组（编号+标号）表示点，和一个以终点为弧头存边（邻接表从起点指向终点的指针，逆邻接表从终点指向起点的指针）表示边
十字链表：邻接表+逆邻接表
图的深度优先遍历DFS：当访问某个定点是，递归的访问他的所有未被访问的相邻顶点，把所有从该点出去的边存入栈，从栈顶弹出一条边，从该边找到一个相邻顶 点为下一个要访问的顶点，重复直到这个分支完成，再回溯访问下一个分支。即一头到底
图的广度优先遍历BFS：先检查七点的所有相邻结点，写入队列后深度访问。每当一个顶点的所有相邻接点被访问之后，出队，直到队列为空。即一圈一圈搜索
拓扑排序：将一个有向无环图DAG中所有顶点在不违反前置依赖条件下排成线性序列的过程。通过DFS，递归返回到该节点时输出，再逆序倒置得到
最短路径问题：有Dijkstra算法和Floyd算法
Dijkstra算法：对指定的点到其他店，非负权值。从已经处理的顶点的集合A中任取顶点U，都有一条从S到U，再由U到X的边的权值最小
Floyd算法：DJ算法的全局版，可正可负，从所有可能路径中选择最短，三重循环比较D(v,k)+D(k,u)与D(v,u)的值
最小生成树MST：一个包括图中所有顶点以及一部分边的图，要求边的权值之和最小，且保证图连通，必无回路，有prim算法和kruskal算法
prim算法：与DJ很像，主要区别是DJ是寻找距初始点最近的点，而prim是寻找距离整个MST最近的点
kruskal算法：先将顶点集合分为|V|个等价类，每个类包含一个顶点，然后按照边权大小处理每一条边，如果一条边连接属于两个不同等价类的顶点，则添加到MST中，并合成为一个等价类，直到仅有一个等价类，不用初始点
查找：分为基于线性的查找，基于树的查找和基于散列的查找（直接访问）
静态查找表：构建+查找；动态查找表：构建+查找+插入+删除
索引：把关键码KEY和数据位置关联的过程
平均查找长度：比较次数
线性查找：分为顺序查找，二分查找，自组织线性表，集合检索和分块查找
顺序查找：输入一组数据元素和待查找的值，用线性表无序存储，从一端开始，逐个查找
二分查找：必须是顺序结构，必须大小有序排列，不适合链表，采用分治法。定义两个指针分别指示待查范围的下界和上届，在范围大于1的时候比较中间处的值 ，进行缩小范围，直到范围为1，如果还没有则不存在。
自组织线性表：根据实际的记录访问在线性表中修改记录顺序，有三种修改规则：1、计数方法，为每条记录保存一个访问数，且一直按照这个顺序访问；2、移至前端：如果找到一条记录，则放到最前面；3、转置方法：把找到的记录与他之前的记录交换位置
集合检索：在关键码值优先的情况下，使用一个位数组（向量），为每一个可能的元素分配一个比特位空间，用来标识这个集合。对每一个关键字，标识一个维向量，每一个文档占一位；或者对每一个文档，标识一个位向量（签名文件）每个关键字一个bit位
分块查找：分块有序，前一块中的max小于后一块中min，去max及起始位置成索引，通过二分找到合适的块，再通过顺序找到值
树形查找：有二叉搜索树BST，平衡搜索树AVL，多路平衡搜索树B树，Trie树字典树，空间数据结构K-D树
BST：左小右大
AVL：BST的升级版，由左旋和右旋的到左右子树深度近似相等的二叉树，高度趋近于logn
B树：平衡多叉树，大规模，基于磁盘（块）的数据
字典树：三叉搜索树，比BST多了一条分支
K-D树：空间应用程序的显著特征
散列查找：用于精确查找，把关键码值通过某些算术运算，映射到顺序表中的位置来访问记录，由任意大小到固定大小
散列表：用来存放记录的数组，槽的数目为记录数，是一种数据结构，存储关键字及其关联的值，有创、搜、插、删（墓碑）
散列函数：将关键码映射到位置的函数，用h表示。有除留余数法、平方取中法、折叠法
冲突：两个不同的关键码值散列成相同的值
散列两大问题：构造散列函数，处理冲突并设计冲突解决策略
完美散列：一组特定的记录通过散列函数计算的值均不相等
开散列方法：将冲突记录在散列表外
闭散列方法：将冲突记录在散列表内
冲突解决策略：寻找一个替代位置的过程
单链（分离链）方法： 把散列中的槽定义为链表的表头，即数组+链表实现
桶式散列：把散列表中的槽分成多个桶，包含一个亿触痛，把每条记录分配到某个桶中的槽中，若桶满则到溢出桶中，适合磁盘
开放地址法：找到本应的槽，若已被占用则向后找下一个槽，以此类推。分线性探查（直接下移）、伪随机探查（选择一个从1到n-1的随机排列，插入检索都用这个）、二次探查（p(k,i)=i^2）
双散列方法：p(k,i)=ih2(k)，即h1计算基地址，h2计算冲突地址
查找长度：等概率下的平均查找长度（成功）：找到元素时的比较次数的和与元素数的比值；等概率下的平均查找长度（不成功）：找到空槽时的比较次数和与空槽数的比值
排序代价：比较次数和交换次数决定
稳定性：对于关键码相同的记录，稳定为相对次序不变，不稳定改变
简单排序方法：分插入排序、冒泡排序、选择排序，都是相邻元素间的交换
插入排序：逐个处理，每个与已排的比较，插入到合适的位置。稳定排序，n^2，正逆序有差别
冒泡排序：从底部开始，依次比较相邻两元素的大小，重复n-1次，稳定排序，n^2
选择排序：第i次选择第i小的记录，与第i个位置的元素交换位置，不稳定排序，n^2
经典排序方法，分希尔排序、归并排序、快速排序、堆排序，都是不相邻元素间的交换
希尔排序：插入的改进，分步长画区，每个区中进行插入排序，逐步缩小步长直到步长为1，注意序列的位置不变，不稳定排序，n*(logn)^2
归并排序：设有n个待排，分为n个长为1的有序子表，两两归并相邻，直到只有一个子表，稳定排序，nlogn
快速排序：在待排序记录中选取一轴值，轴值与末尾交换，从两边开始移动，必要时交换，直到相遇，后将相遇点与轴值交换位置，重复直到待排序列长度为1， 不稳定排序，nlogn
堆排序：将数组转化为一个满足堆定义的序列，将堆顶取出，剩下重新成堆。先按层次生成完全二叉，然后交换，从最后一个非子节点开始交换，不稳定排序，2nlogn
特殊排序方法：分分配排序、基数排序，不进行元素间比较
分配排序：由关键码来确定一个记录在排序中的位置，直接分配空间。经典为桶式排序，即将元素分配到一组桶中，每个桶分别排，最后遍历每个桶。稳定排序，n+MAXKEYVALUE
基数排序：将关键码看成若干个关键字符合而成，依次对关键字进行分配排序，重复直到有序，直接按顺序插入链表，稳定排序，一般为nlogn，小时为n
最差情况下，任一个基于比较的算法都要nlogn的时间代价

最后

以上就是还单身宝贝为你收集整理的数据结构知识点总结的全部内容，希望文章能够帮你解决数据结构知识点总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。