PAGEPAGE23**＊*****＊****＊＊***＊實(shí)踐教學(xué)＊***＊＊*******＊****＊蘭州理工大學(xué)軟件職業(yè)技術(shù)學(xué)院2011年春季學(xué)期算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目:約瑟夫環(huán)專業(yè)班級(jí)：姓名:學(xué)號(hào)：指導(dǎo)教師:成績(jī):摘要約瑟夫環(huán)問(wèn)題是典型的線性表的應(yīng)用實(shí)例,其開發(fā)主要包括后臺(tái)數(shù)據(jù)庫(kù)的建立和維護(hù)以及前端應(yīng)用程序的開發(fā)兩個(gè)方面。對(duì)于前者要求建立起數(shù)據(jù)一致性和完整性強(qiáng)、數(shù)據(jù)安全性好的庫(kù).而對(duì)于后者則要求應(yīng)用程序功能完備,易使用等特點(diǎn)。經(jīng)過(guò)分析，我們使用MICＲＯSOFＴ公司的MicｒosoftＶisuａlＣ+＋６.0開發(fā)工具，利用其提供的各種面向?qū)ο蟮拈_發(fā)工具,尤其是數(shù)據(jù)窗口這一能方便而簡(jiǎn)潔操縱數(shù)據(jù)庫(kù)的智能化對(duì)象,首先在短時(shí)間內(nèi)建立系統(tǒng)應(yīng)用原型，然后,對(duì)初始原型系統(tǒng)進(jìn)行需求迭代,不斷修正和改進(jìn),直到形成用戶滿意的可行系統(tǒng)。關(guān)鍵詞:單循環(huán)鏈表；ｃ語(yǔ)言;約瑟夫環(huán);序言數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素之間的邏輯關(guān)系的一門課程，以及數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)中的存儲(chǔ)表示和對(duì)這些數(shù)據(jù)所施加的運(yùn)算.該課程設(shè)計(jì)的目的是通過(guò)課程設(shè)計(jì)的綜合訓(xùn)練,培養(yǎng)分析和編程等實(shí)際動(dòng)手能力，系統(tǒng)掌握數(shù)據(jù)結(jié)構(gòu)這門課程的主要內(nèi)容。本次課程設(shè)計(jì)的內(nèi)容是用單循環(huán)鏈表模擬約瑟夫環(huán)問(wèn)題,循環(huán)鏈表是一種首尾相接鏈表，其特點(diǎn)是無(wú)須增加存儲(chǔ)容量,僅對(duì)表的鏈接方式稍作改變,使表處理更加靈活，約瑟夫環(huán)問(wèn)題就是用單循環(huán)鏈表處理的一個(gè)實(shí)際應(yīng)用。通過(guò)這個(gè)設(shè)計(jì)實(shí)例，了解單鏈表和單循環(huán)鏈表的相同與不同之處,進(jìn)一步加深對(duì)鏈表結(jié)構(gòu)類型及鏈表操作的理解.通過(guò)該課程設(shè)計(jì),能運(yùn)用所學(xué)知識(shí),能上機(jī)解決一些實(shí)際問(wèn)題,了解并初步掌握設(shè)計(jì)、實(shí)現(xiàn)較大程序的完整過(guò)程，包括系統(tǒng)分析、編碼設(shè)計(jì)、系統(tǒng)集成、以及調(diào)試分析,熟練掌握數(shù)據(jù)結(jié)構(gòu)的選擇、設(shè)計(jì)、實(shí)現(xiàn)以及操作方法,為進(jìn)一步的應(yīng)用開發(fā)打好基礎(chǔ)。目錄TOC\ｏ”1—３”\ｈ＼z\uＨＹPＥRＬINK＼l”_Toｃ29８072296”摘要PＡＧEREF_Ｔoc298０72296\h１HYPERLＩNK＼l”_Ｔｏｃ２98072297”序言PAＧＥＲEF_Toｃ29807229７＼ｈ2HYＰＥＲLIＮK\l”＿Toc２9807229８”目錄PAGＥRＥF_Tｏc2980722９８\h3ＨＹＰEＲLINK\l”_Toｃ29807229９”正文PAGERＥＦ_Toc29807２２99\ｈ４HＹPERLINK\l"_Tｏc298072300"一、問(wèn)題描述PAGＥＲＥF＿Toc2980７２300\h4ＨYＰERLINK\l”＿Toc2９80７２301"二、邏輯設(shè)計(jì)PAＧEＲEF＿Toc298072３01\h5ＨYPEＲLＩNK\l”_Ｔｏc２98０72３02”三、詳細(xì)設(shè)計(jì)PAＧＥＲEF＿Ｔoc２9807２３02\ｈ７HYＰERLＩNK\l”_Toc298072303”四、程序代碼PAＧEREＦ_Toｃ2980７2303\h1３HYPＥRLINＫ\ｌ”＿Ｔoｃ29８0723０4＂五、程序調(diào)試與測(cè)試PＡGＥREF_Toc29807２304＼h13ＨYPERＬIＮK\l”_Toc２98072３05”設(shè)計(jì)總結(jié)ＰＡGERＥF_Tｏc298072305\h18HYＰERLINK\l”_Ｔoｃ２9８07２306"參考文獻(xiàn)PＡＧEＲEF_Ｔｏc298072３０６\h19HYPERLＩNK\l”_Tｏｃ29８0７2307＂致謝ＰAＧERＥF_Ｔｏc2９8072307\ｈ20HＹPEＲＬＩNＫ［２]按要求求解約瑟夫環(huán)\n”)； ｐｒintf(”［０］退出\n");?ｐｒintf("＊***＊＊*＊＊**＊**＊*****＊**＊**歡迎使用!**＊*＊*＊**＊****＊＊*******＊****＼n＂);｝四、程序代碼見(jiàn)附錄源程序.五、程序調(diào)試與測(cè)試1.調(diào)用模塊時(shí)，結(jié)點(diǎn)結(jié)構(gòu)的調(diào)用與其他模塊產(chǎn)生沖突,導(dǎo)致每一行都出現(xiàn)兩次錯(cuò)誤,加入子函數(shù)的聲明后錯(cuò)誤消失.2.剛開始時(shí)曾忽略了一些變量參數(shù)的標(biāo)識(shí)”&＂和“＊”，使調(diào)試程序時(shí)費(fèi)時(shí)不少。今后應(yīng)重視確定參數(shù)的變量和賦值屬性的區(qū)分和標(biāo)識(shí)。３.本次課程設(shè)計(jì)采用數(shù)據(jù)抽象的程序設(shè)計(jì)方法，將程序劃分為三個(gè)層次結(jié)構(gòu)：元素節(jié)點(diǎn)、單向循環(huán)鏈表,主控制模塊.思路較為清晰，實(shí)現(xiàn)調(diào)用順利。經(jīng)過(guò)本次實(shí)驗(yàn),使我對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程有了進(jìn)一步的了解，每一個(gè)程序經(jīng)過(guò)需求分析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)之后，思路即清晰呈現(xiàn),程序也很快就出來(lái)了,最后經(jīng)過(guò)調(diào)試、運(yùn)行又有新的體驗(yàn)。＜測(cè)試用例>這是一個(gè)使用循環(huán)鏈表的經(jīng)典問(wèn)題。本程序開始運(yùn)行界面如下:圖7約瑟夫環(huán)開始運(yùn)行界面圖7約瑟夫環(huán)開始運(yùn)行界面選擇1進(jìn)入約瑟夫環(huán)問(wèn)題闡述.圖8約瑟夫環(huán)問(wèn)題闡述圖8約瑟夫環(huán)問(wèn)題闡述①選擇2,輸入下列數(shù)據(jù)測(cè)試：請(qǐng)輸入總?cè)藬?shù)n：7請(qǐng)輸入開始上限數(shù)ｍ：20；請(qǐng)依次輸入每個(gè)人的密碼：3１７２4８４出隊(duì)順序:６147２3５圖9約瑟夫環(huán)測(cè)試1圖9約瑟夫環(huán)測(cè)試1②繼續(xù)選擇2,輸入下列數(shù)據(jù)測(cè)試：請(qǐng)輸入總?cè)藬?shù)n:5請(qǐng)輸入開始上限數(shù)m:３0請(qǐng)依次輸入每個(gè)人的密碼：3456７出隊(duì)順序：53１24圖10約瑟夫環(huán)測(cè)試2圖10約瑟夫環(huán)測(cè)試2③繼續(xù)選擇2，輸入下列數(shù)據(jù)測(cè)試：請(qǐng)輸入總?cè)藬?shù)ｎ：８請(qǐng)輸入開始上限數(shù)ｍ：14請(qǐng)依次輸入每個(gè)人的密碼:３45６78910出隊(duì)順序：67２８３514圖11約瑟夫環(huán)測(cè)試3圖11約瑟夫環(huán)測(cè)試3測(cè)試完成,選擇0退出。設(shè)計(jì)總結(jié)我的這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的題目是:《約瑟夫環(huán)》,通過(guò)對(duì)該題目的設(shè)計(jì),我加深了對(duì)數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)的理解,進(jìn)一步地理解和掌握了課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu),尤其是對(duì)單循環(huán)鏈表上基本運(yùn)算的實(shí)現(xiàn)，學(xué)會(huì)了如何把學(xué)到的知識(shí)用于解決實(shí)際問(wèn)題,鍛煉了自己動(dòng)手的能力.通過(guò)這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，我感受最深的就是對(duì)于循環(huán)鏈表的使用,可以說(shuō)對(duì)循環(huán)鏈表有了比以前更進(jìn)一步的認(rèn)識(shí)，以前只是一知半解的，如果只給個(gè)題目自己根本不能把程序完整地編寫出來(lái)，所以這次課程設(shè)計(jì)最大的收獲就在于對(duì)循環(huán)鏈表有了一定的理解,包括其中的一系列操作，如建立一個(gè)循環(huán)鏈表,刪除鏈表中的一個(gè)結(jié)點(diǎn)，增加一個(gè)結(jié)點(diǎn)等。在調(diào)試程序的時(shí)候我也有所體會(huì),雖然約瑟夫環(huán)問(wèn)題不是很難，但調(diào)試的時(shí)候還是會(huì)出現(xiàn)很多錯(cuò)誤,因此我們不能認(rèn)為容易就不認(rèn)真對(duì)待。在以后的學(xué)習(xí)中,要能不斷發(fā)現(xiàn)問(wèn)題，提出問(wèn)題,解決問(wèn)題，從不足之處出發(fā),在不斷學(xué)習(xí)中提高自己.兩周的課程設(shè)計(jì)很短暫,但其間的內(nèi)容是很充實(shí)的,在其中我學(xué)習(xí)到了很多平時(shí)書本中無(wú)法學(xué)到的東西,積累了經(jīng)驗(yàn),鍛煉了自己分析問(wèn)題，解決問(wèn)題的能力，并學(xué)會(huì)了如何將所學(xué)的各課知識(shí)融會(huì),組織起來(lái)進(jìn)行學(xué)習(xí)，總而言之這兩周中我學(xué)到很多,受益匪淺。參考文獻(xiàn)1.嚴(yán)蔚敏，吳偉民。《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》.清華大學(xué)出版社.2.嚴(yán)蔚敏，吳偉民.《數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版)》。清華大學(xué)出版社。3．《ＤＡTASTＲUCTＵREWITHC++》.ＷｉｌliａmForｄ，ＷilｌｉamTｏpp.清華大學(xué)出版社(影印版)．４．譚浩強(qiáng).《ｃ語(yǔ)言程序設(shè)計(jì)》.清華大學(xué)出版社.致謝這次的課程設(shè)計(jì)，我們兩人一個(gè)小組去完成我們自己的課程，但是還是得到了來(lái)自很多方面的幫助。在此首先要感謝學(xué)院提供給我這次實(shí)踐的機(jī)會(huì),讓我們有機(jī)會(huì)貼近現(xiàn)實(shí)，感受成功的喜悅；其次要感謝實(shí)驗(yàn)機(jī)房的老師提供優(yōu)良的實(shí)驗(yàn)設(shè)備供我們做課設(shè)，正是這種良好的課設(shè)環(huán)境讓我們整個(gè)課設(shè)過(guò)程心情都非常愉快.再次要感謝指導(dǎo)老師們的辛勤指導(dǎo)，每當(dāng)我們遇到疑難問(wèn)題時(shí),是他們一次次不厭其煩的解釋和悉心的指導(dǎo),我們才能闖過(guò)一個(gè)個(gè)難關(guān),到達(dá)勝利的彼岸,是他們給我們提供了一次寶貴的檢驗(yàn)自己機(jī)會(huì).最后也要感謝同學(xué)們的幫助，有了他們的支持使我遇到任何困難都不是一個(gè)人在戰(zhàn)斗.感謝所有在我課程設(shè)計(jì)過(guò)程中幫助過(guò)我的人!附錄源代碼：#iｎcｌude<stｄio。h〉／/輸入輸出函數(shù)頭文件#include<ｓtdｌiｂ.ｈ＞／／字符串轉(zhuǎn)短整形函數(shù)的頭文件１0１40219//tｙpedefｓｔrｕctLNodｅ/／定義單循環(huán)鏈表中節(jié)點(diǎn)的結(jié)構(gòu){ ｉnｔnuｍ；／/編號(hào)?intpwd;/／pａssword?strucｔLNode＊next；//指向下一結(jié)點(diǎn)的指針}LNoｄｅ;/＊構(gòu)造結(jié)點(diǎn)*/LＮｏｄe*ｃreatｅNode(intｍ_ｎum,inｔm_pwd）{ LNｏｄe*p;?ｐ＝(LNode＊)maｌlｏｃ(ｓiｚeｏf（ＬN(yùn)ode));//生成一個(gè)結(jié)點(diǎn) p—〉nｕｍ＝m_num;//把實(shí)參賦給相應(yīng)的數(shù)據(jù)域?p－>ｐwd＝m＿ｐwｄ； p-〉next=NＵLL；//指針域?yàn)榭?rｅtuｒnｐ;}/**創(chuàng)建循環(huán)鏈表＊＊/voidcｒeatｅLｉsｔ（LNode**ppHead,intn）{/*創(chuàng)建單向循環(huán)鏈表pｐHｅad，人數(shù)個(gè)數(shù)為n，并輸入每個(gè)人的密碼值,若建立失敗則生成頭結(jié)點(diǎn)，讓cｕr指向他,若建立成功則插入結(jié)點(diǎn)P，cuｒ指向的數(shù)據(jù)元素為p，后續(xù)為”空"的節(jié)點(diǎn)，再把P插入循環(huán)鏈表ppHeaｄ中＊/ ｉｎti，m_pｗd;?ＬN(yùn)odｅ＊p,*ｃur;//cuｒ：浮標(biāo)指針 for（ｉ=１;i〈=n；i＋＋)?{ ｐrintf(”輸入第%d個(gè)人的密碼:"，i); ｓｃaｎf(”%d”，＆m_pwd);//輸入持有密碼 ?p=crｅａt(yī)eNode(i，m＿pwｄ）；//調(diào)用構(gòu)造結(jié)點(diǎn)函數(shù)? if（*ppHead==ＮULＬ)/／如果頭結(jié)點(diǎn)為空??{???＊pｐHead=cuｒ＝p;//生成頭結(jié)點(diǎn),讓cｕr指向他?? cur—〉next=*ｐpHead;/／cuｒ的指針域指向自身 }??elsｅ//如果不為空,則插入結(jié)點(diǎn) ?｛ ?p—〉next=cuｒ—〉next； ?cur—〉nexｔ=p；? cur=p；//ｃuｒ指向新插入結(jié)點(diǎn)???｝?｝ prinｔf(”完成創(chuàng)建?。躰");／／提示鏈表創(chuàng)建完成｝/＊出隊(duì)處理*/vｏｉdjoｓe（ＬN(yùn)ｏde＊pｐＨeaｄ,ｉｎtm_pwd){／*p指向要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，ppHeaｄ指向要?jiǎng)h除的節(jié)點(diǎn)，使ｐ=ｐpHeaｄ,ppHead再指向要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，使p和ppHｅad鏈接,輸出p指向節(jié)點(diǎn)的編號(hào)和密碼值，釋放pｐHead，如此循環(huán),直至把所有節(jié)點(diǎn)都打印和刪除為止!＊/?inti，ｊ； LNｏde*p,＊p＿ｄel;/／定義指針變量 fｏr(i=1；p!=pｐHead;ｉ++){ ?fｏr(j=１;j<m_pwd;++j）{?? p=ｐpHead；//ｐ賦值為ppHｅａd，p指向要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)???ppHead＝ppＨeaｄ—>next;/／ppHｅad指向下一個(gè)元素 ?} p-〉next=ｐpHeaｄ—〉nｅxt;／/ｐ結(jié)點(diǎn)與頭結(jié)點(diǎn)鏈接? i=ppHeaｄ—〉ｐwｄ；/／i賦值為pｐＨｅａd—〉pwd j=ｐpHeａd—〉num；/／ｊ賦值為ｐpHead－〉num，j為要?jiǎng)h除的密碼值 ?ｐrｉntf(”第％d個(gè)人出列,密碼：％d\ｎ”，j,ｉ);??m＿pwｄ=ｐpＨeaｄ—〉ｐwｄ;/／m＿pｗd賦值為ppHｅad-〉ｐwｄ ?ｆrｅe(cuò)（ppHｅad)；//釋放頭結(jié)點(diǎn) ?pｐＨead=p—〉nｅxｔ；//ppＨeａd重新賦值給p-〉neｘt,即釋放前的ｐpＨead—＞pｗd指針//刪除報(bào)數(shù)結(jié)點(diǎn) } i＝ｐpHｅａd－〉pｗd;//ｉ賦值為ｐpＨead-〉ｐwd?j=pｐHｅａd—〉nuｍ；//ｊ賦值為ppHead-〉num pｒiｎtf（"最后一個(gè)出列是％d號(hào),密碼是:%d＼n",j，i）; fｒeｅ(ppHｅａd)；//釋放頭結(jié)點(diǎn)}voiｄｉｎstruｃtion（）{printｆ（"＊**＊*＊＊******＊**＊＊＊＊＊*＊**＊＊*＊*＊＊*＊*＊****＊**＊*＊**＊＊＊＊＊＊＊＊*****＊**\n”);prｉntf（”約瑟夫環(huán):\n"）;pｒｉｎtf（”編號(hào)為1,２,3，4…,n的ｎ個(gè)人按順時(shí)針?lè)较驀蝗?，每人持有一個(gè)密\n"）；ｐrｉｎtf(”碼(正整數(shù)).一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m,從第一個(gè)人開始\n");pｒinｔf(”按順時(shí)針?lè)较蜃?開始順序報(bào)數(shù)，報(bào)到時(shí)停止.報(bào)m的人出列，將他的密碼\n”);priｎｔf（”m作為新的ｍ值,從他在順時(shí)針?lè)较蛏系南乱蝗碎_始重新從１報(bào)數(shù)，如此下去,＼n”）;printf(”直到所有人全部出列為止。編程打印出列順序．\n”)；prｉnｔf(＂*＊＊*****＊＊＊*＊**＊****＊＊*＊＊****＊**＊*＊*＊*＊＊**＊****＊＊＊**＊*\n");reｔｕrｎ0;｝voｉdmｅnu(){ pｒiｎtｆ(”＊*****＊**＊****＊＊**＊＊＊*＊＊**約瑟夫環(huán)＊*****＊**＊＊＊*＊＊*＊**＊*＊**＊**＊*\n”)； printｆ（”\n")；?pｒｉntｆ（”［１]約瑟夫環(huán)問(wèn)題的闡述\n”)；?ｐｒinｔf(”［2］按要求求解約瑟夫環(huán)\n＂)； pｒiｎtｆ(”[0]退出＼n");?pｒintf（”＊＊＊****＊＊＊＊＊＊**＊*＊＊***＊**＊?dú)g迎使用!***＊*******＊＊＊****＊*＊*＊*＊***＼n”)；｝/＊主函數(shù)模塊*/intｍaｉn（){?intn，ｍ,x;?ＬN(yùn)oｄｅ*ppHeaｄ=NＵLL; ｍｅnｕ（); fｏｒ（；；){ printf(”\n請(qǐng)選擇要執(zhí)行的操作：”）; scａnf("％ｄ”,＆x)；?ｓｙstｅm（”clｓ”);?swｉtcｈ（x)｛ｃase１：? priｎtｆ（"＊＊＊＊＊***＊＊＊*＊＊＊****＊*＊**＊＊*＊＊＊＊***＊＊＊*＊＊****＊＊***＊*＊*＊＊**＊＊***＊＊\n”）；ｐrinｔf（"約瑟夫環(huán):\ｎ");prinｔf(”編號(hào)為1,２，3，4…,n的