第一篇：題目：約瑟夫環(huán)問題
數(shù)據(jù)結(jié)構(gòu)上機實驗報告
02090401 12 雒文杰 題目：約瑟夫環(huán)問題
一．問題描述
設(shè)有n個人圍做一圈，現(xiàn)從某個人開始報數(shù)，數(shù)到m的人出列，接著從出列的下一個人開始重新報數(shù)，數(shù)到m的人又出列，如此下去，直到所有人都出列為止。試設(shè)計確定他們的出列次序序列的程序。
二．基本要求
運用循環(huán)單鏈表解決約瑟夫環(huán)問題。
三．算法說明
本程序采用循環(huán)單鏈表的算法來解決約瑟夫環(huán)問題：建立一個循環(huán)單鏈表，按順序查找指定結(jié)點，找到后刪除，最后打印刪除的編號序列。
四 ．源程序清單 #include
/* 人的序號, 密碼*/ struct clist *next;
/* 指向下一個節(jié)點的指針 */ };typedef struct clist cnode;typedef cnode *clink;clink createclist(int *array,int len)
/* 建立循環(huán)鏈表 */ {clink head;clink before;clink new_node;int i;head=(clink)malloc(sizeof(cnode));if(!head)return NULL;head->data=array[0];head->order=1;head->next=NULL;before=head;for(i=1;i if(!new_node) return NULL; new_node->data=array[i]; new_node->order=i+1; new_node->next=NULL; before->next=new_node; before=new_node;} new_node->next=head;return head;} void main(){clink head,ptr;int find,j,i,a,list[n];printf(“Please input 'm'n”);for(i=0;i printf(“n”);} head=createclist(list,n);printf(“input first 's'n”);scanf(“%d”,&a);for(i=1;i head=head->next; ptr=head->next; head->next=ptr->next; find=ptr->data; printf(“order is %dn”,ptr->order); free(ptr); /* 讓最后一個人也出列 */ } } 《數(shù)據(jù)結(jié)構(gòu)》 課程設(shè)計報告 課程名稱： 課程設(shè)計題目：姓名： 院系： 專業(yè)： 年級： 學(xué)號： 指導(dǎo)教師： 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 joseph環(huán) 計算機學(xué)院 2011年12月18日 目 錄 課程設(shè)計的目的………………………………………………………………2 2 需求分析………………………………………………………………………2 3 課程設(shè)計報告內(nèi)容……………………………………………………………3 1、概要設(shè)計……………………………………………………………………3 2、詳細設(shè)計……………………………………………………………………3 3、調(diào)試分析……………………………………………………………………x 4、用戶手冊……………………………………………………………………x 5、測試結(jié)果……………………………………………………………………6 6、程序清單……………………………………………………………………7 4 小結(jié) …………………………………………………………………………10 1、課程設(shè)計的目的 （1）熟練使用C++編寫程序，解決實際問題； （2）了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；（3）初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；（4）提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力； 2、需求分析 1、問題描述： 編號是1，2，……,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設(shè)計一個程序來求出出列順序。 2、要求： 利用不帶表頭結(jié)點的單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個人的編號。 3、測試數(shù)據(jù)： m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？ 輸出形式：建立一個輸出函數(shù)，將正確的輸出序列 3、課程設(shè)計報告內(nèi)容 概要設(shè)計： 在理解了題目后，我先想到的是我們所學(xué)的單鏈表，利用單鏈表先建立循環(huán)鏈表進行存貯，建立完循環(huán)鏈表后，我將所要編寫的函數(shù)分為了兩塊，一塊是經(jīng)過學(xué)過的單鏈表改編的循環(huán)鏈表的基本操作函數(shù)，還有一塊是運行約瑟夫環(huán)的函數(shù)。 詳細設(shè)計： 我先建立一個結(jié)構(gòu)體，與單鏈表一樣，只是多了一個存密碼的code域 struct LinkNode { int data; //順序 int code; //密碼 LinkNode *next; };建立一個類LinkList ,包含的函數(shù)： LinkList(); //構(gòu)造函數(shù) void Creat(const int); //創(chuàng)建循環(huán)鏈表 int Delete(LinkNode*); //刪除報到數(shù)的結(jié)點 int Joseph(int); // 約瑟夫環(huán) 私有成員是 LinkNode* head; //指向第一個結(jié)點的指針 LinkNode* elem; // 同上 int len; //長度 我定義了一個elem指針是為了約瑟夫環(huán)里運行方便，elem只在約瑟夫環(huán)這個函數(shù)里用到，其他函數(shù)沒有特別大的用處。 構(gòu)造函數(shù)與書上的沒什么大差別，創(chuàng)建循環(huán)鏈表時，要考慮幾個問題，一個是題目要求是不帶頭結(jié)點，所以head指針直接指向了第一個結(jié)點，我在創(chuàng)建鏈表時把第一個結(jié)點初始化data為1，表明這個結(jié)點是第一個結(jié)點。具體如下： void LinkList::Creat(const int number) //number為結(jié)點個數(shù)，也就是參與的人數(shù) { if(number==1) //只有一個人的情況 { head=elem=new LinkNode; head->data=1; cout<<“請輸入密碼:”< cin>>head->code; head->next=head;} else { head=elem=new LinkNode; head->data=1; cout<<“請依次輸入各個密碼:”< cin>>head->code;LinkNode*q=head; q=head; for(int i=1;i //將每個結(jié)點鏈接上，在鏈接時填入密碼 { LinkNode*p=new LinkNode; p->data=i+1; cin>>p->code; q->next=p; q=p;} q->next=head; //構(gòu)成循環(huán)鏈表 } len=number;} 在構(gòu)建約瑟夫環(huán)的執(zhí)行函數(shù)時，我首先考慮了遞歸調(diào)用的函數(shù)，原本的這個程序的所有的都定為elemtype類型的，雖然編譯沒出錯，但是在連接時發(fā)生了錯誤，在老師的指導(dǎo)下改成了具體的int型。int LinkList::Joseph(int m){ if(len>1){ LinkNode *q;if(m==1) //在初始報數(shù)為1的情況下 { q=elem;int a=q->code; //將選中的結(jié)點的密碼記錄在a中 elem=elem->next;cout< //用已經(jīng)刪除的結(jié)點的存的密碼作為下一次循環(huán)的報數(shù)值 } else //一般情況下 { for(int i=1;i elem=elem->next;//找到需要出列的結(jié)點 q=elem;elem=elem->next; //此處的elem指針指向要刪除的結(jié)點的下一個結(jié)點，下 次遞歸調(diào)用時從這里開始向下循環(huán)報數(shù) int a=q->code; cout< //在只有一個結(jié)點的情況下 cout< 最后還有一個Delete函數(shù)，在刪除結(jié)點的時候要考慮幾個特殊情況，頭尾結(jié)點。刪除第一個結(jié)點時，需要將head指針下移，尾結(jié)點的next也要指向第二個結(jié)點；刪除尾結(jié)點時，要將尾結(jié)點前的結(jié)點與第一個結(jié)點相連。在設(shè)計這個函數(shù)時，我只考慮了當len大于1的情況，在只剩下一個結(jié)點時，不必要刪除，直接輸出data的值即可（在約瑟夫函數(shù)中有寫）。具體函數(shù)如下： int LinkList::Delete(LinkNode *a) { if(len>1)//只考慮長度大于1的情況 { if(head==a){ int out=head->data;LinkNode* q=head; while(q->next!=head){ q=q->next;} q->next=head->next;head=head->next;delete a;len--; //用len記錄刪除后的循環(huán)鏈表的長度 return out;} else { LinkNode* q=head;int out=a->data; while(q->next!=a){ q=q->next;} if(a->next=head).//刪除的是尾結(jié)點時（不知道為什么我寫程序里總是編譯出現(xiàn)錯誤） { q->next=head; //重新鏈接 delete a; len--; return out;} else { q->next=a->next; delete a; len--; return out; } } } } 5、測試結(jié)果： 程序清單： #include int data; int code; LinkNode *next;}; class LinkList { public: LinkList(); void Creat(const int); //~LinkList(); int Delete(LinkNode*); int Joseph(int); private: LinkNode* head; LinkNode* elem; int len; }; LinkList::LinkList() { head=elem=NULL; len=0;} void LinkList::Creat(const int number) { if(number==1){ head=elem=new LinkNode; head->data=1; cout<<“請輸入密碼:”< cin>>head->code; head->next=head;} else { head=elem=new LinkNode; head->data=1; cout<<“請依次輸入各個密碼:”< cin>>head->code; LinkNode*q=head; q=head; for(int i=1;i { LinkNode*p=new LinkNode; p->data=i+1; cin>>p->code; q->next=p; q=p; } q->next=head;} len=number;} int LinkList::Delete(LinkNode *a) { if(len>1) { if(head==a) { int out=head->data; LinkNode* q=head; while(q->next!=head) { q=q->next; } q->next=head->next; head=head->next; delete a; len--; return out; } else { LinkNode* q=head; int out=a->data; while(q->next!=a) { q=q->next; } q->next=a->next; delete a; len--; return out; } } } int LinkList::Joseph(int m){ if(len>1){ LinkNode *q; if(m==1) { q=elem; int a=q->code; elem=elem->next; cout< Joseph(a); } else { for(int i=1;i elem=elem->next; q=elem; elem=elem->next; int a=q->code; cout< Joseph(a); } } else cout< int main(){ int num,code; cout<<“請輸入人數(shù): ”; cin>>num; LinkList L; L.Creat(num); cout<<“請輸入第一個上限數(shù): ”; cin>>code; cout<<“出列順序:”< L.Joseph(code); return 0;} 4、小結(jié) 一、這次課程設(shè)計的心得體會通過實踐我的收獲如下： 一開始接觸數(shù)據(jù)結(jié)構(gòu)課程設(shè)計真的挺難的，好多都不會，不是邏輯方面的問題，而是不具備動手能力，腦子里總有一團火，比如對于這個題目，一開始有很多的想法，想到了從邏輯上怎么實現(xiàn)他，要編寫哪些程序，但是一到需要編寫了就開始為難了，可以說是幾乎不知道從哪里入手，參考了書本里的程序，仿照他的結(jié)構(gòu)一步一步做下來，現(xiàn)在對于單鏈表的各種操作已經(jīng)算是比較熟練了，讓我知道光有理論知識還遠遠不夠，需要多動手，寫的多了自然就能手到擒來。 二、根據(jù)我在實習(xí)中遇到得問題，我將在以后的學(xué)習(xí)過程中注意以下幾點： 1、認真上好專業(yè)實驗課，多在實踐中鍛煉自己。 2、寫程序的過程中要考慮周到，嚴密。 3、在做設(shè)計的時候要有信心，有耐心，切勿浮躁。 4、認真的學(xué)習(xí)課本知識，掌握課本中的知識點，并在此基礎(chǔ)上學(xué)會靈活運用。 5、在課余時間里多寫程序，熟練掌握在調(diào)試程序的過程中所遇到的常見錯誤，以便能節(jié)省調(diào)試程序的時間。 實習(xí)報告 題目:約瑟夫環(huán) 班級：08052712學(xué)號: 08052211姓名: 葛俊峰 一、需求分析 1.本演示程序中，編號為1，2，?，n的n個人按順時針方向圍坐一圈，每個人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，如此下去，直到所有人全部出列為止。 2.演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入相應(yīng)數(shù)據(jù)（即總?cè)藬?shù)，m的值，每個人所持的密碼），運算結(jié)果顯示在其后。 3.程序執(zhí)行的命令包括： （1）構(gòu)造鏈表；（2）輸入數(shù)據(jù)；（3）執(zhí)行報數(shù)，儲存出列人的序號，刪除出列人的信息以及把出列人的密碼賦給m；（4）結(jié)束。 4.測試數(shù)據(jù)： m的初始值為20；n＝7，7個人的密碼依次為：3，1，7，2，4，8，4，首先m值為6，則這正確的出列順序為6，1，4，7，2，3，5。 二、概要設(shè)計 為了實現(xiàn)上述操作，應(yīng)以單向循環(huán)鏈表為存儲結(jié)構(gòu)。為此，需要1個抽象數(shù)據(jù)類型：線性表。 1.線性表的抽象數(shù)據(jù)類型為： ADT List{ 數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,?，n,n≥0} 數(shù)據(jù)關(guān)系：R1={ 基本操作： InitList(&L) 操作結(jié)果：構(gòu)造一個空的線性表L。 }ADT List 2.本程序包括三個模塊: 1）主程序模塊： void main（）{ 初始化； 輸入數(shù)據(jù)； 函數(shù)調(diào)用； } 2）構(gòu)造鏈表并輸入每個人信息的模塊-----實現(xiàn)線性表的抽象數(shù)據(jù)類型； 3）運行模塊-----模擬約瑟夫環(huán)依次出列； 各模塊之間調(diào)用關(guān)系如下： 主程序模塊 ↓ 構(gòu)造鏈表并輸入每個人信息的模塊 ↓ 運行模塊 三、詳細設(shè)計 1.結(jié)點類型和指針類型 typedef struct Node{ int num; int password; struct Node *next; }LNode,*LinkList;//結(jié)點類型,指針類型 Status MakeNode（LinkList &p，Elem Type e） { //分配由p指向的數(shù)據(jù)元素為e、后繼為“空”的特點，并返回TRUE，//若分配失敗，則返回FALSE P=(LinkType)malloc（sizeof（NodeType））； If（！p）return FALSE； p->data=e；p->next=null；return TRUE； } viod Free Node（Link Type &p） { //釋放p所指結(jié)點 } 2.主函數(shù)和其他函數(shù) int main() { //主函數(shù) LinkList L = NULL; LinkList s ,r; int n,i,j,m;//初始化 printf(“請輸入人數(shù)nn”); scanf(“%d”,&n); printf(“請輸入mn”); scanf(“%d”,&m); printf(“請依次輸入每個人的密碼n”);//輸入數(shù)據(jù) CreatList(L,s,r,n);//創(chuàng)建鏈表run(L,n,m);//模擬約瑟夫環(huán)并輸出 return 0; }//main void CreatList(LinkList &L,LinkList &s,LinkList &r,int n) { //創(chuàng)建鏈表 int i=1; s=(LNode*)malloc(sizeof(LNode));//分配空間 scanf(“%d”,&s->password);//輸入密碼 s->num = i;//序號為i if(L==NULL) L=s; else r->next=s; r=s;//為下次連接做準備 for(i=2;i<=n;i++) { s=(LNode*)malloc(sizeof(LNode));//分配空間 scanf(“%d”,&s->password); s->num = i; r->next=s;//連接到下個結(jié)點 r=s;//為下次連接做準備 } r->next = L;//閉合L = r; } // void CreatList void run(LinkList &L,int n,int m) { //模擬約瑟夫環(huán)并輸出 LinkList s,r; int i,j; for(i = 0;i < n;i ++) { for(j = 1;j < m;j ++) L = L->next;//報數(shù) s = L->next; r = s->next; printf(“%dn”,s->num);//輸出序號 m = s->password; L->next = r; free(s);//刪除結(jié)點 } }//run 3.函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu): main ↓↓ CreatListrun ↓↓ Make NodeFree Node 四、調(diào)試分析 1.剛開始由于使用頭結(jié)點,使得程序不符合要求。 2.在寫程序時忽略了一些變量參數(shù)的標識“&”,使調(diào)試程序費時不少。今后應(yīng)重視確定參數(shù)的變量和賦值屬性的區(qū)分和標識。 3.本程序模塊劃分比較簡單且容易看懂，但頭指針賦空不太合理。 4.本實習(xí)作業(yè)采用數(shù)據(jù)抽象的設(shè)計方法，將程序劃分為3個層次，使得設(shè)計時思路清晰，實現(xiàn)調(diào)試順利 五、用戶手冊 1.本程序運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為約瑟夫環(huán).exe。 2． 進入演示程序后出現(xiàn)提示信息： “請輸入人數(shù)n” 輸入后，出現(xiàn)提示信息： “請輸入m” 輸入后，出現(xiàn)提示信息： “請依次輸入每個人的密碼” 輸入后，顯示相應(yīng)的結(jié)果。 /*功能：約瑟夫變種問題 假如有k個好人，和k個壞人，所有人站成一圈，前K個人是好人，后K個人是壞人，編寫程序計算一個最小的m,使k個壞人都被處死，而不處決任何好人。 本程序基于韓順平Java約瑟夫環(huán)程序！ */ public class Demo { public static void main(String[] args) { int m=ysminm(2);//該圈中有2個好人和2個壞人 System.out.println(“將壞人殺死的最小的m=”+m); } //找出將k個壞人殺死的最小m public static int ysminm(int k) { int temp=1; int m=1; while(true) { CycLink cyclink=new CycLink(); cyclink.setLen(2*k);//設(shè)置環(huán)為k個好人和k個壞人 cyclink.createLink(); cyclink.setK(temp); cyclink.setM(m); cyclink.show(); if(cyclink.play()) { return m; } m++; } } } class Child { int no; Child nextchild=null; public Child(int no){ //給一個編號this.no=no;} } //環(huán)形鏈表 class CycLink { //先定義一個指向鏈表第一個人的引用 Child firstChild=null;Child temp=null;int len=0;//表示共有幾個人 int k=0;//表示從第幾個開始數(shù) int m=0;//表示第幾個人別殺死//設(shè)置鏈表大小 public void setLen(int len){this.len=len;} //設(shè)置從第幾個人開始數(shù)數(shù) public void setK(int k){this.k=k;}public void setM(int m){this.m=m;}//開始play，如果找到m則返回true,否則返回false.public boolean play(){int lenTemp=len;Child temp=this.firstChild;//1.先找到開始數(shù)數(shù)的人 for(int i=1;i }temp=temp.nextchild;} //找到要殺死的前一個人 Child temp2=temp;while(temp2.nextchild!= temp){temp2=temp2.nextchild;} //3.將數(shù)到m的人殺死，推出圈 temp2.nextchild=temp.nextchild;// 如果殺死的人是好人，就表示m設(shè)置的不正確，返回false if(temp.no>=1&&temp.no<=lenTemp/2){return false;} //讓temp指向下一個數(shù)數(shù)的人 System.out.println(“第”+temp.no+“ 個人出局”);temp=temp.nextchild;this.len--;} //運行到此處表明殺死的都是壞人，所以返回true.return true;//初始化環(huán)形鏈表 public void createLink(){for(int i=1;i<=len;i++){if(i==1){//創(chuàng)建第一個人Child ch=new Child(i);this.firstChild=ch;this.temp=ch;}else{//創(chuàng)建最后一個人if(i==len){//繼續(xù)創(chuàng)建人Child ch=new Child(i);temp.nextchild=ch;temp=ch; }}}} } else {} //繼續(xù)創(chuàng)建人 Child ch=new Child(i);temp.nextchild=ch;temp=ch;//打印該環(huán)形鏈表 public void show(){} //定義一個跑龍?zhí)椎?Child temp=this.firstChild;do{System.out.println(temp.no);temp=temp.nextchild;}while(temp!= this.firstChild); #include typedef struct LNode { //數(shù)據(jù)域 int cipher; //密碼 int number; //編號 struct LNode *next; //指針域 }LNode,*LinkList; void InitList(LinkList &L) //創(chuàng)建一個只有頭結(jié)點鏈表 { L =(LinkList)malloc(sizeof(LNode));if(!L){ exit(1); printf(“/n/nError!/n/n”);} L->next = L;} void CreateList(int n,LinkList &L)//初始化循環(huán)單鏈表 { LinkList p,q;q = L;printf(“分別輸入每個人的密碼：”);for(int i = 1;i <= n;i++){ int k; scanf(“%d”,&k); if(k <= 0) { printf(“nn密碼有誤!nn”); exit(1); } p =(LinkList)malloc(sizeof(LNode)); if(!p) { exit(1); printf(“/n/nError!/n/n”); } p->cipher = k; p->number = i; L->next = p; L = p;} L->next = q->next;free(q);} void PrintList(int x,int n,LinkList L)//輸出出列順序 { LinkList p,q;p = L;for(int i = 1;i <= n;i++){ for(int j = 1;j < x;j++) p = p->next; q = p->next; x = q->cipher; printf(“%d ”,q->number); p->next = q->next; free(q);} } int main(){ printf(“=============約瑟夫環(huán)==============nnn”); int n,x;LinkList L;L = NULL;InitList(L); //構(gòu)造空鏈表 printf(“輸入初始密碼：”);scanf(“%d”,&x); //初始密碼為x printf(“n”);printf(“輸入?yún)⑴c總?cè)藬?shù)：”);scanf(“%d”,&n); //總共的人數(shù)n printf(“n”);CreateList(n,L); //建立好一個約瑟夫環(huán) printf(“nnn===================================nn”); printf(“出列編號為：”);PrintList(x,n,L); //輸出出列順序 printf(“nn”);return 0;}第二篇：約瑟夫環(huán)課程設(shè)計實驗報告
第三篇：數(shù)據(jù)結(jié)構(gòu)報告--約瑟夫環(huán)范文
第四篇：約瑟夫環(huán)變種問題——k個好人k個壞人
第五篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計——約瑟夫環(huán)報告(含代碼)
點擊咨詢 