C語言循環鏈表的原理與使用操作

Posted on by

一.引入

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

二.循環鏈表的定義

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

簡單理解就是形成一個閉合的環，在環內尋找自己需要的結點。

三.單鏈表與循環鏈表對比

3.1圖示對比

單鏈表：

循環鏈表：

3.2代碼對比

單鏈表：

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

循環鏈表：

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

四.循環鏈表的操作

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

4.1循環鏈表的初始化

單鏈表和循環鏈表初始化對比如下：

單鏈表 循環鏈表
數據域不處理 數據域不處理
next域賦值為NULL next域賦值為頭結點自身的地址

代碼如下：

void InitClist(struct Clist* plist)
{
	//assert
	//plist->data; // 數據域不處理
	plist->next = plist;
}

4.2循環鏈表的建立

循環鏈表的建立是基於單鏈表所以也有頭插和尾插兩種方式。

4.2.1頭插法建立循環鏈表

頭插法建立循環鏈表的主要是這兩行代碼：

pnewnode->next=plist->next;
plist->next=pnewnode;

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

不是空鏈：

是空鏈：

代碼如下：

bool Insert_head(PClist plist, ELEMTYPE val)
{
	//assert
	//1.購買新節點
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//購買的新節點  處理完畢
	//2.找到插入位置  （頭插  不用找）
	//3.插入
	pnewnode->next = plist->next;
	plist->next = pnewnode;
	return true;
}

4.2.2尾插法建立循環鏈表

尾插法建立循環鏈表主要代碼如下：

for(p=plist;p->next!=plist;p=p->next);

代碼如下：

bool Insert_tail(PClist plist, ELEMTYPE val)
{
	//assert
	//1.購買新節點
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//購買的新節點  處理完畢
	//2.找到插入位置(通過帶前驅的for循環)
	struct Clist* p = plist;
	for (p; p->next != plist; p = p->next);
	//此時 for循環執行結束   p指向尾結點
	//3.插入
	pnewnode->next = p->next;
	p->next = pnewnode;
	return true;
}

4.3循環鏈表的插入操作

與單向鏈表的插入不同，循環單鏈表插入時隻能往表頭節點的後面插入，由初始結構可知，想完成插入操作，必須先找到要插入位置的前一個節點，然後修改相應指針即可完成操作。

bool Insert_pos(PClist plist, int pos, ELEMTYPE val)
{
	assert(plist != NULL);
	assert(pos >= 0 && pos <= Get_length(plist));
	//1.購買新節點
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//購買的新節點  處理完畢
	//2.找到插入位置(通過帶前驅的for循環)
	struct Clist* p = plist;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}
	//此時 for循環執行結束   p指向待插入的合適位置
	//3.插入
	pnewnode->next = p->next;
	p->next = pnewnode;
	return true;
}

4.4循環鏈表的刪除操作

循環鏈表的刪除操作相當於單鏈表的刪除操作，主要分為以下三個步驟：

  • 指針p指向待刪除的結點；
  • 指針q指向待刪除結點的前一個結點；
  • 跨越指向。
void Delete(list **pNode,int place)  //刪除操作
{
	list *temp,*target;
	int i;
	temp=*pNode;
	if(temp==NULL)				//首先判斷鏈表是否為空
	{
		printf("這是一個空指針 無法刪除\n");
		return;
	}
	if(place==1)		//如果刪除的是頭節點	
	{				//應當特殊處理，找到尾節點，使尾節點的next指向頭節點的下一個節點
                    // rear->next=(*head)->next;然後讓新節點作為頭節點，釋放原來的頭節點
		for(target=*pNode;target->next!=*pNode;target=target->next);
		temp=*pNode;
		
		*pNode=(*pNode)->next;
		target->next=*pNode;
		free(temp);
	}
	else //刪除其他節點
	{		//首先找出尾節點
		for(i=1,target=*pNode;target->next!=*pNode&&i!=place-1;target=target->next,i++); 
		if(target->next==*pNode)		//判斷要刪除的位置是否大於鏈表長度，若大於鏈表長度，        
                                        //特殊處理直接刪除尾節點
		{
                //找出尾節的前一個節點
			for(target=*pNode;target->next->next!=*pNode;target=target->next);
			temp=target->next;	 //	尾節點的前一個節點直接指向頭節點  釋放原來的尾節點									
			target->next=*pNode;
			printf("數字太大刪除尾巴\n");
			free(temp);
		}
		else
		{
			temp=target->next;//  刪除普通節點  找到要刪除節點的前一個節點target，
                                //使target指向要刪除節點的下一個節點  轉存刪除節點地址
			target->next=temp->next;	//  然後釋放這個節點
			free(temp);
		}
	}
}

4.5循環鏈表的銷毀

循環鏈表這裡有兩種銷毀方式：

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其他操作

循環鏈表還有查找值，判空，求鏈表長度，清空等一系列操作，這些操作與單鏈表那的操作基本相同，這裡不進行詳細贅述，在後面的完整代碼中會寫出來。

五.總結

循環鏈表相對於單鏈表來說會稍微復雜一點，主要思想還是和單鏈表差不多的，隻不過是將鏈表的首位進行相連，但是正是因為首尾的相連，便於我們通過任意一個結點出發都可以找到鏈表中的其它結點。

六.全部代碼

#include <stdio.h>
#include <malloc.h>
#include <assert.h>
//循環鏈表裡邊很少出現NULL， nullptr
//初始化
void InitClist(struct Clist* plist)
{
	//assert
	//plist->data; // 數據域不處理
	plist->next = plist;
}
//頭插
bool Insert_head(PClist plist, ELEMTYPE val)
{
	//assert
	//1.購買新節點
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//購買的新節點  處理完畢
	//2.找到插入位置  （頭插  不用找）
	//3.插入
	pnewnode->next = plist->next;
	plist->next = pnewnode;
	return true;
}
//尾插
bool Insert_tail(PClist plist, ELEMTYPE val)
{
	//assert
	//1.購買新節點
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//購買的新節點  處理完畢
	//2.找到插入位置(通過帶前驅的for循環)
	struct Clist* p = plist;
	for (p; p->next != plist; p = p->next);
	//此時 for循環執行結束   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.購買新節點
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//購買的新節點  處理完畢
	//2.找到插入位置(通過帶前驅的for循環)
	struct Clist* p = plist;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}
	//此時 for循環執行結束   p指向待插入的合適位置
	//3.插入
	pnewnode->next = p->next;
	p->next = pnewnode;
	return true;
}
//頭刪
bool Del_head(PClist plist)
{
	//assert
	if (IsEmpty(plist))//不空  則至少存在一個有效值
	{
		return false;
	}
	//1.指針p指向待刪除節點
	struct Clist* p = plist->next;
	//2.指針q指向待刪除節點的前一個節點
	//q 就是 頭結點  這裡就不再額外處理
	//3.跨越指向
	plist->next = p->next;
	free(p);
	return true;
}
//尾刪
bool Del_tail(PClist plist)
{
	//assert
	if (IsEmpty(plist))//不空  則至少存在一個有效值
	{
		return false;
	}
	//1.指針p指向待刪除節點(尾刪的話，這裡指向尾結點)
	struct Clist* p = plist;
	for (p; p->next != plist; p = p->next);
	//此時 for指向結束  代表著p指向尾結點
	//2.指針q指向倒數第二個節點
	struct Clist* q = plist;
	for (q; q->next != p; q = q->next);
	//此時 for指向結束  代表著q指向p的上一個節點
	//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指向待刪除節點
	//2.指針q指向待刪除節點的上一個節點
	//這裡采用第二種方案找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;
}
//查找(如果查找到，需要返回找到的這個節點的地址)
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;
}
//判滿（循環鏈表不需要這個操作）
//獲取長度
/*指針p從頭結點的下一個節點開始向後跑，如果p再次遇到瞭頭結點，
證明p走瞭一圈回來瞭，這是有效節點肯定已經遍歷結束*/
int Get_length(PClist plist)
{
	//不帶前驅的for循環 跑一遍就好
	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語言循環鏈表的原理與使用操作的文章就介紹到這瞭,更多相關C語言循環鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：