苏州大学数据结构04.ppt

苏州大学数据结构04.ppt第四章数组、 串与广义表
数据结构电子教案
殷人昆王宏
1
第四章数组、串与广义表
一维数组与多维数组
特殊矩阵
稀疏矩阵
字符串
广义表
2
一维数组
定义
数组是相同类型的数据元素的集合,而一维数组的每个数组元素是一个序对,由下标(index)和值(value)组成。
一维数组的示例
在高级语言中的一维数组只能按元素的下标直接存取数组元素的值。
35 27 49 18 60 54 77 83 41 02
0 1 2 3 4 5 6 7 8 9
3
一维数组的定义和初始化
#include <>
main ( ) {
int a[3] = { 3, 5, 7 }, *elem, i; //静态数组
for (i = 0; i < 3; i++)
cout << a[i] << endl;
elem = new int[3]; //动态数组
for (i = 0; i < 3; i++)
cin >> elem[i];
while (elem)
{ cout << *elem << endl; elem++; }
}
4
多维数组
多维数组是一维数组的推广。
多维数组的特点是每一个数据元素可以有多个直接前驱和多个直接后继。
数组元素的下标一般具有固定的下界和上界,因此它比其他复杂的非线性结构简单。
例如二维数组的数组元素有两个直接前驱,两个直接后继,必须有两个下标(行、列)以标识该元素的位置。
5
二维数组三维数组
行向量下标 i 页向量下标 i
列向量下标 j 行向量下标 j
列向量下标 k
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
7
二维数组
一维数组常被称为向量(Vector)。
二维数组 A[m][n] 可看成是由 m 个行向量组成的向量,也可看成是由 n 个列向量组成的向量。
一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型:
typedef T array2[m][n]; //T为元素类型
等价于:
typedef T array1[n]; //列向量类型
typedef array1 array2[m]; //二维数组类型
8
同理,一个三维数组类型可以定义为其数据元素为二维数组类型的一维数组类型。
静态定义的数组,其维数和维界不再改变,在编译时静态分配存储空间。一旦数组空间用完则不能扩充。
动态定义的数组,其维界不在说明语句中显式定义,而是在程序运行中创建数组对象时通过 new 动态分配和初始化,在对象销毁时通过 delete 动态释放。
用一维内存来表示多维数组,就必须按某种次序将数组元素排列到一个序列中。
9
二维数组的动态定义和初始化
#include <>
…………
int **A;
int row = 3, col = 3; int i, j;
A = new int *[row];
for (i = 0; i < row; i++)
A[i] = new int [col];
for (i = 0; i < row; i++)
for (j = 0; j < col; j++) cin >> A[i][j];
…………
10