1、1 上海應用技術學院課程設計任務書上海應用技術學院課程設計任務書 課程名稱數據結構課程設計課程代碼B704208 設計題目 7、 猴子選大王 8、 建立二叉樹，層序、先序遍歷 10、 紙牌游戲 12、拓撲排序 設計時間2012 年 6 月 25 日 2012 年 6 月 29 日 系（院） 計算機科學與信息 工程系 專業計算機科學與技術班級 一、課程設計任務（條件） 、具體技術參數（指標） 7、 猴子選大王* 任務：一堆猴子都有編號，編號是 1，2，3 .m ,這群猴子（m 個）按照 1-m 的 順序圍坐一圈，從第 1 開始數，每數到第 N 個，該猴子就要離開此圈，這樣依次 下來，直到圈中只剩

2、下最后一只猴子，則該猴子為大王。 要求： 輸入數據：輸入 m,n m,n 為整數，nm 輸出形式：中文提示按照 m 個猴子，數 n 個數的方法，輸出為大王的猴子是幾號 ，建立一個函數來實現此功能 8、 建立二叉樹，層序、先序遍歷（ 用遞歸或非遞歸的方法都可以）* 任務： 要求能夠輸入樹的各個結點，并能夠輸出用不同方法遍歷的遍歷序列；分別建立 建立二叉樹存儲結構的的輸入函數、輸出層序遍歷序列的函數、輸出先序遍歷序 列的函數； 10、 紙牌游戲* 任務：編號為 1-52 張牌，正面向上，從第 2 張開始，以 2 為基數，是 2 的倍數的 牌翻一次，直到最后一張牌；然后，從第 3 張開始，以 3 為

3、基數，是 3 的倍數的 牌翻一次，直到最后一張牌；然后從第 4 張開始，以 4 為基數，是 4 的倍數的 牌翻一次， 直到最后一張牌；.再依次 5 的倍數的牌翻一次，6 的，7 的 直到 以 52 為基數的 翻過，輸出：這時正面向上的牌有哪些？ 12、拓撲排序 任務：編寫函數實現圖的拓撲排序。 二、對課程設計成果的要求（包括課程設計說明書、圖紙、圖表、實物等軟硬件 要求） 1.提交課程設計報告（格式及文件名參見模板）一份。 2.提交源程序文件及配套文件一套（每個項目占一個文件夾，如“項目一” ） 。 三、課程設計工作進度計劃： 6 月 22 日：指導老師下發課程設計指導書和任務書，并進行必要的

4、指導，學生完 成選題。 6 月 23 日：完成詳細設計說明，進入編程階段。 6 月 24 日：完成編程和測試工作。 6 月 25 日：完成課程設計報告撰寫工作。 6 月 26 日：提交課程設計報告和源程序，答辯，成績評定。 2 四、主要參考資料 1李春葆.數據結構學習指導.清華大學出版社,2006 2張曉莉等.數據結構與算法.機械工業出版社,2002 3李春葆.數據結構教程上機實驗指導.清華大學出版社,2005. 指導教師（簽名）： 年 月 日 教研室主任（簽名）：薛黎 年 月 日 3 目錄目錄 1 1概述概述.3 1.1.1.1.設計要求設計要求.3 1.2.1.2.具體內容具體內容.4 2

5、 2程序分析程序分析.5 2.12.1猴子選大王猴子選大王.5 2.1.1任務概述.5 2.1.2詳細說明.8 2.1.3調試.8 2.22.2建立二叉樹，層序、先序遍歷建立二叉樹，層序、先序遍歷.8 2.2.1任務概述.8 2.2.2詳細說明.13 2.2.3調試.14 2.32.3紙牌游戲紙牌游戲.14 2.3.1任務概述.14 2.3.2詳細說明.17 2.3.3調試.17 2.42.4拓撲排序拓撲排序.17 2.4.1任務概述.17 2.4.2詳細說明.22 2.4.3調試.23 3 3總結總結.23 4 4參考文獻參考文獻.24 5 5源代碼源代碼 .24 4 1 1概述概述 1.1

6、. 設計要求 學生必須仔細閱讀數據結構課程設計方案，認真主動完成課設的要求。有問 題及時主動通過各種方式與教師聯系溝通。 學生要發揮自主學習的能力，充分利用時間，安排好課設的時間計劃，并在課設 過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。 課程設計按照教學要求時間完成，每天（按每周 5 天）至少要上 3-4 小時的機來 調試 C 語言設計的程序，總共至少要上機調試程序 30 小時 1.2. 具體內容 本次課程設計完成如下模塊（共 13 個模塊，學生可以在其中至少挑選 4 個功能塊 完成，但有*號的模塊是必須要選擇 2 個,多做可以加分）以下是我選的 4 個功能。 7、 猴子選大王* 任

7、務：一堆猴子都有編號，編號是 1，2，3 .m ,這群猴子（m 個）按照 1-m 的 順序圍坐一圈，從第 1 開始數，每數到第 N 個，該猴子就要離開此圈，這樣依次下來， 直到圈中只剩下最后一只猴子，則該猴子為大王。 要求： 輸入數據：輸入 m,n m,n 為整數，nm 輸出形式：中文提示按照 m 個猴子，數 n 個數的方法，輸出為大王的猴子是幾號 ，建立一個函數來實現此功能 8、 建立二叉樹，層序、先序遍歷（ 用遞歸或非遞歸的方法都可以）* 任務： 要求能夠輸入樹的各個結點，并能夠輸出用不同方法遍歷的遍歷序列；分別建立 建立二叉樹存儲結構的的輸入函數、輸出層序遍歷序列的函數、輸出先序遍歷序列

8、的 函數； 10、 紙牌游戲* 任務：編號為 1-52 張牌，正面向上，從第 2 張開始，以 2 為基數，是 2 的倍數的 牌翻一次，直到最后一張牌；然后，從第 3 張開始，以 3 為基數，是 3 的倍數的牌翻 5 一次，直到最后一張牌；然后從第 4 張開始，以 4 為基數，是 4 的倍數的牌翻一次， 直到最后一張牌；.再依次 5 的倍數的牌翻一次，6 的，7 的 直到 以 52 為基數的 翻過，輸出：這時正面向上的牌有哪些？ 12、拓撲排序 任務：編寫函數實現圖的拓撲排序。 2 2程序分析程序分析 2.1猴子選大王 2.1.1任務概述 一堆猴子都有編號，編號是 1，2，3 .m ,這群猴子（

9、m 個）按照 1-m 的順序圍 坐一圈，從第 1 開始數，每數到第 N 個，該猴子就要離開此圈，這樣依次下來，直到 圈中只剩下最后一只猴子，則該猴子為大王。 要求： 輸入數據：輸入 m,n m,n 為整數，nm 輸出形式：中文提示按照 m 個猴子，數 n 個數的方法，輸出為大王的猴子是幾號 ，建立一個函數來實現此功能 源代碼源代碼 #include #include typedef struct LNode/定義鏈表結點類型 int data; struct LNode *next; LinkList; void CreateListR(LinkList * int i; 6 L=(LinkL

10、ist *)malloc(sizeof(LinkList); L-data=1; r=L; for(i=2;idata=i; r-next=s; r=s; r-next=L; void ListDelete(LinkList * LinkList *p=L,*q; while(p-next!=p) while(j!=i-1) j+; p=p-next; q=p-next; p-next=p-next-next; printf(%d 號猴子離開了猴圈n,q-data); free(q); j=0; printf(猴子大王是：); printf(%dn,p-data); free(p); 7 vo

11、id main() LinkList *L; int n,m; int i=1; while(i=1) printf(請輸入猴子的總數:); scanf(%d, printf(請輸入要求數幾個數:); scanf(%d, if(m=n) printf(輸入錯誤.n); i=1; else i=0; CreateListR(L,m); ListDelete(L,n); 流程圖流程圖 8 開始 輸入 m,n MN 創建循環鏈表，輸出 離開猴子的編號。 輸出誰是猴子大王 結束 否 是 2.1.2詳細說明 由題意可得 m 只 猴子首尾相接的坐，可以用鏈表的存儲方式把編號存儲起來。由 于數到 n，第 n

12、 個猴子被提出，直到最后一只猴子，它 就是王。我們用尾插法建立循 環鏈表 void CreateListR(LinkList * typedef struct node 10 ElemType data; struct node *lchild; struct node *rchild; BTNode; typedef int KeyType; /定義關鍵字類型 typedef char InfoType10; typedef struct /記錄類型 KeyType key; /關鍵字項 InfoType data; /其他數據項,類型為 InfoType RecType; void Cre

13、ateBTNode(BTNode * int top=-1,k,j=0; char ch; b=NULL; ch=strj; while (ch!=0) switch(ch) case (:top+;Sttop=p;k=1; break; case ):top-;break; case ,:k=2; break; default:p=(BTNode *)malloc(sizeof(BTNode); p-data=ch;p-lchild=p-rchild=NULL; if (b=NULL) b=p; 11 else switch(k) case 1:Sttop-lchild=p;break; c

14、ase 2:Sttop-rchild=p;break; j+; ch=strj; void DispBTNode(BTNode *b) /以括號表示法輸出二叉樹 if (b!=NULL) printf(%c,b-data); if (b-lchild!=NULL | b-rchild!=NULL) printf(); DispBTNode(b-lchild); if (b-rchild!=NULL) printf(,); DispBTNode(b-rchild); printf(); void PreOrder(BTNode *b) /先序遍歷的遞歸算法 12 if (b!=NULL) pri

15、ntf(%c ,b-data); PreOrder(b-lchild); PreOrder(b-rchild); void LevelOrder(BTNode *b) /層次遍歷算法 BTNode *p; BTNode *quMaxSize; int front,rear; front=rear=-1; rear+; qurear=b; while (front!=rear) front=(front+1)%MaxSize; p=qufront; printf(%c ,p-data); if (p-lchild!=NULL) rear=(rear+1)%MaxSize; qurear=p-lc

16、hild; if (p-rchild!=NULL) rear=(rear+1)%MaxSize; qurear=p-rchild; void main() 13 BTNode *b=NULL,*q=NULL; char str100; int i,j; int flag=0; printf(輸入二叉樹：); scanf(%s,str); CreateBTNode(b,str); printf (n); printf (n 先序遍歷輸出：); DispBTNode (b); printf (n); printf (n 層次遍歷輸出：); LevelOrder (b); 流程圖流程圖 開始 輸入二

17、叉樹 層序遍歷函數， 輸出層序遍歷 先序遍歷函數。 輸出先序遍歷 結束 14 2.2.2詳細說明 二叉樹的結構簡單，存儲效率高，其運算算法也相對簡單，而且任何 m 樹都可以 轉化為二叉樹，所以，二叉樹具有很重要的地位。在遍歷一棵樹時按照一定的順序訪 問二叉樹中所有的結點。 先序遍歷的過程：訪問根結點；先序遍歷左子樹；先序遍歷右子樹； 層序遍歷過程：先將根結點進隊，在隊不空時循環；從隊列中出列一個結點*p， 訪問它；若他有左孩子結點，將左孩子結點進隊，右孩子結點同樣。如此操作直到隊 空為止。 2.2.3調試 2.3紙牌游戲 2.3.1任務概述 任務：編號為 1-52 張牌，正面向上，從第 2 張

18、開始，以 2 為基數，是 2 的倍數的 牌翻一次，直到最后一張牌；然后，從第 3 張開始，以 3 為基數，是 3 的倍數的牌翻 一次，直到最后一張牌；然后從第 4 張開始，以 4 為基數，是 4 的倍數的牌翻一次， 15 直到最后一張牌；.再依次 5 的倍數的牌翻一次，6 的，7 的 直到 以 52 為基數的 翻過，輸出：這時正面向上的牌有哪些？ 源代碼源代碼 #include #define N 52 void main() int i,j; int cardN = 0; for (i = 2;i = N;i+) for (j = 2;j = N;j+) if (i % j = 0) if

19、(cardi - 1) cardi - 1 = 0; else cardi - 1 = 1; printf(最后正面向上的撲克牌為:n); for (i = 0;i N;i+) if (cardi = 0) printf(第%d 張,i + 1); printf(n); 流程圖流程圖 18 開始 所有牌面向上 cardN = 0 翻面 i % j = 0 不翻面 cardi = 0 輸出“第 i+1 張為正面朝 上” I,j=52 I=i+1 J=j+1 結束 是 否 I=0 I52 I=i+1 是 是 是 否 否 否 19 2.3.2詳細說明 先定義一個數組，52 個元素代表 52 張牌，用

20、元素的值來表示他是向上還是向下。 在這里是指假定正面向上為 0，向下為 1.因此所有的牌的初始值為 1.內外兩層循環， 第一層的是從第一張牌到第 25 張牌，內層循環指的是翻動以幾為基數的牌。顯然，若 原來為一翻動后為 0，若為 0，則翻動后為 1。最后要求輸出向上的牌，輸出值應該為 0。 2.3.3調試 2.4拓撲排序 2.4.1任務概述 任務：編寫函數實現圖的拓撲排序。 源代碼源代碼 #include #include #define MAXV 6 20 typedef struct int no;/頂點編號 int info;/頂點其他信息 VertexType;/頂點類型 typede

21、f struct/圖的定義 int edgesMAXVMAXV;/鄰接矩陣的邊數組 int n,e;/定點數，弧數 VertexType vexsMAXV;/存放頂點信息 MGraph; typedef struct ANode/弧的結點結構 int adjvex;/該弧的終點位置 struct ANode *nextarc;/指向下一條弧的指針 int info;/該弧的有關信息 ArcNode; typedef struct Vnode/鄰接表頭結點的類型 int data;/頂點信息 int count;/存放頂點入度 ArcNode *firstarc;/指向第一條弧 VNode; t

22、ypedef VNode AdjListMAXV; typedef struct AdjList adjlist; int n; int e; 21 ALGraph; void MatToList(MGraph g,ALGraph * ArcNode *p; G=(ALGraph*)malloc(sizeof(ALGraph); for(i=0;iadjlisti.firstarc=NULL; for(i=0;i=0;j-) if(g.edgesij!=0) p=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex=j; p-nextarc=G-adjlist

23、i.firstarc; G-adjlisti.firstarc=p; G-n=n;G-e=g.e; void DispAdj(ALGraph *G)/輸出鄰接表 G int i; ArcNode *p; for (i=0;in;i+) p=G-adjlisti.firstarc; printf(%3d: ,i); while (p!=NULL) printf(%3d,p-adjvex); /輸出該弧的終點位置 22 p=p-nextarc; printf(n); void TopSort(ALGraph *G) int i,j; int StMAXV,top=-1; ArcNode *p; f

24、or(i=0;in;i+)/入度置初值為 0 G-adjlisti.count=0; for(i=0;in;i+)/求所有頂點的入度 p=G-adjlisti.firstarc; while(p!=NULL) G-adjlistp-adjvex.count+; p=p-nextarc; for(i=0;in;i+) if(G-adjlisti.count=0)/入度為 0 的頂點進棧 top+; Sttop=i; while(top-1) /棧不為空時循環 i=Sttop;top-; /出棧 printf(%d,i); /輸出頂點 p=G-adjlisti.firstarc;/找第一個相鄰頂點

25、 while(p!=NULL) j=p-adjvex; G-adjlistj.count-; 23 if(G-adjlistj.count=0)/入度為 0 的相鄰頂點進棧 top+; Sttop=j; p=p-nextarc; void main() int i,j; MGraph g; ALGraph *G; g.n=6;g.e=6; int AMAXVMAXV= 0,1,0,0,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0, 0,1,0,0; for(i=0;ig.n;i+)/建立鄰接矩陣 for(j=0;jg.n;j+)

26、 g.edgesij=Aij; printf(圖 G 的鄰接矩陣轉換成鄰接表:n); MatToList(g,G); DispAdj(G); printf(輸出一個拓撲序列:n); TopSort(G); printf(n); 流程圖流程圖 24 開始 寫出圖的鄰接矩陣 把鄰接矩陣轉化為 鄰接表 輸出鄰接表 用拓撲算法對鄰接表進行排 序 輸出它的拓撲排 序 結束 2.4.2詳細說明 這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。 簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲 排序。 拓撲排序的算法一般用于以給定的有向圖，

27、用戶可以采用鄰接表作為存儲結構， 為每個頂點設立一個鏈表，每個鏈表有一個表頭結點構成一個數組，表頭結點中增加 一個存放頂點入度的域 count。 在執行拓撲排序的過程中，當某個頂點的入度為零時，就將此頂點輸出，同時將 該頂點的所有后繼頂點的入度減 1，為了避免重復檢測入度為零的頂點，設立一個棧 St，以存放入度為零的頂點。 25 2.4.3調試 3 3總結總結 數據結構是計算機程序設計的重要理論基礎，它是計算機科學的核心課程。他兼 顧了諸多高級語言的特點，是一種典型的結構化的程序設計語言。 經過這一周的學習，我不僅鞏固了以前的知識并在此基礎上還對數據結構的特點 和算法有了更深的了解。使我在這門

28、課程的實際應用上有了一定的提高。 通過這一周的學習，使我明白了程序設計的一些基本要求：第一要從問題的要害 入手，要從前到后解決每個方面；第二就是編程通過在編譯環境中各種調試，才能夠 得到完整的程序。 通過實訓我體會到了要從多方面著手，包括先前的找資料，看參考書，編寫過程 中的寫流程圖等，還有就是在面對困難時的解決方法。 總之這一個禮拜的課程設計讓我受益匪淺，我深深的認識到，學好一門學課，要 有刻苦的鉆研精神，要從失敗中找經驗才能獲得成功。 26 4 4參考文獻參考文獻 1李春葆.數據結構學習指導.清華大學出版社,2006 2張曉莉等.數據結構與算法.機械工業出版社,2002 3李春葆.數據結構

29、教程上機實驗指導.清華大學出版社,2005. 5 5源代碼源代碼 #include #include #include #define MAXV 6 #define N 52 #define maxsize 50 #define MaxSize 20 void zhipai() int i,j; int cardN = 0; for (i = 2;i = N;i+) for (j = 2;j = N;j+) if (i % j = 0) if (cardi - 1) cardi - 1 = 0; else cardi - 1 = 1; printf(最后正面向上的撲克牌為:n); for (i

30、 = 0;i data=1; r=L; for(i=2;idata=i; r-next=s; r=s; r-next=L; void ListDelete(LinkList * LinkList *p=L,*q; while(p-next!=p) while(j!=i-1) j+; p=p-next; q=p-next; p-next=p-next-next; printf(%d 號猴子離開了猴圈n,q-data); free(q); j=0; printf(猴子大王是：); printf(%dn,p-data); free(p); void Monkey() LinkList *L; int

31、 n,m; int i=1; while(i=1) printf(請輸入猴子的總數:); scanf(%d, printf(請輸入要求數幾個數:); scanf(%d, if(m=n) printf(輸入錯誤.n); i=1; else 28 i=0; CreateListR(L,m); ListDelete(L,n); typedef struct /拓撲排序 int no;/頂點編號 int info;/頂點其他信息 VertexType;/頂點類型 typedef struct/圖的定義 int edgesMAXVMAXV;/鄰接矩陣的邊數組 int n,e;/定點數，弧數 Vertex

32、Type vexsMAXV;/存放頂點信息 MGraph; typedef struct ANode/弧的結點結構 int adjvex;/該弧的終點位置 struct ANode *nextarc;/指向下一條弧的指針 int info;/該弧的有關信息 ArcNode; typedef struct Vnode/鄰接表頭結點的類型 int data;/頂點信息 int count;/存放頂點入度 ArcNode *firstarc;/指向第一條弧 VNode; typedef VNode AdjListMAXV; typedef struct AdjList adjlist; int n;

33、 int e; ALGraph; void MatToList(MGraph g,ALGraph * ArcNode *p; G=(ALGraph*)malloc(sizeof(ALGraph); for(i=0;iadjlisti.firstarc=NULL; for(i=0;i=0;j-) if(g.edgesij!=0) p= (ArcNode *)malloc(sizeof(ArcNode); p-adjvex=j; p-nextarc=G-adjlisti.firstarc; G-adjlisti.firstarc=p; G-n=n;G-e=g.e; void DispAdj(ALG

34、raph *G)/輸出鄰接表 G int i; ArcNode *p; for (i=0;in;i+) p=G-adjlisti.firstarc; printf(%3d: ,i); while (p!=NULL) printf(%3d,p-adjvex); /輸出該弧的終點位置 p=p-nextarc; printf(n); void TopSort(ALGraph *G) int i,j; int StMAXV,top=-1; ArcNode *p; for(i=0;in;i+)/入度置初值為 0 G-adjlisti.count=0; for(i=0;in;i+)/求所有頂點的入度 p=

35、G-adjlisti.firstarc; while(p!=NULL) G-adjlistp-adjvex.count+; p=p-nextarc; for(i=0;in;i+) if(G-adjlisti.count=0)/入度為 0 的頂點進棧 top+; Sttop=i; while(top-1) /棧不為空時循環 30 i=Sttop;top-; /出棧 printf(%d,i); /輸出頂點 p=G-adjlisti.firstarc;/找第一個相鄰頂點 while(p!=NULL) j=p-adjvex; G-adjlistj.count-; if(G-adjlistj.count=0)/入度為 0 的相鄰頂點進棧 top+; Sttop=j; p=p-nextarc; void tuopu() int i,j; MGraph g; ALGraph *G; g.n=6;g.e=6; int AMAXVMAXV=0,1,0,0,1,0,0,0,1,0,0,0,0,0,0,1,0,