欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間：2022年05月23日 10:42:36   作者：Mi?ronin  
無論是靜態(tài)鏈表還是動態(tài)鏈表，有時在解決具體問題時，需要我們對其結(jié)構(gòu)進(jìn)行稍微地調(diào)整。比如，可以把鏈表的兩頭連接，使其成為了一個環(huán)狀鏈表，通常稱為循環(huán)鏈表

一.引入

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

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

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

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

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

3.1圖示對比

單鏈表：

循環(huán)鏈表：

3.2代碼對比

單鏈表：

typedef struct Node{ //定義單鏈表結(jié)點(diǎn)類型
	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é)點(diǎn)的地址（尾結(jié)點(diǎn)的next保存頭結(jié)點(diǎn)的地址）
}Clist, * PClist;

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

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

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

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

單鏈表循環(huán)鏈表
數(shù)據(jù)域不處理數(shù)據(jù)域不處理
next域賦值為NULLnext域賦值為頭結(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)鏈表為空時是否適用：這里明確告訴大家不管是否是空鏈表，這兩行代碼均可以使用，下面給大家用示意圖表示一下；

不是空鏈：

是空鏈：

代碼如下：

bool Insert_head(PClist plist, ELEMTYPE val)
{
	//assert
	//1.購買新節(jié)點(diǎn)
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//購買的新節(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.購買新節(jié)點(diǎn)
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//購買的新節(jié)點(diǎn)  處理完畢
	//2.找到插入位置(通過帶前驅(qū)的for循環(huán))
	struct Clist* p = plist;
	for (p; p->next != plist; p = p->next);
	//此時 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)單鏈表插入時只能往表頭節(jié)點(diǎn)的后面插入，由初始結(jié)構(gòu)可知，想完成插入操作，必須先找到要插入位置的前一個節(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.購買新節(jié)點(diǎn)
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//購買的新節(jié)點(diǎn)  處理完畢
	//2.找到插入位置(通過帶前驅(qū)的for循環(huán))
	struct Clist* p = plist;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}
	//此時 for循環(huán)執(zhí)行結(jié)束   p指向待插入的合適位置
	//3.插入
	pnewnode->next = p->next;
	p->next = pnewnode;
	return true;
}

4.4循環(huán)鏈表的刪除操作

循環(huán)鏈表的刪除操作相當(dāng)于單鏈表的刪除操作，主要分為以下三個步驟：

  • 指針p指向待刪除的結(jié)點(diǎn)；
  • 指針q指向待刪除結(jié)點(diǎn)的前一個結(jié)點(diǎn)；
  • 跨越指向。
void Delete(list **pNode,int place)  //刪除操作
{
	list *temp,*target;
	int i;
	temp=*pNode;
	if(temp==NULL)				//首先判斷鏈表是否為空
	{
		printf("這是一個空指針 無法刪除\n");
		return;
	}
	if(place==1)		//如果刪除的是頭節(jié)點(diǎn)	
	{				//應(yīng)當(dāng)特殊處理，找到尾節(jié)點(diǎn)，使尾節(jié)點(diǎn)的next指向頭節(jié)點(diǎn)的下一個節(jié)點(diǎn)
                    // rear->next=(*head)->next;然后讓新節(jié)點(diǎn)作為頭節(jié)點(diǎn)，釋放原來的頭節(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é)點(diǎn)
		{
                //找出尾節(jié)的前一個節(jié)點(diǎn)
			for(target=*pNode;target->next->next!=*pNode;target=target->next);
			temp=target->next;	 //	尾節(jié)點(diǎn)的前一個節(jié)點(diǎn)直接指向頭節(jié)點(diǎn)  釋放原來的尾節(jié)點(diǎn)									
			target->next=*pNode;
			printf("數(shù)字太大刪除尾巴\n");
			free(temp);
		}
		else
		{
			temp=target->next;//  刪除普通節(jié)點(diǎn)  找到要刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)target，
                                //使target指向要刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)  轉(zhuǎn)存刪除節(jié)點(diǎn)地址
			target->next=temp->next;	//  然后釋放這個節(jié)點(diǎn)
			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)鏈表還有查找值，判空，求鏈表長度，清空等一系列操作，這些操作與單鏈表那的操作基本相同，這里不進(jìn)行詳細(xì)贅述，在后面的完整代碼中會寫出來。

五.總結(jié)

循環(huán)鏈表相對于單鏈表來說會稍微復(fù)雜一點(diǎn)，主要思想還是和單鏈表差不多的，只不過是將鏈表的首位進(jìn)行相連，但是正是因?yàn)槭孜驳南噙B，便于我們通過任意一個結(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.購買新節(jié)點(diǎn)
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//購買的新節(jié)點(diǎn)  處理完畢
	//2.找到插入位置  （頭插  不用找）
	//3.插入
	pnewnode->next = plist->next;
	plist->next = pnewnode;
	return true;
}
//尾插
bool Insert_tail(PClist plist, ELEMTYPE val)
{
	//assert
	//1.購買新節(jié)點(diǎn)
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//購買的新節(jié)點(diǎn)  處理完畢
	//2.找到插入位置(通過帶前驅(qū)的for循環(huán))
	struct Clist* p = plist;
	for (p; p->next != plist; p = p->next);
	//此時 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.購買新節(jié)點(diǎn)
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//購買的新節(jié)點(diǎn)  處理完畢
	//2.找到插入位置(通過帶前驅(qū)的for循環(huán))
	struct Clist* p = plist;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}
	//此時 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))//不空  則至少存在一個有效值
	{
		return false;
	}
	//1.指針p指向待刪除節(jié)點(diǎn)
	struct Clist* p = plist->next;
	//2.指針q指向待刪除節(jié)點(diǎn)的前一個節(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))//不空  則至少存在一個有效值
	{
		return false;
	}
	//1.指針p指向待刪除節(jié)點(diǎn)(尾刪的話，這里指向尾結(jié)點(diǎn))
	struct Clist* p = plist;
	for (p; p->next != plist; p = p->next);
	//此時 for指向結(jié)束  代表著p指向尾結(jié)點(diǎn)
	//2.指針q指向倒數(shù)第二個節(jié)點(diǎn)
	struct Clist* q = plist;
	for (q; q->next != p; q = q->next);
	//此時 for指向結(jié)束  代表著q指向p的上一個節(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)的上一個節(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;
}
//查找(如果查找到，需要返回找到的這個節(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)鏈表不需要這個操作）
//獲取長度
/*指針p從頭結(jié)點(diǎn)的下一個節(jié)點(diǎn)開始向后跑，如果p再次遇到了頭結(jié)點(diǎn)，
證明p走了一圈回來了，這是有效節(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);
}
//銷毀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");
}

到此這篇關(guān)于C語言循環(huán)鏈表的原理與使用操作的文章就介紹到這了,更多相關(guān)C語言循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

  • C++實(shí)現(xiàn)LeetCode(120.三角形)

    C++實(shí)現(xiàn)LeetCode(120.三角形)

    這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(120.三角形),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • C++使用opencv調(diào)用級聯(lián)分類器來識別目標(biāo)物體的詳細(xì)流程

    C++使用opencv調(diào)用級聯(lián)分類器來識別目標(biāo)物體的詳細(xì)流程

    所謂級聯(lián)分類器其實(shí)就是把分類器按照一定的順序聯(lián)合到一起,下面這篇文章主要給大家介紹了關(guān)于C++使用opencv調(diào)用級聯(lián)分類器來識別目標(biāo)物體的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2022-05-05
  • C++合并二叉樹的思路與示例代碼

    C++合并二叉樹的思路與示例代碼

    二叉樹大家應(yīng)該都不陌生,但是合并二叉樹呢?這篇文章主要給大家介紹了關(guān)于C++合并二叉樹的相關(guān)資料,文中給出了兩種解決的方法,大家可以根據(jù)需要選擇對應(yīng)的方法,需要的朋友可以參考下
    2021-08-08
  • C語言實(shí)現(xiàn)井字棋小游戲

    C語言實(shí)現(xiàn)井字棋小游戲

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)井字棋小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2021-04-04
  • 淺談C++函數(shù)聲明后面加throw()的作用(必看)

    淺談C++函數(shù)聲明后面加throw()的作用(必看)

    下面小編就為大家?guī)硪黄獪\談C++函數(shù)聲明后面加throw()的作用(必看)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
    2017-01-01
  • C語言三子棋小游戲的實(shí)現(xiàn)代碼

    C語言三子棋小游戲的實(shí)現(xiàn)代碼

    這篇文章主要為大家詳細(xì)介紹了C語言三子棋小游戲的實(shí)現(xiàn)代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2020-11-11
  • 詳解C語言基礎(chǔ)的類型轉(zhuǎn)換

    詳解C語言基礎(chǔ)的類型轉(zhuǎn)換

    這篇文章主要為大家介紹了C語言基礎(chǔ)的類型轉(zhuǎn)換，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
    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)換示例

    這篇文章主要為大家介紹了C++實(shí)現(xiàn)主機(jī)字節(jié)序和網(wǎng)絡(luò)字節(jié)序轉(zhuǎn)換示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪
    2023-11-11
  • c語言中十進(jìn)制轉(zhuǎn)二進(jìn)制顯示小工具的實(shí)現(xiàn)代碼

    c語言中十進(jìn)制轉(zhuǎn)二進(jìn)制顯示小工具的實(shí)現(xiàn)代碼

    本篇文章是對c語言中十進(jìn)制轉(zhuǎn)二進(jìn)制顯示小工具的實(shí)現(xiàn)代碼進(jìn)行了詳細(xì)的分析的介紹，需要的朋友參考下
    2013-05-05
  • C++11中強(qiáng)類型枚舉的使用

    C++11中強(qiáng)類型枚舉的使用

    本文主要介紹了C++11中強(qiáng)類型枚舉的使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-02-02

最新評論