稀疏矩陣應(yīng)用

1、稀疏矩陣應(yīng)用課題簡(jiǎn)介1.1課題及要求稀疏矩陣應(yīng)用(限1人完成)設(shè)計(jì)要求：實(shí)現(xiàn)三元組，十字鏈表下的稀疏矩陣的加、轉(zhuǎn)、乘的實(shí)現(xiàn)。(1) 稀疏矩陣的存儲(chǔ)(2) 稀疏矩陣加法(3) 矩陣乘法(4) 矩陣轉(zhuǎn)置1.2課程任務(wù)分析本課程設(shè)計(jì)主要實(shí)現(xiàn)在三元組存儲(chǔ)結(jié)構(gòu)與十字鏈表存儲(chǔ)結(jié)構(gòu)下輸入稀疏矩陣，并對(duì)稀疏矩陣進(jìn)行轉(zhuǎn)置，相加，相乘操作，最后輸出運(yùn)算后的結(jié)果。稀疏矩陣采用三元組和十字鏈表表示， 并在兩種不同的存儲(chǔ)結(jié)構(gòu)下， 求兩個(gè)具有相同行列數(shù)的稀疏矩陣 A和B的相加矩陣C,并輸出C;求 出A的轉(zhuǎn)置矩陣D,輸出D;求兩個(gè)稀疏矩陣A和B勺相乘矩陣E,并輸出E。1.3課程的意義其意義是讓我們?cè)趯W(xué)習(xí)完 G數(shù)據(jù)結(jié)構(gòu)等課程

2、基礎(chǔ)上，掌握多維數(shù)組的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié) 構(gòu)、掌握稀疏矩陣的壓縮存儲(chǔ)及轉(zhuǎn)置，相加，相乘等基本操作，并用不同的方法輸出結(jié)果，進(jìn) 一步掌握設(shè)計(jì)、實(shí)現(xiàn)較大系統(tǒng)的完整過程，包括系統(tǒng)分析、編碼設(shè)計(jì)、系統(tǒng)集成、以及調(diào)試分 析，熟練掌握數(shù)據(jù)結(jié)構(gòu)的選擇、設(shè)計(jì)、實(shí)現(xiàn)以及操作方法，為進(jìn)一步的應(yīng)用開發(fā)打好基礎(chǔ)。程序分析2.1設(shè)計(jì)函數(shù)建立稀疏矩陣及初始化值和輸出稀疏矩陣的值本模塊要求設(shè)計(jì)函數(shù)建立稀疏矩陣并初始化，包括在三元組結(jié)構(gòu)下和十字鏈表結(jié)構(gòu)下。首先要定義兩種不同的結(jié)構(gòu)體類型，在創(chuàng)建稀疏矩陣時(shí)，需要設(shè)計(jì)兩個(gè)不同的函數(shù)分別在三元組 和十字鏈表下創(chuàng)建稀疏矩陣，在輸入出現(xiàn)錯(cuò)誤時(shí)，能夠?qū)﹀e(cuò)誤進(jìn)行判別處理，初始化稀疏矩陣 都為

3、空值，特別注意在十字鏈表下，對(duì)變量進(jìn)行動(dòng)態(tài)的地址分配。在設(shè)計(jì)輸出稀疏矩陣的值的 函數(shù)時(shí)，也要針對(duì)兩種不同的情況，分別編制函數(shù)，才能準(zhǔn)確的輸出稀疏矩陣。在對(duì)稀疏矩陣 進(jìn)行初始化及輸出值時(shí)，均只輸出非零元素的值和它所在的所在行及所在列。2.2構(gòu)造函數(shù)進(jìn)行稀疏矩陣的轉(zhuǎn)置并輸出結(jié)果本模塊要求設(shè)計(jì)函數(shù)進(jìn)行稀疏矩陣的轉(zhuǎn)置并輸出轉(zhuǎn)置后的結(jié)果，由于對(duì)稀疏函數(shù)的轉(zhuǎn)置只對(duì)一個(gè)矩陣進(jìn)行操作，所以實(shí)現(xiàn)起來難度不是很大，函數(shù)也比較容易編寫。在編寫函數(shù)時(shí)，要 先定義一個(gè)相應(yīng)的結(jié)構(gòu)體變量用于存放轉(zhuǎn)置后的矩陣，最后把此矩陣輸出。2.3構(gòu)造函數(shù)進(jìn)行兩個(gè)稀疏矩陣相加及相乘并輸出最終的稀疏矩陣本模塊要求設(shè)計(jì)相加和相乘函數(shù)對(duì)兩個(gè)矩陣

4、進(jìn)行運(yùn)算，并輸出最終的稀疏矩陣，在進(jìn)行運(yùn) 算前，要對(duì)兩個(gè)矩陣進(jìn)行檢查，看是不是相同類型的矩陣，因?yàn)閮蓚€(gè)矩陣相加要求兩個(gè)矩陣一 定是同一類型的矩陣，定義相應(yīng)的矩陣類型用于存放兩個(gè)矩陣相加相乘后的結(jié)果矩陣，這個(gè)結(jié) 果矩陣的行數(shù)列數(shù)需要綜合多方面情況來確定。這四個(gè)函數(shù)也是整個(gè)程序的難點(diǎn)，需要靈活運(yùn) 用數(shù)組及指針的特點(diǎn)。2.4退出系統(tǒng)本模塊要求設(shè)置選項(xiàng)能隨時(shí)結(jié)束程序的運(yùn)行，本程序中采用exit (0)函數(shù)。程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示提示信息”之后，由用戶在鍵盤上輸入演示程序中需要的相關(guān)信息及命令。概要設(shè)計(jì)3.1主界面設(shè)計(jì)為了實(shí)現(xiàn)在兩種存儲(chǔ)結(jié)構(gòu)下對(duì)稀疏矩陣的多種算法功能的管理

5、，首先設(shè)計(jì)一含有多個(gè)菜單 項(xiàng)的主控菜單子程序以鏈接系統(tǒng)的各項(xiàng)子功能，方便用戶交互式使用本系統(tǒng)。本系統(tǒng)主控菜單運(yùn)行界面如圖 1所示。圖1主界面圖3.2存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)本系統(tǒng)采用三元組結(jié)構(gòu)和十字鏈表結(jié)構(gòu)存儲(chǔ)稀疏矩陣的具體信息。其中：在三元組中，所 有元素的信息用數(shù)組表示，每個(gè)數(shù)組元素中包含有行下標(biāo)(i),列下標(biāo)(j)和對(duì)應(yīng)的數(shù)值(e),它們是整型數(shù)據(jù)，全部的信息用在十字鏈表中，全部結(jié)點(diǎn)的信息用結(jié)構(gòu)體(TSMatrix )包含，包括用數(shù)組(Triple data MAXSIZE )和總共的行數(shù)(mu)，列數(shù)(nu)以及非零元素的 個(gè)數(shù)(tu)。在十字鏈表下，頭結(jié)點(diǎn)為指針數(shù)組的十字鏈表存儲(chǔ)；每個(gè)結(jié)點(diǎn)里面包

6、含行下標(biāo)(i),列下標(biāo)(j)和對(duì)應(yīng)的數(shù)值(e)，它們是整型數(shù)據(jù)，還有兩個(gè)指針 (right)、(down),屬于OLNode結(jié) 構(gòu)體。全部的信息用結(jié)構(gòu)體 (crosslist)包含，包括指針數(shù)組(OLink* rhead和*chead)和總共的行 數(shù)(mu)，列數(shù)(nu)以及非零元素的個(gè)數(shù)(tu)。三元組結(jié)構(gòu)體定義typedef struct(int i,j;int e;Triple;typedef struct(Triple dataMAXSIZE;int rposMAXSIZE + 1;int nu, mu,tu; TSMatrix ;十字鏈表結(jié)構(gòu)體定義：typedef struct OL

7、Nodeint i,j;int e;struct OLNode *right,*down;OLNode,*OLink;typedef struct int mu,nu,tu;OLink *rhead,*chead;CrossList;3.3系統(tǒng)功能設(shè)計(jì)本系統(tǒng)除了要完成分別在三元組存儲(chǔ)結(jié)構(gòu)以及在十字鏈表下實(shí)現(xiàn)稀疏矩陣的初始化功能外還設(shè)置了 4個(gè)子功能菜單。稀疏矩陣的建立及初始化在三元組存儲(chǔ)結(jié)構(gòu)下，由函數(shù)voidCreateSMatrix (TSMatrix &M)實(shí)現(xiàn)， 在十字鏈表存儲(chǔ)結(jié)構(gòu)下， 由函數(shù)void CreateSMatix_OL (CrossList & M)依據(jù)讀入

8、的行數(shù)和列數(shù)以及非零元素的個(gè)數(shù)，分別設(shè)定每個(gè)非 零元素的信息。4個(gè)子功能的設(shè)計(jì)描述如下。(1) 稀疏矩陣的轉(zhuǎn)置：此功能在三元組存儲(chǔ)結(jié)構(gòu)下，由函數(shù) void TransposeSMatrix(TSMatrix M,TSMatrix &T)實(shí) 現(xiàn)，在十字鏈表存儲(chǔ)結(jié)構(gòu)下，由函數(shù) void TurnSMatrix_OL(CrossList &M)實(shí)現(xiàn)。當(dāng)用戶選擇 該功能，系統(tǒng)提示用戶初始化一個(gè)矩陣，然后進(jìn)行轉(zhuǎn)置，最終輸出結(jié)果。(2) 稀疏矩陣的加法：此功能在三元組存儲(chǔ)結(jié)構(gòu)下，由函數(shù) void AddTMatix(TSMatrix M,TSMatrix T,TSMatrix &S

9、)實(shí)現(xiàn)，在十字鏈表存儲(chǔ)結(jié)構(gòu)下，由函數(shù) int SMatrix_ADD(CrossList *A,CrossList *B)實(shí)現(xiàn)。當(dāng)用 戶選擇該功能，系統(tǒng)即提示用戶初始化要進(jìn)行加法的兩個(gè)矩陣的信息。然后進(jìn)行加法，最后輸 出結(jié)果。(3) 稀疏矩陣的乘法：此功能在三元組存儲(chǔ)結(jié)構(gòu)下，由函數(shù) int MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q)實(shí)現(xiàn)。在十字鏈表存儲(chǔ)結(jié)構(gòu)下，由函數(shù) int MultSMatrix_OL(CrossList M, CrossList N, CrossList&Q)實(shí)現(xiàn)。當(dāng)用戶選擇該功能，系統(tǒng)提示輸入要進(jìn)行相乘

10、的兩個(gè)矩陣的詳細(xì)信息。然后進(jìn)行相 乘，最后得到結(jié)果。(4)退出：即退出稀疏矩陣的應(yīng)用系統(tǒng)，由 exit(0)函數(shù)實(shí)現(xiàn)。當(dāng)用戶選擇該功能，則退出該稀疏矩 陣的應(yīng)用系統(tǒng)。調(diào)試分析4.1系統(tǒng)運(yùn)行主界面系統(tǒng)運(yùn)行主界面如圖2所示:-13 -圖2主界面圖4.2各子功能測(cè)試運(yùn)行結(jié)果(以三元組為例)(1) 稀疏矩陣的創(chuàng)建及初始化:在主菜單下，用戶輸入1回車，是用三元組創(chuàng)建稀疏矩陣，根據(jù)屏幕提示初始化一個(gè)稀疏矩陣，按enter鍵，運(yùn)行結(jié)果如圖3所示。璧口非零元個(gè)裁 在歹!)星大八： 在歹!)辰太卜;j孳普IJ建稀疏矩陣，請(qǐng)選擇操作=青你選寸巡健稀疏 L用三元組倉(cāng) 表=魂出程序檸列美小1262 343 1B經(jīng)選擇

11、三疏矩性和加 .日辭距住相乘 k：退出程序圖3三元組倉(cāng)!j建并初始化矩陣(2) 稀疏矩陣的轉(zhuǎn)置:用三元組創(chuàng)建稀疏矩陣后，用戶輸入 1回車，便顯示該矩陣的轉(zhuǎn)置矩陣，運(yùn)行結(jié)果如圖4所圖4三元組稀疏矩陣轉(zhuǎn)置結(jié)果示意圖(3) 稀疏矩陣的相加：用三元組創(chuàng)建并初始化一個(gè)稀疏矩陣后，輸入2回車，按屏幕提示輸入第二個(gè)同類型的稀疏矩陣，按enter鍵，運(yùn)行結(jié)果如圖5所示。請(qǐng)選擇操作:-羞坐陣： 另WWU 入元元元的廠 叟入會(huì)丁 88112 3 312 3 12歹二主krTTTF74 9 數(shù)2 3 2 行1 2 3 的 矩大大大 疏魘及.列數(shù)和非零元個(gè)數(shù):圖5三元組稀疏矩陣相加結(jié)果示意圖(4) 稀疏矩陣的相乘：用

12、三元組創(chuàng)建并初始化一個(gè)稀疏矩陣后，輸入3回車，按屏幕提示輸入第二個(gè)同類型的稀疏矩陣，按enter鍵，運(yùn)行結(jié)果如圖6所示。甬蘭弓主目上 , I 1 I 請(qǐng)選擇操作:行列序 E-ps_nE組創(chuàng)建稀疏矩陣, 專置M輒另一個(gè)稀疏矩陣:請(qǐng)輸入稀疏矩陣的行數(shù)、列數(shù)和非零元個(gè)教瞇2瑾羋雷買素坐橋（ 尋后的矩陣為（只列出非蓼完素）.行麹關(guān)小1 3352 3283 148意鍵繼續(xù)枷八陶驪枳阡t塞歹!）及大七、116 ，在歹!）及大U 23? 吞歹心及大小* 3 1?（5）退出：在主菜單下，用戶輸入圖8。圖6三元組稀疏矩陣相乘結(jié)果示意圖3回車，或者在下級(jí)菜單中輸入 4回車，退出程序。運(yùn)行結(jié)果如圖7,圖7主菜單退出

13、程序圖圖8下級(jí)菜單退出程序圖總結(jié)由于本程序要求用兩種辦法對(duì)稀疏矩陣進(jìn)行運(yùn)算，特別是用十字鏈表這種形式來對(duì)稀疏矩 陣進(jìn)行運(yùn)算，是實(shí)現(xiàn)起來有很多困難，主要包括：1、書上這種方面的東西不多，資料少，可以參考的東西不是很多；2、用十字鏈表進(jìn)行運(yùn)算比較復(fù)雜，難度較大，需要對(duì)指針掌握較好；3、在書寫課程設(shè)計(jì)報(bào)告時(shí)，沒有具體的模板，感覺無從下手。針對(duì)上述困難，我通過網(wǎng)絡(luò)，圖書館找資料，借鑒別人的以往的優(yōu)秀的課程設(shè)計(jì)報(bào)告，和 同學(xué)們一起討論，逐步地解決自己的問題。通過此次課程設(shè)計(jì)，使我對(duì)本學(xué)期學(xué)的數(shù)據(jù)結(jié)構(gòu)有了更深的了解，也使自己的所學(xué)更加 牢固，并能夠把更方面的知識(shí)綜合起來運(yùn)用。附錄：程序源代碼#includ

14、e<stdio.h>#include<stdlib.h>#define MAXSIZE 100int num100;typedef struct OLNodeint i,j;int e;struct OLNode *right,*down;OLNode,*OLink;typedef struct int mu,nu,tu;OLink *rhead,*chead;CrossList;十字鏈表結(jié)構(gòu)體定義typedef structint i,j;int e;Triple;typedef structTriple dataMAXSIZE;int rposMAXSIZE + 1

15、;int nu,mu,tu;TSMatrix;三元組結(jié)構(gòu)體定義；int CreateSMatix_OL(CrossList &M)int i,j,e;OLink q;OLink p;printf("請(qǐng)輸入稀疏矩陣的行數(shù)，列數(shù)，非零元素的個(gè)數(shù):");矩陣行數(shù)，列數(shù)下標(biāo)均從開始；scanf("%d%d%d",&M.mu,&M.nu,&M.tu);M.rhead=(OLink *)malloc(M.mu+1)*sizeof(OLNode);/分配內(nèi)存空間M.chead=(OLink *)malloc(M.nu+1)*sizeof

16、(OLNode);/分配內(nèi)存空間for( i=1;i<=M.mu;i+)M.rheadi=NULL;/把矩陣每個(gè)元素置空值for( i=1;i<=M.nu;i+)M.cheadi=NULL;printf("請(qǐng)輸入稀疏矩陣，如果行為 0,則退出n");scanf("%d%d%d”,&i,&j,&e);while(i!=0)p=(OLink)malloc(sizeof(OLNode);p->i=i;p->j=j;p->e=e;if(M.rheadi=NULL|M.rheadi->j>j)p->ri

17、ght=M.rheadi;M.rheadi=p;elseq=M.rheadi;while(q->right&&q->right->j<j)q=q->right;p->right=q->right;q->right=p;if(M.cheadj=NULL|M.cheadj->i>i)p->down=M.cheadj;M.cheadj=p;elseq=M.cheadj;while(q->down&&q->down->i<i)q=q->down;p->down=q-&g

18、t;down;q->down=p;scanf("%d%d%d",&i,&j,&e);return 1;/創(chuàng)建十字鏈表void CreateSMatrix(TSMatrix &M)/米用三兀組順序表存儲(chǔ)表示，創(chuàng)建稀疏矩陣Mprintf("請(qǐng)輸入稀疏矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)：");scanf("%d%d%d",&M.mu,&M.nu,&M.tu);if(M.mu<=0)|(M.nu<=0)|(M.tu<=0)|(M.tu>M.mu*M.nu)判斷行值

19、、列值、元素個(gè)數(shù)是否合法printf("輸入有誤！");for(int i=1;i<=M.tu;i+)/輸入稀疏矩陣元素printf("請(qǐng)輸入元素坐標(biāo)(所在行，所在列)及大?。?quot;);scanf("%d%d%d”,&M.datai.i,&M.datai.j,&M.datai.e);if(M.datai.i<=0)|(M.datai.j<=0)printf(-輸入錯(cuò)誤，請(qǐng)重新輸入");scanf("%d%d%d",&M.datai.i,&M.datai.j,&a

20、mp;M.datai.e);/if/for iint num100;if(M.tu)int i;for(i = 1; i <= M.mu; i+) numi = 0;/ 初始化for(int t = 1; t <= M.tu; t+) +numM.datat.i;/求M 中每一行含非零元素個(gè)數(shù)/ 求 rposM.rpos1 = 1;for(i = 2; i <= M.mu; i+) M.rposi = M.rposi-1 + numi-1;/創(chuàng)建三元組void TransposeSMatrix(TSMatrix M,TSMatrix &T)T.nu=M.mu;/T矩陣

21、存放轉(zhuǎn)置后的矩陣T.mu=M.nu;T.tu=M.tu;int q=1;for(int col=1;col<=M.nu;col+)/通過循環(huán)，把非零元素的行數(shù)與列數(shù)進(jìn)行交換，實(shí)現(xiàn)轉(zhuǎn)置for(int p=1;p<=M.tu;p+)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;q+;/三元組轉(zhuǎn)置int Compare(int a1,int b1,int a2,int b2)if(a1>a2)return 1;else if(a1<a2)return -1;else i

22、f(b1>b2)return 1;if(b1<b2)return -1;else return 0;void AddTMatix(TSMatrix M,TSMatrix T,TSMatrix &S)/矩陣 S 存放相加后的矩陣S.mu=M.mu>T.mu?M.mu:T.mu;/ 對(duì)S矩陣的行數(shù)賦值S.nu=M.nu>T.nu?M.nu:T.nu;/ 對(duì)S矩陣的列數(shù)賦值S.tu=0;int ce;int q=1;int mcount=1,tcount=1;while(mcount<=M.tu&&tcount<=T.tu)switch(C

23、ompare(M.datamcount.i,M.datamcount.j,T.datatcount.i,T.datatcount.j)/用switch分支語句，用compare函數(shù)對(duì)需要相加的兩個(gè)矩陣的某元素行數(shù)列數(shù)進(jìn)行比較case -1: S.dataq.e=M.datamcount.e;/ 當(dāng) M.datamcount.i<T.datatcount.i 或 M.datamcount.j<T.datatcount.jS.dataq.i=M.datamcount.i;S.dataq.j=M.datamcount.j;/把第一個(gè)矩陣的行數(shù)i,列數(shù)j賦值給S矩陣的行數(shù)i,列數(shù)j q+;

24、mcount+;break;case 1: S.dataq.e=T.datatcount.e;/ 當(dāng) M.datamcount.i>T.datatcount.i 或M.datamcount.j>T.datatcount.jS.dataq.i=T.datatcount.i;S.dataq.j=T.datatcount.j;/把第二個(gè)矩陣的行數(shù)i,列數(shù)j賦值給S矩陣的行數(shù)i,列數(shù)jq+;tcount+;break;case 0: ce=M.datamcount.e+T.datatcount.e;/ 其他情況下把兩個(gè)矩陣的值相加if(ce) S.dataq.e=ce;S.dataq.i=

25、M.datamcount.i;S.dataq.j=M.datamcount.j;q+;mcount+;tcount+;else mcount+;tcount+;break;while(mcount<=M.tu)(S.dataq.e=M.datamcount.e;S.dataq.i=M.datamcount.i;S.dataq.j=M.datamcount.j;q+;mcount+; /在case=-1的情況下對(duì)S矩陣的非零值，行數(shù)，列數(shù)進(jìn)行賦值while(tcount<=M.tu)(S.dataq.e=T.datatcount.e;S.dataq.i=T.datatcount.i;

26、S.dataq.j=T.datatcount.j;q+;tcount+;/在case=1的情況下對(duì)S矩陣的非零值，行數(shù)，列數(shù)進(jìn)行賦值S.tu=q-1;/三元組相加int MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q)( int arow, brow, ccol, i, t, ctemp100, p, q, tp;/ 定義相乘函數(shù)中所需要用到的變量if(M.nu != N.mu) return 0;/如果第一個(gè)矩陣的行數(shù)不等于第二個(gè)矩陣的列數(shù)，則退出Q.mu = M.mu, Q.nu = N.nu, Q.tu = 0;/三元組結(jié)構(gòu)類型 Q

27、存放相乘后的結(jié)果if(M.tu * N.tu != 0)/如果兩個(gè)矩陣元素相乘不為零，則進(jìn)行運(yùn)算for(arow = 1; arow <= M.mu; +arow)/最外側(cè)循環(huán)以矩陣行數(shù)作為循環(huán)變量( for(i = 0; i <= N.nu; +i) ctempi = 0;Q.rposarow = Q.tu + 1;if(arow < M.mu) tp = M.rposarow + 1;else tp = M.tu +1;for(p = M.rposarow; p < tp; +p)/ 把每行與每列相乘brow = M.datap.j;if(brow < N.m

28、u) t = N.rposbrow+1;else t = N.tu + 1;for(q = N.rposbrow; q < t; +q)ccol = N.dataq.j;ctempccol += M.datap.e * N.dataq.e;/ 值相乘for(ccol = 1; ccol <= Q.nu; +ccol) /把運(yùn)算后的結(jié)果存放到 Q中 if(ctempccol)if(+(Q.tu) > MAXSIZE) return 1;Q.dataQ.tu.i = arow, Q.dataQ.tu.j = ccol, Q.dataQ.tu.e = ctempccol;retur

29、n 1;/三元組相乘void ShowTMatrix(TSMatrix M)for(int col=1;col<=M.mu;col+)/通過雙重循環(huán)，把稀疏矩陣中不為零的元素的行數(shù)、列數(shù)和值顯不'出來for(int p=1;p<=M.tu;p+)if(M.datap.i=col)printf("%4d %4d %4dn”,M.datap.i,M.datap.j,M.datap.e);/三元組顯示void TurnSMatrix_OL(CrossList &M)int col,row;/定義循環(huán)變量OLink p,q;/定義OLink結(jié)構(gòu)類型變量for(co

30、l=1;col<=M.mu;col+) /通過循環(huán)，把非零元素的行數(shù)與列數(shù)進(jìn)行交換，實(shí)現(xiàn)轉(zhuǎn)置 q=p=M.rheadcol;while(q)row=p->i;p->i=p->j;p->j=row;q=p->right;p->right=p->down;p->down=q;/十字鏈表轉(zhuǎn)置int SMatrix_ADD(CrossList *A,CrossList *B)OLNode *pa,*pb,*pre,*p,*cp100; / 定義 OLNode 類型的變量 int i,j,t; t=A->tu+B->tu;for(j=1;

31、j<=A->nu;j+)cpj=A->cheadj;/將 A 矩陣的列表頭指針賦給c政組for(i=1;i<=A->mu;i+)pa=A->rheadi;pb=B->rheadi;/將A, B矩陣的行表頭指針分別賦給pa, pbpre=NULL;while(pb)/當(dāng)pb不等于零if(pa=NULL|pa->j>pb->j)p=(OLink)malloc(sizeof(OLNode);/ 給 p 動(dòng)態(tài)分配空間 if(!pre)A->rheadi=p;else pre->right=p;p->right=pa;pre=

32、p;p->i=i;p->j=pb->j;p->e=pb->e;if(!A->cheadp->j)A->cheadp->j=cpp->j=p;p->down=NULL;/如果A->cheadp->j不等于零，則把p賦給它及cpp->jelsecpp->j->down=p;cpp->j=p;pb=pb->right;/否則把p賦給cpp->jelse if(pa->j<pb->j)pre=pa;pa=pa->right;else if(pa->e+pb-&

33、gt;e) t-;pa->e+=pb->e;pre=pa;pa=pa->right;pb=pb->right;else (t=t-2;if(!pre)A->rheadi=pa->right;else pre->right=pa->right;p=pa;pa=pa->right;if(A->cheadp->j=p)A->cheadp->j=cpp->j=p->down;else cpp->j->down=p->down;free(p);pb=pb->right;A->mu=A-

34、>mu>B->mu?A->mu:B->mu;A->nu=A->nu>B->nu?A->nu:B->nu;/A的行與列為 A及B當(dāng)中較大的一個(gè)return 1;/十字鏈表相加int MultSMatrix_OL(CrossList M, CrossList N, CrossList &Q)(一int i, j, e;中間變量OLink p0, q0, p, pl, pla;中間變量if(M.nu != N.mu)/檢查稀疏矩陣M的列數(shù)和N的行數(shù)是否對(duì)應(yīng)相等(printf ("稀疏矩陣A的列數(shù)和B的行數(shù)不相等，不能

35、相乘。n");return 0;Q.mu = M.mu, Q.nu = N.nu, Q.tu = 0;if(!(Q.rhead = (OLink *)malloc(Q.mu + 1) * sizeof(OLink) exit(-2);if(!(Q.chead = (OLink *)malloc(Q.nu + 1) * sizeof(OLink) exit(-2);for(i = 1; i <= Q.mu; i+) Q.rheadi = NULL;for(i = 1; i <= Q.nu; i+) Q.cheadi = NULL;/相乘for(i =1; i <= Q

36、.mu; i+)for(j = 1; j <= Q.nu; j+)(p0 = M.rheadi, q0 = N.cheadj, e = 0;while(p0&&q0)/M第i行和N第j列有元素(if( p0->j > q0->i) q0 = q0->down; /M的列大于N的行，則N的列指針后移 else if(p0->j < q0->i) p0 = p0->right;/M的列小于N的行，則M的行指針右移else (/M的行等于N的列e += p0->e * q0->e;乘積累加q0 = q0->dow

37、n, p0 = p0->right;移動(dòng)指針 if(e)乘積不為(if(!(p = (OLink)malloc(sizeof(OLNode) exit(-2);Q.tu+;/非零元素增加p->i = i, p->j = j, p->e = e, p->right = NULL, p->down = NULL;/ 賦值，指針后移 將p®入十字鏈表，行插入if(Q.rheadi = NULL)若p為該行的第個(gè)結(jié)點(diǎn)Q.rheadi = pl = p;/p插在該行的表頭且pl指向p(該行的最后一個(gè)結(jié)點(diǎn))else pl->right = p, pl =

38、 p;插在pl所指結(jié)點(diǎn)之后，pl右移列插入if(Q.cheadj = NULL)/若p為該列的第一個(gè)結(jié)點(diǎn)Q.cheadj = p;該列的表頭指向pelse 插在列表尾pla = Q.cheadj;/pla指向j行的第個(gè)結(jié)點(diǎn) while(pla->down) pla = pla->down;/pla 指向 j 行最后一個(gè)結(jié)點(diǎn) pla->down = p; return 1;/十字鏈表相乘 int ShowMAtrix(CrossList *A)int col;OLink p;for(col=1;col<=A->mu;col+)if(A->rheadcol)p=

39、A->rheadcol;while(p)printf("%3d%3d%3dn”,p->i,p->j,p->e);p=p->right;return 1;/十字鏈表顯示void main()int n,i;TSMatrix M,T,S;CrossList MM,TT,SS;printf(" *稀疏矩陣應(yīng)用*");printf("n請(qǐng)你選擇創(chuàng)建稀疏矩陣的方法：n1 ：用三元組創(chuàng)建稀疏矩陣n2:用十字鏈表創(chuàng)建稀疏矩 陣n3:退出程序");printf("n");scanf("%d",&