数据结构第五章数组和广义表.ppt

文档介绍：该【数据结构第五章数组和广义表 】是由【wyj199215】上传分享，文档一共【48】页，该文档可以免费在线阅读，需要了解更多关于【数据结构第五章数组和广义表 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第五章 数组和广义表
单击此处添加您的正文
目录
CONTENTS
第五章   数组和广义表
单击此处添加标题
01
02
本章讨论的两种数据结构：数组和广义表，其共同特点是：
数据元素本身也是一个数据结构；
都属于线性数据结构；
从逻辑结构上看它们，可看成是线性结构的一种扩展；
每种数据结构中的数据元素，都作为原子数据，不再进行分解；
前4章介绍的数据结构共同特点：
第五章     数组和广义表
数组的定义
数组的抽象数据类型定义
ADT Array
{ 数据对象：
D＝{aj1,j2,…,ji,…,jn|ji=0,…,bi-1,i=1,2,…,n ( n>0)
称为数组的维数,bi是数组第i维的长度，ji是数组元素的第i维下标}
数据关系：R＝{R1, R2,… ,Rn}
5．1 数组的定义
(2)  二维数组的解释
a00 a01 … a0 n-1
a10 a11 … a1 n-1
┋ ┋ ┋
am-1 0 am-1 1 … am-1 n-1
二维数组中的每个元素都受两个线性关系的约束，即行关系和列关系，在每个关系中，每个元素aij都有且仅有一个直接前趋，都有且仅有一个直接后继。
在行关系中
aij直接前趋是 aij-1 aij直接后继是 aij+1
在列关系中
aij直接前趋是 ai-1j aij直接后继是 ai+1j
A=(0 ,1 ,2 ,3 , 4 ,……,p ) p = m-1 或 n-1
其中每一个数据元素 j 是一个列向量的线性表
j=（a0j , a1j ,a2j , a3j ,…… ,am-1j ) 0≤j≤n-1
二维数组也可看作这样的线性表：其每一个数据元素也是一个线性表。
a00 a01 … a0 n-1
a10 a11 … a1 n-1
┋ ┋ ┋
am-1 0 am-1 1 … am-1 n-1
Amn=
a00
a10
┋
am-1 0
Amn=
或 i 是一个行向量的线性表
i=（ai0 ,ai1 ,ai2 , ai3 ,…… ,ain-1 ) 0≤i≤m-1
Amn=((a00 a01… a0 n-1 ),(a10 a11… a1 n-1),(am-1 0 am-1 1… am-1 n-1))
(3) C语言中二维数组类型的一种定义
typedef elemtype Array2[m][n];
等价于
typedef elemtype Array1[n];
typedef Array1 Array2[m];
同理，可以用 n-1 维数组的数据类型来定义 n 维数组。
5．2 数组的顺序存贮结构
数组的顺序表示和实现
类型特点
只有引用型操作，一般不作插入或删除操作；
数组是多维的结构，而存储空间是一个一维的结构。
两个策略----两种顺序映象的方式
以行序为主序(低下标优先)；
以列序为主序(高下标优先)。
a00 a01 … a0 n-1
a10 a11 … a1 n-1
┋ ┋ ┋
am-1 0 am-1 1 … am-1 n-1
Amn=
以行为主序的方式：
a00 a01 a0n-1 a10 a11 a1n-1 a(m-1)n-1 amn-1
0 1 n-1 n n+1 2n-1 mn-1
0 1 m-1 m m+1 2m-1 nm-1
a00 a10 am-10 a01 a11 am-11 a0n-1 a1n-1 amn-1
以列为主序的方式：