南京航空航天大学：《数据结构》课程教学资源（PPT课件讲稿）第五章 数组和广义表

教育部—微软精品课程建设项目 第五章数组和广义表 南京航空航天大学数据结构课题组版权所有

第五章 数组和广义表

教育部—微软精品课程建设项目 51数组的类型定义 52数组的顺序表示和实现 5.3稀疏矩阵的压缩存储 54广义表的类型定义 55广义表的表示方法 56广义表操作的递归函数 京航空航天大学数据结构课匙有

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

教育部—微软精品课程建设项目 5.1数组的类型定义 ADTArray i 数据对象 D=(一1=0…,b1-1,=1,2,n} 数据关系 R={R1,R2,…,Rn} Ri=ajv,j n,j,ji+1,jn >0≤j≤bk 1≤k≤n且k≠,0≤j≤b;-2,i=2,,n} 基本操作: 3 ADT Array 南京航空航天大学数据结构课题组版权所有

5.1 数组的类型定义 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 基本操作:

教育部—微软精品课程建设项目 二维数组的定义 数据对象 D={a1|0≤sb-10≤≤b2-1 数据关系 R=ROW, COL ROW={10≤b11,0≤jb2 南京航空航天大学数据结构课题组版权所有

二维数组的定义: 数据对象: 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, ., bound) Destroy Array (&a) Value(A, &e, index1, ., inden) Assign(&a, e, index1, ., index) 南京航空航天大学数据结构课题组版权所有

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

教育部—微软精品课程建设项目 InitArray( &A, n, boundI, . bound 操作结果:若维数n和各维长度合法 则构造相应的数组A,并 返回OK。 南京航空航天大学数据结构课题组版权所有

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

教育部—微软精品课程建设项目 Destroy Array(&a) 操作结果:销毁数组A。 南京航空航天大学数据结构课题组版权所有

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

教育部—微软精品课程建设项目 Value(A, &e, indexI, .. index) 初始条件:A是n维数组,e为元素变量, 随后是n个下标值。 操作结果:若各下标不超界,则e赋值为 所指定的A的元素值,并返 回OK。 南京航空航天大学数据结构课题组版权所有

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

教育部—微软精品课程建设项目 Assign( &A, e, indexI, ., index) 初始条件:A是n维数组,e为元素变量, 随后是n个下标值。 操作结果:若下标不超界,则将e的值赋 给所指定的A的元素,并返回 OK。 南京航空航天大学数据结构课题组版权所有

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

教育部—微软精品课程建设项目 52数组的顺序表示和实现 类型特点: 1)只有引用型操作,没有加工型操作; 2)数组是多维的结构,而存储空间是 一个一维的结构。 有两种顺序映象的方式 l)以行序为主序(低下标优先); 2)以列序为主序高下标优先) 南京航空航天大学数据结构课题组版权所有

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