C語言循環(huán)鏈表的原理與使用操作

更新時間：2022年05月23日 10:42:36 作者：Mi?ronin

無論是靜態(tài)鏈表還是動態(tài)鏈表，有時在解決具體問題時，需要我們對其結構進行稍微地調(diào)整。比如，可以把鏈表的兩頭連接，使其成為了一個環(huán)狀鏈表，通常稱為循環(huán)鏈表

一.引入

在單鏈表中我們是把結點遍歷一遍后就結束了，為了使表處理更加方便靈活，我們希望通過任意一個結點出發(fā)都可以找到鏈表中的其它結點,因此我們引入了循環(huán)鏈表。

二.循環(huán)鏈表的定義

將單鏈表中終端結點的指針端由空指針改為頭結點，就使整個單鏈表形成了一個環(huán)，這種頭尾相接的單鏈表稱為循環(huán)鏈表。

簡單理解就是形成一個閉合的環(huán)，在環(huán)內(nèi)尋找自己需要的結點。

三.單鏈表與循環(huán)鏈表對比

3.1圖示對比

單鏈表：

循環(huán)鏈表：

3.2代碼對比

單鏈表：

typedef struct Node{ //定義單鏈表結點類型
	int data; //數(shù)據(jù)域，可以是別的各種數(shù)據(jù)類型
	struct Node *next; //指針域
}LNode, *LinkList;

循環(huán)鏈表：

typedef int ELEMTYPE;
typedef struct Clist
{
	ELEMTYPE data; //數(shù)據(jù)域   存放數(shù)據(jù)
	struct Clist* next;
//指針域存放下一個節(jié)點的地址（尾結點的next保存頭結點的地址）
}Clist, * PClist;

四.循環(huán)鏈表的操作

循環(huán)鏈表是單鏈表中擴展出來的結構，所以有很多的操作是和單鏈表相同的，如求長度，查找元素，獲取一個元素，這里我們對循環(huán)鏈表進行初始化，創(chuàng)建，插入，刪除，銷毀的一系列操作。

4.1循環(huán)鏈表的初始化

單鏈表和循環(huán)鏈表初始化對比如下：

單鏈表	循環(huán)鏈表
數(shù)據(jù)域不處理	數(shù)據(jù)域不處理
next域賦值為NULL	next域賦值為頭結點自身的地址

代碼如下：

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;

這里我們需要思考一下當鏈表為空時是否適用：這里明確告訴大家不管是否是空鏈表，這兩行代碼均可以使用，下面給大家用示意圖表示一下；

不是空鏈：

是空鏈：

代碼如下：

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ù)據(jù)域不處理
	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é)點肯定已經(jīng)遍歷結束*/
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)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

vscode刷acm、leetcode的題目
vscode是一款越來越受碼農(nóng)們喜愛的軟件，大多數(shù)人學習編程繞不開的一部分就是算法，很多人都喜歡刷LeetCode的題目，本文就來介紹一下
2021-06-06
C語言實現(xiàn)隨機生成6位數(shù)密碼
這篇文章主要為大家詳細介紹了如何使用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ù)專題
這篇文章主要介紹了C++中虛函數(shù)的知識點，文中配合代碼講解非常細致，供大家參考和學習，感興趣的朋友可以了解下
2020-06-06
C語言計算大數(shù)相加的方法
這篇文章主要為大家詳細介紹了C語言計算大數(shù)相加的方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2021-05-05
詳解C語言中getgid()函數(shù)和getegid()函數(shù)的區(qū)別
這篇文章主要介紹了詳解C語言中getgid()函數(shù)和getegid()函數(shù)的區(qū)別,注意getegid只返回有效的組識別碼,需要的朋友可以參考下
2015-08-08
手把手教你用C語言實現(xiàn)三子棋
三子棋是黑白棋的一種。三子棋是一種民間傳統(tǒng)游戲，又叫九宮棋、圈圈叉叉、一條龍、井字棋等。這篇文章就教你如何用C語言實現(xiàn)三子棋的功能
2021-08-08
C語言中字母大小寫轉化簡單示例
在C語言中,有時候我們遇到這樣的考題,將c語言大寫字母轉化為小寫字母,下面這篇文章主要給大家介紹了關于C語言中字母大小寫轉化的相關資料,文中介紹的非常詳細,需要的朋友可以參考下
2022-11-11
Win32下C++實現(xiàn)快速獲取硬盤分區(qū)信息
這篇文章主要為大家詳細介紹了Win32下C++如何實現(xiàn)快速獲取硬盤分區(qū)信息,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下
2025-03-03