溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
循環鏈表的任意元素都有一個前驅和一個后繼，所有數據元素在關系上構成邏輯上的環。
循環鏈表是一種特殊的單鏈表，尾結點的指針指向首結點的地址。
循環鏈表的邏輯關系圖如下：
循環鏈表的設計實現要點：
A、通過模板定義CircleList，繼承自LinkedList
B、定義連接鏈表首尾的內部函數
C、實現首元素的插入和刪除操作
D、重寫清空操作和遍歷操作
A、插入位置為0時，頭結點和尾結點均指向新結點，新結點作為首結點插入鏈表。
B、刪除位置為0時，頭結點和尾結點指向位置為1的結點，刪除銷毀首結點
Node* last()
{
return this->position(this->m_length - 1)->next;
}void lastToFirst()
{
last()->next = this->m_header.next;
} template <typename T>
class CircleList:public LinkedList<T>
{
protected:
typedef typename LinkedList<T>::Node Node;
//尾結點
Node* last()
{
return this->position(this->m_length - 1)->next;
}
//鏈接最后一個結點和首結點
void lastToFirst()
{
last()->next = this->m_header.next;
}
int mod(int index)const
{
return (this->m_length == 0)?0:(index % this->m_length);
}
public:
bool insert(int index, const T& value)
{
bool ret = true;
//計算插入結點的位置
index = index % (this->m_length + 1);
ret = LinkedList<T>::insert(index, value);
//如果插入位置為0
if(ret && (index == 0))
{
lastToFirst();//連接首尾結點
}
return ret;
}
bool insert(const T& value)
{
return insert(this->m_length, value);
}
bool remove(int index)
{
bool ret = true;
index = mod(index);
//刪除結點為首結點
if(index == 0)
{
//首結點
Node* toDel = this->m_header.next;
if(toDel)
{
//將頭結點的下一個結點指向首結點的下一個結點
this->m_header.next = toDel->next;
this->m_length--;//鏈表長度減1
//鏈表不為空
if(this->m_length > 0)
{
lastToFirst();//連接新的首結點與尾結點
if(this->m_current == toDel)
{
this->m_current = toDel->next;
}
}
else
{
//鏈表為空，置空
this->m_header.next = NULL;
this->m_current = NULL;
}
//銷毀要刪除的結點
this->destroy(toDel);
}
else
{
ret = false;
}
}
else
{
//刪除的結點不是首結點，按單鏈表處理
ret = LinkedList<T>::remove(index);
}
return ret;
}
bool set(int index, const T& value)
{
index = mod(index);
return LinkedList<T>::set(index, value);
}
T get(int index)const
{
index = mod(index);
return LinkedList<T>::get(index);
}
bool get(int index, T& value)
{
index = mod(index);
return LinkedList<T>::get(index, value);
}
int find(const T& value)
{
int ret = -1;
//首結點
Node* current = this->m_header.next;
//遍歷鏈表查找數據元素
for(int i = 0; i < this->length(); i++)
{
if(current->value == value)
{
ret = i;
break;
}
//移動游標
current = current->next;
}
return ret;
}
void clear()
{
//刪除鏈表中結點至頭結點
while(this->m_length > 1)
{
remove(1);
}
//刪除首結點
if(this->m_length == 1)
{
Node* toDel = this->m_header.next;
this->m_header.next = NULL;
this->m_current = NULL;
this->m_length = 0;
this->destroy(toDel);
}
}
bool move(int pos, int step)
{
pos = mod(pos);
return LinkedList<T>::move(pos, step);
}
bool end()
{
return (this->m_length == 0) || (this->m_current == NULL);
}
~CircleList()
{
clear();
}
};Josephu約瑟夫環問題為：設編號為1，2，… n的n個人圍坐一圈，約定編號為k（1<=k<=n）的人從1開始報數，數到m 的那個人出列，它的下一位又從1開始報數，數到m的那個人又出列，依次類推，直到所有人出列為止，由此產生一個出隊編號的序列。
//約瑟夫環
void jusephus(int n, int k, int m)
{
//構建循環鏈表
CircleList<int> cl;
for(int i = 1; i <= n; i++)
{
cl.insert(i);
}
//移動當前結點到位置k-1，設置步長為m-1
cl.move(k-1, m-1);
while(cl.length() > 0)
{
cl.next();//移動到目標位置
cout << cl.current() << endl;
//刪除目標位置結點
cl.remove(cl.find(cl.current()));
}
}當編號為1開始時可以使用遞歸
假設n=10,m=3
1 2 3 4 5 6 7 8 9 10 m=3
第一次有人出列后：1 2 4 5 6 7 8 9 10
出環的序列：4 5 6 7 8 9 10 1 2
轉換為：1 2 3 4 5 6 7 8 9
+3: 4 5 6 7 8 9 10 11 12
%10: 4 5 6 7 8 9 10 1 2
設f(n,m,i)為n個人的環，報數為m，第i個人出環的編號，則f(10,3,10)是我們要的結果
當i=1時，? f(n,m,i) = (n-1+m)%n
當i>1時，? f(n,m,i)= ( f(n-1,m,i-1)+m )%n
當編號為0開始時可以使用遞歸
假設n=10,m=3
0 1 2 3 4 5 6 7 8 9 m=3
第一次有人出列后：0 1 3 4 5 6 7 8 9
3 4 5 6 7 8 9 0 1
1 2 3 4 5 6 7 8 9
+3: 4 5 6 7 8 9 10 11 12
%10: 3 4 5 6 7 8 9 1 2
設f(n,m,i)為n個人的環，報數為m，第i個人出環的編號，則f(10,3,10)是我們要的結果
當i=1時，? f(n,m,i) = (n-1+m)%n
當i>1時，? f(n,m,i)= ( f(n-1,m,i-1)+m )%n
#include <stdio.h>
#include <stdlib.h>
int Josephu_recursion(int n, int m, int i)
{
if(1 == i)
return (n-1 + m) % n;
else
return (Josephu_recursion(n-1, m, i-1) + m) % n;
}
int main(void)
{
int i;
for(i = 1; i <= 10; i ++)
printf("第%2d次出環：%2d\n", i, Josephu_recursion(10, 3, i));
}/***********************************************
* 約瑟夫環問題的數組解決
* n:約瑟夫環的長度
* k:起點
* m:步長
* *********************************************/
int JosephuArray(int n, int k, int m)
{
//分配n+1個int空間
int *a = (int *)malloc((n+1) * sizeof(int));
int i, j;
//下標從1開始賦值
for(i = 1; i <= n; i++)
a[i] = i;//從a[1]開始
//依次出環
for(i = n; i >= 1; i--)
{
//計算每次出環的k值
k = (k + m -1) % i;
if(k == 0)
k = i;
printf("%2d\n", a[k]);//打印出出環的序號
//將出環的位置后的元素前移
for(j = k; j < i; j++)
a[j] = a[j+1];
}
free(a);
}免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
