logo头像
Snippet 博客主题

数据结构-静态链表代码(C++类模板封装)

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

熬了一个下午,终于写完了.哈哈,用了C++的类模板封装了一个静态链表,简单的增删查改功能都有了.具体可以看代码。

StaticLinkList.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
#pragma once
#include <iomanip>

#define MAXSIZE 100

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

template <typename DATATYPE>
class Component
{
public:
	DATATYPE data; //数据域
	int cur;       //cur域，指向下一个元素的下标
};


template <typename DATATYPE>
class CStaticLinkList
{
public:
	Component<DATATYPE>  StaticLinkList[MAXSIZE];  //静态表
//自定义malloc和free
public:
	int MallocNodeSSL();
	status FreeNodeSSL(int index);
public:
	status InitList(); //初始化静态表
	status BackAddList( DATATYPE AddData); //尾增加
	status InsertNodeList(DATATYPE InsertData, int index);//指定位置插入
	status DeleteNodeList(DATATYPE *DelData, int index); //指定位置删除
	int SearchList(DATATYPE sData);       //搜索数据为sData的节点,返回其在数组中的下标,0表示失败
	status GetIndexList(DATATYPE *gData, int index);//获取指定索引的节点数据
	int GetLengthList(); //获取静态表的长度
	status ClearList(); //清空静态表
	status IsEmptyList(); //判断静态表是否为空
	status IsFullList(); //判断静态表是否满了
	void PrintList(); //打印静态表,此函数根据实际情况编写

public:
	CStaticLinkList();
	~CStaticLinkList();
};

StaticLinkList.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
#include "StaticLinkList.h"

template <typename DATATYPE>
CStaticLinkList<DATATYPE>::CStaticLinkList()
{
	cout << "===========静态表创建===========" << endl;
	InitList();
}

template <typename DATATYPE>
CStaticLinkList<DATATYPE>::~CStaticLinkList()
{
	cout << "===========静态表销毁===========" << endl;
}

template <typename DATATYPE>
int CStaticLinkList<DATATYPE>::MallocNodeSSL()
{
	int index = StaticLinkList[0].cur; //把备用链表第一个节点拿出来用
	if (StaticLinkList[0].cur) //判断是否还有位置
	{
		StaticLinkList[0].cur = StaticLinkList[index].cur; //让备用链表第二个节点上来顶替第一个的位置
	}

	return index; //返回0表示分配失败
}

template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::FreeNodeSSL(int index)
{
	//将删除节点挂接到备用链表上
	this->StaticLinkList[index].cur = this->StaticLinkList[0].cur;
	this->StaticLinkList[0].cur = index;
	
	return OK;
}

template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::InitList()
{
	int i;
	for (i = 0; i < MAXSIZE - 1; i++)
	{
		StaticLinkList[i].cur = i + 1;//全部塞入备用链表
	}
	StaticLinkList[MAXSIZE - 1].cur = 0;/*因为目前静态表为空,最后一个节点的cur域为0*/
	return OK;
}

template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::BackAddList(DATATYPE AddData) //尾增加
{
	if (IsFullList())
	{
		return ERROR;
	}
	int index = MAXSIZE - 1;
	int last = index;

	while (index != 0)
	{
		last = index;
		index = StaticLinkList[index].cur;
	}

	int k = MallocNodeSSL(); //获取空闲位置下标
	if (k)
	{
		StaticLinkList[k].data = AddData; //存入数据
		StaticLinkList[k].cur = 0;   //末尾指向0
		StaticLinkList[last].cur = k;
		return OK;
	}

	return ERROR;
	
}
//在List中第i个节点之前插入新的节点
template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::InsertNodeList(DATATYPE InsertData, int index)//指定位置插入
{
	int i, GetFree, pos;
	pos = MAXSIZE - 1;//最后节点下标
	if (index < 1 || index > GetLengthList() || IsFullList())
	{
		return ERROR; //位置异常处理
	}

	GetFree = MallocNodeSSL();
	if (GetFree)
	{
		StaticLinkList[GetFree].data = InsertData;
		for (i = 0; i < index - 1; i++)
		{
			pos = StaticLinkList[pos].cur; //定位
		}
		StaticLinkList[GetFree].cur = StaticLinkList[pos].cur;
		StaticLinkList[pos].cur = GetFree; //插入

		int q = StaticLinkList[MAXSIZE - 1].cur;
		if (q == 0) //静态表为空
		{
			StaticLinkList[MAXSIZE - 1].cur = 1;
		}
		return OK;
	}
	return ERROR;
}

//判断是否为空
template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::IsEmptyList()
{
	if (StaticLinkList[MAXSIZE-1].cur == 0)
	{
		return YES; 
	}

	return NO;
}
//判断静态表是否满了
template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::IsFullList()
{
	if (GetLengthList() == MAXSIZE - 2) //因为首位不存数据,因此pass掉
	{
		return YES;
	}
	return NO;
}
template <typename DATATYPE>
int CStaticLinkList<DATATYPE>::GetLengthList() //获取静态表的长度
{
	int iCount = 0;
	int k = MAXSIZE - 1;
	while (StaticLinkList[k].cur != 0)
	{
		iCount++;
		k = StaticLinkList[k].cur;
	}

	return iCount;
}
template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::DeleteNodeList(DATATYPE *DelData, int index)//指定位置删除
{
	int i, pos, k;
	pos = MAXSIZE - 1;//最后节点下标
	if (index < 1 || index > GetLengthList() || IsEmptyList())
	{
		return ERROR; //位置异常处理
	}
	for (i = 0; i < index - 1; i++)
	{
		pos = StaticLinkList[pos].cur; //定位到被删除节点的前一个节点
	}
	k = StaticLinkList[pos].cur; 
	*DelData = StaticLinkList[k].data; //获取数据
	StaticLinkList[pos].cur = StaticLinkList[k].cur;//让前一个节点直接指向后一个节点.把夹在中间的踢掉
	FreeNodeSSL(k); //释放空间

	return OK;
}
//搜索数据为sData的节点,返回其在静态表中的第i个位置,0表示没找到
template <typename DATATYPE>
int CStaticLinkList<DATATYPE>::SearchList(DATATYPE sData)
{
	int pos = StaticLinkList[MAXSIZE-1].cur;
	int iCount = 1;
	while (pos != 0)
	{
		if (StaticLinkList[pos].data == sData) //找到数据
		{
			return iCount;
		}
		pos = StaticLinkList[pos].cur; //循环遍历
		iCount++;
	}

	return 0;
}
template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::GetIndexList(DATATYPE *gData, int index)//获取第index个节点数据
{
	int i, pos;
	pos = MAXSIZE - 1;//最后节点下标
	if (index < 1 || index > GetLengthList() || IsEmptyList())
	{
		return ERROR; //位置异常处理
	}
	for (i = 0; i < index; i++)
	{
		pos = StaticLinkList[pos].cur; //定位到第index个节点
	}
	*gData = StaticLinkList[pos].data;

	return OK;
}
template <typename DATATYPE>
status  CStaticLinkList<DATATYPE>::ClearList() //清空静态表
{
	InitList();//再初始化一次就是清空了
	return  OK;
}
template <typename DATATYPE>
void  CStaticLinkList<DATATYPE>::PrintList()
{
	int pos = StaticLinkList[MAXSIZE - 1].cur;
	if (pos == 0)
	{
		cout << "===========静态链表为空,打印鸡毛!!!===========" << endl;
		return;
	}
	cout << setiosflags(ios::left);
	cout << setw(10) << "索引" << setw(10) << "下标" << setw(10) << "data" << setw(10) << "cur" << endl;
	int iCount = 1;
	while (pos != 0)
	{
		cout << setw(10) << iCount << setw(10) << pos << setw(10) << StaticLinkList[pos].data << setw(10) << StaticLinkList[pos].cur << endl;
		pos = StaticLinkList[pos].cur; //循环遍历
		iCount++;
	}
}

StaticLinkListTest.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
#include <iostream>
#include <iomanip>
#include "StaticLinkList.h"
#include "StaticLinkList.cpp"
using namespace std;

int main()
{
	char get;
	CStaticLinkList<char> *p = new CStaticLinkList<char>;
	p->PrintList();
	
	p->BackAddList('a'); //pass
	p->BackAddList('b');
	p->BackAddList('c');
	p->BackAddList('d');
	p->BackAddList('e');

	//p->ClearList();      //pass

	p->PrintList();

	p->DeleteNodeList(&get, 2);  //pass
	cout << "get = " << get << endl;

	p->DeleteNodeList(&get, 2);
	cout << "get = " << get << endl;

	p->PrintList();
	p->BackAddList('f');

	p->PrintList();
	cout << "length = " << p->GetLengthList() << endl;//pass

	p->GetIndexList(&get, 3);  //pass
	cout << "get = " << get << endl; 

	p->InsertNodeList('h', 2);
	p->InsertNodeList('i', 3);

	p->PrintList();
	cout << "length = " << p->GetLengthList() << endl;//pass

	cout << "search_pos = " << p->SearchList('q') << endl;
	cout << "search_pos = " << p->SearchList('h') << endl;
	cout << "search_pos = " << p->SearchList('i') << endl;

	delete p;

	return 0;
}

运行结果
运行结果

代码未经过严谨测试,如果有错,欢迎大家指正和交流啊.

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