数据结构相关笔记
一，基本概念
[]
**数据：**对客观事物的符号表示；
数据结构（DS）：相互间存在一种或多种特定关系的数据元素的集合；主要指数据的逻辑机构；而数据的物理结构一般称为存储结构； 数据的逻辑结构：数据元素之间的逻辑关系；
-
集合结构：数据元素之间的关系是“属于同一集合”；例如：一个开发团队中的所有成员；<a,b>:ab属于同一小组；
-
线性结构：数据元素之间存在一对一的关系；例如：一个排队购买车票的队伍；<a,b>:a是b的直接前驱； -
树结构：数据元素之间存在一对多的关系；例如：家族的家谱图；<a,b>:
-
图结构：数据元素之间存在多对多的关系；例如：对地域间的航空路线图；<a,b>:
**线性：**每个数据对象可以由他的编号唯一确定，这样的数据对象集的逻辑结构就称为线性；
算法：
-
定义：
-
一般指一个有限的指令集，算法的每一条指令必须有充分明确的目标，不可以有歧义；且其实现不依赖于任何一种计算机语言以及具体的实现手段！
-
在有限步骤内求解特定问题所使用的一组定义明确的规则；
-
类型：数值算法（解数值积分，解线性方程组，解代数方程，解微分方程），非数值算法（排序算法，查找算法，插入算法，删除算法，遍历算法）；
-
特征：应该具有有穷性，确定性，可行性，输入和输出特征；
-
算法的复杂度衡量指标：
- 空间复杂度S（n）：指根据此算法写成的程序在执行时占用存储单元的长度；其一般与输入数据的规模n有关；
-
时间复杂度T（n）：指根据此算法写成的程序在执行时耗费时间的长度；其一般也与输入数据的规模n有关；
算法效率的判定标准： 最坏情况复杂度：Tworst(n); 平均复杂度：Tavg(n);
-
二，线性表
- 定义：由n个类型相同的数据元素组成的有限序列的结合；元素的个数成为列表的长度；n为空时，线性表成为空线性表
线性表的ADT（Abstract Data Type）描述：
1 初始化线性表；
2 销毁线性表；
3 清空线性表；
4 求线性表的长度；
5 判断线性表是否为空；
6 获取线性表忠的某个数据元素内容；
7 检索值为e的数据元素；
8 返回线性表中e的直接前驱元素；
9 返回线性表中e的直接后继元素；
10 在线性表中插入一个数据元素；
11 删除线性表中第I个数据元素；
三，栈和队列
栈：指一种操作受限的线性表；此结构只允许一段进行插入和删除； 允许插入和删除的一端称为栈顶；另一端称为栈底；插入数据称为入栈；删除数据成为出栈；
栈的ADT描述：
- 1，初始化栈；
- 2，入栈；
- 3，出栈；
- 4，获取栈顶元素内容；
- 5，判断栈是否为空；
栈的实现：
- //初始化栈，实际上就是令栈顶指针为-1
- //入栈时，判断栈是否满，若是则返回栈满信息；否则，可以往栈中写入元素；
- //出栈时，判断栈是否空，当栈为空时，不可能有元素出栈；只有栈非空时，才有元素出栈；
- //top指针指向栈顶；
- //top指针为-1时栈为空；
队列：指一种操作受限的线性表，此结构允许在一段进行插入和在另一端进行删除；只允许场如的一端称为队尾9Rear）；只允许删除的一端称为队头（Front）； 队列的ADT描述：
-
1，初始化队列； -
2，入队； -
3，出队； -
4，获取队头元素内容； -
5，判断队列是否为空；
四，串和数组
串：指字符串的简称；由n个字符组成的有限序列，是一种以支付作为数据元素的线性表； 空串和一空格作为字符的串是有区别的！
串同样具有顺序存储结构和粮食存储结构；
矩阵的压缩储存： 矩阵:一个由M*N歌元素排成的m行n列的排列具有一定规律的表；
矩阵类型：
- 对称矩阵：一个N阶矩阵A的元素满足Aij=Aji （1<=i,j<=n）,此时的矩阵称为对称矩阵；
-
对角矩阵：所有非零元素都集中在以主对角线为中心的带状区域中；带状区域主对角线上下各有b条行非零元素的对角线；b称为半带宽；整个矩阵的带宽为2b+1； -
下（上）三角矩阵：以主对角线为界的上（下）半部分为一个固定的值，下（上）半部分的元素之没有任何规律；
五，树和二叉树
树：值一种常用的非线性结构；通常采用递归方式来定义数；
- 1，数是n个节点的有限结合；
- 2，若n=0，则称为空数；
- 3，如果n>0,n个节点中有且仅有一个特定的节点作为树的根节点（简称为根），当n〉1时，其余节点被分成m个不相交的子集T1，T2。。。。，每个自己本身又是符合本定义的一棵树；
树的表示方法：
- 1，树形表示法；
- 2，文氏图表示法；
- 3，括号表示法；
树的基本概念：
- 1，结点：表示树中的元素；
- 2，结点的度：节点的分支数；
- 3，终端结点：结点度为0的结点；
- 4，树的度：树中所有结点度的最大值。通常称度为m的树成为m次树；
- 5，结点的层次：从1开始, 越往下越多, 数字越大 ; 树中根结点的层次为1，根结点子树的根为第2层；
- 6，树的深度：从 0 开始, 越往下越深, 数字越大 ; 树中所有结点的层次的最大值；
- 7, 树的高度: 从 0 开始，越往上越高，数字越大
- 8，森林：m棵互不相交的树的集合；
树的ADT描述：
1，构造一个树；2，清空以T为根的树；3，判断树是否为空；4，获取给定结点的第i个孩子；5，获取给定结点的双亲；6，遍历树；
二叉树：
概念：1，是一种特殊的树；
2，二叉树是n个结点的有限合集；
3，d当n=0，时称为空二叉树；
4，当n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，一个作为右子集；
特点：1，每个结点最多有两颗子树；2，子树有左右之分；
二叉树的运算：
1，构造一颗二叉树；2，清空以BT为根的二叉树；3，判断二叉树是否为空；4，获取给定结点的左孩子和右孩子；5，获取给定结点的双亲；6，遍历二叉树；
二叉树的性质：
1，具有n个结点的飞控二叉树共有n-1个分支；
2，在二叉树的第i层上最多有2的i-1次方个结点；
3，深度为K的二叉树最多有2的k次方-1个结点；
4，对于任意一棵二叉树BT，如果度为0的结点个数为n0，度位2的结点个数为n2，则n0=n2+1;
5，具有n个结点的完全二叉树的深度为[log2N] +1，其中[log2N]表示不大于log2N的最大整数；
完全二叉树：
有一棵深度为k，具有n歌结点的二叉树，若将它与一颗同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号后，该二叉树中的每个节点分别与满二叉树中编号为1~n的结点位置一一对应，则称这可二叉树为完全二叉树；
遍历二叉树：
定义：按照某种规则访问二叉树中的每个结点一次且仅一次的过程；
遍历方式：[X]
1，按根，左子树，右子树3部分进行遍历；
可用的遍历顺序：TLR(根左右),TRL（根右左）,LTR（左根右）,RTL（右根左）,LRT（左右根）,RLT（右左根）;
` 主要使用的方式为先左后右的方式也即是：TLR（先序遍历），LTR（中序遍历），LRT（后序遍历） 2，按层次遍历二叉树：按照从上层到下层，从左到右的顺序依次访问每个结点；
树，森林与二叉树的转换：
树---->二叉树
1，加线：在兄弟结点间加一连线；2，抹线：对每个结点，除了其左孩子外，去除其余孩子之间的关系；3，旋转：以树的根结点未周星，将整个树顺时针旋转45度；
森林---->二叉树
1，将森林中的每棵树分别转换成二叉树；2，将每棵树的根结点用线相连；3，以第一棵树的根结点为二叉树的根，再以根结点为轴心，顺时针旋转45度；
二叉树----》树
1，加线：若p结点是双亲结点的左孩子，则将p的右孩子，有孩子的右孩子。。。。，沿分支找到的所有右孩子，都与p的双亲用线联结起来；2，抹线：抹掉原二叉树中双亲与右孩子之间的连线；3，调整：将结点按层次排列；
二叉树----》森林
七，查找
定义：在数据元素集合中查找满足某种条件的数据元素的过程；一般称用于查找的数据集合称为查找表
查找表的操作分类： 1，在查找表中查看墨迹个特定的数据元素是否在查找表中； 2，检索某个特定的元素的各种属性 3，在查找表中插入一个数据元素； 4，从查找表中删除某个数据元素；
查找表的操作类型分类： 静态查找： 1，顺序查找：将查找表作为一个线性表，从第一个数据元素开始，将给定值与表中元素逐一比较，若某个元素的关键字值与给定值相等，则查找成功，返回该元素的存储位置，如果到最后也没有查找到相等值，则查找失败； 2，折半查找：将一个预先排序好的数组进行对中平分，比较预定义值是否预期相等；
动态查找：
1,二叉 排序树：
特点：1，若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值；
2，若他的右子树不空，则右子树桑所有结点的值均大于它的根节点的值；
3，它的左右子树都是二叉排序树；··············
查找：如果二叉树为空，则查找失败。将根节点的关键字值与k比较，如果相等，则查找成功；如果根节点的关键字值小于给定值k，则在左子树中继续搜索。否则，在右子树中继续搜索；
插入：若二叉排序树为空,则新街点作为二叉排序树的根结点; 否则,若给定节点的关键字值小雨根结点关键字值,则插入在左子树上,若给定结点的关键字值大于根结点的值,则插入右子树上;
删除：
a,如果要删除的结点为叶子结点，则可以直接删除；
b,p只有左子树Pl或则右子树Pr。此时只要令Pl或Pr直接称为p的双亲节点f的左子树（或右子树）即可；
c,若要删除节点的左右子树均为非空，则首先要找到要删除节点的右子树中关键字值最小的结点，利用上面的方法将该结点重游自述中删除，并用它取代要删除节点的位置；这样处理的结果一定能够保证删除节点后二叉树的性质不变；
删除p之前，中序遍历二叉树得到的序列假设为｛...c1,c,q1,q,s1,s,p,pr,f...｝ ,删除p之后，为保持其他元素之间的想读欻处置不变，可以有两种方法：第一种是：令p的直接前驱（或直接后继）替代p，然后再从二叉排序树中删去它的直接前驱（或直接后继）；
另一种是：令p的左子树为f'的左子树，而p的右子树为s的右子树；
一个小坎：p163 二叉排序树的删除的应用；
哈希表： 哈希函数：将记录的关键字值与记录的存储位置对应起来的关系H，一般称为哈希函数； 哈希表：根据哈希函数建立的表格；如果两个变量进过哈希函数处理后，数值相同即指向了同一地址，则称为产生冲突；
哈希函数的构造：
1，计算哈希函数所需时间；
2，关键字长度；
3，哈希表长度；
4，关键字分布情况；
5，记录的查找频率；
常用的哈希函数的构造方法;
1.直接定址法：利用线性关系，直接存储： H(key) = key 或 H(key) = a*key + b （适合关键字的分布连续时试用）
2.除留余数法：用关键字key初一某个不大于哈希表长度m的数字： H(key)= key % p（p<=m）（p一般为小于m的最大质数或素数）；
3.平方取中法：取关键字平方后的中间极为为哈希地址。
4.折叠法：把关键字折叠成位数相同的几部分，然后取这几部分的叠加作为哈希地址；（移位叠加、间界叠加）
冲突处理的方法：冲突处理：一旦冲突发生，为发生冲突的元素寻找另一个空闲的哈希地址存放该元素；
1，开放地址法：如果发生冲突，则在冲突未知的前后附近寻找可以存放元素的空闲单元；
线性探测序列公式：Hi(k) = (H(k) + di ) % m ,i =1,2,3....... H(k):哈希函数；m表长度；di第i次探测的地址增量,di = i；
二次探测序列公式：Hi(k) = (H(k) + di ) % m ,i =1,2,3....... H(k):哈希函数；m表长度；di第i次探测的地址增量,di = i的平方；
线性探测序列公式：Hi(k) = (H(k) + di ) % m ,i =1,2,3....... H(k):哈希函数；m表长度；di第i次探测的地址增量,di = 伪随机数；
2，链地址法：将所有关键字是同义词的元素或记录链接成一个线性链表，而将其链头链接在有哈希函数确定的哈希地址所指示的存储单元中；
3，溢出法：将哈希表分为基本区和溢出区两个部分，把没有发生冲突的记录放在基本区，当发生冲突时，把具有相同哈希地址的记录存放在溢出区，并把具有相同哈希地址的记录采用一个线性链表联结起来；
哈希表查找和分析：
计算出给定关键字值k对应的哈希地址adr = H(k)--------->while((addr中不空) && (addr 中关键字值！=k))，按冲突处理方法求得下一地址addr-------->如果addr中为空，则查找失败，返回失败信息------------>否则查找成功，并返回地址addr；
八、排序
基本概念： 内部排序和外部排序：根据在排序时是否将所有的数据元素放入到内存中，将排序方法分为内部排序和外部排序两类； 外部排序在排序过程中需要频繁在内外存之间多次交换数据； 排序算法的稳定性：如果在待排序的记录序列中有多个相同关键字值的数据元素，经过排序后，这些数据元素的相对次序保持不变，则称这种排序算法是稳定的；反之，则是不稳定的； 排序算法的效率评价：效率主要考虑时间和空间两个角度； 对于排序算法，时间主要小号在关键字间的比较和数据元素的移动上，因此排序算法的比较次数越少和移动次数越少则时间效率越高； 对于排序算法，空间效率主要消耗在辅助存储空间（指存放待排序数据元素占用的存储空间之外，需要的其他空间），
插入排序：将待排序的数据元素逐个插入到有序序列中！ 直接插入排序：
希尔排序：