2022年数据结构知识点归纳文 .pdf

《2022年数据结构知识点归纳文 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构知识点归纳文 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构知识点归纳1. 数据结构的定义：数据在计算机中的组织。包括逻辑结构，存储结构，数据运算。逻辑结构：与具体的计算机无关。一、顺序表：线性表 (a1,a2 ,an) 有唯一的第一个和最后一个元素(n 0) 。其余的有唯一的前驱和后继。顺序表定义：用一组地址连续的存储单元依次存放的数据元素。在顺序表的第i 个位置前插入一个数据元素，需要向后移动n i +1个元素，删除第i 个位置的元素需要向前移动n i个元素。二、栈和队列1栈：允许在表的一端插入和删除的线性表。栈底，不允许操作，栈顶，允许操作。栈的操作原则：LIFO 后进先出【例】设进栈顺序是（a,b,c,d） ，不可能的出栈序列是：（ C

2、 ）A. (a,b,c,d) B.(a,c,b,d) C. (a,d,b,c) D. (d,c,b,a) 2队列：允许在表的一端插入，另一端删除的线性表队尾：插入端队首：删除端队列的操作原则：FIFO 先进先出三、数组： 1数组的定义： A.一维数组：具有相同特性的元素集合。A4 数组元素下标A0 A1 A2 A3 B.二维数组矩阵 A= a11 a12 a21 a22 a31 a32 C语言 A = a00 a01 a10 a11 a20 a21 矩阵下界为1。C语言中二维数组下界为0。如 A32 指 3行 2 列。C. 存储方式：行优先次序（行主）设一个数据元素占S个存储单元二维数组寻址公

3、式：amn LOC （aij）= LOC(a00)+(in+j) s ai j指存放相应元素的首地址【例】二维数组A43，首地址A00是 SA,每个元素占2 个存储单元，按行优先次序，求 A32与 A21存放地址。解： A32：SA+(33+2) 2 = SA+22 A21： SA+（ 23+1） 2=SA+14 2下三角矩阵压缩存储方法：（下三角是非0 元素，其余为0。 ）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - A =

4、 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

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树的定义和术语n0 个结点的有限集合。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - n0 有且只有一个根结点，其余结点分为m 0 个互不相交的有限集T1Tm 。每个集合Ti

6、又是一棵树。称为根的子树。双亲，子女，祖先，子孙。兄弟：同一个双亲的子女互为兄弟。结点的度：结点的子树数目。树的度：结点度的最大值叶结点：度为 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

7、的二叉树最多有2 k 1 个结点3满二叉树，高度为k 的二叉树具有2 k 1 个结点4完全二叉树层次编号 : 满二叉树按自顶向下，从左到右的次序进行编号。n 个结点的完全二叉树结点的排列顺序与满二叉树的层次编号次序一一对应（满二叉树是完全二叉树的子集）完全二叉树的特点：除最高层可以不满外，其余层都充满结点，每一层结点的个数是上一层结点个数的两倍。最高层上的结点集中在左部。完全二叉树中，如果一个结点没有左子女，就一定是叶结点高度为k 的完全二叉树最少有2 k-1个结点。层次编号为i 的结点：双亲：若 i =1为根，无双亲。否则双亲为 i/2 。i/2指不 i/2的最大整数。下取等。左子女：若2i

8、n 则无左子女，否则左子女是2i 。右子女：若2i+1n 则无右子女，否则右子女是2i+1 。5二叉树的遍历先序遍历：根，左，右中序遍历：左，根，右后序遍历：左，右，根层次遍历：访问根，再从左到右访问第i 层上的结点。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 先序序列： ABDFICEJGH 中序序列： DBFIAEJCHG 后序序列： DIFBJEHGCA 层次序列： ABCDFEGIJH 6树与二叉树的转换树转换成二叉

9、树：1. 加线：从左子女起，沿右子女之间加线。2. 抹线：抹除双亲至右子女之间的连线。3. 调整 : 旋转 454. 转换后根结点一定没有右子。因为无右邻兄弟。二叉树还原为树：1. 加线 : 从左子女起，沿右子女走，与双亲之间加线。2. 抹线：抹除左子女与右子女之间的连线。3. 调整 : 端平。森林与二叉树之间的转换与还原森林： n 棵树的集合。n0 1先将每棵树转成二叉树。2根结点之间连线3旋转 45森林： 若第一棵树m1个结点， 第二棵树m2个，第三棵树m3个结点。 则左子树为m11 个结点，右子树为m2 + m3 个结点。二叉树森林还原方法：根 +左子树还原成第一棵树根的右子树作为新的二

10、叉树重复二叉树的遍历与转换森林5查找二分法查找前提：顺序存储的有序表基本思想：待查值与中间元素比较：m= ( i + j ) /2 例10 ，15，22， 36，45，52， 63，96 1 2 3 4 5 6 7 8 i ：待查子表起始位置。 j ：待查子表结束位置。rm （m位置的元素）k = rm 查找成功k rm 继续在表的右半查找 i = m1 i为表头 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 当待查子表为空，

11、则查找失败。平均检索长度 = 总比较次数 / 元素个数（ ASL ）比较次数元素个数1 1 =2 0 2 2 =2 1 3 4 =2 2 4 1 = 总数 (2 n 11) =8 (2 3 1) ASL = (1 1+2 2+3 4+41)/ 8 = (1+4+12+4)/8 = 21/8 【例】将有序表存于A20 ，比较 4 次， 5 次查找成功的元素个数为 8 ， 5 。ASL= (1 1+22+34+48+55)/ 20 = (1+4+12+32+25)/20 = 3.7 6 散列法d = H ( key ) 散列散列键值地址函数冲突：用散列函数给不同值算出的地址相同。解决思路：先来先占

12、位。从散列地址开始顺次找空位。（直到有空位为止）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 ，请写出直接选择排序，直接插入排序，起泡排序和归并排序的第一趟排序结果：直接选择

13、：一趟结果（选最小值与第一个元素进行交换）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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -