-n階魔方課程設(shè)計(jì)報(bào)告

1、<p>　　經(jīng)濟(jì)管理學(xué)院本科課程設(shè)計(jì)論文</p><p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p>　　學(xué) 號(hào)： </p><p>　　姓 名： </p><p>　　班 級(jí)： &l

2、t;/p><p>　　專 業(yè)： 信息管理與信息系統(tǒng) </p><p>　　系 別: 管理系 </p><p>　　指導(dǎo)教師： </p><p>　　2011 年 1 月 14日 吉 林</p><p><b>　　目

3、錄</b></p><p><b>　　第1章 引言概述</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)是一門理論性強(qiáng)、思維抽象、難度較大的課程，是基礎(chǔ)課和專業(yè)課之間的橋梁。該課程的先行課程是計(jì)算機(jī)基礎(chǔ)、程序設(shè)計(jì)語(yǔ)言、離散數(shù)學(xué)等，后續(xù)課程有操作系統(tǒng)、編譯原理、數(shù)據(jù)庫(kù)原理、軟件工程等。 通過(guò)本門課程的學(xué)習(xí)，我們應(yīng)該能透徹地理解各種數(shù)據(jù)對(duì)象的特點(diǎn)，學(xué)會(huì)數(shù)據(jù)的組織方法和

4、實(shí)現(xiàn)方法，并進(jìn)一步培養(yǎng)良好的程序設(shè)計(jì)能力和解決實(shí)際問(wèn)題的能力，而且該課程的研究方法對(duì)我們學(xué)生在校和離校后的學(xué)習(xí)和工作，也有著重要的意義。　　數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門核心專業(yè)基礎(chǔ)課程，在該專業(yè)的課程體系中起著承上啟下的作用，學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)于提高理論認(rèn)知水平和實(shí)踐能力有著極為重要的作用。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的最終目的是為了獲得求解問(wèn)題的能力。對(duì)于現(xiàn)實(shí)世界中的問(wèn)題，應(yīng)該能從中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，該數(shù)學(xué)模型在計(jì)算機(jī)內(nèi)部用相應(yīng)的數(shù)據(jù)結(jié)

5、構(gòu)來(lái)表示，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，再進(jìn)行編程調(diào)試，最后獲得問(wèn)題的解答。　　進(jìn)行課程設(shè)計(jì)是為了加強(qiáng)編程能力的培養(yǎng)，鼓勵(lì)我們?cè)趯W(xué)習(xí)完理論知識(shí)之后多動(dòng)手同時(shí)發(fā)揮我們自主學(xué)習(xí)的能力。相信通過(guò)數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐，無(wú)論是理論知識(shí)，還是實(shí)踐動(dòng)手能力，我們都會(huì)有不同程度上的提高。</p><p><b>　　第2章 需求分析</b></p><p><b>　　2.

6、1問(wèn)題描述</b></p><p>　　2.1.1語(yǔ)言描述：給定一奇數(shù)n，構(gòu)造一個(gè)n階魔陣。n階魔陣是一個(gè)n階方陣，其元素由自然數(shù)1，2，3，…，n2組成。魔陣的每一行元素之和，每列元素之和以及主、副對(duì)角線元素之和均相等。即對(duì)于給定的奇數(shù)n以及i=1,2,3,…,n，魔陣a滿足條件：</p><p>　　要求輸出結(jié)果的格式要具有n階方陣的形式。</p><p

7、>　　2.1.2算法概述:依次將自然數(shù)填入方陣中，共填n輪，每輪填n次。第一輪的第一次，將1填如入方陣的中間一行的最后一列位置。設(shè)前一次填入的位置是，每輪中第2至第n次將數(shù)填入，若遇到下列兩種情況之一，則填寫位置按以下規(guī)則調(diào)整。</p><p>　　是最后一列（即j=n）位置，則將下一個(gè)數(shù)填入；</p><p>　　是最后一行（即i=n）位置，則將下一個(gè)數(shù)填入；</p>

8、<p>　　新一輪的第一次填入 。</p><p>　　2.1.3舉例說(shuō)明：當(dāng)n=3時(shí)，得到3*3魔陣：</p><p>　　具體程序?qū)嵭羞^(guò)程如下：</p><p>　　圖1-1 在中間行最后一列的位置上插入第一個(gè)數(shù)據(jù)1；</p><p>　　圖1-2 在數(shù)據(jù)1的右下角位置上插入元素2（即i+1）；</p><

9、p>　　圖1-3 檢查2的右下方為空，即將3插入；</p><p>　　圖1-4 3的右下方有數(shù)據(jù)1，故將4插入3的左方；</p><p>　　圖1-5 4的右下方有空位置，插入5；</p><p>　　圖1-6 將6插入；</p><p>　　圖1-7 將7插入；</p><p>　　圖1-8 將8插入；<

10、;/p><p><b>　　圖1-9將9插入；</b></p><p><b>　　2.2 基本要求</b></p><p>　　要求輸出結(jié)果的格式要具有n階魔陣的形式。給定一奇數(shù)n，構(gòu)造一個(gè)n階魔</p><p>　　陣。n階魔陣是一個(gè)n階方陣，其元素由自然數(shù)1，2，3，…，n2組成。魔陣的</

11、p><p>　　每一行元素之和，每列元素之和以及主、副對(duì)角線元素之和均相等。遇到不合法數(shù)據(jù)時(shí)能有相應(yīng)的提示并加以處理，同時(shí)保證不會(huì)出現(xiàn)死循環(huán)。提供連續(xù)實(shí)現(xiàn)的功能。</p><p><b>　　2.3測(cè)試數(shù)據(jù)</b></p><p><b>　　第一組：1,n; </b></p><p><b>

12、;　　第二組：2; </b></p><p><b>　　第三組：3,y; </b></p><p><b>　　第四組：3,a; </b></p><p><b>　　第五組：1，3; </b></p><p><b>　　第3章 概要設(shè)計(jì)</b

13、></p><p>　　3.1 數(shù)據(jù)結(jié)構(gòu) </p><p>　　此課程設(shè)計(jì)采用一維數(shù)組來(lái)存儲(chǔ)二維矩陣。利用指針和數(shù)組之間相互應(yīng)用，表達(dá)矩陣。所用一維數(shù)組來(lái)存儲(chǔ)二維矩陣的方法能夠使矩陣更容易操作，并可</p><p>　　在開(kāi)辟的連續(xù)存儲(chǔ)空間中能夠有效的存儲(chǔ)矩陣。</p><p>　　則上例n=3在一維數(shù)組中的存儲(chǔ)為如下圖：</p

14、><p>　　0 1 2 3 4 5 6 7 8 </p><p>　　圖3-1 n=3時(shí)在一維數(shù)組中的存儲(chǔ)圖</p><p>　　＊具體的表示運(yùn)行方法為以下程序： </p><p>　　int *p=new int[n*n];</p&

15、gt;<p>　　int i; </p><p>　　for(i=0;i<n*n;i++)</p><p><b>　　{</b></p><p>　　p[i]=0; </p><p><b>　　}<

16、/b></p><p>　　i=n/2; </p><p>　　int j=n-1;</p><p>　　int k=1; </p><p>　　p[i*n+j]=k;

17、 </p><p>　　while(k<n*n) </p><p><b>　　{</b></p><p>　　if(!p[((i+1)%n)*n+((j+1)%n)]) </p>

18、<p><b>　　{</b></p><p>　　p[((i+1)%n)*n+((j+1)%n)]=k+1; </p><p>　　i++; </p><p><b>　　j++;</b></p><p><b

19、>　　}</b></p><p>　　else </p><p><b>　　{</b></p><p>　　p[(i%n)*n+((j-1)%n)]=k+1; </p><p>　　j--;

20、 </p><p><b>　　} </b></p><p>　　k++; </p><p><b>　　}</b></p><p>　?。獮榱吮ＷC算法的健壯性，在程序的設(shè)計(jì)當(dāng)中，加

21、入了一些模塊。</p><p><b>　　while(1)</b></p><p><b>　　{</b></p><p>　　cout<<"************n階魔陣************"<<endl;</p><p>　　cout<&

22、lt;"請(qǐng)輸入一個(gè)奇數(shù)n"<<endl;</p><p>　　int n; //魔陣階數(shù)</p><p>　　string nn; //浮點(diǎn)數(shù)，用以判斷輸入數(shù)是否為整數(shù) </p><p>　　while(cin>>nn,n=ConvertStringToInt(nn),n

23、%2==0||n<=0||IsContainInString(nn,'.'))</p><p><b>　　{</b></p><p>　　if(IsContainInString(nn,'.'))</p><p><b>　　{</b></p><p>　　c

24、out<<"請(qǐng)輸入一個(gè)整數(shù)！"<<endl;</p><p><b>　　}</b></p><p>　　else if(n%2==0)</p><p><b>　　{</b></p><p>　　cout<<"請(qǐng)不要輸入偶數(shù)！&qu

25、ot;<<endl;</p><p><b>　　}</b></p><p>　　else if(n<=0)</p><p><b>　　{</b></p><p>　　cout<<"請(qǐng)輸入一個(gè)大于0的數(shù)"<<endl;</p>

26、;<p><b>　　}</b></p><p><b>　　}</b></p><p>　?。O(shè)計(jì)模塊可進(jìn)行連續(xù)計(jì)算，程序如下：</p><p>　　string re;</p><p>　　cout<<"繼續(xù)？(y/n)"<<endl;&

27、lt;/p><p>　　while(cin>>re,!IsContainInString(re,'y')&& !IsContainInString(re,'n'))</p><p><b>　　{</b></p><p>　　cout<<"選擇無(wú)效，請(qǐng)重新選擇！&qu

28、ot;<<endl;</p><p><b>　　}</b></p><p>　　if(IsContainInString(re,'n'))</p><p><b>　　{</b></p><p>　　cout<<"謝謝使用，再見(jiàn)！"<

29、;<endl;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　?。缬龅教厥馇闆r，可以用dos命令對(duì)程序進(jìn)行操作,具體程序如下：</p><p>　　system("pause");

30、 </p><p><b>　　return 0;</b></p><p>　　當(dāng)遇到輸入錯(cuò)誤時(shí)，如，輸入的為浮點(diǎn)型數(shù)據(jù)，則用一下模塊進(jìn)行處理：</p><p>　　int ConvertStringToInt(string re) </p><p><b>　　{</b></

31、p><p>　　int n=re.length();</p><p>　　int i,t=0;</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　if(re[i]<'0' || re[i]>'9&

32、#39;)</p><p><b>　　return 0;</b></p><p>　　t=t*10+re[i]-48;</p><p><b>　　}</b></p><p>　　return t; </p><p><b>　　}</b></p

33、><p>　?。狪nt ConertStringToInt(string re)的流程圖如下：</p><p>　　圖3-1 ConertStringToInt()函數(shù)流程圖</p><p>　?。猙ool IsContainInString(string &a,char b)的流程圖如下：</p><p>　　圖3-2 IsContai

34、nInString()函數(shù)流程圖</p><p><b>　　第4章 詳細(xì)設(shè)計(jì)</b></p><p>　　#include <iostream></p><p>　　#include <iomanip></p><p>　　#include <string></p>&

35、lt;p>　　using namespace std;</p><p>　　int ConvertStringToInt(string);</p><p>　　bool IsContainInString(string &,char);</p><p>　　int main()</p><p><b>　　{</

36、b></p><p><b>　　while(1)</b></p><p><b>　　{</b></p><p>　　cout<<"************n階魔陣************"<<endl;</p><p>　　cout<<

37、;"請(qǐng)輸入一個(gè)奇數(shù)n"<<endl;</p><p>　　int n; //魔陣階數(shù) </p><p>　　string nn; //浮點(diǎn)數(shù)，用以判斷輸入數(shù)是否為整數(shù) </p><p>　　while(cin>>nn,n=ConvertStringToInt(nn),n%

38、2==0||n<=0|| IsContainInString(nn,'.'))</p><p><b>　　{</b></p><p>　　if(IsContainInString(nn,'.'))</p><p><b>　　{</b></p><p>　　c

39、out<<"請(qǐng)輸入一個(gè)整數(shù)！"<<endl;</p><p><b>　　}</b></p><p>　　else if(n%2==0)</p><p><b>　　{</b></p><p>　　cout<<"請(qǐng)不要輸入偶數(shù)！&qu

40、ot;<<end</p><p><b>　　}</b></p><p>　　else if(n<=0)</p><p><b>　　{</b></p><p>　　cout<<"請(qǐng)輸入一個(gè)大于0的數(shù)"<<endl;</p>

41、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　int *p=new int[n*n];</p><p><b>　　int i;</b></p><p>　　for(i=0;i<n*n;i++)</p>

42、<p><b>　　{</b></p><p>　　p[i]=0; //將數(shù)組全部清零 </p><p><b>　　}</b></p><p>　　i=n/2; //將初始坐標(biāo)定為中間一行最后一頁(yè) </p><p>　　int j=n-1;&

43、lt;/p><p>　　int k=1; //第一個(gè)被填的數(shù)設(shè)為1 </p><p>　　p[i*n+j]=k; //填第一個(gè)數(shù) </p><p>　　while(k<n*n) //需要循環(huán)n*n-1次 </p><p><b>　　{</b></p>

44、<p>　　if(!p[((i+1)%n)*n+((j+1)%n)]) //判斷當(dāng)前坐標(biāo)的右下方是否有數(shù) </p><p><b>　　{</b></p><p>　　p[((i+1)%n)*n+((j+1)%n)]=k+1; //將右下方數(shù)填為k+1 </p><p>　　i++;

45、 //當(dāng)前坐標(biāo)移向右下方 </p><p><b>　　j++;</b></p><p><b>　　}</b></p><p>　　else //右下方有數(shù) </p><p><b>

46、　　{</b></p><p>　　p[(i%n)*n+((j-1)%n)]=k+1; //將左方數(shù)填為k+1 </p><p>　　j--; //當(dāng)前坐標(biāo)移向左方 </p><p><b>　　} </b></p><p>

47、　　k++; //被填數(shù)自增 </p><p><b>　　}</b></p><p>　　for(i=0;i<n;i++) //填數(shù)完畢，將矩陣輸出 </p><p><b>　　{</b>&l

48、t;/p><p>　　for(j=0;j<n;j++)</p><p><b>　　{</b></p><p>　　cout<<setw(4)<<p[i*n+j]; //格式控制 </p><p><b>　　}</b></p>&l

49、t;p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　string re;</p><p>　　cout<<"繼續(xù)？(y/n)"<<endl; //是否繼續(xù) </p><p>　　

50、while(cin>>re,!IsContainInString(re,'y') && !IsContainInString(re,'n')) //如果既沒(méi)有輸入Y，也沒(méi)有輸入N，則認(rèn)定</p><p>　　//非法輸入，重新輸入直到輸入合法為止 </p><p><b>　　{</b></p&g

51、t;<p>　　cout<<"選擇無(wú)效，請(qǐng)重新選擇！"<<endl;</p><p><b>　　}</b></p><p>　　if(IsContainInString(re,'n')) //如果輸入N，則退出 </p><p><b>　　{<

52、/b></p><p>　　cout<<"謝謝使用，再見(jiàn)！"<<endl;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p>

53、<p>　　system("pause"); //外部DOS命令pause，用于暫停以監(jiān)測(cè)</p><p><b>　　//結(jié)果</b></p><p><b>　　return 0;</b></p><p><b>　　}</b><

54、;/p><p>　　int ConvertStringToInt(string re) //將字符串轉(zhuǎn)換成整型數(shù)的函數(shù)，若 </p><p>　　//字符串中部全為字符，則返回0</p><p><b>　　{</b></p><p>　　int n=re.length();</p><p&

55、gt;　　int i,t=0;</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　if(re[i]<'0' || re[i]>'9')</p><p><b>　　return 0;</b&g

56、t;</p><p>　　t=t*10+re[i]-48;</p><p><b>　　}</b></p><p><b>　　return t;</b></p><p><b>　　}</b></p><p>　　bool IsContainInStr

57、ing(string &a,char b) //判斷字符串中是否包</p><p><b>　　//含指定字符 </b></p><p><b>　　{</b></p><p>　　int n=a.length();</p><p><b>　　int i;&

58、lt;/b></p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　if(a[i]==b)</p><p>　　return true;</p><p><b>　　}</b></p>&l

59、t;p>　　return false;</p><p><b>　　}</b></p><p><b>　　第5章 調(diào)試分析</b></p><p>　　5.1輸入界面（1）:</p><p>　　圖5-1 輸入1，再輸入n</p><p>　　5.2輸入界面（2）:

60、</p><p><b>　　圖5-2 輸入2</b></p><p>　　5.3輸入界面（3）:</p><p>　　圖5-3 輸入3，再輸入y</p><p>　　5.4輸入界面（4）:</p><p>　　圖5-4 輸入3，再輸入a</p><p>　　5.5輸

61、入界面（5）:</p><p>　　圖5-5 輸入1.3</p><p>　　為了使程序健壯行良好，我進(jìn)行了多次調(diào)試，力求盡列出所有的可能數(shù)據(jù)，并最程序進(jìn)行修改，使之成為一個(gè)優(yōu)秀的程序。本程序是關(guān)于二維數(shù)組的，時(shí)間復(fù)雜度為O(n2 )。 </p><p><b>　　第6章 課設(shè)總結(jié)</b></p><p>　

62、　通過(guò)此次課程設(shè)計(jì)，我深化了對(duì)數(shù)據(jù)結(jié)構(gòu)的基本概念、理論和方法的理解，把所學(xué)的理論知識(shí)用于處理實(shí)際問(wèn)題。這種學(xué)以致用的感覺(jué)非常好，讓自己真正的掌握了所學(xué)的知識(shí)，并將其利用在實(shí)際問(wèn)題中。還有就是C++的面向?qū)ο蟮某绦蛟O(shè)計(jì)理念，對(duì)程序設(shè)計(jì)是一個(gè)好的啟發(fā)。其中，在程序的調(diào)試中遇到了一些問(wèn)題，這讓我重新審視到了做好一個(gè)程序需要具備哪些能力。實(shí)踐能給人以成就之感，我是以著“態(tài)度決定一切”的心態(tài)對(duì)待此次《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)的，于是偶然又必然地收獲了諸

63、多，概而言之，大約以下幾點(diǎn)：</p><p>　　1.溫故而知新。課程設(shè)計(jì)發(fā)端之始，對(duì)知識(shí)系統(tǒng)全面地進(jìn)行了梳理，遇到難處先是自己思考查資料，再向同學(xué)請(qǐng)教，掌握了基本理論知識(shí)，而且對(duì)理論知識(shí)進(jìn)行實(shí)踐應(yīng)用，使得理解更加深刻，學(xué)會(huì)了如何思考的思維方式。</p><p>　　2實(shí)踐出真知。時(shí)至今日，課程設(shè)計(jì)基本告成，切身領(lǐng)悟有了思路還需要用實(shí)踐進(jìn)行考驗(yàn)，才明曉實(shí)踐出真知。如在進(jìn)行算法分析時(shí)要深刻地

64、從正確性、穩(wěn)健性、可讀性、時(shí)間復(fù)雜度等方面進(jìn)行考慮，在一個(gè)算法中，進(jìn)行簡(jiǎn)單操作的次數(shù)越少，其運(yùn)行時(shí)間也就相對(duì)的越短；次數(shù)越多，其運(yùn)行時(shí)間也就相對(duì)的越長(zhǎng)。同樣很多時(shí)候時(shí)間的長(zhǎng)短與程序的難易程度（實(shí)現(xiàn)的所要付出的代價(jià)）呈反比。通過(guò)這次課設(shè)使我深刻理解了“不為則不知，無(wú)為則無(wú)知，實(shí)踐出真知”這句名言。 </p><p>　　3.創(chuàng)新求發(fā)展。“創(chuàng)新”目前已經(jīng)提升到國(guó)家發(fā)展戰(zhàn)略地位，足見(jiàn)“創(chuàng)新”的舉足輕重。因此，我們要從小

65、處著手，順應(yīng)時(shí)代發(fā)展潮流，在課程設(shè)計(jì)中不忘在小處創(chuàng)新，未必是創(chuàng)新技術(shù)，但凡創(chuàng)新思維亦可，未必成功，只要實(shí)現(xiàn)創(chuàng)新思維培育和鍛煉即可。</p><p>　　4.過(guò)而能改，善莫大焉。至善至美，是人類永恒的追求。但是，不從忘卻“金無(wú)足赤，人無(wú)完人”，我們換種思維方式，去惡亦是至善，改錯(cuò)亦為至美。在課程設(shè)計(jì)過(guò)程中，我們不斷發(fā)現(xiàn)錯(cuò)誤，不斷改正，不斷領(lǐng)悟，不斷獲取。最終的檢測(cè)調(diào)試環(huán)節(jié)，本身就是在踐行“過(guò)而能改，善莫大焉”的知行

66、觀。</p><p>　　一邊制作一邊探索，發(fā)現(xiàn)理論和實(shí)踐要充分地結(jié)合，是需要扎實(shí)的基本功的，解決實(shí)際的應(yīng)用問(wèn)題，在理解了數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系的基礎(chǔ)上，深入討論它們?cè)谟?jì)算機(jī)中的存儲(chǔ)表示，結(jié)合上機(jī)進(jìn)行算法及存儲(chǔ)表示的實(shí)現(xiàn)。進(jìn)一步提高自身的綜合運(yùn)用所學(xué)知識(shí)處理實(shí)際問(wèn)題的能力，強(qiáng)化面向?qū)ο蟮某绦蛟O(shè)計(jì)理念，從而使自己有所提高。</p><p>　　這就表明學(xué)好基礎(chǔ)知識(shí)是理論付諸實(shí)踐的前提。在這次