《数据结构》 第五章数组和广义表
《数据结构》 第五章 数组和广义表
第五章数组和广义表 内容和要求 ●内容和要求 重点 数组和广义表的 数组和广义表的 既念、存储结构和矩 存储特性,桸疏矩阵 阵的压缩存储方法 要求对数组和广义表 存储。 有较深刻的了解。掌 握数组和广义表的概 念,熟悉它们的存储 结构及基本应用。 第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={| c1≤i≤d1 , c2≤j≤d2 -1, aij, ai , j+1 ∈D} Col={| 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={| i=1,2,···,m, j=1,2,···,n-1, aij, ai , j+1∈D} Col={| 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) 都只有一个后继结点或者只有一个前趋结点
0数组的逻辑结构 第五章数组和广义表 n(>2)维数组的逻辑结构一 n维数组的逻辑结构的形式定义 n- Array=(D,R) (5-2) 其中 Ji=Ci, ci i=1.2 D=14…n∈D,且c和d均为整数 R=RR R ≤d.1≤k≤n且k≠ R +1 j1≤d1-1 ∈D 说明 1)n维数组的元素个数为nn2…nn=∏n 2)n维数组中每个数据元素都属于n个向量(受n个关系制约) ,除边界上的元素外,均可以有n个前趋和n个后继。 第6页
第五章 数组和广义表 第6页 n(n>2)维数组的逻辑结构 n维数组的逻辑结构的形式定义 (5 2) ( , ) − n − Array = D R − = = = = = − = − + + + a a D c j d c j d k n k i R a a R R R R a D c d j c c d i n n D a n Array D R i n i n i n i n n n j j j j j j i i i k k k i j j j j j j n j j j i i i i i i j j j 1 , , 1 1 2 , 0 1 , 1 1 1 1 1 2 1 2 , 1 ,1 , , , , , , , , , 1,2, ( 0) ( , ) (5 2) 且 且 和 均为整数 其中 说明： 1）n维数组的元素个数为n1·n2· ··· ·nn = ni . 2）n维数组中每个数据元素都属于n个向量（受n个关系制约） ，除边界上的元素外，均可以有n个前趋和n个后继。 ⚫ 数组的逻辑结构
0数组的逻辑结构 第五章数组和广义表 N维数组的递归定义一 K_Aray=(D,R6)(1≤k≤n)(5-3) 其中 (k) k+1 时,A.)是k-1维数组 R()={AR} ≤i1≤ AR=3<A (k) (k) k)(k) 43a+∈D 在这递归定义中,一个k维数组是其数据元素为k-1维数组的线 性表,Cnk+1和dnk是第k维下标的一对界偶。 n维数组是一种较复杂的数据结构,但它可以由简单的数据结 构——线性表辗转合成而得。 第7页
第五章 数组和广义表 第7页 N维数组的递归定义 = = − = = = − + − + − + + − + − + A A D c i d AR A A R AR k A k k A D A c i d D K Array D R k n k i k i n k k n k k i k i k k i k i n k k n k k i k k k k k k k k k k ( ) 1 ( ) 1 1 ( ) 1 ( ) ( ) ( ) 0 ( ) 1 1 ( ) ( ) ( ) ( ) , , 1 , 1 1 , _ ( , )(1 ) (5 3) 时 是 维数组 时 其中 在这递归定义中，一个k维数组是其数据元素为k-1维数组的线 性表，cn-k+1和dn-k+1是第k维下标的一对界偶。 n维数组是一种较复杂的数据结构，但它可以由简单的数据结 构——线性表辗转合成而得。 ⚫ 数组的逻辑结构
0数组的逻辑结构 第五章数组和广义表 数组的操作 个数组中所有的数据元素都必须属于同一数据类型。 对于数组,通常只有两种基本操作: 1)给定一组下标,存取相应的数据元素。 几)给定一组下标,修改相应数据元素中的某一个或 数据项的值 注.对于二维数组的抽象即矩阵,可包含取值、赋值 和初始化等操作。编译程序用线性存储器来实现矩阵。 第8页
第五章 数组和广义表 第8页 数组的操作 一个数组中所有的数据元素都必须属于同一数据类型。 对于数组，通常只有两种基本操作： 1）给定一组下标，存取相应的数据元素。 2）给定一组下标，修改相应数据元素中的某一个或 几个数据项的值。 注. 对于二维数组的抽象即矩阵，可包含取值、赋值 和初始化等操作。编译程序用线性存储器来实现矩阵。 ⚫ 数组的逻辑结构
0数组的版序存猪结构 第五章数组和广义表 数组的顺序存储结构:用一组连续的存储 单元顺序地存放数组中的诸数组元素 数据元素的存放次序问题:解决存储单元 是一维结构,而数组是个多维结构的矛盾 (指多维数组) 二维数组元素间次序的排列方法:行优先 与列优先序 优先序:按以行序为主序进行排列,就 1列 一是把数组元素按行表次序、第计1行的元素紧 跟在第i行元素后面进行存储 第9页
第五章 数组和广义表 第9页 数组的顺序存储结构：用一组连续的存储 单元顺序地存放数组中的诸数组元素。 数据元素的存放次序问题：解决存储单元 是一维结构，而数组是个多维结构的矛盾。 （指多维数组） 二维数组元素间次序的排列方法：行优先 与列优先序。 行优先序：按以行序为主序进行排列，就 是把数组元素按行表次序、第i+1行的元素紧 跟在第i行元素后面进行存储。 （列） （列） （列） （j+1列） （j列） ⚫ 数组的顺序存储结构
0数组的版序存猪结构 第五章数组和广义表 一示例:W是一个3*4的整数数组(起始下标从1开始)。 设二维数组变量w的诸数据组元素值如下表所示 0 82 340 -3 3 5120 以列序为主序的存储方式 以行序为主序的存储方式一 列优先序「0 行优先序 8第1列 5 2第2列 01458 第1行 4 2第2行 0第3列 3 2530 -5 第4列 2}第3行 FORTRAN中采用 C, Pascal,BASC,PL1, COBOL等中采用 下面讨论的是按行为主序规则存储的情形。 第10页
第五章 数组和广义表 第10页 示例: w是一个3*4的整数数组（起始下标从1开始）。 设二维数组变量w的诸数据组元素值如下表所示 1 2 3 4 1 0 -1 4 5 2 8 2 0 -3 3 -5 1 2 0 以列序为主序的存储方式—— 列优先序 以行序为主序的存储方式—— 0 行优先序 8 -5 -1 2 1 4 0 2 5 -3 0 第1列 第2列 第3列 第4列 0 -1 4 5 8 2 0 -3 -5 1 2 0 第1行 第2行 第3行 FORTRAN中采用 C,Pascal, BASIC, PL/1, COBOL等中采用 下面讨论的是按行为主序规则存储的情形。 ⚫ 数组的顺序存储结构