課程設(shè)計(jì)報(bào)告---文章編輯、猴子選大王、建立二叉樹、拓?fù)渑判?、各種排序

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：24 大?。?99.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

2023年全國(guó)碩士研究生考試考研英語一試題真題（含答案詳解+作文范文）_第1頁(yè)

已閱讀1頁(yè)，還剩23頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　課程設(shè)計(jì)　　2009 ~ 2010學(xué)年第二學(xué)期　　設(shè)計(jì)題目文章編輯、猴子選大王、建立二叉樹、拓?fù)渑判颉⒏鞣N排序 　　目錄<

2、;p>　　1、目的與要求2　　2、課程設(shè)計(jì)內(nèi)容說明3　　2.1主菜單界面：3　　2.2項(xiàng)目一：文章編輯**3　　2.3項(xiàng)目二：猴子選大王**4　　2.4項(xiàng)目三：建立二叉樹，層序、先序遍歷**6<

3、/p>　　2.5項(xiàng)目四：拓?fù)渑判?　　2.6項(xiàng)目五：各種排序：插入排序和改進(jìn)冒泡排序算法10　　5、結(jié)論及體會(huì)14　　6、附錄14　　目的與要求<

4、/p>　　鞏固和加深對(duì)常見數(shù)據(jù)結(jié)構(gòu)的理解和掌握　　掌握基于數(shù)據(jù)結(jié)構(gòu)進(jìn)行算法設(shè)計(jì)的基本方法　　掌握用高級(jí)語言實(shí)現(xiàn)算法的基本技能　　掌握書寫程序設(shè)計(jì)說明文檔的能力　　提高運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識(shí)及高級(jí)語言解決非數(shù)值實(shí)際問題的能力&l

5、t;p>　　課程設(shè)計(jì)內(nèi)容說明　　主菜單界面：　　項(xiàng)目一：文章編輯**　　（1）功能：輸入一頁(yè)文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。　　靜態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過80個(gè)字符，共N行

6、；要求（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。　　存儲(chǔ)結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；　　輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。　　輸出形式：（1）分行輸

7、出用戶輸入的各行字符；（2）分4行輸出"全部字母數(shù)"、"數(shù)字個(gè)數(shù)"、"空格個(gè)數(shù)"、"文章總字?jǐn)?shù)"（3）輸出刪除某一字符串后的文章；　?。?）程序的輸入輸出描述：　　進(jìn)入應(yīng)用程序：

8、　?。?）輸入文章：　　（2）查找：　?。?）刪除：原文為：QuYing111，刪除Y后為:Quing111　?。?）尚未解決的問題或改進(jìn)方向　　這個(gè)文章編輯的缺點(diǎn)在于無法統(tǒng)計(jì)空格數(shù)，只能夠統(tǒng)計(jì)大小寫字母以及數(shù)字&

9、lt;/p>　?。?）對(duì)軟件的使用說明　　在CFree4.0下打開軟件，進(jìn)行操作　　項(xiàng)目二：猴子選大王**　　對(duì)設(shè)計(jì)任務(wù)內(nèi)容的概述　　一堆猴子都有編號(hào)，編號(hào)是1，2，3 ...m ,這群猴子（m個(gè)）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到

10、第N個(gè)，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。　　需求分析或功能描述　　輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，n<m　　輸出形式：中文提示按照m個(gè)猴子，數(shù)n 個(gè)數(shù)的方法，輸出為大王的猴子是幾號(hào) ，建立一個(gè)函數(shù)來實(shí)現(xiàn)此功能。<

11、/p>　　程序輸入輸出描述：　　開始程序：　　部分程序代碼：　　#define MaxSize 50　　int houzi(int

12、 n,int m)　　{　　int p[MaxSize];　　int i,j,t;　　for(i=0;i<n;i++)　　p[i]=i+1;<

13、/p>　　t=0;　　printf("\n出列順序:");　　for(i=n;i>=1;i--)　　{　　t=(t+m-1)%i;</p

14、>　　printf("%d",p[t]);　　for(j=t+1;j<=i-1;j++)　　p[j-1]=p[j];　　} printf("\n");　　printf("\n故編號(hào) %d

15、的猴子是大王!\n",p[t]);　　printf("\n");　　}　　項(xiàng)目三：建立二叉樹，層序、先序遍歷**　　（1）對(duì)設(shè)計(jì)任務(wù)內(nèi)容的概述　　要求能夠輸入樹

16、的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；　?。?）需求分析或功能描述　　程序功能包括，建立二叉樹，輸出二叉樹，對(duì)二叉樹進(jìn)行層次遍歷和先序遍歷。　?。?）概要設(shè)計(jì)或程序流程圖

17、進(jìn)入程序，選擇菜單，1創(chuàng)建二叉樹，在程序中進(jìn)行構(gòu)造二叉樹，并輸出創(chuàng)建好的二叉樹，2層次遍歷二叉樹，輸出二叉樹的層次遍歷序列，3先序遍歷二叉樹，輸出二叉樹的先序遍歷序列。　?。?）詳細(xì)設(shè)計(jì)或源代碼說明　　創(chuàng)建二叉樹CreateBTNode（*b，*str）。根據(jù)二叉樹括號(hào)表示的字符串*str生成對(duì)應(yīng)的二叉鏈存儲(chǔ)結(jié)構(gòu)，用ch掃描采用括號(hào)表示法表示二叉樹的字符

18、串。輸出二叉樹，以括號(hào)表示法輸出一棵二叉樹。先序遍歷二叉樹的過程是，訪問根結(jié)點(diǎn)，先序遍歷左子樹，先序遍歷右子樹。層次遍歷的過程是，先將根結(jié)點(diǎn)進(jìn)隊(duì)，在隊(duì)不為空時(shí)循環(huán)，從隊(duì)列中出列一個(gè)結(jié)點(diǎn)*p，訪問它，若它有左孩子結(jié)點(diǎn)，如此操作直到隊(duì)空為止。 　　（5）程序模塊及其接口描述　　typedef char ElemType;<p&g

19、t;　　typedef struct node　　{　　ElemType data;//數(shù)據(jù)元素 　　struct node *lchild;//指向左孩子 　　struct node *rchild;//指向右孩子 </p&g

20、t;　　}BTNode;　　void CreateBTNode(BTNode *&b,char *str)//由str串創(chuàng)建二叉鏈　　void DispBTNode(BTNode *b)//以括號(hào)表示法輸出二叉樹　　void TravLevel

21、(BTNode *b)//層次遍歷　　void PreOrder(BTNode *b)//先序遍歷的遞歸算法　?。?）程序的輸入與輸出描述　　輸入界面：　　輸出界面：<

22、;p>　　（7）調(diào)試分析或程序測(cè)試　?。?）尚未解決的問題或改進(jìn)方向　　因?yàn)楸境绦蜃罱K要與其他兩個(gè)程序合并在一起，在主界面進(jìn)行選擇。所以在進(jìn)入主界面時(shí)要在本程序的主函數(shù)處修改字符，否則在調(diào)用本程序時(shí)主函數(shù)會(huì)發(fā)生沖突。　　（9）對(duì)軟件的使用說明　　在CFree4.0下

23、打開軟件，進(jìn)行操作。　　項(xiàng)目四：拓?fù)渑判?lt;/b>　　對(duì)設(shè)計(jì)任務(wù)內(nèi)容的概述　　編寫函數(shù)，實(shí)現(xiàn)圖的拓?fù)渑判颉?lt;/p>　　需求分析或功能描述　　在一個(gè)有向圖中找一個(gè)拓?fù)湫蛄械倪^

24、程稱為拓?fù)渑判?，而每一個(gè)有向圖的拓?fù)湫蛄胁⒉晃ㄒ?，本程序的功能就是將用戶輸入的序列進(jìn)行拓?fù)渑判颉?lt;/p>　　概要設(shè)計(jì)或程序流程圖　　在程序菜單中選擇開始，輸入有向圖的結(jié)點(diǎn)數(shù)和邊數(shù)，此時(shí)程序就會(huì)輸出結(jié)點(diǎn)信息，如v1，v2，v3等，接下來會(huì)要求用戶輸入第一條邊的起點(diǎn)和終點(diǎn)，通過程序運(yùn)行就可以輸出拓?fù)渑判蚪Y(jié)果。　　詳細(xì)設(shè)計(jì)或源

25、代碼說明　　對(duì)于給定的有向圖，采用鄰接表作為存儲(chǔ)結(jié)構(gòu)，為每個(gè)頂點(diǎn)設(shè)置一個(gè)鏈表，每個(gè)鏈表有一個(gè)表頭結(jié)點(diǎn)，這些表頭結(jié)點(diǎn)構(gòu)成一個(gè)數(shù)組，表頭結(jié)點(diǎn)中增加一個(gè)存放頂點(diǎn)入度的域count，在執(zhí)行拓?fù)渑判虻倪^程中，當(dāng)某個(gè)頂點(diǎn)的入度為0（沒有前驅(qū)結(jié)點(diǎn)時(shí)），就將此頂點(diǎn)輸出，同時(shí)將該頂點(diǎn)的所有后繼結(jié)點(diǎn)的入度減1，為了避免重復(fù)檢測(cè)入度為0的頂點(diǎn)，設(shè)立一個(gè)棧St，以存放入度為0的頂點(diǎn)。<p&

26、gt;　　程序模塊及其接口描述　　typedef struct　　{　　int *base; //棧底 　　int *top; //棧頂

27、;　　int stacksize; //?？臻g 　　}Stack;　　int InitStack(Stack &s) //創(chuàng)建一個(gè)空棧　　int Push(Stack &s,int e)

28、 //進(jìn)棧　　bool Empty(Stack s) //查看棧是否為空　　int Pop(Stack &s) //出棧　　int LocateVex(Graph G,int v) //返回節(jié)點(diǎn)v在圖中的位置</p&

29、gt;　　void CreateGraph(Graph &G) //建圖 　　void TopologicalSort(Graph G) //拓?fù)渑判蚝瘮?shù)　　程序的輸入與輸出描述　　輸入界面：

30、;　　再輸入結(jié)點(diǎn)數(shù)和邊數(shù)，此時(shí)會(huì)輸出頂點(diǎn)信息：　　排序結(jié)果輸出界面：　　調(diào)試分析或程序測(cè)試　　對(duì)軟件的使用說明　　在CFree4.0下打開軟件，進(jìn)行操作。&l

31、t;/p>　　項(xiàng)目五：各種排序：插入排序和改進(jìn)冒泡排序算法　　對(duì)設(shè)計(jì)任務(wù)內(nèi)容的概述　　用程序?qū)崿F(xiàn)插入法排序、起泡法改進(jìn)算法排序；利用插入排序和冒泡法的改進(jìn)算法,將用戶隨機(jī)輸入的一列數(shù)按遞增的順序排好。輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列。<

32、b>　　需求分析或功能描述　　插入排序的基本思想是：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子表中的適當(dāng)位置，直到每次記錄插入完成為止。本程序使用直接插入排序。　　交換排序的基本思想是：兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的記錄為止。本程序使用改進(jìn)的冒泡排序算法。<

33、;/p>　　概要設(shè)計(jì)或程序流程圖　　直接插入排序：假設(shè)待排序的記錄存放在數(shù)組R[0..n-1]中，排序過程的某一中間時(shí)刻，R被劃分成兩個(gè)子區(qū)間[0..i-1]和[i..n-1]（剛開始時(shí)i=1,有序區(qū)序號(hào)只有R[0]一個(gè)記錄），其中：前一個(gè)子區(qū)間是已排好序的有序區(qū)，后一個(gè)子區(qū)間則是當(dāng)前未排序的部分，不妨稱其為無序區(qū)。直接插入排序的基本操作是將當(dāng)前無序區(qū)的第一個(gè)記錄R[

34、i]插入到有序區(qū)[0..i-1]中適當(dāng)?shù)奈恢蒙?，使[0..i]變?yōu)樾碌挠行騾^(qū)。　　有序區(qū) 無序區(qū)　　一趟排序　　有序區(qū) 無序區(qū)　　直接插入排序的一趟排序過程</

35、p>　　冒泡排序：整個(gè)算法是從最下面的記錄開始，對(duì)每?jī)蓚€(gè)相臨的關(guān)鍵字進(jìn)行比較，且使關(guān)鍵字較小的記錄換至關(guān)鍵字較大的記錄之上，使得經(jīng)過一趟冒泡排序之后，關(guān)鍵字最小的記錄到達(dá)最上端，接著，再在剩下的記錄中找關(guān)鍵字次小的記錄，并把它換在第二個(gè)位置上。依次類推，一直到所有記錄都有序?yàn)橹埂６谟行┣闆r下，在第i（i<n-1）趟時(shí)已排好序了，但仍執(zhí)行后面幾趟的比較。實(shí)際上，一旦酸法中某一趟比較時(shí)不出現(xiàn)任何記錄交換，

36、說明已經(jīng)排好序了，就可以結(jié)束本算法。為此，改進(jìn)了冒泡排序算法。 　　有有　　序序　　區(qū) 一趟排序

37、區(qū)　　無　　序無　　區(qū) 序　　區(qū)</

38、b>　　程序模塊及其接口描述　　typedef int KeyType; //定義關(guān)鍵字類型為int　　typedef char InfoType[10];　　typedef struct //記錄類型

39、　　{　　KeyType key; //關(guān)鍵字類型　　InfoType data; //其他數(shù)據(jù)項(xiàng)，類型為InfoType　　}RecType ;//排序的記錄類型定義

40、;　　void InsertSort(RecType R[],int n)//直接插入排序　　void BubbleSort(RecType R[],int n)//改進(jìn)冒泡排序　　程序的輸入與輸出描述：　　直接插入排序：<

41、p>　　輸入：　　輸出：　　冒泡排序：　　輸入：　　輸出：

42、;　　調(diào)試分析或程序測(cè)試　　直接插入排序：　　冒泡排序：　　尚未解決的問題或改進(jìn)方向　　在算法的定義中，一開始就定義數(shù)組長(zhǎng)度為10，如果

43、用戶操作中輸入了大于10個(gè)數(shù)時(shí)將只對(duì)前10個(gè)數(shù)進(jìn)行操作，而后面的數(shù)不會(huì)參加運(yùn)算。　　對(duì)軟件的使用說明　　在CFree4.0下打開軟件，進(jìn)行操作。　　結(jié)論及體會(huì)　　在這次的數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)中，從十三

44、個(gè)題目中選了五個(gè)自己比較感興趣的題目進(jìn)行編程，因?yàn)樵S多算法可以在書上找到類似的類型，加上自己的想法，做的可以說比較順利。和平時(shí)上機(jī)所做的不同，這次需要一個(gè)程序的主界面，用來調(diào)用所設(shè)計(jì)的五個(gè)項(xiàng)目，而且分別對(duì)五個(gè)項(xiàng)目的程序設(shè)計(jì)從構(gòu)思，到算法，再到輸入輸出和調(diào)試，進(jìn)行了比較充分的說明，使用起來也比較方便。　　附錄<b

45、>　　附錄1：參考文獻(xiàn)　　[1]李春葆.數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)指導(dǎo).清華大學(xué)出版社,2010　　[2]張曉莉等.數(shù)據(jù)結(jié)構(gòu)與算法.機(jī)械工業(yè)出版社,2002　　[3]李春葆.數(shù)據(jù)結(jié)構(gòu)教程上機(jī)實(shí)驗(yàn)指導(dǎo).清華大學(xué)出版社,2010.　　附錄2：部分源代碼清單<

46、/p>　　********************************************************文章編輯；　　#define MAX 3000 　　typedef struct

47、 　　{ 　　char data[MAX]; 　　int length; 　　}SqString; 　　void StrAss

48、ign(SqString &str,char cstr[])//建立串 　　{　　int i;　　for(i=0;cstr[i]!='\0';i++)　　str.data[

49、i]=cstr[i];　　str.length=i;　　}　　void DispStr(SqString p)　　{　　int i;&l

50、t;/b>　　if(p.length>0)　　{ printf("當(dāng)前的文章為:");　　for(i=0;i<p.length;i++)　　{　　pri

51、ntf("%c",p.data[i]);　　if((i+1)%80==0)　　printf("\n");　　}　　}

52、;　　}　　int cout(SqString p)//各種字符數(shù)量統(tǒng)計(jì) 　　{　　int i=0;int a=0 ,b=0,c=0,d=0;

53、;　　for(i=0;i<p.length;i++)　　{　　if(p.data[i]>='a'&&p.data[i]<='z')　　a++;<

54、/p>　　if(p.data[i]>='A'&&p.data[i]<='Z')　　b++;　　if(p.data[i]>='0'&&p.data[i]<='9')<

55、/p>　　c++;　　if(p.data[i]==32)　　d++;　　}　　printf("英文小寫字母有：%d個(gè)\n

56、",a) ;　　printf("英文大寫字母有：%d個(gè)\n",b) ;　　printf("數(shù)字有：%d個(gè)\n",c);　　printf("空格有：%d個(gè)\n",d);　　return p.length;

57、　　}　　int FindFind(SqString p,SqString q)//查找 　　{　　int i=0;int j=0;int n=0;　　w

58、hile(i<=p.length)　　{　　if((p.data[i]==q.data[j])&&(q.data[j]!='\0'))　　{i++;j++;}　　else<

59、/b>　　i++;　　if(j>=q.length)　　{n++;j=0;}　　}　　printf("經(jīng)查找個(gè)字符共有 %d 個(gè)\n

60、",n);　　}　　SqString Dele(SqString p,SqString a)//刪除 　　{　　int i=0;int j=0;int n=0;int pos=0; &l

61、t;/p>　　while(i<=p.length)　　{　　if((p.data[i]==a.data[j])&&(a.data[j]!='\0'))　　{i++;j++;}<p&

62、gt;　　else 　　i++;　　if(j>=a.length)　　{ pos=i-j+1;　　int k;<p&g

63、t;　　SqString b;b.length=0;　　if(pos<=0||pos>=p.length||pos+a.length>p.length+1)　　return b;　　for(k=0;k<pos-1;k++)<

64、;p>　　b.data[k]=p.data[k];　　for(k=pos+j-1;k<p.length;k++)　　b.data[k-j]=p.data[k];　　b.length=p.length-a.length;　　return b;&

65、lt;/b>　　pos=0;　　j=0;　　}　　}

66、　　}　　********************************************************猴子選大王；　　#define MaxSize 50　　int houzi(int n,int m)　　{<

67、;/b>　　int p[MaxSize];　　int i,j,t;　　for(i=0;i<n;i++)　　p[i]=i+1;　　t=0;<

68、;/p>　　printf("\n出列順序:");　　for(i=n;i>=1;i--)　　{　　t=(t+m-1)%i;　　printf("%d",p[t]);

69、　　for(j=t+1;j<=i-1;j++)　　p[j-1]=p[j];　　} printf("\n");　　printf("\n故編號(hào) %d 的猴子是大王!\n",p[t]);

70、　printf("\n");　　}　　*******************************************************創(chuàng)建二叉樹：　　#define MaxSize 100　　type

71、def char ElemType;　　typedef struct node　　{　　ElemType data;//數(shù)據(jù)元素 　　struct node *lchild;//指向左孩子

72、　struct node *rchild;//指向右孩子 　　}BTNode;　　void CreateBTNode(BTNode *&b,char *str)//由str串創(chuàng)建二叉鏈 　　{<p&

73、gt;　　BTNode *St[MaxSize],*p=NULL;　　int top=-1,k,j=0;　　char ch;　　b=NULL;//建立的二叉樹初始時(shí)為空 　　ch=str[j];

74、;　　while(ch!='\0')//str未掃描完時(shí)循環(huán) 　　{　　switch(ch)　　{　　case '(':top++;St[top]=p;k=1;br

75、eak;//為左結(jié)點(diǎn) 　　case ')':top--;break;　　case ',':k=2;break;//為右結(jié)點(diǎn) 　　default:p=(BTNode *)malloc(sizeof(BTNode));　　p->data=

76、ch;　　p->lchild=p->rchild=NULL;　　if(b==NULL)//p指向二叉樹的根結(jié)點(diǎn) 　　b=p;　　else//已建立二叉樹根結(jié)點(diǎn)

77、　{　　switch(k)　　{　　case 1:St[top]->lchild=p;break;　　case 2:St[top]->rchild=p;break;

78、　　}　　}　　}　　j++;　　ch=str[j];

79、　　}　　}　　void DispBTNode(BTNode *b)//以括號(hào)表示法輸出二叉樹 　　{　　if(b!=NULL)</p

80、>　　{　　printf("%c",b->data);　　if(b->lchild!=NULL||b->rchild!=NULL)　　{<p&

81、gt;　　printf("(");　　DispBTNode(b->lchild);　　if(b->rchild!=NULL) printf(",");　　DispBTNode(b->rchild);　　printf

82、(")");　　}　　}　　}　　void TravLevel(BTNode *b)//層次遍歷

83、　　{　　BTNode *Qu[MaxSize];　　int front,rear;　　front=rear=0;　　if(b!=NULL)　　printf("%c",b-

84、>data); 　　rear++;　　Qu[rear]=b;　　while(rear!=front)　　{　　front=(front+1)%Max

85、Size;　　b=Qu[front];　　if(b->lchild!=NULL)　　{　　printf("%c",b->lchild->data);　　r

86、ear=(rear+1)%MaxSize;　　Qu[rear]=b->lchild;　　}　　if(b->rchild!=NULL)　　{

87、printf("%c",b->rchild->data);　　rear=(rear+1)%MaxSize;　　Qu[rear]=b->rchild;　　}　　}

88、;　　printf("\n");　　}　　void PreOrder(BTNode *b)//先序遍歷的遞歸算法 　　{　　if(b!

89、=NULL)　　{　　printf("%c",b->data);//訪問根結(jié)點(diǎn) 　　PreOrder(b->lchild);//先序遍歷左子樹 　　PreOrder(b->rchild);//先序

90、遍歷右子樹 　　}　　}　　void menu8()　　{　　BTNode *b;<p

91、>　　char s[MaxSize];　　printf("請(qǐng)輸入二叉樹：");　　gets(s);　　CreateBTNode(b,s);　　printf("輸出此二叉樹:");</

92、p>　　DispBTNode(b);　　printf("\n");　　printf("層序遍歷序列：");　　TravLevel(b);　　printf("先序遍歷遞歸序列：");&l

93、t;/p>　　PreOrder(b);　　printf("\n");　　}　　#include <stdio.h>　　#define MAXE 20&

94、lt;p>　　typedef int KeyType;　　typedef char InfoType[10];　　typedef struct　　{　　KeyType key;　　Inf

95、oType data;　　}RecType;　　****************************************************************拓?fù)渑判颍?lt;/p>　　#define STACKSIZE 100 //?？臻g大小 &

96、lt;/p>　　#define STACKINCREMENT 20 //進(jìn)棧棧增量 　　#define MAX 20 //鄰接表數(shù)組的最大值 　　typedef struct　　{</p&

97、gt;　　int *base; //棧底 　　int *top; //棧頂 　　int stacksize; //?？臻g 　　}Stack;<

98、;/p>　　int InitStack(Stack &s) //創(chuàng)建一個(gè)空棧　　{　　s.base=(int*)malloc(STACKSIZE*sizeof(int));　　if(!s.base)

99、　　return -1;　　s.top=s.base;　　s.stacksize=STACKSIZE;　　return 1;　　}

100、int Push(Stack &s,int e) //進(jìn)棧 　　{　　if((s.top-s.base)>s.stacksize)　　{　　s.base=(int*

101、)realloc(s.base,(STACKSIZE+STACKINCREMENT)*sizeof(int));　　if(!s.base)　　return-1;　　s.top=s.base+s.stacksize;　　s.stacks

102、ize+=STACKINCREMENT;　　}　　*s.top++=e;　　return 1;　　}　　bool E

103、mpty(Stack s) //查看棧是否為空 　　{　　if(s.base==s.top)　　return true;　　else<p&

104、gt;　　return false;　　}　　int Pop(Stack &s) //出棧 　　{　　int e;&l

105、t;/p>　　e=*--s.top;　　return e;　　}　　typedef struct ArcNode //頭節(jié)點(diǎn)　　{

106、　　int adjvex; //該邊所指向的頂點(diǎn)的位置　　struct ArcNode *nextarc; //指向下一條邊　　}ArcNode;　　typedef str

107、uct VNode //表節(jié)點(diǎn)　　{　　int data; //頂點(diǎn)信息　　int indegree; //節(jié)點(diǎn)的入度　　ArcNode *f

108、irstarc; //指向第一條依附該節(jié)點(diǎn)的邊的指針　　}VNode,AdjList[MAX];　　typedef struct 　　{　　AdjList vertices; //表節(jié)點(diǎn)<

109、;/p>　　int vexnum; //節(jié)點(diǎn)的個(gè)數(shù)　　int arcnum; //邊的條數(shù)　　}Graph;　　int LocateVex(Graph G,int v) /

110、/返回節(jié)點(diǎn)v在圖中的位置　　{　　int i;　　for(i=0;i<G.vexnum;++i)　　{　　if

111、(G.vertices[i].data==v)　　break;　　else　　continue;　　}

112、;　　if(i<G.vexnum)　　return i;　　else 　　return -1;　　}<

113、;p>　　void CreateGraph(Graph &G) //建圖 　　{　　int m,n;　　printf("①現(xiàn)在請(qǐng)輸入DAG的結(jié)點(diǎn)數(shù): ");<p

114、>　　scanf("%d",&m);　　while(m<0)　　{　　printf("\t\t\t\tError!\n\t\t\t\tDAG結(jié)點(diǎn)數(shù)不能小于1.\n");　　p

115、rintf("請(qǐng)重新輸入DAG的頂點(diǎn)數(shù): "); //DAG是有向無環(huán)圖 　　scanf("%d",&m);　　}　　printf("②現(xiàn)在請(qǐng)輸入DAG的邊數(shù): ");<p&

116、gt;　　scanf("%d",&n);　　while(n<0)　　{　　printf("\t\t\t\tError!\n\t\t\t\tDAG的邊數(shù)不能小于0.\n");　　pr

117、intf("請(qǐng)重新輸入DAG的邊數(shù): ");　　scanf("%d",&n);　　}　　G.vexnum=m; //頂點(diǎn)數(shù)目　　G.arcnum=

118、n; //邊的數(shù)目　　int i,j,k;　　for(i=0;i<G.vexnum;++i) //初始化圖的信息　　{　　G.vertices[i].data=i+1;

119、 //頂點(diǎn)信息　　G.vertices[i].firstarc=0;　　G.vertices[i].indegree=0; //開始時(shí)入度都為0　　}　　//頂點(diǎn)信息</p&

120、gt;　　printf("③現(xiàn)在輸出頂點(diǎn)信息:\n");　　for(i=0;i<G.vexnum;++i)　　printf("v%d\n",G.vertices[i].data);　　int v1,v2,flag=0;&l

121、t;p>　　for(k=0;k<G.arcnum;++k)　　{　　printf("④請(qǐng)輸入第%d邊的起點(diǎn)和終點(diǎn)(樣例:1 2),注意其中分隔符為一個(gè)空格: ",k+1);　　scanf("%d%d",&v1,&am

122、p;v2);　　i=LocateVex(G,v1); //頂點(diǎn)v1在圖中的位置　　j=LocateVex(G,v2); //頂點(diǎn)v2在圖中的位置　　if(i >=0 && j>=0)<

123、;b>　　{　　++flag;　　(G.vertices[j].indegree)++;　　ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode));　　p->adjve

124、x=j;　　p->nextarc=0;　　ArcNode *p1;　　if(! G.vertices[i].firstarc)　　G.vertices[i].firstarc=p;　　else</b&

125、gt;　　{　　for(p1=G.vertices[i].firstarc;p1->nextarc;p1=p1->nextarc); //求該頂點(diǎn)的最后一個(gè)鄰接頂點(diǎn)　　p1->nextarc=p; //將p插入到最后一個(gè)鄰接頂點(diǎn)

126、的后面　　}　　}　　else //沒有該弧，刪除掉　　{　　printf("********

127、***************************************"); 　　printf("沒有該邊!\n");　　k=flag;　　printf("************************************

128、***********"); 　　} 　　}　　}　　void TopologicalSort(Graph G) //拓?fù)渑判蚝瘮?shù)</p&g

129、t;　　{　　int i,j,k;　　int count=0; //用來統(tǒng)計(jì)頂點(diǎn)的個(gè)數(shù)　　Stack s; //定義一個(gè)棧，用來保存入度為0的頂點(diǎn)　　InitStack(s); //初始化棧</p&g

130、t;　　for(i=0;i<G.vexnum;++i)　　if(G.vertices[i].indegree==0) //若第i個(gè)頂點(diǎn)的入度為0 ，i表示頂點(diǎn)在圖中的位置　　Push(s,i); //將第i個(gè)頂點(diǎn)入棧　　while(!Empty(

131、s))　　{　　j=Pop(s); // 將為入度0的頂點(diǎn)位置出棧，并保存到j(luò)中　　count++; //統(tǒng)計(jì)頂點(diǎn)的個(gè)數(shù)　　printf("v%d ",G.vertices[j].data

132、); //輸出入度為0的頂點(diǎn)　　ArcNode *p;　　for(p=G.vertices[j].firstarc; p ;p=p->nextarc) //找與第j個(gè)頂點(diǎn)的鄰接頂點(diǎn)，并將其入度減1　　{　　k=p->a

133、djvex;　　--(G.vertices[k].indegree);　　if(G.vertices[k].indegree==0) //如果入度為0,就入棧　　Push(s,k);　　}

134、;　　}　　if(count<G.vexnum) //count小于頂點(diǎn)的個(gè)數(shù)時(shí)候，說明有環(huán)，不符合拓?fù)渑判虻囊?lt;/p>　　{　　printf("***************************************

135、*****************************************"); 　　printf("\t\t\t\tError!\n\t\t\t\t圖中有環(huán)!該圖不是DAG!\n");　　exit(0); //退出　　}<

136、/b>　　}　　//主函數(shù)的實(shí)現(xiàn)　　/*void TuoPu()　　{　　printf("\t\t\

137、t\t拓?fù)渑判蜓菔綷n");　　printf("\t\t\t\t現(xiàn)在開始\n");　　Graph g;　　CreateGraph(g);　　printf("\n\t\t\t\t拓?fù)渑判蚪Y(jié)果為:

138、\n");　　printf("************************************************"); 　　TopologicalSort(g);　　printf("\n*************************************

139、***********"); 　　printf("\n\t\t\t\t演示完畢\n");　　}*/　　*****************************************************各種排序<

140、;p>　　void InsertSort(RecType R[],int n)//直接插入排序 　　{　　int i,j,k;　　RecType temp;　　for(i=1;i<n;i++)<

141、;p>　　{　　temp=R[i];　　j=i-1; //從左向右在有序區(qū)R[0..i-1]中找R[i]的插入位置　　while(j>=0&&temp.key<R[j].key)<

眾賞文庫(kù)> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

課程設(shè)計(jì)報(bào)告---文章編輯、猴子選大王、建立二叉樹、拓?fù)渑判?、各種排序

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

課程設(shè)計(jì)報(bào)告---文章編輯、猴子選大王、建立二叉樹、拓?fù)渑判?、各種排序

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載

課程設(shè)計(jì)報(bào)告---文章編輯、猴子選大王、建立二叉樹、拓?fù)渑判?、各種排序