上傳人：灰***

認(rèn)證信息

認(rèn)證類型：機(jī)構(gòu)認(rèn)證

認(rèn)證主體：寧夏凱米世紀(jì)網(wǎng)絡(luò)科技有限公司

IP屬地：寧夏

統(tǒng)一社會(huì)信用代碼/組織機(jī)構(gòu)代碼

91640100MA774ECW4K

IP屬地：寧夏 上傳時(shí)間：2021-10-15 格式：DOC 頁(yè)數(shù)：23 大?。?71KB 積分：15 舉報(bào) 版權(quán)申訴

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

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

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

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

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

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

7、說(shuō)是一個(gè)順序表。定義的結(jié)構(gòu)體有兩個(gè)數(shù)據(jù)項(xiàng)：data用來(lái)存放牌的序號(hào)，info用來(lái)存放牌被翻過(guò)的次數(shù)。開始的時(shí)候做一個(gè)52次的循環(huán)，分別為52個(gè)空間的編號(hào)賦值，并把info全部置零，因?yàn)樗麄兌紱](méi)有被翻過(guò)。for(i=2;i=52;i+)這句話的意思是依次以2，3，4，n為基數(shù)翻拍，所謂基數(shù)，就是如果這張牌的代碼是基數(shù)的倍數(shù)，那么這張牌就翻一次。if(aj.data)%i=0)這句話就是來(lái)判斷代號(hào)是否為基數(shù)的倍數(shù)的，因?yàn)橛鄶?shù)為零就表示為倍數(shù)，info+1，翻一次。全部翻過(guò)之后，開始一次掃描info的值，因?yàn)橐婚_始全是正面，換言之，當(dāng)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+)/每次翻過(guò)基數(shù)的倍數(shù)的牌 if(aj.data)%i=0)+;/每翻過(guò)一次，加一 printf(正面向上的牌為：); for(i=0;irear=q-front表示隊(duì)滿。也可表示隊(duì)空。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(多項(xiàng)式減法的結(jié)果為：);disppoly(hc);3.3.4流程圖1、輸入輸出開始申請(qǐng)結(jié)點(diǎn)空間+num輸入多項(xiàng)式的項(xiàng)數(shù)指針數(shù)組tempi中（i=1num）輸入多項(xiàng)式各項(xiàng)的系數(shù) x, 指數(shù) y輸出已輸入的多項(xiàng)式 合并同類項(xiàng)結(jié)束否是是否輸入正確2、

12、多項(xiàng)式的加法開始定義存儲(chǔ)結(jié)果的空鏈 r是 否輸出存儲(chǔ)多項(xiàng)式的和的鏈r結(jié)束是否同指數(shù)項(xiàng)系數(shù)相加后存入r中直接把p中各項(xiàng)存入r中直接把q中各項(xiàng)存入r存儲(chǔ)多項(xiàng)式2的空鏈q是否為空存儲(chǔ)多項(xiàng)式1的空鏈p是否為空合并同類項(xiàng)3、 多項(xiàng)式的減法 開始定義存儲(chǔ)結(jié)果的空鏈 r是 否輸出存儲(chǔ)多項(xiàng)式的和的鏈r結(jié)束是否同指數(shù)項(xiàng)系數(shù)相加后存入r中把p中各項(xiàng)系數(shù)改變符號(hào)后存入r中直接把q中各項(xiàng)存入r存儲(chǔ)多項(xiàng)式2的空鏈q是否為空存儲(chǔ)多項(xiàng)式1的空鏈p是否為空合并同類項(xiàng)3.3.5調(diào)試3.4 拓?fù)渑判?.4.1需求分析及功能簡(jiǎn)介編寫函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判蜻@樣的線性序列稱為滿足拓?fù)浯涡?topological order)的序列，簡(jiǎn)稱

13、拓?fù)湫蛄?。?jiǎn)單的說(shuō)，由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱之為拓?fù)渑判颉ｋx散數(shù)學(xué)中關(guān)于偏序和全序的定義： 若集合x上的關(guān)系是r是自反的、反對(duì)稱的和傳遞的，則稱r是集合x上的偏序關(guān)系。 設(shè)r是集合x上的偏序（partial order）,如果對(duì)每個(gè)x,y屬于x必有xry 或 yrx，則稱r是集合x上的全序關(guān)系。 注意： 若將圖中頂點(diǎn)按拓?fù)浯涡蚺懦梢恍?，則圖中所有的有向邊均是從左指向右的。 若圖中存在有向環(huán)，則不可能使頂點(diǎn)滿足拓?fù)浯涡?。一個(gè)dag的拓?fù)湫蛄型ǔ１硎灸撤N方案切實(shí)可行。 3.4.2功能模塊一覽實(shí)現(xiàn)拓?fù)渑判?.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+)/*求所有頂點(diǎn)的入度*/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的頂點(diǎn)進(jìn)棧*/top+; sttop=i; while (top-1) /*棧不為空時(shí)循環(huán)*/i