04推广的线性表 - 数组和广义表

第四章串和数组

第四章推广的线性表—数组和广义表数据结构基础教程史九林编著ISBN978-7-113-15395-3

本章目录4.1数组4.2矩阵与数组4.3广义表4.4数组和矩阵、广义表的应用

中国铁道出版社主要内容数组的概念、定义与存储结构1矩阵的概念、特殊矩阵、矩阵与数组2特殊矩阵的数组存储3广义表的概念与定义、特点4广义表的表示方法以及存储结构5数组、矩阵和广义表的应用6中国铁道出版社教学要求目标要求1.理解数组和广义表的结构特点；2.掌握数组元素的存储地址计算方法3.理解矩阵，特别是特殊矩阵与数组之间的关系；4.掌握广义表的表示方法和存储结构特点；5.了解数组、矩阵和广义表的应用教学重点1.数组、广义表相对于线性表的推广性；2.数组元素地址计算公式的设计方法；3.利用数组结构存储特殊矩阵的设计方法；特别存储稀疏矩阵的十字链表结构；4.广义表结构的递归性，以及广义表的链存储结构教学难点1.高维数组的元素地址计算公式；2.稀疏矩阵压缩存储表示下实现的算法，以及十字链表结构；3.广义表的递归性问题；4.数组、矩阵和广义表的应用中国铁道出版社4.1数组中国铁道出版社1.数组的定义118234185202数组：

n（n＞1）个相同类型的数据元素a1,a2,…,an逻辑上按一定维度规则排列构成的有限序列。相同类型：数据元素都有相同的数据类型；维（度）：数据元素的排列方向，可以是一个或多个方向；457911516341270315421一维数组列向列向行向二维数组列向层向行向三维数组中国铁道出版社1.数组的定义数组：

n（n＞1）个相同类型的数据元素a1,a2,…,an逻辑上按一定维度规则排列构成的有限序列。数组元素：数组中的任何一个数据元素；如“12”，“3”下标：标示数组元素在数组中位置的数；如[3,1]，[2,3]；下标界：下标的变化范围（下界≤下标≤上界）；4579115163412703154211234123数组AA[2,3]A[3,1]如，A[i,j]1≤i≤31≤j≤4ij中国铁道出版社1.数组的定义数组：

n（n＞1）个相同类型的数据元素a1,a2,…,an逻辑上按一定维度规则排列构成的有限序列。数组的结构类型描述：#defineMAXSIZE1p#defineMAXSIZE2m#defineMAXSIZE2n

数据类型符1A[MAXSIZE3];

数据类型符2A[MAXSIZE2][MAXSIZE3];数据类型符3A[MAXSIZE1][MAXSIZE2][MAXSIZE3];一维数组二维数组三维数组还可以描述四维或更高维的数组中国铁道出版社2.数组的存储结构数组一般都采用顺序表的结构存储一维数组元素的地址计算公式：

存储空间起始地址s第5个数组元素的存储地址s+(5-1)b单个数组元素存储单元长度b三要素决定一维数组的数组元素地址：①基地址s:第1个数组元素的存储地址,即数组的开始地址;②数组元素长度b:单个数组元素所占用的单元个数:③数组元素的逻辑序号i:数组元素在数组中的逻辑位置。一维数组的存储结构就是一个顺序表。如118234185202数组元素：A[1]A[2]A[3]A[4]A[5]A[6]数组A：存储位置：s+0bs+1b

s+2bs+3b

s+4bs+5bb<sz[i]>=s+(i-1)×b数组名表示“地址”中国铁道出版社2.数组的存储结构例如，一维数组A的存储结构如下面的布局图118234185202基地址s=2054数组元素长度b=4数组元素逻辑号设为i地址计算公式<A[i]>=s+(i-1)b地址数组类型A[6]2054：2058：2062：2066：2070：2074：<A[1]>=2054+(1-1)×4=2054<A[2]>=2054+(2-1)×4=2058<A[3]>=2054+(3-1)×4=2062<A[4]>=2054+(4-1)×4=2066<A[5]>=2054+(5-1)×4=2070<A[6]>=2054+(6-1)×4=2074中国铁道出版社2.数组的存储结构首先把二维数组看成是其每行为数组元素的一维数组：二维数组同样采用顺序表的结构存储457911516341270315421套用一维数组的地址计算公式，有：数组TT[1]T[2]T[3]T[1]T[2]T[3]s+0eS+1es+2ee

<T[i]>=s+(i-1)e中国铁道出版社2.数组的存储结构因为每行都是一个一维数组，因此二维数组是一个嵌套了一维数组的数组：二维数组同样采用顺序表的结构存储T[1]T[2]T[3]s+0eS+1es+2e综合以上计算，有：

<T[i][j]>=s+(i-1)e+(j-1)b=s+（(i-1)4+(j-1)）×b

457911516341270315421T[1][1]T[1][2]T[1][[3]T[1][4]T[2][1]T[2][2]T[2][3]T[2][4]T[3][1]T[3][2]T[3][3]T[3][4]b因为有e=4b，则

<T[1][1]>=s+0e+0b=s+0b<T[2][1]>=s+1e+0b=s+4b+0b<T[3][1]>=s+2e+0b=s+8b+0b

<T[1][2]>=s+0e+1b=s+1b<T[2][2]>=s+1e+1b=s+4b+1b<T[3][2]>=s+2e+1b=s+8b+1b

<T[1][3]>=s+0e+2b=s+2b<T[2][3]>=s+1e+2b=s+4b+2b<T[3][3]>=s+2e+2b=s+8b+2b

<T[1][4]>=s+0e+3b=s+3b<T[2][4]>=s+1e+3b=s+4b+3b<T[3][4]>=s+2e+3b=s+8b+3b一行上数组元素的个数（列下标的上界）中国铁道出版社2.数组的存储结构因为每行都是一个一维数组，因此二维数组是一个嵌套了一维数组的数组：二维数组同样采用顺序表的结构存储T[1]T[2]T[3]s+0eS+1es+2e

<T[i][j]>=s+（(i-1)n+(j-1)）×b457911516341270315421T[1][1]T[1][2]T[1][[3]T[1][4]T[2][1]T[2][2]T[2][3]T[2][4]T[3][1]T[3][2]T[3][3]T[3][4]b设二维数组T[m][n]，则其数组元素的一般地址计算公式为：列下标的上界中国铁道出版社2.数组的存储结构例如，二维数组T的存储结构如下面的布局图基地址s=2048数组元素长度b=2数组元素逻辑号设为i，j地址计算公式<T[i][j]>=s+（(i-1)4+(j-1)）b<T[1][1]>=2048+((1-1)×4+(1-1))×2=2048<T[1][2]>=2048+((1-1)×4+(2-1))×2=2050<T[1][3]>=2048+((1-1)×4+(3-1))×2=2052<T[1][4]>=2048+((1-1)×4+(4-1))×2=2054<T[2][1]>=2048+((2-1)×4+(1-1))×2=2056<T[2][2]>=2048+((2-1)×4+(2-1))×2=2058<T[2][3]>=2048+((2-1)×4+(3-1))×2=2060<T[2][4]>=2048+((2-1)×4+(4-1))×2=2062<T[3][1]>=2048+((3-1)×4+(1-1))×2=2064<T[3][2]>=2048+((3-1)×4+(2-1))×2=2066<T[3][3]>=2048+((3-1)×4+(3-1))×2=2068<T[3][4]>=2048+((3-1)×4+(4-1))×2=2070457911516341270315421地址2048：2050：2052：2054：2056：2058：2060：2062：2064：2066：2068：2070：数组类型T[3][4]

中国铁道出版社2.数组的存储结构三维数组同样采用顺序表的结构存储

<T[i][j][k]>=s+（(i-1)m×n+(j-1)n+(k-1))×b设三维数组S[p][m][n]，则其数组元素的一般地址计算公式为：由此不难推导出多维（4维或以上）数组数组元素的一般地址计算公式一层上数组元素的最多个数一行上数组元素的最多个数中国铁道出版社3.数组的基本运算1创建数组建立一个新数组2数组初始化对数组元素赋初始值3读数组元素读取并返回指定数组元素的当前值4数组元素赋值给指定数组元素赋一个新值5销毁数组删除数组并释放存储空间中国铁道出版社4.2矩阵与数组中国铁道出版社1.矩阵矩阵是一种数学工具；在科学与工程问题求解中运用很多见；数学上，一个m×n的矩阵是一个由m行n列元素排列成的矩形阵列。矩阵里的元素可以是数字、符号或数学式。中国铁道出版社2.矩阵的存储常规的矩阵与二维数组的逻辑结构基本一致；因此，在计算机上用二维数组表示和存储一个矩阵。A[m][n]

a[1][1]a[1][2]......a[1][n]a[2][1]a[2][2]......a[2][n]......a[m][1]a[m[2]......a[m][n]第1行第2行第m行......表示为二维数组存储二维数组中国铁道出版社3.特殊矩阵一个m×n阶矩阵必有m×n个元素；有些矩阵的元素值具有某些特殊特征，并称之为特殊矩阵；常见的有：特殊矩阵稀疏矩阵三角形矩阵对角线矩阵对称矩阵中国铁道出版社4.特殊矩阵的存储特殊矩阵的存储设计意在以较少的存储空间存储整个矩阵，而且不失去它的可用性特殊矩阵的存储设计思想是：不再依一般矩阵的存储方法设置一个二维数组存储数组的全部元素。几乎所有的特殊矩阵都可以设计一个一维数组存储，称为顺序存储结构，或压缩存储。通常是设计一个一维数组和一个与之对应的映射公式。映射公式的任务是建立矩阵元素与数组元素的等值关系。对某些特殊矩阵可以设计链存储结构。中国铁道出版社4.特殊矩阵的存储（1）对角线矩阵的存储对n×n阶对角线矩阵设计一个有n个数组元素的一维数组，存储主对角线上的元素，其余元素皆已知为“0”。a11a22a33...anna1100...00a220...000a33...0............000...annDnn=数组D[n]Dii

=D[i]当i=j时0当i≠j时映射公式：只n有效数据却有n(n-1)个“0”中国铁道出版社4.特殊矩阵的存储（2）三角形矩阵的存储三角形矩阵分上三角形矩阵和下三角形矩阵两种；其主对角线的下部或上部皆为“0”；可以不予存储。a11a21a22a31a32a33...an1an2an3...ann第1行第2行第3行

...

第n行上三角矩阵下三角矩阵Ann=Bnn=数组B[(1+n)n/2]Bij=B[k+j]（其中k=i(i-1)/2）当i≥j时0

当i<j时

映射公式：中国铁道出版社4.特殊矩阵的存储（3）对称矩阵的存储

对称矩阵是其元素以主对角线为对称轴对应相等的矩阵；即有Dji=Dij。只要存储它的下或上三角形部分就可以了。忽略主对角线上方元素，成下三角形矩阵忽略主对角线下方元素，成上三角形矩阵Dnn=a11a21a22a31a32a33...an1an2an3...ann第1行第2行第3行

...

第n行数组D[(1+n)n/2]Dij=D[k2+j]（其中k2=i(i-1)/2

当

i≥j时

D[k1+i]（其中k1=j(j-1)/2）当i＜j

时映射公式：中国铁道出版社4.特殊矩阵的存储（4）稀疏矩阵的存储--顺序存储结构（三元组方式）

稀疏矩阵是“0”元素比“非0”元素多得多，且出现位置无规律的矩阵。例如，5×6的稀疏矩阵M应有30个元素，但其中只有8个“非0”元素，其余22个元素恒为“0”。（行号,列号,非0元素）（i，j，v）（1，1

,

5）（1

,

4

,

3）（2,2,1）（2

,

6

,

2）（3

,1,7）（3

,4,4）（4,6,9）（5,5,6）“非0”元素表示表示“非0”元素的三元组线性表可存储为顺序表或单向链表注意其有序性中国铁道出版社4.特殊矩阵的存储typedefstruct{

inti,j；

数据类型符v；}Node；typedefstruct{

intn,m；

NodeD[9]；

intk；}SparseMatrix；稀疏矩阵的顺序存储结构类型描述：顺序表的结点描述（三元组）顺序表的描述（4）稀疏矩阵的存储--顺序存储结构（三元组方式）中国铁道出版社4.特殊矩阵的存储（4）稀疏矩阵的存储--链存储结构（十字链表方式）任何一个矩阵元素都处在一个行链和一个列链上，形成一个“十”字交叉点。中国铁道出版社5.数组和矩阵的应用

对一个m×n的矩阵M，执行转置运算后的结果MT是一个m×n矩阵，其元素的等价关系是

MT（i,j）=M（j,i）转置后转置后（1）稀疏矩阵的转置中国铁道出版社5.数组和矩阵的应用ijv012345678568115143221262317344469556Mijv012345678

7

6

8115137221413434556622649MT

解决思路：

将矩阵行、列

维数互换将每个三元组中的i

和j

相互调换重排三元组次序，使MT中元素以MT

的行(即M的列)

为主序。MTijv0123456781154132216221374346495566

5

8

转置算法的思路中国铁道出版社5.数组和矩阵的应用（2）打印杨辉三角杨辉三角是(x+a)n

展开式的系数。它的分布规律是：⑴第1列和主对角线上的元素都为1；⑵其余元素是上一行中同列元素与其左边元素之和。10000000110000001210000013310000146410001510105100161520156101102135352171中国铁道出版社5.数组和矩阵的应用（2）打印杨辉三角解决方案1：

设置一个二维数组Y[n][n]；Y[n][n]

=1000000011000000121000001331000014641000151010510016152015610172135352171

0

(当i＜j时)1

(当j＝1或j＝i时)

Y[i-1][j]+Y[i-1][j-1]

(当i,j≠1且i≠j且j＜i时)Ｙ[i][j]

=使有，中国铁道出版社5.数组和矩阵的应用（2）打印杨辉三角解决方案2：

杨辉三角实际是一个三角形矩阵；可以设置一个一维数组存储之。Y[(1+n)n/2]1111211331...17213535217110000000110000001210000013310000146410001510105100161520156101102135352171中国铁道出版社5.数组和矩阵的应用（2）打印杨辉三角YanghuiTriangle(n){

intTri[n(1+n)/2]={1,1,1};

inti,j,k;

for(i←3；i≤n；i←i+1)

{

Tri[i(i-1)/2+1]←1;

for(j←2；j＜i；j←j+1)

{

k←(i-1)(i-2)/2+j;

Tri[i(i-1)/2+j]←Tri[k-1]+Tri[k];

}

Tri[i(i-1)/2+j]←1

}

for(i←1；i≤n；i←i+1)

{

printf(“%d:”,i);

for(j←1；j≤i；j←j+1)

printf(“%d”,Tri[i(i-1)/2+j])

}}解决方案2的算法描述：

中国铁道出版社5.数组和矩阵的应用（3）解线性方程组解决方案（高斯-若当(Gauss—Jordan)消去法）：

a11x1+a12x2+…+a1nxn

=

b1,a21x1+a22x2+…+a2nxn

=

b2,…an1x1+an2x2+…+annxn

=

bn,原形表示：a11a12…a1na21a22…a2n…An1an2…annA=X=x1

x2…xnB=b1

b2…bn对应矩阵：AX=B矩阵表示：系数矩阵未知数矩阵常数项矩阵中国铁道出版社5.数组和矩阵的应用（3）解线性方程组解决方案：

a11a12…a1na21a22…a2n…An1an2…ann增广矩阵：P=X=x1

x2…xnB=b1

b2…bn对应矩阵：A=定义二维数组：A[n][n+1]=a11a12...a1nb1a21a22...a2nb2...............an1an2...annbn中国铁道出版社5.数组和矩阵的应用（3）解线性方程组解决方案：

定义二维数组：A[n][n+1]=a11a12...a1nb1a21a22...a2nb2...............an1an2...annbn利用二维数组实施矩阵变换得：（高斯-若当消去法）10...0b‘101...0b’2...............00...1b‘n最后得到方程组的解为：x1=b‘1，x2=b‘2，...，xn=b‘n中国铁道出版社4.3广义表中国铁道出版社1.广义表的定义

广义表是n（n≥0）个元素ai(i=1,2,...,n)的有限序列；其中，ai或者是一个原子元素（或简称原子），或者是一个广义表（或简称子表）；并表示为， GL=(a1，a2，…，ai，…，an)理解定义：

⑴广义表中元素也可能是广义表，且元素有序；⑵广义表是线性表的一个推广；⑶广义表是一种多层次的表；⑷广义表可以共享；⑸广义表可以是递归的；⑹广义表可以为空。中国铁道出版社1.广义表的定义

广义表是n（n≥0）个元素ai(i=1,2,...,n)的有限序列；其中，ai或者是原子元素（或简称原子），或者是一个广义表（或简称子表）。记为， GL=(a1，a2，…，ai，…，an)几个例子：

E=() A=(a,b,c) B=(x,A)=(x,(a,b,c)) C=(B,y)=((x,(a,b,c)),y) D=(A,B)=((a,b,c),(x,(a,b,c))) F=(z,F) G=(())空表纯原子元素的层次的，被共享的递归的非空表共享B共享B中国铁道出版社1.广义表的定义

广义表是n（n≥0）个元素ai(i=1,2,...,n)的有限序列；其中，ai或者是原子元素（或简称原子），或者是一个广义表（或简称子表）。记为， GL=(a1，a2，…，ai，…，an)可见：

广义表是线性表的一种推广；数组是一种广义表，也是线性表的推广；但它的元素具有规律性；矩阵对应于二维数组，特殊矩阵可以存储为一维数组或线性表；所以矩阵是线性表的推广。中国铁道出版社1.广义表的定义

广义表是n（n≥0）个元素ai(i=1,2,...,n)的有限序列；其中，ai或者是原子元素（或简称原子），或者是一个广义表（或简称子表）。记为， GL=(a1，a2，…，ai，…，an)几个术语：

⑴广义表的长度广义表最外层的元素个数；

⑵广义表的深度在广义表被充分展开后，其括号嵌套的最大重数。

⑶广义表的表头和表尾。非空广义表的第一个元素为表头（记为Head(GL)），其余元素为表尾（记为Tail(GL)）中国铁道出版社2.广义表的表示

广义表具有层次性；它的表示必须表现出这种层次性。广义表有多种表示方法。（1）嵌套表示法：用括号表示出表的嵌套关系。

如，E=() A=(a,b,c) B=(x,(a,b,c)) C=((x,(a,b,c)),y) D=((a,b,c),(x,(a,b,c))) F=(z,(z,(z,...))) G=(())中国铁道出版社2.广义表的表示

广义表具有层次性；它的表示必须表现出这种层次性。广义表有多种表示方法。（2）带名字表示法：类似嵌套表示法，在每个表的前面冠以该表的名字

如，E=() A=(a,b,c) B=(x,A(a,b,c)) C=(B(x,A(a,b,c)),y) D=(A(a,b,c),B(x,A(a,b,c))) F=(z,F(z,F(z,F(...))))中国铁道出版社2.广义表的表示

广义表具有层次性；它的表示必须表现出这种层次性。广义表有多种表示方法。（3）图形表示法：用括号表示出表的嵌套关系。

如，方形表示原子圆形表示表或子表中国铁道出版社3.广义表的存储结构

广义表一般都采用链结构（1）H-T链结构：即“头-尾”结构。分别用“表头”和“表尾”配对表示广义表及其所含的子表。如例表C=(B,y)=((x,(a,b,c)),y)存储为：

表头表头表头表头表头表尾中国铁道出版社3.广义表的存储结构

广义表一般都采用链结构（1）H-T链结构：即“头-尾”结构。分别用“表头”和“表尾”配对表示广义表及其所含的子表。如例表C=(B,y)=((x,(a,b,c)),y)存储为：

H-T链结构类型描述：typedefstructnode{ inttag; union

{

原子数据类型符data;

structnode*hp,*tp; }dataorptr;

}HTnode;原子结点=0子表结点=1原子结点时，存储结点数据值子表结点时，存储表头结点指针和表尾结点指针中国铁道出版社3.广义表的存储结构

广义表一般都采用链结构（2）C-B链结构：即“孩子-兄弟”结构。分别用“孩子”指针和“兄弟”指针表示广义表的嵌套关系。如例表C=(B,y)=((x,(a,b,c)),y)存储为：

孩子孩子表头表头表头表尾表头中国铁道出版社3.广义表的存储结构

广义表一般都采用链结构（2）C-B链结构：可以先用图形表示法表示出广义表，在此基础上转换为C-B链结构。如例表C=(B,y)=((x,(a,b,c)),y)的存储结构转换方法为：

CBAXYabc操作步骤：第1步，连接兄弟；第2步，删除第1个孩子以外的孩子连线；中国铁道出版社3.广义表的存储结构

广义表一般都采用链结构（2）C-B链结构：可以先用图形表示法表示出广义表，在此基础上转换为C-B链结构。如例表C=(B,y)=((x,(a,b,c)),y)