稀疏矩陣和廣義表

第三章稀疏矩陣和廣義表學(xué)習(xí)目標(biāo)掌握稀疏矩陣的定義及三元組表示和存儲結(jié)構(gòu)；掌握稀疏矩陣的運算方法和時間復(fù)雜度；掌握廣義表的定義及存儲，長度、深度求解方法和算法。數(shù)據(jù)結(jié)構(gòu)》第三章稀疏矩陣的定義

稀疏矩陣(SparseMatrix)：是矩陣的特殊情況，它的非零元素的個數(shù)遠遠小于零元素的個數(shù)。

3.1稀疏矩陣123456

30050000-200010406000000000-1000如:數(shù)據(jù)結(jié)構(gòu)》第三章稀疏矩陣中非零元素用（行號，列號，元素值）表示，并以行號為主關(guān)鍵字，列號為次關(guān)鍵字對所有三元組進行排序。三元組線性表表示

123456

30050000-200010406000000000-1000((1,1,3),(1,4,5),(2,3,-2),(3,1,1),(3,3,4),(3,5,6),(5,3,-1))數(shù)據(jù)結(jié)構(gòu)》第三章稀疏矩陣的壓縮存儲1、三元組線性表順序存儲2、三元組線性表鏈接存儲帶行指針向量的鏈接存儲十字鏈接數(shù)據(jù)結(jié)構(gòu)》第三章三元組順序存儲123456

30050000-200010406000000000-100011314523-2311334356531下標(biāo)rowcolval1234567:.MaxTerms數(shù)據(jù)結(jié)構(gòu)》第三章三元組線性表順序存儲StructTriple{introw,col;ElemTypeval;}StructSMatrix{intm,n,t;Triplesm[MaxTems+1];};數(shù)據(jù)結(jié)構(gòu)》第三章35614553-123-211314523-2311334356531帶行指針向量的鏈接存儲113334311數(shù)據(jù)結(jié)構(gòu)》第三章三元組線性表鏈接存儲(1)帶行指針向量的鏈接存儲StructTripleNode{introw,col;ElemTypeval;TripleNode*next;}StructLMatrix{intm,n,t;TripleNode*vector[MaxRows+1];};數(shù)據(jù)結(jié)構(gòu)》第三章113

145十字鏈接存儲23-253-1356334

311

12345612345數(shù)據(jù)結(jié)構(gòu)》第三章(2)十字鏈接存儲StructCrossNode{introw,col;ElemTypeval;CrossNode*down,*rigth;}StructCLMatrix{intm,n,t;CrossNode*rv[MaxRows+1];CrossNode*cv[MaxColumns+1];};數(shù)據(jù)結(jié)構(gòu)》第三章

稀疏矩陣抽象數(shù)據(jù)類型ADTSparseMatrixis

Data:

稀疏矩陣類型

SMatrix（或CLMatrix）

Operation:voidInitMatrix(SMatrix&M);

SMatrixTranspose(SMatrix&M);SMatrixAdd(SMatrix&M1,SMatrix&M2);SMatrixMultiply(SMatrix&M1,SMatrix&M2);voidInputMatrix(SMatrix&M,intm,intn);voidOutputMatrix(SMatrix&M);endSparseMatrix數(shù)據(jù)結(jié)構(gòu)》第三章稀疏矩陣的運算

1.初始化運算voidInitMatrix(SMatrix&M){M.m=0;M.n=0;M.t=0;}voidInitMatrix(LMatrix&M){M.m=0;M.n=0;M.t=0;for(inti=1;i<=MaxRows;i++)M.vector[i]=NULL;}voidInitMatrix(CLMatrix&M){M.m=0;M.n=0;M.t=0;for(inti=1;i<=MaxRows;i++)M.rv[i]=NULL;for(inti=1;i<=MaxColumns;i++)M.cv[i]=NULL;}數(shù)據(jù)結(jié)構(gòu)》第三章2、稀疏矩陣的輸入voidInputMatrix(SMatrix&M,intm,intn){M.m=m;M.n=n;introw,col,val;intk=0;cin>>row>>col>>val;While(row!=0){k++;M.sm[k].row=row;M.sm[k].col=col;M.sm[k].val=val;cin>>row>>col>>val;}M.t=k;}數(shù)據(jù)結(jié)構(gòu)》第三章voidInputMatrix(CLMatrix&M,intm,intn);{M.m=m;M.n=n;introw,col,val;intk=0;cin>>row>>col>>val;while(row!=0){k++;CrossNode*cp,*newptr;newptr=newCrossNode;newptr->row=row;newptr->col=col;newptr->val=val;數(shù)據(jù)結(jié)構(gòu)》第三章newptr->right=newptr->down=NULL;cp=M.rv[row];if(cp==NULL)M.rv[row]=newptr;else{while(cp->right!=NULL)cp=cp->right;cp->right=newptr;}cp=M.cv[col];if(cp==NULL)M.cv[col]=newptr;else{while(cp->down!=NULL)cp=cp->down;cp->down=newptr;}cin>>row>>col>>val;}M.t=k;}數(shù)據(jù)結(jié)構(gòu)》第三章3、稀疏矩陣的輸出voidOutputMatrix(SMatrix&M){cout<<“(“;for(inti=1;i<M.t;i++){cout<<“(“<<M.sm[i].row<<“,”;cout<<M.sm[i].col<<“,”;cout<<M.sm[i].val<<“)”<<“,”;}for(M.t!=0){cout<<“(“<<M.sm[M.t].row<<“,”;cout<<M.sm[M.t].col<<“,”;cout<<M.sm[M.t].val<<“)”;}cout<<“)“<<endl;}數(shù)據(jù)結(jié)構(gòu)》第三章4、稀疏矩陣的轉(zhuǎn)置運算SMatrixTranspose(SMatrix&M){SMatrixS;InitMatrix(S);intm,n,t;m=M.m;n=M.n;t=M.t;S.m=n;S.n=m;S.t=t;if(t==0)returnS;intk=1;for(intcol=1;col<=n;col++)for(inti=1;i<=t;i++)if(M.sm[i].col==col){S.sm[k].row=col;S.sm[k].col=M.sm[i].row;S.sm[k].val=M.sm[i].val;k++;}returnS;}數(shù)據(jù)結(jié)構(gòu)》第三章5、稀疏矩陣的加法運算LMatrixAdd(LMatrix&M1,LMatrix&M2){LMatrixM;InitMatrix(M);if((M1.m!=M2.m)||(M1.n!=M2.n)){cerr<<“twomatrixmeasurenentsaredifferent!”<<endl;exit(1);}M.m=M1.m;M.n=M1.n;if((M1.t==0)&&(M2.t==0))returnM;intk=0;數(shù)據(jù)結(jié)構(gòu)》第三章for(inti=1;i<=M1.m;i++){TripleNode*p1;*p2,*p;p1=M1.vector[i];p2=M2.vector[i];p=M.vector[i];while((p1!=NULL)&&(p2!=NULL)){TripleNode*newptr=newTripleNode;if(p1->col<p2->col){*newptr=*p1;p1=p1->next;}elseif(p1->col>p2->col){*newptr=*p2;p2=p2->next;}數(shù)據(jù)結(jié)構(gòu)》第三章elseif(p1->val+p2->vol==0){p1=p1->next;p2=p2->next;deletenewptr;continue;}else{*newptr=*p1;newptr->val+=p2->vol;p1=p1->next;p2=p2->next;}if(p==NULL)M.vector[i]=newptr;elsep->next=newptr;p=newptr;k++;}數(shù)據(jù)結(jié)構(gòu)》第三章while(p1!=NULL){TripleNode*newptr=newTripleNode;*newptr=*p1;newptr->next=NULL;if(p==NULL)M.vector[i]=newptr;elsep->next=newptr;p=newptr;p1=p1->next;k++;}數(shù)據(jù)結(jié)構(gòu)》第三章while(p2!=NULL){TripleNode*newptr=newTripleNode;*newptr=*p2;newptr->next=NULL;if(p==NULL)M.vector[i]=newptr;elsep->next=newptr;p=newptr;p2=p2->next;k++;}}M.t=k;returnM;}數(shù)據(jù)結(jié)構(gòu)》第三章廣義表的定義

n(0)個表元素組成的有限序列，記作

LS=(a0,a1,a2,…,an-1)LS是表名，ai是表元素，它可以是表(稱為子表)，可以是數(shù)據(jù)元素(稱為原子)。

n為表的長度。n=0的廣義表為空表。

n>0時，表的第一個表元素稱為廣義表的表頭(head)，除此之外，其它表元素組成的表稱為廣義表的表尾(tail)。

3.2廣義表數(shù)據(jù)結(jié)構(gòu)》第三章A=()B=(6,2)

C=(‘a(chǎn)’,(5,3,‘x’))表的深度：樹根結(jié)點到每個樹枝結(jié)點所經(jīng)過的結(jié)點個數(shù)的最大值D=(B,C,A)數(shù)據(jù)結(jié)構(gòu)》第三章廣義表的存儲結(jié)構(gòu)structGLNode{booltag;union{ElemTypedata;GLNode*sublist;};GLNode*next;};數(shù)據(jù)結(jié)構(gòu)》第三章A=()B=(6,2)

C=(‘a(chǎn)’,(5,3,‘x’))A=NULL02B061C0a03050x數(shù)據(jù)結(jié)構(gòu)》第三章A=()B=(6,2)

C=(‘a(chǎn)’,(5,3,‘x’))帶表頭結(jié)點的廣義表存儲結(jié)構(gòu)1AB02061C110a03050x數(shù)據(jù)結(jié)構(gòu)》第三章廣義表的運算1、求廣義表長度intLenth(GLNode*GL){if(GL!=NULL)return1+Lenth(G->next);elsereturn0;}數(shù)據(jù)結(jié)構(gòu)》第三章2、求廣義表深度intDepth(GLNode*GL){intmax=0;while(GL!=NULL){if(GL->tag==true){intdep=Depth(GL->sublist);if