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

1、陜源理N孽龍數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計說明書對稱矩陣壓縮算法的實現(xiàn)學生姓名學號班級成績指導(dǎo)教師數(shù)學與計算機科學學院2015年1月2日課程設(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ù)組存儲對稱矩陣其空間代價較高，為了降低對稱矩陣存儲代價，常常采用一維數(shù)組只存儲對稱矩陣中的對 角線

2、及其以上或以下元素值，此過程需要進行二維數(shù)組(矩陣)下標到一維數(shù)組下標的存儲變換。t#用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+程序，算法中的各子算法要力求用函數(shù)來實現(xiàn)；(5)

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

4、詞：VC+ ;對稱矩陣；壓縮存儲；節(jié)省空間1課題描述 12設(shè)計要求 22.1 設(shè)計要求 22.2 各模塊程序的偽碼算法 22.3 各模塊之間的調(diào)用關(guān)系圖 23模塊內(nèi)的核心算法及流程圖 33.1 構(gòu)建任意矩陣 33.1.1 構(gòu)建矩陣代碼 43.2 判斷矩陣是否對稱 43.2.1 判斷矩陣是否對稱代碼 63.3 對對稱矩陣進彳T壓縮存儲 63.3.1 對對稱矩陣進行壓縮存儲代碼 83.4 將存儲后的矩陣按照數(shù)學形式輸出 83.4.1 將存儲后的矩陣按照數(shù)學形式輸出的代碼 104詳細代碼 115程序測試 165.1 合法車入 165.1.1 菜單 165.1.2 構(gòu)建任意矩陣 165.1.3 成功構(gòu)

5、建矩陣對其進行判斷是否為對稱矩陣 175.1.4 對對稱矩陣進彳T壓縮存儲 185.1.5 按照數(shù)學形式輸出所壓縮的矩陣 195.1.6 退出程序 205.2 非法輸入 205.2.1 非法操作菜單 205.2.2 n 值的非法輸入 21總結(jié) 22參考資料 231課題描述矩陣是很多科學與工程計算問題中研究的數(shù)學對象。在此，人們感興趣的不是矩陣本身，而是如何存儲矩陣的元，從而使矩陣的各種運算能有效的進行。通常，用高級語言編制程序時，都是用二維數(shù)組來存儲矩陣元。有的程序設(shè)計語言中還提供了各種矩陣運算， 用戶使用時都很方便， 然而，在數(shù)值分析中經(jīng)常出現(xiàn)一些階數(shù)很高的 矩陣，同時在矩陣中有許多值相同的

6、元素或者是零元素。有時為了節(jié)省存儲空間，可以對這類矩陣進行壓縮存儲。壓縮矩陣：為多個值相同的元止分配一個存儲空間；對零元不分配空間。開發(fā)工具：Visual C+6.032設(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

7、*n矩陣。(2)判斷矩陣是否對稱：JudgeMatrix(Array &s);初始條件：矩陣 M存在。操作結(jié)果：判斷 M是否為對稱矩陣，若不是，則重新構(gòu)建，最終得到對稱矩陣。(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所示。圖2.1各模塊之間的調(diào)用關(guān)系3模塊內(nèi)的核心算法及流程圖3.1

8、 構(gòu)建任意矩陣在構(gòu)建任意n*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為行下表或列下標。圖3.1輸入流程圖圖3.2輸出流程圖3.1.1構(gòu)建矩陣代碼int CreatMatrix(Array &s)/構(gòu)建任意矩陣int i,j；printf(&quo

9、t;t請輸入您需要構(gòu)建n階矩陣中的n彳Kn");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(&q

10、uot;tt您構(gòu)建的矩陣為：n");printf("n");for(i=1;i<=n;i+)for(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ù)，因此，要判斷第一步輸入的矩陣是否是對稱矩陣，就是要判斷這一條件是否成

11、立，如果成立，則程序結(jié)束，若不成立，則調(diào)用函數(shù) CreatMatrix重新輸入，構(gòu)建矩陣并再次判斷，直到輸入的矩陣為對稱矩陣結(jié)束。判斷流程圖如圖3.3所示，判斷結(jié)果流程圖如圖 3.4所示。5圖3.3判斷流程圖圖3.4判斷結(jié)果流程圖#3.2.1判斷矩陣是否對稱代碼int JudgeMatrix(Array s)判斷矩陣是否為對稱矩陣int i,j,k； k=0;for(i=1;i<=n;i+) for(j=1產(chǎn)n;j+) if(s.Mij!=s.Mji) k+; printf("tt判斷得到不相等元素的對數(shù)k=%d",k);printf("n");

12、if(k=0) printf("n"); printf("ttMij=M皿小n");printf("ntt對稱矩陣建正確！請您選擇其他服務(wù)！n"); else printf("n"); printf("tt您構(gòu)建的矩陣不是對稱矩陣");return 1; return 0;3.3 對對稱矩陣進行壓縮存儲當判斷得到對稱矩陣后，便可對其進行壓縮存儲，將一維數(shù)組作為對稱矩陣的存儲結(jié)構(gòu)從而實現(xiàn)存儲過程。CompMatrix()函數(shù)：此函數(shù)功能是對對稱矩陣進行壓縮存儲，即就是將二維數(shù)組壓縮存儲到一維數(shù)組中

13、，壓縮存儲的元素為下三角元，再將壓縮后的數(shù)組元素進行輸出。壓縮部分：通過賦值語句s.mk=s.Mij,將矩陣進行壓縮存儲。壓縮流程圖如圖3.5所示，輸出流程圖如圖3.6所示7圖3.5壓縮流程圖9int 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");for(k=0;k<n*(n+1)/2;k+)printf(&

14、quot;%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所示。結(jié)束 )圖3.8輸出流程圖圖3.7賦值流程圖3.4.1將存儲后的矩陣按

15、照數(shù)學形式輸出的代碼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；n");printf("tt您壓縮存儲的矩陣按照數(shù)學形式輸出為:printf("n");for(i=1;i<=n;i+)for(j=1;j<=n;j+)printf("t%2d",s.Mij);pri

16、ntf("n");return ok;114詳細代碼#include<stdio.h>#include<stdlib.h>#include<stdarg.h>#define OVERFLOW -2#define UNDERFLOW -1#define ok 1typedef struct int M100100;int m100;Array;Array s;int n;int CreatMatrix(Array &s)/構(gòu)建任意矩陣int i,j;/printf("tt請輸入數(shù)組中各元素，輸入時請注意：s.Mij=s.M

17、jin");printf("t請輸入您需要構(gòu)建n階矩陣中的n彳Kn");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(&qu

18、ot;%d",&s.Mij); printf("tt您構(gòu)建的矩陣為：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 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("

19、;tt 判斷得到不相等元素的對數(shù) k=%d",k);printf("n");if(k=0)printf("n");printf("ttMij=M皿小n");!n");printf("ntt對稱矩陣建正確！請您選擇其他服務(wù) else printf("n");printf("tt您構(gòu)建的矩陣不是對稱矩陣");return 1;return 0;int CompMatrix(Array &s) int i,j,k=0;對對稱矩陣進行壓縮存儲19for(i=1;i&

20、lt;=n;i+)for(j=1;j<=i;j+)s.mk=s.Mij;k+;printf("tt壓縮后的矩陣存入一維數(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； el

21、se k=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;int menu_select() /菜單char c;doprintf("tt*對稱矩陣壓縮算法的實現(xiàn)printf("tt*1.構(gòu)建任意N*N個兀素的矩陣printf("

22、tt*2.判斷所建矩陣是否為對稱矩陣printf("tt*3.對對稱矩陣進行壓縮存儲printf("tt*4.按照數(shù)學形式輸出所壓縮的矩陣printf("tt*5.退出程序*n");printf("tt*n");*n");*n");*n");*n");*n");printf("tt*請您輸入選項 1-5*n");fflush(stdin);c=getchar();printf("tt*n");while(c<'1'|c>

23、;'5');return(c); /返回選擇 void main() / 主函數(shù)char n='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(&qu

24、ot;n");printf("ttt");system("pause");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&qu

25、ot;);break;case'3':printf("n");printf("ttt<對對稱矩陣進彳T壓縮存儲>n");printf("n");printf("tt只存儲其下三角各元素：n");printf("n");CompMatrix(s);printf("n");printf("ttt");system("pause");break;case'4':printf("n"

26、;);>n");printf("ttt<按照數(shù)學形式輸出所壓縮的矩陣printf("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 菜單為了使程序界面能夠美化，使用

27、* *對其進行框圈，并且使用t使其跳到下一個制表位置，菜單的使用，使程序的操作簡單明了，如圖 5.1所示。 ' CrUsersAdmi r istratQrDe slctop5SrJDe bug'課爰-ex"*清您輸入選項IT ,圖5.1菜單5.1.2 構(gòu)建任意矩陣在對矩陣進行構(gòu)建時，先確定矩陣的階數(shù)n,然后對矩陣中的元素進行錄入，錄入時用空格鍵區(qū)分兩個數(shù)字，即使輸入元素超過 n*n個，也只取前n*n個元素，并將其以矩陣的形式輸出，如圖5.2所示。黨青您輸入選項1T*構(gòu)建任意n知個元素的矩陣請輸入您需要構(gòu)建n階矩陣中的n值清輸入數(shù)組中等元素，輸入時請注意口】56769

28、01234567890123456?99您構(gòu)建的矩陣為：您已經(jīng)成功構(gòu)建*ft意嘵陣，請您選擇其他服務(wù)，請按任意鍵繼續(xù). 一，圖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所示日青您輸入選項IT*構(gòu)建任意n«n個元素的矩陣請輸入您需要構(gòu)建n階矩陣中的n值請

29、輸入數(shù)組中各元素，輸入時請注意二s.rninjif.nq八口1234567B901234567890123456?fl9您構(gòu)建的矩陣為：您已經(jīng)成功構(gòu)建意味陣，請您選擇其他服務(wù)中“請您輸入選項IT*判斷矩陣是否為對前矩陣 判斷得到不相等元素的對數(shù)k=2H請輸入您需要構(gòu)建“才寸稱矩陣圖5.3矩陣的對稱判斷（不對稱矩陣）在矩陣輸入時，必須是對稱矩陣才可以進行第三步第四步操作，否則在判斷對稱矩陣不是對稱矩陣之后，系統(tǒng)提示重新輸入數(shù)據(jù)，在輸入并對其判斷為對稱矩陣之后，該矩陣是對稱矩陣，因為對角線為1、3、5、7、9;如若對稱則s.Mij=s.Mji,通過矩陣的輸出，我們發(fā)現(xiàn)（2,2） （3, 3） （4

30、,4） （4,4） （5,5） （6,6） .10組數(shù)據(jù)中，括號內(nèi)的元素都相同，則不相等的元素數(shù)為k=0.所以該矩陣是對稱矩陣，如圖所示 5.4 。判斷矩陣是否為對稱矩陣判斷得到不相等元素的對數(shù)k=2W請輸入您爨震鬻歌陣請輸入數(shù)組中各元素，輸入時請注意士 nMHI 口】4S6345G74您構(gòu)建的矩陣為二5678S678912345現(xiàn)矩番對存壓-一一一氐:二淮鏟劈式 琦N*h矩陣形 朝任算照出12 3 4 545678請按任意鍵繼續(xù). . .“請您輸入選項1T*判斷矩陣是否為民慚矩陣） 判斷得到不相等元素的對數(shù)h口 對稱矩陣構(gòu)建正確，請您選擇其他赧務(wù)，請按任意鍵繼續(xù).圖5.4矩陣的對稱判斷（對稱

31、矩陣）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 所示。' C:UsersAdnniini stratarXDes Ictop'串同好De bu g深爰 exe時稱矩陣構(gòu)建正確?請您選擇其他服務(wù)?*請您輸入選項T*對對稱矩陣進行壓縮存儲）只存儲其下三角各元素：壓縮后的矩陣存入一維數(shù)組后各元素為：123345456756789請按任意鍵繼續(xù). . .圖5.5對稱矩陣的壓縮5.1.5 按照數(shù)學形式輸

32、出所壓縮的矩陣矩陣是很多科學與工程計算問題中研究的數(shù)學對象，因此，程序編寫的最終目的是使其能夠以數(shù)學形式輸出，方便人們的研究，如圖 5.6所示。5E 8住 7114 657二 二 二12 3 4 5二宿N口五一工 丫庭矩陣形 一班蹙源譯 X編任程的陣 陣矩“請您輸入選項1T*按照數(shù)學形式輸出所壓縮的矩陣您壓縮存儲的矩陣按照數(shù)學形式輸出為E1234S2345634567456795&789請按任意鍵繼續(xù). 一 .圖5.6數(shù)學形式輸出矩陣5.1.6退出程序退出程序按鈕使得程序更加完整，禮貌的結(jié)束語，使得程序更加文明 ，如圖5.7所示。請按任意鍵繼續(xù). . .翦任=縮算法的實現(xiàn)形式評陣I的矩陣23W青您輸入選項A5*祝您好運，Press any key to continue圖5.7退出程序5.2非法輸入5.2.1 非法操作菜單在程序操作過程中， 會因程序操作不當?shù)雀鞣N原因，而導(dǎo)致程序無法進行， 在對程序進行修改之后，使得非法操作程序得到相應(yīng)的解決，也讓程序更加完善。 在對程序菜單進行操作時，例如，輸入的選項值不在菜單中這一非法操作后，程序會重新彈出菜單欄， 重新選擇選擇以便程序能夠完整白進行下去。如圖5.8所示1 &