山东理工大学：《数据结构》课程教学课件（数学）CH5 数组和广义表

第五章 数组和广义表

34

5.1数组的类型定义 5.2数组的顺序表示和实现 5.3稀疏矩阵的压缩存储 STOP 5.4广义表的类型定义 5.5广义表的表示方法

5.1 数组的类型定义 5.3 稀疏矩阵的压缩存储 5.2 数组的顺序表示和实现 5.4 广义表的类型定义 5.5 广义表的表示方法

5.1数组的类型定义 ADT Array 数据对象： D={aji2.jnji=0b-l,ie1,2.n n称为数组的维数，bi是数组第维的长度， j是数组元素的第维下标} 数据关系： R={R1,R2,Rn} Ri={Kaj,jw-i,ijt1,i,>|0≤jk≤bkl, 1≤k≤n且k≠i,0≤ji≤b:-2,i=2,n} 基本操作： ADT Array

5.1 数组的类型定义 ADT Array { 数据对象： D＝{ | ji =0,.,bi -1, i=1,2,.,n n称为数组的维数，bi是数组第i维的长度， ji是数组元素的第i维下标 } 数据关系： R＝{R1, R2, ., Rn} Ri＝{ | 0  jk  bk -1, 1  k  n 且k  i, 0  ji  bi -2, i=2,.,n } } ADT Array 基本操作: n j j j a 1 2

二维数组的定义： 数据对象： D={aii 0sisb-1,0sjsb2-1 数据关系： R=ROW,COL ROW ={0si<b-1,0sjsb2-2}

二维数组的定义: 数据对象: D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1} 数据关系: R = { ROW, COL } ROW = {| 0≤i≤b1-2, 0≤j≤b2-1} COL = {| 0≤i≤b1-1, 0≤ j≤b2-2}

基本操作： InitArray(&A,n,bound1,.boundn) DestroyArray(&A) Value(A,&e,index1,.indexn) Assign(&A,e,index1,.indexn)

基本操作： InitArray(&A, n, bound1, ., boundn) DestroyArray(&A) Value(A, &e, index1, ., indexn) Assign(&A, e, index1, ., indexn)

InitArray(&A,n,bound1,.boundn) 操作结果：若维数n和各维长度合法， 则构造相应的数组A,并 返回OK

InitArray(&A, n, bound1, ., boundn) 操作结果：若维数 n 和各维长度合法， 则构造相应的数组A，并 返回OK

Destroy Array(&A) 操作结果：销毁数组A

DestroyArray(&A) 操作结果：销毁数组A

Value(A,&e,index1,.indexn) 初始条件：A是n维数组，e为元素变量， 随后是n个下标值。 操作结果：若各下标不越界，则e赋值为 所指定的A的元素值，并返 回OK

Value(A, &e, index1, ., indexn) 初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。 操作结果：若各下标不越界，则e赋值为 所指定的A 的元素值，并返 回OK

Assign(&A,e,index1,.indexn) 初始条件：A是n维数组，e为元素变量， 随后是n个下标值。 操作结果：若下标不越界，则将e的值赋 给所指定的A的元素，并返回 OK

Assign(&A, e, index1, ., indexn) 初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。 操作结果：若下标不越界，则将e的值赋 给所指定的A的元素，并返回 OK

5.2数组的顺序表示和实现 类型特点： 数组是多维的结构，而存储空间是 一个一维的结构。 有两种顺序映象的方式： 1)以行序为主序（低下标优先）：PASCAL、C; 2)以列序为主序（高下标优先）：FORTRAN、VB;

5.2 数组的顺序表示和实现 类型特点: 数组是多维的结构，而存储空间是 一个一维的结构。 有两种顺序映象的方式: 1)以 为主序(低下标优先):PASCAL、C; 2)以 为主序(高下标优先):FORTRAN 、VB;