第6章多维数组和广义表课件.ppt

1、第第6 6章章 多维数组和广义表 多维数组和广义表可以看作是线性表的推广，其特点是线性表中的数据元素仍然是一个表。知 识 点 多维数组的逻辑结构和存储结构多维数组的逻辑结构和存储结构 特殊矩阵的压缩存储特殊矩阵的压缩存储 稀疏矩阵的三元组存储、十字链表存储稀疏矩阵的三元组存储、十字链表存储 广义表的逻辑结构、存储结构及其基本算法广义表的逻辑结构、存储结构及其基本算法难难 点点要 求 6-1 6-1 多维数组多维数组 6-2 6-2 特殊矩阵的压缩存储特殊矩阵的压缩存储6-3 6-3 稀疏矩阵稀疏矩阵 6-4 6-4 广义表广义表 小小 结结验证性实验：验证性实验：稀疏矩阵和广义表子系统稀疏矩阵

2、和广义表子系统自主性实验自主性实验6 6：稀疏矩阵十字链表的存储：稀疏矩阵十字链表的存储 单元练习单元练习6 6.1.1 逻辑结构逻辑结构 数组作为一种数据结构，其特点是结构中的元素可以是数组作为一种数据结构，其特点是结构中的元素可以是具有某种结构的数据，但属于同一数据类型。比如，一维数具有某种结构的数据，但属于同一数据类型。比如，一维数组可以看作一个线性表，二维数组可以看作组可以看作一个线性表，二维数组可以看作“数据元素是一数据元素是一维数组维数组”的一维数组，三维数组可以看作的一维数组，三维数组可以看作“数据元素是二维数据元素是二维数组数组”的一维数组。一般把三维以上的数组称为多维数组，的

3、一维数组。一般把三维以上的数组称为多维数组，n维的多维数组可以视为维的多维数组可以视为n 1维数组元素组成的线性结构。其维数组元素组成的线性结构。其中每一个一维数组又由中每一个一维数组又由m个单元组成。个单元组成。图图6-1是一个是一个n行行m列的数组。列的数组。在二维数组中的每一个元素最多可以有两个直接前驱在二维数组中的每一个元素最多可以有两个直接前驱和两个直接后继（边界除外），在和两个直接后继（边界除外），在n维数组中的每一个元素维数组中的每一个元素最多可以有最多可以有n个直接前驱和个直接前驱和n个直接后继。所以多维数组是个直接后继。所以多维数组是一种非线性结构。一种非线性结构。数组是一个

4、具有固定格式和数量的数据有序集，每一数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，通常在很多高级语言个数据元素有唯一的一组下标来标识，通常在很多高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。因中数组一旦被定义，每一维的大小及上下界都不能改变。因此，在数组上一般不做插入或删除数据元素的操作。在数组此，在数组上一般不做插入或删除数据元素的操作。在数组中经常做的两种操作如下。中经常做的两种操作如下。（1）取值操作：给定一组下标，读取其对应的数据元素。）取值操作：给定一组下标，读取其对应的数据元素。（2）赋值操作：给定一组下标，存储或修改与其相对应的）赋值

5、操作：给定一组下标，存储或修改与其相对应的数据元素。数据元素。6.1.2 存储结构存储结构 通常，数组在内存被映象为向量，即用向量作为数组的一种存通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为在计算机内存储结构是一维的。数组的行列固储结构，这是因为在计算机内存储结构是一维的。数组的行列固定后，通过一个映象函数，就可以根据数组元素的下标得到它的定后，通过一个映象函数，就可以根据数组元素的下标得到它的存储地址。对于一维数组只要按下标顺序分配即可；存储地址。对于一维数组只要按下标顺序分配即可；对多维数组对多维数组分配时，要把它的元素映象存储在一维存储器中。分配时，要把它的元素

6、映象存储在一维存储器中。1存储方式存储方式（1）以行为主（）以行为主（row major order）以行为主的存储方式也称为按行优先顺序方式，实现时按行号以行为主的存储方式也称为按行优先顺序方式，实现时按行号从小到大的顺序，先存储第从小到大的顺序，先存储第0行的全部元素，再存放第行的全部元素，再存放第1行的元素、行的元素、第第2行的元素行的元素 一个一个23二维数组的逻辑结构如图二维数组的逻辑结构如图6-2所示，以行为主的内存所示，以行为主的内存映象如图映象如图6-3（a）所示，其分配顺序为：）所示，其分配顺序为：a00，a01，a02，a10，a11，a12。以行为主序的分配规律是：最右边

7、的下标先变化，即最右下标以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变从小到大，循环一遍后，右边第二个下标再变，从右向左，从右向左，最后是左下标。最后是左下标。（2）以列为主序（）以列为主序（column major order）以列为主的存储方式也称为按列优先顺序方式，实现时按列号以列为主的存储方式也称为按列优先顺序方式，实现时按列号从小到大的顺序，先存储第从小到大的顺序，先存储第0列的全部元素，再存储第列的全部元素，再存储第1列的元素、列的元素、第第2 列的元素列的元素 图图6-2所示的逻辑结构，以列为主的内存映象如图所示的逻辑结构，以列为主

8、的内存映象如图6-3（b）所示，）所示，其分配顺序为：其分配顺序为：a00，a10，a01，a11，a02，a12。以列为主分配的规律恰好与以行为主次序相反：最左边的下标以列为主分配的规律恰好与以行为主次序相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变变，从左向右，最后是右下标。，从左向右，最后是右下标。2存储地址存储地址“以行为主以行为主”次序分配存储单元为例看其地址的计算次序分配存储单元为例看其地址的计算（1）二维数组中）二维数组中aij的地址的地址 在在C语言中数组中每一维的下界定义为语言中数组中每一维

9、的下界定义为0，数组的基址为，数组的基址为LOC(a00)，每个数组元素占据，每个数组元素占据d个字节，那么个字节，那么aij 的物理地址的物理地址可用一个线性寻址函数计算：可用一个线性寻址函数计算：LOC(aij)=LOC(a00)+(in+j)d （0下标起始的语言）下标起始的语言）（2）三维数组中）三维数组中aijk的地址的地址 同理对于三维数组元素同理对于三维数组元素aijk的物理地址为：的物理地址为：LOC(aijk)=LOC(a000)+(inp+jp+k)d （0下标起始的语言）下标起始的语言）【例【例6-1】设二维数组设二维数组A56，每个元素占，每个元素占4个字节（个字节（B

10、yte），存储），存储器按字节编址。已知器按字节编址。已知A的起始地址为的起始地址为2000。计算。计算（1）数组的大小）数组的大小 nmd=564=120 Byte（2）数组结点）数组结点a45的存储地址的存储地址 LOC(aij)=LOC(a00)+(i*n+j)*d /n为总列数为总列数 LOC(a45)=2000+(46+5)4=2116（3）按行为主存储，计算）按行为主存储，计算a32的存储地址的存储地址 LOC(aij)=LOC(a00)+(i*n+j)*d /n为总列数为总列数 LOC(a32)=2000+(36+2)4=2080（4）按列为主存储，计算）按列为主存储，计算a32

11、的存储地址的存储地址 LOC(aij)=LOC(a00)+(j*m+i)*d /m为总行数为总行数 LOC(a32)=2000+(25+3)4=2052 【例【例6-2】若矩阵若矩阵A An nm m 中存在某个元素中存在某个元素a aijij，满足：，满足：a aijij是第是第i i行中最小行中最小值且是第值且是第j j列中的最大值，则称该元素为矩阵列中的最大值，则称该元素为矩阵A A的一个鞍点。试编写的一个鞍点。试编写一个算法，找出一个算法，找出A A中的所有鞍点。中的所有鞍点。基本思想：在矩阵基本思想：在矩阵A A中求出每一行的最小值元素，然后判断该元素是中求出每一行的最小值元素，然后

12、判断该元素是否是它所在列中的最大值。如果是则打印输出，接着处理下一行。否是它所在列中的最大值。如果是则打印输出，接着处理下一行。设矩阵设矩阵A A用一个二维数组表示，其算法如下：用一个二维数组表示，其算法如下：void saddle(int A,int n,int m)int i,j,min;for(i=0;in;i+)/按行处理按行处理 min=Ai0 for(j=1;jm;j+)if(Aijmin)min=Aij;/找第找第i行最小值行最小值 for(j=0;jm;j+)/检测最小值是否是鞍点检测最小值是否是鞍点 if(Aij=min)k=j;p=0;while(pn&Apj=n)prin

13、tf(%d,%d,%dn,i,k,min);算法的时间复杂度为算法的时间复杂度为O O(n n(m m+n mn m)。矩阵是一个二维数组，是众多科学与工程计矩阵是一个二维数组，是众多科学与工程计算问题中研究的数学对象。在矩阵中非零元素或算问题中研究的数学对象。在矩阵中非零元素或零元素的分布有一定规律的矩阵称为特殊矩阵，零元素的分布有一定规律的矩阵称为特殊矩阵，如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等。如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等。当矩阵的阶数很大时，用普通的二维数组存储这当矩阵的阶数很大时，用普通的二维数组存储这些特殊矩阵将会占用很多的存储单元。从节约存些特殊矩阵将会占用很多

14、的存储单元。从节约存储空间的角度考虑，下面来考虑这些特殊矩阵的储空间的角度考虑，下面来考虑这些特殊矩阵的存储方法。存储方法。6.2.1 对称矩阵对称矩阵 对称矩阵是一种特殊矩阵，对称矩阵是一种特殊矩阵，n阶方阵的元素满足性质：阶方阵的元素满足性质：aij=aji（0=i,j=n 1）。）。如图如图6-4所示是一个阶对称矩阵。对称矩阵是关于主所示是一个阶对称矩阵。对称矩阵是关于主对角线的对称，因此只需存储上三角或下三角部分的数据对角线的对称，因此只需存储上三角或下三角部分的数据即可。比如，只存储下三角中的元素即可。比如，只存储下三角中的元素aij，其特点是中，其特点是中j=i且且0=i=n 1，

15、对于上三角中的元素，对于上三角中的元素aij，它和对应的，它和对应的aji相等，相等，因此当访问的元素在上三角时，直接去访问和它对应的下因此当访问的元素在上三角时，直接去访问和它对应的下三角元素即可，这样，原来需要三角元素即可，这样，原来需要n n个存储单元，现在只需个存储单元，现在只需要要n(n+1)/2个存储单元了，节约了个存储单元了，节约了n(n 1)/2个存储单元。个存储单元。图图6-4 5阶对称方阵及它的压缩存储阶对称方阵及它的压缩存储 如何只存储下三角部分呢？将下三角部分以行序为主序如何只存储下三角部分呢？将下三角部分以行序为主序顺序存储到一个向量顺序存储到一个向量SA中去。在下三

16、角中共有中去。在下三角中共有n(n+1)/2个元个元素，存储到一个向量空间素，存储到一个向量空间SA0至至SAn(n+1)/2-1中，存储顺中，存储顺序可用图序可用图6-5示意。示意。图图6-5 6-5 对称矩阵下三角压缩存储对称矩阵下三角压缩存储 原矩阵下三角中的某一个元素原矩阵下三角中的某一个元素aij具体对应一个具体对应一个sasak k，用，用“以行优先以行优先”存放下三角部分的元素时，存放下三角部分的元素时，a00存入存入sa0，a10存存入入sa1，a11存入存入sa2。sasak k与与aij的一一对应关系为：的一一对应关系为：k=j(j+1)/2+i （0=k n(n+1)/2

17、 1）当当ij时，在下三角部分时，在下三角部分aij前有前有i行，共有行，共有1+2+3+i个元素，个元素，而而aij是第是第i行的第行的第j个元素，即有个元素，即有k=1+2+3+i+j=i(i+1)/2+j。当当ij时，时，aij是上三角中的元素，因为是上三角中的元素，因为aij=aji，这样，访，这样，访问上三角中的元素问上三角中的元素aij时则去访问和它对应的下三角中的时则去访问和它对应的下三角中的aji即即可，因此将上式中的行列下标交换就是上三角中的元素在可，因此将上式中的行列下标交换就是上三角中的元素在SA中的对应关系：中的对应关系：k=j(j+1)/2+i （0=krow=m;H

18、-row=m;H-col H-col=n;=n;hd0=H;hd0=H;for(i=1;iS;i+)for(i=1;irow=0;p-colp-row=0;p-col=0;=0;p-right=p;p-down=p;p-right=p;p-down=p;hdi hdi=p;hdi-1-v_next.next=p;=p;hdi-1-v_next.next=p;hdShdS-v_next.next=H;-v_next.next=H;/将头结点们形成循环链表将头结点们形成循环链表 for(k=1;k=t;k+)for(k=1;krow=i;p-col p-row=i;p-col=j;p-v_next

19、.v=v=j;p-v_next.v=v q=hdi q=hdi;while(q-right!=hdi&(q-right-col while(q-right!=hdi&(q-right-col)j)/)right;q=q-right;p-right=q-right;/p-right=q-right;/插入插入 q-right=p;q=hdiq-right=p;q=hdi;while(q-down!=hdj&(q while(q-down!=hdj&(q-down-row)down-row)down;q=q-down;p-down=q-down;p-down=q-down;/插入插入 q-down

20、=p;q-down=p;return H;return H;上述算法中，建立头结点循环链表时间复杂度为上述算法中，建立头结点循环链表时间复杂度为O O(S S)，插入每个结点到相应的行表和列表的时间复杂度，插入每个结点到相应的行表和列表的时间复杂度是是O O(t t S S)，这是因为每个结点插入时都要在链表中寻找，这是因为每个结点插入时都要在链表中寻找插入位置，所以总的时间复杂度为插入位置，所以总的时间复杂度为O O(t t S S)。该算法对三。该算法对三元组的输入顺序没有要求。如果我们输入三元组时是按元组的输入顺序没有要求。如果我们输入三元组时是按以行为主序（或列）输入的，则每次将新结点

21、插入到链以行为主序（或列）输入的，则每次将新结点插入到链表的尾部的，改进算法后，时间复杂度为表的尾部的，改进算法后，时间复杂度为O O(S S+t t)。2 2稀疏矩阵的加法稀疏矩阵的加法 已知两个十字链表存储的稀疏矩阵已知两个十字链表存储的稀疏矩阵A A和和B B，计算，计算C C=A A+B B，C C也采用十字链表方式存储，并且在也采用十字链表方式存储，并且在A A的基础上形成的基础上形成C C。由矩阵的加法规则知，只有由矩阵的加法规则知，只有A A和和B B行列对应相等，二者才行列对应相等，二者才能相加。能相加。C C中的非零元素中的非零元素c cijij只可能有只可能有3 3种情况：

22、或者是种情况：或者是a aijij+b bijij，或者是或者是a aijij（b bijij=0=0），或者是），或者是b bijij（a aijij=0=0），因此当），因此当B B加到加到A A上上时，对时，对A A十字链表的当前结点来说，对应下列四种情况：或十字链表的当前结点来说，对应下列四种情况：或者改变结点的值（者改变结点的值（a aijij+b bijij00），或者不变（），或者不变（b bijij 0 0），或者），或者插入一个新结点（插入一个新结点（a ai ji j 0 0），还可能是删除一个结点），还可能是删除一个结点（a aijij+b bijij 0 0）。整个运算

23、从矩阵的第一行起逐行进行。对每）。整个运算从矩阵的第一行起逐行进行。对每一行都从行表的头结点出发，分别找到一行都从行表的头结点出发，分别找到A A和和B B在该行中的第一在该行中的第一个非零元素结点后开始比较，然后按个非零元素结点后开始比较，然后按4 4种不同情况分别处理。种不同情况分别处理。设设papa和和pbpb分别指向分别指向A A和和B B的十字链表中行号相同的两个结点，的十字链表中行号相同的两个结点，4 4种情况如下：种情况如下：（1 1）若）若pa-col=pb-colpa-col=pb-col且且pa-pa-v v+pb+pb-v v0 0，则只要用，则只要用a aijij+b

24、bijij的的值改写值改写papa所指结点的值域即可。所指结点的值域即可。（2 2）若）若pa-col=pb-colpa-col=pb-col且且pa-pa-v v+pb+pb-v v=0=0，则需要在矩阵，则需要在矩阵A A的的十字链表中删除十字链表中删除papa所指结点，此时需改变该行链表中前趋结点所指结点，此时需改变该行链表中前趋结点的的rightright域，以及该列链表中前趋结点的域，以及该列链表中前趋结点的downdown域。域。（3 3）若）若pa-col colpa-col col且且pa-colpa-col0 0（即不是表头结点），（即不是表头结点），则只需要将则只需要将pa

25、pa指针向右推进一步，并继续进行比较。（指针向右推进一步，并继续进行比较。（4 4）若若pa-col pb-colpa-col pb-col或或pa-colpa-col 0 0（即是表头结点），则需要在（即是表头结点），则需要在矩阵矩阵A A的十字链表中插入一个的十字链表中插入一个pbpb所指结点。所指结点。由前面建立十字链表算法知，总表头结点的行列域存放的是由前面建立十字链表算法知，总表头结点的行列域存放的是矩阵的行和列，而各行（列）链表的头结点其行列域值为零，矩阵的行和列，而各行（列）链表的头结点其行列域值为零，当然各非零元素结点的行列域其值不会为零，下面分析的当然各非零元素结点的行列域其

26、值不会为零，下面分析的4 4种情种情况利用了这些信息来判断是否为表头结点。况利用了这些信息来判断是否为表头结点。MLink AddMat(Ha,Hb)MLink Ha,Hb;Mnode *p,*q,*pa,*pb,*ca,*cb,*qa;if(Ha-row!=Hb-row|Ha-col!=Hb-col)return NULL;ca=Ha-v_next.next;/ca初始指向初始指向A矩阵中第一行表头结点矩阵中第一行表头结点 cb=Hb-v_next.next;/cb初始指向初始指向B矩阵中第一行表头结点矩阵中第一行表头结点 do pa=ca-right;/pa指向指向A矩阵当前行中第一个结点

27、矩阵当前行中第一个结点 qa=ca;/qa是是pa的前驱的前驱 pb=cb-right;/pb指向指向B矩阵当前行中第一个结点矩阵当前行中第一个结点 while(pb-col!=0)/当前行没有处理完当前行没有处理完 if(pa-colcol&pa-col!=0)qa=pa;pa=pa-right;else if(pa-colpb-col|pa-col=0)p=new MNode;p-row=pb-row;p-col=pb-col;p-v=pb-v;p-right=pa;qa-right=p;/新结点插入新结点插入*pa的前面的前面 pa=p;/新结点还要插到列链表的合适位置，先找位置，再插入

28、新结点还要插到列链表的合适位置，先找位置，再插入 q=F i n d _ J H(H a,p-c o l);/从列链表的头结点找起从列链表的头结点找起 while(q-down-row!=0&q-down-rowrow)q=q-down;p-down=q-down;/插在插在*q的后面的后面 q-down=p;pb=pb-right;else /第一、二种情况第一、二种情况 x=pa-v_next.v+pb-v_next.v;if(x=0)/第二种情况第二种情况 qa-right=pa-right;/从行链中删除，从行链中删除，/要从列链中删除，找要从列链中删除，找*pa的列前驱结点的列前驱结

29、点 q=Find_JH(Ha,pa-col);/从列链表的头结点找起从列链表的头结点找起 while(q-down-row row)q=q-down;q-down=pa-down;delete pa;pa=qa;else /第一种情况第一种情况 pa-v_next.v=x;qa=pa;pa=pa-right;pb=pb-right;ca=ca-v_next.next;/ca指向指向A中下一行的表头结点中下一行的表头结点 cb=cb-v_next.next;/cb指向指向B中下一行的表头结点中下一行的表头结点 while(ca-row=0)/当还有未处理完的行则继续当还有未处理完的行则继续 re

30、turn Ha;为了保持算法的层次，在上面的算法中用到了一个函数为了保持算法的层次，在上面的算法中用到了一个函数Find_JH()Find_JH()，其功能是：返回十字链表，其功能是：返回十字链表H H中第中第j j列链表的头结点指针。列链表的头结点指针。3 3 矩阵的转矩阵的转置置 设设SPMatrix A;表示一表示一m m*n n的稀疏矩阵，其转置的稀疏矩阵，其转置B B则是一个则是一个n n*m m的的稀疏矩阵，因此也有稀疏矩阵，因此也有SPMatrix B;由稀疏矩阵由稀疏矩阵A A求它的转置求它的转置B B只要将只要将A A的的行、列转化成行、列转化成B B的列、行。的列、行。将将

31、A.dataA.data中每一三元组的行列交换后转化到中每一三元组的行列交换后转化到B.dataB.data后，似乎已完后，似乎已完成了转置，其实不然。成了转置，其实不然。A A的转置的转置B B如图如图6.156.15所示，图所示，图6.166.16是它对应的三是它对应的三元组存储。也就是说，在元组存储。也就是说，在A A的三元组存储基础上得到的三元组存储基础上得到B B的三元组表存储。的三元组表存储。转置算法的实质是将矩阵转置算法的实质是将矩阵A A的行和列转化成矩阵的行和列转化成矩阵B B的列和行。的列和行。sparmatrix Trans(sparmatrixsparmatrix Tr

32、ans(sparmatrix A)/A)/调用稀疏矩阵调用稀疏矩阵A A sparmatrix sparmatrix B;/B;/定义稀疏矩阵定义稀疏矩阵B B B.rows=A.cols;B.rows=A.cols;B.cols=A.rows;B.cols=A.rows;B.terms=A.terms;B.terms=A.terms;for(int for(int n=0;n=A.terms-1;n+)n=0;ntag=0;-tag=0;gh gh-node.data=-node.data=*s;s;gh gh-link=NULL;-link=NULL;elseelse gh=new lin

33、knode gh=new linknode;gh gh-tag=1;-tag=1;p=gh p=gh;s+;s+;strncpy(subs,s,len-2);strncpy(subs,s,len-2);subslen-2=0;subslen-2=0;dodo Disastr(subs,hstr Disastr(subs,hstr););r=CreateGL(hstr r=CreateGL(hstr););p-node.sublist p-node.sublist=r;=r;q=p;q=p;len=strlen(subs len=strlen(subs););if(len if(len0)0)p

34、=new linknode p=new linknode;p-tag=1;p-tag=1;q-link=p;q-link=p;while(len while(len0);0);q-link=NULL;q-link=NULL;return gh return gh;创建广义表创建广义表算法的时间复杂度为算法的时间复杂度为O(n)O(n)。2 2广义表取头算法广义表取头算法 若广义表若广义表GL=GL=（a1，a2，an），则，则head（GL）=a1。取表头运算的结果可以是原子，也可以是一个子表。取表头运算的结果可以是原子，也可以是一个子表。例如，例如，head（a1，a2），（），（a3，a4

35、，a5），），a6）=（a1，a2）。）。Head(linknodeHead(linknode *GL)GL)if GL-tag=1 if GL-tag=1 p=GL-hp;p=GL-hp;return p;return p;3.3.广义表取尾算法广义表取尾算法 若广义表若广义表GL=GL=（a1，a2，an），则，则tail（GL）=（a2，an）。取表尾运算的结果是取出除表头以外的所有。取表尾运算的结果是取出除表头以外的所有元素。元素。例如，例如，tail（a1，a2），（），（a3，a4，a5），），a6）=（a3，a4，a5），），a6）。）。Tail(linknodeTail(lin

36、knode *GL)GL)if GL-tag=1 if GL-tag=1 p=GL-tp p=GL-tp;return p;return p;4.4.求广义表深度算法求广义表深度算法int Depth(linknodeint Depth(linknode *GL)GL)int int max=0;max=0;while(GL!=NULL)while(GL!=NULL)if(GL-tag=0)if(GL-tag=0)/有子表有子表 int dep=Depth(GL-sublit int dep=Depth(GL-sublit)if(dep if(depmax)max)max=dep max=de

37、p;GL=GL-link;GL=GL-link;return max+1;return max+1;/非空表的深度是各元素的深度的最大值加非空表的深度是各元素的深度的最大值加1 1 求广义表深度算法的时间复杂度为求广义表深度算法的时间复杂度为O(n)O(n)。（1）数组是一个具有固定格式和数量的数据有序集，每一个数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，在数组上不太适宜做插数据元素有唯一的一组下标来标识，在数组上不太适宜做插入、删除数据元素的操作。入、删除数据元素的操作。（2 2）二维数组中）二维数组中aij的地址为：的地址为：LOC(aij)=LOC(a

38、00)+(in+j)d（0下标起始的语下标起始的语言）言）（3）三）三维数组中维数组中aijk的地址为：的地址为：LOC(aijk)=LOC(a000)+(inp+jp+k)d （0下标下标起始的语言）起始的语言）（4）对称矩阵是一种特殊矩阵，）对称矩阵是一种特殊矩阵，n阶方阵的元素满足性质：阶方阵的元素满足性质：aij=aji（0i,jn-1）。对称矩阵是关于主对角线的对称，）。对称矩阵是关于主对角线的对称，因此只需存储上三角或下三角部分的数据即可。因此只需存储上三角或下三角部分的数据即可。（5）三角矩阵的特殊性是以主对角线划分矩阵。主对角线任意）三角矩阵的特殊性是以主对角线划分矩阵。主对角

39、线任意一侧（不包括主对角线中）的元素均为常数（一侧（不包括主对角线中）的元素均为常数（C）。下三角矩阵，）。下三角矩阵，主对角线以上均为同一个常数；上三角矩阵，主对角线以下均为主对角线以上均为同一个常数；上三角矩阵，主对角线以下均为同一个常数，均可以采用压缩存储。同一个常数，均可以采用压缩存储。（6 6）在）在m m*n n的矩阵中有的矩阵中有t t个非零元素，且个非零元素，且t t远小于远小于m m*n n，这样的矩，这样的矩阵称稀疏矩阵。稀疏矩阵常用的有：阵称稀疏矩阵。稀疏矩阵常用的有：三元组表存储三元组表存储、带行指针的、带行指针的链表存储、十字链表存储等存储方法。链表存储、十字链表存储

40、等存储方法。（7）广义表是广义表是n（n0）个数据元素的有序序列，广义表的元素）个数据元素的有序序列，广义表的元素可以是单元素，也可以是一个广义表。可以是单元素，也可以是一个广义表。（8）由于广义表的元素有两种形式，所以其结点的存储形式也由于广义表的元素有两种形式，所以其结点的存储形式也有两种：表结点由标志域、表头指针域、表尾指针域组成；而原有两种：表结点由标志域、表头指针域、表尾指针域组成；而原子结点由标志域和值域组成。子结点由标志域和值域组成。1 1实验目的实验目的 （1 1）掌握稀疏矩阵三元组表的存储方法。掌握稀疏矩阵三元组表的存储方法。（2 2）掌握稀疏矩阵三元组表创建、显示、转置和查

41、找等算法。）掌握稀疏矩阵三元组表创建、显示、转置和查找等算法。（3 3）掌握广义表的存储方法。）掌握广义表的存储方法。（4 4）掌握广义表的新建、显示和查找等算法。）掌握广义表的新建、显示和查找等算法。（5 5）掌握稀疏矩阵三元组表和广义表的算法分析方法。）掌握稀疏矩阵三元组表和广义表的算法分析方法。2 2实验内容实验内容 （1 1）编写稀疏矩阵三元组表的存储程序；）编写稀疏矩阵三元组表的存储程序；（2 2）编写疏矩阵三元组表创建、显示、转置和查找程序；）编写疏矩阵三元组表创建、显示、转置和查找程序；（3 3）编写建立广义表的程序；）编写建立广义表的程序；（4 4）编写广义表的显示和查找程序；

42、）编写广义表的显示和查找程序；（5 5）设计选择式菜单，其一级菜单形式如下：）设计选择式菜单，其一级菜单形式如下：稀疏矩阵和广义表子系统稀疏矩阵和广义表子系统*1-1-稀稀 疏疏 矩矩 阵阵 *2-2-广广 义义 表表 *0-0-退退 出出 *请输入菜单号（请输入菜单号（0-20-2）:稀疏矩阵二级菜单稀疏矩阵二级菜单形式如下：形式如下：稀疏矩阵的三元组存储稀疏矩阵的三元组存储*1-1-新新 建建 *2-2-转转 置置 *3-3-查查 找找 *4-4-显显 示示 *0-0-返返 回回 *请输入菜单号（请输入菜单号（0-40-4）:广义表二级菜单广义表二级菜单形式如下：形式如下：广广 义义 表表

43、*1-1-新新 建建 *2-2-查查 找找 *3-3-显显 示示 *0-0-返返 回回 *请输入菜单号（请输入菜单号（0-30-3）:1实验目的实验目的（1）掌握稀疏矩阵十字链表存储的方法。）掌握稀疏矩阵十字链表存储的方法。（2）掌握稀疏矩阵的显示、查找等基本算法。）掌握稀疏矩阵的显示、查找等基本算法。2实验内容实验内容（1）创建空的稀疏矩阵的十字链表存储结构。）创建空的稀疏矩阵的十字链表存储结构。（2）稀疏矩阵十字链表的数据输入。）稀疏矩阵十字链表的数据输入。（3）稀疏矩阵十字链表的数据显示。）稀疏矩阵十字链表的数据显示。（4）稀疏矩阵十字链表的数据查找。）稀疏矩阵十字链表的数据查找。3实验要求实验要求（1）利用）利用C或或C+语言完成算法设计和程序设计。语言完成算法设计和程序设计。（2）上机调试通过实验程序。）上机调试通过实验程序。（3）输入下列矩阵）输入下列矩阵A，检验程序运行结果。，检验程序运行结果。（4）给出具体的算法分析，包括时间复杂度）给出具体的算法分析，包括时间复杂度和空间复杂度等。和空间复杂度等。（5）撰写实验报告。）撰写实验报告。