約瑟夫環(huán)課程設(shè)計(jì)報(bào)告

沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目：約瑟夫環(huán)院（系）：專業(yè):班級(jí)：學(xué)號(hào):姓名：指導(dǎo)教師：目錄TＯC\o"1—3＂＼h\ｚ＼uHYPEＲＬIＮＫ\l"_Tｏc3４5５96９62"1課程設(shè)計(jì)介紹?ＰＡＧERＥF_Toc3４55９６9６2\h1ＨYPERLINＫ\ｌ＂_Ｔoc34559６9６３＂1.1課程設(shè)計(jì)內(nèi)容?PＡGEREF_Tｏc345596９６3\ｈ1ＨYPERLＩＮK\l”_Ｔoc３45596964”1.2課程設(shè)計(jì)要求 PAGEREF_Toｃ345596９6４\ｈ1ＨＹPEＲLIＮＫ＼l＂_Ｔoc34５5969６5"2課程設(shè)計(jì)原理 PAＧEREF_Toc34５５9６９65\h2HYPERLIＮK\l"_Ｔoc34559６966"2．1課設(shè)題目粗略分析 ＰAGＥREF_Toｃ345５96９66\ｈ２HYＰERLINK\ｌ”＿Ｔｏｃ３455９６967＂2。２原理圖介紹?ＰAGERＥF_Tｏc3４5596967\h2ＨYPERＬINK\ｌ”_Tｏc３4５596968＂2.2．１功能模塊圖（如圖２.1) ５５９69６8\h2ＨＹPERLINK＼l”_Toc3４5５969６9"２.２。2流程圖分析 ＰＡGEREF_Ｔｏc３4559６９６9\h3ＨYPERLＩＮK\ｌ＂＿Toｃ345５9697０”3數(shù)據(jù)結(jié)構(gòu)分析?PAＧＥREF_Tｏｃ34５596970＼h5ＨYPEＲLＩNK\ｌ”_Toc３4559６971"３．１存儲(chǔ)結(jié)構(gòu)?PAＧＥREF_Toc３４5596971\h5HYPERLINK＼l"_Ｔoc3４５59６972＂3．2算法描述 PAGEREF＿Toc３45５96972\h5HYPERLINK\ｌ”_Ｔoc3455９6９73＂4調(diào)試與分析?PAGEREＦ_Toc３45５9６9７3\h6HYPERLIＮK＼l＂＿Ｔｏc３4５596974＂4。１調(diào)試過程?PＡGEREF＿Ｔoｃ３４5596974＼ｈ6HYPＥRＬＩNK\l”_Tｏc34５５96975”4。２程序執(zhí)行過程 ＰAGEREF＿Tｏc3４５5969７5\h６HYＰＥRLIＮK\l”_Toｃ34559６976”參考文獻(xiàn) PAGEREF_Ｔoc3４5596976\h8ＨYＰERLINK附錄(關(guān)鍵部分程序清單）?ＰAGEREF＿Toc3４5596977＼h9１課程設(shè)計(jì)介紹1.1課程設(shè)計(jì)內(nèi)容編號(hào)為1，２，……，ｎ的n個(gè)人按順時(shí)針方向圍坐一圈,每人持有一個(gè)密碼(正整數(shù)）.一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m,從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù),報(bào)ｍ的人出列，將他的密碼作為新的m值，從他的順時(shí)針方向上的下一個(gè)開始重新從1報(bào)數(shù),如此下去,直至所有人全部出列為止，設(shè)計(jì)一個(gè)程序求出出列順序。使用單循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)分析：由題意可以將每個(gè)人看做鏈表上的一個(gè)節(jié)點(diǎn)，每個(gè)人持有的密碼即為每個(gè)節(jié)點(diǎn)所存儲(chǔ)的數(shù)據(jù)；相鄰的人之間存在連結(jié)關(guān)系,即鏈表的兩個(gè)相鄰節(jié)點(diǎn)之間由指針來進(jìn)行關(guān)聯(lián)；最后一個(gè)人和第一個(gè)人也存在連結(jié)關(guān)系，即鏈表的末尾節(jié)點(diǎn)和頭結(jié)點(diǎn)相連構(gòu)成了單循環(huán)鏈表存儲(chǔ)結(jié)構(gòu).執(zhí)行報(bào)數(shù)過程可以看做一個(gè)單獨(dú)指針依次指向每一個(gè)節(jié)點(diǎn)，有人出列即刪除掉鏈表中相應(yīng)的節(jié)點(diǎn)。1。２課程設(shè)計(jì)要求1。參考相應(yīng)的資料，獨(dú)立完成課程設(shè)計(jì)任務(wù)。2。交規(guī)范課程設(shè)計(jì)報(bào)告和軟件代碼。２課程設(shè)計(jì)原理2。1課設(shè)題目粗略分析根據(jù)課設(shè)題目要求，程序應(yīng)該分為兩大部分：1、單循環(huán)鏈表儲(chǔ)存結(jié)構(gòu)的建立:建立所需的單循環(huán)鏈表數(shù)據(jù)存儲(chǔ)結(jié)構(gòu),對(duì)每個(gè)節(jié)點(diǎn)輸入所需的密碼、序號(hào)數(shù)據(jù)并通過指針連接成單循環(huán)鏈表。2、實(shí)現(xiàn)約瑟夫環(huán)數(shù)據(jù)出列順序的算法:依照題目要求按照?qǐng)?bào)數(shù)上限對(duì)節(jié)點(diǎn)進(jìn)行查找和刪除操作，按順序輸出出列的節(jié)點(diǎn)序號(hào),依照每次出列的節(jié)點(diǎn)存儲(chǔ)的密碼修改報(bào)數(shù)上限循環(huán)操作直到全部節(jié)點(diǎn)出列完畢程序運(yùn)行結(jié)束。２。2原理圖介紹2。2．1功能模塊圖（如圖2.1)約約瑟夫環(huán)輸出出列順序建立單循環(huán)鏈表輸出出列順序建立單循環(huán)鏈表圖２．１功能模塊圖2.2．2流程圖分析1。主程序圖，如圖２．2：首先建立單循環(huán)鏈表作為數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)并存儲(chǔ)數(shù)據(jù)，然后如果執(zhí)行報(bào)數(shù)。如果鏈表中剩余節(jié)點(diǎn)數(shù)大于１，執(zhí)行報(bào)數(shù)操作,得到節(jié)點(diǎn)的序號(hào)數(shù)據(jù)并輸出;若鏈表中只剩一個(gè)節(jié)點(diǎn)，輸出節(jié)點(diǎn)的序號(hào)數(shù)據(jù)，程序運(yùn)行結(jié)束。開開始構(gòu)建單循環(huán)鏈表；構(gòu)建單循環(huán)鏈表；選定報(bào)數(shù)上限m；鏈鏈表中節(jié)點(diǎn)數(shù)大于1是是報(bào)數(shù)并保存報(bào)數(shù)并保存數(shù)據(jù)刪除節(jié)點(diǎn)否否選定新的報(bào)數(shù)上限選定新的報(bào)數(shù)上限m為刪除節(jié)點(diǎn)儲(chǔ)存的密碼

輸出結(jié)果輸出結(jié)果結(jié)束結(jié)束圖2。2主程序圖2．構(gòu)建單循環(huán)鏈表流程圖，如圖2．3：首先為鏈表存儲(chǔ)空間，然后判斷節(jié)點(diǎn)數(shù)是否達(dá)到上限,若沒有到達(dá)上限，構(gòu)建新節(jié)點(diǎn)；若已到達(dá)上限，將末尾節(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)形成單循環(huán)鏈表并結(jié)束建立鏈表操作。開開始分配存儲(chǔ)空間分配存儲(chǔ)空間節(jié)點(diǎn)數(shù)達(dá)到最大節(jié)點(diǎn)數(shù)達(dá)到最大否否構(gòu)建新節(jié)點(diǎn)構(gòu)建新節(jié)點(diǎn)是是末尾節(jié)點(diǎn)指向表頭末尾節(jié)點(diǎn)指向表頭結(jié)束結(jié)束圖2。3構(gòu)建單循環(huán)鏈表流程圖3數(shù)據(jù)結(jié)構(gòu)分析3。1存儲(chǔ)結(jié)構(gòu)typedeｆｓtructLNｏde｛?iｎtdatａ；//每個(gè)人持有的密碼iｎｔnuｍ；//每個(gè)人的編號(hào) ｓｔruｃｔLNｏｄe＊nexｔ；//指向下一個(gè)節(jié)點(diǎn)的指針｝LNode,＊ＬinｋList；/／定義一個(gè)結(jié)構(gòu)體為一個(gè)持有密碼的人３。２算法描述1。構(gòu)建單循環(huán)鏈表：首先定義結(jié)構(gòu)體節(jié)點(diǎn)指針節(jié)點(diǎn)p，鏈表L,頭指針head。使head指向L的頭結(jié)點(diǎn)，ｐ指向L。對(duì)結(jié)構(gòu)體ｐ的數(shù)據(jù)部分進(jìn)行輸入賦值作為Ｌ的一個(gè)節(jié)點(diǎn)然后向后移一位。循環(huán)此步操作形成單鏈表.最后將末尾節(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)形成單循環(huán)鏈表.２.約瑟夫環(huán)出列操作：首先定義指針Ｊ和K，指針Ｊ指向單循環(huán)鏈表的第一個(gè)節(jié)點(diǎn)，隨機(jī)生成一個(gè)報(bào)數(shù)上限m值.將指針p向后撥m-１次,此時(shí)p所指向節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)即為要出列的節(jié)點(diǎn)，使指針K指向該節(jié)點(diǎn)，將這個(gè)節(jié)點(diǎn)從鏈表中刪除,然后讀取其中存儲(chǔ)的序號(hào)數(shù)據(jù)輸出，讀取其中存儲(chǔ)的密碼作為新的ｍ值.然后繼續(xù)反復(fù)執(zhí)行撥指針ｐ，出列節(jié)點(diǎn)，讀取數(shù)據(jù)操作，直到鏈表中只剩下一個(gè)節(jié)點(diǎn)停止循環(huán)操作,此時(shí)輸出最后一個(gè)節(jié)點(diǎn)中的序號(hào)數(shù)據(jù)完成全部出列操作。4調(diào)試與分析4.1調(diào)試過程調(diào)試過程中出現(xiàn)eｒｒｏrC2０６５：'ranｄ’：ｕｎｄeclarｅｄｉdｅntifiｅr報(bào)錯(cuò),在添加預(yù)處理命令#inclｕｄes“tｉme。h”后正常執(zhí)行；在執(zhí)行過程中出現(xiàn)極大數(shù)據(jù)，發(fā)現(xiàn)構(gòu)建循環(huán)鏈表時(shí)將末尾指針指向了頭結(jié)點(diǎn)，改為指向頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)之后正常運(yùn)行；4。2程序執(zhí)行過程1.如圖4．1所示，當(dāng)輸入人數(shù)為５,每個(gè)人所持有的密碼依次為2、4、6、8、10時(shí)，輸出結(jié)果：出列順序?yàn)椋?-〉3-〉2—>５－＞4,程序運(yùn)行正確。圖４。１當(dāng)人數(shù)為5時(shí)的程序運(yùn)行結(jié)果2．如圖4.2所示,當(dāng)輸入人數(shù)為10，每個(gè)人所持有的密碼依次為9、１、5、７、３、6、８、2、4、1０時(shí)，輸出結(jié)果:出列順序?yàn)椋?—＞10—〉２—>３->9-〉６->1—〉7->5－〉４，程序運(yùn)行正確。圖4．2當(dāng)人數(shù)為1０時(shí)的程序運(yùn)行結(jié)果參考文獻(xiàn)[1］嚴(yán)蔚敏，吳偉民。數(shù)據(jù)結(jié)構(gòu)[Ｍ］．北京：清華大學(xué)出版社，2007.[2]張長(zhǎng)海，陳娟。C程序設(shè)計(jì)[M］．北京:高等教育出版社，20０4.［3］譚浩強(qiáng).C程序設(shè)計(jì)［M］.北京:清華大學(xué)出版社,2005。［４]蘇士華，黃學(xué)俊。數(shù)據(jù)結(jié)構(gòu)解析．習(xí)題。課程設(shè)計(jì)［M].合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，２0０9。［5］張瑞軍.數(shù)據(jù)結(jié)構(gòu)[M]。北京：清華大學(xué)出版社,2００9.［6］劉懷亮．?dāng)?shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)驗(yàn)指導(dǎo)[M］.北京：冶金出版社，200９．［7]王敬華，林萍，張清國(guó)。Ｃ語言程序設(shè)計(jì)教程（第二版)[M].背景：清華大學(xué)出版社,200５。附錄(關(guān)鍵部分程序清單)#incｌｕdｅ<stdafｘ.h>＃ｉnｃｌude〈stｄio。ｈ>#ｉnclude"sｔｄｌib.ｈ”#includｅ<ｓtｒing．h〉＃inｃluｄｅ〈ｍalloc．h＞#iｎclude〈ｍａt(yī)h。h>＃inclｕde”ｔimｅ。h”typedefstrucｔLNode｛?iｎtdata; inｔｎum； sｔrucｔLＮｏde＊nexｔ;｝LＮｏde，*LinkLiｓt；ｖoidｃｒｅatｅｌｉst(ＬinｋＬist＆L,iｎtｎ）｛ ＬinkLｉstp,head; intｉ，a； Ｌ＝(LiｎkList）malloc(sｉzeoｆ（LＮode)）; heaｄ=L；?ｆor（i＝０;ｉ＜ｎ；i++） ｛??ｐ＝(LｉnkList)malｌoｃ(sizeof（LNode));??priｎｔｆ（”請(qǐng)輸入第%d個(gè)人的密碼\n"，i＋1）；??scanf("％ｄ＂，&a）； ?p－＞data=a; p—〉num＝i+1； ?L-〉next=p； ｐ—〉nｅxt=ＮＵLL； L＝p;?}?ｐ->ｎeｘt＝ｈｅad—＞nｅｘt;｝voidmain（）{?ｉnｔn，m，x,k，ｌ；?ＬinkＬistJ,L，K；?ｐrｉnｔｆ（＂請(qǐng)輸入人數(shù)：\n”);?ｓcanf（＂%d”,&n)； creａt(yī)ｅlｉsｔ（L，ｎ）；?J=L;?ｓrａnd（（uｎsigｎed)time(NUＬL））；?ｍ=ｒanｄ（)%ｎ；?ｐriｎtf（"出列順序?yàn)?＂);?for(l=0；l＜n－１；l++）?｛?for(ｋ=０;k＜m－１；k++)? ｛ ?J=J—〉ｎexｔ；??｝ Ｋ＝J-〉nｅxｔ; J—〉next=K-＞ｎeｘｔ;?x＝K-＞ｎｕm;?prinｔｆ(”％d->”，ｘ);??m=K－〉data;??fｒee（K)； ｝?x=J—〉ｎuｍ; pｒintf（”%d\n＂，x）;｝?課程設(shè)計(jì)總結(jié):在老師讓我們?cè)谡n設(shè)題目中選擇一道時(shí)，我看到這道題的條件似乎很有思考的價(jià)值,有點(diǎn)類似于ＡCM比賽題目便選擇了這道題目.在完成了課程設(shè)計(jì)的過程中我并沒有遇到太大的阻礙，一開始就對(duì)題目的理解十分透徹，有很清晰的解題思路，編寫代碼以及調(diào)試程序的過程也十分順利，僅僅遇到了幾個(gè)小的問題，經(jīng)過仔細(xì)的推敲就得以成功解決。整個(gè)過程幾乎不需要借助參考和幫助就輕松獨(dú)立完成。這次課程設(shè)計(jì)對(duì)我的數(shù)據(jù)結(jié)構(gòu)以及C語言學(xué)習(xí)掌握有很大幫助,它讓我對(duì)鏈表這一存儲(chǔ)結(jié)