雙向迴圈鏈表的增刪改查功能

来源:https://www.cnblogs.com/cwp-home/p/18158610
-Advertisement-
Play Games

數據結構 雙向迴圈鏈表 雙向迴圈鏈表的增刪改查 /***************************************************************************************************************** * * file na ...


數據結構

雙向迴圈鏈表

雙向迴圈鏈表的增刪改查

/*****************************************************************************************************************
*	
*	file name	:	DoubleCirLinkedList.c
*	author	 	:	[email protected]
*	data  	 	:	2024/04/24
*	function	:	雙向迴圈鏈表的介面程式
*	note	 	:	None
* 	
*  	CopyRight (c)	2024	[email protected] 	All Right Reseverd
*
* ****************************************************************************************************************/

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<string.h>

//指的是雙向迴圈鏈表中的結點有效數據類型，用戶可以根據需要進行修改
typedef int  DataType_t;

//構造雙向迴圈鏈表的結點,鏈表中所有結點的數據類型應該是相同的
typedef struct DoubleLinkedList
{
	DataType_t  		     data; //結點的數據域
	struct DoubleLinkedList	*prev; //直接前驅的指針域
	struct DoubleLinkedList	*next; //直接後繼的指針域

}DoubleLList_t;


//創建一個空雙向迴圈鏈表，空鏈表應該有一個頭結點，對鏈表進行初始化
DoubleLList_t * DoubleCirLList_Create(void)
{
	//1.創建一個頭結點並對頭結點申請記憶體
	DoubleLList_t *Head = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
	if (NULL == Head)
	{
		perror("Calloc memory for Head is Failed");
		exit(-1);
	}

	//2.對頭結點進行初始化，頭結點是不存儲數據域，指針域指向自身即可，體現“迴圈”
	Head->prev = Head;
	Head->next = Head;

	//3.把頭結點的地址返回即可
	return Head;
}

//創建新的結點，並對新結點進行初始化（數據域 + 指針域）
DoubleLList_t * DoubleCirLList_NewNode(DataType_t data)
{
	//1.創建一個新結點並對新結點申請記憶體
	DoubleLList_t *New = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}

	//2.對新結點的數據域和指針域（2個）進行初始化,指針域指向結點自身，體現“迴圈”
	New->data = data;
	New->prev = New;
	New->next = New;

	return New;
}

/******************************************************************************************************************
*	
*	func name	:	DoubleCirLLinst_HeadInsert
*	function	:	把新結點插入雙向迴圈鏈表中的頭部
*	retval		:	bool
*	note		:	None
*	author	 	:	[email protected]
*	date  	 	:	2024/04/24
*
* ****************************************************************************************************************/

//頭插
bool DoubleCirLLinst_HeadInsert(DoubleLList_t *Head,DataType_t data)
{
	//1.創建新結點，並對新結點進行初始化
	DoubleLList_t *New = DoubleCirLList_NewNode(data);
	if (NULL == New)
	{
		printf("Can not insert new node\n");
		return false;
	}
	
	//2.判斷迴圈雙向鏈表是否為空，如果為空，則直接插入即可
	if (Head->next == Head)
	{
		Head->next = New;
		return true;
	}
	
	//3.如果迴圈雙向鏈表為非空，則把新結點插入鏈表頭部
	Head->next->prev->next = New;	//把尾結點的next指針指向新結點

	New->prev = Head->next->prev;	//把新結點的prev指針指向尾結點

	New->next = Head->next;			//把新結點的next指針指向原本首結點

	Head->next->prev = New;			//把原本首結點的prev指針指向新結點

	Head->next = New;				//把頭結點的next指針指向新結點
	return true;
}

/******************************************************************************************************************
*	
*	func name	:	DoubleCirLLinst_TailInsert
*	function	:	把新結點插入雙向迴圈錶鏈中的尾部
*	retval		:	bool
*	note		:	None
*	author	 	:	[email protected]
*	date  	 	:	2024/04/24
*
* ****************************************************************************************************************/

//尾插
bool DoubleCirLLinst_TailInsert(DoubleLList_t *Head,DataType_t data)
{
	//1.創建新結點，並對新結點進行初始化
	DoubleLList_t *New = DoubleCirLList_NewNode(data);
	if (NULL == New)
	{
		printf("Can not insert new node\n");
		return false;
	}
	
	//2.判斷迴圈雙向鏈表是否為空，如果為空，則直接插入即可
	if (Head->next == Head)
	{
		Head->next = New;
		return true;
	}

	//3.如果迴圈雙向鏈表為非空，則把新結點插入鏈表頭部
	New->prev= Head->next->prev;	//把新結點的prev指針指向原本的尾結點

	Head->next->prev->next = New;	//把原本的尾結點的next指針指向新結點

	New->next = Head->next;			//把新結點的next指針指向首結點

	Head->next->prev = New;			//把首結點的prev指針指向新結點
	return true;
}

/******************************************************************************************************************
*	
*	func name	:	DoubleCirLLinst_DestInsert
*	function	:	把新結點插入雙向迴圈鏈表中的指定元素的尾部
*	retval		:	bool
*	note		:	None
*	author	 	:	[email protected]
*	date  	 	:	2024/04/24
*
* ****************************************************************************************************************/

//指定插
bool DoubleCirLLinst_DestInsert(DoubleLList_t *Head,DataType_t destval,DataType_t data)
{
	//1.創建新結點，並對新結點進行初始化
	DoubleLList_t *New = DoubleCirLList_NewNode(data);
	if (NULL == New)
	{
		printf("Can not insert new node\n");
		return false;
	}
	
	//2.判斷迴圈雙向鏈表是否為空，如果為空，則直接插入即可
	if (Head->next == Head)
	{
		Head->next = New;
		return true;
	}

	//3.如果迴圈雙向鏈表為非空，則把新結點插入鏈表中指定元素的尾部
	DoubleLList_t *Phead = Head->next;	//備份首結點地址，防止首結點丟失
	while (Phead->next != Head->next)
	{	
		if (Phead->data == destval)
		{
			break;
		}
		Phead = Phead->next;
	}

	//如果遍歷鏈表之後發現沒有目標結點，則退出即可
	if (Phead->next == Head->next && Phead->data != destval)
	{
		printf("dest node is not found\n");
		return false;
	}
	
	//如果遍歷鏈表找到目標結點，則分為(頭部 or 尾部 or 中間)

	// if (Phead == Head->next)
	// {
	// 	New->prev = Head->next;		//把新結點的prev指針指向首結點

	// 	New->next = Head->next;		//把新結點的next指針指向首結點

	// 	Head->next->next = New;		//把首結點的next指針指向新結點

	// 	Head->next->prev = New;		//把首結點的prev指針指向新結點

	//	}
	if (Phead->next == Head->next)
	{
		New->next = Head->next;		//把新結點的next指針指向首結點

		New->prev = Phead;			//把新結點的prev指針指向原本的尾結點

		Phead->next = New;			//把原本的尾結點的next指針指向新結點

		Head->next->prev = New;		//把首結點的prev指針指向新結點
	}else
	{
		New->next = Phead->next;	//把新結點的next指針指向指定結點的直接後繼

		Phead->next->prev = New;	//把指定結點的直接後繼的prev指針指向新結點

		New->prev = Phead;			//把新結點的prev指針指向指定節點
	
		Phead->next = New;			//把指定節點的next指針指向新結點
	}
	
	return true;
}

/******************************************************************************************************************
*	
*	func name	:	DoubleCirLLinst_HeadDel
*	function	:	刪除雙向迴圈鏈表的頭部結點
*	retval		:	bool
*	note		:	None
*	author	 	:	[email protected]
*	date  	 	:	2024/04/24
*
* ****************************************************************************************************************/

//頭刪
bool DoubleCirLLinst_HeadDel(DoubleLList_t *Head)
{
	//1.判斷當前鏈表是否為空，為空則直接退出
	if (Head->next == Head)
	{
		printf("current linkedlist is empty!\n");
		return false;
	}

	//2.判斷鏈表中是否只有首結點
	if (Head->next == Head->next->next)
	{
		Head->next = Head;	//頭結點的next指針指向頭結點，體現“迴圈”

		free(Head->next);	//釋放首結點記憶體

		return true;
	}
	

	//3.如果當前鏈表為非空，則刪除當前鏈表的頭部結點
	DoubleLList_t *Phead = Head->next;			//備份首結點地址
	
	Head->next->prev->next = Head->next->next;	//把尾結點的next指針指向首結點的直接後繼

	Head->next->next->prev = Head->next->prev;	//把首結點的直接後繼的prev指針指向尾結點

	Head->next =Phead->next;					//把頭結點的next指針指向首結點的直接後繼
	
	Phead->next = Phead;						//把首結點的next指針指向首結點

	Phead->prev = Phead;						//把首結點的prev指針指向首結點
	
	free(Phead);								//釋放首結點記憶體

	return true;
}

/******************************************************************************************************************
*	
*	func name	:	DoubleCirLLinst_TailDel
*	function	:	刪除雙向迴圈鏈表的尾部結點
*	retval		:	bool
*	note		:	None
*	author	 	:	[email protected]
*	date  	 	:	2024/04/24
*
* ****************************************************************************************************************/

//尾刪
bool DoubleCirLLinst_TailDel(DoubleLList_t *Head)
{
	//1.判斷當前鏈表是否為空，為空則直接退出
	if (Head->next == Head)
	{
		printf("current linkeflist is empty!\n");
		return false;
	}

	//2.判斷鏈表中是否只有首結點
	if (Head->next == Head->next->next)
	{
		Head->next = Head;	//頭結點的next指針指向頭結點，體現“迴圈”

		free(Head->next);	//釋放首結點記憶體

		return true;
	}

	//3.如果當前鏈表為非空，則刪除當前鏈表的尾部結點
	DoubleLList_t *Phead = Head->next->prev;	//備份尾結點地址

	Head->next->prev->prev->next = Head->next;	//把尾結點的直接前驅的next指針指向首結點

	Head->next->prev = Head->next->prev->prev;	//把首結點的prev指針指向尾結點的直接前驅

	Phead->next = Phead;						//把尾結點的next指針指向尾結點

	Phead->prev = Phead;						//把尾結點的prev指針指向尾結點

	free(Phead);								//釋放尾結點記憶體

	return true;
}

/******************************************************************************************************************
*	
*	func name	:	DoubleCirLLinst_DestDel
*	function	:	刪除雙向迴圈鏈表的指定結點
*	retval		:	bool
*	note		:	None
*	author	 	:	[email protected]
*	date  	 	:	2024/04/24
*
* ****************************************************************************************************************/

//指定刪
bool DoubleCirLLinst_DestDel(DoubleLList_t *Head,DataType_t destval)
{
	//1.判斷當前鏈表是否為空，為空則直接退出
	if (Head->next == Head)
	{
		printf("current linkeflist is empty!\n");
		return false;
	}

	//2.判斷鏈表中是否只有首結點
	if (Head->next == Head->next->next)
	{
		Head->next = Head;	//頭結點的next指針指向頭結點，體現“迴圈”

		free(Head->next);	//釋放首結點記憶體

		return true;
	}

	//3.如果當前鏈表為非空，則刪除當前鏈表的指定結點
	DoubleLList_t *Phead = Head->next;	//備份首結點地址
	while (Phead->next != Head->next)
	{
		if (Phead->data == destval)
		{
			break;
		}
		Phead = Phead->next;
	}

	//如果遍歷鏈表之後發現沒有目標結點，則退出即可
	if (Phead->next == Head->next && Phead->data != destval)
	{
		printf("dest node is not found\n");
		return false;
	}

	//如果遍歷鏈表找到目標結點，則分為(頭部 or 尾部 or 中間)
	if (Phead == Head->next)
	{
		
		Head->next->prev->next = Head->next->next;	//把尾結點的next指針指向首結點的直接後繼

		Head->next->next->prev = Head->next->prev;	//把首結點的直接後繼的prev指針指向尾結點

		Head->next = Head->next->next; 				//把頭結點的next指針指向首結點的直接後繼

		Phead->next = Phead;						//把首結點的next指針指向首結點

		Phead->prev = Phead;						//把首結點的prev指針指向首結點

		
		free(Phead);								//釋放首結點記憶體

	}else if (Phead->next == Head->next)
	{
		Phead->prev->next = Head->next;		//把尾結點的直接前驅的next指針指向首結點

		Head->next->prev = Phead->prev;		//把首結點的prev指針指向尾結點的直接前驅

		Phead->next = Phead;				//把尾結點的next指針指向尾結點

		Phead->prev = Phead;				//把尾結點的prev指針指向尾結點

		free(Phead);						//釋放尾結點記憶體

	}else
	{
		Phead->prev->next = Phead->next;	//把指定結點的直接前驅的next指針指向指定結點的直接後繼

		Phead->next->prev = Phead->prev;	//把指定結點的直接後繼的prev指針指向指定結點的直接前驅

		Phead->next = Phead;				//把指定結點的next指針指向指定結點

		Phead->prev = Phead;				//把指定結點的prev指針指向指定結點

		free(Phead);						//釋放指定結點的記憶體
	}
	
	return true;
}

/******************************************************************************************************************
*	
*	func name	:	DoubleCirLLinst_Print
*	function	:	遍歷雙向迴圈鏈表並輸出鏈表中的數據域
*	retval		:	bool
*	note		:	None
*	author	 	:	[email protected]
*	date  	 	:	2024/04/24
*
* ****************************************************************************************************************/

//遍歷雙向迴圈鏈表
bool DoubleCirLLinst_Print(DoubleLList_t *Head)
{
	//1.判斷當前雙向迴圈鏈表是否為空，為空則直接退出
	if (Head->next == Head)
	{
		printf("current linkeflist is empty!\n");
		
		return false;
	}
	//2.從首結點開始遍歷鏈表
	DoubleLList_t *Phead = Head;	 //備份頭結點地址，防止頭結點丟失
	while (Phead->next)
	{
		Phead = Phead->next;		 //把頭結點的直接後繼作為新的頭結點

		printf("%d->",Phead->data);	 //輸出頭結點的直接後繼的數據域

		if (Phead->next == Head->next)//判斷是否到達尾結點，尾結點的next指針是指向首結點的地址
		{
			break;
		}
		
	}
	return true;
	
}

int main(int argc, char const *argv[])
{
	//創建雙向迴圈鏈表
	DoubleLList_t *Head = DoubleCirLList_Create();

	//頭插
	DoubleCirLLinst_HeadInsert(Head,5);
	DoubleCirLLinst_HeadInsert(Head,56);
	DoubleCirLLinst_HeadInsert(Head,35);
	DoubleCirLLinst_HeadInsert(Head,20);
	DoubleCirLLinst_HeadInsert(Head,8);
	DoubleCirLLinst_Print(Head);
	printf("\n");

	// //尾插
	DoubleCirLLinst_TailInsert(Head,61);
	DoubleCirLLinst_TailInsert(Head,9);
	DoubleCirLLinst_TailInsert(Head,4);
	DoubleCirLLinst_TailInsert(Head,18);
	DoubleCirLLinst_TailInsert(Head,40);
	DoubleCirLLinst_Print(Head);
	printf("\n");

	//指定插
	DoubleCirLLinst_DestInsert(Head,5,21);
	DoubleCirLLinst_DestInsert(Head,40,89);
	DoubleCirLLinst_Print(Head);
	printf("\n");

	// 頭刪
	DoubleCirLLinst_HeadDel(Head);
	DoubleCirLLinst_HeadDel(Head);
	DoubleCirLLinst_Print(Head);
	printf("\n");
	
	// 尾刪
	DoubleCirLLinst_TailDel(Head);
	DoubleCirLLinst_TailDel(Head);
	DoubleCirLLinst_Print(Head);
	printf("\n");
	
	// //指定刪
	DoubleCirLLinst_DestDel(Head,5);
	DoubleCirLLinst_DestDel(Head,61);
	DoubleCirLLinst_Print(Head);
	printf("\n");


	return 0;
}

結果驗證：

image


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • kvm網路，docker網路,，vm網路
    一：vmware網路 1：概念的介紹 虛擬網路編輯器：控制的就是虛擬機的網段的 window中的適配器：更這個虛擬網路編輯器連在一起的，是同一個網段，通常是分配的.1的IP地址 2：橋接模式 原理：就是將虛擬機的物理網卡橋接到物理主機上面，實現了訪問外網的操作 圖解： 操作：就是將虛擬機的ip地址， ...
  • linux中limits.conf和sysctl.conf需做哪些優化
    limits.conf 和 sysctl.conf 是 Linux 系統中用於配置用戶資源限制和系統內核參數的兩個重要配置文件。針對這兩個文件進行優化，可以幫助提升系統的安全性和性能。 limits.conf 的優化 limits.conf 是 PAM（Pluggable Authenticatio ...
  • kube-state-metrics和cAdvisorc結合使用的好處
    kube-state-metrics是Kubernetes監控系統的重要組成部分，它提供了對集群中對象狀態的實時監控。具體來說，kube-state-metrics通過監聽API Server生成有關資源對象的狀態指標，比如Deployment、Node、Pod等。kube-state-metric ...
  • 習題---利用兩個棧實現隊列的“入隊”和“出隊”
    利用兩個棧進行實現隊列的入隊和出隊操作 題目： 解題分析： ​ 該題目需要藉助兩個棧來實現隊列的“入隊”和“出隊”，並封裝好了三個對應的函數。我們需要註意的是棧的特點是“先進後出",與隊列的”先進先出“的輸出並不一致。所以，我們要利用棧來輸出正常排序的序列，需要藉助類似取反的原理，例如 ！false ...
  • 能源管理系統EMS與IEC61850
    隊列 原理介紹： ​ 隊列（Queue）和棧類似，相同點是都屬於線性結構，不同點是棧遵循“後進先出”原則，而隊列遵循“*先進先出*”的原則，也被稱為“FIFO”結構，就是“First Input First Output” ​ 數據結構中的隊列的兩端都允許操作，只不過要求數據只能從隊列的一端插入，從 ...
  • 以鏈表為基礎實現鏈式隊列
    數據結構 鏈式隊列 以鏈表為基礎實現鏈式隊列 1.思路： 如果打算以鏈表作為基礎來實現隊列的操作，可以避免記憶體浪費以及避免記憶體成片移動，只需要確定隊頭和隊尾即可，一般把鏈表頭部作為隊頭，可以實現頭刪，把鏈表尾部作為隊尾，可以實現尾插。 2.圖示： 3.代碼： /******************* ...
  • Linux啟動過程以及7種運行級別
    題目： ​ 輸入一個包括 '(' 和 ')' 的字元串string ，判斷字元串是否有效。要求設計演算法實現檢查字元串是否有效，有效的字元串需滿足以下條件： A. 左括弧必須用相同類型的右括弧閉合。 B. 左括弧必須以正確的順序閉合。 C. 每個右括弧都有一個對應的相同類型的左括弧。 題目分析： ​ ...
  • Centos7使用Nginx配置HTTPS正向代理
    Nginx預設安裝只支持代理HTTP, 不支持代理 HTTPS, 如果需要支持HTTPS需要在Nginx編譯時加入 ngx_http_proxy_connect_module. ...
一周排行
    -Advertisement-
    Play Games
  • 如何基於surging跨網關跨語言進行緩存降級
    基於.NET Framework 4.8 開發的深度學習模型部署測試平臺，提供了YOLO框架的主流系列模型，包括YOLOv8~v9，以及其系列下的Det、Seg、Pose、Obb、Cls等應用場景，同時支持圖像與視頻檢測。模型部署引擎使用的是OpenVINO™、TensorRT、ONNX runti... ...
  • 十年沉澱，重啟開發之路
    十年沉澱，重啟開發之路 十年前，我沉浸在開發的海洋中，每日與代碼為伍，與演算法共舞。那時的我，滿懷激情，對技術的追求近乎狂熱。然而，隨著歲月的流逝，生活的忙碌逐漸占據了我的大部分時間，讓我無暇顧及技術的沉澱與積累。 十年間，我經歷了職業生涯的起伏和變遷。從初出茅廬的菜鳥到逐漸嶄露頭角的開發者，我見證了 ...
  • C#.NET體系圖文概述—2024最全總結
    C# 是一種簡單、現代、面向對象和類型安全的編程語言。.NET 是由 Microsoft 創建的開發平臺，平臺包含了語言規範、工具、運行，支持開發各種應用，如Web、移動、桌面等。.NET框架有多個實現，如.NET Framework、.NET Core（及後續的.NET 5+版本），以及社區版本M... ...
  • 班級擂臺（光榮）榜 - 極簡教育小工具
    前言 本文介紹瞭如何使用三菱提供的MX Component插件實現對三菱PLC軟元件數據的讀寫，記錄了使用電腦模擬，模擬PLC，直至完成測試的詳細流程，並重點介紹了在這個過程中的易錯點，供參考。 用到的軟體： 1. PLC開發編程環境GX Works2，GX Works2下載鏈接 https:// ...
  • web server apache tomcat11-31-websocket
    前言 整理這個官方翻譯的系列，原因是網上大部分的 tomcat 版本比較舊，此版本為 v11 最新的版本。 開源項目 從零手寫實現 tomcat minicat 別稱【嗅虎】心有猛虎，輕嗅薔薇。 系列文章 web server apache tomcat11-01-官方文檔入門介紹 web serv ...
  • day31-jQuery
    1、jQuery介紹 jQuery是什麼 jQuery是一個快速、簡潔的JavaScript框架，是繼Prototype之後又一個優秀的JavaScript代碼庫（或JavaScript框架）。jQuery設計的宗旨是“write Less，Do More”，即倡導寫更少的代碼，做更多的事情。它封裝 ...
  • aardio爬蟲) 實戰篇：逆向有道翻譯web介面
    前言 之前的文章把js引擎(aardio封裝庫) 微軟開源的js引擎(ChakraCore))寫好了，這篇文章整點js代碼來測一下bug。測試網站：https://fanyi.youdao.com/index.html#/ 逆向思路 逆向思路可以看有道翻譯js逆向（MD5加密，AES加密）附完整源碼 ...
  • 面試官：這就是你理解的Java多線程基礎？
    引言 現代的操作系統（Windows，Linux，Mac OS）等都可以同時打開多個軟體（任務），這些軟體在我們的感知上是同時運行的，例如我們可以一邊瀏覽網頁，一邊聽音樂。而CPU執行代碼同一時間只能執行一條，但即使我們的電腦是單核CPU也可以同時運行多個任務，如下圖所示，這是因為我們的 CPU 的 ...
  • Python文本統計與分析從基礎到進階
    掌握使用Python進行文本英文統計的基本方法，並瞭解如何進一步優化和擴展這些方法，以應對更複雜的文本分析任務。 ...
  • Redis多數據源，看這篇就夠了
    背景 Redis多數據源常見的場景： 分區數據處理：當數據量增長時，單個Redis實例可能無法處理所有的數據。通過使用多個Redis數據源，可以將數據分區存儲在不同的實例中，使得數據處理更加高效。 多租戶應用程式：對於多租戶應用程式，每個租戶可以擁有自己的Redis數據源，以確保數據隔離和安全性。 ...
所有分類