引言
鏈表還有一種常用的形式，那就是循環(huán)鏈表旧烧，看到循環(huán)兩個字影钉，相比都已經(jīng)知道他是怎樣的鏈表了吧，是的掘剪，他就是一種首尾相連的鏈表平委，這樣的鏈表形成了一個環(huán)的形狀。
什么是循環(huán)鏈表杖小？
上文已經(jīng)說了肆汹，循環(huán)鏈表是首尾相接的一種鏈表，他的尾結(jié)點的后繼指針又指向鏈表的第一個結(jié)點予权，這樣形成了一個環(huán)昂勉。對于循環(huán)鏈表，從表中的任何一個結(jié)點出發(fā)扫腺，都能找到其他所有的結(jié)點岗照。
下圖展示的就是一個單向的循環(huán)鏈表
循環(huán)鏈表的形式有很多種，如雙向循環(huán)鏈表笆环，多重循環(huán)鏈表（將表中結(jié)點鏈在多個環(huán)上）等攒至。
我們來看下多重循環(huán)鏈表的示意圖：
上面的多重循環(huán)鏈表中的14元素，他所在的結(jié)點既在左邊的循環(huán)表中躁劣，也在右邊的循環(huán)表中迫吐。
多重循環(huán)鏈表并不常用，本篇文章主要講解單鏈的循環(huán)鏈表账忘。
循環(huán)鏈表既有單鏈表的優(yōu)點又有雙鏈表的優(yōu)點志膀，相對于單鏈表，雙鏈表需要為每個結(jié)點增加部分存儲空間從而保存前驅(qū)指針的信息鳖擒，而循環(huán)鏈表無須增加存儲空間溉浙，只是改變了尾節(jié)點中后繼指針的指向，就使操作更加靈活多變蒋荚。
需要注意的是戳稽，循環(huán)鏈表中沒有NULL指針，涉及遍歷操作時期升，其終止條件就不再是非循環(huán)鏈表中判別pNode->next是否為空了惊奇，而是判別他們是否等于某一指定指針互躬，如頭指針或尾指針等
我們用代碼表示一下：
//判斷是否與頭結(jié)點的指針指向相同，相同則表示已經(jīng)遍歷到最后的位置了
if(pNode->next==pHead->next){
...
}
2赊时、循環(huán)鏈表的實現(xiàn)
在單鏈表中吨铸，從一個已知結(jié)點觸發(fā)，只能訪問到該結(jié)點機器后繼結(jié)點祖秒，無法找到該結(jié)點之前的其他結(jié)點诞吱。而在單循環(huán)鏈表中，從任一結(jié)點出發(fā)竭缝，都可以訪問到表中的所有結(jié)點房维，這一優(yōu)點使某些運算更容易實現(xiàn)。
由于單循環(huán)鏈表的創(chuàng)建抬纸、查找元素等基本操作相同咙俩，所以這里主要介紹插入、刪除元素時與單鏈表的差別湿故。
1阿趁、插入元素
在循環(huán)鏈表中插入元素，如果是插入到第一個位置坛猪，即頭結(jié)點之后的位置脖阵，則稍微有點麻煩，因為這里需要處理3個指針墅茉，這3個指針分別是：
頭結(jié)點中的指針
尾結(jié)點中的指針
插入元素的結(jié)點指針
我們看下面圖來理解一下
我們看到命黔，當我們把元素插入到第一個位置時，需要將插入結(jié)點分別于頭結(jié)點就斤、尾結(jié)點悍募、原來的第一個元素結(jié)點相連接
這樣一來，單循環(huán)鏈表的插入操作 比 單鏈表處理多了一個尾結(jié)點指針的處理洋机。
在尾部插入元素時坠宴，也有所不同，p->next 不再指向NULL,而是指向head->next绷旗。
除此兩處外啄踊，在其他位置插入元素，則與單鏈表處理相同刁标。
我們來看下代碼實現(xiàn)：
int ClistInsert(pHead ph,int pos,int val){
if(ph==NULL||pos<0||pos>ph->length)
{
printf("插入元素時，參數(shù)傳入有誤!");
}
pNode pval=NULL;
pval=(pNode)malloc(sizeof(struc Node));
pval->data=val;
//如果表為空址晕，直接將結(jié)點插入到頭結(jié)點之后膀懈，然后自己的next指向自己
if(IsEmpty(ph)){
ph->next=pval;
pval->next=pval;
}
else{
//表不為空，則主要分為在頭部插入和在其他部分插入
pNode pRear=ph->next;
if(pos==0){
//在0號位置插入谨垃，需要先找到尾結(jié)點
while(pRear->next!=ph->next){
pRear=pRear->next;//指針向后移動
}
//while結(jié)束之后 pRear指向尾結(jié)點
//此時再插入元素
pval->next=ph->next;
ph->next=pval;
pRear->next=pval;//注意启搂，這三個步驟順序不能更改
}
else{
//說明不是從0的位置插入硼控，這個時候只需要斷開指針，重新指定指針即可
pNode pCur=ph->next;
for(int i=1;i<pos;i++){
pCur=pCur->next;
}
//循環(huán)結(jié)束時就是說明此時pCur指向要插入位置
pval->next=pCur->next;
pCur->next=pval;//指針斷開又鏈接的過程
}
}
ph->length++;
return 1;
}
ok胳赌，總結(jié)一下的話牢撼，就是：在插入新元素時，先判斷鏈表是否為空疑苫，如果為空熏版，則將元素插入到頭結(jié)點后，然后將其指針指向自身捍掺；如果不為空撼短，則根據(jù)插入的位置做出相應(yīng)的操作。代碼的注釋應(yīng)該能夠幫助大家看懂了~~~
2挺勿、刪除元素
在刪除元素時曲横，也要考慮刪除的是否是頭結(jié)點后的第一個結(jié)點，如果是不瓶，則需要將頭結(jié)點和尾結(jié)點的指針指向待刪除結(jié)點的后繼結(jié)點:
如圖所示
如果是刪除其他位置的元素禾嫉，則和單鏈表處理方式相同，其代碼實現(xiàn)如下：
pNode ClistDelete(pHead ph,int val){
if(ph==NULL||ph->lenght==0){
printf("參數(shù)傳入有誤蚊丐！")熙参；
}
//先找到鏈表的尾結(jié)點
pNode pRear=ph->next;
while(pRear!=ph->next){
pRear=pRear->next;
}
//查找要刪除的元素
pNode pval=ClistFind(ph,val);//ClistFind方法跟第七篇的單鏈表查找元素方法相同
if(pval==NULL){
return NULL;
}
if(pval==ph->next){
ph->next=pval->next;
//讓尾結(jié)點指向要刪除元素后邊的結(jié)點
pRear->next=pval->next;
}else{
//找到pval的前驅(qū)結(jié)點
pNode pRe=ph->next;
for(int i=0;i<ph->length;i++){
//這樣pRe就是pval的前驅(qū)結(jié)點
if(val==pRe->data){
//更改指向就可以了
pRe->next=pval->next;
//返回刪除的結(jié)點
return pval;
}
//讓指針后移
pRe=pRe->next;
}
}
//如果上方?jīng)]有返回值，則返回空
return NULL;
}
一句話總結(jié)
在循環(huán)鏈表中吠撮，處理插入和刪除操作與單鏈表稍有不同之外尊惰，其他操作與單鏈表都是一樣的。
大家加油哦~
多謝關(guān)注~~
