文章目錄

一.帶頭雙向回圈鏈表
二.實作
- (1).動態申請一個結點
- (2).創建頭結點進行初始化
- (3).尾插
- (4).尾刪
- (5).頭插
- (6).頭刪
- (7).查找元素
- (8).在pos位置之前進行插入
- (9).洗掉pos位置的結點
- (10).列印資料
三.代碼實作

一.帶頭雙向回圈鏈表

帶頭雙向回圈鏈表：結構最復雜，一般用在單獨存盤資料，實際中使用的鏈表資料結構，都是帶頭雙向回圈鏈表，另外這個鏈表雖然結構復雜，但是使用代碼實作以后會發現能帶來很多優勢.

二.實作

Lish.h中部分宣告

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	LTDataType data;
}ListNode;

prev為結點中的指向前一個結點的指標 , next 為指標中的指向后一個結點的指標 , data為結點中的資料

(1).動態申請一個結點

動態申請一個大小為sizeof(ListNode)的結點

// 動態申請一個結點
ListNode*BuyListNode(LTDataType x)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if(newNode == NULL)
	{
		printf("分配記憶體失敗\n");
		exit(-1);
	}
	newNode->prev = newNode->next = NULL;
	newNode->data = x;
	return newNode;
}

(2).創建頭結點進行初始化

因為為帶頭的雙向回圈鏈表,因此初始化頭結點時，頭結點的prev,next指標都指向自已

// 創建頭結點進行初始化
ListNode* ListInit()
{
	ListNode* plist = BuyListNode(0); // 頭結點中的資料初始化為 0
	plist->prev = plist->next = plist;
	return plist;
}

(3).尾插

通過頭結點的prev指標可以找到尾結點tail，tail->next指向待插入的結點，待插入結點的prev指標指向tail，頭結點的prev指標指向待插入結點，待插入結點的next指向頭結點

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

(4).尾刪

通過頭結點的prev指標找到尾結點tail,通過tail的prev指標找到 tailPrev結點

要使tailPrev成為尾結點,將tailPrev結點和plist頭結點連接到一起

// 尾刪
void ListPopBack(ListNode* plist)
{
	assert(plist);
	assert(plist->next != plist);
	ListNode* tail = plist->prev;
	ListNode* tailPrev = tail->prev;
	tailPrev->next = plist;
	plsit->prev = tailPrev;
	free(tail);
	tail = NULL;
}

(5).頭插

動態申請一個結點newNode,通過plist->next找到當前的第一個結點(first)，newNode結點要插入到plist頭結點和first結點之間

// 頭插
void ListPushFront(ListNode* plist,LTDataType x)
{
	assert(plist);
	ListNode* newNode = BuyListNode(x);
	ListNode* first = plist->next;
	plist->next = newNode;
	newNode->prev = plist;
	newNode->next = first;
	first->prev = newNode;
}

(6).頭刪

通過plist->next找到第一個結點(first),first->next找到第二個結點(second),將plist頭結點和second結點連接到一起,釋放掉第一個結點(first)

// 頭刪
void ListPopFront(ListNode* plist)
{
	assert(plist);
	assert(plist->next != plist);
	ListNode* first = plist->next;
	ListNode* second = first->next;
	plist->next = second;
	second->prev = plist;
	free(first);
	first = NULL;
}

(7).查找元素

遍歷一次鏈表，終止條件為 cur != plist ,因為 cur = plist 說明已經回圈了一遍

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

(8).在pos位置之前進行插入

動態申請一個結點 ,找到pos位置的前一個結點(posPrev),將pos,posPrev,newNode結點連接到一起

// 在pos位置前插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newNode = BuyListNode(x);
	ListNode* posPrev = pos->prev;
	posPrev->next = newNode;
	newNode->prev = posPrev;
	newNode->next = pos;
	pos->prev = newNode;
}

(9).洗掉pos位置的結點

找到pos的前一個結點(posPrev)和后一個結點(posNext),將posPrev,posNext結點連接到一起,洗掉掉pos結點

// 洗掉pos位置的結點
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* PosPrev = pos->prev;
	ListNode* PosNext = pos->next;
	PosPrev->next = PosNext;
	PosNext->prev = PosPrev;
	free(pos);
	pos = NULL;
}

(10).列印資料

遍歷一次鏈表，終止條件為 cur != plist ,因為 cur = plist 說明已經回圈了一遍

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

三.代碼實作

List.h檔案

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	LTDataType data;
}ListNode;
// 初始化創建頭結點
ListNode* ListInit();
// 動態申請一個結點
ListNode* BuyListNode(LTDataType x);
// 列印
void Listprint(ListNode* plist);
// 尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 尾刪
void ListPopBack(ListNode* plist);
// 頭插
void ListPushFront(ListNode* plist, LTDataType x);
// 頭刪
void ListPopFront(ListNode* plist);
// 查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 在pos前插入
void ListInsert(ListNode* pos, LTDataType x);
// 洗掉pos位置的結點
void ListErase(ListNode* pos);

Lish.c檔案

#include"List.h"
// 初始化創建頭結點
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
// 動態申請一個結點
ListNode* BuyListNode(LTDataType x)
{
	ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
	if (NewNode == NULL)
	{
		printf("分配記憶體失敗\n");
		exit(-1);
	}
	NewNode->prev = NewNode->next = NULL;
	NewNode->data = x;
	return NewNode;
}
// 列印
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, LTDataType x)
{
	assert(plist);
	ListNode* NewNode = BuyListNode(x);
	ListNode* tail = plist->prev;
	tail->next = NewNode;
	NewNode->prev = tail;
	plist->prev = NewNode;
	NewNode->next = plist;
}
// 尾刪
void ListPopBack(ListNode* plist)
{
	assert(plist);
	assert(plist->next != plist);
	ListNode* tail = plist->prev;
	ListNode* tail_prev = tail->prev;
	tail_prev->next = plist;
	plist->prev = tail_prev;
	free(tail);
	tail = NULL;
}
// 頭插
void ListPushFront(ListNode* plist, LTDataType x)
{
	assert(plist);
	ListNode* NewNode = BuyListNode(x);
	ListNode* first = plist->next;
	plist->next = NewNode;
	NewNode->prev = plist;
	NewNode->next = first;
	first->prev = NewNode;
}
// 頭刪
void ListPopFront(ListNode* plist)
{
	assert(plist);
	assert(plist->next != plist);
	ListNode* first = plist->next;
	ListNode* second = first->next;
	plist->next = second;
	second->prev = plist;
	free(first);
	first = NULL;
}
// 查找
ListNode* ListFind(ListNode* plist, LTDataType x)
{
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
// 在pos位置前插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* NewNode = BuyListNode(x);
	ListNode* PosPrev = pos->prev;
	PosPrev->next = NewNode;
	NewNode->prev = PosPrev;
	NewNode->next = pos;
	pos->prev = NewNode;
}
// 洗掉pos位置的結點
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* PosPrev = pos->prev;
	ListNode* PosNext = pos->next;
	PosPrev->next = PosNext;
	PosNext->prev = PosPrev;
	free(pos);
	pos = NULL;
}

TestLish.c檔案

#include"List.h"
void TestList01()
{
	ListNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	Listprint(plist);

	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	// ListPopBack(plist);
	Listprint(plist);

	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);
	Listprint(plist);

	ListPopFront(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	// ListPopFront(plist);
	Listprint(plist);
}
void TestList02()
{
	ListNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);

	ListNode* pos = ListFind(plist, 3);
	ListInsert(pos, 30);
	Listprint(plist);
	ListErase(pos);
	Listprint(plist);

}
int main()
{
	TestList01();
	TestList02();
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/274780.html

標籤：其他

上一篇：精寫15篇，學會Python爬蟲 -- （1）開篇：初識爬蟲，基礎鋪墊丨蓄力計劃

下一篇：【C語言學習筆記——2】

雙向回圈鏈表講解及實作