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
| #include<iostream>
#include <sstream>
#include<iterator>
#include<algorithm>
using namespace std;
// 重写copy代码
template<class iterator>
void copy(iterator start, iterator end, iterator to) {
// 从start复制到[to, to+end-start)
while (start != end)
*(to++) = *(start++);
}
template<class T>
class linearList {
public:
virtual ~linearList() = default;;
virtual bool empty() const = 0; /* 返回true，当且仅当线性表为空 */
virtual int size() const = 0; /* 返回线性表的元素个数 */
virtual T &get(int theIndex) const = 0; /* 返回索引为theIndex的元素 */
virtual int indexOf(const T &theElement) const = 0; /* 返回元素theElement第一次出现时的索引 */
virtual void erase(int theIndex) = 0; /* 删除索引为theIndex的元素 */
virtual void insert(int theIndex, const T &theElement) = 0;/* 把theElement插入线性表中索引为theIndex的位置上 */
virtual void output(ostream &out) const = 0;/*把线性表插入输出流*/
};
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 outputMessage() { cout << message << endl; }
private:
string message;
};
/* 改变一个一位数组的长度*/
template<class T>
void changeLength1D(T *&a, int oldLength, int newLength) {
if (newLength < 0) /* 如果新表长小于0 */
throw illegalParameterValue("new length muse be >= 0"); /* 抛出异常*/
T *temp = new T[newLength]; /* 申请新的数组空间*/
int number = min(oldLength, newLength); /*过的原来数组长度和现在数组长度中较小者*/
copy(a, a + number, temp); /* 将原数组中的数据放到新的数组中*/
delete[] a; /* 删除原来数组的空间*/
a = temp; /*将新数组空间的地址给原来的数组名*/
}
/* 类arrayList定义
* 定义抽象类linearList的派生类arrayList
* 来实现抽象数据类型linearList
*/
template<class T>
class arrayList : public linearList<T> {
public:
/* 构造函数，复制构造函数和构析函数 */
arrayList(int initialCapacity = 10);
arrayList(const arrayList<T> &);
~arrayList() { delete[]element; }
/* 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;
int capacity() const { return arrayLength; }
protected:
void checkIndex(int theIndex) const;
T *element; /* 存储线性表元素的一维数组 */
int arrayLength; /* 一维数组的容量 */
int listSize; /* 线性表的元素个数 */
};
template<class T>
void arrayList<T>::checkIndex(int theIndex) const {
if (theIndex < 0 || theIndex >= listSize) {
ostringstream s;
s << "index = " << theIndex << " size = " << listSize;
throw illegalParameterValue(s.str());
}
}
template<class T>
T &arrayList<T>::get(int theIndex) const {
// 返回索引为theIndex的元素
// 若此元素不存在，则抛出异常
checkIndex(theIndex);
return element[theIndex];
}
template<class T>
int arrayList<T>::indexOf(const T &theElement) const {
// 返回元素theElement第一次出现时的索引
// 若该元素不存在，则返回-1
// 查找元素theElement
int theIndex = (int) (find(element, element + listSize, theElement) - element);
// 确定theElement是否找到
if (theIndex == listSize)
// 没有找到
return -1;
else
return theIndex;
}
template<class T>
void arrayList<T>::erase(int theIndex) {
// 删除其索引为theIndex的元素
// 如果该元素不存在，则抛出illegal
checkIndex(theIndex);
// 有效索引，移动其索引大于theIndex的元素
copy(element + theIndex + 1, element + listSize, element + theIndex);
element[--listSize].~T(); // 调用构析函数
}
// arrayList的构造函数
template<class T>
arrayList<T>::arrayList(int initialCapacity) {
// 构造函数
if (initialCapacity < 1) {
ostringstream s;
s << "Initial capacity = " << initialCapacity << " Must be > 0";
throw illegalParameterValue(s.str());
}
arrayLength = initialCapacity;
element = new T[arrayLength];
listSize = 0;
}
template<class T>
arrayList<T>::arrayList(const arrayList<T> &theList) {
// 复制构造函数
arrayLength = theList.arrayLength;
listSize = theList.listSize;
element = new T[arrayLength];
copy(theList.element, theList.element + listSize, element);
}
template<class T>
void arrayList<T>::insert(int theIndex, const T &theElement) {
// 在索引theIndex处插入元素theElement
if (theIndex < 0 || theIndex > listSize) {
// 无效索引
ostringstream s;
s << "index = " << theIndex << " size = " << listSize;
throw illegalParameterValue(s.str());
}
// 有效索引，确认数组是否已满
if (listSize == arrayLength) {
// 数组空间已满，数组长度倍增
changeLength1D(element, arrayLength, arrayLength * 2);
arrayLength *= 2;
}
// 把元素向右移动一个位置
copy_backward(element + theIndex, element + listSize, element + listSize + 1);
element[theIndex] = theElement;
++listSize;
}
// 把一个线性表插入输出流
template<class T>
void arrayList<T>::output(ostream &out) const {
copy(element, element + listSize, ostream_iterator<T>(cout, " "));
}
// 重载<<
template<class T>
ostream &operator<<(ostream &out, const arrayList<T> &x) {
x.output(out);
return out;
}
int main() {
auto *array1 = new arrayList<int>(100);
arrayList<double> y(100);
cout << *array1 << endl;
cout << y << endl;
return 0;
}
|