1.概念
對于單鏈表壶谒，由于每個結(jié)點值存儲了向后的指針云矫，到了尾部標識就停止了向后鏈的操作。也就是說汗菜，按照這樣的方式让禀，只能索引后繼結(jié)點不能索引前驅(qū)結(jié)點。
這樣的話陨界，假如不從頭結(jié)點觸發(fā)巡揍，就無法訪問到全部結(jié)點。為了解決這個問題普碎，我們將單鏈表中終端結(jié)點的指針由空指針改為指向頭結(jié)點吼肥，問題就解決了录平。
定義
將單鏈表中終端結(jié)點的指針端由空指針改為指向頭結(jié)點麻车，就使整個單鏈表形成一個環(huán)缀皱，這種頭尾相接的單鏈表稱為單循環(huán)鏈表，簡稱循環(huán)鏈表动猬。
注意：
并不是說循環(huán)鏈表一定要有頭結(jié)點
循環(huán)鏈表和單鏈表的主要差異就在于循環(huán)的判斷空鏈表的條件上啤斗，單 鏈表是判斷head->next是否為NULL,現(xiàn)在則是head->next是否等于head
下方示例都以尾指針rear來指代循環(huán)鏈表而不是頭指針,而且示例中的循環(huán)鏈表都沒有頭結(jié)點，也就是說赁咙，循環(huán)鏈中第一個結(jié)點钮莲，實際上是尾結(jié)點(這點需要發(fā)揮一點想象力)
由于終端結(jié)點用尾指針rear指示，則查找終端結(jié)點的復雜度為O(1)彼水，而開始結(jié)點是rear->next->next,當然也是O(1)
2. 循環(huán)鏈表的定義
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *CircleLinkList;
3. 循環(huán)鏈表的創(chuàng)建
void initCircleLinkList(CircleLinkList *L){
//表示輸入的內(nèi)容
int item;
CircleLinkList temp;
//target每次用來標記尾結(jié)點
CircleLinkList target = NULL;
printf("輸入結(jié)點的值崔拥，輸入0表示完成初始化\n");
while (1) {
scanf("%d",&item);
fflush(stdin);
if (item == 0) {
return;
}
if (*L == NULL) {
/*循環(huán)鏈表為空 則創(chuàng)建第一個結(jié)點 作為尾結(jié)點*/
*L = (CircleLinkList)malloc(sizeof(Node));
if (!(*L)) {
exit(0);
}
(*L)->data = item;
(*L)->next = *L;
} else {
//找到尾結(jié)點前面第一個結(jié)點
for (target = *L; target->next != *L; target = target->next);
temp = (CircleLinkList)malloc(sizeof(Node));
if (!temp) {
exit(0);
}
//在尾結(jié)點之前插入一個新的結(jié)點
temp->data = item;
temp->next = *L;
target->next = temp;
}
}
}
4. 循環(huán)鏈表的插入
/// 插入結(jié)點
/// @param L 鏈表的尾結(jié)點
/// @param i 插入的位置
void insertCircleLinkList(CircleLinkList *L,int i){
CircleLinkList temp,target;
int item,j = 1;
printf("請輸入要插入結(jié)點的值:");
scanf("%d",&item);
if (i == 1) {
//i==1 表示要替換到之前的尾結(jié)點
temp = (CircleLinkList)malloc(sizeof(Node));
if (!temp) {
exit(0);
}
temp->data = item;
//循環(huán)得到尾結(jié)點前面一個結(jié)點
for (target = *L; target->next != *L; target = target->next);
temp->next = *L;
target->next = temp;
//將新結(jié)點放在尾結(jié)點位置
*L = temp;
} else {
target = *L;
//通過i-2次遍歷，得到i位置前面一個結(jié)點
for (; j < (i-1); ++j) {
target = target->next;
}
temp = (CircleLinkList)malloc(sizeof(Node));
if (!temp) {
exit(0);
}
temp->data = item;
temp->next = target->next;
target->next = temp;
}
}
5.循環(huán)鏈表的刪除
void deleteCircleLinkList(CircleLinkList *L,int i){
CircleLinkList target,temp;
if (i == 1) {
//刪除尾指針的結(jié)點
//獲取到尾結(jié)點前面的一個結(jié)點
for (target = *L; target->next != *L; target = target->next);
//重新指向
temp = *L;
*L = (*L)->next;
target->next = *L;
//釋放結(jié)點
free(temp);
} else {
//獲取到i-1位置的結(jié)點
target = *L;
for (int j = 1; j < i-1; j++) {
target = target->next;
}
temp = target->next;
target->next = target->next->next;
free(temp);
}
}
6.循環(huán)鏈表返回結(jié)點的位置
//通過數(shù)據(jù)的值凤覆，得到結(jié)點位置
int searchCircleLinkList(CircleLinkList L,int elem){
CircleLinkList target;
int i = 1;
for (target = L; target->data != elem && target->next != L; ++i) {
target = target->next;
}
if (target->next == L) {
//找了一圈還是沒找到
return 0;
}
return i;
}
7链瓦、循環(huán)鏈表的特點
- 使用rear是否等于rear->next來判斷循環(huán)鏈表是否為空表
一個例子：
題目：實現(xiàn)將兩個線性表(a1,a2,...,an)和(b1,b2,...,bm)連接成一個線性表(a1,...an,b1,...bm)的運算
分析：
若在單鏈表或頭指針表示的單循環(huán)表上左這種鏈接操作，都需要遍歷第一個鏈表盯桦，找到結(jié)點an,然后將結(jié)點b1鏈到an的后面慈俯，其執(zhí)行時間是O(n)
若在尾指針表示的單循環(huán)鏈表上實現(xiàn)，則只需要修改指針拥峦，無需遍歷贴膘，其執(zhí)行時間為O(1)
CircleLinkList connectLinkList(CircleLinkList L1,CircleLinkList L2){
CircleLinkList head = L1->next; //保存L1的頭結(jié)點位置
L1->next = L2->next->next; //L1的尾結(jié)點指向L2的第一個結(jié)點
free(L2->next); //是否L2的頭結(jié)點
L2->next = head; //讓L2的尾結(jié)點指向L1的頭結(jié)點
return L2;
}
8、約瑟夫問題
據(jù)說著名猶太歷史學家 Josephus有過以下的故事：在羅馬人占領(lǐng)喬塔帕特后略号，39 個猶太人與Josephus及他的朋友躲到一個洞中刑峡，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式玄柠，41個人排成一個圓圈氛琢，由第1個人開始報數(shù)，每報數(shù)到第3人該人就必須自殺随闪，然后再由下一個重新報數(shù)阳似，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從铐伴。首先從一個人開始撮奏，越過k-2個人（因為第一個人已經(jīng)被越過），并殺掉第k個人当宴。接著畜吊，再越過k-1個人，并殺掉第k個人户矢。這個過程沿著圓圈一直進行玲献，直到最終只剩下一個人留下，這個人就可以繼續(xù)活著。問題是捌年，給定了和瓢娜，一開始要站在什么地方才能避免被處決？Josephus要他的朋友先假裝遵從礼预，他將朋友與自己安排在第16個與第31個位置眠砾，于是逃過了這場死亡游戲。
解題思路：
- 創(chuàng)建一個包含41個結(jié)點的循環(huán)鏈表（沒有頭結(jié)點）,每個節(jié)點的數(shù)據(jù)域都存放一個序號托酸，分別為1-41
- 模擬計數(shù)過程褒颈，每次數(shù)到3則刪除這個節(jié)點，并在下一個節(jié)點開始重新計數(shù)励堡，最后得到免死的序號與人數(shù)
//創(chuàng)建一個不包含頭結(jié)點的循環(huán)鏈表
Node *create(int n){
//head用于存儲第一個結(jié)點的地址
Node *p = NULL,*s = NULL,*head = NULL;
for (int i = 1;i <= n; i++) {
p = (Node *)malloc(sizeof(Node));
p->data = i;
if (i == 1) {
//第一個結(jié)點
head = s = p;
} else {
s->next = p;
s = p;
}
}
//構(gòu)成循環(huán)
s->next = head;
return head;
}
//解決約瑟夫問題谷丸，返回免死的人數(shù)
void soulutionProblem(int *args){
//n表示總?cè)藬?shù)，m表示數(shù)到幾
int n = 41,m = 3;
// scanf("%d%d",&n,&m);
Node *L = create(n);
Node *p = L;
int counter = 1;
while (p != p->next) {
if (counter % m == 0) {
//數(shù)到了這個數(shù)字
/*
這個就是需要自殺的人 我們刪除這個節(jié)點
然后再從下一個開始再排
*/
Node *temp = p->next;
p->next = temp->next;
free(temp);
p = p->next;
counter = 1;
n--;
if (n < m) {
//如果剩下總?cè)藬?shù)比計數(shù)的總?cè)藬?shù)還少的時候
//剩下的這些人就可以耍賴不自殺了
*args = n;
while (p != p->next) {
printf("%d\n",p->next->data);
Node *temp = p->next;
p->next = temp->next;
free(temp);
p = p->next;
}
printf("%d\n",p->data);
free(p);
break;
}
} else {
counter++;
if (counter % m != 0) {
p = p->next;
}
}
}
}
9.約瑟夫問題簡易方法
大致思路就是逆推得到n人应结、m個數(shù)的問題淤井，可以由(n-1)人推導到位置，依次類推,最后得到單次的公式為（ans + m）% n,其中ams為最后出列人的序號摊趾，m表示要數(shù)的數(shù)字币狠，n表示單次總?cè)藬?shù)，下面給出代碼
void simpleSolution(){
int n, m, i, s = 0;
n = 41;m = 3;
scanf("%d%d", &n, &m);
//經(jīng)過n-1次的推導砾层，單次的總?cè)藬?shù)為i
for (i = 2; i <= n; i++)
{
s = (s + m) % i;
printf("%d\n",s);
}
printf ("\nThe winner is %d\n", s+1);
}
這種方法的缺點是只能得到最終一個人漩绵，不能求得其它可以免于自殺的人的序號
