《数据结构》第6章数组特殊矩阵和广义表课件.ppt

1、王钢王钢 主编主编清华大学出版社清华大学出版社第6章 数组、特殊矩阵和广义表l数组的定义及其存储l特殊矩阵的压缩存储l稀疏矩阵逻辑结构和存储结构l广义表的逻辑结构和存储结构l数组和广义表的操作应用举例数组的定义及逻辑结构数组的定义及逻辑结构 数组数组是由下标和值组成的元素序列的集合。在数组中，一旦给定下标，都存在一个与其对应的值，这个值称为数组元素数组元素。在数组中通常做下面两种操作：l取值操作：给定一组下标，读其对应的数组元素。l赋值操作：给定一组下标，存储或修改与其相对应的数据元素。l例例6.1 若矩阵Amn 中存在某个元素aij满足：aij是第i行中最小值且第j 列中的最大值，则称该元素

2、为矩阵A的一个鞍点。试编写一个算法，找出A中所有的鞍点。l基本思路：在矩阵A中求出每一行的最小元素，然后判断该元素是否是它所在列中的最大值，若是则打印出，接着处理下一行。矩阵A用二维数组表示。算法如下：例题算法6.1 求矩阵鞍点算法void saddle(int A,int m,int n)/m,n是矩阵A的行和列int i,j,k,min;for(i=0;im;i+)min=Ai0;for(j=1;jn;j+)if(Aijmin)min=Aij;/找第i行最小值for(j=0;jn;j+)/检测该行中的每一个最小值是否是鞍点if(Aij=min)k=j;p=0;while(pm&Apj=m)

3、printf(%d%d%d,i,j,k);/if对称矩阵的压缩存储对称矩阵的压缩存储 1对称矩阵若一个n阶矩阵M 中满足下述性质：aij=aji 0i,jn1则称为n阶对称矩阵阶对称矩阵。例如A矩阵是一个5阶对称矩阵，如图6.5所示。2 3 5 2 93 6 6 3 85 6 2 7 32 3 7 8 49 8 3 4 1A=2对称矩阵的存储a0,0a1,0a1,1a2,0an-1,0an-1,n-1k值 n(n+1)/21 0 1 2 3第1行 第2行 第n行 图6.6 对称矩阵的压缩存储1三角矩阵8 2 3 4 5a 5 6 7 1a a 8 9 7a a a 1 0a a a a 8B=

4、8 0 0 0 02 5 0 0 03 6 8 0 04 7 9 1 05 1 7 0 8C=图6.7 上三角矩阵及下三角矩阵1带状矩阵00a0,0 a0,1 a0,2 0 0a1,0 a1,1 a1,2 a1,3 0a2,0 a2,1 a2,2 a2,3 a2,4 0 a3,1 a3,2 a3,3 a3,4 0 0 a4,2 a4,3 a4,4D=b条b条图6.8 带状矩阵 图6.9 半带宽为2的5阶带状矩阵 稀 疏 矩 阵 1 6 152 2 112 3 31 1 155 1 913 4 6ijv1A=15 300000 0 22 0 15 1100060000000091 0000000

5、0002341 4 225670图6.11 稀疏矩阵 图6.12 三元组表 三元组的类型定义：#define SMAX 1024 /最大非零元素个数typedef struct int i,j;/非零所在行、列 Elemtype v;/非零元素的值SPNode;/存储非零元素的三元组结构体类型typedef struct int mu,nu,tu;/矩阵的行、列及非零元素的实际个数SPNode dataSMAX;/三元组表SPMatrix;/稀疏矩阵的三元组表存储类型稀疏矩阵的转置 1 5 911 2 113 2 34 1 221 1 156 1 154 3 6ijv1234567B=15 0

6、 0 0 91 00 0 0 0 0 0 0 11 0 0 0 00 3 0 0 0 015 0 0 0 0 022 0 6 0 0 0 图6.13 A的转置B 图6.14 B 的三元组 算法思路：A的行、列转化成B的列、行；在A.data中依次找第一列的、第二列的、直到最后一列，并将找到的每个三元组的行、列交换后顺序存储到B.data中即可。算法6.2 稀疏矩阵的转置算法SPMatrix *TransM1(SPMatrix *A)SPMatrix*B;int p,q,col;B=(SPMatrix *)malloc(sizeof(SPMatrix);B-mu=A-nu;B-nu=A-mu;B

7、-tu=A-tu;if(B-tu0)q=1;for(col=1;colnu);col+)/按A的列序转换for(p=1;ptu);p+)/扫描整个三元组表 if(A-datap.j=col)B-dataq.i=A-datap.j;B-dataq.j=A-dataq.i;B-dataq.v=A-datap.v;q+;/if/if(b-tu0)return B;/返回转置后矩阵的指针/TransM1稀疏矩阵的乘积 稀疏矩阵的乘法运算的粗略步骤如下：(1)初始化。清理一些单元，准备按行顺序存放乘积矩阵。(2)求B的num，rpot。(3)做矩阵乘法。将A.data中三元组的列值与B.data中三元组

8、的行值相等的非零元素相乘，并将具有相同下标的乘积元素相加。算法6.3 稀疏矩阵的乘积算法 SPMatrix *MulSMatrix(SPMatrix *A,SPMatrix *B)/稀疏矩阵A(m1n1)和B(m2n2)用三元组表存储,求ABSPMatrix *C;/乘积矩阵的指针int p,q,i,j,k,r;Elemtype tempn+1;int numB-nu+1,rpotB-nu+1;if(A-nu!=B-mu)return NULL;/A的列与B的行不相等C=(SPMatrix *)malloc(sizeof(SPMatrix);/申请C的存储空间C-mu=A-mu;C-nu=A-

9、nu;if(A-tu*B-tu=0)C-tu=0;return C;for(i=1;imu;i+)num i=0;/求矩阵B中每一行非零元素的个数for(k=1;ktu;k+)i=B-datak.i;num i+;rpot 1=1;/求矩阵B中每一行第一个非零元素在B.data中的位置for(i=2;imu;i+)rpot i=rpot i-1+num i-1;r=0;/当前C中非零元素的位置p=1;for(i=1;imu;i+)for(j=1;jnu;j+)temp j=0;/C累加器初始化while(A-datap.i=i)k=A-datap.j;if(kmu)t=rpot k+1;els

10、et=B-tu+1;/确定B中第k行的非零元素在B.data中下限位置for(q=rpotk;qdata q.j;temp j+=A-data p.v*B-data q.v;p+;/whilefor(j=1;jnu;j+)if(temp j )r+;C-data r=i,j,temp j ;/for iC-tu=r;return C;/MulSMtrix广义表的概念和特性 1。定义：广义表。定义：广义表是n(n0)个元素有限序列，记作A=(a1,a2,a3,an)其中，A是广义表的名称，n是它的长度，ai(1in)或者是数据元素，或者是广义表。显然广义表的定义是一个递归的定义，即广义表中可以包

11、含广义表。2。举例(1)A=()，A是一个空表，其长度为零。(2)B=(e)，表B只有一个原子e，B的长度为1。(3)C=(a,(b,c,d)，表C的长度为2，两个元素分别为原子 a和子表(b,c,d)。(4)D=(A,B,C)，列表D的长度为3，3个元素都是列表。(5)E=(a,E)，这是一个递归的表，其长度为2，E是相当于一个无穷表。1头尾表示法 tag=0datatag=1hptp表结点原子结点 图6.18 头尾表示法的结点形式2孩子兄弟表示法 tag=1 hp tp tag=0 data tp 图6.20 孩子兄弟表示法的结点形式1广义表的基本运算lCreat(LS)：根据广义表的书写

12、形式创建一个广义表LS。lIsEmpty(LS)：若广义表LS为空，则返回True；否则返回False。lLength(LS)：求广义表的长度。lDepth(LS)：求广义表的深度。lLocate(LS,x)：在广义表LS上查找数据元素x。lMerage(LS1，LS2)：复制广义表，即按照LS1建立广义表LS2。lHead(LS)：返回广义表的头部。lTail(LS)：返回广义表的尾部。2广义表运算的实现算法6.4 广义表的取头算法Glist Head(Glist*ls)GLNode*p;p=NULL;if(ls-tag)p=ls-hp;return p;算法6.5 广义表的取尾算法Glis

13、t Tail(Glist ls)GLNode*p;p=NULL;if(ls-tag)p=ls-tp;return p;算法6.6 建立广义表的存储结构的算法int Create(Glist ls,char*s)GLNode*p,*q;char*sub,hsub;if(StrEmpty(s)*ls=NULL;else(*ls)=(GLNode *)malloc(sizeof(GLNode);if(!(*ls)return 0;if(Strlength(s)=1)(*ls)-tag=0;(*ls)-data=s;else(*ls)-tag=1;p=*ls;hsub=SubStr(s,2,StrLe

14、ngth(s)-2);do sever(sub,hsub);Create(&(p-ptr.hp),sub);q=p;if(!StrEmpty(sub)p=(GLNode *)malloc(sizeof(GLNode);if(!p)return 0;p-tag=1;q-ptr.tp=p;while(!StrEmpty(sub);q-ptr.tp=NULL;return 1;int sever(char*str,char*hstr)int i,k,n;char ch;n=StrLength(str);i=1;k=0;for(i=1,k=0;i=n|k!=0;+i)ch=SubStr(str,i,1

15、);if(ch=()+k;else if(ch=)-k;if(itag=1;(*ls)-hp=ls1;(*ls)-tp=ls2;return 1;算法6.8 求广义表的深度算法int Depth(Glist ls)in dep,max;Glist p;if(!ls)return 1;/空表深度为1if(ls-tag=0)return 0;/单元素深度为0for(max=0,p=ls;p;p=p-ptr.tp)dep=Depth(p-ptr.hp);/求以p-ptr.hp尾头指针的子表深度if(depmax)max=dep;return max+1;/非空表的深度是各元素的深度的最大值加1算法6

16、.9 复制广义表算法int CopyGlist(Glist ls1,Glist*ls2)if(!ls1)(*ls2)=NULL;else(*ls2)=malloc(sizeof(GLNode);if(!(*ls2)return 0;/建表头结点(*ls2)-tag=ls1-tag;if(ls1-tag=0)(*ls2)-data=ls1-data;/复制单元素elseCopyGList(&(*ls2)-ptr.hp),ls1-ptr.hp);/复制广义表ls1-ptr.hp的一个副本CopyGList(&(*ls2)-ptr.tp),ls1-ptr.tp);/复制广义表ls1-ptr.tp的一个副本return 1;