實(shí)驗(yàn)作業(yè)一：線性表（鏈表）

1.?用單循環(huán)鏈表解決約瑟夫問題。

問題描述：

一個(gè)旅行社要從n個(gè)旅客中選出一名旅客，為他提供免費(fèi)的環(huán)球旅行服務(wù)。旅行社安排這些旅客圍成一個(gè)圓圈，從帽子中取出一張紙條，用上面寫的正整數(shù)m(<n)作為報(bào)數(shù)值。游戲進(jìn)行時(shí)，從第s個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人被淘汰出列，然后從他順時(shí)針方向上的下一個(gè)人開始重新報(bào)數(shù)，如此下去，直到圓圈中只剩下一個(gè)人，這個(gè)最后的幸存者就是游戲的勝利者，將得到免費(fèi)旅行的獎勵。其中數(shù)據(jù)結(jié)構(gòu)采用單循環(huán)鏈表。

解決方案要求：

輸入?yún)?shù)：n、m、s

輸出參數(shù)：n個(gè)人的淘汰序列

參考樣例：

?

?

代碼：

1 #include "stdlib.h" 2 #include "stdio.h" 3 #include <iostream> 4 using namespace std; 5 6 typedef int datatype; 7 8 typedef struct node { 9 datatype data; 10 struct node *next; 11 }node, *LinkList; 12 13 void Inite(LinkList &first, int n) { 14 first = (node*)malloc(sizeof(node)); //注意此處，不可以直接分配長度為n*sizeof(node)的空間，因?yàn)檫@里只可以給頭節(jié)點(diǎn)分配，如果分配多了也沒用 15 node *p = first, *q; 16 //first->data = 1; 17 //cout << first->data; 18 for(int i = 0; i < n - 1; i++) { 19 p->data = i + 1; 20 q = (node*)malloc(sizeof(node)); 21 //cout << "Number " << i+1 << " p->data " << p->data << endl; 22 p -> next = q; 23 p = q; 24 } 25 p -> data = n; 26 p -> next = first; 27 //cout << "Number " << n << " p->data " << p->data << endl; 28 } 29 30 void Josephus(LinkList &first, int m, int s) { 31 cout << "******** Solve Josephus Problem ********" << endl; 32 33 node *nowPoint = first, *prePoint = first; 34 if (s > 1) { 35 for (int i = 0; i < s - 1; i++) { 36 prePoint = nowPoint; 37 nowPoint = nowPoint -> next; 38 //cout << "NUMBER " << i + 1 << " prePoint " << prePoint->data << endl; 39 //cout << "NUMBER " << i + 1 << " nowPoint " << nowPoint->data << endl; 40 } 41 } 42 else if(s == 1) { 43 while(prePoint -> next != nowPoint) 44 prePoint = prePoint -> next; 45 } 46 else { 47 printf("PLEASE ENTER AN S WHICH BIGGER THAN 4 !"); 48 } 49 while (nowPoint -> next != nowPoint) { 50 for (int i = 0; i < m - 1; i++) { 51 prePoint = nowPoint; 52 nowPoint = nowPoint -> next; 53 //cout << "NUMBER " << i + 1 << " prePoint " << prePoint->data << endl; 54 //cout << "NUMBER " << i + 1 << " nowPoint " << nowPoint->data << endl; 55 } 56 prePoint -> next = nowPoint -> next; 57 cout << "Number " << nowPoint -> data << " is out" << endl; 58 free(nowPoint); 59 nowPoint = prePoint -> next; 60 } 61 cout << "Number " << nowPoint -> data << " is out" << endl; 62 cout << "****************** END *****************" << endl; 63 } 64 65 int main() { 66 int n, m, s; 67 LinkList first; 68 69 cout << "Enter n:" << endl; 70 cin >> n; 71 cout << "Enter m:" << endl; 72 cin >> m; 73 cout << "Enter s:" << endl; 74 cin >> s; 75 76 Inite(first, n); 77 Josephus(first, m, s); 78 79 return 0; 80 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/QingHuan/p/4947244.html

總結(jié)

以上是生活随笔為你收集整理的【数据结构作业—01】用单循环链表解决约瑟夫问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。