《数据结构》 第五章数组和广义表
《数据结构》 第五章 数组和广义表
第五章数组和广义表 内容和要求 ●内容和要求 重点 数组和广义表的 数组和广义表的 既念、存储结构和矩 存储特性,桸疏矩阵 阵的压缩存储方法 要求对数组和广义表 存储。 有较深刻的了解。掌 握数组和广义表的概 念,熟悉它们的存储 结构及基本应用。 第2页
第五章 数组和广义表 第2页 内容和要求 ●内容和要求 数组和广义表的 概念、存储结构和矩 阵的压缩存储方法。 要求对数组和广义表 有较深刻的了解。掌 握数组和广义表的概 念，熟悉它们的存储 结构及基本应用。 ● 重点 数组和广义表的 存储特性，稀疏矩阵 存储
0数组的逻辑结构 第五章数组和广义表 维数组的逻辑结构二 数组和广义表可以看成是线性表在下述含义上的扩展:即线性 表中的数据元素本身也是一个数据结构。 类似于线性表,一个二维数组的逻辑结构可形式地表示为 2Aray=(D,R)(5-1) 其中 D={ai=c1,c1+1,…,djC2,C2+1,,d2a∈Do} R= RoW, Col∥行关系,列关系 ROW={可1a1c1sdC25502-1,aanH1∈D Col=aj ai+ 1, >1 C1sisd1-1, C2sjsd2, ajr a+1, EDy D为某个数据对象,C1,C2,d1,d2均为整数。 第3页
第五章 数组和广义表 第3页 二维数组的逻辑结构 数组和广义表可以看成是线性表在下述含义上的扩展：即线性 表中的数据元素本身也是一个数据结构。 类似于线性表，一个二维数组的逻辑结构可形式地表示为 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均为整数。 ⚫ 数组的逻辑结构
0数组的逻辑结构 第五章数组和广义表 若C1=1,d1=m,C2=1,d2=n,则有 D={a=1,2…m,=1,2,,n,∈D} R=(RoW, Col] R0W=aar1>|11,2,…m,j=12…,n1,aa+1∈D} Coaa1=1,2,m-1,=1,2,,n,a2+1,∈D 记作Ann,即A为m行n列的二维数组(起始下标为1)。 说明: 1)用于二维数组的抽象可称之为矩阵,它是对向量的推广,其 元素个数为m×n个。 1112 2142a2n mlm 第4页
第五章 数组和广义表 第4页 若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个。 ⚫ 数组的逻辑结构 = m m mn n n m n a a a a a a a a a A 1 2 21 22 2 11 12 1
0数组的逻辑结构 第五章数组和广义表 2)二维数组也可以看作是这样一个线性表:它的每一个数据 元素是一个线性表。从而对二维数组可以进行递归定义,即它是 数据元素为一维数组的线性表。可把Am×n看成是由m个行向量所 组成的向量(线性表),也可以看成是n个列向量所组成的向量。 m×n2=(a1,a2,…,ap)(p=m或n 若a1为行向量:a1=(a1a2…,an)-1-m 若为列向量:=(aya2…,an)1j≤n 3)二维数组中的每个元素都属于两个向量:第行的行向量和 第列的列向量(对元素可而言)。 4)每个元素可有两个前趋结点a1m和a(25m,2Sn),两 个后继结点a和a,#1(1m1,1n-1),其中a1无前趋,am无 后继。边界上的结点a1=2;…,n),am(=1,n-1)和an(=1,,m-1) 都只有一个后继结点或者只有一个前趋结点 第5页
第五章 数组和广义表 第5页 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) 都只有一个后继结点或者只有一个前趋结点