C語言循環(huán)鏈表的原理與使用操作
更新時間：2022年05月23日 10:42:36 作者：Mi?ronin
無論是靜態(tài)鏈表還是動態(tài)鏈表，有時在解決具體問題時，需要我們對其結構進行稍微地調整。比如，可以把鏈表的兩頭連接，使其成為了一個環(huán)狀鏈表，通常稱為循環(huán)鏈表
一.引入
在單鏈表中我們是把結點遍歷一遍后就結束了，為了使表處理更加方便靈活，我們希望通過任意一個結點出發(fā)都可以找到鏈表中的其它結點,因此我們引入了循環(huán)鏈表。
二.循環(huán)鏈表的定義
將單鏈表中終端結點的指針端由空指針改為頭結點，就使整個單鏈表形成了一個環(huán)，這種頭尾相接的單鏈表稱為循環(huán)鏈表。
簡單理解就是形成一個閉合的環(huán)，在環(huán)內尋找自己需要的結點。
三.單鏈表與循環(huán)鏈表對比
3.1圖示對比
單鏈表：
循環(huán)鏈表：
3.2代碼對比
單鏈表：
typedef struct Node{ //定義單鏈表結點類型
int data; //數(shù)據域，可以是別的各種數(shù)據類型
struct Node *next; //指針域
}LNode, *LinkList;
循環(huán)鏈表：
typedef int ELEMTYPE;
typedef struct Clist
{
ELEMTYPE data; //數(shù)據域 存放數(shù)據
struct Clist* next;
//指針域存放下一個節(jié)點的地址（尾結點的next保存頭結點的地址）
}Clist, * PClist;
四.循環(huán)鏈表的操作
循環(huán)鏈表是單鏈表中擴展出來的結構，所以有很多的操作是和單鏈表相同的，如求長度，查找元素，獲取一個元素，這里我們對循環(huán)鏈表進行初始化，創(chuàng)建，插入，刪除，銷毀的一系列操作。
4.1循環(huán)鏈表的初始化
單鏈表和循環(huán)鏈表初始化對比如下：
| 單鏈表 | 循環(huán)鏈表 |
|---|---|
| 數(shù)據域不處理 | 數(shù)據域不處理 |
| next域賦值為NULL | next域賦值為頭結點自身的地址 |
代碼如下：
void InitClist(struct Clist* plist)
{
//assert
//plist->data; // 數(shù)據域不處理
plist->next = plist;
}4.2循環(huán)鏈表的建立
循環(huán)鏈表的建立是基于單鏈表所以也有頭插和尾插兩種方式。
4.2.1頭插法建立循環(huán)鏈表
頭插法建立循環(huán)鏈表的主要是這兩行代碼：
pnewnode->next=plist->next;
plist->next=pnewnode;
這里我們需要思考一下當鏈表為空時是否適用：這里明確告訴大家不管是否是空鏈表，這兩行代碼均可以使用，下面給大家用示意圖表示一下；
不是空鏈：
是空鏈：
代碼如下：
bool Insert_head(PClist plist, ELEMTYPE val)
{
//assert
//1.購買新節(jié)點
struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;//購買的新節(jié)點 處理完畢
//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.購買新節(jié)點
struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;//購買的新節(jié)點 處理完畢
//2.找到插入位置(通過帶前驅的for循環(huán))
struct Clist* p = plist;
for (p; p->next != plist; p = p->next);
//此時 for循環(huán)執(zhí)行結束 p指向尾結點
//3.插入
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
4.3循環(huán)鏈表的插入操作
與單向鏈表的插入不同，循環(huán)單鏈表插入時只能往表頭節(jié)點的后面插入，由初始結構可知，想完成插入操作，必須先找到要插入位置的前一個節(jié)點，然后修改相應指針即可完成操作。
bool Insert_pos(PClist plist, int pos, ELEMTYPE val)
{
assert(plist != NULL);
assert(pos >= 0 && pos <= Get_length(plist));
//1.購買新節(jié)點
struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;//購買的新節(jié)點 處理完畢
//2.找到插入位置(通過帶前驅的for循環(huán))
struct Clist* p = plist;
for (int i = 0; i < pos; i++)
{
p = p->next;
}
//此時 for循環(huán)執(zhí)行結束 p指向待插入的合適位置
//3.插入
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
4.4循環(huán)鏈表的刪除操作
循環(huán)鏈表的刪除操作相當于單鏈表的刪除操作，主要分為以下三個步驟：
- 指針p指向待刪除的結點；
- 指針q指向待刪除結點的前一個結點；
- 跨越指向。
void Delete(list **pNode,int place) //刪除操作
{
list *temp,*target;
int i;
temp=*pNode;
if(temp==NULL) //首先判斷鏈表是否為空
{
printf("這是一個空指針 無法刪除\n");
return;
}
if(place==1) //如果刪除的是頭節(jié)點
{ //應當特殊處理，找到尾節(jié)點，使尾節(jié)點的next指向頭節(jié)點的下一個節(jié)點
// rear->next=(*head)->next;然后讓新節(jié)點作為頭節(jié)點，釋放原來的頭節(jié)點
for(target=*pNode;target->next!=*pNode;target=target->next);
temp=*pNode;
*pNode=(*pNode)->next;
target->next=*pNode;
free(temp);
}
else //刪除其他節(jié)點
{ //首先找出尾節(jié)點
for(i=1,target=*pNode;target->next!=*pNode&&i!=place-1;target=target->next,i++);
if(target->next==*pNode) //判斷要刪除的位置是否大于鏈表長度，若大于鏈表長度，
//特殊處理直接刪除尾節(jié)點
{
//找出尾節(jié)的前一個節(jié)點
for(target=*pNode;target->next->next!=*pNode;target=target->next);
temp=target->next; // 尾節(jié)點的前一個節(jié)點直接指向頭節(jié)點 釋放原來的尾節(jié)點
target->next=*pNode;
printf("數(shù)字太大刪除尾巴\n");
free(temp);
}
else
{
temp=target->next;// 刪除普通節(jié)點 找到要刪除節(jié)點的前一個節(jié)點target，
//使target指向要刪除節(jié)點的下一個節(jié)點 轉存刪除節(jié)點地址
target->next=temp->next; // 然后釋放這個節(jié)點
free(temp);
}
}
}
4.5循環(huán)鏈表的銷毀
循環(huán)鏈表這里有兩種銷毀方式：
4.5.1無限頭刪
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兩個指針變量
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)鏈表還有查找值，判空，求鏈表長度，清空等一系列操作，這些操作與單鏈表那的操作基本相同，這里不進行詳細贅述，在后面的完整代碼中會寫出來。
五.總結
循環(huán)鏈表相對于單鏈表來說會稍微復雜一點，主要思想還是和單鏈表差不多的，只不過是將鏈表的首位進行相連，但是正是因為首尾的相連，便于我們通過任意一個結點出發(fā)都可以找到鏈表中的其它結點。
六.全部代碼
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
//循環(huán)鏈表里邊很少出現(xiàn)NULL， nullptr
//初始化
void InitClist(struct Clist* plist)
{
//assert
//plist->data; // 數(shù)據域不處理
plist->next = plist;
}
//頭插
bool Insert_head(PClist plist, ELEMTYPE val)
{
//assert
//1.購買新節(jié)點
struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;//購買的新節(jié)點 處理完畢
//2.找到插入位置 （頭插 不用找）
//3.插入
pnewnode->next = plist->next;
plist->next = pnewnode;
return true;
}
//尾插
bool Insert_tail(PClist plist, ELEMTYPE val)
{
//assert
//1.購買新節(jié)點
struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;//購買的新節(jié)點 處理完畢
//2.找到插入位置(通過帶前驅的for循環(huán))
struct Clist* p = plist;
for (p; p->next != plist; p = p->next);
//此時 for循環(huán)執(zhí)行結束 p指向尾結點
//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.購買新節(jié)點
struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;//購買的新節(jié)點 處理完畢
//2.找到插入位置(通過帶前驅的for循環(huán))
struct Clist* p = plist;
for (int i = 0; i < pos; i++)
{
p = p->next;
}
//此時 for循環(huán)執(zhí)行結束 p指向待插入的合適位置
//3.插入
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
//頭刪
bool Del_head(PClist plist)
{
//assert
if (IsEmpty(plist))//不空 則至少存在一個有效值
{
return false;
}
//1.指針p指向待刪除節(jié)點
struct Clist* p = plist->next;
//2.指針q指向待刪除節(jié)點的前一個節(jié)點
//q 就是 頭結點 這里就不再額外處理
//3.跨越指向
plist->next = p->next;
free(p);
return true;
}
//尾刪
bool Del_tail(PClist plist)
{
//assert
if (IsEmpty(plist))//不空 則至少存在一個有效值
{
return false;
}
//1.指針p指向待刪除節(jié)點(尾刪的話，這里指向尾結點)
struct Clist* p = plist;
for (p; p->next != plist; p = p->next);
//此時 for指向結束 代表著p指向尾結點
//2.指針q指向倒數(shù)第二個節(jié)點
struct Clist* q = plist;
for (q; q->next != p; q = q->next);
//此時 for指向結束 代表著q指向p的上一個節(jié)點
//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é)點
//2.指針q指向待刪除節(jié)點的上一個節(jié)點
//這里采用第二種方案找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;
}
//查找(如果查找到，需要返回找到的這個節(jié)點的地址)
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)鏈表不需要這個操作）
//獲取長度
/*指針p從頭結點的下一個節(jié)點開始向后跑，如果p再次遇到了頭結點，
證明p走了一圈回來了，這是有效節(jié)點肯定已經遍歷結束*/
int Get_length(PClist plist)
{
//不帶前驅的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);
}
//銷毀1(無限頭刪)
void Destroy1(PClist plist)
{
//assert
while (plist->next != plist)
{
struct Clist* p = plist->next;
plist->next = p->next;
free(p);
}
plist->next = plist;
}
//銷毀2(要用到兩個指針變量)
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");
}到此這篇關于C語言循環(huán)鏈表的原理與使用操作的文章就介紹到這了,更多相關C語言循環(huán)鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
vscode是一款越來越受碼農們喜愛的軟件，大多數(shù)人學習編程繞不開的一部分就是算法，很多人都喜歡刷LeetCode的題目，本文就來介紹一下2021-06-06
這篇文章主要為大家詳細介紹了如何使用C語言實現(xiàn)一個簡單而實用的隨機密碼生成器,該生成器將生成包含字母、數(shù)字和特殊字符的隨機密碼,有需要的小伙伴可以參考下2023-11-11
OpenCV實現(xiàn)低對比度圖像臟污區(qū)域檢測
本文主要介紹了OpenCV實現(xiàn)低對比度圖像臟污區(qū)域檢測，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-09-09
C++實現(xiàn)圖書管理系統(tǒng)(文件操作與類)
這篇文章主要為大家詳細介紹了C++實現(xiàn)圖書管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要介紹了C++中虛函數(shù)的知識點，文中配合代碼講解非常細致，供大家參考和學習，感興趣的朋友可以了解下2020-06-06
這篇文章主要為大家詳細介紹了C語言計算大數(shù)相加的方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-05-05
詳解C語言中getgid()函數(shù)和getegid()函數(shù)的區(qū)別
這篇文章主要介紹了詳解C語言中getgid()函數(shù)和getegid()函數(shù)的區(qū)別,注意getegid只返回有效的組識別碼,需要的朋友可以參考下2015-08-08
三子棋是黑白棋的一種。三子棋是一種民間傳統(tǒng)游戲，又叫九宮棋、圈圈叉叉、一條龍、井字棋等。這篇文章就教你如何用C語言實現(xiàn)三子棋的功能2021-08-08
在C語言中,有時候我們遇到這樣的考題,將c語言大寫字母轉化為小寫字母,下面這篇文章主要給大家介紹了關于C語言中字母大小寫轉化的相關資料,文中介紹的非常詳細,需要的朋友可以參考下2022-11-11
Win32下C++實現(xiàn)快速獲取硬盤分區(qū)信息
這篇文章主要為大家詳細介紹了Win32下C++如何實現(xiàn)快速獲取硬盤分區(qū)信息,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2025-03-03