目錄
問題描述
一、基本概念
?1.普通鏈表
2.單向循環(huán)鏈表?
二、問題處理
1.創(chuàng)建鏈表
2.查找
3.刪除
?4.其他
?三.實(shí)驗(yàn)環(huán)節(jié)
四.總結(jié)
問題描述
約瑟夫環(huán)問題的一種描述是：編號為1，2，...，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ù)，如此下去，直到所有人全部出列為止。
基本要求：利用鏈表模擬此過程，按照出列的順序印出各人的編號。
一、基本概念
鏈表是一種鏈?zhǔn)酱鎯Φ木€性表，用一組地址任意的存儲單元存放線性表的數(shù)據(jù)元素，稱存儲單元為一個(gè)結(jié)點(diǎn)（節(jié)點(diǎn)）。單向循環(huán)鏈表與普通鏈表的區(qū)別在于：普通鏈表的最后一個(gè)鏈表的next指向NULL，而單向循環(huán)鏈表的最后一個(gè)節(jié)點(diǎn)的next指向頭結(jié)點(diǎn)
?1.普通鏈表
2.單向循環(huán)鏈表?
?
二、問題處理
1.創(chuàng)建鏈表
首先因?yàn)樘幚韱栴}時(shí)，鏈表元素的訪問并不是從頭開始的，而是采用“接力棒”的方式進(jìn)行訪問。所以應(yīng)該使用不帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表。
代碼如下：?
typedef struct Data
{
int number; // 編號
int code; // 密碼
/*
存放數(shù)據(jù)
*/
} Data;
typedef struct SqList
{
Data data; // 數(shù)據(jù)域
SqList *next; // 指針域
} SqList;
SqList *CreateList(int n) // 生成一個(gè)不帶頭節(jié)點(diǎn)的n個(gè)元素的循環(huán)鏈表
{
if (n < 1) // 輸入的n不合法
{
printf("輸入不合法！");
system("pause");
return NULL;
}
SqList *end = new SqList; // 尾指針
for (int i = 1; i < n + 1; i++)
{
SqList *newNode = (SqList *)malloc(sizeof(SqList *));
if (i == 1) // 鏈表為空時(shí)輸入首元節(jié)點(diǎn)的密碼
{
newNode->next = newNode;
cout << "請輸入成員" << i << "的密碼：";
cin >> newNode->data.code;
newNode->data.number = 1;
end = newNode;
continue;
}
// 鏈表不為空時(shí)輸入newNode數(shù)據(jù)的密碼
cout << "請輸入成員" << i << "的密碼：";
cin >> newNode->data.code;
newNode->data.number = i;
// 尾插法構(gòu)建鏈表
newNode->next = end->next;
end->next = newNode;
end = newNode;
}
return end->next;
}這里需要注意的是因?yàn)榫幪柺怯行虻摹错槙r(shí)針方向，所以采用尾插法。
2.查找
代碼如下：
SqList *ListSearch(SqList *L, int k) // 返回鏈表中的第k個(gè)元素
{
if (!L || k < 1 || k > ListLength(L)) // 鏈表為空或輸入的k值不合法
{
cout << "Error3!" << endl;
system("pause");
exit(0);
}
for (int i = 0; i < k - 1; i++)
{
L = L->next;
}
return L;
}3.刪除
代碼如下：
SqList *ListDelete(SqList *L, int n) // 刪除鏈表L中指定的第n個(gè)元素
{
if (!L || n < 1) // 鏈表為空或刪除位置不合法
{
cout << "Error2!" << endl;
system("pause");
exit(0);
}
SqList *front = L;
SqList *temp = nullptr; // 暫時(shí)儲存要刪除的元素
for (int i = 0; i < n - 1; i++) // 移動指針到要刪除的位置上
{
L = L->next;
}
while (front->next != L) // 尋找要刪除的元素前面的一個(gè)元素
{
front = front->next;
}
front->next = L->next; // 將要刪除的元素移出鏈表
temp = L;
L = L->next;
free(temp); // 釋放內(nèi)存
return L;
}
因?yàn)椴捎谩敖恿Π簟钡姆绞皆L問元素，需要記住被刪除元素的后一個(gè)元素。所以返回指針類型。
?4.其他
代碼如下：
int ListLength(SqList *L) // 返回鏈表長度
{
if (!L) // 輸入空鏈表時(shí)報(bào)錯(cuò)并退出函數(shù)
{
cout << "Error1!";
system("pause");
exit(0);
}
SqList *F_Node = L;
int count = 1; // 因?yàn)椴粠ь^節(jié)點(diǎn)的鏈表，所以非空時(shí)鏈表節(jié)點(diǎn)個(gè)數(shù)至少為1
while (L->next != F_Node)
{
count++;
L = L->next;
}
return count;
}
void ListPrint(SqList *L) // 打印鏈表L中的元素
{
if (!L)
{
return;
}
SqList *Node = L;
do
{
if (Node->next == L)
{
cout << "成員" << Node->data.number << "的密碼：" << Node->data.code << "\t";
return;
}
cout << "成員" << Node->data.number << "的密碼：" << Node->data.code << "\t";
Node = Node->next;
} while (1);
return;
}
?三.實(shí)驗(yàn)環(huán)節(jié)
整體代碼：
/*
整個(gè)實(shí)驗(yàn)重要的步驟就是創(chuàng)建、查找、刪除
*/
#include <iostream>
using namespace std;
typedef struct Data
{
int number; // 編號
int code; // 密碼
/*
存放數(shù)據(jù)
*/
} Data;
typedef struct SqList
{
Data data; // 數(shù)據(jù)域
SqList *next; // 指針域
} SqList;
SqList *CreateList(int n) // 生成一個(gè)不帶頭節(jié)點(diǎn)的n個(gè)元素的循環(huán)鏈表
{
if (n < 1) // 輸入的n不合法
{
printf("輸入不合法！");
system("pause");
return NULL;
}
SqList *end = new SqList; // 尾指針
for (int i = 1; i < n + 1; i++)
{
SqList *newNode = (SqList *)malloc(sizeof(SqList *));
if (i == 1) // 鏈表為空時(shí)輸入首元節(jié)點(diǎn)的密碼
{
newNode->next = newNode;
cout << "請輸入成員" << i << "的密碼：";
cin >> newNode->data.code;
newNode->data.number = 1;
end = newNode;
continue;
}
// 鏈表不為空時(shí)輸入newNode數(shù)據(jù)的密碼
cout << "請輸入成員" << i << "的密碼：";
cin >> newNode->data.code;
newNode->data.number = i;
// 尾插法構(gòu)建鏈表
newNode->next = end->next;
end->next = newNode;
end = newNode;
}
return end->next;
}
int ListLength(SqList *L) // 返回鏈表長度
{
if (!L) // 輸入空鏈表時(shí)報(bào)錯(cuò)并退出函數(shù)
{
cout << "Error1!";
system("pause");
exit(0);
}
SqList *F_Node = L;
int count = 1; // 因?yàn)椴粠ь^節(jié)點(diǎn)的鏈表，所以非空時(shí)鏈表節(jié)點(diǎn)個(gè)數(shù)至少為1
while (L->next != F_Node)
{
count++;
L = L->next;
}
return count;
}
void ListPrint(SqList *L) // 打印鏈表L中的元素
{
if (!L)
{
return;
}
SqList *Node = L;
do
{
if (Node->next == L)
{
cout << "成員" << Node->data.number << "的密碼：" << Node->data.code << "\t";
return;
}
cout << "成員" << Node->data.number << "的密碼：" << Node->data.code << "\t";
Node = Node->next;
} while (1);
}
void ListInsert(SqList *L, Data elem, int a) // 向鏈表L中第a個(gè)位置后面插入數(shù)據(jù)elem
{
for (int i = 0; i < a - 1; i++)
{
L = L->next;
}
if (!L)
{
return;
}
SqList *newNode = new SqList;
newNode->data = elem;
newNode->next = L->next;
L->next = newNode;
}
SqList *ListDelete(SqList *L, int n) // 刪除鏈表L中指定的第n個(gè)元素
{
if (!L || n < 1) // 鏈表為空或刪除位置不合法
{
cout << "Error2!" << endl;
system("pause");
exit(0);
}
SqList *front = L;
SqList *temp = nullptr; // 暫時(shí)儲存要刪除的元素
for (int i = 0; i < n - 1; i++) // 移動指針到要刪除的位置上
{
L = L->next;
}
while (front->next != L) // 尋找要刪除的元素前面的一個(gè)元素
{
front = front->next;
}
front->next = L->next; // 將要刪除的元素移出鏈表
temp = L;
L = L->next;
free(temp); // 釋放內(nèi)存
return L;
}
SqList *ListSearch(SqList *L, int k) // 返回鏈表中的第k個(gè)元素
{
if (!L || k < 1 || k > ListLength(L)) // 鏈表為空或輸入的k值不合法
{
cout << "Error3!" << endl;
system("pause");
exit(0);
}
for (int i = 0; i < k - 1; i++)
{
L = L->next;
}
return L;
}
測試數(shù)據(jù)：m的初值為20；n=7，7個(gè)人的密碼依次為：3，1，7，2，4，8，4
（正確的出列順序應(yīng)為6，1，4，7，2，3，5）。?
測試如下：
#define N 7 // 約瑟問題中的人數(shù)
int main(void)
{
SqList *List = CreateList(N);
int res[N]; // 存放出列順序
int m, i = 0, code = 0;
cout << "請輸入初始的正整數(shù)密碼m" << endl;
cin >> m;
while (ListLength(List) != 1)
{
int k = 0;
m = m % (N - i);
// cout << "當(dāng)前m的值是：" << m << endl;
/*
注意在這里m的取值是[0,N-i-1],
而實(shí)際上m應(yīng)該屬于[1,N-i]。
所以需要對求模后的m進(jìn)行條件判斷
*/
if (m == 0)
{
k = N - i;
}
else
k = m;
code = ListSearch(List, k)->data.code;
res[i] = ListSearch(List, k)->data.number;
List = ListDelete(List, k); // 返回新的起始訪問位置
m = code;
i++;
}
res[i] = ListSearch(List, 1)->data.number; //此時(shí)鏈表中僅有一個(gè)元素
cout << "出列順序?yàn)?";
for (int i = 0; i < N; i++)
cout << res[i] << "\t";
free(List); // 釋放內(nèi)存
return 0;
}?
四.總結(jié)
該問題的難點(diǎn)就在于元素的訪問是采取“接力棒”的方式進(jìn)行訪問，需要對循環(huán)鏈表有足夠的的理解，同時(shí)對密碼的處理上也需要小心。對于本次實(shí)驗(yàn)來說，還有許多能改進(jìn)的地方，比如非法輸入的檢測，可以把它包裝成一個(gè)函數(shù)，這樣處理的話，代碼會更簡潔并且更容易閱讀。文章來源：http://www.zghlxwxcb.cn/news/detail-725042.html
如有錯(cuò)誤，歡迎在評論區(qū)指正。以上內(nèi)容若涉及侵權(quán)請聯(lián)系作者進(jìn)行刪改。?文章來源地址http://www.zghlxwxcb.cn/news/detail-725042.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)-循環(huán)鏈表：處理約瑟夫環(huán)問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
