算法及數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書

1、目錄摘 要3一求素數(shù)問題41.1 采用類C語言定義相關(guān)的數(shù)據(jù)類型41.2算法設(shè)計41.3函數(shù)的調(diào)用關(guān)系圖51.4調(diào)試分析51.5測試結(jié)果61.6 源程序（帶注釋）7二猴子摘桃子問題92.1采用類C語言定義相關(guān)的數(shù)據(jù)類型92.2算法設(shè)計92.3函數(shù)調(diào)用關(guān)系圖102.4調(diào)試分析112.5測試結(jié)果112.5源程序（帶注釋）13三跳馬問題163.1采用類語言定義相關(guān)的數(shù)據(jù)類型163.2算法設(shè)計163.3函數(shù)的調(diào)用關(guān)系圖173.4調(diào)試分析173.5測試結(jié)果183.6.源程序（帶注釋）19四.可以使n個城市連接的最小生成樹254.1采用類C語言定義相關(guān)的數(shù)據(jù)類型254.2算法設(shè)計254.3函數(shù)的調(diào)用關(guān)系圖

2、274.4調(diào)試分析274.5測試結(jié)果284.6源程序（帶注釋）29總 結(jié)32參考文獻33致 謝34摘 要素數(shù)問題主要是運用數(shù)據(jù)邏輯結(jié)構(gòu)。采用指針數(shù)組，算法進行求解。猴子吃桃子桃子問題主要運用了數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)。采用數(shù)組，連式存儲結(jié)構(gòu)和遞歸調(diào)用進行。跳馬問題要求在8*8的64個國際象棋格子,任意位置放一個馬,如何不重復(fù)地把格子走完。給定一個8*8的棋盤，起始點在某坐標(biāo)處，要求求出有多少種方法，可以不重復(fù)的遍歷棋盤上所有的點規(guī)則：1.馬走日字2.走過的點就不能再走。構(gòu)造可以使n個城市連接的最小生成樹問題給定一個地區(qū)的n個城市間的距離網(wǎng),城市間的距離網(wǎng)采用鄰接矩陣表示,鄰接矩陣的存儲結(jié)

3、構(gòu)定義,關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；鄰接矩陣；類C語言；數(shù)組；普里姆算法34一求素數(shù)問題埃拉托色尼篩法（Sieve of Eratosthenes）是一種用來求所有小于N的素數(shù)的方法。從建立一個整數(shù)2N的表著手，尋找 i的整數(shù)，編程實現(xiàn)此算法，并討論運算時間。1.1 采用類C語言定義相關(guān)的數(shù)據(jù)類型定義一個線性表順序存儲結(jié)構(gòu)，用來求所有小于N的素數(shù)typedef int DataType;/數(shù)據(jù)類型typedef structDataType datamaxsize;定義一個一維數(shù)組int length;/線性表中實際元素的個數(shù)Seqlist;1.2算法設(shè)計 順序存儲結(jié)構(gòu)是存儲結(jié)構(gòu)類型中的一種，該結(jié)構(gòu)是把

4、邏輯上相鄰的節(jié)點存儲在物理位置上相鄰的存儲單元中，結(jié)點之間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。本程序通過建立一個指針數(shù)組為其分配一個空間，在通過埃拉托色尼篩法通過判斷將其輸出。 for( m1=1;m1<j1;m1+) if(numm1!=0) for(p1=m1+1;p1<n1;p1+) a1=nump1%numm1; if(a1=0) nump1 = 0; 1.3函數(shù)的調(diào)用關(guān)系圖1. 如圖1.1函數(shù)調(diào)用關(guān)系圖Main()print()圖1.1 函數(shù)調(diào)用關(guān)系圖 1.4調(diào)試分析1 當(dāng)m的值大于maxsize的值是發(fā)生越界問題，在輸入m時要確保m的值要小于maxsize的值圖1.2

5、開始界面2 算法的時間復(fù)雜度O(L.length-1)+O(m)。1.5測試結(jié)果1 圖1為2200數(shù)的表 圖1.3表2 圖2為1m之間的素數(shù)圖1.4運行結(jié)果3 圖3為m大于L.length時的圖圖1.5大于L.lenggth1.6 源程序（帶注釋）#include <stdio.h>#include <math.h>#define maxsize 200#define FALSE 0typedef int DataType;typedef struct DataType datamaxsize; int length;Seqlist;/結(jié)點結(jié)構(gòu)int sushu(Dat

6、aType i)/判斷是否為素數(shù) int m; if(i=1) return 0; for(m=2;m<i;m+) if(i%m=0) return 0; return 1;int main() Seqlist L; int m,j; int i,k=0; L.length=maxsize; for(j=2;j<=L.length ;j+) L.dataj-1=j; printf("%dt",L.dataj-1); printf("n"); printf("input m:n"); scanf("%d"

7、,&m); if(m>L.length ) return FALSE; printf("1至m之間的素數(shù)從小到大分別為:n"); for(i=1;i<=m ;i+) L.datai-1=i; for(i=1;i<=m;i+) if(sushu(L.datai-1) k+; printf("%dt",L.datai-1); /符號"t"的作用是橫向制表。 printf("n總共%d個。n",k ); return 0; 二猴子摘桃子問題 有一群猴子摘了一堆桃子，他們每天都吃當(dāng)前桃子的一半且再

8、多吃一個，到了第10天就只余下一個桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃子。要求：1)采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解；2)采用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解；3)采用遞歸實現(xiàn)上述求解。2.1采用類C語言定義相關(guān)的數(shù)據(jù)類型1、采用數(shù)組數(shù)據(jù)結(jié)構(gòu)在函數(shù)中定義數(shù)組peach_tal210來存儲每天剩下的桃子總數(shù)利用while循環(huán)來輸出每天剩下的桃子總數(shù).2、采用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)構(gòu)建創(chuàng)建鏈棧stack2，stack2 IT2(stack2 *s2)，void push2(stack2 *s2,int num2)，void peach_lianzhan2(stack2 *s2)。3、采用遞歸算法 利用fo

9、r循環(huán)，來調(diào)用遞歸函數(shù)，2.2算法設(shè)計 1.一維數(shù)組解決。建立一個一維數(shù)組a10從第九天開始算起令a9=1利用for循環(huán)計算前八天猴子吃的桃子數(shù)目并同時將后一天吃的桃子數(shù)賦值到前一天。最后即可得出猴子一共吃的桃子數(shù)。void peach_shuzu2( )int i2=0, j2=0 ,peach_tal210;peach_tal2days2-1=1;i2=days2;2鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)解決：鏈棧用鏈表作為存儲結(jié)構(gòu)，棧初始化時僅需給棧頂指針分配內(nèi)存空間，而后每當(dāng)有數(shù)據(jù)入棧時再為該數(shù)據(jù)分配空間，這樣實現(xiàn)了內(nèi)存空間的動態(tài)分配。通過鏈棧定義了棧頂*t2和棧底*l2;利用每計算一次就出棧并且計算下一天直到

10、結(jié)束。并將后一天的之賦值給前一天。最后便可得到猴子吃的總的桃子數(shù)。typedef struct 、int *t2;int *l2;stack2;stack2 IT2(stack2 *s2) s2->l2=(int *)malloc(MAX2*sizeof(int); if(s2->l2=NULL) printf(" stack2 initial fail!n"); 3.遞歸函數(shù)解決：遞歸過程一般通過函數(shù)或子過程來實現(xiàn)。遞歸方法：在函數(shù)或子過程的內(nèi)部，直接或者間接地調(diào)用自己的算法。使用if函數(shù)控制是否調(diào)用函數(shù)本身。桃子數(shù)等與一這說明第九天吃了一個桃子函數(shù)便可以結(jié)束

11、。如果桃子數(shù)不為一則一直調(diào)用函數(shù)本身知道調(diào)用結(jié)束。void peach_digui2(int n2,int i2) if(i2=days2) peach_digui2(n2,i2); 2.3函數(shù)調(diào)用關(guān)系圖1.如圖2.1函數(shù)調(diào)用關(guān)系圖main()menu()peach_lianzha()peach_shuzu()peach_digui()exit()圖2.1 函數(shù)調(diào)用關(guān)系圖2.4調(diào)試分析(1)遇到的問題剛開始時，每一個算法我都是單獨的一個程序來實現(xiàn)，基本上沒有出現(xiàn)問題，在將所有方法、程序做好后，再將所有程序集合在一起，利用主函數(shù)的菜單來分塊調(diào)用以實現(xiàn)題目要求。在整合過程中，出現(xiàn)了一些編輯錯誤，但

12、是都是比較小的錯誤，很快就找出來了，應(yīng)該說整個程序做的過程還是比較順利的。(2)算法的時間復(fù)雜度和空間復(fù)雜度 a.時間復(fù)雜度： (1)數(shù)組解決：O(1) 2)鏈棧解決：O(n) (3)遞歸解決：O(n) b.空間復(fù)雜度： (1)數(shù)組解決：O(n) (2)鏈棧解決：O(n) (3)遞歸解決：O(n)2.5測試結(jié)果2.如圖2.2測試界面操作圖2.2 3. 如圖2.3數(shù)組測試結(jié)果操作 圖2.3 4. 圖2.4鏈棧測試結(jié)果操作圖2.4 5如圖2.5遞歸測試結(jié)果圖2.5 2.5源程序（帶注釋）#include<stdio.h>#include<stdlib.h>#include&

13、lt;math.h>#define MAX 50#define days 10#define ERROR 0#define TURE 1void peach_shuzu2( )int i2=0, j2=0 ,peach_tal210;peach_tal2days2-1=1;/最后一天桃子數(shù)i2=days2; while(i2>0)/判斷天數(shù)是否符合要求 peach_tal2j2=2*(peach_tal2i2+1);/該天桃子數(shù) i2=i2-1; j2=i2-1;void pop2(stack2 *s2,int &num2) if(s2->t2=NULL)/判斷棧是否

14、為空 printf("error"); else s2->t2-; num2=*s2->t2;void peach_lianzhan2(stack2 *s2)int i2=0,num2=0; push2(s2,1);/進行第一天運算 i2+; for(i2;i2<days2;i2+)/判斷天數(shù)是否符合 pop2(s2,num2); push2(s2,num2); void peach_digui2(int n2,int i2) if(i2=days2)/判斷天數(shù) else n2=2*(n2+1); /計算桃子數(shù) i2+; peach_digui2(n2,i

15、2)；/返回函數(shù)繼續(xù)計算int menu(int m) printf("ttt-n");printf("ttt-1.數(shù)組-n");printf("ttt-2.鏈棧-n");printf("ttt-3.遞歸-n");printf("ttt-4.退出-n"); printf("please input number:"); scanf("%d",&m); return m;int main() int i=1,n=1,m;stack s; s=IT(&

16、amp;s);while(1) switch(menu(m) case 1: peach_shuzu();break; case 2: peach_lianzhan(&s);break; case 3: peach_digui(n,i);break; case 4: exit(0);break; return 0 ;三跳馬問題 要求在64個國際象棋格子,任意位置放一個馬,如何不重復(fù)地把格子走完。3.1采用類語言定義相關(guān)的數(shù)據(jù)類型#define MAXNUM 8 /橫縱格數(shù)最大值 #define INVALIDDIR - 1 /無路可走的情況 #define MAXLEN 64 /棋盤總

17、格數(shù) #define MAXDIR 8 /下一步可走的方向 typedef struct int x; /表示橫坐標(biāo) int y; /表示縱坐標(biāo) int direction; /表示移動方向 HorsePoint; HorsePoint ChessPathMAXLEN; /模擬路徑棧 int count; /入棧結(jié)點個數(shù)int ChessBoardMAXNUMMAXNUM; /標(biāo)志棋盤數(shù)組3.2算法設(shè)計棋盤初始化的數(shù)組,通過建立Initiai()函數(shù)。將馬沒有在棋盤上走過的位置初始化為0，用ChessBoardij=0;表示。其代碼如下：void Initial() /棋盤初始化的數(shù)組int

18、i,j;for(i=0;i<MAXNUM;i+)for(j=0;j<MAXNUM;j+)ChessBoardij=0; /棋盤格均初始化為0，表示沒有走過for(i=0;i<MAXLEN;i+)ChessPathi.x=0;ChessPathj.y=0;ChessPathi.direction=INVALIDDIR;count=0; / 棧中最初沒有元素3.3函數(shù)的調(diào)用關(guān)系圖函數(shù)的調(diào)用關(guān)系圖如圖3.1所示圖3.1 函數(shù)調(diào)用關(guān)系圖開始數(shù)組初始化數(shù)組為1時,表示已走過數(shù)組為0表未走走下一個結(jié)點判斷是否小于NUM,大于返回上一結(jié)點小于則繼續(xù)往下走圖3.1 函數(shù)的調(diào)用關(guān)系圖3.4調(diào)試

19、分析關(guān)于時間復(fù)雜度的計算是按照運算次數(shù)來進行的, 關(guān)于空間復(fù)雜度的計算是在程序運行過程所要借助的內(nèi)容空間大小。即：空間復(fù)雜是儲存空間的大小和變換等等決定的時間復(fù)雜是邏輯比較、賦值等基本運算的次數(shù)決定的3.5測試結(jié)果 （1）輸入初始值 2，4 0，0（2）測試結(jié)果如圖3.2 圖3.3所示圖3.2 測試結(jié)果圖3.3 測試結(jié)果3.6.源程序（帶注釋） #include<stdio.h>#include<stdlib.h>#define MAXNUM 8 /橫縱格數(shù)最大值#define INVALIDDIR - 1 /無路可走的情況#define MAXLEN 64 /棋盤總格

20、數(shù)#define MAXDIR 8 /下一步可走的方向typedef struct int x; /表示橫坐標(biāo)int y; /表示縱坐標(biāo)int direction; /表示移動方向HorsePoint;HorsePoint ChessPathMAXLEN; /模擬路徑棧int count; /入棧結(jié)點個數(shù)int ChessBoardMAXNUMMAXNUM; /標(biāo)志棋盤數(shù)組void Initial() /棋盤初始化的數(shù)組int i,j;for(i=0;i<MAXNUM;i+)for(j=0;j<MAXNUM;j+)ChessBoardij=0; /棋盤格均初始化為0，表示沒有走過f

21、or(i=0;i<MAXLEN;i+)ChessPathi.x=0;ChessPathj.y=0;ChessPathi.direction=INVALIDDIR;count=0; / 棧中最初沒有元素void PushStack(HorsePoint positon) /入棧函數(shù)ChessBoardpositon.xpositon.y=1; /把標(biāo)志設(shè)為1，證明已走過ChessPathcount=positon;count+;HorsePoint PopStack() /出棧函數(shù) HorsePoint positon;count-;positon=ChessPathcount;Chess

22、Boardpositon.xpositon.y=0;ChessPathcount.direction=INVALIDDIR;return positon;HorsePoint GetInitPoint() /輸入horse的起始坐標(biāo)HorsePoint positon;doprintf("n請輸入起始點(x,y):");scanf("%d,%d",&positon.x,&positon.y);printf("nn");while(positon.x>=MAXNUM|positon.y>=MAXNUM|pos

23、iton.x<0|positon.y<0); /不超過各個邊緣positon.direction=INVALIDDIR; /是初值，沒走過return positon;HorsePoint GetNewPoint(HorsePoint *parent) /產(chǎn)生新結(jié)點函數(shù)int i;HorsePoint newpoint;int tryxMAXDIR=1,2,2,1,-1,-2,-2,-1; /能走的8個方向坐標(biāo)增量int tryyMAXDIR=-2,-1,1,2,2,1,-1,-2;newpoint.direction=INVALIDDIR; /新結(jié)點可走方向初始化parent-&

24、gt;direction=parent->direction+; /上一結(jié)點能走的方向for(i=parent->direction;i<MAXDIR;i+)newpoint.x=parent->x+tryxi; /試探新結(jié)點的可走方向newpoint.y=parent->y+tryyi;if(newpoint.x<MAXNUM&&newpoint.x>=0&&newpoint.y<MAXNUM&&newpoint.y>=0&&ChessBoardnewpoint.xnewpo

25、int.y=0)parent->direction=i; /上一結(jié)點可走的方向ChessBoardnewpoint.xnewpoint.y=1; /標(biāo)記已走過return newpoint;parent->direction=INVALIDDIR;return newpoint;void CalcPoint(HorsePoint hh ) /計算路徑函數(shù)HorsePoint npositon;HorsePoint *ppositon;Initial(); /調(diào)用初始化函數(shù)ppositon=&hh; /調(diào)用輸入初始點函數(shù)PushStack(*ppositon);while(!

26、(count=0|count=MAXLEN) /當(dāng)路徑棧不滿或不空時ppositon=&ChessPathcount-1; /指針指向棧npositon=GetNewPoint(ppositon); /產(chǎn)生新的結(jié)點if(ppositon->direction!=INVALIDDIR) /可以往下走ChessPathcount-1.direction=ppositon->direction;PushStack(npositon);else PopStack();void PrintChess() /以8*8矩陣的形式輸出運行結(jié)果int i,j;int stateMAXNUMM

27、AXNUM; /stateij為棋盤上（i,j）點被踏過的次序int step=0; /行走初始化HorsePoint positon;count=MAXLEN;if(count=MAXLEN) /當(dāng)棋盤全部走過時for(i=0;i<MAXLEN;i+)step+;positon=ChessPathi;statepositon.xpositon.y=step;for(i=0;i<MAXNUM;i+)printf("tt");for(j=0;j<MAXNUM;j+)if(stateij<10)printf(" ");printf(&

28、quot;%6d",stateij); /按順序輸出馬踏過的點printf("n");printf("n");elseprintf("tt此時不能踏遍棋盤上所有點!n");int main(int argc,char *argv)HorsePoint h;h=GetInitPoint();CalcPoint(h);PrintChess();return 0;四.可以使n個城市連接的最小生成樹4.1采用類C語言定義相關(guān)的數(shù)據(jù)類型鄰接矩陣,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;鄰接矩陣的存儲

29、結(jié)構(gòu)定義, MGraph最小值判斷minsideMAX_VERTEX_NUM;普利姆算法PRIM(MGraph G,VertexType u)4.2算法設(shè)計 假設(shè) WN=(V,E) 是一個含有 n 個頂點的連通網(wǎng)，TV 是 WN 上最小生成樹中頂點的集合，TE 是最小生成樹中邊的集合。顯然，在算法執(zhí)行結(jié)束時，TV=V，而 TE 是 E 的一個子集。在算法開始執(zhí)行時，TE 為空集，TV 中只有一個頂點，因此，按普里姆算法構(gòu)造最小生成樹的過程為：在所有“其一個頂點已經(jīng)落在生成樹上，而另一個頂點尚未落在生成樹上”的邊中取一條權(quán)值為最小的邊，逐條加在生成樹上，直至生成樹中含有 n-1條邊為止。通過教材

30、給出的結(jié)構(gòu)再加自己的想法，通過定義鄰接矩陣，領(lǐng)用普利姆算法選著選著最小值在判斷。typedef structVRType adj; ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum;intarcnum; MGraph;typedef structVertexType adjvex;VRType lowcost;minsideMAX_VERTEX_NUM;void PRIM(MGraph G,VertexType

31、u)int i,j,k,s=0;minside closedge;k=LocateVex(G,u);for(j=0;j<G.vexnum;+j) if(j!=k)strcpy(closedgej.adjvex,u);closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0; for(i=1;i<G.vexnum;i+) k=minimum(closedge,G); printf("(%s-%s)t%dn",closedgek.adjvex,G.vexsk,closedgei.lowcost); s+=closedgek

32、.lowcost;closedgek.lowcost=0; for(j=0;j<G.vexnum;j+)if(G.arcskj.adj<closedgej.lowcost)strcpy(closedgej.adjvex,G.vexsk);closedgej.lowcost=G.arcskj.adj; printf("%dn",s);4.3函數(shù)的調(diào)用關(guān)系圖如圖4.1函數(shù)調(diào)用關(guān)系圖main()GreatAN()LocateVex()display()minimum()PRIM()圖4.1 函數(shù)調(diào)用關(guān)系圖 4.4調(diào)試分析 (1)遇到的問題 a.依據(jù)書上給的定義敲入代碼

33、時，無法執(zhí)行。 解決方法：通過查閱資料，查找相似的例子，通過分析，再看課本不斷理解，不斷試運行才得以解決。 (2)算法的時間復(fù)雜度和空間復(fù)雜度 通過對PRIM算法的分析具體方法是假定在進行第k次前已經(jīng)保留著從T中到T外的每一頂點（共n-k個頂點）的各一條最短邊，進行第k次時，首先從這n-k條最短邊中，找出一條最最短的邊，它就是從T中到T外的所有邊中的最短邊，假設(shè)為（i,j），此步需進行n-k次比較；然后把邊（i,j）和頂點j分別并入T中的邊集TE和頂點集U中，此時T外只有n-(k+1)個頂點，對于其中的每個頂點t，若（j,t）邊上的權(quán)值小于已保留的從原T中到頂點t的最短邊的權(quán)值，則用（j,t）

34、修改之，使從T中到T外頂點t的最短邊為（j,t），否則原有最短邊保持不變，這樣，就把第k次后從T中到T外每一頂點t的各一條最短邊都保留下來了，為進行第k+1次運算做好了準(zhǔn)備，此步需進行n-k-1次比較。所以，利用此方法求第k次的最短邊共需比較2(n-k)-1次，即時間復(fù)雜度為O(n-k)。4.5測試結(jié)果1.如圖4.2測試界面圖4.2 2.如圖4.3測試結(jié)果圖4.3 4.6源程序（帶注釋）#include"stdio.h"#include <limits.h>#include<string.h>#define MAX_VERTEX_NUM 20#def

35、ine MAX_NAME 3#define MAX_INFO 20 #define INFINITY INT_MAXtypedef int VRType;typedef char InfoType;typedef char VertexTypeMAX_NAME;typedef structVertexType adjvex;VRType lowcost;minsideMAX_VERTEX_NUM;void PRIM(MGraph G,VertexType u)/普里姆算法int i,j,k,s=0;minside closedge;/最小權(quán)值k=LocateVex(G,u);/k為頂點u在G中的序號for(j=0;j<G.vexnum;j+) /輔助數(shù)組初始化if(j!=k)strcpy(closedgej.adjvex,u);closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0; /將頂點u并入最小生成樹集合 printf("最小代價生成樹的各條邊為:n");for(i=1;i<G.vexnum;i+) k=minimum(closedge,G); printf("