第2章 数组数据结构课件.ppt

第2章 数组 1. 数组及其抽象数据类型 1)一维数组 2) 一维数组的抽象数据类型的类声明 3)二维数组（矩阵） 4)特殊矩阵 2.顺序表(sequential List) 1)顺序表定义和特点 2) 顺序表的类定义 3)顺序表的查找 插入 删除 4) 使用顺序表的例子(用抽象数据类型） 3.多项式抽象数据类型 1)如何表达多项式：系数，阶数 2)多项式相加 4. 稀疏矩阵 5.字符串（String） 1) 字符串（简称串）的定义以及一些术语 2)串的基本操作 3)串的类定义以及串操作的实现 4)字符串的模式匹配（pattern matching） 朴素的匹配算法 改进的模式匹配算法：KMP 第2章 数组 数组：具有相同数据类型的数据元素的集合。 一般存储于一个连续存储空间中。 通过数组元素的下标来存取该元素。 1. 数组及其抽象数据类型 1)一维数组：具有相同数据类型的n（n=0）个元素的有限序列。例如： 0 1 2 3 4 5 6 7 8 9 a： i 2 ) 一维数组的抽象数据类型的类声明 对数组的操作主要有：对数组元素的存与取。 3 ) 二维数组（矩阵） 由n个行向量和m个列向量所组成的向量 a00 a01 a02 …… a0,m-1 A[n][m] = a10 a11 a12 …… a 1,m-1 an-1,0an-1,1an-1,2……an-1,m-1 对二维数组的顺序存储： 1）按行优先顺序存放 a[0][0] , a[0][1] ,a[0][2], ……,a[0][m-1] ,a[1][0]…… 如ALGOL,PASCAL,C++,BASIC,Ada等都是按行优先顺序存放的。 2) 按列优先顺序存放 a[0][0] , a[1][0] , a[2][0] ,……a [n-1][0] ,a[0][1]…… 如Fortran语言 如果按行优先存放，其下标元素的映射公式为： Loc(i, j)=Loc(0,0)+[i*m+j]*L 如果按列优先存放，其下标元素的映射公式为： Loc (i,j) = Loc (0, 0)+[j*n+i]*L 同理对三维数组a[m1][m2][m3] 其下标元素a[i][j][k] Loc(i, j, k)=Loc(0,0,0)+i*m2*m3+j*m3+k 4)特殊矩阵 (1)下三角矩阵（对于对称矩阵的压缩存储） 上三角矩阵 a11 a12 a1n a11 a22 a2n 按行序存放 a12 a33 a1n a2