数据结构知识点归纳70661

《数据结构知识点归纳70661》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构知识点归纳70661数据结构知识点归纳.txt没有不疼的伤口，只有流着血却微笑的人有时候给别人最简单的建议却是自己最难做到的。数据结构知识点归纳1.数据结构的定义：数据在计算机中的组织。包括逻辑结构，存储结构，数据运算。逻辑结构：与具体的计算机无关。一、顺序表：线性表(a1,a2…,an)有唯一的第一个和最后一个元素(n≥0)。其余的有唯一的前驱和后继。顺序表定义：用一组地址连续的存储单元依次存放的数据元素。在顺序表的第i个位置前插入一个数据元素，需要向后移动n－i+1个元素，删除第i个位置的元素需要向前移动n－i个元素。二、栈和队列1．栈：允许在表的一端插入和删除的

2、线性表。栈底，不允许操作，栈顶，允许操作。栈的操作原则：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={a11a12a21a22a31a32}C语言A={a[0][0]a[0][1]a[1][0]a[1][1]a[2][

3、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)×sa[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+22A[2][1]：SA+（2×3+1）×2=SA+142．下三角矩阵压缩存储方法：（下三角是非0元素，其

4、余为0。）A={a110a21a220a31a32a330a41a42a43a440}n阶下三角矩阵元素个数：(n+1)n/2n阶下三角矩阵压缩存储于一维数组F(m)，则m=(n+1)n/2F数组A11A21A22A31A32A33A41A42A43A4401234567893．稀疏矩阵的三元组表示：非0元素相对较少，且无规律。A={30100020000001000001}描述一个非零元素的（r行c列v值）三元组稀疏矩阵的三元组表：按行优先次序进行转换rcv545113131232421541转置矩阵A-={30000000101200000001}RCV455113241

5、311322451四、树和二叉树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),(

6、d,i),(d,j)},用树形表示法画出此树。2．二叉树性质：1．二叉树中i层(i>=1)上最多有2i—1个结点2．高度为k的二叉树最多有2k–1个结点3．满二叉树，高度为k的二叉树具有2k–1个结点4．完全二叉树层次编号:满二叉树按自顶向下，从左到右的次序进行编号。n个结点的完全二叉树结点的排列顺序与满二叉树的层次编号次序一一对应（满二叉树是完全二叉树的子集）完全二叉树的特点：①除最高层可以不满外，其余层都充满结点，每一层结点的个数是上一层结点个数的两倍。最高层上的结点集中在左部。②完全二叉树中，如果一个结点没有左子女，就一定是叶结点③高度为k的完全二叉树最少有2k-1个结

7、点。④层次编号为i的结点：双亲：若i=1为根，无双亲。否则双亲为[i/2]。[i/2]指不≥i/2的最大整数。下取等。左子女：若2i>n则无左子女，否则左子女是2i。右子女：若2i+1>n则无右子女，否则右子女是2i+1。5．二叉树的遍历先序遍历：根，左，右中序遍历：左，根，右后序遍历：左，右，根层次遍历：访问根，再从左到右访问第i层上的结点。先序序列：ABDFICEJGH中序序列：DBFIAEJCHG后序序列：DIFBJEHGCA层次序列：ABCDFEGIJH6．树与二叉树的转换树转换成二叉树：1.加