1-5.1-5.2--数组顺序表示.ppt

一、教学内容：1、 数组的定义和顺序存储方式；2、 特殊矩阵的压缩存储；3、 稀疏矩阵4、 广义表的概念、表示及基本操作；广义表存储结构的实现。二、教学要求：1、 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；2、 掌握对特殊矩阵进行压缩存储时的下标变换公式；3、 了解稀疏矩阵的两种压缩存储方法的特点和适用范围，理解以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法；4、 掌握广义表的结构特点及其存储表示方法，会对非空广义表进行分解。 知识结构图 知识结构图 第五章 数组和广义表 5.1数组的定义 5.2数组的顺序表示和实现 5.3矩阵的压缩存储 5.4广义表的定义 5.5广义表的存储结构 5.1 数组的定义 本章之前讨论的线性结构的数据元素都是非结构的原子类型，元素值不可再分。本章讨论的两种数据结构——数组和广义表。作为线性表的扩展，表中的数据元素本身也是一种数据结构。 抽象数据类型数组的定义 数组的顺序表示 n维数组的存储方式 n维数组的数据元素存储位置的计算公式 5.1 数组的定义 n维数组是线性表的推广 当n=1，n维数组退化成顺序表 当n1，n维数组可看成表中数据元素仍是线性表的线性表 5.1数组的定义 C语言中二维数组的类型定义:typedef ElemType Array2[m][n]; 等价于 typedef ElemType Array1[n]; typedef Array1 Array2[m]; 因此定义二维数组A可如右： Array2 A; 二维的数组 = 定长的线性表 数组的抽象数据类型 ADT Array { 数据对象：D = {aj1j2...jn | ji =0,...,bi -1, i=1,2,..,n n(0)称为数组的维数,bi是数组第i维的长度, ji是数组元素的第i维下标, aj1j2...jn?Elemset} 数据关系： R={R1 , R2 ... Rn} Ri = {＜ aj1...ji...jn, aj1...ji+1...jn ＞| 0 ? jk ? bk -1, 1 ? k ? n 且k ? i, 0 ? ji ? bi -2, i=2,...,n, aj1...ji...jn, aj1...ji+1...jn ?D}。 基本操作： InitArray(A,n,bound1,bound2,...,boundn); //构造数组A DestroyArray (A); // 销毁数组A Value(A,e,index1,index2,...,indexn); //取数组元素值 Assign(A,e, index1,index2,...,indexn) //给数组元素赋值 }ADT Array n维数组的特点 n维数组中含有?bi个数据元素; 每个数据元素都受着n个关系的约束； 在每个关系中，元素aj1j2…jn(0=ji=bi-2)都有一个直接后继; 数据元素都必须属于同一数据类型; n=1时，退化为定长的线性表； n维数组可以看成是线性表的推广。 数组一旦被定义，则维数已定，对于数组的操作只有存取元素和修改元素。(一旦建立了数组，数组中的元素个数和元素之间的关系就不再发生变动) 数组是多维的结构，而存储空间是一个一维的结构。（存储时需要一个次序约定） 5.2 数组的顺序表示和实现 类型特点: 1) 只有引用型操作，没有加工型操作； 2) 数组是多维的结构，而存储空间是 一个一维的结构。 二维数组的两种存储方式 5.2 数组的顺序表示 计算数组任一元素( 　 )的地址需要的三要素： ①数组的起始地址（即基地址） ②数组维数和各维的长度； ③数组中每个元素所占的存储单元 已知二维数组Ab1*b2，每个元素占L个存储单元， LOC(0,0)是数组第一个元素的起始地址，以行序为主存储，求LOC(i,j)。 5.2 数组的顺序表示和实现 n维数组元素存储地址的计算公式---教材93页 设各维长度分别为b1, b2, b3, …, bn,每个元素占L个存储单元， 起始地址是LOC(0,0,…,0) ，求元素 的存储位置？ 5.2 数组的顺序表示-小结 n维数组的特点: 数据元素同属于一种数据类型； 数组一旦被定义，则维数和各维长度不能改变； 数组操作只有引用型操作，没有加工型操作； 数组是多维结构，但存储空间是一维结构。 数组顺序表示的特点 存储单元地址连续（需要一段连续空间） 存储规则（以行（列）为主序）决定元素实际存储位置 随机存取 存储密度最大（100%） * 第五章 数组和广义表 数组与