數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---稀疏矩陣

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：docx 頁數(shù)：34 大?。?09.32KB 人氣指數(shù)：12 舉報 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---稀疏矩陣_第1頁

已閱讀1頁，還剩33頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　稀疏矩陣應(yīng)用　　摘要本課程設(shè)計主要實現(xiàn)在三元組存儲結(jié)構(gòu)與十字鏈表存儲結(jié)構(gòu)下輸入稀疏矩陣，并對稀疏矩陣進(jìn)行轉(zhuǎn)置，相加，相乘操作，最后輸出運(yùn)算后的結(jié)果。在程序設(shè)計中，考慮到方法的難易程度，采用了先用三元組實現(xiàn)稀疏矩陣的輸入，輸出，及其轉(zhuǎn)置，相加，相乘操作的方法，再在十字鏈表下實現(xiàn)。程序通過調(diào)試運(yùn)行，結(jié)果與預(yù)期一樣，初步實現(xiàn)了設(shè)計目標(biāo)

2、。　　關(guān)鍵詞程序設(shè)計；稀疏矩陣；三元組；十字鏈表　　1 引言　　課程設(shè)計任務(wù)　　本課程設(shè)計主要實現(xiàn)在三元組存儲結(jié)構(gòu)與十字鏈表存儲結(jié)構(gòu)下輸入稀疏矩陣，并對稀疏矩陣進(jìn)行轉(zhuǎn)置，相加，相乘操作，最后輸

3、出運(yùn)算后的結(jié)果。稀疏矩陣采用三元組和十字鏈表表示，并在兩種不同的存儲結(jié)構(gòu)下，求兩個具有相同行列數(shù)的稀疏矩陣A和B的相加矩陣C，并輸出C；求出A的轉(zhuǎn)置矩陣D，輸出D；求兩個稀疏矩陣A和B的相乘矩陣E，并輸出E。　　課程設(shè)計性質(zhì)　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計是重要地實踐性教學(xué)環(huán)節(jié)。在進(jìn)行了程序設(shè)計語言課和《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)的

4、基礎(chǔ)上，設(shè)計實現(xiàn)相關(guān)的數(shù)據(jù)結(jié)構(gòu)經(jīng)典問題，有助于加深對數(shù)據(jù)結(jié)構(gòu)課程的認(rèn)識。本課程設(shè)計是數(shù)據(jù)結(jié)構(gòu)中的一個關(guān)于稀疏矩陣的算法的實現(xiàn)，包括在三元組和十字鏈表下存儲稀疏矩陣，并對輸入的稀疏矩陣進(jìn)行轉(zhuǎn)置，相加，相乘等操作，最后把運(yùn)算結(jié)果輸出。此課程設(shè)計要求對數(shù)組存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)非常熟悉，并能熟練使用它們。　　1.3課程設(shè)計目的<p&g

5、t;　　其目的是讓我們在學(xué)習(xí)完C、數(shù)據(jù)結(jié)構(gòu)等課程基礎(chǔ)上，掌握多維數(shù)組的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)、掌握稀疏矩陣的壓縮存儲及轉(zhuǎn)置，相加，相乘等基本操作，并用不同的方法輸出結(jié)果，進(jìn)一步掌握設(shè)計、實現(xiàn)較大系統(tǒng)的完整過程，包括系統(tǒng)分析、編碼設(shè)計、系統(tǒng)集成、以及調(diào)試分析，熟練掌握數(shù)據(jù)結(jié)構(gòu)的選擇、設(shè)計、實現(xiàn)以及操作方法，為進(jìn)一步的應(yīng)用開發(fā)打好基礎(chǔ)。　　需求分析

6、;　　2.1設(shè)計函數(shù)建立稀疏矩陣及初始化值和輸出稀疏矩陣的值　　本模塊要求設(shè)計函數(shù)建立稀疏矩陣并初始化，包括在三元組結(jié)構(gòu)下和十字鏈表結(jié)構(gòu)下。首先要定義兩種不同的結(jié)構(gòu)體類型，在創(chuàng)建稀疏矩陣時，需要設(shè)計兩個不同的函數(shù)分別在三元組和十字鏈表下創(chuàng)建稀疏矩陣，在輸入出現(xiàn)錯誤時，能夠?qū)﹀e誤進(jìn)行判別處理，初始化稀疏矩陣都為空值，特別注意在十字鏈表下，對變量進(jìn)行動態(tài)的地址分配。在設(shè)計輸出稀

7、疏矩陣的值的函數(shù)時，也要針對兩種不同的情況，分別編制函數(shù)，才能準(zhǔn)確的輸出稀疏矩陣。在對稀疏矩陣進(jìn)行初始化及輸出值時，均只輸出非零元素的值和它所在的所在行及所在列。　　2.2構(gòu)造函數(shù)進(jìn)行稀疏矩陣的轉(zhuǎn)置并輸出結(jié)果　　本模塊要求設(shè)計函數(shù)進(jìn)行稀疏矩陣的轉(zhuǎn)置并輸出轉(zhuǎn)置后的結(jié)果，由于對稀疏函數(shù)的轉(zhuǎn)置只對一個矩陣進(jìn)行操作，所以實現(xiàn)起來難度不是很大，函數(shù)也比較容易編寫。

8、在編寫函數(shù)時，要先定義一個相應(yīng)的結(jié)構(gòu)體變量用于存放轉(zhuǎn)置后的矩陣，最后把此矩陣輸出。　　2.3構(gòu)造函數(shù)進(jìn)行兩個稀疏矩陣相加及相乘并輸出最終的稀疏矩陣　　本模塊要求設(shè)計相加和相乘函數(shù)對兩個矩陣進(jìn)行運(yùn)算，并輸出最終的稀疏矩陣，在進(jìn)行運(yùn)算前，要對兩個矩陣進(jìn)行檢查，看是不是相同類型的矩陣，因為兩個矩陣相加要求兩個矩陣一定是同一類型的矩陣，定義相應(yīng)的矩陣類型用于存放

9、兩個矩陣相加相乘后的結(jié)果矩陣，這個結(jié)果矩陣的行數(shù)列數(shù)需要綜合多方面情況來確定。這四個函數(shù)也是整個程序的難點，需要靈活運(yùn)用數(shù)組及指針的特點。　　2.4退出系統(tǒng)　　本模塊要求設(shè)置選項能隨時結(jié)束程序的運(yùn)行，本程序中采用exit(0)函數(shù)。程序以用戶和計算機(jī)的對話方式執(zhí)行，即在計算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上

10、輸入演示程序中需要的相關(guān)信息及命令。　　概要設(shè)計　　3.1主界面設(shè)計　　為了實現(xiàn)在兩種存儲結(jié)構(gòu)下對稀疏矩陣的多種算法功能的管理，首先設(shè)計一個含有多　　個菜單項的主控菜單子程序以鏈接系統(tǒng)的各項子功能

11、，方便用戶交互式使用本系統(tǒng)。本系　　統(tǒng)主控菜單運(yùn)行界面如圖1所示。　　圖1主界面圖　　3.2存儲結(jié)構(gòu)設(shè)計　　本系統(tǒng)采用三元組結(jié)構(gòu)和十字鏈表結(jié)構(gòu)存儲稀疏矩陣的具體信息。其中：在三元組中，所有元素的信

12、息用數(shù)組表示，每個數(shù)組元素中包含有行下標(biāo)(i)，列下標(biāo)(j)和對應(yīng)的數(shù)值(e)，它們是整型數(shù)據(jù)，全部的信息用在十字鏈表中，全部結(jié)點的信息用結(jié)構(gòu)體（TSMatrix）包含，包括用數(shù)組（Triple data[MAXSIZE]）和總共的行數(shù)（mu）,列數(shù)（nu）以及非零元素的個數(shù)(tu)。在十字鏈表下，頭結(jié)點為指針數(shù)組的十字鏈表存儲；每個結(jié)點里面包含行下標(biāo)(i)，列下標(biāo)(j)和對應(yīng)的數(shù)值(e)，它們是整型數(shù)據(jù)，還有兩個指針(right)、(

13、down),屬于OLNode結(jié)構(gòu)體。全部的信息用結(jié)構(gòu)體(crosslist)包含，包括指針數(shù)組(OLink* rhead和*chead）和總共的行數(shù)（mu）,列數(shù)（nu）以及非零元素的個數(shù)(tu)。　　三元組結(jié)構(gòu)體定義:　　typedef struct{

14、int i,j;　　int e;　　}Triple;　　typedef struct{　　Triple data[MAXSIZE];

15、　int rpos[MAXSIZE + 1]; 　　int nu,mu,tu;　　}TSMatrix; 　　十字鏈表結(jié)構(gòu)體定義: 　　typedef struct OLNode{　　int i

16、,j;　　int e;　　struct OLNode *right,*down;　　}OLNode,*OLink;　　typedef struct {　　int mu,nu

17、,tu;　　OLink *rhead,*chead;　　}CrossList; 　　3.3系統(tǒng)功能設(shè)計　　本系統(tǒng)除了要完成分別在三元組存儲結(jié)構(gòu)以及在十字鏈表下實現(xiàn)稀疏矩陣的初始化功能外還設(shè)置了4個子功能菜單。稀疏矩陣的建立及初始化在三

18、元組存儲結(jié)構(gòu)下，由函數(shù) void CreateSMatrix(TSMatrix &M)實現(xiàn)，在十字鏈表存儲結(jié)構(gòu)下，由函數(shù)void CreateSMatix_OL(CrossList &M)依據(jù)讀入的行數(shù)和列數(shù)以及非零元素的個數(shù)，分別設(shè)定每個非零元素的信息。4個子功能的設(shè)計描述如下。　?。?）稀疏矩陣的轉(zhuǎn)置：　　此功能在三元組存儲結(jié)構(gòu)下，由

19、函數(shù)void TransposeSMatrix(TSMatrix M,TSMatrix &T)實現(xiàn)，在十字鏈表存儲結(jié)構(gòu)下，由函數(shù)void TurnSMatrix_OL(CrossList &M)實現(xiàn)。當(dāng)用戶選擇該功能，系統(tǒng)提示用戶初始化一個矩陣，然后進(jìn)行轉(zhuǎn)置，最終輸出結(jié)果。　?。?）稀疏矩陣的加法：　　此功能在三元組存儲結(jié)構(gòu)下，由函數(shù)

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

21、功能在三元組存儲結(jié)構(gòu)下，由函數(shù)int MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q)實現(xiàn)。在十字鏈表存儲結(jié)構(gòu)下，由函數(shù)int MultSMatrix_OL(CrossList M, CrossList N, CrossList &Q)實現(xiàn)。當(dāng)用戶選擇該功能，系統(tǒng)提示輸入要進(jìn)行相乘的兩個矩陣的詳細(xì)信息。然后進(jìn)行相乘，最后得到結(jié)果。

22、　　（4）退出：　　即退出稀疏矩陣的應(yīng)用系統(tǒng)，由exit(0)函數(shù)實現(xiàn)。當(dāng)用戶選擇該功能，則退出該稀疏矩陣的應(yīng)用系統(tǒng)。　　4 詳細(xì)設(shè)計　　4.1 數(shù)據(jù)類型定義　　三元組結(jié)構(gòu)體定義

23、:　　typedef struct{ //三元組結(jié)構(gòu)體　　int i,j; //行標(biāo)、列表　　int e;

24、 //值 　　}Triple;　　typedef struct{　　Triple data[MAXSIZE]; //三元組表　　int rpos[MAXSIZE + 1]; &

25、lt;/p>　　int nu,mu,tu; //行數(shù)、列數(shù)、非零元個數(shù)　　}TSMatrix; 　　十字鏈表結(jié)構(gòu)體定義: 　　typedef struct OLNode{ /

26、/結(jié)點結(jié)構(gòu)　　int i,j; //行標(biāo)、列標(biāo) 　　int e; //值　　struct OLNode *right,*down; //同

27、一行、列的下一個結(jié)點　　}OLNode,*OLink;　　typedef struct {　　int mu,nu,tu; //行數(shù)、列數(shù)、非零元個數(shù)　　OLink *rhead,*chead;

28、 //行、列指針基指　　}CrossList; 　　4.2系統(tǒng)主要子程序詳細(xì)設(shè)計　　A. 主程序模塊設(shè)計：　　void main(){　　int n,i;<

29、/p>　　TSMatrix M,T,S; //聲明三個三元組數(shù)組　　CrossList MM,TT,SS; //聲明三個十字鏈表　　printf(" ***稀疏矩陣應(yīng)用***");　　printf("

30、;\n請你選擇創(chuàng)建稀疏矩陣的方法：\n1：用三元組創(chuàng)建稀疏矩陣\n2:用十字鏈表創(chuàng)建稀疏矩陣\n3:退出程序");　　printf("\n");　　scanf("%d",&n);　　switch(n){<b&

31、gt;　　case 1:　　CreateSMatrix(M); //創(chuàng)建三元組矩陣　　printf("您輸入的稀疏矩陣為（只列出非零元素）：\n 行列大小\n");　　ShowTMatrix(M); /

32、/顯示三元組矩陣　　printf("已經(jīng)選擇三元組創(chuàng)建稀疏矩陣，請選擇操作:\n1：稀疏矩陣轉(zhuǎn)置\n2：稀疏矩陣相加\n3：稀疏矩陣相乘\n4：退出程序\n");　　scanf("%d",&i);　　switch(i){

33、case 1:TransposeSMatrix(M,T); //對三元組矩陣進(jìn)行轉(zhuǎn)置　　printf("轉(zhuǎn)置后的矩陣為（只列出非零元素）：\n 行列大小\n");　　ShowTMatrix(T);　　break;&l

34、t;p>　　case 2:printf("請你輸入另一個稀疏矩陣:");　　CreateSMatrix(T);　　AddTMatix(M,T,S); //兩個三元組矩陣相加　　printf("相加后的矩陣為（只列出非零元素）：\n 行列大小\n&

35、quot;);　　ShowTMatrix(S);　　break;　　case 3:printf("請你輸入另一個稀疏矩陣:");　　CreateSMatrix(T);　　M

36、ultSMatrix(M,T,S); //兩個三元組矩陣相乘　　printf("相乘后的矩陣為（只列出非零元素）：\n 行列大小\n");　　ShowTMatrix(S);　　break;

37、;　　case 4:exit(0);};break;　　case 2:{CreateSMatix_OL(MM); //創(chuàng)建十字鏈表矩陣　　printf("您輸入的稀疏矩陣為（只列出非零元素）：\n 行列大小\n");　　ShowMAtrix(&MM); /

38、/顯示十字鏈表矩陣　　printf("已經(jīng)選擇十字鏈表創(chuàng)建稀疏矩陣，請選擇操作: 1：稀疏矩陣轉(zhuǎn)置\n 2：稀疏矩陣相加\n 3：稀疏矩陣相乘\n 4：退出程序\n");　　scanf("%d",&i);　　switch(i){<

39、p>　　case 1:　　TurnSMatrix_OL(MM); //十字鏈表矩陣轉(zhuǎn)置　　printf("轉(zhuǎn)置后的矩陣為（只列出非零元素）：\n 行列大小\n");　　ShowMAtrix(&MM);</p&

40、gt;　　break;　　case 2:　　printf("請你輸入另一個稀疏矩陣:");　　CreateSMatix_OL(TT);　　SMatrix_

41、ADD(&MM,&TT); //兩個十字鏈表矩陣相加 　　printf("相加后的矩陣為（只列出非零元素）：\n 行列大小\n");　　ShowMAtrix(&MM);break;　　case 3:printf("請你輸入另一個稀疏矩陣:&

42、quot;);　　CreateSMatix_OL(TT);　　MultSMatrix_OL(MM,TT,SS); //兩個十字鏈表矩陣相乘　　printf("相乘后的矩陣為（只列出非零元素）：\n 行列大小\n");　　ShowM

43、Atrix(&SS);break;　　case 4:exit(0);　　}};break;　　case 3:exit(0);　　default :printf("erorr");&l

44、t;p>　　}　　}　　B. 稀疏矩陣操作各子函數(shù)的定義：　　(1)建立與初始化稀疏矩陣：　　void CreateSMatrix(TSMatrix &M){//采用三元組順序表存儲

45、表示，創(chuàng)建稀疏矩陣M 　　printf("請輸入稀疏矩陣的行數(shù)、列數(shù)和非零元個數(shù)：");　　scanf("%d%d%d",&M.mu,&M.nu,&M.tu);　　if((M.mu<=0)||(M.nu<=0)||(M.tu<=0)

46、||(M.tu>M.mu*M.nu))　　//判斷行值、列值、元素個數(shù)是否合法　　printf("輸入有誤！");　　for(int i=1;i<=M.tu;i++){//輸入稀疏矩陣元素　　printf("請輸入元素坐標(biāo)(所在行

47、，所在列）及大?。?quot;);　　scanf("%d%d%d",&M.data[i].i,&M.data[i].j,&M.data[i].e);　　if((M.data[i].i<=0)||(M.data[i].j<=0)){　　printf("

48、;輸入錯誤，請重新輸入");　　scanf("%d%d%d",&M.data[i].i,&M.data[i].j,&M.data[i].e);　　}　　}<

49、;p>　　int num[100];　　if(M.tu)　　{int i;　　for(i = 1; i <= M.mu; i++) num[i] = 0;//初始化　　for(int

50、t = 1; t <= M.tu; t++) ++num[M.data[t].i];　　//求M中每一行含非零元素個數(shù)　　//求rpos　　M.rpos[1] = 1;　　for(i = 2; i <= M.mu; i++

51、) M.rpos[i] = M.rpos[i-1] + num[i-1];　　}　　} //創(chuàng)建三元組　　int CreateSMatix_OL(CrossList &M){　　int i

52、,j,e;　　OLink q;　　OLink p;　　printf("請輸入稀疏矩陣的行數(shù)，列數(shù)，非零元素的個數(shù)"); //矩陣行數(shù)，列數(shù)下標(biāo)均從開始；　　scanf(&

53、quot;%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(OLNode));//分配內(nèi)存空間

54、　　for( i=1;i<=M.mu;i++)M.rhead[i]=NULL;//把矩陣每個元素置空值　　for( i=1;i<=M.nu;i++)M.chead[i]=NULL;　　printf("請輸入稀疏矩陣，如果行為，則退出\n");　　scanf(&q

55、uot;%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.rhead[i]==

56、NULL||M.rhead[i]->j>j){p->right=M.rhead[i];M.rhead[i]=p;}　　else{　　q=M.rhead[i];　　while(q->right&&q->right->j<

57、j)q=q->right;　　p->right=q->right;　　q->right=p;}　　if(M.chead[j]==NULL||M.chead[j]->i>i){p->down=M.chead[j];M.chead[j]=p;}<

58、p>　　else{　　q=M.chead[j];　　while(q->down&&q->down->i<i)q=q->down;　　p->down=q->down;　　q

59、->down=p;　　}　　scanf("%d%d%d",&i,&j,&e);　　}　　return 1;&

60、lt;/p>　　}//創(chuàng)建十字鏈表　?。?）輸出稀疏矩陣：　　void ShowTMatrix(TSMatrix M){　　for(int col=1;col<=M.mu;col++)　　//通過雙重

61、循環(huán)，把稀疏矩陣中不為零的元素的行數(shù)、列數(shù)和值顯示出來　　for(int p=1;p<=M.tu;p++)　　if(M.data[p].i==col)printf("%4d %4d %4d\n",M.data[p].i,M.data[p].j,M.data[p].e);

62、　　}//三元組顯示　　int ShowMAtrix(CrossList *A){　　int col;　　OLink p;　　for(col=1;col<=A->m

63、u;col++)if(A->rhead[col]){p=A->rhead[col];　　//通過循環(huán)，把A結(jié)點的rhead[col]賦給p　　while(p){printf("%3d%3d%3d\n",p->i,p->j,p->e);p=p->right;}

64、　　}　　return 1;　　}//十字鏈表顯示　?。?）實現(xiàn)矩陣的轉(zhuǎn)置：　　void TransposeSMatrix(TSMatrix M,TSMatr

65、ix &T){　　T.nu=M.mu;//T矩陣存放轉(zhuǎn)置后的矩陣　　T.mu=M.nu;　　T.tu=M.tu;　　int q=1;　　for(int col=1;col<=M.

66、nu;col++)//通過循環(huán)，把非零元素的行數(shù)與列數(shù)進(jìn)行交換，實現(xiàn)轉(zhuǎn)置　　for(int p=1;p<=M.tu;p++)　　if(M.data[p].j==col){　　T.data[q].i=M.data[p].j;　　T.data[q].j=M.data[p

67、].i;　　T.data[q].e=M.data[p].e;　　q++;　　}　　}//三元組轉(zhuǎn)置　　void

68、TurnSMatrix_OL(CrossList &M){　　int col,row; //定義循環(huán)變量　　OLink p,q; //定義OLink結(jié)構(gòu)類型變量　　for(col=1;col<=M.mu;col++) //通過循環(huán)，把非零元素的行數(shù)與列數(shù)進(jìn)行交換，實現(xiàn)轉(zhuǎn)置

69、　　{ q=p=M.rhead[col];　　while(q){　　row=p->i;　　p->i=p->j;　　p->j=row

70、;　　q=p->right;　　p->right=p->down;　　p->down=q;　　}　　}<

71、/p>　　}//十字鏈表轉(zhuǎn)置　?。?）實現(xiàn)兩個矩陣的相加：　　void AddTMatix(TSMatrix M,TSMatrix T,TSMatrix &S){　　//矩陣S存放相加后的矩陣　　S

72、.mu=M.mu>T.mu?M.mu:T.mu;//對S矩陣的行數(shù)賦值　　S.nu=M.nu>T.nu?M.nu:T.nu;//對S矩陣的列數(shù)賦值　　S.tu=0;　　int ce;

73、　int q=1;int mcount=1,tcount=1;　　while(mcount<=M.tu&&tcount<=T.tu){　　switch(Compare(M.data[mcount].i,M.data[mcount].j,T.data[tcount].i,T.data[tcount].j))

74、　　//用switch分支語句，用compare函數(shù)對需要相加的兩個矩陣的某元素行數(shù)列數(shù)進(jìn)行比較　　{case -1: S.data[q].e=M.data[mcount].e;//當(dāng)M.data[mcount].i<T.data[tcount].i或M.data[mcount].j<T.data[tcount].j　　S

75、.data[q].i=M.data[mcount].i;　　S.data[q].j=M.data[mcount].j;　　//把第一個矩陣的行數(shù)i，列數(shù)j賦值給S矩陣的行數(shù)i，列數(shù)j　　q++;　　mcount++; </p&g

76、t;　　break;　　case 1: S.data[q].e=T.data[tcount].e;//當(dāng)M.data[mcount].i>T.data[tcount].i或M.data[mcount].j>T.data[tcount].j　　S.data[q].i=T.data[tc

77、ount].i;　　S.data[q].j=T.data[tcount].j;　　//把第二個矩陣的行數(shù)i，列數(shù)j賦值給S矩陣的行數(shù)i，列數(shù)j　　q++;　　tcount++; <b&g

78、t;　　break;　　case 0: ce=M.data[mcount].e+T.data[tcount].e;　　//其他情況下把兩個矩陣的值相加　　if(ce){ S.data[q].e=ce;　　S.data[q].i=M.data[mco

79、unt].i;　　S.data[q].j=M.data[mcount].j;　　q++;　　mcount++;　　tcount++;}　　else {mc

80、ount++;　　tcount++;}　　break;　　}}　　while(mcount<=M.tu){　　S.data[q].e=M.data[

81、mcount].e;　　S.data[q].i=M.data[mcount].i;　　S.data[q].j=M.data[mcount].j;　　q++;　　mcount++; }//在case=-1的情況下對S矩陣的非零值，行數(shù)，

82、列數(shù)進(jìn)行賦值　　while(tcount<=M.tu){　　S.data[q].e=T.data[tcount].e;　　S.data[q].i=T.data[tcount].i;　　S.data[q].j=T.data[tcount].j;

83、　　q++;　　tcount++; 　　}//在case=1的情況下對S矩陣的非零值，行數(shù)，列數(shù)進(jìn)行賦值　　S.tu=q-1;　　}//三元組相加</b&

84、gt;　　int SMatrix_ADD(CrossList *A,CrossList *B){　　OLNode *pa,*pb,*pre,*p,*cp[100]; //定義OLNode類型的變量　　int i,j,t;　　t=A->tu+B->tu;<

85、/p>　　for(j=1;j<=A->nu;j++)cp[j]=A->chead[j];//將A矩陣的列表頭指針賦給cp數(shù)組　　for(i=1;i<=A->mu;i++){　　pa=A->rhead[i];　　pb=B->rhead[i];//

86、將A，B矩陣的行表頭指針分別賦給pa，pb　　pre=NULL;　　while(pb){//當(dāng)pb不等于零　　if(pa==NULL||pa->j>pb->j){　　p=(OLink)malloc(sizeof(OL

87、Node));//給p動態(tài)分配空間　　if(!pre)A->rhead[i]=p;　　else pre->right=p;　　p->right=pa;　　pre=p;　　p-

88、>i=i;p->j=pb->j;p->e=pb->e;　　if(!A->chead[p->j]){　　A->chead[p->j]=cp[p->j]=p;　　p->down=NULL;　　}//如果A-&g

89、t;chead[p->j]不等于零，則把p賦給它及cp[p->j]　　else{　　cp[p->j]->down=p;　　cp[p->j]=p;　　}</p&g

90、t;　　pb=pb->right;　　}//否則把p賦給cp[p->j]　　else if(pa->j<pb->j){pre=pa;　　pa=pa->right;}　　else if(pa->e+pb->

91、;e){　　t--;　　pa->e+=pb->e;　　pre=pa;　　pa=pa->right;　　pb=pb->right;}

92、　　else { t=t-2;　　if(!pre)A->rhead[i]=pa->right;　　else pre->right=pa->right;　　p=pa;pa=pa->right;

93、if(A->chead[p->j]==p)A->chead[p->j]=cp[p->j]=p->down;　　else cp[p->j]->down=p->down;　　free(p);　　pb=pb->right;

94、　　}　　}　　}　　A->mu=A->mu>B->mu?A->mu:B->mu;

95、;　　A->nu=A->nu>B->nu?A->nu:B->nu;//A的行與列為A及B當(dāng)中較大的一個　　return 1;　　}//十字鏈表相加　　（5）實現(xiàn)兩個矩陣的相乘：&

96、lt;p>　　int MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q)　　{　　int arow, brow, ccol, i, t, ctemp[100], p, q, tp; 　　//定義相乘函數(shù)中所需要用到

97、的變量　　if(M.nu != N.mu) return 0;　　//如果第一個矩陣的行數(shù)不等于第二個矩陣的列數(shù)，則退出　　Q.mu = M.mu, Q.nu = N.nu, Q.tu = 0;//三元組結(jié)構(gòu)類型Q存放相乘后的結(jié)果　　if(M.tu * N.tu != 0

98、)//如果兩個矩陣元素相乘不為零，則進(jìn)行運(yùn)算　　{　　for(arow = 1; arow <= M.mu; ++arow)；//最外側(cè)循環(huán)以矩陣行數(shù)作為循環(huán)變量　　{　　for(i = 0

99、; i <= N.nu; ++i) ctemp[i] = 0;　　Q.rpos[arow] = Q.tu + 1;　　if(arow < M.mu) tp = M.rpos[arow + 1];　　else tp = M.tu +1;　　for(p = M.r

100、pos[arow]; p < tp; ++p)//把每行與每列相乘　　{　　brow = M.data[p].j; 　　if(brow < N.mu) t = N.rpos[brow+1];　　else t

101、= N.tu + 1;　　for(q = N.rpos[brow]; q < t; ++q)　　{　　ccol = N.data[q].j; 　　ctemp[ccol] += M.data[p].e * N.data[q

102、].e;//值相乘　　}　　}　　for(ccol = 1; ccol <= Q.nu; ++ccol) //把運(yùn)算后的結(jié)果存放到Q中　　{</p

103、>　　if(ctemp[ccol])　　{　　if(++(Q.tu) > MAXSIZE) return 1;　　Q.data[Q.tu].i = arow, Q.data[Q.tu].j = ccol, Q.data[Q.tu].e = c

104、temp[ccol]; 　　} 　　}　　} 　　}&l

105、t;b>　　return 1;　　}//三元組相乘　　int MultSMatrix_OL(CrossList M, CrossList N, CrossList &Q)　　{&l

106、t;p>　　int i, j, e; //中間變量　　OLink p0, q0, p, pl, pla; //中間變量　　if(M.nu != N.mu) //檢查稀疏矩陣M的列數(shù)和N的行數(shù)是否對應(yīng)相等　　{&l

107、t;/p>　　printf ( "稀疏矩陣A的列數(shù)和B的行數(shù)不相等，不能相乘。\n" );　　return 0; 　　}　　Q.mu = M.mu, Q.nu = N.nu, Q.tu = 0;<

108、;p>　　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

109、++) Q.rhead[i] = NULL;　　for(i = 1; i <= Q.nu; i++) Q.chead[i] = NULL; //相乘　　for(i =1; i <= Q.mu; i++)　　for(j = 1; j <= Q.nu; j++)<p&g

110、t;　　{　　p0 = M.rhead[i], q0 = N.chead[j], e = 0;　　while(p0&&q0) //M第i行和N第j列有元素　　{<p&g

111、t;　　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

112、的列　　e += p0->e * q0->e; //乘積累加　　q0 = q0->down, p0 = p0->right; //移動指針　　}　　}</b

113、>　　if(e) //乘積不為零　　{　　if(!(p = (OLink)malloc(sizeof(OLNode)))) exit(-2);　　Q.tu++

114、;//非零元素增加　　p->i = i, p->j = j, p->e = e, p->right = NULL, p->down = NULL;　　//賦值，指針后移　　//將p插入十字鏈表<b&

115、gt;　　//行插入　　if(Q.rhead[i] == NULL) //若p為該行的第個結(jié)點　　Q.rhead[i] = pl = p; //p插在該行的表頭且pl指向p(該行的最后一個結(jié)點)　　else pl->right = p, pl = p; //插在pl所指

116、結(jié)點之后，pl右移　　//列插入　　if(Q.chead[j] == NULL) //若p為該列的第一個結(jié)點　　Q.chead[j] = p; //該列的表頭指向p　　else {//插在

117、列表尾　　pla = Q.chead[j];//pla指向j行的第個結(jié)點　　while(pla->down) pla = pla->down;//pla指向j行最后一個結(jié)點　　pla->down = p; 　　}&l

118、t;/p>　　}　　}　　return 1;　　}//十字鏈表相乘　　調(diào)試

119、分析　　5.1系統(tǒng)運(yùn)行主界面　　系統(tǒng)運(yùn)行主界面如圖2所示：　　圖2 主界面圖　　5.2 各子功能測試運(yùn)行結(jié)果　?。?）稀疏矩陣的創(chuàng)建及初始化：<

120、;p>　　在主菜單下，用戶輸入1回車，是用三元組創(chuàng)建稀疏矩陣，根據(jù)屏幕提示初始化一個稀疏矩陣，按enter鍵，運(yùn)行結(jié)果如圖3所示。　　圖3 三元組創(chuàng)建并初始化矩陣　　在主菜單下，用戶輸入2回車，是用十字鏈表創(chuàng)建稀疏矩陣，根據(jù)屏幕提示初始化　　一個稀疏矩陣，按enter鍵，運(yùn)行結(jié)果如圖4所示。</p&g

121、t;　　圖4 十字鏈表創(chuàng)建并初始化矩陣　　（2）稀疏矩陣的轉(zhuǎn)置：　　用三元組創(chuàng)建稀疏矩陣后，用戶輸入1回車，便顯示該矩陣的轉(zhuǎn)置矩陣，運(yùn)行結(jié)果如圖5所示。　　圖5 三元組稀疏矩陣轉(zhuǎn)置結(jié)果示意圖　　用十字鏈表創(chuàng)建稀疏矩陣后，用戶輸入1回車，便顯示該矩陣的

122、轉(zhuǎn)置矩陣，運(yùn)行結(jié)果如圖6所示。　　圖6 十字鏈表稀疏矩陣轉(zhuǎn)置結(jié)果示意圖　?。?）稀疏矩陣的相加：　　用三元組創(chuàng)建并初始化一個稀疏矩陣后，輸入2回車，按屏幕提示輸入第二個同類型的稀疏矩陣，按enter鍵，運(yùn)行結(jié)果如圖7所示。　　圖7 三元組稀疏矩陣相加結(jié)果示意圖</p

123、>　　用十字鏈表創(chuàng)建并初始化一個稀疏矩陣后，輸入2回車，按屏幕提示輸入第二個同類型的稀疏矩陣，按enter鍵，運(yùn)行結(jié)果如圖8所示。　　圖8 三元組稀疏矩陣相加結(jié)果示意圖　?。?）稀疏矩陣的相乘：　　用三元組創(chuàng)建并初始化一個稀疏矩陣后，輸入3回車，按屏幕提示輸入第二個同類型的稀疏矩陣，按

124、enter鍵，運(yùn)行結(jié)果如圖9所示。　　圖9 三元組稀疏矩陣相乘結(jié)果示意圖　　用十字鏈表創(chuàng)建并初始化一個稀疏矩陣后，輸入3回車，按屏幕提示輸入第二個同類型的稀疏矩陣，按enter鍵，運(yùn)行結(jié)果如圖10所示。　　圖10 十字鏈表稀疏矩陣相乘結(jié)果示意圖　?。?）

125、退出：　　在主菜單下，用戶輸入3回車，或者在下級菜單中輸入4回車，退出程序。運(yùn)行結(jié)果如圖11，圖12。　　圖11 主菜單退出程序圖　　圖12 下級菜單退出程序圖　　總結(jié)

126、由于本程序要求用兩種辦法對稀疏矩陣進(jìn)行運(yùn)算，特別是用十字鏈表這種形式來對稀　　疏矩陣進(jìn)行運(yùn)算，是實現(xiàn)起來有很多困難，主要包括：　　1、書上這種方面的東西不多，資料少，可以參考的東西不是很多；　　2、用十字鏈表進(jìn)行運(yùn)算比較復(fù)雜，難度較大，需要對指針掌握較好；　　3、在書寫課

127、程設(shè)計報告時，沒有具體的模板，感覺無從下手。　　針對上述困難，自己對癥下藥，通過網(wǎng)絡(luò)，圖書館找資料，借鑒別人的已往的優(yōu)秀的課程設(shè)計報告，和同學(xué)們一起討論，逐步地解決自己的問題。　　通過此次課程設(shè)計，使我對本學(xué)期學(xué)的《數(shù)據(jù)結(jié)構(gòu)》有了更深的了解，也使自己的所學(xué)更加牢固，并能夠把更方面的知識綜合起來運(yùn)用。<b&g

128、t;　　參考文獻(xiàn)　　[1]王立柱.C/C++與數(shù)據(jù)結(jié)構(gòu).北京：清華大學(xué)出版社，2002　　[2]顧元剛.數(shù)據(jù)結(jié)構(gòu)簡明教程.南京：東南大學(xué)出版社等，2003　　[3]郭福順，王曉芬，李蓮治《數(shù)據(jù)結(jié)構(gòu)》（修訂本），大連理工大學(xué)出版社，1997　　[4

129、] [美]Mark Allen Weiss，數(shù)據(jù)結(jié)構(gòu)與算法分析——C語言描述(英文版?第2版)，人民郵電出版社，2005.8　　[5] 李春葆著，數(shù)據(jù)結(jié)構(gòu)教程，清華大學(xué)出版社，2005.1　　附錄：程序源代碼　　#include<stdio.h></p&g

130、t;　　#include<stdlib.h>　　#define MAXSIZE 100　　int num[100];　　typedef struct OLNode{　　int i,j;</p&g

131、t;　　int e;　　struct OLNode *right,*down;　　}OLNode,*OLink;　　typedef struct {　　int mu,nu,tu;<p

132、>　　OLink *rhead,*chead;　　}CrossList; //十字鏈表結(jié)構(gòu)體定義 　　typedef struct{　　int i,j;　　int e;&

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---稀疏矩陣

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---稀疏矩陣

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載