数组与广义表课件

数组与广义表

5.1数组的定义

数组：由一组名字相同、下标不同的变量构成。答：对的。因为——①数组中各元素具有统一的类型；②数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。判断：“数组的处理比其它复杂的结构要简单”，对吗？二维数组的特点：一维数组的特点：1个下标，ai

是ai+1的直接前驱2个下标，每个元素ai,j受到两个关系（行关系和列关系）的约束：一个m×n的二维数组可以看成是m行的一维数组，或者n列的一维数组。N维数组的特点：n个下标，每个元素受到n个关系约束一个n维数组可以看成是由若干个n－1维数组组成的线性表。

a11a12…a1n

a21a22…a2n

…………

am1am2…amn

Amn=N维数组的数据类型定义n_ARRAY=(D,R)其中：

Ri

={<aj1,j2,…ji…jn,aj1,j2,…ji+1…jn

>|

aj1,j2,…ji…jn,aj1,j2,…ji+1…jn

D}

数据关系：R={R1,R2，….Rn}数据对象：D={aj1,j2…jn|ji为数组元素的第i维下标，

aj1,j2…jn

Elemset}构造数组、销毁数组、读数组元素、写数组元素

基本操作：5.2数组的顺序存储表示和实现问题：计算机的存储结构是一维的，而数组一般是多维的，怎样存放？解决办法：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。注意：若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所不同；C和PASCAL中一般采用行优先顺序；FORTRAN采用列优先。补充：计算二维数组元素地址的通式

设一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是0或1

无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址：二维数组列优先存储的通式为：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*Lac1,c2…ac1,d2…aij…

ad1,c2…ad1,d2

Amn=单个元素长度aij之前的行数数组基址总列数，即第2维长度aij本行前面的元素个数①开始结点的存放地址（即基地址）②维数和每维的上、下界；③每个数组元素所占用的单元数则行优先存储时的地址公式为：

LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*La(0,0)a(0,1)……a(0,3)a(1,0)a(1,1)……a(1,3)………………………………a(3,2)………………………………………………a(6,0)…………a(6,3)01230123456例1：如何求出a(3,2)的存储地址？要事先确定：①是行优先方式还是列优先方式？②数组的首地址是多少？③每个元素的长度？否则无法求出结果例3：已知二维数组Am,m按行存储的元素地址公式是：

Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K,请问按列存储的公式相同吗？答：尽管是方阵，但公式仍不同。应为：

Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K例2：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是

个字节。288答：

Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288例4

：〖00年计算机系考研题〗：设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为

。根据列优先公式Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K得：LOC(a32,58)=2048+[(58-1)*60+(32-1)]*2＝8950答：请注意审题！想一想：若数组是a[0…59,0…69]，结果是否仍为8950？8950维界虽未变，但此时的a[32,58]不再是原来的a[32,58]Loc(j1,j2,…jn)=LOC(0,0,…0)＋若是n维数组，其中任一元素的地址该如何计算？其中Cn=L,Ci-1=bi×Ci，1<i≤n每个元素长度数组基址前面若干元素占用的地址字节总数第i维长度与所存元素个数有关的系数，可用递推法求出低维优先的地址计算公式，该式称为n维数组的映像函数：三维数组且列优先时的元素地址要会计算！例5：假设有三维数组A7×9×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，末尾元素A[6][8][7]的第一个字节地址为多少？若按高地址优先存储时，元素A[4][7][6]的第一个字节地址为多少？

答：

①末尾元素A[6][8][7]的第1个字节地址＝

1000+(7×9×8)×6－6=4018

②按高地址优先存储时，元素A[4][7][6]的第1个字节地址＝提示：将第3维看作“页码”，前面两维就是每页上的二维数组。3586只要计算出任一数组元素的地址，就能对其轻松地进行读写操作！计算地址的意义：#defineMAX_ARRAY_DIM8//假设最大维数为8typedefstruct{ELemType*base;//数组元素基址

intdim;//数组维数

int*bound;//数组各维长度信息保存区基址

int*constants;//数组映像函数常量的基址

}Array;即Ci信息保存区N维数组的顺序存储表示^……行指针向量a11a12…^a1nam1am2…^amn补充：数组的链式存储方式—用带行指针向量的单链表来表示。注：链式数组的运算请参见“稀疏矩阵的转置”5.3矩阵的压缩存储讨论：1.什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。2.所有二维数组（矩阵）都能压缩吗？未必，要看矩阵是否具备以上压缩条件。3.什么样的矩阵具备以上压缩条件？

一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。4.什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于5%）一、稀疏矩阵的压缩存储问题：如果只存储稀疏矩阵中的非零元素，那这些元素的位置信息该如何表示？解决思路：对每个非零元素增开若干存储单元，用来存放其所在的行号和列号，便可准确反映该元素所在位置。实现方法：将每个非零元素用一个三元组（i，j，aij）来表示，则每个稀疏矩阵可用一个三元组表来表示。例2：写出右图所示稀疏矩阵的压缩存储形式。0

1290000

00000

-30001400

0240000

18000015

00-700

(1,2,12)

，(1,3,9)，(3,1,-3)，(3,5,14)，

(4,3,24)，(5,2,18)，(6,1,15)，(6,4,-7)解：至少有4种存储形式。法1：用线性表表示：0

1290000

00000

-30001400

024

0000

18000015

00-700()例1：

三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的

、

和

。行下标列下标元素值法2：用三元组矩阵表示：0

1290000

00000

-30001400

024

0000

18000015

00-700121213931-3351443245218611564-7注意：为更可靠描述，通常再加一行“总体”信息：即总行数、总列数、非零元素总个数668ijvalue稀疏矩阵压缩存储的缺点：012345678将失去随机存取功能！法三：用带辅助向量的三元组表示。

方法：增加2个辅助向量：①记录每行非0元素个数，用NUM（i）表示；

②记录稀疏矩阵中每行第一个非0元素在三元组中的行号，用POS（i）表示。76531211202NUM(i)6543POS(

i)21i0

1290000

00000

-30001400

024

0000

18000015

00-700-7461516182524341453-3139311221866vji0123456783POS(i)如何计算？POS(1)＝1POS(i)＝POS(i-1)+NUM(i-1)用途后续法四：用十字链表表示用途：方便稀疏矩阵的加减运算方法：每个非0元素占用5个域rightdownvji同一列中下一非零元素的指针同一行中下一非零元素的指针十字链表的特点：①每行非零元素链接成带表头结点的循环链表；②每列非零元素也链接成带表头结点的循环链表。则每个非零元素既是行循环链表中的一个结点；又是列循环链表中的一个结点，即呈十字链状。122100H19311825稀疏矩阵的加减运算容易实现例3：下面的三元组表表示一个稀疏矩阵，试还原出它的稀疏矩阵。64612221123134445366116ijvalue0123456646

0

000

0

000

0000

0

000

0

000

0

000

0

20012

000

3000

0

004

0

06016

000typedefstruct{

Triple

data[MAXSIZE+1];//三元组表，以行为主序存入一维向量

data[]中

int

mu;//矩阵总行数

int

nu;//矩阵总列数

inttu;//矩阵中非零元素总个数}TsMatrix;三元组表的顺序存储表示

#defineMAXSIZE125000//设非零元素最大个数125000typedefstruct{inti;//元素行号

intj;//元素列号

ElemTypee;//元素值}Triple;

对表中每个结点的结构定义二、稀疏矩阵的操作

0

12

9

0000

00000-3

000

14

00

0

24

0000

18

000015

00

-7

000

0–3001512

000180

90024000

0000-70

0140000

00000(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)(1,3,-3)(1,6,15)(2,1,12)(2,5,18)(3,1,9)(3,4,24)(4,6,-7)(5,3,14)已知三元组表a.data求三元组表b.data转置后MT目的：答：肯定不正确！除了：（1）每个元素的行下标和列下标互换（即三元组中的i和j互换）；还需要：（2）T的总行数mu和总列数nu也要互换；（3）重排三元组内各元素顺序，使转置后的三元组也按行（或列）为主序有规律的排列。上述（1）和（2）容易实现，难点在（3）。

若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法正确吗？有两种实现转置的方法压缩转置快速(压缩)转置提问：方法1：压缩转置思路：反复扫描a表（记为a.data）中的列序，从j=1～n依次进行转置。已知三元组表a.data求三元组表b.data①(1,3,-3)②(1,6,15)③(2,1,12)④

(2,5,18)⑤(3,1,9)⑥

(3,4,24)⑦

(4,6,-7)⑧

(5,3,14)(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)11

22colq1234每个元素的列分量表示为：a.data[p].jp1234......方法2

快速转置已知三元组表a.data求三元组表b.data③(1,3,-3)①(2,1,12)⑥(2,5,18)②(3,1,9)⑧(4,6,-7)④(5,3,14)⑦

(1,6,15)⑤(3,4,24)(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)思路：依次把a.data中的元素直接送入b.data的恰当位置上（即M三元组的p指针不回溯）。关键：怎样寻找b.data的“恰当”位置？p1234q35快速转置寻找对应元素的位置需引入两个向量来实现：num[n+1]和cpot[n+1]，num[col]表示矩阵A中第col列的非零元素的个数（为了方便均从1单元用起），cpot［col］初始值表示矩阵A中的第col列的第一个非零元素在B.data中的位置。于是cpot的初始值为：

cpot[1]=1；

cpot[col]=cpot[col-1]+num[col-1]；

2≤col≤n

稀疏矩阵的乘积

已知稀疏矩阵A(m1×n1)和B(m2×n2)，求乘积C(m1×n2)。稀疏矩阵的乘法运算的步骤如下：⑴初始化。清理一些单元，准备按行顺序存放乘积矩阵;⑵求B的num，rpot;⑶做矩阵乘法。将A.data中三元组的列值与B.data中三元组的行值相等的非零元素相乘，并将具有相同下标的乘积元素相加。稀疏矩阵的十字链表存储

用十字链表表示稀疏矩阵的基本思想是：对每个非零元素存储为一个结点，结点由5个域组成：row域存储非零元素的行号，col域存储非零元素的列号，v域存储本元素的值，right，down是它的两个指针域。十字链表的存储结构typedefstructnode{introw,col;structnode*down,*right;unionv_next{datatypev;structnode*next;}}MNode，*MLink;

5.4

广义表的定义

顾名思义，广义表是线性表的推广。也有人称其为列表（Lists，用复数形式以示与统称的表List的区别）。

广义表（GeneralizedLists）是n（n≥0）个数据元素a1，a2，…，ai，…，an的有序序列，一般记作：

ls＝（a1，a2，…，ai，…，an）

广义表是一个多层次的线性结构例如：D=(E,F)其中:

E=(a,(b,c))F=(d,(e))DEFa()d()bce

2.广义表的性质

⑴广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，…。⑵广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。例如表E就是一个递归的表。⑶广义表可以为其他表所共享。例如，表A、表B、表C是表D的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。⒊广义表基本运算

广义表有两个重要的基本操作，即取头操作（Head）和取尾操作（Tail）。根据广义表的表头、表尾的定义可知，对于任意一个非空的列表，其表头可能是单元素也可能是列表，而表尾必为列表。例如：

Head（B）＝eTail（B）＝（）

Head（C）＝aTail（C）＝（（b，c，d））

Head（D）＝ATail（D）＝（B，C）

Head（E）＝aTail（E）＝（E）

Head（F）＝（）

Tail（F）＝（）

5.5广义表的存储结构tag=1hptptag=0data通常采用头、尾指针的链表结构表结点:原子结点：1)表头、表尾分析法：构造存储结构的两种分析方法:若表头为原子，则为空表

ls=NIL非空表lstag=1指向表头的指针指向表尾的指针tag=0data否则，依次类推。L=(a,(x,y),((x)))

1

L0a

1

1

1

1

1

0a

5.6广义表操作的递归函数递归函数

一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：1)在每一次调用自己时，必须是(在某种意义上)更接近于解;2)必须有一个终止处理或计算的准则。例如:

梵塔的递归函数voidhanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);}}广义表的深度=Max{子表的深度}+1例1求广义表的深度可以直接求解的两种简单情况为：

空表的深度=1

原子的深度=0

将广义表分解成n个子表，分别(递归)求得每个子表的深度：intGlistDepth(GlistL){if(!L)return1;if(L->tag==ATOM)return0;for(max=0,pp=L;pp;pp=pp->ptr.tp){dep=GlistDepth(pp->ptr.hp);if(dep>max)max=dep;}returnmax+1;}//GlistDepth111L…

for(max=0,

pp=L;pp;pp=pp->ptr.tp){dep=GlistDepth(pp->ptr.hp);

if(dep>max)max=dep;

}例如:pppp->ptr.hppppppp->ptr.hppp->ptr.hp例二复制广义表新的广义表由新的表头和表尾构成。

可以直接求解的两种简单情况为：空表复制求得的新表自然也是空表;

原子结点可以直接复制求得。

将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾，若ls=N