1、2010-2011 第二學(xué)期數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目1 : 大數(shù)相乘題目2: 馬的遍歷學(xué) 院：計(jì)算機(jī)學(xué)院姓名：浩學(xué)號(hào)：099074140班級(jí)：軟件091班評(píng)閱教師：湯亞玲2011年6月9日工業(yè)大學(xué)、目加深對(duì)數(shù)據(jù)結(jié)構(gòu)課程所學(xué)知識(shí)的理解，進(jìn)一步鞏固 C 語(yǔ)言語(yǔ)法規(guī)則。學(xué)會(huì)編制結(jié)構(gòu)清晰、風(fēng)格良好、數(shù)據(jù)結(jié)構(gòu)適當(dāng)?shù)腃語(yǔ)言程序，從而具備解決綜合性實(shí)際問(wèn)題的能力。目錄：系統(tǒng)功能分析 3基本要求 3功能需求 3開(kāi)發(fā)工具 3程序說(shuō)明 3大數(shù)相乘總括 4源程序 4測(cè)試與結(jié)論 5創(chuàng)新及難點(diǎn) 6 程序設(shè)計(jì)總結(jié)心得體會(huì) 62011-6-9正文容如下：一、 系統(tǒng)功能分析功能分析：大數(shù)相乘可以實(shí)現(xiàn)對(duì)兩個(gè)任意大的正數(shù)相乘。用戶可

2、以通過(guò)本程序?qū)o(wú)法實(shí)現(xiàn)的兩數(shù)進(jìn)行相乘，其意在方便用戶，方便群眾。二、 1編寫基本目的要求 ： 分析程序開(kāi)發(fā)過(guò)程的具體問(wèn)題，構(gòu)架程序的功能，同時(shí)使該程序的使用者對(duì)本程序 有一定的了解，為實(shí)現(xiàn)功能的編碼做好基礎(chǔ)，對(duì)數(shù)據(jù)結(jié)構(gòu)有一個(gè)更深入的了解。1、背景：a. 開(kāi)發(fā)的軟件系統(tǒng)的名稱：大數(shù)相乘。b. 本項(xiàng)目的任務(wù)提出者湯亞玲；開(kāi)發(fā)者：浩。2、功能需求： 根據(jù)大數(shù)相乘的實(shí)際需求， 分析系統(tǒng)應(yīng)該設(shè)計(jì)的功能， 其中應(yīng)該包括對(duì)于超過(guò)整型大 數(shù)的輸入，存儲(chǔ)，運(yùn)算，輸出。實(shí)現(xiàn)乘法的一般功能。3、數(shù)據(jù)需求 ：運(yùn)行環(huán)境及知識(shí)要求：運(yùn)行環(huán)境要求： windows xp/visita/7 知識(shí)要求： 熟悉 vc+6.0 編

3、譯系統(tǒng) 熟悉 AISCC 熟練掌握字符與數(shù)字之間的轉(zhuǎn)換4、分析及實(shí)現(xiàn)簡(jiǎn)介：由于大數(shù)相乘問(wèn)題相對(duì)簡(jiǎn)單，我只寫了一個(gè)主函數(shù)實(shí)現(xiàn)了其功能。大數(shù)用字符數(shù)組存儲(chǔ)， 用 AISCC 數(shù)字之間轉(zhuǎn)換進(jìn)行運(yùn)算。二、程序的說(shuō)明：首先定義兩個(gè)字符數(shù)組存儲(chǔ)兩個(gè)大數(shù)，在定義兩個(gè)數(shù)組，一個(gè)用與保存結(jié)果，另一個(gè)為輔助只用，具體的思想是 a b兩個(gè)大數(shù) 用b的個(gè)位一次乘a的每一位結(jié)果保存在輔助數(shù) 組 temp 中，在進(jìn)位取余得到正常的 10 進(jìn)制數(shù)，用 sum 數(shù)組的 temp 的求和，用 flag 標(biāo)記， 以便 temp 的錯(cuò)位相加。用 while 可以控制大數(shù)運(yùn)行的次數(shù)。三、模塊分析及源程序：/* 大數(shù)相乘問(wèn)題 */#i

4、nclude<stdio.h>#include<string.h>#define MAX 10000int main()int n,i,j,t,s;char a100,b100,temp105=0,sumMAX=0; /* 定義兩個(gè)字符數(shù)組 a， b 用來(lái)存儲(chǔ)大數(shù) temp 為輔助 */int lena,lenb,flag,m=0;printf(" 輸入運(yùn)算的次數(shù) n:n");scanf("%d",&n); /* 輸入運(yùn)算的次數(shù) n*/while(n-) m+;flag=0; /* 設(shè)置標(biāo)志 flag*/printf(&q

5、uot;輸入將要運(yùn)算的兩數(shù)a, b;用回車鍵相分隔n");scanf("%s%s",a,b);/* 輸入兩要相乘的大數(shù)用回車鍵相分隔 */lena=strlen(a);lenb=strlen(b); /*求兩數(shù)的長(zhǎng)度 */for(j=lenb-1;j>=0;j-)/* 依次從低位開(kāi)始求的 b 的某一位與 afor(t=lena,i=lena-1;i>=0;i-,t-) tempt=(ai-48)*(bj-48);的乘積 */for(t=lena;t>=1;t-)if(tempt>9)tempt-1+=tempt/10; tempt%=10;

6、for(s=lena+lenb-flag,t=lena;t>=0;t-,s-) 相加 */sums+=tempt;for(t=lena;t>=0;t-)tempt=0;/* 進(jìn)位取余 */* 標(biāo)志 flag 確保錯(cuò)位/* 輔助數(shù)組復(fù)位志零 */for(s=lena+lenb;s>=1;s-)if(sums>9)sums-1+=sums/10; sums%=10;flag+;sumlena+lenb+1='0'for(s=0;s<=lena+lenb;s+)sums=sums+48;for(s=0;s<lena+lenb;s+) if(sum0

7、=48) for(t=0;t<=lena+lenb-s;t+) sumt=sumt+1;位為零 */else break;printf("Case %d:n",m);printf("%s * %s = %sn",a,b,sum); if(n!=0)printf("n"); for(s=lena+lenb+1;s>=0;s-) while 循環(huán) */sums=0;/* s 進(jìn)位取余 */* 數(shù)值還原， 48 對(duì)應(yīng) 0'字符 */* 高位有零向前移位，防止輸出的數(shù)第一/ 輸出結(jié)果；/*sum 字符數(shù)組復(fù)位志零等待下一輪

8、return 0;測(cè)試與結(jié)論 ： 進(jìn)過(guò)我的反復(fù)測(cè)試，只要是兩個(gè)正整數(shù)相乘結(jié)果正確，程序穩(wěn)定性好，可以運(yùn)算任意 大是數(shù)。運(yùn)行結(jié)果抓圖如：g敦?fù)砦蓆Dpfbn叭大敦紊” reg*氏自蕭入將要倉(cāng)算的兩如加用目年費(fèi)冃分隔2J4223C&3C 1234 * 223 = 52162語(yǔ)入搐要運(yùn)算的兩數(shù)和加用回車費(fèi)盼隔214217457CasA 2:2J4215745? * 67S899% T入糕要話算的兩數(shù)b：用回車黑相分隔橫 55555 眈卿456365Cue 3:也5初時(shí)7M566 * 5555555676麗55 = 4813636?19?847760454229&606312590 P

9、res ary key to continue1四、創(chuàng)新及難點(diǎn)：1、創(chuàng)新: 只有一個(gè)主函數(shù)，while循環(huán)實(shí)現(xiàn)大數(shù)相乘，使得程序簡(jiǎn)短高效。 使用temp輔助字符數(shù)組，降低了運(yùn)算是難度，程序清晰易懂。 系統(tǒng)在操作提示上較多，用戶與系統(tǒng)間的信息交互比較方便，便于操作。2、難點(diǎn)： 要用一個(gè)大數(shù)的各個(gè)位去乘一個(gè)大數(shù)并把的到的數(shù)反向存儲(chǔ)且使得數(shù)字每一位 不大于9。 因?yàn)橄喑嗣恳晃粰?quán)重不一樣，要錯(cuò)位相加。得數(shù)求余，變換。四、心得體會(huì)：通過(guò)為一學(xué)期的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)課使我了解到了一個(gè)程序開(kāi)發(fā)的過(guò)程，雖然規(guī)模不大，但為我以后的編程學(xué)習(xí)打下了基礎(chǔ)。 在編程的過(guò)程中，我體會(huì)到了 學(xué)習(xí)編程的辛苦，為了一個(gè)算法的

10、實(shí)現(xiàn)而思考，為了一個(gè)小小的編譯錯(cuò)誤而花時(shí) 間去尋找，這需要很大的毅力和耐心，而且要有良好的思維，這才使得我完成這 個(gè)任務(wù)，也使我感到一分喜悅，畢竟自己完成了一個(gè)有模有樣的程序。于此，我 也發(fā)現(xiàn)自己的一些不足，良好的編程習(xí)慣的養(yǎng)成，堅(jiān)定的毅力和耐心仍是我要加 強(qiáng)的，同別人的交流也是必須的，這樣才能不斷使我進(jìn)步。題目二 ：馬的遍歷目錄：流程圖： 8系統(tǒng)功能分析 9基本要求 9程序說(shuō)明 .9創(chuàng)建標(biāo)志矩陣函數(shù)模塊 9巡游子函數(shù)模塊 . 9賦值子函數(shù)模塊 .11主程序函數(shù)模塊 11測(cè)試運(yùn)行與結(jié)論 1213程序設(shè)計(jì)總結(jié)心得體會(huì)流程圖結(jié)束/*創(chuàng)建標(biāo)志矩陣函數(shù)聲明 */void creatadjm(void)

11、; void mark(int,int,int,int); void travel(int,int);int n,m;/*定義矩陣大小及標(biāo)志矩陣的大小 */系統(tǒng)功能分析：?jiǎn)栴}描述 ：設(shè)計(jì)一個(gè)國(guó)際象棋上的馬的遍歷棋盤的演示過(guò)程的程序?；疽?：將馬任意放在國(guó)際棋盤的 8x8 的棋盤 board88 的某個(gè)方格， 馬按走棋規(guī)則 進(jìn)行移動(dòng)。 要求每個(gè)方格只進(jìn)入一次，走遍棋盤上的全部64 個(gè)方格。編制程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，。 64 依次填入一個(gè) 8x8 的方陣，輸出之。程序說(shuō)明：首先，國(guó)際象棋是 8*8 的棋盤，馬的走法是“馬走日” ，忽略“蹩腳馬” 的情況。其次

12、，這個(gè)題目采用的是遞歸， 算法當(dāng)中的深度優(yōu)先算法和回溯法： 在“走 到”一個(gè)位置后要尋找下一個(gè)位置，如果發(fā)生“阻塞”的情況，就是后面走不 通的情況，則向后回溯，重新尋找。在尋找下一步的時(shí)候，對(duì)周圍的這幾個(gè)點(diǎn) 進(jìn)行比較， 從而分出優(yōu)劣程度， 即看它們周圍可以走的點(diǎn)誰(shuí)最少， 然后就走那 條可走路線最少的那條。 經(jīng)過(guò)這樣的篩選后，就會(huì)為后面的路徑尋找提供方便， 從而減少回溯次數(shù)。最后，本程序的棋盤和數(shù)組類似， 因而采用數(shù)組進(jìn)行存儲(chǔ)， 同時(shí)還有八個(gè) 方向的數(shù)組，和為棧設(shè)計(jì)的每個(gè)點(diǎn)周圍的八個(gè)方向那些可以走的數(shù)組。數(shù)據(jù)初始定義如下 : / /* 馬 的 變 遍 歷 問(wèn) 題 */ /#include <

13、;stdio.h>int f1111 ;/* 定義一個(gè)矩陣來(lái)模擬棋盤 */int adjm121121;/* 標(biāo)志矩陣，即對(duì)于上述棋盤，依次進(jìn)行編號(hào)1-121（行優(yōu)先）可以從一個(gè)棋盤格i跳到棋盤格j時(shí)，adjmij=1*/*將標(biāo)志矩陣相應(yīng)位置置 1*/*巡游函數(shù)聲明 */創(chuàng)建標(biāo)志矩陣子函數(shù)創(chuàng)建標(biāo)志矩陣子函數(shù)void creatadjm()int i,j;for(i=1;i<=n;i+) /* 遍歷矩陣初始化 */ for(j=1;j<=n;j+)fij=0;for(i=1;i<=m;i+)/* 標(biāo)志矩陣初始化 */for(j=1;j<=m;j+)adjmij=0;

14、for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(fij=0) /* 對(duì)所有符合條件的標(biāo)志矩陣種元素置 1*/ fij=1;if(i+2<=n)&&(j+1<=n) mark(i,j,i+2,j+1);if(i+2<=n)&&(j-1>=1) mark(i,j,i+2,j-1);if(i-2>=1)&&(j+1<=n) mark(i,j,i-2,j+1);if(i-2>=1)&&(j-1>=1) mark(i,j,i-2,j-1);if(j+2<

15、=n)&&(i+1<=n) mark(i,j,i+1,j+2);if(j+2<=n)&&(i-1>=1) mark(i,j,i-1,j+2);if(j-2>=1)&&(i+1<=n) mark(i,j,i+1,j-2);if(j-2>=1)&&(i-1>=1) mark(i,j,i-1,j-2);return;巡游子函數(shù)：、巡游子函數(shù)/*棋盤矩陣的置 r 時(shí)，置 0*/* 跳步計(jì)數(shù)加 1*/* 還原棋盤矩陣的橫坐標(biāo) */void travel(int p,int r)int i,j,q;f

16、or(i=1;i<=n;i+)for(j=1;j<=n;j+) if(fij>r) fij=0;r=r+1;i=(p-1)/n)+1;j=(p-1)%n)+1;fij=r;/* 還原棋盤矩陣的縱坐標(biāo) */*將fij做為第r跳步的目的地*/for(q=1;q<=m;q+)/*從所有可能的情況出發(fā)，開(kāi)始進(jìn)行試探式巡游 */i=(q-1)/n)+1;j=(q-1)%n)+1; if(adjmpq=1)&&(fij=0) travel(q,r);/* 遞歸調(diào)用自身 */ return;賦值子函數(shù)賦值子函數(shù)void mark(int i1,int j1,int i

17、2,int j2)adjm(i1-1)*n+j1(i2-1)*n+j2=1;adjm(i2-1)*n+j2(i1-1)*n+j1=1; return;主函數(shù)： void main()提示輸入起點(diǎn)位置，這里的起點(diǎn)位置就是日常生活觀念中的順序，開(kāi)始點(diǎn) 是(1,1), 而不是數(shù)組中的初始位置 (0,0), 輸入錯(cuò)誤則無(wú)效，時(shí)間復(fù)雜度為。主函數(shù)*/int main()int i,j,k,l;printf("Please input size of the chessboard: "); /*輸入矩陣的大小值 */ scanf("%d",&n);m=n*n

18、;/* 創(chuàng)建標(biāo)志矩陣 */* 打印輸出標(biāo)志矩陣 */creatadjm();puts("The sign matrix is:");for(i=1;i<=m;i+) for(j=1;j<=m;j+) printf("%2d",adjmij);printf("n");printf("Please input the knight's position (i,j): "); /* 輸入騎士的初始位置 */scanf("%d %d",&i,&j);l=(i-1)*n

19、+j;while (i>0)|(j>0)for(i=1;i<=n;i+)for(j=1;j<=n;j+)fij=0;k=0;travel(l,k);/* 騎士當(dāng)前位置對(duì)應(yīng)的標(biāo)志矩陣的橫坐標(biāo) */* 對(duì)騎士位置的判斷 */* 棋盤矩陣初始化 */* 所跳步數(shù)計(jì)數(shù) */ /* 從 i,j 出發(fā)開(kāi)始巡游 */puts("The travel steps are:");/* 巡游完成后輸出巡游過(guò)程 */for(i=1;i<=n;i+)for(j=1;j<=n;j+) printf("%4d",fij);printf("

20、;n");printf("Please input the knight's position (i,j): ");/* 為再次巡游輸入起始位置 */ scanf("%d %d",&i,&j);l=(i-1)*n+j;puts("n Press any key to quit. "); /*輸入( 0，0)作為結(jié)束標(biāo)準(zhǔn) */ getch();return 0;運(yùn)行與測(cè)試 ： 程序運(yùn)行開(kāi)始時(shí)，提示用戶輸入棋盤大小，再次輸入，提示輸入橫縱坐標(biāo)， 用回車鍵分隔。出現(xiàn)結(jié)果，顯示坐標(biāo)形式；提示可重新輸入，輸入 0 0 表示結(jié)束 標(biāo)志。運(yùn)行結(jié)果舉例:小結(jié)鞫氓在讖門馬的題即、馬“tmi飢旳轄電QIPlea-eoof t hai t 9Ploctco irtput 1114 knJ a )os it dan < j 相菲t和蓍.：2 GTJie Lr-aUe L streps arc S丄8522.3207L0±33 2416J.122183M 174bb22歲14112S314015“S34