上傳人：伐***

認(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-28 格式：DOC 頁數(shù)：22 大?。?32KB 積分：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ì)說明書、圖紙、圖表、實(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ì)說明，進(jìn)入編程階段。6月19日：完成編程和測(cè)試工作。6月20日：提交課程設(shè)計(jì)報(bào)告和源程序，答辯，成績?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語言版）。清華大學(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í)語言實(shí)現(xiàn)算法的基本技能4. 掌握書寫程序設(shè)計(jì)說明文檔的能力5. 提高運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識(shí)及高級(jí)語言解決非數(shù)值實(shí)際問題的能力二. 課程設(shè)計(jì)內(nèi)容說明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ù)的翻過，輸出：這時(shí)正面向上的牌有哪些？2、猴子選大王任務(wù)：一堆猴子都有編號(hào)，編號(hào)是1，2，3 .m ,這群猴子（m個(gè)）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第n個(gè)，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。要求：輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，n<m輸出形式：中文提示按照m個(gè)猴子，數(shù)n 個(gè)數(shù)的方法，輸出為大王的猴子是幾號(hào) ，建立一個(gè)函數(shù)來實(shí)現(xiàn)此功能 3、一元多項(xiàng)式計(jì)算任務(wù)：能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸入；在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、多項(xiàng)式相加的基本過程的算法（可以使用程序

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

7、，也可以說是一個(gè)順序表。定義的結(jié)構(gòu)體有兩個(gè)數(shù)據(jù)項(xiàng)：data用來存放牌的序號(hào)，info用來存放牌被翻過的次數(shù)。開始的時(shí)候做一個(gè)52次的循環(huán)，分別為52個(gè)空間的編號(hào)賦值，并把info全部置零，因?yàn)樗麄兌紱]有被翻過。for(i=2;i<=52;i+)這句話的意思是依次以2，3，4，n為基數(shù)翻拍，所謂基數(shù)，就是如果這張牌的代碼是基數(shù)的倍數(shù)，那么這張牌就翻一次。if(aj.data)%i=0)這句話就是來判斷代號(hào)是否為基數(shù)的倍數(shù)的，因?yàn)橛鄶?shù)為零就表示為倍數(shù)，info+1，翻一次。全部翻過之后，開始一次掃描info的值，因?yàn)橐婚_始全是正面，換言之，當(dāng)info的值為奇數(shù)表示這張牌是背面向上，為偶數(shù)表示

8、這張牌是正面向上。用%2=0的方法判斷info為偶數(shù)的牌，即正面向上的牌，輸出。for(k=0;k<max;k+)/為數(shù)組賦初值，即從1到52張牌 ak.data=k+1;=0;/被翻次數(shù)一開始都是0，且均正面向上 for(i=2;i<=max;i+)/從2開始，基數(shù)遞增 for(j=i-1;j<max;j+)/每次翻過基數(shù)的倍數(shù)的牌 if(aj.data)%i=0)+;/每翻過一次，加一 printf("正面向上的牌為："); for(i=0;i<max;i+)/因?yàn)榉^偶數(shù)次后依然為正面，所以判斷那些牌的

9、翻過次數(shù)為偶數(shù)，就是正面 if(%2=0)printf("%d ",ai.data);3.1.4流程圖3.1.5調(diào)試由于正面向上的紙牌確實(shí)為1、4、9、16、25、36、49。所以程序完全正確。3.2猴子選大王3.2.1需求分析及功能簡介本題，就是給定一個(gè)數(shù)，讓一列人按照這個(gè)數(shù)字報(bào)數(shù)，報(bào)到這個(gè)數(shù)的人出列，知道最后剩一個(gè)人的時(shí)候那個(gè)人的編號(hào)就是所求的結(jié)果。并且題目規(guī)定，猴子數(shù)量必須大于數(shù)的數(shù)。由于題目規(guī)定猴子數(shù)m必須大于數(shù)的數(shù)n，故猴子數(shù)大于1。其實(shí)當(dāng)猴子為一只時(shí)，大王就是它本身了，也沒有數(shù)的必要了。之后就會(huì)輸出要求的大王，并且會(huì)很人性化的輸出一次被淘汰的猴子的

10、編號(hào)。3.2.2功能模塊一覽該程序有兩個(gè)功能。第一個(gè)功能是錄入猴子的數(shù)量，和要數(shù)的數(shù)字，這些數(shù)據(jù)均可以由用戶輸入。第二個(gè)功能就是做猴子選大王的運(yùn)算，依次輸出被淘汰的猴子，并輸出大王的號(hào)碼。3.2.3核心算法這個(gè)子程序用到的數(shù)據(jù)結(jié)構(gòu)是隊(duì)列。隊(duì)列簡稱隊(duì)，它也是一種操作受限的線性表，期限制為僅允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。把進(jìn)行插入的一端稱為隊(duì)尾（rear），進(jìn)行刪除的一端稱作隊(duì)首或隊(duì)頭（front）。向隊(duì)列中插入新元素稱為進(jìn)隊(duì)或入隊(duì)，新元素進(jìn)隊(duì)后就成為新的隊(duì)尾元素；從隊(duì)列中刪除元素成為出隊(duì)或離隊(duì)，元素出隊(duì)后，其后繼元素就成為隊(duì)首元素。由于隊(duì)列的插入和刪除操作分別是在各自的一端進(jìn)行

11、的，每個(gè)元素必然按照進(jìn)入的次序出隊(duì)，所以又把隊(duì)列成為先進(jìn)先出表。隊(duì)列的基本運(yùn)算有：初始化隊(duì)列，銷毀隊(duì)列，判斷隊(duì)列是否為空，入隊(duì)列，出隊(duì)列。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)需要使用一個(gè)數(shù)組和兩個(gè)整型變量來實(shí)現(xiàn)，利用數(shù)組順序存儲(chǔ)隊(duì)列中的所有元素，利用兩個(gè)整型變量，分別存儲(chǔ)隊(duì)首元素和隊(duì)尾元素的下標(biāo)位置，分別稱它們?yōu)殛?duì)首指針和隊(duì)尾指針。為了能夠充分地使用數(shù)組中的存儲(chǔ)空間，把數(shù)組的前端和后端連接起來，形成一個(gè)環(huán)形的順序表，即把存儲(chǔ)隊(duì)列元素的表從邏輯上看成一個(gè)環(huán)，成為環(huán)形隊(duì)列。隊(duì)首指針進(jìn)1：front=(fronr+1)%maxsize隊(duì)尾指針進(jìn)1：rear=(rear+1)%maxsizeq->rear=q-&

12、gt;front表示隊(duì)滿。也可表示隊(duì)空。void number(int n,int m) int i,j,e; sqqueue 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;i<m;i+)printf("第%d只猴子被淘汰了t_tn",i);printf("大王為第%d只猴子！",m);else while(q.rear-q.front)%m!=1) for(j=1;j<n;j+) q.front=(q.

13、front+1)%m; e=q.dataq.front; q.rear=(q.rear+1)%m; q.dataq.rear=e; printf("第%d只猴子被淘汰了t_tn",q.data(q.front+1)%m);q.front=(q.front+1)%m; e=q.dataq.rear; printf("大王為第%d只猴子！ ",e);3.2.4流程圖圖3猴子選大王3.2.5調(diào)試第一次輸入0，由于m的值規(guī)定大于1，所以報(bào)錯(cuò)。第二次輸入3，符合要求，繼續(xù)輸入。第三次輸入4，此時(shí)n的值大于m，不符合規(guī)定，報(bào)錯(cuò)。第四次輸入2，此時(shí)n的值小于m，符合規(guī)

14、定，系統(tǒng)開始依次輸出被淘汰的倒霉鬼的序號(hào)，并輸出最后的大王。3.3一元多項(xiàng)式計(jì)算3.3.1需求分析及功能簡介1.能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；2.能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸入；3.3.2功能模塊一覽3.3.3核心算法void minus(polynode *ha,polynode *hb,polynode *hc)polynode *pa=ha->next,*pb=hb->next,*s,*tc;float c;hc=(polynode *)malloc(sizeof(polynode);tc=hc;while(pa!=null&&pb!=n

15、ull)if(pa->exp>pb->exp)s=(polynode *)malloc(sizeof(polynode);s->exp=pa->exp;s->coef=pa->coef;tc->next=s;tc=s;pa=pa->next;else if(pa->exp<pb->exp)s=(polynode *)malloc(sizeof(polynode);s->exp=pb->exp;s->coef=-pb->coef;tc->next=s;tc=s;pb=pb->next;el

16、sec=pa->coef-pb->coef;if(c!=0)s=(polynode *)malloc(sizeof(polynode);s->exp=pa->exp;s->coef=c;tc->next=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->

17、;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、 多項(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ǔ)

18、多項(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需求分析及功能簡介編寫函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判蜻@樣的線性序列稱為滿足拓?fù)浯涡?topological order)的序列，簡稱拓?fù)湫蛄?。簡單的說，由某個(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ù)浯涡蚺懦梢恍校瑒t圖中所有的有向邊均是從左指向右的。 若圖中存在有向環(huán)，則不可能使頂點(diǎn)滿足拓?fù)浯涡?。一個(gè)dag的拓?fù)湫蛄型ǔ１硎灸撤N方案切實(shí)可行。 3.4.2功能模塊一覽實(shí)現(xiàn)拓?fù)渑判?.4.3核心算法vo