logo头像
Snippet 博客主题

数据结构-单循环链表代码(C++类模板封装)

数据结构 数据结构 2018/02/18

循环链表就是末尾指向头形成一个循环的链表.实现思路也很简单,大体把单链表代码做个小小的改动就OK了.这次还是封装在一个类里面吧.

CircleLinkList.h 类头文件,各种声明定义

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
#pragma once //VC防止头文件重复包含的一条预编译指令

#define status bool
#define OK true
#define ERROR false
#define YES true
#define NO false

template <typename DType>
class Node
{
public:
	DType data;
	Node * pnext;
};
template <typename DType>
class CCircleLinkList
{
private:
	Node<DType> *phead;
public:
	CCircleLinkList();
	~CCircleLinkList();
public:
	//初始化链表
	status InitCList();
	//获取链表长度
	int GetCListLength();
	//增加一个节点 前插法
	status AddCListNodeFront(DType idata);
	//增加一个节点 后插法
	status AddCListNodeBack(DType idata);
	//判断链表是否为空
	status IsCListEmpty();
	//获取指定位置节点值(注意，本程序规定0号为头节点，e获取删除元素)
	status GetCListIndexNode(DType *e, int index);
	//删除指定位置节点(e获取删除元素)
	status DeleteCListIndexNode(DType *e, int index);
	//查找链表中指定值(pindex获取位置0==>not found)
	status SearchCListNode(DType SData, int *pindex);
	//指定位置前插
	status InsertCListNodeFront(DType IData, int index);
	//指定位置后插
	status InsertCListNodeBack(DType IData, int index);
	//清空链表(保留根节点)
	status ClearCList();
	//销毁链表(all delete)
	status DestoryCList();
	//尾部删除一个元素
	status DeleteCListNodeBack();
	//打印链表   此函数根据实际情况而定
	void PrintCList();
};

CircleLinkList.cpp 类的具体实现代码

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
#include "CircleLinkList.h"

#include <stdio.h>

template <typename DType>
CCircleLinkList<DType>::CCircleLinkList()
{
	cout << "链表创建" << endl;
	InitCList();
}

template <typename DType>
CCircleLinkList<DType>::~CCircleLinkList()
{
	cout << "链表销毁" << endl;
	DestoryCList();
}


//初始化链表
template <typename DType>
status CCircleLinkList<DType>::InitCList()
{
	Node<DType> * ph = new Node<DType>;
	if (ph != NULL)
	{
		ph->pnext = ph;    //尾指向头
		this->phead = ph; //头结点
		return OK;
	}

	return ERROR;

}

//获取链表长度(head_node is not included)
template <typename DType>
int CCircleLinkList<DType>::GetCListLength()
{
	int length = 0;
	Node<DType> * ph = this->phead;
	while (ph->pnext != this->phead)
	{
		length++;
		ph = ph->pnext;
	}
	return length;
}

//增加一个节点 前插法
template <typename DType>
status CCircleLinkList<DType>::AddCListNodeFront(DType idata)
{
	Node<DType> * pnode = new Node<DType>;
	if (pnode != NULL)
	{
		pnode->data = idata;
		pnode->pnext = this->phead->pnext;
		this->phead->pnext = pnode; //挂载

		return OK;
	}

	return ERROR;

}


//增加一个节点 尾插法
template <typename DType>
status CCircleLinkList<DType>::AddCListNodeBack(DType idata)
{
	Node<DType> * pnode = new Node<DType>;
	Node<DType> * ph = this->phead;
	if (pnode != NULL)
	{
		while (ph->pnext != this->phead)
		{
			ph = ph->pnext;
		}
		pnode->data = idata;
		pnode->pnext = this->phead;
		ph->pnext = pnode; //挂载
		return OK;
	}

	return ERROR;
}
//判断链表是否为空
template <typename DType>
status CCircleLinkList<DType>::IsCListEmpty()
{
	if (this->phead->pnext == this->phead)
	{
		return YES;
	}

	return NO;
}
//获取指定位置节点值(注意，本程序规定0号为头节点，e获取节点的值)
template <typename DType>
status CCircleLinkList<DType>::GetCListIndexNode(DType *e, int index)
{
	Node<DType> * ph = this->phead;
	int i = 0; //计数器
	if (ph->pnext == this->phead || index < 1 || index > GetCListLength())
	{
		return ERROR; //异常 处理
	}
	while (ph->pnext != this->phead)
	{
		i++;
		ph = ph->pnext;
		if (i == index)
		{
			*e = ph->data;
			return OK;
		}
	}

	return ERROR;
}
//删除指定位置节点(e获取删除元素)
template <typename DType>
status CCircleLinkList<DType>::DeleteCListIndexNode(DType *e, int index)
{
	Node<DType> * ph = this->phead;
	int i = 0; //计数器
	Node<DType> * q = nullptr;
	if (ph->pnext == this->phead || index < 1 || index > GetCListLength())
	{
		return ERROR; //异常 处理
	}
	while (ph->pnext != this->phead)
	{
		i++;
		q = ph; //保存备用
		ph = ph->pnext;
		if (i == index)
		{
			*e = ph->data;
			q->pnext = ph->pnext; //删除出局
			delete ph;
			return OK;
		}
	}
	return ERROR;
}
//查找链表中指定值(pindex获取位置   0==>not found)
template <typename DType>
status CCircleLinkList<DType>::SearchCListNode(DType SData, int *pindex)
{
	Node<DType> * ph = this->phead;
	int iCount = 0;//计数器
	while (ph->pnext != this->phead)
	{
		iCount++;
		ph = ph->pnext;
		if (ph->data == SData)
		{
			*pindex = iCount;
			return YES;
		}
	}
	*pindex = 0;
	return NO;

}
//指定位置前插
template <typename DType>
status CCircleLinkList<DType>::InsertCListNodeFront(DType IData, int index)
{
	Node<DType> * ph = this->phead;
	if (ph->pnext == this->phead || index < 1 || index > GetCListLength())
	{
		return ERROR; //异常 处理
	}
	int iCount = 0; //计数器
	Node<DType> * q = nullptr; //备用
	while (ph->pnext != this->phead)
	{
		iCount++;
		q = ph;
		ph = ph->pnext;
		if (iCount == index)
		{
			Node<DType> * p = new Node<DType>;
			p->data = IData;
			p->pnext = ph;
			q->pnext = p;   //前插
			return OK;
		}
	}
	return ERROR;
}
//指定位置后插
template <typename DType>
status CCircleLinkList<DType>::InsertCListNodeBack(DType IData, int index)
{
	Node<DType> * ph = this->phead;
	if (ph->pnext == this->phead || index < 1 || index > GetCListLength())
	{
		return ERROR; //异常 处理
	}
	int iCount = 0; //计数器
	Node<DType> * q = nullptr; //备用
	while (ph->pnext != this->phead)
	{
		iCount++;
		q = ph;
		ph = ph->pnext;
		if (iCount == index)
		{
			Node<DType> * p = new Node<DType>;
			q = ph;
			ph = ph->pnext; //后插就是后一个节点的前插咯
			p->data = IData;
			p->pnext = ph;
			q->pnext = p;
			return OK;
		}
	}
	return ERROR;
}
//清空链表(保留根节点)
template <typename DType>
status CCircleLinkList<DType>::ClearCList()
{
	Node<DType> * ph = this->phead;
	Node<DType> * q = nullptr; //防止那啥，野指针
	ph = ph->pnext;//保留头节点
	while (ph != this->phead)
	{
		q = ph;
		ph = ph->pnext;
		delete q; //释放
	}
	this->phead->pnext = this->phead;
	return OK;
}
//销毁链表(all delete)
template <typename DType>
status CCircleLinkList<DType>::DestoryCList()
{
	ClearCList();
	delete this->phead;//释放头结点 
	return OK;
}

template <typename DType>
status CCircleLinkList<DType>::DeleteCListNodeBack()
{
	Node<DType> * ph = this->phead;
	Node<DType> * q = nullptr; //备用
	if (ph->pnext == this->phead)
	{
		return ERROR; //链表都空了还删鸡毛
	}
	while (ph->pnext != this->phead)
	{
		q = ph;
		ph = ph->pnext;
	}
	q->pnext = this->phead;
	delete ph;

	return OK;

}
template <typename DType>
void CCircleLinkList<DType>::PrintCList()
{
	Node<DType> * ph = this->phead;
	if (ph->pnext == this->phead)
	{
		cout << "链表为空，打印鸡毛" << endl;
		return;
	}
	int i = 1;
	cout << "===============print list================" << endl;
	while (ph->pnext != this->phead)
	{
		ph = ph->pnext;
		cout << "node[" << i++ << "] = " << ph->data << endl;
	}
}

CircleLinkListTest.cpp 测试代码

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
#include <iostream>
#include "CircleLinkList.h"
#include "CircleLinkList.cpp"

using namespace std;

int main()
{
	CCircleLinkList<int> * pMySList = new CCircleLinkList<int>;
	cout << pMySList->IsCListEmpty() << endl;
	pMySList->AddCListNodeFront(111);
	pMySList->AddCListNodeFront(222);
	pMySList->AddCListNodeFront(333);

	cout << "链表长度" << pMySList->GetCListLength() << endl;

	pMySList->PrintCList();

	pMySList->AddCListNodeBack(444);
	pMySList->AddCListNodeBack(555);
	pMySList->AddCListNodeBack(666);

	pMySList->PrintCList();

	cout << pMySList->IsCListEmpty() << endl;
	cout << "链表长度" << pMySList->GetCListLength() << endl;

	int GetElem, GetIndex;
	pMySList->GetCListIndexNode(&GetElem, 2);
	cout << "Got Elem = " << GetElem << endl;

	pMySList->GetCListIndexNode(&GetElem, 6);
	cout << "Got Elem = " << GetElem << endl;

	pMySList->GetCListIndexNode(&GetElem, 4);
	cout << "Got Elem = " << GetElem << endl;

	pMySList->DeleteCListIndexNode(&GetElem, 1);
	cout << "del Elem = " << GetElem << endl;
	pMySList->DeleteCListIndexNode(&GetElem, 3);
	cout << "del Elem = " << GetElem << endl;


	pMySList->PrintCList();

	pMySList->SearchCListNode(555, &GetIndex);
	cout << "Search Index = " << GetIndex << endl;
	pMySList->SearchCListNode(111, &GetIndex);
	cout << "Search Index = " << GetIndex << endl;
	pMySList->SearchCListNode(666, &GetIndex);
	cout << "Search Index = " << GetIndex << endl;

	pMySList->InsertCListNodeFront(333, 1);
	pMySList->InsertCListNodeFront(444, 4);

	pMySList->PrintCList();

	pMySList->InsertCListNodeBack(777, 3);
	pMySList->InsertCListNodeBack(888, 5);

	pMySList->PrintCList();

	pMySList->DeleteCListNodeBack();
	pMySList->PrintCList();
	pMySList->DeleteCListNodeBack();
	pMySList->PrintCList();
	pMySList->DeleteCListNodeBack();
	pMySList->PrintCList();
	return 0;
}

代码未经严谨测试,如果有误,欢迎指正.

转载声明：商业转载请联系作者获得授权,非商业转载请注明出处 © infinitor
上一篇
Copyright © 2017 | Powered by Hexo | Theme by Snippet