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

王钢主编清华大学出版社数据结构王钢主编数据结构1第6章数组、特殊矩阵和广义表数组的定义及其存储特殊矩阵的压缩存储稀疏矩阵逻辑结构和存储结构广义表的逻辑结构和存储结构数组和广义表的操作应用举例第6章数组、特殊矩阵和广义表数组的定义及其存储2数组的定义及逻辑结构

数组是由下标和值组成的元素序列的集合。在数组中，一旦给定下标，都存在一个与其对应的值，这个值称为数组元素。在数组中通常做下面两种操作：取值操作：给定一组下标，读其对应的数组元素。赋值操作：给定一组下标，存储或修改与其相对应的数据元素。数组的定义及逻辑结构数组是由下标和值组成的元素序列的集合。3例6.1若矩阵Am×n中存在某个元素aij满足：aij是第i行中最小值且第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中所有的鞍点。基本思路：在矩阵A中求出每一行的最小元素，然后判断该元素是否是它所在列中的最大值，若是则打印出，接着处理下一行。矩阵A用二维数组表示。算法如下：例题例6.1若矩阵Am×n中存在某个元素aij满足：aij4[算法6.1]求矩阵鞍点算法voidsaddle(intA[][],intm,intn){//m,n是矩阵A的行和列inti,j,k,min;for(i=0;i<m;i++){min=A[i][0];for(j=1;j<n;j++)if(A[i][j]<min)min=A[i][j];//找第i行最小值for(j=0;j<n;j++)//检测该行中的每一个最小值是否是鞍点if(A[i][j]==min){k=j;p=0;while(p<m&&A[p][j]<=min)p++;if(p>=m)printf("%d%d%d",i,j,k);}//if}}[算法6.1]求矩阵鞍点算法5对称矩阵的压缩存储

1．对称矩阵若一个n阶矩阵M中满足下述性质：aij=aji0≤i,j≤n–1则称为n阶对称矩阵。例如A矩阵是一个5阶对称矩阵，如图6.5所示。2352936638562732378498341A=对称矩阵的压缩存储1．对称矩阵23529362．对称矩阵的存储a0,0a1,0a1,1a2,0…an-1,0an-1,n-1k值n(n+1)/2–10123第1行第2行第n行图6.6对称矩阵的压缩存储2．对称矩阵的存储a0,0a1,0a1,1a2,0…an-171．三角矩阵

82345a5671aa897aaa10aaaa8B=8000025000368004791051708C=图6.7上三角矩阵及下三角矩阵1．三角矩阵

82345a56781．带状矩阵00a0,0a0,1a0,200a1,0a1,1a1,2a1,30a2,0a2,1a2,2a2,3a2,4

0a3,1a3,2a3,3a3,4

00a4,2a4,3a4,4D=b条b条图6.8带状矩阵图6.9半带宽为2的5阶带状矩阵1．带状矩阵00a0,0a0,1a0,209稀疏矩阵

16–15221123311155191346ijv1A=153000000220–151100060000000091000000000023414225670图6.11稀疏矩阵图6.12三元组表稀疏矩阵16–15221110三元组的类型定义：#defineSMAX1024//最大非零元素个数typedefstruct{inti,j;//非零所在行、列

Elemtypev;//非零元素的值}SPNode;//存储非零元素的三元组结构体类型typedefstruct{intmu,nu,tu;//矩阵的行、列及非零元素的实际个数SPNodedata[SMAX];//三元组表}SPMatrix;//稀疏矩阵的三元组表存储类型三元组的类型定义：11稀疏矩阵的转置159112113234122111561–15436ijv1234567B=150009100000000110000030000–15000002206000图6.13A的转置B图6.14B的三元组算法思路：①A的行、列转化成B的列、行；②在A.data中依次找第一列的、第二列的、直到最后一列，并将找到的每个三元组的行、列交换后顺序存储到B.data中即可。稀疏矩阵的转算法6.2]稀疏矩阵的转置算法SPMatrix*TransM1(SPMatrix*A){SPMatrix*B;intp,q,col;B=(SPMatrix*)malloc(sizeof(SPMatrix));B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;if(B->tu>0){q=1;for(col=1;col<=(A->nu);col++)//按A的列序转换for(p=1;p<=(A->tu);p++)//扫描整个三元组表

if(A->data[p].j==col){B->data[q].i==A->data[p].j;B->data[q].j=A->data[q].i;B->data[q].v=A->data[p].v;q++;}//if}//if(b->tu>0)returnB;//返回转置后矩阵的指针}//TransM1[算法6.2]稀疏矩阵的转置算法13稀疏矩阵的乘积稀疏矩阵的乘法运算的粗略步骤如下：(1)初始化。清理一些单元，准备按行顺序存放乘积矩阵。(2)求B的num，rpot。(3)做矩阵乘法。将A.data中三元组的列值与B.data中三元组的行值相等的非零元素相乘，并将具有相同下标的乘积元素相加。稀疏矩阵的乘积稀疏矩阵的乘法运算的粗略步骤如下：14[算法6.3]稀疏矩阵的乘积算法

SPMatrix*MulSMatrix(SPMatrix*A,SPMatrix*B){//稀疏矩阵A(m1×n1)和B(m2×n2)用三元组表存储,求A×BSPMatrix*C;//乘积矩阵的指针intp,q,i,j,k,r;Elemtypetemp[n+1];intnum[B->nu+1],rpot[B->nu+1];if(A->nu!=B->mu)returnNULL;//A的列与B的行不相等C=(SPMatrix*)malloc(sizeof(SPMatrix));//申请C的存储空间C->mu=A->mu;C->nu=A->nu;if(A->tu*B->tu==0){C->tu=0;returnC;}for(i=1;i<=B->mu;i++)num[i]=0;//求矩阵B中每一行非零元素的个数for(k=1;k<=B->tu;k++){

[算法6.3]稀疏矩阵的乘积算法15{i=B->data[k].i;num[i]++;}rpot[1]=1;//求矩阵B中每一行第一个非零元素在B.data中的位置for(i=2;i<=B->mu;i++)rpot[i]=rpot[i-1]+num[i-1];r=0;//当前C中非零元素的位置p=1;for(i=1;i<=A->mu;i++){for(j=1;j<=B->nu;j++)temp[j]=0;//C累加器初始化while(A->data[p].i==i){k=A->data[p].j;if(k<B->mu)t=rpot[k+1];{16elset=B->tu+1;//确定B中第k行的非零元素在B.data中下限位置for(q=rpot[k];q<t;q++)//B中第k行的每一个非零元素{j=B->data[q].j;temp[j]+=A->data[p].v*B->data[q].v;}p++;}//whilefor(j=1;j<=B->nu;j++)if(temp[j]){r++;C->data[r]={i,j,temp[j]};}}//foriC->tu=r;returnC;}//MulSMtrixelse17广义表的概念和特性1。定义：广义表是n(n≥0)个元素有限序列，记作A=(a1,a2,a3,…,an)其中，A是广义表的名称，n是它的长度，ai(1≤i≤n)或者是数据元素，或者是广义表。显然广义表的定义是一个递归的定义，即广义表中可以包含广义表。

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。定义：广义表是n(n≥0)个元素有限181．头尾表示法

图6.18头尾表示法的结点形式1．头尾表示法图6.18头尾表示法的结点形式192．孩子兄弟表示法

图6.20孩子兄弟表示法的结点形式2．孩子兄弟表示法

图6.20孩子兄弟表示法的结点形式201．广义表的基本运算

Creat(LS)：根据广义表的书写形式创建一个广义表LS。IsEmpty(LS)：若广义表LS为空，则返回True；否则返回False。Length(LS)：求广义表的长度。Depth(LS)：求广义表的深度。Locate(LS,x)：在广义表LS上查找数据元素x。Merage(LS1，LS2)：复制广义表，即按照LS1建立广义表LS2。Head(LS)：返回广义表的头部。Tail(LS)：返回广义表的尾部。1．广义表的基本运算

Creat(LS)：根据广义表的书写形212．广义表运算的实现[算法6.4]广义表的取头算法GlistHead(Glist*ls){GLNode*p;p=NULL;if(ls->tag)p=ls->hp;returnp;}2．广义表运算的实现[算法6.4]广义表的取头算法22[算法6.5]广义表的取尾算法GlistTail(Glistls){GLNode*p;p=NULL;if(ls->tag)p=ls->tp;returnp;}[算法6.5]广义表的取尾算法23[算法6.6]建立广义表的存储结构的算法intCreate(Glistls,char*s){GLNode*p,*q;char*sub,hsub;if(StrEmpty(s))*ls=NULL;else{(*ls)=(GLNode*)malloc(sizeof(GLNode));if(!(*ls))return0;if(Strlength(s)==1){(*ls)->tag=0;(*ls)->data=s;}else{(*ls)->tag=1;[算法6.6]建立广义表的存储结构的算法24p=*ls;hsub=SubStr(s,2,StrLength(s)-2);do{sever(sub,hsub);Create(&(p->ptr.hp),sub);q=p;if(!StrEmpty(sub){p=(GLNode*)malloc(sizeof(GLNode));if(!p)return0;p->tag=1;q->ptr.tp=p;}}while(!StrEmpty(sub));q->ptr.tp=NULL;}}return1;}intsever(char*str,char*hstr){inti,k,n;p=*ls;25charch;n=StrLength(str));i=1;k=0;for(i=1,k=0;i<=n||k!=0;++i){ch=SubStr(str,i,1);if(ch==′(′)++k;elseif(ch==′)′)--k;}if(i<=n){hstr=SubStr(str,1,i-2);str=SubStr(str,i,n-i+1);}else{StrCopy(hstr,str);CreatStr(str);}}charch;26[算法6.7]以表头、表尾建立广义表算法intMerge(Glistls1,Glistls2,Glist*ls){(*ls)=malloc(sizeof(GLNode));if(!(*ls))return0;(*ls)->tag=1;(*ls)->hp=ls1;(*ls)->tp=ls2;return1;}[算法6.7]以表头、表尾建立广义表算法27[算法6.8]求广义表的深度算法intDepth(Glistls){indep,max;Glistp;if(!ls)return1;//空表深度为1if(ls->tag==0)return0;//单元素深度为0for(max=0,p=ls;p;p=p->ptr.tp){dep=Depth(p->ptr.hp);//求以p->ptr.hp尾头指针的子表深度if(dep>max)max=dep;}returnmax+1;//非空表的深度是各元素的深度的最大值加1}[算法6.8]求广义表的深度算法28[算法6.9]复制广义表算法intCopyGlist(Glistls1,Glist*ls2){if(!ls1)(*ls2)=NULL;else{(*ls2)=malloc(sizeof(GLNode));if(!(*ls2))return0;//建表头结点(*ls2)->tag=ls1->tag;if(ls1->tag==0)(*ls2)->data=ls1->data;//复制单元素else{CopyGList(&((*ls2)->ptr.hp),ls1->ptr.hp);//复制广义表ls1->ptr.hp的一个副本CopyGList(&((*ls2)->ptr.tp),ls1->ptr.tp);//复制广义表ls1->ptr.tp的一个副本}}return1;}[算法6.9]复制广义表算法29王钢主编清华大学出版社数据结构王钢主编数据结构30第6章数组、特殊矩阵和广义表数组的定义及其存储特殊矩阵的压缩存储稀疏矩阵逻辑结构和存储结构广义表的逻辑结构和存储结构数组和广义表的操作应用举例第6章数组、特殊矩阵和广义表数组的定义及其存储31数组的定义及逻辑结构

数组是由下标和值组成的元素序列的集合。在数组中，一旦给定下标，都存在一个与其对应的值，这个值称为数组元素。在数组中通常做下面两种操作：取值操作：给定一组下标，读其对应的数组元素。赋值操作：给定一组下标，存储或修改与其相对应的数据元素。数组的定义及逻辑结构数组是由下标和值组成的元素序列的集合。32例6.1若矩阵Am×n中存在某个元素aij满足：aij是第i行中最小值且第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中所有的鞍点。基本思路：在矩阵A中求出每一行的最小元素，然后判断该元素是否是它所在列中的最大值，若是则打印出，接着处理下一行。矩阵A用二维数组表示。算法如下：例题例6.1若矩阵Am×n中存在某个元素aij满足：aij33[算法6.1]求矩阵鞍点算法voidsaddle(intA[][],intm,intn){//m,n是矩阵A的行和列inti,j,k,min;for(i=0;i<m;i++){min=A[i][0];for(j=1;j<n;j++)if(A[i][j]<min)min=A[i][j];//找第i行最小值for(j=0;j<n;j++)//检测该行中的每一个最小值是否是鞍点if(A[i][j]==min){k=j;p=0;while(p<m&&A[p][j]<=min)p++;if(p>=m)printf("%d%d%d",i,j,k);}//if}}[算法6.1]求矩阵鞍点算法34对称矩阵的压缩存储

1．对称矩阵若一个n阶矩阵M中满足下述性质：aij=aji0≤i,j≤n–1则称为n阶对称矩阵。例如A矩阵是一个5阶对称矩阵，如图6.5所示。2352936638562732378498341A=对称矩阵的压缩存储1．对称矩阵235293352．对称矩阵的存储a0,0a1,0a1,1a2,0…an-1,0an-1,n-1k值n(n+1)/2–10123第1行第2行第n行图6.6对称矩阵的压缩存储2．对称矩阵的存储a0,0a1,0a1,1a2,0…an-1361．三角矩阵

82345a5671aa897aaa10aaaa8B=8000025000368004791051708C=图6.7上三角矩阵及下三角矩阵1．三角矩阵

82345a567371．带状矩阵00a0,0a0,1a0,200a1,0a1,1a1,2a1,30a2,0a2,1a2,2a2,3a2,4

0a3,1a3,2a3,3a3,4

00a4,2a4,3a4,4D=b条b条图6.8带状矩阵图6.9半带宽为2的5阶带状矩阵1．带状矩阵00a0,0a0,1a0,2038稀疏矩阵

16–15221123311155191346ijv1A=153000000220–151100060000000091000000000023414225670图6.11稀疏矩阵图6.12三元组表稀疏矩阵16–15221139三元组的类型定义：#defineSMAX1024//最大非零元素个数typedefstruct{inti,j;//非零所在行、列

Elemtypev;//非零元素的值}SPNode;//存储非零元素的三元组结构体类型typedefstruct{intmu,nu,tu;//矩阵的行、列及非零元素的实际个数SPNodedata[SMAX];//三元组表}SPMatrix;//稀疏矩阵的三元组表存储类型三元组的类型定义：40稀疏矩阵的转置159112113234122111561–15436ijv1234567B=150009100000000110000030000–15000002206000图6.13A的转置B图6.14B的三元组算法思路：①A的行、列转化成B的列、行；②在A.data中依次找第一列的、第二列的、直到最后一列，并将找到的每个三元组的行、列交换后顺序存储到B.data中即可。稀疏矩阵的转算法6.2]稀疏矩阵的转置算法SPMatrix*TransM1(SPMatrix*A){SPMatrix*B;intp,q,col;B=(SPMatrix*)malloc(sizeof(SPMatrix));B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;if(B->tu>0){q=1;for(col=1;col<=(A->nu);col++)//按A的列序转换for(p=1;p<=(A->tu);p++)//扫描整个三元组表

if(A->data[p].j==col){B->data[q].i==A->data[p].j;B->data[q].j=A->data[q].i;B->data[q].v=A->data[p].v;q++;}//if}//if(b->tu>0)returnB;//返回转置后矩阵的指针}//TransM1[算法6.2]稀疏矩阵的转置算法42稀疏矩阵的乘积稀疏矩阵的乘法运算的粗略步骤如下：(1)初始化。清理一些单元，准备按行顺序存放乘积矩阵。(2)求B的num，rpot。(3)做矩阵乘法。将A.data中三元组的列值与B.data中三元组的行值相等的非零元素相乘，并将具有相同下标的乘积元素相加。稀疏矩阵的乘积稀疏矩阵的乘法运算的粗略步骤如下：43[算法6.3]稀疏矩阵的乘积算法

SPMatrix*MulSMatrix(SPMatrix*A,SPMatrix*B){//稀疏矩阵A(m1×n1)和B(m2×n2)用三元组表存储,求A×BSPMatrix*C;//乘积矩阵的指针intp,q,i,j,k,r;Elemtypetemp[n+1];intnum[B->nu+1],rpot[B->nu+1];if(A->nu!=B->mu)returnNULL;//A的列与B的行不相等C=(SPMatrix*)malloc(sizeof(SPMatrix));//申请C的存储空间C->mu=A->mu;C->nu=A->nu;if(A->tu*B->tu==0){C->tu=0;returnC;}for(i=1;i<=B->mu;i++)num[i]=0;//求矩阵B中每一行非零元素的个数for(k=1;k<=B->tu;k++){

[算法6.3]稀疏矩阵的乘积算法44{i=B->data[k].i;num[i]++;}rpot[1]=1;//求矩阵B中每一行第一个非零元素在B.data中的位置for(i=2;i<=B->mu;i++)rpot[i]=rpot[i-1]+num[i-1];r=0;//当前C中非零元素的位置p=1;for(i=1;i<=A->mu;i++){for(j=1;j<=B->nu;j++)temp[j]=0;//C累加器初始化while(A->data[p].i==i){k=A->data[p].j;if(k<B->mu)t=rpot[k+1];{45elset=B->tu+1;//确定B中第k行的非零元素在B.data中下限位置for(q=rpot[k];q<t;q++)//B中第k行的每一个非零元素{j=B->data[q].j;temp[j]+=A->data[p].v*B->data[q].v;}p++;}//whilefor(j=1;j<=B->nu;j++)if(temp[j]){r++;C->data[r]={i,j,temp[j]};}}//foriC->tu=r;returnC;}//MulSMtrixelse46广义表的概念和特性1。定义：广义表是n(n≥0)个元素有限序列，记作A=(a1,a2,a3,…,an)其中，A是广义表的名称，n是它的长度，ai(1≤i≤n)或者是数据元素，或者是广义表。显然广义表的定义是一个递归的定义，即广义表中可以包含广义表。

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。定义：广义表是n(n≥0)个元素有限471．头尾表示法

图6.18头尾表示法的结点形式1．头尾表示法图6.18头尾表示法的结点形式482．孩子兄弟表示法

图6.20孩子兄弟表示法的结点形式2．孩子兄弟表示法

图6.20孩子兄弟表示法的结点形式491．广义表的基本运算

Creat(LS)：根据广义表的书写形式创建一个广义表LS。IsEmpty(LS)：若广义表LS为空，则返回True；否则返回False。Length(LS)：求广义表的长度。Depth(LS)：求广义表的深度。Locate(LS,x)：在广义表LS上查找数据元素x。Merage(LS1，LS2)：复制广义表，即按照LS1建立广义表LS2。Head(LS)：返回广义表的头部。Tail(LS)：返回广义表的尾部。1．广义表的基本运算

Creat(LS)：根据广义表的书写形502．广义表运算的实现[算法6.4]广义表的取头算法GlistHead(Glist*ls){GLNode*p;p=NULL;if(ls->tag)p=ls->hp;returnp;}2．广义表运算的实现[算法6.4]广义表的取头算法51[算法6.5]广义表的取尾算法GlistTail(Glistls){GLNode*p;p=NULL;if(ls->tag)p=ls->tp;returnp;}[算法6.5]广义表的取尾算法52[算法6.6]建立广义表的存储结构的算法intCreate(Glistls,char*s){GLNode*p,*q;char*sub,hsub;if(StrEmpty(s))*ls=NULL;else{(*ls)=(GLNode*)malloc(sizeof(GLNode));if(!(*ls))return0;if(Strlength(s)==1){(*ls)->tag=0;(*ls)->data=s;}else{(*ls)->tag=1;[算法6.6]建立广义表的存储结构的算法53p=*ls;hsub=SubStr(s,