數據結構+課程設計+稀疏矩陣的操作(計算機學院)(共19頁)

1、 計算機科學技術學院學生課程設計（論文）題 目： 學生姓名： 學 號： 所在院(系)： 專 業(yè)： 班 級： 指 導 教 師： 職稱： 年 月 日計算機科學技術學院本科學生課程設計任務書題目稀疏矩陣的操作1、課程設計的目的培養(yǎng)學生用學到的書本知識解決實際問題的能力；培養(yǎng)實際工作所需要的動手能力；培養(yǎng)學生以科學理論和工程上能力的技術，規(guī)范地開發(fā)大型、復雜、高質量的應用軟件和系統(tǒng)軟件具有關鍵性作用；通過課程設計的實踐，學生可以在程序設計方法、上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。2、課程設計的內容和要求（包括原始數據、技術要求、工作要求等）基本功能要求：（1） 稀疏矩陣采用三元組

2、表示，求兩個具有相同行列數的稀疏矩陣A和B的相加矩陣C，并輸出C。（2）求出A的轉置矩陣D，輸出D。測試數據： 3、主要參考文獻1數據結構（C語言版），嚴蔚敏，清華大學出版社，20032數據結構題集，嚴蔚敏，清華大學出版社，20053數據結構（C語言版），劉大有，高等教育出版社，20044Data Structure with C+，William FordWilliam Topp，清華大學出版社，20034、課程設計工作進度計劃第1天 完成方案設計與程序框圖 第2、3天 編寫程序代碼第4天 程序調試分析和結果第5天 課程設計報告和總結指導教師（簽字）日期年 月 日教研室意見：年 月 日學生（

3、簽字）： 接受任務時間： 年 月 日注：任務書由指導教師填寫。課程設計（論文）指導教師成績評定表題目名稱評分項目分值得分評價內涵工作表現20%01學習態(tài)度6遵守各項紀律，工作刻苦努力，具有良好的科學工作態(tài)度。02科學實踐、調研7通過實驗、試驗、查閱文獻、深入生產實踐等渠道獲取與課程設計有關的材料。03課題工作量7按期圓滿完成規(guī)定的任務，工作量飽滿。能力水平35%04綜合運用知識的能力10能運用所學知識和技能去發(fā)現與解決實際問題，能正確處理實驗數據，能對課題進行理論分析，得出有價值的結論。05應用文獻的能力5能獨立查閱相關文獻和從事其他調研；能提出并較好地論述課題的實施方案；有收集、加工各種信息

4、及獲取新知識的能力。06設計（實驗）能力，方案的設計能力5能正確設計實驗方案，獨立進行裝置安裝、調試、操作等實驗工作，數據正確、可靠；研究思路清晰、完整。07計算及計算機應用能力5具有較強的數據運算與處理能力；能運用計算機進行資料搜集、加工、處理和輔助設計等。08對計算或實驗結果的分析能力（綜合分析能力、技術經濟分析能力）10具有較強的數據收集、分析、處理、綜合的能力。成果質量45%09插圖（或圖紙）質量、篇幅、設計（論文）規(guī)范化程度5符合本專業(yè)相關規(guī)范或規(guī)定要求；規(guī)范化符合本文件第五條要求。10設計說明書（論文）質量30綜述簡練完整，有見解；立論正確，論述充分，結論嚴謹合理；實驗正確，分析處

5、理科學。11創(chuàng)新10對前人工作有改進或突破，或有獨特見解。成績指導教師評語指導教師簽名： 年月日稀疏矩陣的操作1.課程設計的目的本課程設計是為了配合數據結構課程的開設，通過設計一完整的程序，使學生掌握數據結構的應用、算法的編寫、類C語言的算法轉換成C程序并用TC上機調試的基本方法。利用三元組實現稀疏矩陣的有關算法。 2問題描述2.1稀疏矩陣采用三元組表示，求兩個具有相同行列數的稀疏矩陣A和B的相加矩陣C，并輸出C。2.2求出A的轉置矩陣D，輸出D。3. 基本要求稀疏矩陣是指那些多數元素為零的矩陣。利用“稀疏”特點進行存儲和計算可以大大節(jié)省存儲空間，提高計算效率。實現一個能進行稀疏矩陣

6、基本運算的運算器。以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實現兩個矩陣相加、相減和相乘的運算。稀疏矩陣的輸入形式采用三元組表示，而運算結果的矩陣則通常以陣列形式列出。4.結構設計4.1.以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實現兩個矩陣相加、相減和相乘的運算。4.2.稀疏矩陣的輸入形式采用三元組表示，而運算結果的矩陣則通常以陣列形式列出。4.3.首先應輸入矩陣的行數和列數，并判別給出的兩個矩陣的行、列數對于所要求作的運算是否相匹配?？稍O矩陣的行數和列數均不超過20。4.4.程序可以對三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教材的算法，以便提高計算效率。5.在用三

7、元組表示稀疏矩陣時，相加或相減所得結果矩陣應該另生成，乘積矩陣也可用二維數組存放5.算法思想5.1主函數設置循環(huán)和選擇語句進行運算循環(huán)和選擇，進行稀疏矩陣的加法，減法，乘法，轉置和是否繼續(xù)運算5個分支開關進行運算選擇。5.2設置函數分別實現稀疏矩陣的輸入，輸出，加法，減法，乘法。5.3在數組結構體中設置存放每行第一個非零元在其數組存儲結構單元的位置的存儲單元，若該行無非零元，則存為06.模塊劃分6.1typedef struct存放各行第一個非零元在存儲數組中的位置，若該行無非零元，則其rpos值為零6.2 createsmatrix(rlsmatrix *M) 矩陣輸入函數，輸入各行非零元及

8、其在矩陣中的行列數6.3 FasttransposeRLSMatrix(RLSMatrix M,RLSMatrix *Q) 矩陣快速轉置6.4 HeRLSMatrix(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q) 矩陣求和6.5 ChaRLSMatrix(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q) 矩陣求差6.6 JiRLSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) 矩陣求積7.算法實現7.1首先定義非零元個數的最大值和存放各行第一個非零元在存儲數組中的位置#include<

9、;stdio.h> #define MAXSIZE 100 /* 非零元個數的最大值 */ typedef struct triple int i,j; /* 行下標,列下標 */ int e; /* 非零元素值 */ triple; typedef struct tsmatrix triple dataMAXSIZE+1; /* 非零元三元組表,data0未用 */ int mu,nu,tu; /* 矩陣的行數、列數和非零元個數 */ /* 各列第一個非零元的位置表rpos0未用 */ rlsmatrix; 7.2創(chuàng)建稀疏矩陣矩陣的行數，列數，和非零元素的個數并按行序順序輸入第%d個非

10、零元素所在的行(1%d),列(1%d),元素值。createsmatrix(rlsmatrix *M) /* 創(chuàng)建稀疏矩陣M */ int e,i,m,n; M->data0.i=0; /* 為以下比較順序做準備 */ printf("請輸入矩陣的行數，列數，和非零元素的個數:"); scanf("%d",&M->mu);scanf("%d",&M->nu);scanf("%d",&M->tu); for(i=1;i<=M->tu;i+) printf(&

11、quot;請按行序順序輸入第%d個非零元素所在的行(1%d),列(1%d),元素值：",i,M->mu,M->nu); scanf("%d",&m);scanf("%d",&n);scanf("%d",&e); if(m<1|m>M->mu|n<1|n>M->nu) /*行或列超出范圍 */ printf("行或列超出范圍");getch();exit(); if(m<M->datai-1.i|m=M->datai-

12、1.i&&n<=M->datai-1.j) /*行或列的順序有錯*/ printf("行或列的順序有錯");getch();exit(); M->datai.i=m; M->datai.j=n; M->datai.e=e; 7.3求矩陣的快速轉置 cpos為存放每列的第一個非零元素的地址，temp為中間變量對cpos對初始化，判斷初值為0則為cpos賦值，然后進行轉置。void transposesmatrix(rlsmatrix M,rlsmatrix *T) /* cpos存放每列的第一個非零元素的地址，temp中間變量 *

13、/ int i,m,*cpos,*temp,k=0; T->mu=M.nu; T->nu=M.mu; T->tu=M.tu; cpos=(int *)malloc(M.mu*sizeof(int); if(cpos=NULL)exit(); temp=(int *)malloc(M.mu*sizeof(int); if(temp=NULL)exit(); /* 對cpos對初始化，初值為0 */ *(cpos+1)=0; for(i=1;i<=M.nu;i+) for(m=1;m<=M.tu;m+) if(M.datam.j=i) k+; tempi=k; if(

14、i=1&&k!=0) *(cpos+i)=1;/* 為cpos賦值 */ if(i>1) *(cpos+i)=*(temp+i-1)+1; free(temp); for(i=1;i<=M.tu;i+)/* 進行轉置 */ T->data*(cpos+M.datai.j).i=M.datai.j; T->data*(cpos+M.datai.j).j=M.datai.i; T->data*(cpos+M.datai.j).e=M.datai.e; (*(cpos+M.datai.j)+; free(cpos); 7.3矩陣的相乘 設置兩個指針，分別

15、指向M，N的第一個非零元位置，移動指針進行比較，得出相加后的新矩陣非零元。定義Qe為矩陣Q的臨時數組，矩陣Q的第i行j列的元素值存于*(Qe+(M.datai.i-1)*N.nu+N.dataj.j)中，初值為0，結果累加到Qe，*Qe矩陣中，因為M的每一行和N的每一列相乘都是T的一個元素，不管它是零或非零，當M的第一行和N的第一列相乘則得T的第一個元素；當M的第一行和N的第二列相乘則得T的第二個元素，M的第i行和N的第j列相乘則得T的第p個元素；根據歸納法得p=(i-1)*N的列數+j。multsmatrix(rlsmatrix M,rlsmatrix N,rlsmatrix *T) int

16、 i,j,Qn=0; int *Qe; if(M.nu!=N.mu) printf("兩矩陣無法相乘");getch();exit(); T->mu=M.mu; T->nu=N.nu; Qe=(int *)malloc(M.mu*N.nu*sizeof(int); /* Qe為矩陣Q的臨時數組*/ for(i=1;i<=M.mu*N.nu;i+) *(Qe+i)=0;/* 矩陣Q的第i行j列的元素值存于*(Qe+(M.datai.i-1)*N.nu+N.dataj.j)中，初值為0 */ for(i=1;i<=M.tu;i+) /* 結果累加到Qe

17、*/ for(j=1;j<=N.tu;j+) if(M.datai.j=N.dataj.i) *(Qe+(M.datai.i-1)*N.nu+N.dataj.j)+=M.datai.e*N.dataj.e; for(i=1;i<=M.mu;i+) /*Qe矩陣中，因為M的每一行和N的每一列相乘都是T的一個元素，不管它是零或非零 */ for(j=1;j<=N.nu;j+) /*當M的第一行和N的第一列相乘則得T的第一個元素；當M的第一行和N的第二列相乘則得T的第二個元素； */ if(*(Qe+(i-1)*N.nu+j)!=0) /*當M的第i行和N的第j列相乘則得T的第p個

18、元素；根據歸納法得p=(i-1)*N的列數+j */ Qn+;/非零元個數加一 T->dataQn.e=*(Qe+(i-1)*N.nu+j); T->dataQn.i=i; T->dataQn.j=j; free(Qe); T->tu=Qn; return ; 7.4矩陣的相加編寫一個求兩個對稱矩陣相加運算的函數。設對稱矩陣的數據元素為整數類型，對稱矩陣采用壓縮存儲方法存儲，要求和矩陣采用非壓縮方法存儲。設置兩個指針，分別指向M，N的第一個非零元位置，移動指針進行比較，得出相加后的新矩陣非零元計算各行第一個非零元素在存儲數組中的位置，若該行無非零元，則rpos值為零。H

19、eRLSMatrix(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q)/矩陣求和函數 if(*M).mu!=(*N).mu|(*M).nu!=(*N).nu)printf("不滿足矩陣相加的條件!");return 0;int k=1;Triple *p,*q;/設置兩個指針，分別指向M，N的第一個非零元位置，移動指針進行比較，得出相加后的新矩陣非零元p=&(*M).data1;q=&(*N).data1;while(p<(*M).data+(*M).tu+1&&q<(*N).data+(*N).tu

20、+1)if(*p).i<=(*q).i)if(*p).i<(*q).i)(*Q).datak.i=(*p).i;(*Q).datak.j=(*p).j;(*Q).datak.e=(*p).e;k+;p+;elseif(*p).j<=(*q).j) if(*p).j<(*q).j)(*Q).datak.i=(*p).i;(*Q).datak.j=(*p).j;(*Q).datak.e=(*p).e;k+;p+; else(*Q).datak.i=(*p).i;(*Q).datak.j=(*p).j;(*Q).datak.e=(*p).e+(*q).e;k+;p+;q+;e

21、lse (*Q).datak.i=(*q).i;(*Q).datak.j=(*q).j;(*Q).datak.e=(*q).e;k+;q+;else(*Q).datak.i=(*q).i;(*Q).datak.j=(*q).j;(*Q).datak.e=(*q).e;k+;q+; if(p<=(*M).data+(*M).tu) while(p<=(*M).data+(*M).tu) (*Q).datak.i=(*p).i; (*Q).datak.j=(*p).j; (*Q).datak.e=(*p).e; k+;p+; if(q<=(*N).data+(*N).tu) wh

22、ile(q<=(*N).data+(*N).tu) (*Q).datak.i=(*q).i; (*Q).datak.j=(*q).j; (*Q).datak.e=(*q).e; k+;q+; (*Q).mu=(*M).mu;(*Q).nu=(*M).nu;(*Q).tu=k-1;/計算各行第一個非零元素在存儲數組中的位置/若該行無非零元，則rpos值為零int num(*Q).mu+1,row,cpot(*Q).mu+1;cpot1=1;for(k=1;k<=(*Q).mu;k+)numk=0;for(k=1;k<=(*Q).tu;k+)+num(*Q).datak.i;fo

23、r(row=2;row<=(*Q).mu;row+)cpotrow=cpotrow-1+numrow-1;for(row=1;row<=(*Q).mu;row+)if(cpotrow<=(*Q).tu) if(*Q).datacpotrow.i=row) (*Q).rposrow=cpotrow; else (*Q).rposrow=0;else(*Q).rposrow=0;8.系統(tǒng)運行結果圖1輸入第一個矩陣A圖2輸入第二個矩陣B 兩個矩陣的和圖3矩陣A的轉置矩陣D9.心得體會通過一周的課程設計使我對數據結構有了更深的理解，對以前學習中不明白的，不理解的都有了進一步的理解。在

24、實際操作中遇到了很多困難，但通過找資料，請教同學和老師，使我的動手能力和溝通能力都有了提高。在整個課程設計中總是在編寫程序中發(fā)生錯誤，有時會很沒耐性，但都被我一一克服了，編程一定要有耐心，同時還有認真仔細，盡量保證不出現錯誤。編程要有條理，不僅使自己要看懂 ，別人也能看懂，這樣有利于程序的改正。在做完這個課程設計時，心里有種說不出來的高興，自己動手完成的設計有一種成就感，增強了自己的自信心，我相信在今后的學習中，我會保持這種良好的心情投入到各科的學習中，使我的成績不斷提高。10.參考文獻1 嚴蔚敏 吳偉名 編著，數據結構M.， 清華大學出版社， 2001年1月20-252 張穎江 胡燕 主編，

25、C語言程序設計M.， 科學出版社 ，1998年7月46-803 殷人昆， 數據結構M.，清華大學出版社， 2001年3月 120-1694 徐孝凱 ，數據結構實用教程M.，清華大學出版社，1999年12月 47-805 （美），數據結構與算法M.， ，2003年7月 69-8911.附錄源程序清單#include<stdio.h> #define MAXSIZE 100 /* 非零元個數的最大值 */ typedef struct triple int i,j; /* 行下標,列下標 */ int e; /* 非零元素值 */ triple; typedef struct tsma

26、trix triple dataMAXSIZE+1; /* 非零元三元組表,data0未用 */ int mu,nu,tu; /* 矩陣的行數、列數和非零元個數 */ /* 各列第一個非零元的位置表rpos0未用 */ rlsmatrix; createsmatrix(rlsmatrix *M) /* 創(chuàng)建稀疏矩陣M */ int e,i,m,n; M->data0.i=0; /* 為以下比較順序做準備 */ printf("請輸入矩陣的行數，列數，和非零元素的個數:"); scanf("%d",&M->mu);scanf("

27、;%d",&M->nu);scanf("%d",&M->tu); for(i=1;i<=M->tu;i+) printf("請按行序順序輸入第%d個非零元素所在的行(1%d),列(1%d),元素值：",i,M->mu,M->nu); scanf("%d",&m);scanf("%d",&n);scanf("%d",&e); if(m<1|m>M->mu|n<1|n>M->nu

28、) /*行或列超出范圍 */ printf("行或列超出范圍");getch();exit(); if(m<M->datai-1.i|m=M->datai-1.i&&n<=M->datai-1.j) /*行或列的順序有錯*/ printf("行或列的順序有錯");getch();exit(); M->datai.i=m; M->datai.j=n; M->datai.e=e; void transposesmatrix(rlsmatrix M,rlsmatrix *T) /* cpos存放每

29、列的第一個非零元素的地址，temp中間變量 */ int i,m,*cpos,*temp,k=0; T->mu=M.nu; T->nu=M.mu; T->tu=M.tu; cpos=(int *)malloc(M.mu*sizeof(int); if(cpos=NULL)exit(); temp=(int *)malloc(M.mu*sizeof(int); if(temp=NULL)exit(); /* 對cpos對初始化，初值為0 */ *(cpos+1)=0; for(i=1;i<=M.nu;i+) for(m=1;m<=M.tu;m+) if(M.data

30、m.j=i) k+; tempi=k; if(i=1&&k!=0) *(cpos+i)=1;/* 為cpos賦值 */ if(i>1) *(cpos+i)=*(temp+i-1)+1; free(temp); for(i=1;i<=M.tu;i+)/* 進行轉置 */ T->data*(cpos+M.datai.j).i=M.datai.j; T->data*(cpos+M.datai.j).j=M.datai.i; T->data*(cpos+M.datai.j).e=M.datai.e; (*(cpos+M.datai.j)+; free(cp

31、os); HeRLSMatrix(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q)/矩陣求和函數 if(*M).mu!=(*N).mu|(*M).nu!=(*N).nu)printf("不滿足矩陣相加的條件!");return 0;int k=1;Triple *p,*q;/設置兩個指針，分別指向M，N的第一個非零元位置，移動指針進行比較，得出相加后的新矩陣非零元p=&(*M).data1;q=&(*N).data1;while(p<(*M).data+(*M).tu+1&&q<(*N).data+(

32、*N).tu+1)if(*p).i<=(*q).i)if(*p).i<(*q).i)(*Q).datak.i=(*p).i;(*Q).datak.j=(*p).j;(*Q).datak.e=(*p).e;k+;p+;elseif(*p).j<=(*q).j) if(*p).j<(*q).j)(*Q).datak.i=(*p).i;(*Q).datak.j=(*p).j;(*Q).datak.e=(*p).e;k+;p+; else(*Q).datak.i=(*p).i;(*Q).datak.j=(*p).j;(*Q).datak.e=(*p).e+(*q).e;k+;p

33、+;q+;else (*Q).datak.i=(*q).i;(*Q).datak.j=(*q).j;(*Q).datak.e=(*q).e;k+;q+;else(*Q).datak.i=(*q).i;(*Q).datak.j=(*q).j;(*Q).datak.e=(*q).e;k+;q+; if(p<=(*M).data+(*M).tu) while(p<=(*M).data+(*M).tu) (*Q).datak.i=(*p).i; (*Q).datak.j=(*p).j; (*Q).datak.e=(*p).e; k+;p+; if(q<=(*N).data+(*N).

34、tu) while(q<=(*N).data+(*N).tu) (*Q).datak.i=(*q).i; (*Q).datak.j=(*q).j; (*Q).datak.e=(*q).e; k+;q+; (*Q).mu=(*M).mu;(*Q).nu=(*M).nu;(*Q).tu=k-1;/計算各行第一個非零元素在存儲數組中的位置/若該行無非零元，則rpos值為零int num(*Q).mu+1,row,cpot(*Q).mu+1;cpot1=1;for(k=1;k<=(*Q).mu;k+)numk=0;for(k=1;k<=(*Q).tu;k+)+num(*Q).data

35、k.i;for(row=2;row<=(*Q).mu;row+)cpotrow=cpotrow-1+numrow-1;for(row=1;row<=(*Q).mu;row+)if(cpotrow<=(*Q).tu) if(*Q).datacpotrow.i=row) (*Q).rposrow=cpotrow; else (*Q).rposrow=0;else(*Q).rposrow=0;ChaRLSMatrix(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q)/矩陣求差函數 if(*M).mu!=(*N).mu|(*M).nu!=(*N).nu)

36、printf("不滿足矩陣相減的條件!");return 0;int i;for(i=1;i<=(*N).nu;i+)(*N).datai.e*=-1;HeRLSMatrix(&(*M),&(*N),&(*Q);multsmatrix(rlsmatrix M,rlsmatrix N,rlsmatrix *T) int i,j,Qn=0; int *Qe; if(M.nu!=N.mu) printf("兩矩陣無法相乘");getch();exit(); T->mu=M.mu; T->nu=N.nu; Qe=(int

37、 *)malloc(M.mu*N.nu*sizeof(int); /* Qe為矩陣Q的臨時數組*/ for(i=1;i<=M.mu*N.nu;i+) *(Qe+i)=0;/* 矩陣Q的第i行j列的元素值存于*(Qe+(M.datai.i-1)*N.nu+N.dataj.j)中，初值為0 */ for(i=1;i<=M.tu;i+) /* 結果累加到Qe */ for(j=1;j<=N.tu;j+) if(M.datai.j=N.dataj.i) *(Qe+(M.datai.i-1)*N.nu+N.dataj.j)+=M.datai.e*N.dataj.e; for(i=1;i

38、<=M.mu;i+) /*Qe矩陣中，因為M的每一行和N的每一列相乘都是T的一個元素，不管它是零或非零 */ for(j=1;j<=N.nu;j+) /*當M的第一行和N的第一列相乘則得T的第一個元素；當M的第一行和N的第二列相乘則得T的第二個元素； */ if(*(Qe+(i-1)*N.nu+j)!=0) /*當M的第i行和N的第j列相乘則得T的第p個元素；根據歸納法得p=(i-1)*N的列數+j */ Qn+;/非零元個數加一 T->dataQn.e=*(Qe+(i-1)*N.nu+j); T->dataQn.i=i; T->dataQn.j=j; free(

39、Qe); T->tu=Qn; return ; main()RLSMatrix M,N,Q; char ch;printf(" * n");printf(" * * n");printf(" * 稀疏矩陣運算器 * n");printf(" * - * n");printf(" * n");printf(" _ n");printf(" | 請選擇 | n");printf(" | A.加法 B.減法 C.乘法 D.轉置 Y.繼續(xù)運算 N.

40、結束運算 | n"); printf(" |_| nn");printf("2 輸入數字時請用逗號隔開！nn");printf(" ->");scanf("%c",&ch);while(ch!='N')/進行循環(huán)運算switch(ch)/進行運算選擇case'A': printf(" 請輸入要求和的兩個矩陣：nn"); printf(" 輸入第一個矩陣：nn"); ScanRLSMatrix(&M); print

41、f(" 輸入的第一個矩陣為：nn"); PrintRLSMatrix(M); printf(" 輸入第二個矩陣：nn"); ScanRLSMatrix(&N); printf(" 輸入的第二個矩陣為：nn"); PrintRLSMatrix(N); HeRLSMatrix(&M,&N,&Q); printf(" 兩矩陣之和為：nn"); PrintRLSMatrix(Q); printf(" 是否繼續(xù)運算（Y/N）？nn"); printf(" ->"); ch=getchar();break;case'B': printf(" 請按次序輸入要求差的兩個矩陣：nn"); printf(" 輸入第一個矩陣：nn"); ScanR