数据结构知识点归纳.doc

没有不疼的伤口,只有流着血却微笑的人有时候给别人最简单的建议却是自己最难做到的。数据结构知识点归纳 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 01234567893 .稀疏矩阵的三元组表示: 非0 元素相对较少,且无规律。 A={3010002000000100000 1} 描述一个非零元素的( r行c列v 值)三元组稀疏矩阵的三元组表:按行优先次序进行转换 rcv545113131232421541 转置矩阵 A-= {30000000********** 1} RCV455113241311322451 四、树和二叉树 1 .树的定义和术语 n≥0 个结点的有限集合。 n>0 有且只有一个根结点,其余结点分为 m≥0 个互不相