課程設(shè)計(jì)報(bào)告—稀疏矩陣的完全鏈表表示及其運(yùn)算(已修改)
2025-08-02 11:14 本頁面
【正文】 合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告2014 ～2015 學(xué)年第 2 學(xué)期課程 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)名稱稀疏矩陣的完全鏈表表示及其運(yùn)算學(xué)生姓名 學(xué)號(hào)專業(yè)班級(jí)13軟件工程（2）班 指導(dǎo)教師陳老師 20 15 年 1 月稀疏矩陣的完全鏈表表示及其運(yùn)算【問題描述】 稀疏矩陣的每個(gè)結(jié)點(diǎn)包含down，right，row，col和value五個(gè)域。用單獨(dú)一個(gè)結(jié)點(diǎn)表示一個(gè)非零項(xiàng)，并將所有結(jié)點(diǎn)連接在一起，形成兩個(gè)循環(huán)鏈表。使得第一個(gè)表即行表，把所有結(jié)點(diǎn)按照行序（同一行內(nèi)按列序）用right域鏈接起來。使得第二個(gè)表即列表，把所有結(jié)點(diǎn)按照列序（同一列內(nèi)按行序）用down鏈接起來。這兩個(gè)表共用一個(gè)頭結(jié)點(diǎn)。另外，增加一個(gè)包含矩陣維數(shù)的結(jié)點(diǎn)。稀疏矩陣的這種存儲(chǔ)表示稱為完全鏈表表式。實(shí)現(xiàn)一個(gè)完全鏈表系統(tǒng)進(jìn)行稀疏矩陣運(yùn)算，并分析下列操作函數(shù)的計(jì)算時(shí)間和額外存儲(chǔ)空間的開銷?！驹O(shè)計(jì)目的】認(rèn)識(shí)和掌握稀疏矩陣的完全鏈表表示；能夠建立并運(yùn)用這種存儲(chǔ)結(jié)構(gòu)【基本要求】建立一個(gè)用戶友好、菜單式系統(tǒng)進(jìn)行下列操作，并使用合當(dāng)?shù)臏y試數(shù)據(jù)測試該系統(tǒng)。讀取一個(gè)稀疏矩陣建立其完全鏈表表示輸出一個(gè)稀疏矩陣的內(nèi)容刪除一個(gè)稀疏矩陣兩個(gè)稀疏矩陣相加兩個(gè)稀疏矩陣相減兩個(gè)稀疏矩陣相乘稀疏矩陣的轉(zhuǎn)置【實(shí)現(xiàn)提示]鏈表上的操作。 數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)（一）、問題分析功能要求：根據(jù)用戶輸入的矩陣，實(shí)現(xiàn)稀疏矩陣的求和運(yùn)算，并輸出結(jié)果。輸入要求：矩陣的數(shù)據(jù)在程序運(yùn)行的時(shí)候由用戶提供，先由用戶輸入稀疏矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)。再根據(jù)非零元個(gè)數(shù)，輸入這些非零元，還需要用戶為這些非零元輸入行、列和非零元的值。這樣，一個(gè)稀疏矩陣就輸入完成。用單鏈表存儲(chǔ)非零元素的結(jié)點(diǎn)信息，并且將之用矩陣的形式打印出來（二）、概要設(shè)計(jì)結(jié)構(gòu)體的定義typedef int ElemType。struct OLNode{ int i,j。 //非零元所在行、列 ElemType e。//非零元值 OLNode *right,*down。}。typedef OLNode *OLink。struct CrossList{ OLink *rhead,*chead。//行、列表頭的頭節(jié)點(diǎn) int mu,nu,tu。//矩陣的行、列和非零元個(gè)數(shù)}。存儲(chǔ)結(jié)構(gòu)選擇采用十字鏈表存儲(chǔ)稀疏矩陣，它是稀疏矩陣鏈?zhǔn)奖硎镜囊环N較好的表示方法。在十字鏈表中，每一個(gè)非零矩陣元素存儲(chǔ)在一個(gè)結(jié)點(diǎn)內(nèi)。每一個(gè)節(jié)點(diǎn)除了存儲(chǔ)非零元素的三元組以外，還設(shè)置了right和down兩個(gè)指針，分別指向同一行的下一個(gè)非零元素結(jié)點(diǎn)和同一列的下一個(gè)非零元的結(jié)點(diǎn)。主函數(shù)主函數(shù)包括相加、相減、相乘的各個(gè)子函數(shù)。菜單具有選擇功能的用戶友好、菜單式系統(tǒng)，可以選擇相應(yīng)的功能來處理輸入的數(shù)據(jù)。三、詳細(xì)設(shè)計(jì)和編碼1. 設(shè)計(jì)表示（1）函數(shù)調(diào)用關(guān)系圖主函數(shù) 相加 相減 相乘 非零元 OVERFLOW （2）算法思想稀疏矩陣的每個(gè)結(jié)點(diǎn)包含down，right，row，col和value五個(gè)域。用單獨(dú)一個(gè)結(jié)點(diǎn)表示一個(gè)非零項(xiàng)，并將所有結(jié)點(diǎn)連接在一起，形成兩個(gè)循環(huán)鏈表。使得第一個(gè)表即行表，把所有結(jié)點(diǎn)按照行序（同一行內(nèi)按列序）用right域鏈接起來。使得第二個(gè)表即列表，把所有結(jié)點(diǎn)按照列序（同一列內(nèi)按行序）用down鏈接起來。這兩個(gè)表共用一個(gè)頭結(jié)點(diǎn)。另外，增加一個(gè)包含矩陣維數(shù)的結(jié)點(diǎn)。稀疏矩陣的這種存儲(chǔ)表示稱為完全鏈表表式。(3) 主要編碼int Create(CrossList amp。M){ int i,j,k,m,n,t。 ElemType e。 OLNode *p,*q。 printf(請輸入稀疏距陣的行數(shù) 列數(shù) 非零元的個(gè)數(shù)：)。 scanf(%d%d%d,amp。m,amp。n,amp。t)。 =m。 =n。 =t。 =(OLink*)malloc((m+1)*sizeof(OLink))。 if(!) exit(OVERFLOW)。 =(OLink*)malloc((n+1)*sizeof(OLink))。 if(!) exit(OVERFLOW)。 for(k=0。k!=m。k++)//初始化行頭指針 [k]=NULL。 for(k=0。k!=n。k++)//初始化列頭指針 [k]=NULL。 printf(請按任意次序輸入%d個(gè)非零元的行 列 元素值:\n,)。 for(k=0。kt。k++) { scanf(%d%d%d,amp。i,amp。j,amp。e)。 if(im||jn) { printf(你輸入的元素不在矩陣中 請檢查重輸:\n)。 exit(OVERFLOW)。 } else { p=(OLNode*)malloc(sizeof(OLNode))。 if(!p) exit(OVERFLOW)。 pi=i。 pj=j。 pe=e。 if([i]==NULL||[i]jj)//p插入該行第一節(jié)點(diǎn)處 { pright=[i]。 [i]=p。 } else//尋找行表插入位置 { for(q=[i]。qrightamp。amp。qrightjj。q=qright)。 pright=qright。//完成行插入 qright=p。 } if([j]==NULL||[j]ii)//p插入該列第一節(jié)點(diǎn)處 { pdown=[j]。 [j]=p。 } else//尋找列表插入位置 { for(q=[j]。qdownamp。amp。qdownii。q=qdown)。 pdown=qdown。//完成列插入 qdown=p。 } } } return OK。}int Print(CrossList M){ int i,j,k。 OLink p。 int array[100][100]。 for(i=0。i!=。i++) { for(j=0。j!=。j++)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1