對稱矩陣壓縮算法的實現(xiàn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計說明書對稱矩陣壓縮算法的實現(xiàn)學生姓名學號班級成績指導教師數(shù)學與計算機科學學院2015年1月2日專心-專注-專業(yè)課程設(shè)計任務(wù)書20142015學年第一學期專業(yè)： 網(wǎng)絡(luò)工程 學號： 姓名： 課程設(shè)計名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 設(shè) 計 題 目： 對稱矩陣壓縮算法的實現(xiàn) 完 成 期 限：自 2014 年 12 月 22 日至 2015 年 1 月 2 日共 2 周設(shè)計內(nèi)容及要求:矩陣是一個在科學計算與工程問題中常見的數(shù)學對象，在程序設(shè)計中這種數(shù)學對象常常采用二維數(shù)組來存儲，然而，有些矩陣具有某些特殊性，如對稱矩陣，若用數(shù)組存儲對稱矩陣其空間代價較高，為了降低

2、對稱矩陣存儲代價，常常采用一維數(shù)組只存儲對稱矩陣中的對角線及其以上或以下元素值，此過程需要進行二維數(shù)組(矩陣)下標到一維數(shù)組下標的存儲變換。請用C/C+語言編寫一個程序?qū)崿F(xiàn)對稱矩陣的一維數(shù)組壓縮存儲。設(shè)計過程以及寫作要求如下：（1）要針對本題目，認真研究所設(shè)計的內(nèi)容，用簡明扼要的語言描述課題，給出課題的基本內(nèi)容及要求；（2）根據(jù)數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識給出實現(xiàn)對任意矩陣的輸入、對稱性的判斷、對稱矩陣壓縮存儲的轉(zhuǎn)換，及對轉(zhuǎn)換后的一維數(shù)組元素以數(shù)學形式打印輸出原矩陣的算法基本策略及思路；（3）給出較為詳盡數(shù)據(jù)結(jié)構(gòu)與算法，算法可以用流程圖、偽代碼等描述手段進行描述；（4）給出一個完整的算法實現(xiàn)的C/C+程

3、序，算法中的各子算法要力求用函數(shù)來實現(xiàn)；（5）對編寫的程序要進行詳盡的測試分析；（6）對本課題的設(shè)計工作要進行一個完整深刻的總結(jié)。最終設(shè)計成果形式為：1、 設(shè)計軟件一套；2、 撰寫一份課程設(shè)計說明書一份，打印并裝訂成冊。指導教師（簽字）： 教研室主任（簽字）： 批準日期： 年 月 日數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計評閱書題 目對稱矩陣壓縮算法的實現(xiàn)學生姓名學 號指導教師評語及成績成 績： 教師簽名： 年 月 日教研室意見總成績： 室主任簽名： 年 月 日摘要本課程設(shè)計是以vc+語言編程軟件功能和相關(guān)數(shù)據(jù)結(jié)構(gòu)的知識實現(xiàn)的，借助Visual C+6.0工具實現(xiàn)對稱矩陣壓縮算法功能的源代碼。將矩陣以二維數(shù)組的形式

4、存放，通過對稱矩陣的壓縮存儲，從而達到節(jié)省存儲空間的目的。 關(guān)鍵詞：VC+；對稱矩陣；壓縮存儲；節(jié)省空間目 錄 1 課題描述矩陣是很多科學與工程計算問題中研究的數(shù)學對象。在此，人們感興趣的不是矩陣本身，而是如何存儲矩陣的元，從而使矩陣的各種運算能有效的進行。通常，用高級語言編制程序時，都是用二維數(shù)組來存儲矩陣元。有的程序設(shè)計語言中還提供了各種矩陣運算，用戶使用時都很方便，然而，在數(shù)值分析中經(jīng)常出現(xiàn)一些階數(shù)很高的矩陣，同時在矩陣中有許多值相同的元素或者是零元素。有時為了節(jié)省存儲空間，可以對這類矩陣進行壓縮存儲。壓縮矩陣：為多個值相同的元止分配一個存儲空間；對零元不分配空間。開發(fā)工具：Visual

5、 C+6.02 設(shè)計要求2.1設(shè)計要求本次課程設(shè)計采用結(jié)構(gòu)化程序設(shè)計方法，從整體到模塊、逐步細化，模塊化設(shè)計、結(jié)構(gòu)化編碼的算法只適合特殊矩陣中的對稱矩陣，面對一般矩陣，不進行壓縮存儲。存儲時采用的順序存儲結(jié)構(gòu)主要為數(shù)組，包括一維數(shù)組和二維數(shù)組。程序中定義了一個結(jié)構(gòu)體Array s,其成員為兩個數(shù)組，具體設(shè)計過程如下:2.2各模塊程序的偽碼算法（1）構(gòu)建矩陣： CreatMatrix(Array &s); 操作結(jié)果：創(chuàng)建任意n*n矩陣。（2）判斷矩陣是否對稱： JudgeMatrix(Array &s); 初始條件：矩陣M存在。 操作結(jié)果：判斷M是否為對稱矩陣，若不是，則重新構(gòu)建

6、，最終得到對稱矩陣。（3）壓縮存儲： CompMatrix(Array &s); 初始條件：矩陣M為對稱矩陣。 操作結(jié)果：將M壓縮存儲到一維數(shù)組中。（4）輸出所壓縮的對稱矩陣： OutputMatrix(Array &s); 初始條件：矩陣M已被壓縮存儲到一維數(shù)組中。 操作結(jié)果：將M按照數(shù)學形式輸出。2.2各模塊之間的調(diào)用關(guān)系圖各模塊之間的調(diào)用關(guān)系如圖2.1所示。main CreatMatrix JudgeMatrix CompMatrix OutputMatrix CreatMatrix圖2.1 各模塊之間的調(diào)用關(guān)系3 模塊內(nèi)的核心算法及流程圖3.1構(gòu)建任意矩陣在構(gòu)建任意n*

7、n矩陣這個模塊中，利用了二維數(shù)組來接收所構(gòu)建矩陣的元。CreatMatrix()函數(shù)：在構(gòu)建矩陣時，首先要得到n值，將n值帶入構(gòu)建矩陣中，而輸入部分用for循環(huán)控制輸入格式及元素個數(shù)，輸入前已規(guī)定建立任意矩陣并且元素個數(shù)為n*n個，接收時以二維數(shù)組的形式來存儲從鍵盤輸入的任意元素。輸出所構(gòu)建的矩陣時仍用for循環(huán)來輸出。輸入流程圖如圖3.1所示，輸出流程圖如圖3.2所示，其中n為行下表或列下標。 開始 開始 輸入n值 i=1 行下標初始化為1 n是非零自然數(shù) N 判斷非法輸入 n<0或者n為字符 判斷i值與 Y i<=n 行下標 輸入矩陣 系統(tǒng)提示 N n值的關(guān)系 Y i=1 行下

8、標初始化為1 j=1 列下標初始化為1 N i<=n 判斷i值與行下標n值的關(guān)系 Y j<=n 判斷 j值 j=1 列下標初始化為1 N 與列下標 n值的關(guān)系 Y j<=n 判斷j值與列下標 輸出元素 NY n值的關(guān)系 s.Mij 存入元素 j+ j+ i+ i+ 結(jié)束 結(jié)束 圖3.1輸入流程圖 圖3.2輸出流程圖3.1.1構(gòu)建矩陣代碼int CreatMatrix(Array &s)/構(gòu)建任意矩陣int i,j;printf("t請輸入您需要構(gòu)建n階矩陣中的n值n");scanf("%d",&n);if(n<=0

9、)fflush(stdin);printf("tn值為非法輸入，請您重新輸入n值，n>0n");scanf("%d",&n);fflush(stdin);printf("t請輸入數(shù)組中各元素，輸入時請注意：s.Mij=s.Mjin");for(i=1;i<=n;i+)for(j=1;j<=n;j+)scanf("%d",&s.Mij);printf("tt您構(gòu)建的矩陣為：n");printf("n");for(i=1;i<=n;i+)f

10、or(j=1;j<=n;j+)printf("t%2d",s.Mij); printf("n");return ok;3.2判斷矩陣是否對稱由于矩陣的壓縮只針對對稱矩陣，因此在創(chuàng)建任意矩陣后要判斷是否符合壓縮要求。JudgeMatrix()函數(shù)：函數(shù)包括兩個小部分，判斷部分和判斷結(jié)果輸出部分。在對稱矩陣中，Mij=Mji為判斷矩陣是否對稱的依據(jù),因此，要判斷第一步輸入的矩陣是否是對稱矩陣，就是要判斷這一條件是否成立，如果成立，則程序結(jié)束，若不成立，則調(diào)用函數(shù)CreatMatrix重新輸入，構(gòu)建矩陣并再次判斷，直到輸入的矩陣為對稱矩陣結(jié)束。判斷流程圖

11、如圖3.3所示，判斷結(jié)果流程圖如圖3.4所示。 開始 開始 i=1 行下標初始化為1 調(diào)用判斷 函數(shù) N i<=n 判斷i值與行下 得到k值 標n值的關(guān)系 Y k=0 j=1 列下標初始 N 化為1 Y N 對稱矩陣 構(gòu)建的不j<=n 判斷j值與 構(gòu)建成功 是對稱矩陣 列下標n值 Y 的關(guān)系 調(diào)用 CreatMatrix s.Mij!=s.Mji 函數(shù) 沿對稱線元素不對稱 矩陣構(gòu)建成功N Y k+ 結(jié)束j+ 圖3.4 判斷結(jié)果流程圖 i+ 結(jié)束 圖3.3 判斷流程圖3.2.1判斷矩陣是否對稱代碼int JudgeMatrix(Array s)/判斷矩陣是否為對稱矩陣int i,j,

12、k;k=0;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(s.Mij!=s.Mji)k+;printf("tt判斷得到不相等元素的對數(shù)k=%d",k);printf("n");if(k=0)printf("n");printf("ttMij=Mjin");printf("ntt對稱矩陣構(gòu)建正確!請您選擇其他服務(wù)!n");elseprintf("n");printf("tt您構(gòu)建的矩陣不是對稱矩陣");return 1;r

13、eturn 0;3.3 對對稱矩陣進行壓縮存儲當判斷得到對稱矩陣后，便可對其進行壓縮存儲，將一維數(shù)組作為對稱矩陣的存儲結(jié)構(gòu)從而實現(xiàn)存儲過程。CompMatrix()函數(shù)：此函數(shù)功能是對對稱矩陣進行壓縮存儲，即就是將二維數(shù)組壓縮存儲到一維數(shù)組中，壓縮存儲的元素為下三角元，再將壓縮后的數(shù)組元素進行輸出。壓縮部分：通過賦值語句s.mk=s.Mij,將矩陣進行壓縮存儲。壓縮流程圖如圖3.5所示，輸出流程圖如圖3.6所示 開始 開始 i=1,k=0 初始化行下標i=1, 壓縮時元素個數(shù)k一維數(shù)組下標k=0 N i<=n 判斷行下標 k<n*(n+1)/2 i值與 N值的 下三角元素個數(shù) Y

14、關(guān)系 N 初始化 Y j=1 列下標j 輸出壓縮后矩陣元素s.Mk N j<=i 列下標 與行下標 Y 的比較 結(jié)束 s.mk=s.Mij 圖3.6 輸出流程圖 下三角元素賦值給 s.mk k+j+i+ 結(jié)束 圖3.5 壓縮流程圖3.3.1 對對稱矩陣進行壓縮存儲代碼int CompMatrix(Array &s)/對對稱矩陣進行壓縮存儲int i,j,k=0;for(i=1;i<=n;i+)for(j=1;j<=i;j+)s.mk=s.Mij;k+;printf("tt壓縮后的矩陣存入一維數(shù)組后各元素為：n");printf("n&qu

15、ot;);for(k=0;k<n*(n+1)/2;k+)printf("%2d",s.mk);return ok;3.4 將存儲后的矩陣按照數(shù)學形式輸出矩陣的數(shù)學形式即為一個二維數(shù)組，我們將矩陣進行壓縮存儲后，其原來的形式被改變，變?yōu)橐痪S數(shù)組，而所存儲的元素個數(shù)也少于原矩陣，因此需要編輯函數(shù)將矩陣按數(shù)學形式輸出。OutputMatrix()函數(shù)：此函數(shù)的功能是：將壓縮后的矩陣按照矩陣的數(shù)學形式輸出，通過公式：當i>=j時，k=i*(i-1)/2+j-1;當i<j時，k=j*(j-1)/2+i-1。賦值流程圖如圖3.7所示，輸出流程圖如圖3.8所示。 開始

16、開始 i=1 初始化i=1i=1 初始化i=1 NN 判斷i值與 i<=n 判斷i值與 i<=n 行下標n值 行下標n值的的關(guān)系Y 關(guān)系Y j=1 初始化j=1 j=1 初始化 j=1 N 判斷列下 判斷列下標j j<=i 標j值 j<=n 與n值的 與行下標 大小關(guān)系 Y i值得大小Y k=i*(i-1)/2+j-1 輸出矩陣 k=j*(j-1)/2+i-1 j+ s.Mij=s.mki+ j+ 結(jié)束 i+ 圖3.8 輸出流程圖 結(jié)束 圖3.7 賦值流程圖 3.4.1 將存儲后的矩陣按照數(shù)學形式輸出的代碼int OutputMatrix(Array s)/按照數(shù)學形式

17、輸出矩陣int i,j,k=0;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(i>=j)k=i*(i-1)/2+j-1;s.Mij=s.mk;elsek=j*(j-1)/2+i-1;s.Mij=s.mk;printf("tt您壓縮存儲的矩陣按照數(shù)學形式輸出為：n");printf("n");for(i=1;i<=n;i+)for(j=1;j<=n;j+)printf("t%2d",s.Mij);printf("n");return ok;4 詳細代碼#inclu

18、de<stdio.h>#include<stdlib.h>#include<stdarg.h>#define OVERFLOW -2#define UNDERFLOW -1#define ok 1typedef structint M100100;int m100;Array;Array s;int n;int CreatMatrix(Array &s)/構(gòu)建任意矩陣int i,j;/printf("tt請輸入數(shù)組中各元素，輸入時請注意：s.Mij=s.Mjin");printf("t請輸入您需要構(gòu)建n階矩陣中的n值n&

19、quot;);scanf("%d",&n);if(n<=0)fflush(stdin);printf("tn值為非法輸入，請您重新輸入n值，n>0n");scanf("%d",&n);fflush(stdin);printf("t請輸入數(shù)組中各元素，輸入時請注意：s.Mij=s.Mjin");for(i=1;i<=n;i+)for(j=1;j<=n;j+)scanf("%d",&s.Mij);printf("tt您構(gòu)建的矩陣為：n&quo

20、t;);printf("n");for(i=1;i<=n;i+)for(j=1;j<=n;j+)printf("t%2d",s.Mij);printf("n");return ok;int JudgeMatrix(Array s)/判斷矩陣是否為對稱矩陣int i,j,k;k=0;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(s.Mij!=s.Mji)k+;printf("tt判斷得到不相等元素的對數(shù)k=%d",k);printf("n");if(

21、k=0)printf("n");printf("ttMij=Mjin");printf("ntt對稱矩陣構(gòu)建正確!請您選擇其他服務(wù)!n");elseprintf("n");printf("tt您構(gòu)建的矩陣不是對稱矩陣");return 1;return 0;int CompMatrix(Array &s)/對對稱矩陣進行壓縮存儲int i,j,k=0;for(i=1;i<=n;i+)for(j=1;j<=i;j+)s.mk=s.Mij;k+;printf("tt壓縮

22、后的矩陣存入一維數(shù)組后各元素為：n");printf("n");for(k=0;k<n*(n+1)/2;k+)printf("%2d",s.mk);return ok;int OutputMatrix(Array s)/按照數(shù)學形式輸出矩陣int i,j,k=0;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(i>=j)k=i*(i-1)/2+j-1;s.Mij=s.mk;elsek=j*(j-1)/2+i-1;s.Mij=s.mk;printf("tt您壓縮存儲的矩陣按照數(shù)學形式輸出為：

23、n");printf("n");for(i=1;i<=n;i+)for(j=1;j<=n;j+)printf("t%2d",s.Mij);printf("n");return ok;int menu_select() /菜單char c;doprintf("tt*n");printf("tt* 對稱矩陣壓縮算法的實現(xiàn) *n");printf("tt* 1.構(gòu)建任意N*N個元素的矩陣 *n");printf("tt* 2.判斷所建矩陣是否為對稱矩

24、陣 *n");printf("tt* 3.對對稱矩陣進行壓縮存儲 *n");printf("tt* 4.按照數(shù)學形式輸出所壓縮的矩陣 *n");printf("tt* 5.退出程序 *n");printf("tt*n");printf("tt*請您輸入選項1-5*n");fflush(stdin);c=getchar();while(c<'1'|c>'5');return(c); /返回選擇void main() /主函數(shù)char n=

25、9;1'int m;for(;)switch(menu_select() )case '1':printf("n");printf("ttt<構(gòu)建任意n*n個元素的矩陣>n");printf("n");CreatMatrix(s);printf("n");printf("tt您已經(jīng)成功構(gòu)建*任意*矩陣!請您選擇其他服務(wù)!n");printf("n");printf("ttt");system("pause&qu

26、ot;);break;case'2':printf("n");printf("ttt<判斷矩陣是否為對稱矩陣>n");printf("n");m=JudgeMatrix(s);printf("n");if(m=1)CreatMatrix(s);printf("n");printf("ttt");system("pause");break;case'3':printf("n");printf(&

27、quot;ttt<對對稱矩陣進行壓縮存儲>n");printf("n");printf("tt只存儲其下三角各元素：n");printf("n");CompMatrix(s);printf("n");printf("ttt");system("pause");break;case'4':printf("n");printf("ttt<按照數(shù)學形式輸出所壓縮的矩陣>n");printf(&

28、quot;n");OutputMatrix(s);printf("n");printf("ttt");system("pause");break;case'5':printf("n");printf("ttt祝您好運!n");printf("ttt");exit(0);5 程序測試5.1 合法輸入5.1.1 菜單為了使程序界面能夠美化，使用* *對其進行框圈，并且使用t使其跳到下一個制表位置，菜單的使用，使程序的操作簡單明了，如圖5.1所示。圖5.1

29、 菜單5.1.2構(gòu)建任意矩陣在對矩陣進行構(gòu)建時，先確定矩陣的階數(shù)n，然后對矩陣中的元素進行錄入，錄入時用空格鍵區(qū)分兩個數(shù)字，即使輸入元素超過n*n個，也只取前n*n個元素，并將其以矩陣的形式輸出，如圖5.2所示。圖5.2 構(gòu)建任意矩陣5.1.3 成功構(gòu)建矩陣對其進行判斷是否為對稱矩陣該矩陣是否為對稱矩陣，是通過k值進行判斷，對于上述矩陣，對角線為1、7、3、9、5；如若對稱則s.Mij=s.Mji,但通過矩陣的輸出，我們發(fā)現(xiàn)（6、2）（1、3）（6、4）（1、5）（2、8）（7、9）.10組數(shù)據(jù)中，沒有一組內(nèi)的數(shù)據(jù)相同，則不相等的元素數(shù)為k=20.所以該矩陣不是對稱矩陣。如圖5.3所示圖5.3

30、 矩陣的對稱判斷(不對稱矩陣)在矩陣輸入時，必須是對稱矩陣才可以進行第三步第四步操作，否則在判斷對稱矩陣不是對稱矩陣之后，系統(tǒng)提示重新輸入數(shù)據(jù)，在輸入并對其判斷為對稱矩陣之后，該矩陣是對稱矩陣，因為對角線為1、3、5、7、9；如若對稱則s.Mij=s.Mji,通過矩陣的輸出，我們發(fā)現(xiàn)（2,2）（3，3）（4,4）（4,4）（5,5）（6,6）.10組數(shù)據(jù)中，括號內(nèi)的元素都相同，則不相等的元素數(shù)為k=0.所以該矩陣是對稱矩陣，如圖所示5.4。圖5.4 矩陣的對稱判斷（對稱矩陣）5.1.4 對對稱矩陣進行壓縮存儲對對稱矩陣進行壓縮存儲，其存儲的元素為下三角（包括對角線）中的元，即1、2、3、3、4、5、4、5、6、7、5、6、7、8、9，存儲元素的個數(shù)為k=n*(n+1)/2,即15，如圖5.5所示。圖5.5 對稱矩陣的壓縮5.1.5 按照數(shù)學