C語(yǔ)言循環(huán)鏈表的原理與使用操作
更新時(shí)間：2022年05月23日 10:42:36 作者：Mi?ronin
無(wú)論是靜態(tài)鏈表還是動(dòng)態(tài)鏈表，有時(shí)在解決具體問(wèn)題時(shí)，需要我們對(duì)其結(jié)構(gòu)進(jìn)行稍微地調(diào)整。比如，可以把鏈表的兩頭連接，使其成為了一個(gè)環(huán)狀鏈表，通常稱為循環(huán)鏈表
一.引入
在單鏈表中我們是把結(jié)點(diǎn)遍歷一遍后就結(jié)束了，為了使表處理更加方便靈活，我們希望通過(guò)任意一個(gè)結(jié)點(diǎn)出發(fā)都可以找到鏈表中的其它結(jié)點(diǎn),因此我們引入了循環(huán)鏈表。
二.循環(huán)鏈表的定義
將單鏈表中終端結(jié)點(diǎn)的指針端由空指針改為頭結(jié)點(diǎn)，就使整個(gè)單鏈表形成了一個(gè)環(huán)，這種頭尾相接的單鏈表稱為循環(huán)鏈表。
簡(jiǎn)單理解就是形成一個(gè)閉合的環(huán)，在環(huán)內(nèi)尋找自己需要的結(jié)點(diǎn)。
三.單鏈表與循環(huán)鏈表對(duì)比
3.1圖示對(duì)比
單鏈表：
循環(huán)鏈表：
3.2代碼對(duì)比
單鏈表：
typedef struct Node{ //定義單鏈表結(jié)點(diǎn)類(lèi)型
int data; //數(shù)據(jù)域，可以是別的各種數(shù)據(jù)類(lèi)型
struct Node *next; //指針域
}LNode, *LinkList;
循環(huán)鏈表：
typedef int ELEMTYPE;
typedef struct Clist
{
ELEMTYPE data; //數(shù)據(jù)域 存放數(shù)據(jù)
struct Clist* next;
//指針域存放下一個(gè)節(jié)點(diǎn)的地址（尾結(jié)點(diǎn)的next保存頭結(jié)點(diǎn)的地址）
}Clist, * PClist;
四.循環(huán)鏈表的操作
循環(huán)鏈表是單鏈表中擴(kuò)展出來(lái)的結(jié)構(gòu)，所以有很多的操作是和單鏈表相同的，如求長(zhǎng)度，查找元素，獲取一個(gè)元素，這里我們對(duì)循環(huán)鏈表進(jìn)行初始化，創(chuàng)建，插入，刪除，銷(xiāo)毀的一系列操作。
4.1循環(huán)鏈表的初始化
單鏈表和循環(huán)鏈表初始化對(duì)比如下：
| 單鏈表 | 循環(huán)鏈表 |
|---|---|
| 數(shù)據(jù)域不處理 | 數(shù)據(jù)域不處理 |
| next域賦值為NULL | next域賦值為頭結(jié)點(diǎn)自身的地址 |
代碼如下：
void InitClist(struct Clist* plist)
{
//assert
//plist->data; // 數(shù)據(jù)域不處理
plist->next = plist;
}4.2循環(huán)鏈表的建立
循環(huán)鏈表的建立是基于單鏈表所以也有頭插和尾插兩種方式。
4.2.1頭插法建立循環(huán)鏈表
頭插法建立循環(huán)鏈表的主要是這兩行代碼：
pnewnode->next=plist->next;
plist->next=pnewnode;
這里我們需要思考一下當(dāng)鏈表為空時(shí)是否適用：這里明確告訴大家不管是否是空鏈表，這兩行代碼均可以使用，下面給大家用示意圖表示一下；
不是空鏈：
是空鏈：
代碼如下：
bool Insert_head(PClist plist, ELEMTYPE val)
{
//assert
//1.購(gòu)買(mǎi)新節(jié)點(diǎn)
struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;//購(gòu)買(mǎi)的新節(jié)點(diǎn) 處理完畢
//2.找到插入位置 （頭插 不用找）
//3.插入
pnewnode->next = plist->next;
plist->next = pnewnode;
return true;
}
4.2.2尾插法建立循環(huán)鏈表
尾插法建立循環(huán)鏈表主要代碼如下：
for(p=plist;p->next!=plist;p=p->next);
代碼如下：
bool Insert_tail(PClist plist, ELEMTYPE val)
{
//assert
//1.購(gòu)買(mǎi)新節(jié)點(diǎn)
struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;//購(gòu)買(mǎi)的新節(jié)點(diǎn) 處理完畢
//2.找到插入位置(通過(guò)帶前驅(qū)的for循環(huán))
struct Clist* p = plist;
for (p; p->next != plist; p = p->next);
//此時(shí) for循環(huán)執(zhí)行結(jié)束 p指向尾結(jié)點(diǎn)
//3.插入
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
4.3循環(huán)鏈表的插入操作
與單向鏈表的插入不同，循環(huán)單鏈表插入時(shí)只能往表頭節(jié)點(diǎn)的后面插入，由初始結(jié)構(gòu)可知，想完成插入操作，必須先找到要插入位置的前一個(gè)節(jié)點(diǎn)，然后修改相應(yīng)指針即可完成操作。
bool Insert_pos(PClist plist, int pos, ELEMTYPE val)
{
assert(plist != NULL);
assert(pos >= 0 && pos <= Get_length(plist));
//1.購(gòu)買(mǎi)新節(jié)點(diǎn)
struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;//購(gòu)買(mǎi)的新節(jié)點(diǎn) 處理完畢
//2.找到插入位置(通過(guò)帶前驅(qū)的for循環(huán))
struct Clist* p = plist;
for (int i = 0; i < pos; i++)
{
p = p->next;
}
//此時(shí) for循環(huán)執(zhí)行結(jié)束 p指向待插入的合適位置
//3.插入
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
4.4循環(huán)鏈表的刪除操作
循環(huán)鏈表的刪除操作相當(dāng)于單鏈表的刪除操作，主要分為以下三個(gè)步驟：
- 指針p指向待刪除的結(jié)點(diǎn)；
- 指針q指向待刪除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)；
- 跨越指向。
void Delete(list **pNode,int place) //刪除操作
{
list *temp,*target;
int i;
temp=*pNode;
if(temp==NULL) //首先判斷鏈表是否為空
{
printf("這是一個(gè)空指針 無(wú)法刪除\n");
return;
}
if(place==1) //如果刪除的是頭節(jié)點(diǎn)
{ //應(yīng)當(dāng)特殊處理，找到尾節(jié)點(diǎn)，使尾節(jié)點(diǎn)的next指向頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
// rear->next=(*head)->next;然后讓新節(jié)點(diǎn)作為頭節(jié)點(diǎn)，釋放原來(lái)的頭節(jié)點(diǎn)
for(target=*pNode;target->next!=*pNode;target=target->next);
temp=*pNode;
*pNode=(*pNode)->next;
target->next=*pNode;
free(temp);
}
else //刪除其他節(jié)點(diǎn)
{ //首先找出尾節(jié)點(diǎn)
for(i=1,target=*pNode;target->next!=*pNode&&i!=place-1;target=target->next,i++);
if(target->next==*pNode) //判斷要?jiǎng)h除的位置是否大于鏈表長(zhǎng)度，若大于鏈表長(zhǎng)度，
//特殊處理直接刪除尾節(jié)點(diǎn)
{
//找出尾節(jié)的前一個(gè)節(jié)點(diǎn)
for(target=*pNode;target->next->next!=*pNode;target=target->next);
temp=target->next; // 尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)直接指向頭節(jié)點(diǎn) 釋放原來(lái)的尾節(jié)點(diǎn)
target->next=*pNode;
printf("數(shù)字太大刪除尾巴\n");
free(temp);
}
else
{
temp=target->next;// 刪除普通節(jié)點(diǎn) 找到要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)target，
//使target指向要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) 轉(zhuǎn)存刪除節(jié)點(diǎn)地址
target->next=temp->next; // 然后釋放這個(gè)節(jié)點(diǎn)
free(temp);
}
}
}
4.5循環(huán)鏈表的銷(xiāo)毀
循環(huán)鏈表這里有兩種銷(xiāo)毀方式：
4.5.1無(wú)限頭刪
void Destroy1(PClist plist)
{
//assert
while (plist->next != plist)
{
struct Clist* p = plist->next;
plist->next = p->next;
free(p);
}
plist->next = plist;
}
4.5.2兩個(gè)指針變量
void Destroy2(PClist plist)
{
//assert
struct Clist* p = plist->next;
struct Clist* q = NULL;
plist->next = plist;
while (p != plist)
{
q = p->next;
free(p);
p = q;
}
}4.6其他操作
循環(huán)鏈表還有查找值，判空，求鏈表長(zhǎng)度，清空等一系列操作，這些操作與單鏈表那的操作基本相同，這里不進(jìn)行詳細(xì)贅述，在后面的完整代碼中會(huì)寫(xiě)出來(lái)。
五.總結(jié)
循環(huán)鏈表相對(duì)于單鏈表來(lái)說(shuō)會(huì)稍微復(fù)雜一點(diǎn)，主要思想還是和單鏈表差不多的，只不過(guò)是將鏈表的首位進(jìn)行相連，但是正是因?yàn)槭孜驳南噙B，便于我們通過(guò)任意一個(gè)結(jié)點(diǎn)出發(fā)都可以找到鏈表中的其它結(jié)點(diǎn)。
六.全部代碼
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
//循環(huán)鏈表里邊很少出現(xiàn)NULL， nullptr
//初始化
void InitClist(struct Clist* plist)
{
//assert
//plist->data; // 數(shù)據(jù)域不處理
plist->next = plist;
}
//頭插
bool Insert_head(PClist plist, ELEMTYPE val)
{
//assert
//1.購(gòu)買(mǎi)新節(jié)點(diǎn)
struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;//購(gòu)買(mǎi)的新節(jié)點(diǎn) 處理完畢
//2.找到插入位置 （頭插 不用找）
//3.插入
pnewnode->next = plist->next;
plist->next = pnewnode;
return true;
}
//尾插
bool Insert_tail(PClist plist, ELEMTYPE val)
{
//assert
//1.購(gòu)買(mǎi)新節(jié)點(diǎn)
struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;//購(gòu)買(mǎi)的新節(jié)點(diǎn) 處理完畢
//2.找到插入位置(通過(guò)帶前驅(qū)的for循環(huán))
struct Clist* p = plist;
for (p; p->next != plist; p = p->next);
//此時(shí) for循環(huán)執(zhí)行結(jié)束 p指向尾結(jié)點(diǎn)
//3.插入
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
//按位置插
bool Insert_pos(PClist plist, int pos, ELEMTYPE val)
{
assert(plist != NULL);
assert(pos >= 0 && pos <= Get_length(plist));
//1.購(gòu)買(mǎi)新節(jié)點(diǎn)
struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;//購(gòu)買(mǎi)的新節(jié)點(diǎn) 處理完畢
//2.找到插入位置(通過(guò)帶前驅(qū)的for循環(huán))
struct Clist* p = plist;
for (int i = 0; i < pos; i++)
{
p = p->next;
}
//此時(shí) for循環(huán)執(zhí)行結(jié)束 p指向待插入的合適位置
//3.插入
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
//頭刪
bool Del_head(PClist plist)
{
//assert
if (IsEmpty(plist))//不空 則至少存在一個(gè)有效值
{
return false;
}
//1.指針p指向待刪除節(jié)點(diǎn)
struct Clist* p = plist->next;
//2.指針q指向待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
//q 就是 頭結(jié)點(diǎn) 這里就不再額外處理
//3.跨越指向
plist->next = p->next;
free(p);
return true;
}
//尾刪
bool Del_tail(PClist plist)
{
//assert
if (IsEmpty(plist))//不空 則至少存在一個(gè)有效值
{
return false;
}
//1.指針p指向待刪除節(jié)點(diǎn)(尾刪的話，這里指向尾結(jié)點(diǎn))
struct Clist* p = plist;
for (p; p->next != plist; p = p->next);
//此時(shí) for指向結(jié)束 代表著p指向尾結(jié)點(diǎn)
//2.指針q指向倒數(shù)第二個(gè)節(jié)點(diǎn)
struct Clist* q = plist;
for (q; q->next != p; q = q->next);
//此時(shí) for指向結(jié)束 代表著q指向p的上一個(gè)節(jié)點(diǎn)
//3.跨越指向
q->next = p->next;
free(p);
return true;
}
//按位置刪
bool Del_pos(PClist plist, int pos)
{
assert(plist != NULL);
assert(pos >= 0 && pos < Get_length(plist));
if (IsEmpty(plist))
{
return false;
}
//1.指針p指向待刪除節(jié)點(diǎn)
//2.指針q指向待刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
//這里采用第二種方案找pq，先找q再找p
struct Clist* q = plist;
for (int i = 0; i < pos; i++)
{
q = q->next;
}
struct Clist* p = q->next;
//3.跨越指向
q->next = p->next;
free(p);
return true;
}
//按值刪除
bool Del_val(PClist plist, ELEMTYPE val)
{
//assert
struct Clist* p = Search(plist, val);
if (p == NULL)
{
return false;
}
struct Clist* q = plist;
for (q; q->next != p; q = q->next);
q->next = p->next;
free(p);
return true;
}
//查找(如果查找到，需要返回找到的這個(gè)節(jié)點(diǎn)的地址)
struct Clist* Search(struct Clist* plist, ELEMTYPE val)
{
//assert
for (struct Clist* p = plist->next; p != plist; p = p->next)
{
if (p->data == val)
{
return p;
}
}
return NULL;
}
//判空
bool IsEmpty(PClist plist)
{
//assert
return plist->next == plist;
}
//判滿（循環(huán)鏈表不需要這個(gè)操作）
//獲取長(zhǎng)度
/*指針p從頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開(kāi)始向后跑，如果p再次遇到了頭結(jié)點(diǎn)，
證明p走了一圈回來(lái)了，這是有效節(jié)點(diǎn)肯定已經(jīng)遍歷結(jié)束*/
int Get_length(PClist plist)
{
//不帶前驅(qū)的for循環(huán) 跑一遍就好
int count = 0;
for (struct Clist* p = plist->next; p != plist; p = p->next)
{
count++;
}
return count;
}
//清空
void Clear(PClist plist)
{
//assert
Destroy1(plist);
}
//銷(xiāo)毀1(無(wú)限頭刪)
void Destroy1(PClist plist)
{
//assert
while (plist->next != plist)
{
struct Clist* p = plist->next;
plist->next = p->next;
free(p);
}
plist->next = plist;
}
//銷(xiāo)毀2(要用到兩個(gè)指針變量)
void Destroy2(PClist plist)
{
//assert
struct Clist* p = plist->next;
struct Clist* q = NULL;
plist->next = plist;
while (p != plist)
{
q = p->next;
free(p);
p = q;
}
}
//打印
void Show(struct Clist* plist)
{
//assert
for (struct Clist* p = plist->next; p != plist; p = p->next)
{
printf("%d ", p->data);
}
printf("\n");
}到此這篇關(guān)于C語(yǔ)言循環(huán)鏈表的原理與使用操作的文章就介紹到這了,更多相關(guān)C語(yǔ)言循環(huán)鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++實(shí)現(xiàn)LeetCode(120.三角形)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(120.三角形),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C++使用opencv調(diào)用級(jí)聯(lián)分類(lèi)器來(lái)識(shí)別目標(biāo)物體的詳細(xì)流程
所謂級(jí)聯(lián)分類(lèi)器其實(shí)就是把分類(lèi)器按照一定的順序聯(lián)合到一起,下面這篇文章主要給大家介紹了關(guān)于C++使用opencv調(diào)用級(jí)聯(lián)分類(lèi)器來(lái)識(shí)別目標(biāo)物體的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-05-05
二叉樹(shù)大家應(yīng)該都不陌生,但是合并二叉樹(shù)呢?這篇文章主要給大家介紹了關(guān)于C++合并二叉樹(shù)的相關(guān)資料,文中給出了兩種解決的方法,大家可以根據(jù)需要選擇對(duì)應(yīng)的方法,需要的朋友可以參考下2021-08-08
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)井字棋小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-04-04
淺談C++函數(shù)聲明后面加throw()的作用(必看)
下面小編就為大家?guī)?lái)一篇淺談C++函數(shù)聲明后面加throw()的作用(必看)。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-01-01
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言三子棋小游戲的實(shí)現(xiàn)代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11
詳解C語(yǔ)言基礎(chǔ)的類(lèi)型轉(zhuǎn)換
這篇文章主要為大家介紹了C語(yǔ)言基礎(chǔ)的類(lèi)型轉(zhuǎn)換，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2021-11-11
C++實(shí)現(xiàn)主機(jī)字節(jié)序和網(wǎng)絡(luò)字節(jié)序轉(zhuǎn)換示例
這篇文章主要為大家介紹了C++實(shí)現(xiàn)主機(jī)字節(jié)序和網(wǎng)絡(luò)字節(jié)序轉(zhuǎn)換示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-11-11
c語(yǔ)言中十進(jìn)制轉(zhuǎn)二進(jìn)制顯示小工具的實(shí)現(xiàn)代碼
本篇文章是對(duì)c語(yǔ)言中十進(jìn)制轉(zhuǎn)二進(jìn)制顯示小工具的實(shí)現(xiàn)代碼進(jìn)行了詳細(xì)的分析的介紹，需要的朋友參考下2013-05-05
本文主要介紹了C++11中強(qiáng)類(lèi)型枚舉的使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02