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

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

第四章 数组、串与广义表 1

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

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

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

一维数组的定义和初始化 #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

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

二维数组 三维数组 m1=5 m2=4m3=6 a[2][2] 2 m 2 3×4×6 2×6 ma mi m3 a[3][2][2] 行向量下标i 页向量下标i 列向量下标j 行向量下标j 列向量下标飞 5

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

数组的连续存储方式 一维数组 1oc0-{ix6H1=a40 i=0 123456789 3527 491860 5477 834102 ati*l 6

数组的连续存储方式 一维数组 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

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

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

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

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

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

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

二维数组中数组元素的顺序存放 a0][o] alo][I] a0][2]… ao]m-刂 a1[o] a a12] al1](m-1] a= a[2][0] a2][ a2]2] … a2][m-刂 ain-I][o]aln-I]l]aln-1][2]..aln-I][m-Iy ·行优先存放： 设数组开始存放位置L0C(0,0)=,每个 元素占用1个存储单元 ■ LOC(i,k)=a+(j*m+k)*1 10

二维数组中数组元素的顺序存放 a a a a a m a a a a m a a a a m a n a n a n a n m                [ ][ ] [ ][ ] [ ][ ] [ ][ ] ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] 0 0 0 1 0 2 0 1 1 0 1 1 1 2 1 1 2 0 2 1 2 2 2 1 1 0 1 1 1 2 1 1          [ n 行优先存放： 设数组开始存放位置 LOC(0, 0) = a, 每个 元素占用 l 个存储单元 n LOC ( j, k ) = a + ( j * m + k ) * l 10