課程設(shè)計報告---文章編輯、猴子選大王、建立二叉樹、拓撲排序、各種排序

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

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

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

文檔簡介

1、　　課程設(shè)計　　2009 ~ 2010學(xué)年第二學(xué)期　　設(shè)計題目文章編輯、猴子選大王、建立二叉樹、拓撲排序、各種排序 　　目錄<

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

3、/p>　　2.5項目四：拓撲排序8　　2.6項目五：各種排序：插入排序和改進冒泡排序算法10　　5、結(jié)論及體會14　　6、附錄14　　目的與要求<

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

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

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

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

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

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

10、第N個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。　　需求分析或功能描述　　輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，n<m　　輸出形式：中文提示按照m個猴子，數(shù)n 個數(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故編號 %d

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

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

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

18、串。輸出二叉樹，以括號表示法輸出一棵二叉樹。先序遍歷二叉樹的過程是，訪問根結(jié)點，先序遍歷左子樹，先序遍歷右子樹。層次遍歷的過程是，先將根結(jié)點進隊，在隊不為空時循環(huán)，從隊列中出列一個結(jié)點*p，訪問它，若它有左孩子結(jié)點，如此操作直到隊空為止。 　　（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)//以括號表示法輸出二叉樹　　void TravLevel

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

22、;p>　?。?）調(diào)試分析或程序測試　?。?）尚未解決的問題或改進方向　　因為本程序最終要與其他兩個程序合并在一起，在主界面進行選擇。所以在進入主界面時要在本程序的主函數(shù)處修改字符，否則在調(diào)用本程序時主函數(shù)會發(fā)生沖突。　?。?）對軟件的使用說明　　在CFree4.0下

23、打開軟件，進行操作。　　項目四：拓撲排序　　對設(shè)計任務(wù)內(nèi)容的概述　　編寫函數(shù)，實現(xiàn)圖的拓撲排序。　　需求分析或功能描述　　在一個有向圖中找一個拓撲序列的過

24、程稱為拓撲排序，而每一個有向圖的拓撲序列并不唯一，本程序的功能就是將用戶輸入的序列進行拓撲排序。　　概要設(shè)計或程序流程圖　　在程序菜單中選擇開始，輸入有向圖的結(jié)點數(shù)和邊數(shù)，此時程序就會輸出結(jié)點信息，如v1，v2，v3等，接下來會要求用戶輸入第一條邊的起點和終點，通過程序運行就可以輸出拓撲排序結(jié)果。　　詳細設(shè)計或源

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

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

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

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

29、gt;　　void CreateGraph(Graph &G) //建圖 　　void TopologicalSort(Graph G) //拓撲排序函數(shù)　　程序的輸入與輸出描述　　輸入界面：

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

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

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

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

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

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

36、說明已經(jīng)排好序了，就可以結(jié)束本算法。為此，改進了冒泡排序算法。 　　有有　　序序　　區(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ù)項，類型為InfoType　　}RecType ;//排序的記錄類型定義

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

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

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

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

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

45、>　　附錄1：參考文獻　　[1]李春葆.數(shù)據(jù)結(jié)構(gòu)學(xué)習指導(dǎo).清華大學(xué)出版社,2010　　[2]張曉莉等.數(shù)據(jù)結(jié)構(gòu)與算法.機械工業(yè)出版社,2002　　[3]李春葆.數(shù)據(jù)結(jié)構(gòu)教程上機實驗指導(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("當前的文章為:");　　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)計 　　{　　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個\n

56、",a) ;　　printf("英文大寫字母有：%d個\n",b) ;　　printf("數(shù)字有：%d個\n",c);　　printf("空格有：%d個\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)查找個字符共有 %d 個\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故編號 %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;//建立的二叉樹初始時為空 　　ch=str[j];

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

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

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

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)//以括號表示法輸出二叉樹 　　{　　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é)點 　　PreOrder(b->lchild);//先序遍歷左子樹 　　PreOrder(b->rchild);//先序

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

91、>　　char s[MaxSize];　　printf("請輸入二叉樹：");　　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;　　****************************************************************拓撲排序：　　#define STACKSIZE 100 //?？臻g大小 &

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

97、gt;　　int *base; //棧底 　　int *top; //棧頂 　　int stacksize; //棧空間 　　}Stack;<

98、;/p>　　int InitStack(Stack &s) //創(chuàng)建一個空棧　　{　　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) //進棧 　　{　　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é)點　　{

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

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

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

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

110、/返回節(jié)點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)在請輸入DAG的結(jié)點數(shù): ");<p

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

115、rintf("請重新輸入DAG的頂點數(shù): "); //DAG是有向無環(huán)圖 　　scanf("%d",&m);　　}　　printf("②現(xiàn)在請輸入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("請重新輸入DAG的邊數(shù): ");　　scanf("%d",&n);　　}　　G.vexnum=m; //頂點數(shù)目　　G.arcnum=

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

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

120、gt;　　printf("③現(xià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("④請輸入第%d邊的起點和終點(樣例:1 2),注意其中分隔符為一個空格: ",k+1);　　scanf("%d%d",&v1,&am

122、p;v2);　　i=LocateVex(G,v1); //頂點v1在圖中的位置　　j=LocateVex(G,v2); //頂點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); //求該頂點的最后一個鄰接頂點　　p1->nextarc=p; //將p插入到最后一個鄰接頂點

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

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

128、***********"); 　　} 　　}　　}　　void TopologicalSort(Graph G) //拓撲排序函數(shù)</p&g

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

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

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

132、); //輸出入度為0的頂點　　ArcNode *p;　　for(p=G.vertices[j].firstarc; p ;p=p->nextarc) //找與第j個頂點的鄰接頂點，并將其入度減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小于頂點的個數(shù)時候，說明有環(huán)，不符合拓撲排序的要求　　{　　printf("***************************************

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

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

137、t\t拓撲排序演示\n");　　printf("\t\t\t\t現(xiàn)在開始\n");　　Graph g;　　CreateGraph(g);　　printf("\n\t\t\t\t拓撲排序結(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)<

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

溫馨提示

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

課程設(shè)計報告---文章編輯、猴子選大王、建立二叉樹、拓撲排序、各種排序

文檔簡介

溫馨提示

最新文檔

評論

課程設(shè)計報告---文章編輯、猴子選大王、建立二叉樹、拓撲排序、各種排序

文檔簡介

溫馨提示

最新文檔

評論

免費下載

課程設(shè)計報告---文章編輯、猴子選大王、建立二叉樹、拓撲排序、各種排序