http://blog.csdn.net/qq_34861102/article/details/76862695数据结构的重要概念总结
最近在看数模的东西的时候发现了图和网络这一块涉及到了数据结构中的一些概念，于是将之前总结的数据结构拿出来看一下，也当是复习，有需要查找的直接control + F查找
原文：http://blog.csdn.net/qq_34861102/article/details/76862641
-
详细内容：
这里内容有点多，我将目录单独写一个博客
传送门：
数据
·是计算机加工处理的对象
·分为数值数据和非数值数据
·非数值数据
·数值数据包含整数、实数、复数
·非数值类型包括字符
数据元素
·是数据的基本单位
数据项
·是数据的最小单位
逻辑结构
·线性结构、集合结构、树形结构、图状结构
存储结构
·线性存储、链接存储、索引存储、散列存储
数据结构
·数据结构涉及到数据的逻辑结构、存储结构以及数据的运算
·数据结构的规范：是数据的逻辑结构和数据的运算的定义
·数据结构的实现：是数据的存储表示和数据的运算的描述
数据类型
·数据类型是定义了一个值的集合以及作用在集合上的运算
数据抽象
·数据抽象是只关注数据的逻辑结构（错了）
过程抽象
·过程抽象是只关注数据的运算的定义
抽象数据类型
·抽象数据类型就是过程抽象和数据抽象的联合
·使用和实现的分离
·为什么是使用和实现的分离而不是规范和实现的分离，这里是使用的定义,而数据结构式要定义规范和实现，没有使用
·对象和运算的规范与对象的表示和运算的实现分离
数据结构的规范
·是数据的逻辑结构和数据运算的定义
数据结构的实现
·是数据的存储表示和运算的的实现
算法描述
·算法有五个特点 至少有输出 可以没有输入 无二义性 有穷的 可运行
·算法是一系列有穷的指令序例，用于解决某一特定问题的一系列运算
算法分析
·一个好的算法要有的条件：
简明、健壮、正确、效率
·算法分析目的：
分析算法的效率以求改进算法
算法的时间复杂度
·目的：分析算法的时间复杂度和问题规模的关系
·有最好、最坏、平均
算法的空间复杂度
·目的（不知道）：分析算法的空间复杂度与问题规模的关系
·通常考虑最坏情况
线性表
·是n个元素的线性序列
顺序表
·就是按顺序存储的线性表
顺序表长度
·顺序表的长度是n也是线性表的长度
顺序表在程序中的表示
·即相关程序
顺序表插入算法
·插入就是直接增加元素，后移后面的元素
顺序表删除算法
·删除就是直接减少元素，前移元素
单向链表
·带表头结点和不带的，都有first指针
双向链表
·两个域，一个字段，对应llink和rlink
表头指针
·first指针，指向第一个或者表头结点
表尾指针
·最后一个结点的next称为表尾指针，单向链表就是null
表头结点
·方便运算加的一个结点
循环单向链表
·即表尾指针指向一个第一个结点的元素
循环双向链表
·最后一个的右指向第一个元素的左
单向链表定位算法
·顺着指针往后面找
单向链表插入算法
·改变链接的位置
单向链表删除算法
·同
双向链表插入操作步骤
·
双向链表删除操作步骤
·
栈
·栈是一种数据结构
·是线性表，限制访问的
·限定线性表的插入和删除操作在同端进行
队列
·一种数据结构
·是线性表，限制访问的
·限定线性表的插入和删除操作在不同端进行
栈顶
·进行操作的一端
栈底
·不进行操作的一端
队首
·进数据的一端
队尾
·出数据的一端
顺序栈
·栈的顺序存储结构是顺序栈
链接栈
·栈的链接存储结构是链接栈
栈顶指针
·用来专门指出栈顶元素所在的位置，即Top
顺序栈在程序中的表示
·即代码表示
链接栈在程序中的表示
·即代码表示
顺序队列
·队列的顺序存储结构
链接队列
·队列的链接存储
队首指针
·就是在队列的插入输出的时候，那个往中间移动的，为于队首元素的前一个，即往右移动就是出队
队尾指针
·指向队尾元素，向右就是进队，刚开始的时候在2个指针都在一个位置，就是空队，然后是先进队，就是队尾指针移动
顺序队列在程序中的表示
·记住是限定插入和删除的线性表的顺序存储
链接队列在程序中的表示
·同理，限定插入和删除的线性表的链接存储
顺序栈插入删除算法
·自己构造了一个数组，通过Top指针来插入和删除这个数组内的元素
顺序队列插入删除算法
·这个的就是2个指针的移动，实现自己的那个数组的元素插入和删除
链接栈插入删除算法（自己的扩充）
·我觉得应该Top指针和first指针一样，并在基础上改变相当于单向链表的在一开始插入和删除，可实现要求
链接队列插入删除算法（自己的扩充）
·同上，一个放在链表最后，一个放在最前面，进来在前面插入，出去在后面删除
树
·有根树的简称，必须含有根，不能为空
树根
·有根树的一个定义，就是不存在另外一个到这个点的边的存在，其中关于其余的点，只存在一个点也就是双亲可以存在到该点的边
子树
·有根树的另外一个定义，分成了很多个除根结点外的互不相交的集合，这些集合也就是子树
二叉树
·二叉树是另外一种树形结构，可以为空，由一个根和互不相交的2颗二叉树构成（递归定义）
左子树
·靠左的那颗二叉树
右子树
·靠右的那颗二叉树
双亲结点
·A点的双亲结点是树中唯一存在<b,A>存在的b点
孩子结点
·b点的A
兄弟结点
·有同一个b点的点
分支结点
·度不是0
终端结点
·度为0
树叶
·度为0
结点的度
·儿子的数量
树的度
·结点中最大的那个度
结点的层
·即深度
森林
· 由若干颗树组成的集合
森林与二叉树的转换
·左边是儿子，右边是兄弟，森林到二叉树，第一颗树的根是根，第二颗树的根相当于它的兄弟
树的高度
·就是最后那一层的结点的层吧？？
树的双亲数组存储表示
·这种方法方便寻找子结点的双亲结点
·就是地址值，双亲的地址值，元素值
树的二叉链表存储表示
·左孩子，右兄弟，中间元素值
满二叉树
·满二叉树2的n次方-1个结点
完全二叉树
·从0开始存储结点，结点为i的二叉树的左子树是2i + 1
·因此要求最小一层靠左，中间不能断，即一直满足上面的条件
二叉树的顺序存储表示
·顺序，按照逻辑位置来，就比如层次遍历，形成一个数组
二叉树的二叉链表存储表示
·左子树 元素值 右子树 2个域指向不同的字段，一个字段
树的前序遍历规则
·先访问根，在访问根的子树
树的后序遍历规则
·访问子树后，再访问根
树和二叉树的层次遍历规则
·以队列来理解，当爸爸出队的时候，儿子们就可以进来了，这样就会是层次的
二叉树的前序遍历规则
·根 左 右
二叉树的中序遍历规则
·左 根 右
二叉树的后序遍历规则
·左 右 根
二叉树结点的前序序列
·前序遍历得到的
二叉树结点的中序序列
·中序遍历得到的
二叉树结点的后序序列
·后序遍历得到的
二叉树的递归遍历算法
·采用2个函数，第一个函数通过树开始访问根结点，并且开始遍历的操作左右子树，就像实际遍历的过程中的思路上是一样的。
二叉树的带权路径长度
·叶子的值为权，所有叶子的权和边数目的积的和就是二叉树的带权路径长度
最优二叉树
·对于相同的权值叶子结点，得到最小的带权路径长度
哈夫曼树
·哈夫曼算法构造而成的二叉树
哈夫曼树的构造过程
·依次在叶子的权值中取2个最小的权值相加（形成树），代回，接着操作
哈夫曼编码
·经过的双亲到左子树的边为0，到右子树的边为1，这样每个叶子就有一系列的编码
有向图
·边是不是有方向的
无向图
·边是没方向的
完全图
·每2个不同的点都有路径存在
顶点
·就是点
相邻顶点
·有存在边的，有向图只有一条路径也算是相邻顶点
与顶点相关联的边
·相邻顶点的那一条边
顶点的度
·相关联边的数目
顶点的出度
·有向图的特有，即以该点为出发点的边数目
顶点的入度
·有向图的特有，即以该点为终点的边数目
子图
·点和边都是图的集合中的一部分
路径
·2个点的路径是经历的边
路径长度
·经过边的数目
回路
·初始点和终点相同的简单路径
简单回路
·个人认为和回来概念冲突
简单路径
·路径只有初始点和终点可以相同的路径
连通图
·无向图每2个点之间都有路径可以到达
连通分量
·无向图含有的点的集合中部分点，这些点可以通过边的集合的边构成连通图，这个连通图就是连通分量
强连通图
·有向图每2个点之间都有路径可以到达
强连通分量
·有向图含有的点的集合中部分点，这些点可以通过边的集合的边构成强连通图，这个连通图就是强连通分量
有向图的根（重要）
·到每一个点都有路径可以到达
网络
·无向图的边用权值表示，有向图边没有权值
邻接矩阵
·没权值时，无向图一条边相当于有向图的一来一往的两条边
·有权值时，矩阵中是用0，∞，权值表示 仅仅包括无向图
邻接表(只保存出边的邻接表)
·第一排时放出发点的
·从第二排开始，一个字段，一个域，字段时终点的值，域指向这一排的下一个结点
图的深度遍历规则
·随机开始一个邻接结点进行访问
图的广度遍历规则
·相当于层次遍历，先把开始访问的邻接结点都访问完毕
图的深度遍历算法
·一个判断数组，来判断这个元素是否已经访问，用邻接表的表示来寻找下个点，见其方法，这个是直接下一个没有访问过的邻接点就可以
图的广度遍历算法
·一个判断数组，来判断这个元素是否已经访问，用邻接表的表示来寻找下个点，见其方法，这个还要判断是不是当前这个结点的都访问完毕，就需要加上一个while循环，相当于形成了递归
生成树
·一个连通图的极小连通子图
生成树林
·非连通图生成的连通变量生成的
深度优先生成树
·使用深度遍历算法的图的生成树
广度优先生成树
·使用广度遍历算法图生成的生成树
最小生成树
·权值最小的极小连通子图
普里姆方法
·每一次没有连通的结点的，找最小的权值的边
迪杰斯特拉方法
·单源最短路径的方法
·确定每一个最短路径
·先找到了一个最短路径，看通过这个路径，可不可以让其他路径变短，然后修改，确定一个最短路径
·再找到另外一个最短路径，除开始的那个最短路径，找有没有到其他路的最短路径
拓扑排序
·先把入度为0的结点排出，然后删除结点，在排出入度为0的结点
拓扑序列
·如上
拓扑排序方法
·如上
拓扑排序算法
·这里是用的邻接表，可以根据判断这个顶点的入度（通过邻接表遍历每一个结点，看有没有以这个点结尾的结点，有一个入度加一），放入数组（数组是自己定义的）中，让出入度是0的，输出这个结点，通过邻接表把这个点的邻接点的入度减一，这样就达到删除的结点的目的
AOV网
·用顶点代表事件
关键路径
·在AOE网中开始点的最终点的的最长路径
关键活动
·关键活动是在关键路径上，延期就会对整个工程有影响，所以应该是关键路径上的
AOE网
·用边表示事件，边的权值就是事件完成要的时间
求关键路径的方法
·求最早开始时间和最晚开始时间
·最早开始时间和最晚开始时间
·相同的就是关键活动
·关键活动组成了关键路径
·最早开始时间，求最长的路径，因为必须满足拓扑序列中的上一个相邻接的事件完成才可以开始当前事件，因而是最长的路径
·最晚开始时间就是在已经知道最早开始时间的基础上，通过去减去到终点的路径中最小的那一条。这就是最晚可以开始的时间，再晚就要延期了
关键字
·可以用来判断数据元素的数据项
主关键字
·可唯一判断
次关键字
·不可唯一判断
平均查找长度
·即进行一次查找平均要用的查找次数
顺序查找算法
·就是从0到n-1查找
·因此可以是顺序存储和链接存储都可以访问到
·而其中的有序和无序则要涉及到要不要加上哨兵元素
顺序查找的平均查找长度
· （n+1）/2 吧
折半查找方法
·找中间的元素，再去访问左还是右
·因此，这个是要有序的，对于链接存储，因为链接要求顺序存储的，因此无法找到中间开始
折半查找算法
·因为只能在顺序存储的有序表，设置3个整数值 a是第一个元素的数组地址 b是最后一个元素的地址
c = （a+b）／2也就是开始折半的那个元素
·在判断小于R【c】的时候，b = c -1
·大于的时候，a = c + 1
·再进行折半，以此类推
折半查找的平均查找长度
·具体的问题的时候 m个元素，求每个要的次数，相加的和除以m是平均长度
·当一般化的时候，O(log2`n) 失败是log2`n向上取整或者再加一（会因为n的奇偶）
·搜索成功不超过搜索失败的次数，一般化只有O(log2`n)这个数量级
二叉排序树
·在用折半搜索的方法得时候，相类似的那一棵树，就是中序是一个递增的
二叉排序树查找方法
·先比较根结点来判断要进入左子树还是右子树（较大和较小的进入右和左，等于则成功）
·进入子树后循环这个概念
二叉排序树插入方法
·相类似的，先查找一波，没有再插入
·插入的时候，根据值的大小，先选择进入左子树还是右子树
·一直到某一次的左子树或者右子树出现了null，表述就可以插入那个点
二叉排序树删除方法
·没有儿子的时候，直接杀了
·有一个儿子，杀了，让儿子代替
·有2个孩子，杀了，中序遍历后一个的那个点代替，那个点相当于被杀了，开始看它有没有孩子，再依次执行这些操作
二叉排序树查找算法
·算法严格意义上按照递归的方法，遍历每一个结点
二叉排序树插入算法
·先查找
·查找后，实现方法的递归的操作
二叉排序树删除算法
·如上方法
平衡二叉排序树
·平衡因子绝对值不能大于二的二叉搜索树
平衡因子
·左子树的深度减去右子树的深度
平衡二叉排序树插入方法
·插入，和二叉搜索树一样
·重组，插入的时候发现平衡因子的绝对值大于二要进行重组，防止大于2
·重组的方法，=。 =
树型查找的平均查找长度
·和折半方法的一样
散列表
·是一个通过关键字
·用一个数组ht[m]来存储散列函数得到的地址，m为散列表的长度
·因此这种存储也叫散列存储
散列函数
·散列函数是值域0到m-1，自变量是关键字的函数
散列冲突
·一个地址有2个关键字可以得到，这就是产生了冲突
散列地址
·关键字为k的元素的散列地址是ht[k]
处理冲突的线性探测法
·双散列函数的次散列函数为1的情况
双散列函数法
·定义了2个散列函数，主散列函数是对的，而次散列函数相当于发生冲突的时候，迈过的步子大小，这样可以减少线性探测法连续一片需要花费太多的时间的问题
拉链法
·每一个ht数组的元素都还有一个数组，里面存放着地址相同的散列表的元素
散列表的插入方法
·先查找
·对于查找，这个时候就要用考虑到散列冲突
·寻找过程中（见下），会通过解决散列冲突的方法，已经把pos（第一个空的位置）的值改变了，因此插入只要ht[pos] = x就可以实现了插入，至于表满的情况和已经找到的情况可以通过ResultCode的返回值发现
散列表的查找方法
·噗，查找过程中，先来判断是不是已经以及存在，存在就反悔成功，不存在则进去，开始找空的位置，如果应该放的位置被占了，这个时候就开始散列冲突解决，这样将找到的第一个空的地址，然后标记（就是给pos赋值），如果pos为-1，就表示表满了，返回Overflow，否则返回Notpresent
散列查找
·O(1)
散列表的负载因子
·就是装载密度，实际存储结点数／空间数
排序码
·通常是次关键字
·用于排序
直接插入排序方法
·开始第一个元素一个组，后来慢慢一个一个地加，加的过程排序，比较，较小则往前比较，较大则就不动了，停下来。
·最怕的是反顺序，这样就要一直移动
简单选择排序算法
·不管怎么样，都有O(n`2)的比较
·开始的所有元素一个组，然后从里面剔除最小的元素出来，是一个从n到1的过程，上面是从1到n
·好像没什么影响，但是不管怎么样，都有比较
堆的定义
·一种优先权队列，堆是一种特殊的树形数据结构,每个结点都有一个值.通常我们所说的堆的数据结构,是指二叉堆.堆的特点是根结点的值最小（或最大）,且根结点的两个子树也是一个堆.
快速排序算法
·最坏的时候就会变成冒泡排序
·先挑一个元素出来，大于它的放右边，小于它的放左边
·这样先固定好一个位置，接着拿元素出来进行这个操作
·它是速度最快的，但是存储空间是O(lon2`n)，递归用的
·最坏的就是有顺序，顺序和逆顺序都不好
排序的稳定性
·就是排序码相同的元素相同的，排序以后，相对位置不变的排序
·判断的方法，是不是针对整个数组进行操作了
·这里是冒泡排序、归并排序、直接插入排序是稳定的
内排序
·是在内存中进行的排序，这里的六个都是内排序
冒泡排序
·不停的比较2个元素，大的向后移动，小的向前移动，一直到没有元素的移动才算结束
·注意：排序码较大的也可能往前移动，因为碰到了更大的
·最好是顺序，最坏是逆顺序
堆排序
·堆排序是每次构造最大堆，然后把最大的，也就是堆顶的放到最后，其余的重新构造最大堆，再进行交换，再构造，这样就可以得到一个序列
·最好堆序列，可以少一点移动元素
·
归并排序
·先是每一个元素一个小组，然后一个一个地合并，在合并的过程中，自己构造一个数组，在构造过程中，就比较，用自己的数组帮忙排好序，然后再从这里面放回原来的数组中，完成了合并后排序
·因此最好是顺序，这样可以少一点比较，但是移动都是要的，影响不大
·要O（n）的存储空间，就是自己的辅助数组
算法
·冒泡排序
·说一个实现的方法：自己定义一个元素n，初始值为0，用来记录元素移动的次数，每一次比较开始（比较整个序列每两个相邻的元素的值），赋值n为0，然后一次比较完成后，看n的值，如果什么时候n为0，表面了冒泡排序完成
·堆排序
·主要是构造堆的那个算法，每一次交换最大值和最后一个元素交换后，都重新构造最大堆，通过n（序列的元素个数）—的方法，剔除已经选出来的最大值，这样，就可以一直进行下去直到n为1