数据结构知识点归纳.txt没有不疼的伤口，只有流着血却微笑的人有时候 给别人最简单的建议 却是自己最难做到的。        数据结构知识点归纳
1.数据结构的定义：
数据在计算机中的组织。包括逻辑结构，存储结构，数据运算。
逻辑结构：与具体的计算机无关。
一、顺序表：
线性表(a1,a2…,an)有唯一的第一个和最后一个元素(n≥0)。其余的有唯一的前驱和后继。
顺序表定义：用一组地址连续的存储单元依次存放的数据元素。
在顺序表的第i个位置前插入一个数据元素，需要向后移动n － i +1个元素，删除第i个位置的元素需要向前移动n－ i个元素。
二、栈和队列
1．栈：允许在表的一端插入和删除的线性表。栈底，不允许操作，栈顶，允许操作。
栈的操作原则：LIFO后进先出
【例】设进栈顺序是（a,b,c,d），不可能的出栈序列是：（ C ）
A. (a,b,c,d)  B.(a,c,b,d)  C. (a,d,b,c)  D. (d,c,b,a)
2．队列：允许在表的一端插入，另一端删除的线性表
队尾：插入端  队首：删除端
队列的操作原则：FIFO先进先出
三、数组：
1．数组的定义：
A.一维数组：具有相同特性的元素集合。A[4] 数组元素下标A[0] A[1] A[2] A[3] 
B.二维数组 矩阵 A= {a11 a12
a21 a22
a31 a32}   
C语言  A = {a[0][0]  a[0][1]
a[1][0]  a[1][1]
a[2][0]  a[2][1]}
矩阵下界为1。C语言中二维数组下界为0。如A[3][2] 指3行2列。
C. 存储方式：行优先次序（行主）
设一个数据元素占S个存储单元
二维数组寻址公式：a[m][n]
LOC（a[i][j]）= LOC(a[0][0])+(i×n+j)×s         
a[i][ j]指存放相应元素的首地址
【例】二维数组A[4][3]，首地址A[0][0]是SA，每个元素占2个存储单元，按行优先次序，求A[3][2]与A[2][1]存放地址。
解： A[3][2]：SA+(3×3+2)×2 = SA+22    A[2][1]： SA+（2×3+1）×2=SA+14
2．下三角矩阵压缩存储方法：（下三角是非0元素，其余为0。）
A = { a11            0
a21 a22        0
a31 a32 a33    0
a41 a42 a43 a44  0}
n阶下三角矩阵元素个数：(n+1)n/2
n阶下三角矩阵压缩存储于一维数组F(m) ，则 m=(n+1)n/2
F数组
A11 A21 A22 A31 A32 A33 A41 A42 A43 A44
0 1 2 3 4 5 6 7 8 9
3．稀疏矩阵的三元组表示： 非0元素相对较少，且无规律。
A = { 3 0 1 0
0 0 2 0
0 0 0 0
0 1 0 0
0 0 0 1}
描述一个非零元素的（r行c列v值）三元组
稀疏矩阵的三元组表：按行优先次序进行转换
r c v
5 4 5
1 1 3
1 3 1
2 3 2
4 2 1
5 4 1
转置矩阵
A-= {3 0 0 0 0
0 0 0 1 0
1 2 0 0 0
0 0 0 0 1}
R C V
4 5 5
1 1 3
2 4 1
3 1 1
3 2 2
4 5 1
四、树和二叉树
1．树的定义和术语
n≥0个结点的有限集
合。
n>0 有且只有一个根结点，其余结点分为m≥0个互不相交的有限集T1～Tm 。
每个集合Ti又是一棵树。称为根的子树。
双亲，子女，祖先，子孙。
兄弟：同一个双亲的子女互为兄弟。
结点的度： 结点的子树数目。
树的度：结点度的最大值
叶结点： 度为0的节点
分支结点：度不为0的节点
结点的层次：根结点在第一层。其它结点层次=双亲层次+1
树高度（深度）：树的叶子的最大层次
例： 设在树中结点X是结点y的双亲时，用（x,y）表示树中的边。边的集合是{（a,b）,(a,c), (a,d)  , (b,e) ,(b,f) ,(c,g)  ,(d,h),  (d,i)  ,(d,j) }，用树形表示法画出此树。
2．二叉树
性质：
1．二叉树中i层(i>=1)上最多有2 i—1个结点
2．高度为k的二叉树最多有2 k –1个结点
3．满二叉树，高度为k的二叉树具有2 k–1个结点
4．完全二叉树
层次编号: 满二叉树按自顶向下，从左到右的次序进行编号。
n个结点的完全二叉树结点的排列顺序与满二叉树的层次编号次序一一对应（满二叉树是完全二叉树的子集）
完全二叉树的特点：
①除最高层可以不满外，其余层都充满结点，每一层结点的个数是上一层结点个数的两倍。最高层上的结点集中在左部。
②完全二叉树中，如果一个结点没有左子女，就一定是叶结点
③高度为k的完全二叉树最少有2 k-1个结点。
④层次编号为i 的结点：
双亲：若 i =1为根，无双亲。否则双亲为 [i/2] 。
[i/2]指不≥i/2的最大整数。下取等。
左子女：若2i>n则无左子女，否则左子女是2i。 
右子女：若2i+1>n则无右子女，否则右子女是2i+1。 
5．二叉树的遍历
先序遍历：根，左，右
中序遍历：左，根，右
后序遍历：左，右，根
层次遍历：访问根，再从左到右访问第i层上的结点。
先序序列：ABDFICEJGH
中序序列：DBFIAEJCHG
后序序列：DIFBJEHGCA
层次序列：ABCDFEGIJH
6．树与二叉树的转换
树转换成二叉树：
1.加线：从左子女起，沿右子女之间加线。
2.抹线：抹除双亲至右子女之间的连线。
3.调整: 旋转45°
4.转换后根结点一定没有右子。因为无右邻兄弟。
二叉树还原为树：
1.加线：从左子女起，沿右子女走，与双亲之间加线。
2.抹线：抹除左子女与右子女之间的连线。
3.调整: 端平。
森林与二叉树之间的转换与还原
森林：n棵树的集合。n≥0
1．先将每棵树转成二叉树。
2．根结点之间连线
3．旋转45°
森林：若第一棵树m1个结点，第二棵树m2个，第三棵树m3个结点。则左子树为m1－1个结点，右子树为m2 + m3 个结点。
二叉树  →  森林
还原方法：
①根+左子树还原成第一棵树
②根的右子树作为新的二叉树
③重复①②
二叉树的遍历与转换森林
5．查
二分法查
前提：顺序存储的有序表
基本思想：待查值与中间元素比较：m= ( i + j ) /2
例{10，15，22，36，45，52，63，96}
1  2  3  4  5  6  7  8
i ：待查子表起始位置。  j ：待查子表结束位置。
r[m]（m位置的元素）
k = r[m]  查成功
k < r[m]  继续在表的前半查，j = m－1  [j为表尾]
k>r[m]继续在表的右半查  i = m＋1  [i为表头]
当待查子表为空，则查失败。
平均检索长度 = 总比较次数/元素个数
（ ASL ）
比较次数  元素个数
1 1  =2 0     
2 2  =2 1     
3 4  =2 2     
4 1  = 总数－(2 n－1－1) =8－(2 3－1)
ASL = (1×1+2×2+3×4+4×1)/ 8 = (1+4+12+4)/8 = 21/8
【例】将有序表存于A[20]，比较4次，5次查成功的元素个数为  8  ， 5 。
ASL= (1×1+2×2+3×4+4×8+5×5)/ 20 = (1+4+12+32+25)/20 = 3.7
6． 散列法
d  = H  (  key )
散列  散列  键值
地址  函数
冲突：用散列函数给不同值算出的地址相同。
解决思路：先来先占位。从散列地址开始顺次空位。（直到有空位为止）
d i = ( h (key) +i ) % m    i = 1,2,3,………m  ( m为表长)
【例】散列函数h(key)=key%7，散列地址空间为0到9，用线性探查法处理冲突。
给定链值序列为{6，21，41，40，18，9，16，27}，画出散列表。
解：{6，21，41，40，18，9，16，27}
d=6，0， 6， 5， 4 ，2，2， 6
7．排序：将序列按从小到大的次序排列一次。
给定的整数序列{40，32，58，34，20，90，98，18}，请写出直接选择排序，直接插入排序，起泡排序和归并排序的第一趟排序结果：
c语言二维数组转置直接选择：一趟结果（选最小值与第一个元素进行交换）
{18，32，58，34，20，90，98，18}
直接插入一趟结果：（将前两个元素进行排序）
{[32，40]，58，34，20，90，98，18}
起泡排序：（顺次两两键值进行比较，逆序则交换）
{32，40，34，20，58，90，18，98}
归并排序：（两两相邻的元素进行排序）
{[32，40]，[34，58]，[20，90]，[18，98]}