塔里木大学：《数据结构》课程教学课件（PPT讲稿）五章 数组和广义表

第五章数组和广义表5.1数组的类型定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的类型定义5.5广义表的存储结构

第五章 数组和广义表 5.1 数组的类型定义 5.3 矩阵的压缩存储 5.2 数组的顺序表示和实现 5.4 广义表的类型定义 5.5 广义表的存储结构

学习提要：1.了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。2.掌握对特殊矩阵进行压缩存储时的下标变换公式3.了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法4.掌握广义表的结构特点及其存储表示方法。M

学习提要： 1.了解数组的两种存储表示方法，并掌握 数组在以行为主的存储结构中的地址计算方 法。 2.掌握对特殊矩阵进行压缩存储时的下标 变换公式。 3.了解稀疏矩阵的两种压缩存储方法的特 点和适用范围，领会以三元组表示稀疏矩阵 时进行矩阵运算采用的处理方法。 4.掌握广义表的结构特点及其存储表示方 法

S5.1数组的类型定义ADT Array 数据对象：D = (ajujl i =-,..,b. - , i1,...n .数据关系：VR= {R1,R2, ..., Rn)Ri=(I 0≤jk≤bk-1,1≤k≤n 且k±i, 0≤ji≤b;-2, i=2,...,n}基本操作：ADT Array口

ADT Array { 数据对象： D＝{aj 1,j 2, .,ji,j n| ji =0,.,bi -1, i=1,2,.,n } 数据关系： R＝{R1, R2, ., Rn} Ri＝{ | 0  jk  bk -1, 1  k  n 且k  i, 0  j i  bi -2, i=2,.,n } } ADT Array 基本操作: §5.1 数组的类型定义

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

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

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

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

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

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

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

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

二维数组的定义：数据对象：D = (aij I 0 [ 0 [ 0<i<br-1, 0≤jb2-2]U

二维数组的定义: 数据对象: 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}

2二维数组的定义：doodon-1dolavoalnA二mxnaam-10m-11m-1n-1U

二维数组的定义:                 = − − − − − −  1 0 1 1 1 1 1 0 1 1 1 1 0 0 0 1 0 1 . . . . . . . . . . . m m m n n n m n a a a a a a a a a A

S5.2数组的顺序表示和实现★类型特点：(1)只有引用型操作，没有加工型操作；（2）数组是多维的结构，而存储空间是一个一维的结构★有两种顺序映象的方式(1)以行序为主序(2)以列序为主序

§ 5.2 数组的顺序表示和实现 类型特点: （1） 只有引用型操作，没有加工型操作； （2） 数组是多维的结构，而存储空间是 一个一维的结构。 有两种顺序映象的方式: （1）以行序为主序 （2）以列序为主序