带头双向循环链表的基本入门

分析·功能·讲解

带头双向循环链表的特点

- ***结构最复杂，一般用在单独存储数据。***
- ***实际中使用的链表数据结构，都是带头双向循环链表。***
- ***结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。***
1
2
3

初始化操作

LTNode* ListInit() {
	//哨兵位的头节点
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
1
2
3
4
5
6
7

• 首先申请一个头结点，然后把它的前指针和后指针都指向本身。
• 需要注意的是：要把头结点的指针返回，确保对实参进行有效的改变。

销毁操作

void ListDestroy(ListNode* &phead) {
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead) {
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11

• 需要注意：这里传递参数的方式要保证对实参产生影响。
• 使用Current指针指向要释放的节点，使用Next指针指向下一个节点，然后不断迭代，销毁全部的节点。
• 最后记得把哨兵位的头节点释放。

尾插·节点

void ListPushBack(LTNode* phead, LDateType x) {
	assert(phead);
	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;
}
1
2
3
4
5
6
7
8
9
10
11

尾删

void ListPopBack(LTNode* phead) {
	assert(phead);
	if (phead->next!=NULL) {
		LTNode* oldNote = phead->prev;
		LTNode* newTail = oldNote->prev;
		phead->prev = newTail;
		newTail->next = phead;
		delete(oldNote);
	}
	//ListErase(phead->prev);
}
1
2
3
4
5
6
7
8
9
10
11

头插

void ListPushFront(LTNode* phead, LDateType x) {
	assert(phead);
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	newNode->data = x;
	newNode->next = phead->next;
	phead->next->prev = newNode;
	phead->next = newNode;
	newNode->prev = phead;
}
1
2
3
4
5
6
7
8
9

头删

void ListPopFront(LTNode* phead) {
	assert(phead);
	assert(phead->next!=phead);
	LTNode* oldNote = phead->next;
	LTNode* newHead = oldNote->next;
	phead->next = newHead;
	newHead->prev = phead;
	delete(oldNote);
	//ListErase(phead->next);
}

1
2
3
4
5
6
7
8
9
10
11

指定·插入

void ListInsert(LTNode* pos, LDateType x) {
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	newNode->data = x;
	newNode->prev = posPrev;
	newNode->next = pos;
	posPrev->next = newNode;
	pos->prev = newNode;
}
1
2
3
4
5
6
7
8
9
10

指定·删除

//删除pos位置的节点
void ListErase(LTNode* pos) {
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	free(pos);
	posPrev->next = posNext;
	posNext->prev = posPrev;
}
1
2
3
4
5
6
7
8
9

整体·源码

头文件

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
typedef int LDateType;
typedef struct ListNode
{
	LDateType data;
	struct ListNode* next;
	struct ListNode* prev;
} LTNode;

LTNode* ListInit();
void ListDestroy(ListNode* &phead);
void ListPrint(LTNode* phead);
void ListPushBack(LTNode* phead,LDateType x);
void ListPopBack(LTNode* phead);
void ListPushFront(LTNode* phead,LDateType x);
void ListPopFront(LTNode* phead);
LTNode* ListFind(LTNode* phead,LDateType x);
void ListInsert(LTNode* pos, LDateType x);
void ListErase(LTNode* pos);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

功能实现文件

#define _CRT_SECURE_NO_WARNINGS
#include"DoubleList.h"

LTNode* ListInit() {
	//哨兵位的头节点
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

void ListDestroy(ListNode* &phead) {
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead) {
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

void ListPushBack(LTNode* phead, LDateType x) {
	assert(phead);
	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;
}

void ListPrint(LTNode* phead) {
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead) {
		cout << cur->data;
		if (cur->next != phead) {
			cout << "->";
		}
		cur = cur->next;
	}
	cout << endl;
}
void ListPopBack(LTNode* phead) {
	assert(phead);
	if (phead->next!=NULL) {
		LTNode* oldNote = phead->prev;
		LTNode* newTail = oldNote->prev;
		phead->prev = newTail;
		newTail->next = phead;
		delete(oldNote);
	}
	//ListErase(phead->prev);
}
void ListPushFront(LTNode* phead, LDateType x) {
	assert(phead);
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	newNode->data = x;
	newNode->next = phead->next;
	phead->next->prev = newNode;
	phead->next = newNode;
	newNode->prev = phead;
}
void ListPopFront(LTNode* phead) {
	assert(phead);
	assert(phead->next!=phead);
	LTNode* oldNote = phead->next;
	LTNode* newHead = oldNote->next;
	phead->next = newHead;
	newHead->prev = phead;
	delete(oldNote);
	//ListErase(phead->next);
}

LTNode* ListFind(LTNode* phead, LDateType x) {
	if (phead) {
		ListNode* cur = phead->next;
		while (cur!=phead) {
			if (cur->data == x) {
				return cur;
			}
			cur = cur->next;
		}
	}
	else {
		return NULL;
	}
}
void ListInsert(LTNode* pos, LDateType x) {
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	newNode->data = x;
	newNode->prev = posPrev;
	newNode->next = pos;
	posPrev->next = newNode;
	pos->prev = newNode;
}
//删除pos位置的节点
void ListErase(LTNode* pos) {
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	free(pos);
	posPrev->next = posNext;
	posNext->prev = posPrev;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111