項目作業(yè)文檔模板

1、PAGE PAGE 1湖南大眾傳媒學(xué)院網(wǎng)絡(luò)傳媒系算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告姓 名：班 級：學(xué) 號：指導(dǎo)教師師： 年月日日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 PAGE 8課程設(shè)計計綜合成成績評定定設(shè)計題目目一：約瑟瑟夫生者者死者游游戲考核項目目分值A(chǔ)C得分設(shè)計情況況（共770分）設(shè)計工作作量與難難度20設(shè)計工作作量大與與設(shè)計有有一定難難度設(shè)計工作作量與難難度一般般，基本本達(dá)到了了要求設(shè)計方案15設(shè)計方案案正確、合理設(shè)計方案案較正確確、基本本合理，但不是是最優(yōu)設(shè)計完成成情況35完成了選選題的設(shè)設(shè)計內(nèi)容容，設(shè)計計功能完完整，相相關(guān)算法法設(shè)計正正確，程程序結(jié)果果正確、直觀性性好基本完成成了選題題的設(shè)計計內(nèi)容及及主要選選

2、題功能能，相關(guān)關(guān)算法設(shè)設(shè)計基本本正確，程序結(jié)結(jié)果正確確設(shè)計報告告（共115分）報告組織織結(jié)構(gòu)及及內(nèi)容10內(nèi)容組織織及結(jié)構(gòu)構(gòu)合理、內(nèi)容充充實(shí)、層層次清晰晰、圖表表得當(dāng)內(nèi)容組織織及結(jié)構(gòu)構(gòu)較合理理、內(nèi)容容較充實(shí)實(shí)、層次次較清晰晰、圖表表應(yīng)用基基本得當(dāng)當(dāng)報告排版版格式5格式規(guī)范范，完全全符合要要求格式基本本規(guī)范，基本符符合要求求設(shè)計態(tài)度度（共115分）15設(shè)計態(tài)度度認(rèn)真、積極設(shè)計態(tài)度度比較認(rèn)認(rèn)真綜合得分分課程設(shè)計計綜合成成績（折折合為優(yōu)優(yōu)、良、中、及及格與不不及格計計）其它說明明：目 錄錄TOC o 1-3 h z u HYPERLINK l _Toc185566256 1.約瑟瑟夫生者者死者游游戲

3、PAGEREF _Toc185566256 h 1 HYPERLINK l _Toc185566257 1.1 項目目簡介 PAGEREF _Toc185566257 h 11 HYPERLINK l _Toc185566258 1.2 設(shè)計計思路 PAGEREF _Toc185566258 h 11 HYPERLINK l _Toc185566259 1.3 數(shù)據(jù)據(jù)結(jié)構(gòu) PAGEREF _Toc185566259 h 22 HYPERLINK l _Toc185566260 1.4 運(yùn)行行結(jié)果 PAGEREF _Toc185566260 h 22 HYPERLINK l _Toc185566

4、266 2.總結(jié)結(jié)與分析析 PAGEREF _Toc185566266 h 4 HYPERLINK l _Toc185566267 附錄 PAGEREF _Toc185566267 h 5 HYPERLINK l _Toc185566269 附錄約瑟瑟夫生者者死者游游戲程序序源代碼碼 PAGEREF _Toc185566269 h 51.約瑟瑟夫生者者死者游游戲1.1 項目目簡介約瑟夫生生者死者者游戲的的大意是是：300個旅客客同乘一一條船，因為嚴(yán)嚴(yán)重超載載，加上上風(fēng)高浪浪大，危危險萬分分；因此此船長告告訴乘客客，只有有將全船船一半的的旅客投投入海中中，其余余人才能能幸免遇遇難。無無奈，大大家

5、只得得同意這這種辦法法，并議議定300個人圍成一一圈，由由第一個個人開始始，依次次報數(shù)，數(shù)到第第9人，便把他他投入大大海中，然后從從他的下下一個人人數(shù)起，數(shù)到第第9人，再將他他投入大大海，如如此循環(huán)環(huán)，直到到剩下115個乘乘客為止止。問哪哪些位置置是將被被扔下大大海的位位置。1.2設(shè)設(shè)計思路路本游戲的的數(shù)學(xué)建建模如下下：假設(shè)設(shè)n個旅旅客排成成一個環(huán)環(huán)形，依依次順序序編號11，2，nn。從某某個指定定的第11號開始始，沿環(huán)環(huán)計數(shù)，每數(shù)到到第m個個人就讓讓其出列列，且從從下一個個人開始始重新計計數(shù)，繼繼續(xù)進(jìn)行行下去。這個過過程一直直進(jìn)行到到剩下kk個旅客客為止。本游戲的的要求用用戶輸入入的內(nèi)容包括

6、括： 1. 旅旅客的個個數(shù)，也也就是nn的值； 2. 離離開旅客客的間隔隔數(shù)，也就就是m的的值；3. 所所有旅客客的序號號作為一一組數(shù)據(jù)據(jù)要求存放放在某種種數(shù)據(jù)結(jié)結(jié)構(gòu)中。本游戲要要求輸出出的內(nèi)容容是包括括1. 離離開旅客客的序號號； 2. 剩剩余旅客客的序號號； 所以，根根據(jù)上面面的模型型分析及輸入輸輸出參數(shù)數(shù)分析，可以定定義一種種數(shù)據(jù)結(jié)結(jié)構(gòu)后進(jìn)進(jìn)行算法法實(shí)現(xiàn)。1.3 數(shù)據(jù)據(jù)結(jié)構(gòu)為了解決決這一問問題，可可以用長長度為330的數(shù)數(shù)組作為為線性存存儲結(jié)構(gòu)構(gòu)，并把把該數(shù)組組看成是是一個首首尾相接接的環(huán)形形結(jié)構(gòu)，那么每每投入大大海一個個乘客，就要在在該數(shù)組組的相應(yīng)應(yīng)位置做做一個刪刪除標(biāo)記記，該單單元以

7、后后就不再再作為計計數(shù)單元元。這樣樣做不僅僅算法較較為復(fù)雜雜，而且且效率低低，還要要移動大大量的元元素。用用單循環(huán)環(huán)鏈表解解決這一一問題，實(shí)現(xiàn)的的方法相相對要簡簡單得多多。首先先要定義義鏈表結(jié)結(jié)點(diǎn)，單單循環(huán)鏈鏈表的結(jié)結(jié)點(diǎn)結(jié)構(gòu)構(gòu)與一般般的結(jié)點(diǎn)點(diǎn)結(jié)構(gòu)完完全相同同，只是是數(shù)據(jù)域域用一個個整數(shù)來來表示位位置；然然后將它它們組成成具有330個結(jié)結(jié)點(diǎn)的單單循環(huán)鏈鏈表。接接下來從從位置為為1的結(jié)結(jié)點(diǎn)開始始數(shù)，數(shù)數(shù)到第88個結(jié)點(diǎn)點(diǎn)，就將將下一個個結(jié)點(diǎn)從從循環(huán)鏈鏈表中刪刪去，然然后再從從刪去結(jié)結(jié)點(diǎn)的下下一個結(jié)結(jié)點(diǎn)開始始數(shù)起，數(shù)到第第8個結(jié)結(jié)點(diǎn)，再再將其下下一個結(jié)結(jié)點(diǎn)刪去去，如此此進(jìn)行下下去，直直到剩下下15個個

8、結(jié)點(diǎn)為為止。為了不失失一般性性，將330改為為一個任任意輸入入的正整整數(shù)n，而報數(shù)數(shù)上限（原為99）也為為一個任任選的正正整數(shù)kk。這樣樣該算法法描述如如下：(1) 創(chuàng)建含含有n個個結(jié)點(diǎn)的的單循環(huán)環(huán)鏈表；(2) 生著與與死者的的選擇：p指向鏈鏈表的第第一個結(jié)結(jié)點(diǎn)，初初始i置置為1；whille(iiddataa;i自增增1；(3) 輸出所所有生者者的位置置。1.4運(yùn)運(yùn)行結(jié)果果3.總結(jié)結(jié)與分析析此程序目目前的缺缺點(diǎn)在于于，結(jié)點(diǎn)點(diǎn)密碼數(shù)數(shù)據(jù)類型型定義的的存儲類類型是iint型型，不能能超過-214474883644822147748336488，一旦旦超過則則程序輸輸出結(jié)果果有誤，另一個個缺點(diǎn)就就

9、是程序序運(yùn)行當(dāng)當(dāng)中，一一旦中途途輸入出出現(xiàn)錯誤誤，則無無法返回回，必須須將當(dāng)前前操作結(jié)結(jié)束等到到下個主主函數(shù)的的循環(huán)開開始，或或者直接接退出重重新運(yùn)行行此程序序。優(yōu)點(diǎn)點(diǎn)則在于于程序運(yùn)運(yùn)行速度度較快，不會出出現(xiàn)輸出出結(jié)果有有誤的問問題經(jīng)過這次次集中上上機(jī)的實(shí)實(shí)驗，從從開始選選題到自自己上手手還是編編寫程序序的過程程中，我我學(xué)會了了很多的的東西，以前對對C語言言的知識識和算法法總是模模棱兩可可的，經(jīng)經(jīng)過這次次練習(xí)，在某些些方面上上還是經(jīng)經(jīng)過了加加強(qiáng)的訓(xùn)訓(xùn)練。此此次，實(shí)實(shí)驗，從從開始構(gòu)構(gòu)建循環(huán)環(huán)鏈表然然后實(shí)現(xiàn)現(xiàn)約瑟夫夫環(huán)功能能的過程程中，中中途也遇遇見一些些問題，但都逐逐一克服服，相信信在這次次的實(shí)

10、驗驗中提升升了較大大的自身身動手實(shí)實(shí)踐能力力。學(xué)好好數(shù)據(jù)結(jié)結(jié)構(gòu)！附 錄錄附錄1約約瑟夫生生者死者者游戲程程序源代代碼LinkkLisst IInittRinng(iint n, LinnkLiist R) /尾插插入法建建立單循循環(huán)鏈表表函數(shù)LisstNoode *p, *qq;intt I;R=qq=(LLinkkNodde *)maallooc(ssizeeof(LinnkNoode);forr(i=1;iidaata=i;q-neext=p;q=p;p-datta=nn;p-nexxt=RR;R=pp;retturnn R;LinkkLisst DDeleeteDDeatth(iint

11、n, intt k, LiinkLListt R) /生者與與死者的的選擇intt i, j;LisstNoode *p, *qq;p=RR;forr(i=1; inn/2; i+)/刪刪除一半半結(jié)點(diǎn)foor(jj=1; jneext;q=p-nexxt;p-neext=q-nexxt;prrinttf(“%4dd”, qq-ddataa);frree(q);R=p; reeturrn RR;voiid OOutRRingg(innt nn, LLinkkLisst RR) /輸輸出所有有生者innt ii;LiinkNNodee *pp;p=R;foor(ii=1;inexxt)pprinn

12、tf(“%4dd”, pp-ddataa)有了上述述算法分分析和設(shè)設(shè)計之后后，實(shí)現(xiàn)現(xiàn)就比較較簡單了了。首先先要定義義一個鏈鏈表結(jié)構(gòu)構(gòu)類型，然后編編寫一個個主函數(shù)數(shù)調(diào)用上上面已定定義好的的函數(shù)即即可。主主函數(shù)的的源程序序如下：#inccludde#inccluddetypeedeff sttrucct nnodeeintt daata;strructt noode * nnextt;LisstNoode;typeedeff LiistNNodee * LinnkLiist;voidd maain()LinnkLiist R;intt n,k;LinnkLiist IniitRiing(intt n, LiinkLListt R);LinnkLiist DelleteeDeaath(intt