第五章数组和广义表ppt课件.ppt

《第五章数组和广义表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章数组和广义表第五章  数组和广义表第五章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义前4章介绍的数据结构共同特点：（1）都属于线性数据结构；（2）每种数据结构中的数据元素，都作为原子数据，不再进行分解；本章讨论的两种数据结构：数组和广义表，其共同特点是：1）从逻辑结构上看它们，可看成是线性结构的一种扩展；2）数据元素本身也是一个数据结构；本章讨论三个方面的内容：数组、矩阵的压缩存储、广义表第五章   数组和广义表5．1数组的定义5.1数组的定义一数组的概念二数组的顺序表示和实现数组的概念数组是我们十分熟悉的一种数据类型，几乎所有

2、的程序设计语言都包含数组。本书在讨论各种数据结构的顺序存储分配时，也都是借用一维数组来描述它们的存储结构。这一章将从数据结构的角度，简单讨论数组的逻辑结构及其存储方式，另外书上还给出了数组的基本操作算法，如：数组的初始化，读取指定下标的数组元素算法，给指定下标的数组元素赋值等操作算法；注：数组的基本操作算法，不是本课程要求掌握的内容。数组是由一组个数固定，类型相同的数据元素组成阵列。数组中的每个元素都受n个线性关系的约束，即在每个关系中，每个元素aij都有且仅有一个直接前趋，都有且仅有一个直接后继。在行关系中aij直接前趋是aij-1aij直接后继是aij+1在列关系中aij直接前趋是ai

3、-1jaij直接后继是ai+1j以二维数组为例：二维数组中的每个元素都受两个线性关系的约束Amn=a00a01a0n-1a10a11a1n-1am-10am-11am-1n-1数组的基本操作初始化操作InitArray(&A,n,bound1,…,boundn)功能：参数合法，构造数组A，并返回OK；销毁操作DestroyArray(&A)功能：销毁数组A；3读元素操作Value(A,&e,index1,…,indexn)功能：若指定下标不越界,读指定下标的元素,用e返回,并返回OK；写元素操作Assign(A,e,index1,…,indexn)功能：若指定下标不越界,将e赋值给A指定

4、的下标元素,并返回OK；5．2数组的顺序表示和实现数组的顺序存贮结构一般来说，数组一旦定义，其元素的个数和元素之间的相互关系不再发生变化，即对数组一般不进行插入和删除操作。因此，数组采用顺序存储结构是十分自然的事情。计算机的内存空间是一个一维结构，而二维以上的数组是多维结构。因此，用一组连续的存储单元存放数组元素，就有次序约定的问题。以二维数组为例，它有两种方式：一种是以行为主序的方式，另一种是以列序为主序的方式。行为主序方式是先存储数组的第一行元素，再存储第二行元素…；而列序为主序方式是先存储数组的第一列元素，再存储第二列元素…；在众多的程序设计语言中，以行序为主序方式的有PASCAL、

5、COBOL、C及扩展BASIC等，以列序为主序方式的有FORTRAN语言。设A是一个具有m行n列的元素的二维数组如下：Amn=以行为主序的方式：a00a01a0n-1a10a11a1n-1am-10am-11am-1n-101n-1nn+12n-1mn-1a00a01a0n-1a10a11a1n-1am-10am-11am-1n-1以列为主序的方式：a00a10am-10a01a11am-11a0n-1a1n-1am-1n-101m-1mm+12m-1nm-1数组元素存储地址的计算无论采用哪种存储方式，一旦确定了存储映象的首地址。数组中任意元素的存储地址都可以确定。假设二维数组A每个元素

6、占用k个存储单元，Loc(aij)为元素aij的存储地址，Loc(a00)是a00存储位置,也是二维数组A的基址。若以行序为主序的方式存储二维数组，则元素aij的存储位置可由下式确定：Loc(aij)=Loc(a00)+（ni+j)k若以列序为主序的方式存储二维数组，则元素aij的存储位置可由下式确定：Loc(aij)=Loc(a00)+（mj+i)k一般在程序设计过程中，一维数组和二维数组使用较普遍，超过二维以上的多维数组使用相对较少，对于高维数组的顺序存储方法，读者可以将二维的情形加以推广便能够得到，这里不再赘述。小结数组中的每个元素都受n个线性关系的约束，在每个线性关系中，每

7、个元素aij都有且仅有一个直接前趋，都有且仅有一个直接后继。二维数组有两种方式：一种是以行为主序的方式，另一种是以列序为主序的方式。5．3矩阵的压缩存储5.3矩阵的压缩存储一特殊矩阵的压缩存储二稀疏矩阵的压缩存储基本内容1特殊矩阵的压缩存储；2稀疏矩阵的压缩存储；3稀疏矩阵在三元组顺序表存储方式下，矩阵的运算的实现；学习要点1了解矩阵的两种压缩存储方法及适用范围；2了解在三元组顺序表存储方式下，实现矩阵运算的方法；