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

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

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