《数据结构 Data Structure》课程教学资源（PPT课件讲稿）第四章 数组、串与广义表

第四章数组、串与广义表 一维数组与多维教组 特殊矩阵 稀疏矩阵 字符串 广义表

第四章 数组、串与广义表 • 一维数组与多维数组 • 特殊矩阵 • 稀疏矩阵 • 字符串 • 广义表 1

一维教组 定义 数组是相同类型的数据元素的集合,而一维 数组的每个数组元素是一个序对,由下标 ( index)和值(vale)组成。 维数组的示例 0123456789 35274918605477834102 在高级语言中的一维数组只能按元素的下标 直接存取数组元素的值

一维数组 • 定义 数组是相同类型的数据元素的集合，而一维 数组的每个数组元素是一个序对，由下标 （index）和值（value）组成。 • 一维数组的示例 • 在高级语言中的一维数组只能按元素的下标 直接存取数组元素的值。 35 27 49 18 60 54 77 83 41 02 0 1 2 3 4 5 6 7 8 9 2

维数组的定义和初始化 #include elem 1; int te p≡eem; for(1=0;1<3;i++) f cout <<*temp<< endl; temp++;) delete l elem

一维数组的定义和初始化 #include void main ( ) { int a[3] = { 3, 5, 7 }, *elem, i; //静态数组 for (i = 0; i > elem[i]; int * temp = elem; for (i = 0; i < 3; i++) { cout << *temp<< endl; temp++; } delete [] elem; } 3

多维教组 多维数组是一维数组的推广。 多维数组的特点是每一个数据元素可以有多 个直接前驱和多个直接后继。 数组元素的下标一般具有固定的下界和上界, 因此它比其他复杂的非线性结构简单。 例如二维数组的数组元素有两个直接前驱 两个直接后继,必须有两个下标(行、列 以标识该元素的位置

多维数组 • 多维数组是一维数组的推广。 • 多维数组的特点是每一个数据元素可以有多 个直接前驱和多个直接后继。 • 数组元素的下标一般具有固定的下界和上界， 因此它比其他复杂的非线性结构简单。 • 例如二维数组的数组元素有两个直接前驱， 两个直接后继，必须有两个下标（行、列） 以标识该元素的位置。 4

二维数组 三维数组 1=5m2=4m 3 a[2][2] m2 3×4×6 2×6 m2 n1 a[3][2]2] 行向量下标i 页向量下标i 列向量下标j 行向量下标j 列向量下标k

二维数组 三维数组 行向量 下标 i 页向量 下标 i 列向量 下标 j 行向量 下标 j 列向量 下标 k 5

数组組的连续存储方式 一维数组 i=0 LOC(e LOC(-1)+l=a+i>0 0123456789 35274918605477834102 +i“l

数组的连续存储方式 一维数组 LOC(i) = LOC(i-1)+l = a+i*l, i > 0 a, i = 0 35 27 49 18 60 54 77 83 41 02 0 1 2 3 4 5 6 7 8 9 l l l l l l l l l l a+i*l a 6

二维数组 一维数组常被称为向量(Ⅴ ector)。 二维数组Am]l可看成是由m个行向量 组成的向量,也可看成是由n个列向量组成 的向量。 个二维数组类型可以定义为其分量类型为 维数组类型的一维数组类型: typedef t array2m]n];团为元素类型 等价于 typedef t arrayln]; /列向量类型 typedef array l array2[m;/二三维数组类型

二维数组 • 一维数组常被称为向量（Vector）。 • 二维数组 A[m][n] 可看成是由 m 个行向量 组成的向量，也可看成是由 n 个列向量组成 的向量。 • 一个二维数组类型可以定义为其分量类型为 一维数组类型的一维数组类型: typedef T array2[m][n]; //T为元素类型 等价于： typedef T array1[n]; //列向量类型 typedef array1 array2[m]; //二维数组类型 7

同理,一个三维数组类型可以定义为其数据 元素为二维数组类型的一维数组类型。 静态定义的数组,其维数和维界不再改变, 在编译时静态分配存储空间。一旦数组空间 用完则不能打充。 动态定义的数组,其维界不在说明语句中显 式定义,而是在程序运行中创建数组对象时 通过new动态分配和初始化,在对象销毁时 通过 delete动态释放。 用一维内存来表示多维数组,就必须按某种 次序将数组元素排列到一个序列中

• 同理，一个三维数组类型可以定义为其数据 元素为二维数组类型的一维数组类型。 • 静态定义的数组，其维数和维界不再改变， 在编译时静态分配存储空间。一旦数组空间 用完则不能扩充。 • 动态定义的数组，其维界不在说明语句中显 式定义，而是在程序运行中创建数组对象时 通过 new 动态分配和初始化，在对象销毁时 通过 delete 动态释放。 • 用一维内存来表示多维数组，就必须按某种 次序将数组元素排列到一个序列中。 8

三维数组的动态定义和初始化 #include int *: int row= 3, col =3; int i,j; a-new int *rowI; for(1=0;1>AlLl; 9

二维数组的动态定义和初始化 #include ………… int **A; int row = 3, col = 3; int i, j; A = new int *[row]; for (i = 0; i > A[i][j]; ………… 9

二维数组中数组元素的顺序存放 无法显示该图片 n行优先存放: 设数组开始存放位置LOC(0,0)=a,每个 元素占用l个存储单元 LOC (,k)=a+(*m+k)*l 10

二维数组中数组元素的顺序存放 ◼ 行优先存放： 设数组开始存放位置 LOC(0, 0) = a, 每个 元素占用 l 个存储单元 ◼ LOC ( j, k ) = a + ( j * m + k ) * l 10