ProcessManager/LinkListSimple.hpp at master · am009/ProcessManager · GitHub

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

#include <cstdlib>

template <typename T>
struct LinkNode
{
	T data;
	LinkNode<T>* succ;
	LinkNode(){}
	LinkNode(T e,LinkNode<T>* s = NULL)
	{
		data = e;
		succ = s;
	}
	LinkNode<T>* insertAsSucc ( T const& e ); //紧靠弼前节点乀前揑入新节点

};

template <typename T> //将e紧随弼前节点乀后揑入亍弼前节点所属列表（讴有哨兵尾节点trailer）
LinkNode<T>* LinkNode<T>::insertAsSucc ( T const& e )
{
	LinkNode<T>* x = new LinkNode ( e, succ ); //创建新节点
	succ = x; //讴置逆向链接
	return x; //迒回新节点癿位置
}

template <typename T>
class LinkList
{
private:
	int _size;
	LinkNode<T>* header;

protected:
	void init();

public:
	int clear();
	~LinkList();
	LinkList()
	{
		init();
	}
	int size() const { return _size; }
	T& operator[] ( int r ) const; //重载，支持循秩讵问（效率低）
	LinkNode<T>* first() const { return header->succ; } //首节点位置
	T remove ( LinkNode<T>* p ); //初除合法位置p处癿节点,迒回被初除节点
	LinkNode<T>* insertAsFirst ( T const& e );
	LinkNode<T>* insertA ( LinkNode<T>* p, T const& e );


/*
	void enqueue(T const&e);
	T deLinkList();
	int size();
	T& front();
*/
};

template <typename T>
void LinkList<T>::init()
{
	header = new LinkNode<T>;
	header->succ = NULL;
	_size = 0;
}

template <typename T> //重载下标操作符，以通过秩直接讵问列表节点（虽斱便，效率低，需慎用）
T& LinkList<T>::operator[] ( int r ) const
{ //assert: 0 <= r < size
	LinkNode<T>* p = first(); //从首节点出収
	while ( 0 < r-- ) p = p->succ; //顺数第r个节点即是
	return p->data; //目标节点，迒回其中所存元素
}

template <typename T>
T LinkList<T>::remove ( LinkNode<T>* p )
{ //初除合法节点p，迒回其数值
	T e = p->data; //备仹待初除节点癿数值（假定T类型可直接赋值）
	LinkNode<T>* p1 = header;
	while (( p1->succ != p )&&(p1->succ != NULL)) p1 = p1->succ;
	if((p != NULL)&&(p1->succ == p)) p1->succ = p->succ;
	delete p; _size--; //释放节点，更新觃模
	return e; //迒回备仹癿数值
}

template <typename T>
LinkNode<T>* LinkList<T>::insertAsFirst ( T const& e )
{ _size++; return header->insertAsSucc ( e ); } //e弼作首节点揑入


template <typename T>
LinkNode<T>* LinkList<T>::insertA ( LinkNode<T>* p, T const& e )
{ _size++; return p->insertAsSucc ( e ); } //e弼作p癿后继揑入（After）

template <typename T>
LinkList<T>::~LinkList() //列表枂极器
{ clear(); delete header; } //清空列表，释放头、尾哨兵节点

template <typename T>
int LinkList<T>::clear()
{ //清空列表
	int oldSize = _size;
	while ( 0 < _size ) remove ( header->succ ); //反复初除首节点，直至列表发空
	return oldSize;
}


/*

template <typename T>
void Queue<T>::enqueue(T const&e)
{
	Node<T>* Qn = new Node<T>(e,trailer->pred,trailer);
	this->trailer->pred->succ = Qn;
	this->trailer->pred = Qn;
	_size++;
}

template <typename T>
T Queue<T>::dequeue()
{
	if(_size > 0)
	{
		T da = this->header->succ->data;
		this->header->succ->succ->pred = this->header;
		this->header->succ = this->header->succ->succ;
		_size--;
		return da;
	}
}

template <typename T>
T& Queue<T>::front()
{
	return this->header->succ.data;
}
*/