算法與數(shù)據(jù)結(jié)構(gòu)

1、數(shù)據(jù)結(jié)構(gòu)與算法 課程設(shè)計(jì)題 目：求素?cái)?shù)問題；方程求解問題；最短字符串問題；掃雷問題專業(yè)班級(jí)： 軟件工程三班 目 錄摘 要4一 求素?cái)?shù)問題51.采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型52.算法設(shè)計(jì)53.調(diào)試分析64.測(cè)試結(jié)果65.源程序（帶注釋）6二方程求解問題81.采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型82.算法設(shè)計(jì)83.函數(shù)的調(diào)用關(guān)系圖94.調(diào)試分析95.測(cè)試結(jié)果96.源程序（帶注釋）9三最短字符串問題111.采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型112.算法設(shè)計(jì)113.函數(shù)的調(diào)用關(guān)系圖124.調(diào)試分析125.測(cè)試結(jié)果136.源程序（帶注釋）15四掃雷問題191.采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型192.算法設(shè)計(jì)203.函數(shù)的

2、調(diào)用關(guān)系圖214.調(diào)試分析215.測(cè)試結(jié)果226.源程序（帶注釋）23總 結(jié)27參考文獻(xiàn)28致 謝29摘 要處理了四個(gè)問題：求素?cái)?shù)問題，用埃拉托色尼篩法（Sieve of Eratosthenes）結(jié)合順序表求出所有小于N的素?cái)?shù)；方程求解問題，方程A5+B5+C5+D5+E5=F5剛好有滿足0ABCDEF75的整數(shù)解，利用窮舉循環(huán)求解；最短字符串問題，編寫一個(gè)程序，從輸入中讀取字符串，并按長(zhǎng)度順序，最短字符串優(yōu)先的原則輸出它們。如果有若干，字符串具有相同的長(zhǎng)度，就按字母順序輸出它們；掃雷問題，編寫一個(gè)程序讀取文件，該文件中存放著網(wǎng)格中的行數(shù)、列數(shù)以及網(wǎng)格本身。網(wǎng)格會(huì)含有一些標(biāo)記為O的方塊，這些

3、就是雷。其他方塊不是雷，將會(huì)標(biāo)記上問號(hào)（？）。程序的輸出就是輸出這個(gè)網(wǎng)格。雷依然會(huì)標(biāo)記成O，而那些不含雷的方塊會(huì)替換成一個(gè)數(shù)字，以表明鄰近雷的個(gè)數(shù)。最大數(shù)字將是8。關(guān)鍵詞： 埃拉托色尼篩法；方程求解；最短字符串； 掃雷一 求素?cái)?shù)問題埃拉托色尼篩法（Sieve of Eratosthenes）是一種用來(lái)求所有小于N的素?cái)?shù)的方法。從建立一個(gè)整數(shù)2N的表著手，尋找i#的整數(shù)，編程實(shí)現(xiàn)此算法，并討論運(yùn)算時(shí)間。1.采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型利用順序表存儲(chǔ)結(jié)構(gòu)：typedef structint *elem;int length;int listsize;Sqlist;2.算法設(shè)計(jì)算法描述：先把1刪除（

4、現(xiàn)今數(shù)學(xué)界1既不是質(zhì)數(shù)也不是合數(shù)）；讀取隊(duì)列中當(dāng)前最小的數(shù)2，然后把2的倍數(shù)刪去；讀取隊(duì)列中當(dāng)前最小的數(shù)3，然后把3的倍數(shù)刪去；讀取隊(duì)列中當(dāng)前最小的數(shù)5，然后把5的倍數(shù)刪去；如上所述直到需求的范圍內(nèi)所有的數(shù)均刪除或讀取。算法實(shí)現(xiàn)：Sqlist l;for(int i=1;i=number;i+)l.elemi=i;l.elem1=0;for(int p=2;psqrt(number);p+)for(int j=p+1;j=number;j+)if(l.elemj!=0)&(l.elemj%p=0)l.elemj=0;3.調(diào)試分析由于說(shuō)明書中字符顯示問題，上網(wǎng)搜索埃拉托色尼篩法，了解如何求素?cái)?shù)，

5、用數(shù)組解決了這個(gè)問題。時(shí)間復(fù)雜度是O（n3/2）空間復(fù)雜度是O（n）。4.測(cè)試結(jié)果圖1.1以100為例測(cè)試結(jié)果5.源程序（帶注釋）int InitList_sq(Sqlist &L)L.elem=(int *)malloc(LIST_INIT_SIZE *sizeof(int);if(!L.elem)printf(存儲(chǔ)分配失敗！);L.length=0;L.listsize=LIST_INIT_SIZE;return 0;Sqlist l；for(int i=1;i=number;i+)l.elemi=i;l.elem1=0;for(int p=2;psqrt(number);p+)for(i

6、nt j=p+1;j=number;j+)if(l.elemj!=0)&(l.elemj%p=0)l.elemj=0;二方程求解問題方程A5+B5+C5+D5+E5=F5剛好有一個(gè)滿足0ABCDEF75的整數(shù)解。請(qǐng)編寫一個(gè)求出該解的程序。（3）1. 采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型數(shù)據(jù)聲明和頭文件聲明：#include#include int key();long p76;long A,B,C,D,E,F,i,flag=0;2.算法設(shè)計(jì)算法描述：首先建立數(shù)組，用來(lái)存儲(chǔ)整型ABCDEF五次方的值，然后利用fo嵌套循環(huán)，一次求ABCDEF五次方的值，接下來(lái)用if判斷語(yǔ)句，若ABCDE次方之和與F五次方

7、的差為零，輸出ABCDEF的整數(shù)解。算法實(shí)現(xiàn)：for(i=0;i=75;i+) pi=int(pow(i,5); /把的次方放在數(shù)組中，以便調(diào)用 for(A=0;A=60;A+)/循環(huán)窮舉找到方程的解 for(B=A;B=75;B+)for(C=B;C=75;C+) for(D=C;D=75;D+) for(E=D;E=75;E+) for(F=E;F=75;F+) if(pA+pB+pC+pD+pE-pF=0) printf(ttt%d %d %d %d %d %dnn,A,B,C,D,E,F);3.函數(shù)的調(diào)用關(guān)系圖 4.調(diào)試分析這個(gè)算法說(shuō)明比較容易理解，思路簡(jiǎn)單，就是不容易使用算法與數(shù)據(jù)結(jié)

8、構(gòu)的知識(shí)。時(shí)間復(fù)雜度O(n6),空間復(fù)雜度O(n)。5.測(cè)試結(jié)果圖2.1運(yùn)行后部分結(jié)果截圖6.源程序（帶注釋）#include#include int key() /求方程的解 找到解返回否則返回 long p76; long A,B,C,D,E,F,i,flag=0; for(i=0;i=75;i+) pi=int(pow(i,5); /把的次方放在數(shù)組中，以便調(diào)用 for(A=0;A=60;A+)/循環(huán)窮舉找到方程的解 for(B=A;B=75;B+) for(C=B;C=75;C+) for(D=C;D=75;D+) for(E=D;E=75;E+) for(F=E;F=75;F+) i

9、f(pA+pB+pC+pD+pE-pF=0) printf(ttt%d %d %d %d %d %dnn,A,B,C,D,E,F); flag=1; if(flag=1) return 1; else return 0; int main() if(key()=0) printf(方程A5+B5+C5+D5+E5=F5(0=A=BC=D=E=F=75)無(wú)解); return 1;三最短字符串問題編寫一個(gè)程序，從輸入中讀取字符串，并按長(zhǎng)度順序，最短字符串優(yōu)先的原則輸出它們。如果有若干字符串具有相同的長(zhǎng)度，就按字母順序輸出它們。1.采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型首先，將字符串輸入 tempMaxSi

10、ze，然后將數(shù)據(jù)存入str1中，在比較時(shí)引入str2,比較字符串長(zhǎng)度或者字母，將最短的字符串存入str2中，之后調(diào)用輸出函數(shù)輸出。數(shù)據(jù)聲明，預(yù)編譯，頭文件聲明：#include#include#include#define Max 100/預(yù)設(shè)最大字符串個(gè)數(shù)#define MaxSize 256int num;/全局變量num表示輸入字符串個(gè)數(shù)int input(char *str1)int count=0;char tempMaxSize;2.算法設(shè)計(jì)字符串的輸入代碼通過(guò)建立數(shù)組str1,當(dāng)字符串的格數(shù)小于宏定義中num 時(shí)，可以輸入一些字符串。字符串的排序代碼當(dāng)輸入字符串時(shí)，調(diào)用函數(shù) so

11、rt() 進(jìn)行排序，更具字符串的長(zhǎng)短進(jìn)行排序。如果字符串長(zhǎng)度相同時(shí)，可以更具字母優(yōu)先進(jìn)行排序。算法實(shí)現(xiàn)：int i,j;char tempMaxSize;for(i=0;inum-1;i+)for(j=i+1;jnum;j+)if(strlen(str2j)strlen(str2i)strcpy(temp,str2j);strcpy(str2j,str2i);strcpy(str2i,temp);if(strlen(str2j)=strlen(str2i)if(strcmp(str2j,str2i)0)strcpy(temp,str2j);strcpy(str2j,str2i);strcpy(

12、str2i,temp);puts(排序完畢！);3.函數(shù)的調(diào)用關(guān)系圖最短字符串采用數(shù)組的形式進(jìn)行輸入和排序的，通過(guò)子函數(shù)4.調(diào)試分析調(diào)試中遇到的問題及對(duì)問題的解決方法輸入數(shù)據(jù)看是否滿足需求,采用順序表進(jìn)行存儲(chǔ)。時(shí)間復(fù)雜度：T(n)=O(n)，空間復(fù)雜度：S(n)=O(2n)。5.測(cè)試結(jié)果圖3.1菜單圖3.2輸入字符串圖3.3排序圖3.4輸出排序結(jié)果6.源程序（帶注釋）#include#include#include#define Max 100/預(yù)設(shè)最大字符串個(gè)數(shù)#define MaxSize 256int num; /全局變量num表示輸入字符串個(gè)數(shù)/字符串輸入函數(shù)int input(cha

13、r *str1)int count=0;char tempMaxSize;printf(輸入字符串個(gè)數(shù));scanf(%d,&num);while(countnum)printf(輸入第%d個(gè),count+1);if(scanf(%s,temp)&temp0!=0)str1count=(char *)malloc(sizeof(temp);strcpy(str1count,temp);count+;puts(輸入完畢！);return 1;/字符串排序函數(shù)int sort(char *str2)int i,j;char tempMaxSize;for(i=0;inum-1;i+)for(j=i

14、+1;jnum;j+)if(strlen(str2j)strlen(str2i)strcpy(temp,str2j);strcpy(str2j,str2i);strcpy(str2i,temp);if(strlen(str2j)=strlen(str2i)if(strcmp(str2j,str2i)0)strcpy(temp,str2j);strcpy(str2j,str2i);strcpy(str2i,temp);puts(排序完畢！);return 1;/字符串顯示函數(shù)void show(char *str)int i;for(i=0;inum;i+)puts(stri);/菜單函數(shù)voi

15、d menu()puts(=);puts(= 最短字符串問題 =);puts( 1、輸入字符串 );puts( 2、排序字符串 );puts( 3、輸出字符串 );puts( 4、退出 );puts(=);/主函數(shù)int main()int key,flag1=0,flag2=0;char *str1Max;while(1)system(cls);/清屏fflush(stdin);menu();printf(請(qǐng)選擇(1/2/3):n);scanf(%d,&key);if(key=1)flag1=input(str1);else if(key=2)if(flag1)flag2=sort(str1

16、);elseputs(沒有字符串！請(qǐng)選擇1、輸入字符串！);else if(key=3)if(flag1=1&flag2=0)puts(輸入的字符串為：);show(str1);else if(flag1=1&flag2=1)puts(排序后的字符串為：);show(str1);elseputs(沒有字符串！請(qǐng)選擇1、輸入字符串！);else if(key=4)return 0;elseprintf(對(duì)不起，沒有這個(gè)選項(xiàng)!n);system(pause);/暫停 四掃雷問題有些個(gè)人計(jì)算機(jī)會(huì)帶有一個(gè)名為Minesweeper的游戲。該游戲界面是一個(gè)網(wǎng)格，網(wǎng)格中的有些方塊是雷。編寫一個(gè)程序以讀取文

17、件，該文件中存放著網(wǎng)格中的行數(shù)、列數(shù)以及網(wǎng)格本身。網(wǎng)格會(huì)含有一些標(biāo)記為o的方塊，這些就是雷。其他方塊不是雷，將會(huì)標(biāo)記上問號(hào)（？）。程序的輸出就是輸出這個(gè)網(wǎng)格。雷依然會(huì)標(biāo)記成o，而那些不含雷的方塊會(huì)替換成一個(gè)數(shù)字，以表明鄰近雷的個(gè)數(shù)。最大數(shù)字將是8。（4）1.采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)和頭文件聲明：#include windows.h#include iostream#include fstreamtypedef struct _MINERint IsMiner;int MinerNum;MINER,*LPMINER;/結(jié)構(gòu)體及其位置指針 LPMINER m_Array;long m_

18、N;std:ifstream m_ifs;CMiner();/構(gòu)造函數(shù)CMiner();/析構(gòu)函數(shù)int Init(int n);/初始化int Display();int Sweep(int i, int j);int Probe(int i, int j);2.算法設(shè)計(jì)計(jì)算每個(gè)位置周圍雷的算法：每個(gè)雷周圍有八個(gè)位置，其布雷情況可以有循環(huán)算法來(lái)實(shí)現(xiàn)，在循環(huán)中計(jì)算每個(gè)雷周圍的雷數(shù)，我用了靜態(tài)數(shù)據(jù)存儲(chǔ)實(shí)現(xiàn)。算法實(shí)現(xiàn)：int CMiner:Sweep(int i,int j)/掃雷int sum = 0;sum+=Probe(i - 1, j - 1);sum+=Probe(i - 1, j );

19、 sum+=Probe(i - 1, j + 1);sum+=Probe(i , j - 1);sum+=Probe(i , j + 1);sum+=Probe(i +1, j - 1);sum+=Probe(i + 1, j );sum+=Probe(i + 1, j +1);return sum; int CMiner:Probe(int i, int j)/試探if (i 0)return 0;if (j = m_N)return 0;if (j = m_N)return 0;if (m_Arrayi*m_N + j.IsMiner)return 1;return 0;3.函數(shù)的調(diào)用關(guān)系

20、圖開始判定條件進(jìn)行計(jì)算雷數(shù)條件變化語(yǔ)句結(jié)束輸出計(jì)結(jié)果4.調(diào)試分析這個(gè)問題比較復(fù)雜，聽過(guò)同學(xué)幫助和網(wǎng)上搜索，了解算法和程序設(shè)計(jì)，沒有編寫隨機(jī)布雷的算法，只寫了掃雷的算法。時(shí)間復(fù)雜度O(n2),空間復(fù)雜度O(n)。5.測(cè)試結(jié)果圖4.1文件中的8*8雷陣圖4.2掃雷結(jié)果6.源程序（帶注釋）/miner.h#include windows.h#include iostream#include fstreamtypedef struct _MINERint IsMiner;int MinerNum;MINER,*LPMINER;class CMinerpublic:LPMINER m_Array;lon

21、g m_N;std:ifstream m_ifs;CMiner();/構(gòu)造函數(shù)CMiner();/析構(gòu)函數(shù)int Init(int n);/初始化int Display();int Sweep(int i, int j);int Probe(int i, int j);#include Miner.hCMiner:CMiner()CMiner:CMiner()int CMiner:Init(int n)char temp128;m_ifs.open(miner.txt, std:ios_base:app);/ m_Array初始化m_Array = (LPMINER)malloc(sizeof

22、(MINER)*n*n);memset(m_Array, 0, sizeof(MINER)*n*n);m_N = n;int i,j;for ( i = 0; i m_N; i+)m_ifs.getline(temp, 128);for (j = 0; j m_N; j+)if (tempj = O)m_Arrayi*m_N + j.IsMiner = 1;return 0;int CMiner:Display()/展示int i, j;for (i = 0; i m_N; i+)for (j = 0; j m_N; j+)if (m_Arrayi*m_N + j.IsMiner = 0)m_

23、Arrayi*m_N + j.MinerNum=Sweep(i, j);printf(%2d, m_Arrayi*m_N + j.MinerNum);elseprintf( %O);printf(n);return 0;int CMiner:Sweep(int i,int j)/掃雷int sum = 0;sum+=Probe(i - 1, j - 1);sum+=Probe(i - 1, j ); sum+=Probe(i - 1, j + 1);sum+=Probe(i , j - 1);sum+=Probe(i , j + 1);sum+=Probe(i +1, j - 1);sum+=

24、Probe(i + 1, j );sum+=Probe(i + 1, j +1);return sum;int CMiner:Probe(int i, int j)/試探if (i 0)return 0;if (j = m_N)return 0;if (j = m_N)return 0;if (m_Arrayi*m_N + j.IsMiner)return 1;return 0;/SweepMiner.cpp #include stdafx.h#include Miner.hint _tmain(int argc, _TCHAR* argv)CMiner miner1;miner1.Init(

25、8);miner1.Display();system(pause);return 0;總 結(jié)課程設(shè)計(jì)是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí),發(fā)現(xiàn),提出,分析和解決實(shí)際問題,鍛煉實(shí)踐能力的重要環(huán)節(jié),是對(duì)學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過(guò)程.隨著科學(xué)技術(shù)發(fā)展的日新日異，當(dāng)今計(jì)算機(jī)應(yīng)用在是生活中可以說(shuō)得是無(wú)處不在。因此作為二十一世紀(jì)的大學(xué)來(lái)說(shuō)掌握計(jì)算機(jī)開發(fā)技術(shù)十分重要的?；仡櫰鸫舜握n程設(shè)計(jì)，至今我仍感慨頗多，的確，從從拿到題目到完成整個(gè)編程，從理論到實(shí)踐，在整整半個(gè)月的日子里，可以學(xué)到很多很多的的東西，同時(shí)不僅可以鞏固了以前所學(xué)過(guò)的知識(shí)，而且學(xué)到了很多在書本上所沒有學(xué)到過(guò)的知識(shí)。通過(guò)這次課程設(shè)計(jì)使我懂得了理論與實(shí)際相結(jié)合是很重要的，只有理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識(shí)與實(shí)踐相結(jié)合起來(lái)，從理論中得出結(jié)論，才能真正為社會(huì)服務(wù)，從而提高自己的實(shí)際動(dòng)手能力和獨(dú)立思考的能力。在設(shè)計(jì)的過(guò)程中遇到問題，可以說(shuō)得是困難重重，這畢竟第一次做的，難免會(huì)遇到過(guò)各種各樣的問題，同時(shí)在設(shè)計(jì)的過(guò)程中發(fā)現(xiàn)了自己的不足之處，對(duì)以前所學(xué)過(guò)的知識(shí)理解得不夠深刻，掌握得不夠牢固，通過(guò)這次課程設(shè)計(jì)之后，一定把以前所學(xué)過(guò)的知識(shí)重新溫故。在課程設(shè)計(jì)過(guò)程中，我學(xué)到了很多人生的哲理，懂得怎么樣去制定計(jì)劃，怎么樣去實(shí)現(xiàn)這個(gè)計(jì)劃，并掌握了在執(zhí)行過(guò)程中怎么樣去克服心理