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

来源: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
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類