基于三元組表的存儲結(jié)構(gòu)實(shí)現(xiàn)稀疏矩陣的應(yīng)用課程設(shè)計

1、<p>　　數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計</p><p>　　設(shè)計題目：基于三元組表的存儲結(jié)構(gòu)實(shí)現(xiàn)稀疏矩陣的應(yīng)用</p><p>　　學(xué)生姓名： </p><p>　　專業(yè)班級： </p><p>　　指導(dǎo)教師：

2、 </p><p>　　完成時間： </p><p>　　信息工程學(xué) 院 信科 系</p><p>　　課程設(shè)計成績評定表(本科)</p><p><b>　　目 錄</b></p><p>　　一、課題設(shè)計

3、目的及意義1</p><p>　　1.1、課題設(shè)計目的1</p><p>　　1.2、課程設(shè)計意義1</p><p><b>　　二、需求分析1</b></p><p>　　2.1設(shè)計函數(shù)建立稀疏矩陣及初始化值和輸出稀疏矩陣的值1</p><p>　　2.2 構(gòu)造函數(shù)進(jìn)行稀疏矩陣的轉(zhuǎn)置并

4、輸出結(jié)果1</p><p>　　2.3 構(gòu)造函數(shù)進(jìn)行兩稀疏矩陣相加、減及相乘并輸出最終稀疏矩陣1</p><p>　　2.4 退出系統(tǒng)2</p><p><b>　　三、項目設(shè)計2</b></p><p><b>　　3.1結(jié)構(gòu)設(shè)計2</b></p><p><

5、;b>　　3.2算法思想2</b></p><p><b>　　3.3模塊圖2</b></p><p><b>　　3.4流程圖3</b></p><p><b>　　四、系統(tǒng)實(shí)現(xiàn)4</b></p><p><b>　　4.1主調(diào)函數(shù)4&l

6、t;/b></p><p>　　4.2三元組表建立4</p><p><b>　　4.3矩陣建立4</b></p><p>　　4.4矩陣相加減及轉(zhuǎn)置5</p><p><b>　　五、系統(tǒng)調(diào)試8</b></p><p>　　5.1主菜單輸出8</p&g

7、t;<p><b>　　5.2矩陣相加9</b></p><p><b>　　5.3矩陣轉(zhuǎn)置9</b></p><p>　　5.4矩陣相減10</p><p><b>　　六、實(shí)驗總結(jié)10</b></p><p><b>　　七、附錄11<

8、;/b></p><p>　　一、課題設(shè)計目的及意義</p><p>　　1.1、課題設(shè)計目的 </p><p>　　(1)掌握稀疏矩陣三元組表的存儲，創(chuàng)建，顯示，轉(zhuǎn)置等方法。</p><p>　　(2)利用三元組表實(shí)現(xiàn)矩陣的相加，減。 </p><p>　　(3)了解稀疏矩陣的相關(guān)應(yīng)用。</p&g

9、t;<p>　　1.2、課程設(shè)計意義</p><p>　　本次課題設(shè)計可以使我們更熟練的掌握有關(guān)三元組表及稀疏矩陣的相關(guān)知識，比一般存儲方法節(jié)省了存儲空間，基于三元組表的存儲結(jié)構(gòu)實(shí)現(xiàn)了稀疏矩陣的基本操作。</p><p>　　本次課程設(shè)計是本組成員共同努力而完成的，第一次進(jìn)行課程設(shè)計是我們的探索過程，這個過程中，我們克服了一個個困難，在摸索中前行，我們相信通過此次課程設(shè)計我們

10、每個人都會對數(shù)據(jù)結(jié)構(gòu)這門課程有更深一步的了解。</p><p><b>　　二、需求分析</b></p><p>　　稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲和計算可以大大節(jié)省存儲空間，提高計算效率。實(shí)現(xiàn)一個能進(jìn)行稀疏矩陣基本運(yùn)算的運(yùn)算器。以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實(shí)現(xiàn)兩個矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三

11、元組表示，而運(yùn)算結(jié)果的矩陣則通常以陣列形式列出。</p><p>　　2.1設(shè)計函數(shù)建立稀疏矩陣及初始化值和輸出稀疏矩陣的值</p><p>　　本模塊要求設(shè)計函數(shù)建立稀疏矩陣并初始化，包括在三元組結(jié)構(gòu)下和十字鏈表結(jié)構(gòu)下。在創(chuàng)建稀疏矩陣時，需要設(shè)計兩個不同的函數(shù)分別在三元組和十字鏈表下創(chuàng)建稀疏矩陣，在輸入出現(xiàn)錯誤時，能夠?qū)﹀e誤進(jìn)行判別處理，初始化稀疏矩陣都為空值。在設(shè)計輸出稀疏矩陣的值的函

12、數(shù)時，也要針對兩種不同的情況，分別編制函數(shù)，才能準(zhǔn)確的輸出稀疏矩陣。在對稀疏矩陣進(jìn)行初始化時，只輸入非零元素的值和它所在的所在行及所在列。在對稀疏矩陣輸出時，以矩陣的完整形式輸出。</p><p>　　2.2 構(gòu)造函數(shù)進(jìn)行稀疏矩陣的轉(zhuǎn)置并輸出結(jié)果 </p><p>　　本模塊要求設(shè)計函數(shù)進(jìn)行稀疏矩陣的轉(zhuǎn)置并輸出轉(zhuǎn)置后的結(jié)果。在編寫函數(shù)時，要先定義一個相應(yīng)的結(jié)構(gòu)體變量用于存放轉(zhuǎn)置后的矩陣，最

13、后把此矩陣輸出。 </p><p>　　2.3 構(gòu)造函數(shù)進(jìn)行兩稀疏矩陣相加、減及相乘并輸出最終稀疏矩陣</p><p>　　本模塊要求設(shè)計相加、減和相乘函數(shù)對兩個矩陣進(jìn)行運(yùn)算，并輸出最終的稀疏矩陣，定義相應(yīng)的矩陣類型用于存放兩個矩陣操作后的結(jié)果矩陣，這個結(jié)果矩陣的行、列數(shù)需要綜合多方面情況來確定。這些函數(shù)也是整個程序的難點(diǎn)，需要靈活運(yùn)用數(shù)組及指針的特點(diǎn)。</p><p&

14、gt;<b>　　2.4 退出系統(tǒng) </b></p><p>　　本模塊要求設(shè)置選項能隨時結(jié)束程序的運(yùn)行，本程序中采用do-while循環(huán)。程序在計算機(jī)上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中需要的相關(guān)信息及命令。 </p><p><b>　　三、項目設(shè)計</b></p><p><b>　　3.1

15、結(jié)構(gòu)設(shè)計</b></p><p>　　1、以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實(shí)現(xiàn)兩個矩陣相加、相減和相乘的運(yùn)算</p><p>　　2、稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)果的矩陣則通常以陣列形式列出。</p><p><b>　　3.2算法思想</b></p><p>　　1、首先應(yīng)輸

16、入矩陣的行數(shù)和列數(shù)。</p><p>　　2、 以“帶行邏輯鏈接信息”的三元組順序表表數(shù)，并判別給出的兩個矩陣的行、列數(shù)對于所要求作的運(yùn)算是否相匹配?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過20。</p><p>　　3、程序可以對三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教材的算法，以便提高計算效率。5.在用三元組表示稀疏矩陣時，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可用二維數(shù)組存放。

17、</p><p>　　4、主函數(shù)設(shè)置循環(huán)和選擇語句進(jìn)行運(yùn)算循環(huán)和選擇，進(jìn)行稀疏矩陣的加法，減法和轉(zhuǎn)置。</p><p><b>　　3.3模塊圖</b></p><p><b>　　3.4流程圖</b></p><p><b>　　四、系統(tǒng)實(shí)現(xiàn)</b></p>&

18、lt;p><b>　　4.1主調(diào)函數(shù)</b></p><p>　　#include<stdio.h></p><p>　　#define smax 16</p><p>　　typedef int datatype;</p><p>　　typedef struct</p><p&g

19、t;　　{ int i, j;</p><p>　　datatype v;</p><p><b>　　} node;</b></p><p>　　typedef struct()</p><p>　　{ int m ,n,t;</p><p>　　node data[smax];<

20、/p><p>　　}spmatrix;</p><p><b>　　4.2三元組表建立</b></p><p>　　void print(spmatrix *a)</p><p><b>　　{</b></p><p><b>　　int k;</b><

21、;/p><p>　　for(k=0;k<a->t;k++)</p><p>　　printf("%d\t%d\t%d\n",a->data[k].i,a->data[k].j,a->data[k].v);</p><p><b>　　}</b></p><p><b&g

22、t;　　4.3矩陣建立</b></p><p>　　void printjuzhen(spmatrix *a)</p><p><b>　　{</b></p><p>　　int k,p,l;</p><p>　　int c[5][5]={{0},{0},{0},{0},{0}};</p>&l

23、t;p>　　for(k=0;k<a->t;k++)</p><p>　　c[a->data[k].i][a->data[k].j]=a->data[k].v;</p><p>　　for(p=0;p<a->m;p++)</p><p>　　{for(l=0;l<a->n;l++)</p>&l

24、t;p>　　printf("%d\t",c[p][l]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　4.4矩陣相加減及轉(zhuǎn)置</p>

25、<p>　　pmatrix * xiangjia(spmatrix *a,spmatrix *b)</p><p><b>　　{</b></p><p>　　spmatrix *c;</p><p>　　int pa=0,pb=0,pc=0,sum=0;</p><p>　　c=(spmatrix *)mal

26、loc(sizeof(spmatrix));</p><p>　　if((a->m==b->m)&&(a->n==b->n))</p><p><b>　　{</b></p><p>　　c->m=a->m;</p><p>　　c->n=a->n;<

27、/p><p>　　while(pa<a->t&&pb<b->t)</p><p><b>　　{</b></p><p>　　if(a->data[pa].i==b->data[pb].i)</p><p><b>　　{</b></p>

28、<p>　　if(a->data[pa].j==b->data[pb].j)</p><p><b>　　{</b></p><p>　　sum=a->data[pa].v+b->data[pb].v;</p><p><b>　　if(sum)</b></p><p

29、><b>　　{</b></p><p>　　c->data[pc].v=sum;</p><p>　　c->data[pc].i=a->data[pa].i;</p><p>　　c->data[pc].j=a->data[pa].j;</p><p><b>　　pc++

30、;</b></p><p><b>　　}</b></p><p><b>　　pa++;</b></p><p><b>　　pb++;</b></p><p><b>　　}</b></p><p><b>

31、;　　else</b></p><p><b>　　{</b></p><p>　　if(a->data[pa].j<b->data[pb].j)</p><p><b>　　{</b></p><p>　　if(a->data[pa].v)</p>

32、<p><b>　　{</b></p><p>　　c->data[pc].v=a->data[pa].v;</p><p>　　c->data[pc].i=a->data[pa].i;</p><p>　　c->data[pc].j=a->data[pa].j;</p><p

33、>　　pc++;pa++;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　if(b->data[pb].v)</p><p><b>

34、;　　{</b></p><p>　　c->data[pc].v=b->data[pb].v;</p><p>　　c->data[pc].i=b->data[pb].i;</p><p>　　c->data[pc].j=b->data[pb].j;</p><p>　　pc++;pb++;&l

35、t;/p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b><

36、/p><p>　　if(a->data[pa].i<b->data[pb].i)</p><p><b>　　{</b></p><p>　　if(a->data[pa].v)</p><p><b>　　{</b></p><p>　　c->dat

37、a[pc].v=a->data[pa].v;</p><p>　　c->data[pc].i=a->data[pa].i;</p><p>　　c->data[pc].j=a->data[pa].j;</p><p>　　pc++;pa++;</p><p><b>　　}</b></

38、p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　if(b->data[pb].v)</p><p><b>　　{</b></p><p>　　c->data[pc].v=b->data

39、[pb].v;</p><p>　　c->data[pc].i=b->data[pb].i;</p><p>　　c->data[pc].j=b->data[pb].j;</p><p>　　pc++;pb++;</p><p><b>　　}</b></p><p>&l

40、t;b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　return(0);</p><p>　　while(pa<

41、a->t)</p><p><b>　　{</b></p><p>　　c->data[pc].v=a->data[pa].v;</p><p>　　c->data[pc].i=a->data[pa].i;</p><p>　　c->data[pc].j=a->data[pa].

42、j;</p><p>　　pc++;pa++;</p><p><b>　　}</b></p><p>　　while(pb<b->t)</p><p><b>　　{</b></p><p>　　c->data[pc].v=b->data[pb].v

43、;</p><p>　　c->data[pc].i=b->data[pb].i;</p><p>　　c->data[pc].j=b->data[pb].j;</p><p>　　pc++;pb++;</p><p><b>　　}</b></p><p><b>

44、;　　c->t=pc;</b></p><p>　　return(c);</p><p><b>　　五、系統(tǒng)調(diào)試</b></p><p><b>　　5.1主菜單輸出</b></p><p><b>　　圖1主菜單輸出</b></p><

45、p><b>　　5.2矩陣相加</b></p><p><b>　　圖2 矩陣相加</b></p><p><b>　　5.3矩陣轉(zhuǎn)置</b></p><p><b>　　圖3 矩陣轉(zhuǎn)置</b></p><p><b>　　5.4矩陣相

46、減</b></p><p><b>　　圖4矩陣相減</b></p><p><b>　　六、實(shí)驗總結(jié)</b></p><p>　　稀疏矩陣這個課題在我們平時上課時我就感覺對于我而言這是比較困難的，矩陣的相關(guān)知識，三元組表的相關(guān)知識也一直讓我比較惶恐，從拿到這個課題開始我就知道這次的課程設(shè)計必須用盡全力去認(rèn)真對

47、待。我深知團(tuán)隊合作的必要性，五個人的智慧總好過自己一個閉門造車，所以在課程設(shè)計過程中我們組進(jìn)行了激烈地討論，齊心協(xié)力地把這次課程設(shè)計做好。首先，我們根據(jù)課程設(shè)計所圍繞的程序進(jìn)行編程以及調(diào)試；其次，根據(jù)課程設(shè)計的要求進(jìn)行實(shí)驗?zāi)康囊约皩?shí)驗意義的分析；再次之，進(jìn)行需求分析的解決；然后將項目設(shè)計的算法思想，基本算法，主函數(shù)調(diào)用一一呈現(xiàn)出來。這是我們第一次進(jìn)行比較專業(yè)的關(guān)于課程設(shè)計方面的運(yùn)算，關(guān)于三元組表以及稀疏函數(shù)的相關(guān)應(yīng)用，課程設(shè)計過程中，我

48、在利用三元組表實(shí)現(xiàn)稀疏矩陣相加的程序編制中，出現(xiàn)了很多問題，導(dǎo)致最后編譯、執(zhí)行、鏈接時不能成功，后來我查找了資料，去圖書館借了相關(guān)書籍，詢問老師及本組同學(xué)，經(jīng)過了好多次的改進(jìn)，最后，終于完成了程序的編制。 通過一周的課程設(shè)計使我對數(shù)據(jù)結(jié)構(gòu)有了更深的理解，對以前學(xué)習(xí)中不明白的，不理解的都有了進(jìn)一步的理解。在實(shí)際操作中遇到了很多困難，但通過找資料，請教同學(xué)和老師，使我的動手能力和溝</p><p><b>

49、　　七、附錄</b></p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]唐策善、李龍澍、黃劉生 . 數(shù)據(jù)結(jié)構(gòu)——用C語言描述.高等教育出版社.1994年12月</p><p>　　[2]嚴(yán)蔚敏、 吳偉民.數(shù)據(jù)結(jié)構(gòu)第二版. 清華大學(xué)出版社. 1992</p><p>　　[3] 嚴(yán)蔚敏、