實(shí)習(xí)報(bào)告-約瑟夫環(huán)

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告課程名稱：《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)課程設(shè)計(jì)題目：約瑟夫環(huán)姓名：院系：計(jì)算機(jī)學(xué)院專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)年級(jí)：學(xué)號(hào)：指導(dǎo)教師：課程設(shè)計(jì)的目的1.熟練使用C語言編寫程序，解決實(shí)際問題；2.了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；3.掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；4.提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力；二、需求分析以單項(xiàng)循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬約瑟夫環(huán)問題。即編號(hào)為1、2、3…、n的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的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有的人全部出列為止。按出列順序印出各人的編號(hào)。演示程序以用戶與計(jì)算機(jī)的對(duì)話方式執(zhí)行，用戶輸入相應(yīng)的數(shù)據(jù)，輸出結(jié)果顯示在其后。測(cè)試數(shù)據(jù)：n=77個(gè)人的密碼依次為：3,1,7,2,4,8,4；首先m值為6（正確的輸出順序?yàn)椋?,1,4,7,2,3,5）n=55個(gè)人的密碼依次為：1,2,3,4,5首先m值為1（正確的輸出順序?yàn)椋?,2,4,3,5）n=5首先m值為-2（輸入的人數(shù)和初始密碼不能為負(fù)數(shù)!）三、課程設(shè)計(jì)報(bào)告內(nèi)容（一）、概要設(shè)計(jì)為實(shí)現(xiàn)上述程序功能，應(yīng)利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程。單向循環(huán)鏈表的抽象數(shù)據(jù)類型定義為：ADTCircularList{數(shù)據(jù)對(duì)象：D={ai|ai∈LNode,i=1,2,…,n,n≥0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1∈D,i=2,…,n}基本操作：StatusListDelete_L(LinkList&L,intI,ElemType&e)操作結(jié)果：在帶頭結(jié)點(diǎn)的單鏈表L中，刪除第i個(gè)元素，并用e返回其值}本程序中包括的三個(gè)基本模塊：主程序模塊：Voidmain(){初始化；do{接受命令；處理命令；}while(“命令”=”退出”)}線性表模塊：實(shí)現(xiàn)線性表的抽象數(shù)據(jù)結(jié)構(gòu)元素結(jié)構(gòu)單元模塊：定義線性表中每個(gè)元素的結(jié)構(gòu)（二）、詳細(xì)設(shè)計(jì)結(jié)點(diǎn)類型typedefstructLNode{ intdata;//密碼 inti;//編號(hào) structLNode*next;}LNode,*LinkList;用循環(huán)鏈表存儲(chǔ)約瑟夫環(huán)，沒有頭結(jié)點(diǎn)，基本操作函數(shù)如下：intCreateList(LinkList&L,inta[],intn){//創(chuàng)建循環(huán)鏈表結(jié)構(gòu)的約瑟夫環(huán) LinkLists,r; inti; r=L; for(i=1;i<=n;i++) { s=(LinkList)malloc(sizeof(LNode)); s->data=a[i]; s->i=i; if(i==1) { L=s; s->next=s; r=s;//尾指針指向當(dāng)前元素 } else { s->next=r->next; r->next=s; r=s; } } return1;}intListDelete_L(LNode*L){//刪除表中一個(gè)結(jié)點(diǎn) if(L->next==L)//只剩一個(gè)結(jié)點(diǎn) { printf("%d\n",L->i); free(L); return0; } LNode*p; p=L->next;//p指向要?jiǎng)h除元素的下一個(gè)結(jié)點(diǎn) while(p->next!=L) p=p->next; LNode*q=L;//q指向需要被刪除的元素結(jié)點(diǎn) inte=L->i; p->next=L->next; free(q); printf("%d",e); return1;}intFindNode(LinkListL,intx){//查找表中某個(gè)結(jié)點(diǎn) LinkListp=L; LinkListq; for(inti=1;i<x;i++) p=p->next; q=p->next;//下一次循環(huán)的起始位置 x=p->data; if(ListDelete_L(p)) FindNode(q,x); returnp->i;}主函數(shù)：intmain(){ intn,m; LinkListL; printf("請(qǐng)輸入人數(shù)和初始密碼:"); scanf("%d%d",&n,&m); if(n<0||m<0) { printf("輸入的人數(shù)和初始密碼不能為負(fù)數(shù)!\n"); return0; } inta[100]; printf("請(qǐng)輸入每個(gè)人的密碼:"); for(inti=1;i<=n;i++) scanf("%d",&a[i]); if(CreateList(L,a,n)) { printf("\n"); printf("正確的出列順序?yàn)椋?); FindNode(L,m); printf("\n"); } return0;}函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)：mainCreateListFindNodeListDelete_L（三）、調(diào)試分析剛開始時(shí)，忽略了題目要求的沒有頭結(jié)點(diǎn)這一項(xiàng)，沒有把第一個(gè)結(jié)點(diǎn)單獨(dú)拿出來建立，出現(xiàn)了邏輯上的錯(cuò)誤。程序在編譯時(shí)，有很多錯(cuò)誤，主要是指針與引用概念不清導(dǎo)致。查找下一個(gè)時(shí)候采用求余數(shù)的方法，減少了循環(huán)次數(shù)。程序的算法復(fù)雜度為O(n2),不過雖然是C++寫的，但還有很大的面向過程的思想，函數(shù)間的調(diào)用顯得不好。（四）、用戶手冊(cè)本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件名為：JosephC.exe運(yùn)行程序后，需要根據(jù)提示輸入人數(shù)n、初始密碼m，然后根據(jù)提示輸入n個(gè)正整數(shù)，作為這n個(gè)人的密碼，密碼之間用空格隔開。按回車鍵即可得到測(cè)試結(jié)果。本程序的輸入輸出只進(jìn)行一次，即只做一個(gè)案例的處理，如果用戶要輸入第二個(gè)案例，則需要退出并再運(yùn)行本程序。（五）測(cè)試結(jié)果第一組數(shù)據(jù)測(cè)試結(jié)果：請(qǐng)輸入人數(shù)和初始密碼：720請(qǐng)輸入每個(gè)人的密碼：3172484正確的出列順序?yàn)椋?147235第二組數(shù)據(jù)測(cè)試結(jié)果：請(qǐng)輸入人數(shù)和初始密碼:51請(qǐng)輸入每個(gè)人的密碼：12345正確的出列順序?yàn)椋?2435第三組數(shù)據(jù)測(cè)試結(jié)果：請(qǐng)輸入人數(shù)和初始密碼：5-2輸入的人數(shù)和初始密碼不能為負(fù)數(shù)!、程序清單#include<iostream>typedefstructLNode{ intdata;//密碼 inti;//編號(hào) structLNode*next;}LNode,*LinkList;intCreateList(LinkList&L,inta[],intn){ LinkLists,r; inti; r=L; for(i=1;i<=n;i++) { s=(LinkList)malloc(sizeof(LNode)); s->data=a[i]; s->i=i; if(i==1) { L=s; s->next=s; r=s;//尾指針指向當(dāng)前元素 } else { s->next=r->next; r->next=s; r=s; } } return1;}intListDelete_L(LNode*L){ if(L->next==L)//只剩一個(gè)結(jié)點(diǎn) { printf("%d\n",L->i); free(L); return0; } LNode*p; p=L->next;//p指向要?jiǎng)h除元素的下一個(gè)結(jié)點(diǎn) while(p->next!=L) p=p->next; LNode*q=L;//q指向需要被刪除的元素結(jié)點(diǎn) inte=L->i; p->next=L->next; free(q); printf("%d",e); return1;}intFindNode(LinkListL,intx){ LinkListp=L; LinkListq; for(inti=1;i<x;i++) p=p->next; q=p->next;//下一次循環(huán)的起始位置 x=p->data; if(ListDelete_L(p)) FindNode(q,x); returnp->i;}intmain(){ intn,m; LinkListL; printf("請(qǐng)輸入人數(shù)和初始密碼:"); scanf("%d%d",&n,&m); if(n<0||m<0) { printf("輸入的人數(shù)和初始密碼不能為負(fù)數(shù)!\n"); return0; } inta[100]; printf("請(qǐng)輸入每個(gè)人的密碼:"); for(inti=1;i<=n;i++) scanf("%d",&a[i]); if(CreateList(L,a,n)) { printf("\n"); printf("正確的出列順序?yàn)椋?); FindNode(L,m); printf("\n"); } return0;}四、小結(jié)一、這次課程設(shè)計(jì)的心得體會(huì)通過實(shí)踐我的收獲如下：1、鞏固和加深了對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運(yùn)用本課程所學(xué)知識(shí)的能力。2、培養(yǎng)了我選用參考書，查閱手冊(cè)及文獻(xiàn)資料的能力。培養(yǎng)獨(dú)立思考，深入研究，分析問題、解決問題的能力。3、通過實(shí)際編譯系統(tǒng)的分析設(shè)計(jì)、編程調(diào)試，掌握應(yīng)用軟件的分析方法和工程設(shè)計(jì)方法。4、通過課程設(shè)計(jì)，培養(yǎng)了我嚴(yán)肅認(rèn)真的工作作風(fēng)，逐步建立正確的生產(chǎn)觀念、經(jīng)濟(jì)觀念和全局觀念。二、根據(jù)我在實(shí)習(xí)中遇到得問題，我將在以后的學(xué)習(xí)過程中注意以下幾點(diǎn)：1、認(rèn)真上好專業(yè)實(shí)驗(yàn)課，多在實(shí)踐中鍛煉自己。2、寫程序的過程中要考慮周到，嚴(yán)密。3、在做設(shè)計(jì)的時(shí)候要有信心，有耐心，切勿浮躁。4、認(rèn)真的學(xué)習(xí)課本知