文档介绍：《数据结构》
第五章数组和广义表
内容和要求
●内容和要求
数组和广义表的概念、存储结构和矩阵的压缩存储方法。要求对数组和广义表有较深刻的了解。掌握数组和广义表的概念,熟悉它们的存储结构及基本应用。
●重点
数组和广义表的存储特性,稀疏矩阵存储。
2
二维数组的逻辑结构
数组和广义表可以看成是线性表在下述含义上的扩展:即线性表中的数据元素本身也是一个数据结构。
类似于线性表,一个二维数组的逻辑结构可形式地表示为
2-Array=(D,R) (5-1)
其中
D={aij|i=c1, c1+1,···, d1,j= c2, c2+1,···, d2,aij∈D0}
R={Row,Col} //行关系,列关系
Row={<aij,ai,j+1>| c1≤i≤d1, c2≤j≤d2-1, aij, ai, j+1 ∈D}
Col={<aij,ai+1,j>| c1≤i≤d1-1, c2≤j≤d2, aij, ai+1, j ∈D}
D0为某个数据对象, c1, c2 , d1 , d2均为整数。
数组的逻辑结构
3
若c1=1, d1=m, c2=1, d2=n, 则有
D={aij|i=1,2,···,m, j= 1,2 ,···,n,∈D0}
R={Row,Col}
Row={<aij, ai, j+1>| i=1,2,···,m, j=1,2,···,n-1, aij, ai, j+1∈D}
Col={<aij, ai+1, j>| i=1,2,···,m-1, j=1,2,···,n, aij, ai+1, j ∈D}
记作Am×n,即A为m行n列的二维数组(起始下标为1)。
说明:
1) 用于二维数组的抽象可称之为矩阵,它是对向量的推广,其元素个数为m×n个。
数组的逻辑结构
4
2) 二维数组也可以看作是这样一个线性表:它的每一个数据元素是一个线性表。从而对二维数组可以进行递归定义,即它是数据元素为一维数组的线性表。可把Am×n看成是由m个行向量所组成的向量(线性表),也可以看成是n个列向量所组成的向量。
Am×n=(α1, α 2, ··· , α p) (p=m或n)
若α i为行向量:α i = (ai1, ai2,···, ain) 1≤i≤m
若α j为列向量:α j = (a1j, a2j,···, amj) 1≤j≤n
数组的逻辑结构
3) 二维数组中的每个元素都属于两个向量:第i行的行向量和第j列的列向量(对元素aij而言)。
4) 每个元素aij有两个前趋结点ai-1, j和ai, j-1(2≤i≤m, 2≤j≤n),两个后继结点ai+1, j和ai, j+1(1≤i≤m-1, 1≤j≤n-1),其中a11无前趋,amn无后继。边界上的结点a1j(j=2,···,n),amj(j=1,···,n-1)和ain(i=1,···,m-1)都只有一个后继结点或者只有一个前趋结点。
5
n(n>2)维数组的逻辑结构
n维数组的逻辑结构的形式定义
说明:
1)n维数组的元素个数为n1·n2· ··· ·nn= ni.
2)n维数组中每个数据元素都属于n个向量(受n个关系制约),除边界上的元素外,均可以有n个前趋和n个后继。
数组的逻辑结构
6
N维数组的递归定义
在这递归定义中,一个k维数组是其数据元素为k--k+1和dn-k+1是第k维下标的一对界偶。
n维数组是一种较复杂的数据结构,但它可以由简单的数据结构——线性表辗转合成而得。
数组的逻辑结构
7
数组的操作
一个数组中所有的数据元素都必须属于同一数据类型。
对于数组,通常只有两种基本操作:
1)给定一组下标,存取相应的数据元素。
2)给定一组下标,修改相应数据元素中的某一个或几个数据项的值。
注. 对于二维数组的抽象即矩阵,可包含取值、赋值和初始化等操作。编译程序用线性存储器来实现矩阵。
数组的逻辑结构
8
数组的顺序存储结构:用一组连续的存储单元顺序地存放数组中的诸数组元素。
数据元素的存放次序问题:解决存储单元是一维结构,而数组是个多维结构的矛盾。
(指多维数组)
二维数组元素间次序的排列方法:行优先与列优先序。
行优先序:按以行序为主序进行排列,就是把数组元素按行表次序、第i+1行的元素紧跟在第i行元素后面进行存储。
(列)
(列)
(列)
(j+1列)
(j列)
数组的顺序存储结构
9
示例: w是一个3*4的整数数组(起始下标从1开始)。
设二维数组变量w的诸数据组元素值如下表所示
1 2 3 4
1 0 -1 4 5
2 8 2 0 -3
3 -5 1 2 0
以列序为主序的存储方式——列