文章目錄

- ==也歡迎大家能來到我們小伙伴的社區 [慧編程開源俱樂部](https://bbs.csdn.net/forums/mzt)==
雙鏈表
- - 雙鏈表結構圖
  - 雙鏈表節點
  - 雙鏈表初始化函式ListInit
  - 雙鏈表尾插函式ListPushBack
  - 雙鏈表列印函式ListPrint
  - 雙鏈表尾刪函式ListPopBack
  - 雙鏈表頭插函式ListPushFront
  - 獲得雙鏈表節點函式BuyListNode
  - 雙鏈表頭刪函式ListPopFront
  - 雙鏈表查找函式ListFind
  - 雙鏈表插入函式ListInsert（pos之前插入因為c++中就是之前插入的）
  - 雙鏈表洗掉函式ListErase（洗掉pos）
  - 雙鏈表銷毀函式ListDestroy(實際上我在這里寫報錯了，前面一個函式有bug，但是找到了)
- 代碼
- - DoubleList.h
  - DoubleList.c
  - test.c
- ==也歡迎大家能來到我們小伙伴的社區 [慧編程開源俱樂部](https://bbs.csdn.net/forums/mzt)==

也歡迎大家能來到我們小伙伴的社區慧編程開源俱樂部

雙鏈表

雙鏈表結構圖

雙鏈表節點

typedef int LTDataType;  //C++中的雙鏈表是用list表示的

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

雙鏈表初始化函式ListInit

//雙鏈表初始化函式
LTNode* ListNodeInit()
{
	//創建一個雙鏈表哨兵位頭結點  不存盤有效資料  回圈
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

雙鏈表尾插函式ListPushBack

//雙鏈表尾插函式
void ListNodePushBack(LTNode* phead, LTDataType x)
{
	assert(phead);//實際上phead永遠也不可能是NULL
	LTNode* tail = phead->prev;
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

雙鏈表列印函式ListPrint

//雙鏈表列印函式
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

雙鏈表尾刪函式ListPopBack

//雙鏈表尾刪函式
void ListPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* cur = phead->prev;
	tail = tail->prev;
	tail->next = phead;
	phead->prev = tail;
	free(cur);
}

雙鏈表頭插函式ListPushFront

//雙鏈表頭插函式
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* next = phead->next;//在next和phead中間插一個節點
	/*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;*/
	LTNode* newnode = BuyListNode(x);
	newnode->next = next;
	next->prev = newnode;
	phead->next = newnode;
}

既然我們頭插尾插都遇到了添加節點，所以我們把添加節點的部分抽離出來重新封裝一下

獲得雙鏈表節點函式BuyListNode

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-deIyyV9h-1635520574146)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20211029191337400.png)]

//獲得雙鏈表節點函式
LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

雙鏈表頭刪函式ListPopFront

//雙鏈表頭刪函式
void ListPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* next = phead->next;
	phead->next = next->next;
	next->next->prev = phead;
	free(next);
}

雙鏈表查找函式ListFind

這個一般是和插入，洗掉配合使用

//雙鏈表查找函式
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

雙鏈表插入函式ListInsert（pos之前插入因為c++中就是之前插入的）

//雙鏈表插入函式
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posprev = pos->prev;
	newnode->data = x;
	pos->prev = newnode;
	newnode->next = pos;
	newnode->prev = posprev;
	posprev->next = newnode;
}

雙鏈表洗掉函式ListErase（洗掉pos）

//雙鏈表洗掉函式
void ListErase(LTNode* pos)
{
	assert(pos && pos->next);
	LTNode* posnext = pos->next;
	LTNode* posprev = pos->prev;
	posnext->prev = posprev;
	posprev->next = posnext;
	free(pos);
}

雙鏈表銷毀函式ListDestroy(實際上我在這里寫報錯了，前面一個函式有bug，但是找到了)

//雙鏈表銷毀函式
void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;
	while (tail != phead)
	{
		LTNode* tailprev = tail->next;
		free(tail);
		tail = tailprev;
	}
	free(phead);
	phead = NULL;
}

代碼

DoubleList.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;  //C++中的雙鏈表是用list表示的

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

//雙鏈表初始化函式
extern LTNode* ListInit();
//雙鏈表銷毀函式
extern void ListDestroy(LTNode* phead);
//雙鏈表尾插函式
extern void ListPushBack(LTNode* phead, LTDataType x);
//雙鏈表列印函式
extern void ListPrint(LTNode* phead);
//雙鏈表尾刪函式
extern void ListPopBack(LTNode* phead);
//獲得雙鏈表節點函式
extern LTNode* BuyListNode(LTDataType x);
//雙鏈表頭插函式
extern void ListPushFront(LTNode* phead, LTDataType x);
//雙鏈表頭刪函式
extern void ListPopFront(LTNode* phead);
//雙鏈表查找函式
extern LTNode* ListFind(LTNode* phead, LTDataType x);
//雙鏈表插入函式
extern void ListInsert(LTNode* pos, LTDataType x);
//雙鏈表洗掉函式
extern void ListErase(LTNode* pos);

DoubleList.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "DoubleList.h"

//雙鏈表初始化函式
LTNode* ListInit()
{
	//創建一個雙鏈表哨兵位頭結點  不存盤有效資料  回圈
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
//獲得雙鏈表節點函式
LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
//雙鏈表尾插函式
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);//實際上phead永遠也不可能是NULL
	LTNode* tail = phead->prev;
	/*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;*/
	LTNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
//雙鏈表列印函式
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
//雙鏈表尾刪函式
void ListPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* cur = phead->prev;
	tail = tail->prev;
	tail->next = phead;
	phead->prev = tail;
	free(cur);
}

//雙鏈表頭插函式
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* next = phead->next;//在next和phead中間插一個節點
	/*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;*/
	LTNode* newnode = BuyListNode(x);
	newnode->next = next;
	next->prev = newnode;
	phead->next = newnode;
}

//雙鏈表頭刪函式
void ListPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* next = phead->next;
	phead->next = next->next;
	next->next->prev = phead;
	free(next);
}

//雙鏈表查找函式
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
//雙鏈表插入函式
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posprev = pos->prev;
	newnode->data = x;
	pos->prev = newnode;
	newnode->next = pos;
	newnode->prev = posprev;
	posprev->next = newnode;
}
//雙鏈表洗掉函式
void ListErase(LTNode* pos)
{
	assert(pos && pos->next);
	LTNode* posnext = pos->next;
	LTNode* posprev = pos->prev;
	posnext->prev = posprev;
	posprev->next = posnext;
	free(pos);
}
//雙鏈表銷毀函式
void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;
	while (tail != phead)
	{
		LTNode* tailprev = tail->next;
		free(tail);
		tail = tailprev;
	}
	free(phead);
	phead = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "DoubleList.h"
void TestList1()
{
	LTNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);
	ListPushFront(plist, 10);
	ListPushFront(plist, 20);
	ListPushFront(plist, 30);
	ListPrint(plist);
	LTNode* p1 = ListFind(plist, 10);
	if (p1)
	{
		ListInsert(p1, 100);
	}
	ListPrint(plist);
	LTNode* p2 = ListFind(plist, 20);
	if (p2)
	{
		ListErase(p2);
	}
	ListPrint(plist);
	ListDestroy(plist);
	plist = NULL;
}


int main()
{
	TestList1();
	return 0;
}

也歡迎大家能來到我們小伙伴的社區慧編程開源俱樂部

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

標籤：其他

上一篇：滑動視窗演算法總結及相關例題

下一篇：資料結構之堆疊詳解

演算法開啟小碼農雙鏈表血脈

文章目錄

也歡迎大家能來到我們小伙伴的社區 慧編程開源俱樂部

雙鏈表

雙鏈表結構圖

雙鏈表節點

雙鏈表初始化函式ListInit

雙鏈表尾插函式ListPushBack

雙鏈表列印函式ListPrint

雙鏈表尾刪函式ListPopBack

雙鏈表頭插函式ListPushFront

獲得雙鏈表節點函式BuyListNode

雙鏈表頭刪函式ListPopFront

雙鏈表查找函式ListFind

雙鏈表插入函式ListInsert（pos之前插入因為c++中就是之前插入的）

雙鏈表洗掉函式ListErase（洗掉pos）

雙鏈表銷毀函式ListDestroy(實際上我在這里寫報錯了，前面一個函式有bug，但是找到了)

代碼

DoubleList.h

DoubleList.c

test.c

也歡迎大家能來到我們小伙伴的社區 慧編程開源俱樂部

也歡迎大家能來到我們小伙伴的社區慧編程開源俱樂部

也歡迎大家能來到我們小伙伴的社區慧編程開源俱樂部