用三元組表示稀疏矩陣的乘法

用三元組表示稀疏矩陣的乘法第1頁，課件共26頁，創(chuàng)作于2023年2月兩個矩陣相乘也是矩陣的一種常用的運算。設矩陣M是m1×n1矩陣，N是m2×n2矩陣；若可以相乘，則必須滿足矩陣M的列數(shù)n1與矩陣N的行數(shù)m2相等，才能得到結(jié)果矩陣Q=M×N（一個m1×n2的矩陣）。數(shù)學中矩陣Q中的元素的計算方法如下：其中：1≤i≤m1,1≤j≤n2。第2頁，課件共26頁，創(chuàng)作于2023年2月根據(jù)數(shù)學上矩陣相乘的原理，我們可以得到矩陣相乘的經(jīng)典算法：for(i=1;i<=m1;i++)for(j=1;j<=n2;j++){Q［i］［j］=0;for(k=1;k<=n1;k++)Q［i］［j］=Q［i］［j］+M［i］［k］*N［k］[j］;}第3頁，課件共26頁，創(chuàng)作于2023年2月圖5.17Q=M×N圖5.17給出了一個矩陣相乘的例子。當矩陣M、N是稀疏矩陣時，我們可以采用三元組表的表示形式來實現(xiàn)矩陣的相乘。第4頁，課件共26頁，創(chuàng)作于2023年2月圖5.18矩陣M、N、Q的三元組表第5頁，課件共26頁，創(chuàng)作于2023年2月經(jīng)典算法中，不論M［i］［k］、N［k］［j］是否為零，都要進行一次乘法運算，而實際上，這是沒有必要的。采用三元組表的方法來實現(xiàn)時，因為三元組只對矩陣的非零元素做存儲所以可以采用固定三元組表a中的元素（i，k，Mik）（1≤i≤m1，1≤k≤n1），在三元組表b中找所有行號為k的的對應元素（k，j，Nkj）（1≤k≤m2，1≤j≤n2）進行相乘、累加，從而得到Q［i］［j］，即以三元組表a中的元素為基準，依次求出其與三元組表b的有效乘積。第6頁，課件共26頁，創(chuàng)作于2023年2月算法中附設兩個向量num［］、first［］，其中num［row］表示三元組表b中第row行非零元素個數(shù)（1≤row≤m2），first［row］表示三元組表b中第row行第一個非零元素所在的位置。顯然，first［row+1］-1指向三元組表b中第row行最后一個非零元素的位置。first［1］=1；first［row］=first［row-1］+num［row-1］，2≤row≤m2+1。這里，first［m2+1］-1表示最后一行最后一個非零元素的存儲位置。當三元組表a中第i行非零元素的列號等于三元組表b中非零元素的行號時，則元素相乘并將結(jié)果累加。第7頁，課件共26頁，創(chuàng)作于2023年2月圖5.19Q=M×N第8頁，課件共26頁，創(chuàng)作于2023年2月圖5.20圖5.19中矩陣N對應的向量num［row］,first［row］Row1234(5)Num[row]2111First[row]13456第9頁，課件共26頁，創(chuàng)作于2023年2月＃defineMAXSIZE1000/*非零元素的個數(shù)最多為1000*/＃defineMAXROW1000/*矩陣最大行數(shù)為1000*/typedefstruct{introw,col;/*該非零元素的行下標和列下標*/ElementTypee；/*該非零元素的值*/}Triple;typedefstruct{Tripledata［MAXSIZE+1］;/*非零元素的三元組表，data［0］未用*/intfirst［MAXROW+1］;/*三元組表中各行第一個非零元素所在的位置*/intm,n,len;/*矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)*/}TriSparMatrix；第10頁，課件共26頁，創(chuàng)作于2023年2月具體算法如下：該算法的時間主要耗費在乘法運算及累加上，其時間復雜度為O（A.len×B.n）。當A.len接近于A.m×A.n時，該算法時間復雜度接近于經(jīng)典算法的時間復雜度O（A.m×A.n×B.n）。

第11頁，課件共26頁，創(chuàng)作于2023年2月稀疏矩陣的鏈式存儲結(jié)構(gòu):十字鏈表與用二維數(shù)組存儲稀疏矩陣比較，用三元組表表示的稀疏矩陣不僅節(jié)約了空間，而且使得矩陣某些運算的運算時間比經(jīng)典算法還少。但是在進行矩陣加法、減法和乘法等運算時，有時矩陣中的非零元素的位置和個數(shù)會發(fā)生很大的變化。如A=A+B，將矩陣B加到矩陣A上，此時若還用三元組表表示法，勢必會為了保持三元組表“以行序為主序”而大量移動元素。第12頁，課件共26頁，創(chuàng)作于2023年2月在十字鏈表中，矩陣的每一個非零元素用一個結(jié)點表示，該結(jié)點除了（row，col，value）以外，還要有以下兩個鏈域：right：用于鏈接同一行中的下一個非零元素；down：用于鏈接同一列中的下一個非零元素。rowcolValueDownright第13頁，課件共26頁，創(chuàng)作于2023年2月圖5.23十字鏈表的結(jié)構(gòu)第14頁，課件共26頁，創(chuàng)作于2023年2月十字鏈表的結(jié)構(gòu)類型說明如下：typedefstructOLNode{introw,col;/*非零元素的行和列下標*/ElementTypevalue;structOLNode*right,*down;/*非零元素所在行表、列表的后繼鏈域*/}OLNode;*OLink;typedefstruct{OLink*row_head,*col_head;/*行、列鏈表的頭指針向量*/intm,n,len;/*稀疏矩陣的行數(shù)、列數(shù)、非零元素的個數(shù)*/}CrossList;第15頁，課件共26頁，創(chuàng)作于2023年2月CreateCrossList(CrossList*M){/*采用十字鏈表存儲結(jié)構(gòu)，創(chuàng)建稀疏矩陣M*/scanf(&m,&n,&t);/*輸入M的行數(shù),列數(shù)和非零元素的個數(shù)*/M->m=m;M->n=n;M->len=t;If(!(M->row_head=(OLink*)malloc((m+1)sizeof(OLink))))exit(OVERFLOW);If(!(M->col_head=(OLink*)malloc((n+1)sizeof(OLink))))exit(OVERFLOW);M->row_head［］=M->col_head［］=NULL;/*初始化行、列頭指針向量，各行、列鏈表為空的鏈表*/for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)){if(!(p=(OLNode*)malloc(sizeof(OLNode))))exit(OVERFLOW);p->row=i;p->col=j;p->value=e;/*生成結(jié)點*/if(M->row_head［i］==NULL)M->row_head［i］=p;第16頁，課件共26頁，創(chuàng)作于2023年2月else{/*尋找行表中的插入位置*/for(q=M->row_head［i］;q->right&&q->right->col<j;q=q->right)p->right=q->right;q->right=p;/*完成插入*/}if(M->col_head［j］==NULL)M->col_head［j］=p;else{/*尋找列表中的插入位置*/for(q=M->col-head［j］;q->down&&q->down->row<i;q=q->down)p->down=q->down;q->down=p;/*完成插入*/}}}第17頁，課件共26頁，創(chuàng)作于2023年2月廣義表廣義表，顧名思義，也是線性表的一種推廣。廣義表被廣泛地應用于人工智能等領(lǐng)域的表處理語言LISP語言中。在LISP語言中，廣義表是一種最基本的數(shù)據(jù)結(jié)構(gòu)，就連LISP語言的程序也表示為一系列的廣義表。第18頁，課件共26頁，創(chuàng)作于2023年2月在第2章中，線性表被定義為一個有限的序列（a1，a2，a3，…，an）,其中ai被限定為是單個數(shù)據(jù)元素。廣義表也是n個數(shù)據(jù)元素（d1，d2，d3，…，dn）的有限序列，但不同的是，廣義表中的di既可以是單個元素，還可以是一個廣義表，通常記作：GL=（d1，d2，d3，…，dn）。GL是廣義表的名字，通常廣義表的名字用大寫字母表示。n是廣義表的長度。若其中di是一個廣義表，則稱di是廣義表GL的子表。在廣義表GL中，d1是廣義表GL的表頭，而廣義表GL其余部分組成的表（d2，d3，…，dn）稱為廣義表的表尾。由此可見廣義表的定義是遞歸定義的，因為在定義廣義表時又使用了廣義表的概念。第19頁，課件共26頁，創(chuàng)作于2023年2月·D=（）空表；其長度為零?！=（a，（b，c））表長度為2的廣義表，其中第一個元素是單個數(shù)據(jù)a，第二個元素是一個子表（b，c）?！=（A，A，D）長度為3的廣義表，其前兩個元素為表A，第三個元素為空表D?！=（a，C）長度為2遞歸定義的廣義表，C相當于無窮表C=（a，（a,（a，（…））））。#其中，A、B、C、D是廣義表的名字。下面以廣義表A為例，說明求表頭、表尾的操作：head（A）=a表A的表頭是a。tail（A）=（（b，c））表A的表尾是（（b，c））。廣義表的表尾一定是一個表。第20頁，課件共26頁，創(chuàng)作于2023年2月從上面的例子可以看出：（1）廣義表的元素可以是子表，而子表還可以是子表……由此可見，廣義表是一個多層的結(jié)構(gòu)。（2）廣義表可以被其它廣義表共享，如廣義表B就共享表A。在表B中不必列出表A的內(nèi)容，只要通過子表的名稱就可以引用該表。（3）廣義表具有遞歸性，如廣義表C。第21頁，課件共26頁，創(chuàng)作于2023年2月由于廣義表GL=（d1，d2，d3，…，dn）中的數(shù)據(jù)元素既可以是單個元素，也可以是子表，因此對于廣義表來說，我們難以用順序存儲結(jié)構(gòu)來表示它，通常我們用鏈式存儲結(jié)構(gòu)來表示。表中的每個元素可用一個結(jié)點來表示。廣義表中有兩類結(jié)點：一類是單個元素結(jié)點；另一類是子表結(jié)點。任何一個非空的廣義表都可以分解成表頭和表尾兩部分，反之，一對確定的表頭和表尾可以唯一地確定一個廣義表。由此，一個表結(jié)點可由三個域構(gòu)成：標志域、指向表頭的指針域和指向表尾的指針域。而元素結(jié)點只需要兩個域：標志域和值域。第22頁，課件共26頁，創(chuàng)作于2023年2月typedefenum{ATOM,LIST}ElemTag;/*ATOM＝0，表示原子；LIST＝1，表示子表*/typedefstructGLNode{ElemTagtag;/*標志位tag用來區(qū)別原子結(jié)點和表結(jié)點*/union{AtomTypeatom;/*原子結(jié)點的值域atom*/struct{structGLNode*hp,*tp;}