数据结构之单向链表-游标实现

发表于 | 分类于

基础知识

单向链表的游标实现和指针实现最大的不同是游标实现无法采用指针的方式连接到下一个节点，其只能通过数组下标的方式进行下一节点的索引，因此游标实现相比指针实现需要手动管理数组内存使用情况，本文直接采用《数据结构与算法分析：C语言描述》中的思路，不过本文使用了一个哑节点，代码中约定数组第0号节点用来模拟管理内存，1号节点作为哑节点，具体的定义和实现如下小节所示。

游标单向链表的定义和实现

由于游标实现中不能动态申请内存，因此函数中会预先分配一个固定大小的数组。具体实现见如下代码：

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
template <typename DataType>
struct CursorNode
{
        CursorNode() : next(0) {}
	DataType data;
        /*数组下标指定下一个节点，0代表没有下一个节点*/
	int next;
};

const int maxListSize = 100; /*数组大小*/

template <typename DataType>
class CursorList
{
public:
	CursorList();
	~CursorList(); /*析构函数，负责回收内存*/
	void MakeEmpty(); /*清空链表*/
	bool IsEmpty(); /*判断链表是否为空*/
	bool IsLast(int inPosition); /*判断是否为最后一个元素*/
	int FindElement(DataType value); /*查找一个元素并返回下标*/
	int FindNthElement(int n); /*查找第n个元素并返回下标*/
	void DeleteElement(DataType inData); /*删除一个节点*/
	void DeleteNthElement(int n); /*删除第n个节点*/
	void InsertElement(DataType inData, int n); /*插入一个节点*/
	int Length(); /*返回链表长度*/
        void PrintList(); /*打印链表*/
private:
        int Alloc(); /*获取一个单位节点的空间数组小标索引，没有返回0*/
        void Free(int nodeIndex); /*释放一个单位节点的空间*/
private:
        const int dummyNode = 1; /*哑节点下标固定为1*/
        CursorNode<DataType> listNodes[maxListSize]; /*节点数组*/
        int listSize; /*保存链表长度*/
        int lastNode; /*保存最后一个节点下标*/
};

如上所示，在链表类中有四个数据成员和一个全局变量maxListSize，数据成员分别为dummyNode、listNodes、listSize和lastNode。maxListSize是指节点数组最大容量，listNodes是节点数组，listSize是当前链表大小，dummyNode是哑节点索引，lastNode保存最后一个节点的数组索引。

下面依次实现各函数：

  • 构造函数，0号节点作为内存管理头节点，1作为哑节点（因为0代表没有下一个节点）
1
2
3
4
5
6
7
8
9
10
template <typename DataType>
CursorList<DataType>::CursorList():dummyNode(1), listSize(0), lastNode(0)
{
        for (int i = 0; i < maxListSize; i++) {
                listNodes[i].next = i + 1;
        }
        listNodes[0].next = 2; /*跳过哑节点*/
        listNodes[1].next = 0; /*哑节点初始下一节点指向空*/
        listNodes[maxListSize-1].next = 0; /*最后一个节点下一个节点指向空*/
}
  • 析构函数，模拟内存回收
1
2
3
4
5
template <typename DataType>
CursorList<DataType>::~CursorList()
{
        MakeEmpty();
}
  • 清空链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename DataType>
void CursorList<DataType>::MakeEmpty()
{
	if (listSize <= 0 || listNodes[dummyNode].next == 0) {
		return;
	}
	int tmp = 0;
	while (listNodes[dummyNode].next != 0) {
		tmp = listNodes[dummyNode].next;
		listNodes[dummyNode].next = listNodes[tmp].next;
		Free(tmp);
	}
	listSize = 0; lastNode = 0;
	return;
}
  • 判断列表是否为空
1
2
3
4
5
6
7
8
template <typename DataType>
bool CursorList<DataType>::IsEmpty()
{
	if (listSize <= 0 || listNodes[dummyNode].next == 0) {
		return true;
	}
	return false;
}
  • 判断是否为最后一个元素
1
2
3
4
5
template <typename DataType>
bool CursorList<DataType>::IsLast(int inPosition)
{
	return inPosition != 0 && inPosition == lastNode;
}
  • 查找一个元素并返回下标
1
2
3
4
5
6
7
8
9
10
11
12
template <typename DataType>
int CursorList<DataType>::FindElement(DataType value)
{
	int cycleIter = listNodes[dummyNode].next;
	while (cycleIter != 0) {
		if (listNodes[cycleIter].data == value) {
			return cycleIter;
		}
		cycleIter = listNodes[cycleIter].next;
	}
	return 0;
}
  • 查找第n个元素，dummy为第0个元素，返回地址或者0
1
2
3
4
5
6
7
8
9
10
11
12
template <typename DataType>
int CursorList<DataType>::FindNthElement(int n)
{
	if (n <= 0) {
		return 0;
	}
	int cycleIter = listNodes[dummyNode].next;
	while (--n > 0 && cycleIter != 0) {
		cycleIter = listNodes[cycleIter].next;
	}
	return cycleIter;
}
  • 删除一个节点，如果不存在则不做任何事
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename DataType>
void CursorList<DataType>::DeleteElement(DataType inData)
{
	int cycleIter = dummyNode;
	while (listNodes[cycleIter].next != 0) {
		if (listNodes[listNodes[cycleIter].next].data == inData) {
			int tmp = listNodes[cycleIter].next;
			listNodes[cycleIter].next = listNodes[tmp].next;
			lastNode = lastNode == tmp ? cycleIter : lastNode;
			Free(tmp); --listSize;
			return;
		}
		cycleIter = listNodes[cycleIter].next;
	}

	if (listNodes[dummyNode].next == 0) {
		lastNode = 0;
	}
	return;
}
  • 删除第n个节点，如果不存在则不做任何事
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <typename DataType>
void CursorList<DataType>::DeleteNthElement(int n)
{
	if (n <= 0 || n > listSize) {
		return;
	}

	int cycleIter = dummyNode;
	while (listNodes[cycleIter].next != 0 && --n > 0) {
		cycleIter =listNodes[cycleIter].next;
	}
	if (n <= 0) {
		int tmp = listNodes[cycleIter].next;
		listNodes[cycleIter].next = listNodes[tmp].next;
		lastNode = lastNode == tmp ? cycleIter : lastNode;
		Free(tmp); --listSize;
	}
	if (listNodes[dummyNode].next == 0) {
		lastNode = 0;
	}
	return;
}
  • 插入一个节点, n<0或者>链表长度代表直接插到末尾，其他代表插到第n个节点后
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
template <typename DataType>
void CursorList<DataType>::InsertElement(DataType inData, int n)
{
	int insertElement = Alloc();
        if (insertElement == 0) {
                return; /*空间不足*/
        }
	listNodes[insertElement].data = inData;
	listNodes[insertElement].next = 0;
	if (n < 0 || n >= listSize) {
                /*插到末尾*/
		if (lastNode == 0) {
			lastNode = dummyNode;
		}
		listNodes[lastNode].next = insertElement;
		lastNode = insertElement; ++listSize;
		return;
	}

	int cycleIter = dummyNode;
	while (n-- > 0 && cycleIter != 0) {
		cycleIter = listNodes[cycleIter].next;
	}
	if (n <= 0) {
		listNodes[insertElement].next = listNodes[cycleIter].next;
		listNodes[cycleIter].next = insertElement; ++listSize;
	}
	return;
}
  • 申请一个单位空间函数
1
2
3
4
5
6
7
8
9
10
11
template <typename DataType>
int CursorList<DataType>::Alloc()
{
        if (listNodes[0].next == 0) {
                return 0;
                /*没有空间了*/
        }
        int tmp = listNodes[0].next;
        listNodes[0].next = listNodes[tmp].next;
        return tmp;
}
  • 释放一个单位空间函数
1
2
3
4
5
6
7
8
9
10
template <typename DataType>
void CursorList<DataType>::Free(int nodeIndex)
{
        if (nodeIndex <= 1 || nodeIndex >= maxListSize) {
                return;
        }
        listNodes[nodeIndex].next = listNodes[0].next;
        listNodes[0].next = nodeIndex;
        return;
}
  • 返回链表长度
1
2
3
4
5
template <typename DataType>
int CursorList<DataType>::Length()
{
	return listSize;
}
  • 打印链表
1
2
3
4
5
6
7
8
9
10
template <typename DataType>
void CursorList<DataType>::PrintList()
{
        int cycleIter = listNodes[dummyNode].next;
	while (cycleIter != 0) {
		cout << listNodes[cycleIter].data << ";";
                cycleIter = listNodes[cycleIter].next;
	}
        cout << endl;
}

代码测试

对上述代码进行简单地测试，测试代码如下：

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
#include <iostream>
using namespace std;

int main()
{
        CursorList<char> Test;

        Test.InsertElement('A', 0);
        Test.InsertElement('B', 1);

        Test.PrintList();

        Test.InsertElement('C', 1);
        Test.InsertElement('D', 7);

        cout << Test.IsEmpty() << endl;
        Test.PrintList();

        Test.InsertElement('E', 3);
        Test.InsertElement('F', 2);

        Test.PrintList();

        cout << Test.Length() << endl;

        Test.DeleteElement('B');

        Test.PrintList();

        Test.DeleteElement('F');

        Test.PrintList();

        Test.DeleteElement('D');

        Test.PrintList();

        Test.DeleteElement('B');

        Test.PrintList();

        cout << Test.IsEmpty() << endl;

        cout << Test.Length() << endl;

        Test.InsertElement('A', 0);
        Test.InsertElement('B', 1);
        Test.InsertElement('C', 1);
        Test.InsertElement('D', 7);
        Test.InsertElement('E', 3);
        Test.InsertElement('F', 2);

        Test.PrintList();

        Test.MakeEmpty();

        Test.PrintList();

        Test.InsertElement('A', 0);
        Test.InsertElement('B', 1);
        Test.InsertElement('C', 1);
        Test.InsertElement('D', 7);
        Test.InsertElement('E', 3);
        Test.InsertElement('F', 2);

        Test.PrintList();

        int pTest = Test.FindElement('A');
        pTest = Test.FindElement('E');
	pTest = Test.FindElement('G');

        pTest = Test.FindNthElement(4);
        pTest = Test.FindNthElement(-1);
        pTest = Test.FindNthElement(1);
        pTest = Test.FindNthElement(10);

        return 0;
}

参考文章

数据结构与算法分析