快捷導(dǎo)航

C語言手把手帶你掌握帶頭雙向循環(huán)鏈表

更新時間：2022年04月22日 11:06:20 作者：平凡的人1

帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)反而簡單

前言

關(guān)于鏈表這一塊，寫了多篇博客，學(xué)習(xí)了順序表、單鏈表、及其一些練習(xí)題

順序表：傳送門：順序表

單鏈表：傳送門：單鏈表1 鏈表2

鏈表OJ：傳送門：鏈表OJ

今天，我又來水一水博客，介紹關(guān)于雙鏈表。

帶頭雙向循環(huán)鏈表的結(jié)構(gòu)

實際上，單鏈表也存在一個比較大的缺陷：

1.不能從后往前遍歷

2.無法找到前驅(qū)

除了單鏈表之外，我們自然還有雙向鏈表，我們要說的就是帶頭雙向循環(huán)鏈表，簡單理解為：帶頭結(jié)點的，有兩個方向的。循環(huán)的。結(jié)構(gòu)圖如下：

結(jié)構(gòu)雖然比較復(fù)雜，但是極大方便我們找結(jié)點，比如可以直接找到尾結(jié)點，然后再進入相關(guān)的操作。實際代碼的操作將會比單鏈表簡單，極為方便，這里不做過多說明，直接上手代碼

代碼操作

我們直奔主題，進入代碼實現(xiàn)的操作，之前的操作如果理解了，那我相信這個對于你來說肯定是不難的。下面直接給出源碼：

List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>
#include <stdbool.h>
typedef int LTDataType;
//帶頭雙向循環(huán)--最優(yōu)鏈表結(jié)構(gòu)，在任意位置插入刪除數(shù)據(jù)都是O（1）
typedef struct listNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}ListNode;
//初始化
ListNode*ListInit();
//銷毀
void ListDestory(ListNode* phead);
//打印
void ListPrint(ListNode* phead);
//尾插
void ListPushBack(ListNode* phead, LTDataType x);
//頭插
void ListPushFront(ListNode* phead, LTDataType x);
//頭刪
void ListPopFront(ListNode* phead);
//尾刪
void ListPopBack(ListNode* phead);
ListNode* ListFind(ListNode* phead, LTDataType x);
//在pos位置之前插入x
void ListInsert(ListNode* pos, LTDataType x);
//刪除pos位置的值
void ListErase(ListNode* pos);

List.c

#include "List.h"
//開辟一個新結(jié)點
ListNode* BuyListNode(LTDataType x)
{
	ListNode* newnode =(ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
//初始化
ListNode* ListInit()
{
	ListNode*phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
//銷毀
void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}
//打印
void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
//尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
//頭插
void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* first = phead->next;
	ListNode* newnode = BuyListNode(x);
	newnode->next = first;
	first->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
}
//頭刪
void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* first = phead->next;
	ListNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
	first = NULL;
}
//尾刪
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;
	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;
}
ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
//在pos位置之前插入x
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
//刪除pos位置的值
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}

Test.c

#include "List.h"
void TestList1()
{
	ListNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);
	ListPushFront(plist, 0);
	ListPushFront(plist, -1);
	ListPrint(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);
	ListPopBack(plist);
	ListPrint(plist);
}
void TestList2()
{
	ListNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);
	ListNode* pos = ListFind(plist, 3);
	if (pos)
	{
		pos->data *= 10;
		printf("找到了,并且*10\n");
	}
	else
	{
		printf("沒找到\n");
	}
	ListPrint(plist);
	ListInsert(pos, 300);
	ListPrint(plist);
	ListErase(pos);
	ListPrint(plist);
}
int main()
{
	TestList2();
	return 0;
}

到此這篇關(guān)于C語言手把手帶你掌握帶頭雙向循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C語言帶頭雙向循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: