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
| #include<iostream>
#include <sstream>
using namespace std;
class illegalParameterValue {
public:
illegalParameterValue() : message("Illegal parameter value") {}
explicit illegalParameterValue(char *theMessage) {
message = theMessage;
}
explicit illegalParameterValue(const string &theMessage) {
message = theMessage;
cout << message << endl;
}
void outputMessge() {
cout << message << endl;
}
private:
string message;
};
// 链表结点的结构定义
template<class T>
struct chainNode {
// 数据成员
T element;
chainNode<T> *next;
// 方法
chainNode() {}
chainNode(const T &element) { this->element = element; }
chainNode(const T &element, chainNode<T> *next) {
this->element = element;
this->next = next;
}
};
template<class T>
class chainList {
public:
// 构造函数，复制构造函数和构析函数
chainList(int initialCapacity = 10);
chainList(const chainList<T> &);
~chainList();
// 抽象数据类型ADT的方法
bool empty() const { return listSize == 0; }
int size() const { return listSize; }
T &get(int theIndex) const;
int indexOf(const T &theElement) const;
void erase(int theIndex);
void insert(int theIndex, const T &theElement);
void output(ostream &out) const;
protected:
void checkIndex(int theIndex) const; // 如果索引无效抛出异常
chainNode<T> *firstNode; // 指向链表第一个结点的指针
int listSize;
};
template<class T>
void chainList<T>::checkIndex(int theIndex) const {
if (theIndex < 0 || theIndex >= size()) {
stringstream s;
s << "theIndex " << theIndex << " is illegal";
illegalParameterValue(s.str());
}
}
// 构造函数和复制构造函数
template<class T>
chainList<T>::chainList(int initialCapacity) {
// 构造函数
if (initialCapacity < 1) {
ostringstream s;
s << "Initial capacity = " << initialCapacity << " Muse be > 0 ";
throw illegalParameterValue(s.str());
}
firstNode = nullptr;
listSize = 0;
}
template<class T>
chainList<T>::chainList(const chainList<T> &theList) {
// 复制构造函数
listSize = theList.listSize;
if (listSize == 0) {
// 链表theList为空
firstNode = nullptr;
return;
}
// 链表theList为非空
chainNode<T> *sourceNode = theList.firstNode; // 复制链表theList的节点
firstNode = new chainNode<T>(sourceNode->element); // 复制链表theList的首元素
sourceNode = sourceNode->next;
chainNode<T> *targetNode = firstNode; // 当前链表*this的最后一个结点
while (sourceNode != nullptr) {
// 复制剩余元素
targetNode->next = new chainNode<T>(sourceNode->element);
targetNode = targetNode->next;
sourceNode = sourceNode->next;
}
targetNode->next = nullptr; // 链表结束
}
// 构析函数
template<class T>
chainList<T>::~chainList() {
// 链表构析函数，删除链表的所有节点
while (firstNode != nullptr) {
// 删除首结点
chainNode<T> *nextNode = firstNode->next;
delete firstNode;
firstNode = nextNode;
}
}
// get方法
template<class T>
T &chainList<T>::get(int theIndex) const {
// 返回索引为theIndex的㢝
// 若该元素不存在，则抛出异常
checkIndex(theIndex);
// 移向所需要的结点
chainNode<T> *currentNode = firstNode;
for (int i = 0; i < theIndex; ++i)
currentNode = currentNode->next;
return currentNode->element;
}
// 返回元素theElement首次出现时的索引
template<class T>
int chainList<T>::indexOf(const T &theElement) const {
// 返回元素theElement首次出现时的索引
// 若该元素不存在，则返回-1
// 搜寻链表寻找元素theElement
chainNode<T> *currentNode = firstNode;
int index = 0;
while (currentNode != nullptr && currentNode->element != theElement) {
// 移向下一个结点
currentNode = currentNode->next;
++index;
}
// 确定是否找到所需的元素
if (currentNode == nullptr)
return -1;
else
return index;
}
// 删除索引为theIndex的元素
template<class T>
void chainList<T>::erase(int theIndex) {
// 删除索引为theIndex元素
// 若该元素不存在，则抛出异常
checkIndex(theIndex);
// 索引有效
chainNode<T> *deleteNode;
if (theIndex == 0) {
// 删除链表的头节点
deleteNode = firstNode;
firstNode = firstNode->next;
} else {
// 用指针p指向要删除节点的前驱结点
chainNode<T> *p = firstNode;
for (int i = 0; i < theIndex - 1; ++i)
p = p->next;
deleteNode = p->next;
p->next = p->next->next;
}
--listSize;
delete deleteNode;
}
// 插入theElement并使得其索引为theIndex
template<class T>
void chainList<T>::insert(int theIndex, const T &theElement) {
// 在索引为theIndex的位置上
// 若该位置非法，则抛出异常
if (theIndex < 0 || theIndex > listSize) {
// 无效索引
ostringstream s;
s << "index = " << theIndex << " size = " << listSize;
throw illegalParameterValue(s.str());
}
if (theIndex == 0)
// 在链表头插入
firstNode = new chainNode<T>(theElement, firstNode);
else {
// 寻找新元素的前驱结点
chainNode<T> *p = firstNode;
for (int i = 0; i < theIndex - 1; ++i)
p = p->next;
// 在p之后插入
p->next = new chainNode<T>(theElement, p->next);
}
++listSize;
}
template<class T>
void chainList<T>::output(ostream &out) const {
// 把链表放入输出流
for (chainNode<T> *currentNode = firstNode; currentNode != nullptr; currentNode = currentNode->next)
out << currentNode->element << " ";
}
// 重载
template<class T>
ostream &operator<<(ostream &out, const chainList<T> &x) {
x.output(out);
return out;
}
int main() {
auto *array1 = new chainList<int>(20);
array1->insert(0, 1);
array1->insert(1, 2);
array1->insert(2, 3);
cout << *array1 << endl;
array1->insert(4, 4);
return 0;
}
|