日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言中雙鏈表的基本操作_C 語言

作者：安河橋畔 ? 更新時間： 2023-04-06 編程語言

帶頭結點的雙向循環鏈表

鏈表結構如下：

每個節點都有一個數據域和兩個指針域，這兩個指針分別指向鏈表的前驅節點和后繼節點，頭節點的前驅節點是鏈表的最后一個節點，鏈表最后一個節點的后繼節點是頭節點。

正因為如此，帶頭結點的雙向循環鏈表沒有空節點，在進行遍歷時，循環條件也與單鏈表不同：

單鏈表用cur->next為空判斷當前節點是否為最后一個節點，帶頭的雙向循環鏈表則需判斷cur->next是否等于頭節點。

定義：

typedef int DataType;
typedef struct ListNode
{
	DataType data;//數據域
	struct ListNode* next;//指向下一個節點
	struct ListNode* prev;//指向前一個節點
}ListNode;

基本操作

創建

創建鏈表需要先申請一段內存，然后再進行賦值，這里BuyListNode函數用于申請內存空間，在插入節點時，也需要調用BuyListNode函數。

申請節點：

static ListNode* BuyListNode(int x)
{
	ListNode* newNode = NULL;
	newNode = (ListNode*)malloc(sizeof(ListNode));//為節點動態申請一段內存
	if (NULL == newNode)
	{
		assert(0);
		return NULL;
	}
	//為申請的節點賦值
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}

創建鏈表：

ListNode* ListCreate()
{
	ListNode*head=BuyListNode(0);//調用申請節點的函數
	//為頭節點指針域賦值，鏈表為空時，prev和next都指向頭節點
	head->next = head;
	head->prev = head;
	return head;
}

銷毀

使用鏈表時會申請內存空間，所使用完畢后要進行釋放，避免內存泄漏，這里銷毀鏈表用了頭刪的思想，每次刪除鏈表中的第一個節點并釋放空間，具體過程如圖：

循環執行上述過程，直到鏈表為空，最后再釋放頭節點空間。

程序如下：

void ListDestory(ListNode** plist)
{
	assert(plist);
	ListNode* cur = (*plist)->next;
	while (cur!=(*plist))
	{
		(*plist)->next = cur->next;
		free(cur);
		cur = (*plist)->next;
	}
	free(*plist);
	*plist = NULL;
}

這里需要注意的是，銷毀鏈表要改變鏈表頭結點的指向，所以傳參時需要傳二級指針。在對帶頭結點的雙鏈表的操作中，只有銷毀會改變指向頭結點的指針plist的指向，所以只有銷毀時需要傳二級指針，其余操作傳一級指針即可。

打印

鏈表打印的思想比較簡單，只需要遍歷打印即可。

程序：

void ListPrint(ListNode* plist)
{
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)//遍歷的循環條件
	{
		printf("%d--->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

尾插法

步驟

  • 申請新節點newNode
  • 對newNode的prev和next進行賦值
  • 使原鏈表最后一個節點的next指向新節點
  • 鏈表頭指針的prev指向新節點

void ListPushBack(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* newNode =BuyListNode(x);
	newNode->prev = plist->prev;
	newNode->next = plist;
	plist->prev->next = newNode;
	plist->prev = newNode;
}

尾刪

刪除節點時需要先判斷鏈表是否為空，先寫出鏈表判空的方法

鏈表判空

看plist->next是否等于plist即可判斷鏈表是否為空

static int IsEmpty(ListNode*plist)
{
	assert(plist);
	if (plist->next == plist)
	{
		return 1;//鏈表為空，返回1
	}
	return 0;//鏈表非空，返回0
}

尾刪法

步驟

  • 用del標記最后一個節點
  • 使del前一個節點的next指向頭節點
  • 頭結點的prev指向del的前一個節點
  • 釋放del的空間
  • 這里中間兩步將del節點從鏈表中移除出來，最后一步則釋放內存空間
  • 如圖：

程序

void ListPopBack(ListNode * plist)
{
	assert(plist);
	if (IsEmpty(plist))
	{
		return;
	}
	ListNode* del = plist->prev;
	del->prev->next = plist;
	plist->prev = del->prev;
	free(del);
	del = NULL;
}

頭插

步驟

  • 申請新節點newNode
  • 使新節點的prev指向頭節點
  • 令新節點的next指向原來鏈表第二個節點
  • 令原來第二個節點的prev指向newNode
  • 令頭節點的next指向newNode

程序

void ListPushFront(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* newNode = BuyListNode(0);
	newNode->prev = plist;
	newNode->next = plist->next;

	plist->next->prev = newNode;
	plist->next = newNode;
}

頭刪

  • 用del標記鏈表的第一個節點
  • 令頭結點的next指向del->next
  • 原鏈表中第二個節點的prev指向頭節點，成為新的第一個節點
  • 釋放刪除節點的空間

程序

void ListPopFront(ListNode* plist)
{
	assert(plist);
	if (IsEmpty(plist))//先判空
	{
		return;
	}
	ListNode* del = plist->next;

	plist->next = del->next;
	del->next->prev = plist;

	free(del);
	del = NULL;
}

查找元素位置

對鏈表進行遍歷，比對，找到與目標值相等的數時，返回當前的地址

ListNode* ListFind(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

任意位置插入

由于雙鏈表有兩個指針域，所以可以在pos位置的前面進行插入

步驟

  • 申請一個新節點newNode
  • 為新節點的prev和next賦值，使其分別指向pos的前一個節點和pos
  • 使原來pos前一個節點的next指向新節點
  • 令pos的prev指向新節點

void ListInsert(ListNode* pos, DataType x)
{
	assert(pos);
	ListNode* newNode = BuyListNode(x);
	//在pos前面插入
	newNode->prev = pos->prev;
	newNode->next = pos;

	pos->prev->next = newNode;
	pos->prev = newNode;
}

任意位置刪除

刪除給定的節點pos

  • pos前一個節點的next指向pos的下一個節點
  • pos下一個節點的prev指向pos的前一個節點
  • 釋放pos占用的內存空間

程序

void ListErase(ListNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;	
}

完整代碼及測試

work.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<Windows.h>
typedef int DataType;
typedef struct ListNode
{
	DataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

ListNode* ListCreate();// 創建返回鏈表的頭結點.
void ListDestory(ListNode** plist);// 雙向鏈表銷毀
void ListPrint(ListNode* plist);// 雙向鏈表打印
void ListPushBack(ListNode* plist, DataType x);// 雙向鏈表尾插
void ListPopBack(ListNode* plist);// 雙向鏈表尾刪
void ListPushFront(ListNode* plist, DataType x);// 雙向鏈表頭插
void ListPopFront(ListNode* plist);// 雙向鏈表頭刪
ListNode* ListFind(ListNode* plist, DataType x);// 雙向鏈表查找
void ListInsert(ListNode* pos, DataType x);// 雙向鏈表在pos的前面進行插入
void ListErase(ListNode* pos);// 雙向鏈表刪除pos位置的節點

work.c

#include"work.h"

//申請節點
static ListNode* BuyListNode(int x)
{
	ListNode* newNode = NULL;
	newNode = (ListNode*)malloc(sizeof(ListNode));//為節點動態申請一段內存
	if (NULL == newNode)
	{
		assert(0);
		return NULL;
	}
	//為申請的節點賦值
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}


//創建鏈表
ListNode* ListCreate()
{
	ListNode*head=BuyListNode(0);//調用申請節點的函數
	//為頭節點指針域賦值，鏈表為空時，prev和next都指向頭節點
	head->next = head;
	head->prev = head;
	return head;
}

//銷毀鏈表
void ListDestory(ListNode** plist)
{
	assert(plist);
	ListNode* cur = (*plist)->next;
	while (cur!=(*plist))
	{
		(*plist)->next = cur->next;
		free(cur);
		cur = (*plist)->next;
	}
	free(*plist);
	*plist = NULL;
}

// 打印鏈表
void ListPrint(ListNode* plist)
{
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		printf("%d--->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

//尾插法
void ListPushBack(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* newNode =BuyListNode(x);
	newNode->prev = plist->prev;
	newNode->next = plist;
	plist->prev->next = newNode;
	plist->prev = newNode;
}

//判斷鏈表是否為空
static int IsEmpty(ListNode*plist)
{
	assert(plist);
	if (plist->next == plist)
	{
		return 1;
	}
	return 0;
}

// 尾刪法
void ListPopBack(ListNode * plist)
{
	assert(plist);
	if (IsEmpty(plist))
	{
		return;
	}
	ListNode* del = plist->prev;
	del->prev->next = plist;
	plist->prev = del->prev;
	free(del);
	del = NULL;
}

// 雙向鏈表頭插
void ListPushFront(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* newNode = BuyListNode(0);
	newNode->prev = plist;
	newNode->next = plist->next;

	plist->next->prev = newNode;
	plist->next = newNode;
}

// 雙向鏈表頭刪
void ListPopFront(ListNode* plist)
{
	assert(plist);
	if (IsEmpty(plist))
	{
		return;
	}
	ListNode* del = plist->next;

	plist->next = del->next;
	del->next->prev = plist;

	free(del);
	del = NULL;
}

// 查找元素位置
ListNode* ListFind(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

// 任意位置插入
void ListInsert(ListNode* pos, DataType x)
{
	assert(pos);
	ListNode* newNode = BuyListNode(x);
	//在pos前面插入
	newNode->prev = pos->prev;
	newNode->next = pos;

	pos->prev->next = newNode;
	pos->prev = newNode;
}

//任意位置刪除
void ListErase(ListNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
	
}

main.c

#include"work.h"
int main()
{
	ListNode*plist= ListCreate();//創建一個雙向非循環鏈表

    //尾插五個節點
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPrint(plist);
    //頭插一個節點
	ListPushFront(plist, 0);
	ListPrint(plist);
    //尾刪一個節點
	ListPopBack(plist);
	ListPrint(plist);
    //頭刪一個節點
	ListPopFront(plist);
	ListPrint(plist);
    //在元素3前面插入一個節點
	ListInsert(ListFind(plist,3),9);
	ListPrint(plist);
    //刪除值為9的節點
	ListErase(ListFind(plist,9));
	ListPrint(plist);
    //銷毀鏈表
	ListDestory(&plist);
	system("pause");
	return 0;
}

測試結果：

總結

原文鏈接：https://blog.csdn.net/qq_44631587/article/details/122998309

欄目分類
最近更新