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