課程設計報告1 紙牌游戲2猴子選大王 3多項式計算 4 拓撲排序

1、上海應用技術學院課程設計任務書課程名稱數(shù)據(jù)結構課程設計課程代碼設計題目1、紙牌游戲 2、猴子選大王3、一元多項式計算 4、拓撲排序 設計時間2012年 6 月 17 日 2012年 6 月 21 日系（院）計算機科學與信息工程學院專業(yè)計算機科學與技術班級10104301一、課程設計任務（條件）、具體技術參數(shù)（指標）本次課程設計完成如下模塊（共13個模塊，學生可以在其中至少挑選3個功能塊完成，但有*號的模塊是必須要選擇2個,多做可以加分）1、 運動會分數(shù)統(tǒng)計*2、 一元多項式計算*3、 訂票系統(tǒng)4、 迷宮求解5、 文章編輯*6、 joseph環(huán)7、 猴子選大王*8、建立二叉樹，層序、先序、中序、

2、后序遍歷（ 用遞歸或非遞歸的方法都可以）*9、 赫夫曼樹的建立10、紙牌游戲*11、圖的建立及輸出12、拓撲排序13、各種排序二、對課程設計成果的要求（包括課程設計說明書、圖紙、圖表、實物等軟硬件要求）1. 提交課程設計報告（格式及文件名參見模板）一份。2. 提交源程序文件及配套文件一套。三、課程設計工作進度計劃：6月17日：指導老師下發(fā)課程設計指導書和任務書，并進行必要的指導，學生完成選題。6月18日：完成詳細設計說明，進入編程階段。6月19日：完成編程和測試工作。6月20日：提交課程設計報告和源程序，答辯，成績評定。四、主要參考資料1李春葆.數(shù)據(jù)結構學習指導.清華大學出版社,20102張曉

3、莉等.數(shù)據(jù)結構與算法.機械工業(yè)出版社,20023李春葆.數(shù)據(jù)結構教程上機實驗指導.清華大學出版社,2010.4 r krishnamoorthy、g indirani kumaravel。data structures using c數(shù)據(jù)結構（c語言版）。清華大學出版社。2009-9指導教師（簽名）： 年 月 日教研室主任（簽名）： 年 月 日上海應用技術學院課程設計報告課程名稱 數(shù)據(jù)結構課程設計 設計題目 1 紙牌游戲 2.猴子選大王 3.多項式計算 4 拓撲排序 院系 計算機科學與信息工程學院 專業(yè) 網(wǎng)絡工程 班級 10104301 姓名 周廣捷 學號 1010430135 指導教師 林捷

4、 日期 12年6月17日_12 年 6月21日一. 目的與要求1. 鞏固和加深對常見數(shù)據(jù)結構的理解和掌握2. 掌握基于數(shù)據(jù)結構進行算法設計的基本方法3. 掌握用高級語言實現(xiàn)算法的基本技能4. 掌握書寫程序設計說明文檔的能力5. 提高運用數(shù)據(jù)結構知識及高級語言解決非數(shù)值實際問題的能力二. 課程設計內(nèi)容說明1、紙牌游戲 ；任務：編號為1-52張牌，正面向上，從第2張開始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后從第4張開始，以4為基數(shù)，是4的倍數(shù)的牌翻一次， 直到最后一張牌；.再依次5的倍數(shù)的牌翻一次，6的，7的直

5、到以52為基數(shù)的翻過，輸出：這時正面向上的牌有哪些？2、猴子選大王任務：一堆猴子都有編號，編號是1，2，3 .m ,這群猴子（m個）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第n個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。要求：輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，nm輸出形式：中文提示按照m個猴子，數(shù)n 個數(shù)的方法，輸出為大王的猴子是幾號 ，建立一個函數(shù)來實現(xiàn)此功能 3、一元多項式計算任務：能夠按照指數(shù)降序排列建立并輸出多項式；能夠完成兩個多項式的相加、相減，并將結果輸入；在上交資料中請寫明：存儲結構、多項式相加的基本過程的算法（可以使用程序流程圖）

6、 、源程序、測試數(shù)據(jù)和結果、算法的時間復雜度、另外可以提出算法的改進方法；4、拓撲排序任務：編寫函數(shù)實現(xiàn)圖的拓撲排序3.1.1需求分析及功能簡介這道題的需求很簡單，就是一副紙牌（52）張按序號遞增的順序依次正面向上放好，以2為基數(shù)從2號牌開始依次翻過2的倍數(shù)；以32為基數(shù)從32號牌開始依次翻過32的倍數(shù)；以52為基數(shù)從52號牌開始依次翻過52的倍數(shù)；然后輸出此時依然正面向上的牌。由于52張牌已經(jīng)定死，所以這個程序的功能相對也簡單，就是按照它的要求輸出經(jīng)過51次后仍然正面向上的牌。3.1.2功能模塊一覽該模塊就一個功能，輸出正面向上的牌的序號。3.1.3核心算法該算法用到的數(shù)據(jù)結構是數(shù)組，也可以

7、說是一個順序表。定義的結構體有兩個數(shù)據(jù)項：data用來存放牌的序號，info用來存放牌被翻過的次數(shù)。開始的時候做一個52次的循環(huán)，分別為52個空間的編號賦值，并把info全部置零，因為他們都沒有被翻過。for(i=2;i=52;i+)這句話的意思是依次以2，3，4，n為基數(shù)翻拍，所謂基數(shù)，就是如果這張牌的代碼是基數(shù)的倍數(shù)，那么這張牌就翻一次。if(aj.data)%i=0)這句話就是來判斷代號是否為基數(shù)的倍數(shù)的，因為余數(shù)為零就表示為倍數(shù)，info+1，翻一次。全部翻過之后，開始一次掃描info的值，因為一開始全是正面，換言之，當info的值為奇數(shù)表示這張牌是背面向上，為偶數(shù)表示這張牌是正面向上

8、。用%2=0的方法判斷info為偶數(shù)的牌，即正面向上的牌，輸出。for(k=0;kmax;k+)/為數(shù)組賦初值，即從1到52張牌 ak.data=k+1;=0;/被翻次數(shù)一開始都是0，且均正面向上 for(i=2;i=max;i+)/從2開始，基數(shù)遞增 for(j=i-1;jmax;j+)/每次翻過基數(shù)的倍數(shù)的牌 if(aj.data)%i=0)+;/每翻過一次，加一 printf(正面向上的牌為：); for(i=0;irear=q-front表示隊滿。也可表示隊空。void number(int n,int m) int i,j,e; sqqueu

9、e q; q.front=q.rear=0; for(i=1;i=m;i+) q.rear=(q.rear+1)%m; q.dataq.rear=i; if(n=1)for(i=1;im;i+)printf(第%d只猴子被淘汰了t_tn,i);printf(大王為第%d只猴子！,m);else while(q.rear-q.front)%m!=1) for(j=1;jnext,*pb=hb-next,*s,*tc;float c;hc=(polynode *)malloc(sizeof(polynode);tc=hc;while(pa!=null&pb!=null)if(pa-exppb-ex

10、p)s=(polynode *)malloc(sizeof(polynode);s-exp=pa-exp;s-coef=pa-coef;tc-next=s;tc=s;pa=pa-next;else if(pa-expexp)s=(polynode *)malloc(sizeof(polynode);s-exp=pb-exp;s-coef=-pb-coef;tc-next=s;tc=s;pb=pb-next;elsec=pa-coef-pb-coef;if(c!=0)s=(polynode *)malloc(sizeof(polynode);s-exp=pa-exp;s-coef=c;tc-ne

11、xt=s;tc=s;pa=pa-next;pb=pb-next;if(pb!=null)pa=pb;while(pa!=null)s=(polynode *)malloc(sizeof(polynode);s-exp=pa-exp;s-coef=pa-coef;tc-next=s;tc=s;pa=pa-next;tc-next=null;printf(多項式減法的結果為：);disppoly(hc);3.3.4流程圖1、輸入輸出開始申請結點空間+num輸入多項式的項數(shù)指針數(shù)組tempi中（i=1num）輸入多項式各項的系數(shù) x, 指數(shù) y輸出已輸入的多項式 合并同類項結束否是是否輸入正確2、

12、多項式的加法開始定義存儲結果的空鏈 r是 否輸出存儲多項式的和的鏈r結束是否同指數(shù)項系數(shù)相加后存入r中直接把p中各項存入r中直接把q中各項存入r存儲多項式2的空鏈q是否為空存儲多項式1的空鏈p是否為空合并同類項3、 多項式的減法 開始定義存儲結果的空鏈 r是 否輸出存儲多項式的和的鏈r結束是否同指數(shù)項系數(shù)相加后存入r中把p中各項系數(shù)改變符號后存入r中直接把q中各項存入r存儲多項式2的空鏈q是否為空存儲多項式1的空鏈p是否為空合并同類項3.3.5調(diào)試3.4 拓撲排序3.4.1需求分析及功能簡介編寫函數(shù)實現(xiàn)圖的拓撲排序這樣的線性序列稱為滿足拓撲次序(topological order)的序列，簡稱

13、拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。離散數(shù)學中關于偏序和全序的定義： 若集合x上的關系是r是自反的、反對稱的和傳遞的，則稱r是集合x上的偏序關系。 設r是集合x上的偏序（partial order）,如果對每個x,y屬于x必有xry 或 yrx，則稱r是集合x上的全序關系。 注意： 若將圖中頂點按拓撲次序排成一行，則圖中所有的有向邊均是從左指向右的。 若圖中存在有向環(huán)，則不可能使頂點滿足拓撲次序。一個dag的拓撲序列通常表示某種方案切實可行。 3.4.2功能模塊一覽實現(xiàn)拓撲排序3.4.3核心算法void topsort(algraph *g)int i,j;int stmaxv,top=-1; /*棧st的指針為top*/arcnode *p;for (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) /*棧不為空時循環(huán)*/i