抽象基类 linearList 的定义 linearList .h:
1 #pragma once
2 #include <iostream>
3
4 template<typename T>
5 class linearList
6 {
7 public:
8 virtual ~linearList() {};
9 virtual bool empty() const = 0;
10 virtual int size() const = 0;
11 virtual T &get(int Index) const = 0;
12 virtual int indexOf(const T &theElement) const = 0;
13 virtual void erase(int theIndex) = 0;
14 virtual void insert(int theIndex, T &theElement) = 0;
15 virtual void output(std::ostream& out) = 0;
16 };
异常类的定义 myExceptions.h:
1 // exception classes for various error types
2
3 #ifndef myExceptions_
4 #define myExceptions_
5 #include <string>
6
7 using namespace std;
8
9 // illegal parameter value
10 class illegalParameterValue
11 {
12 public:
13 illegalParameterValue(string theMessage = "Illegal parameter value")
14 {message = theMessage;}
15 void outputMessage() {cout << message << endl;}
16 private:
17 string message;
18 };
19
20 // illegal input data
21 class illegalInputData
22 {
23 public:
24 illegalInputData(string theMessage = "Illegal data input")
25 {message = theMessage;}
26 void outputMessage() {cout << message << endl;}
27 private:
28 string message;
29 };
30
31 // illegal index
32 class illegalIndex
33 {
34 public:
35 illegalIndex(string theMessage = "Illegal index")
36 {message = theMessage;}
37 void outputMessage() {cout << message << endl;}
38 private:
39 string message;
40 };
41
42 // matrix index out of bounds
43 class matrixIndexOutOfBounds
44 {
45 public:
46 matrixIndexOutOfBounds
47 (string theMessage = "Matrix index out of bounds")
48 {message = theMessage;}
49 void outputMessage() {cout << message << endl;}
50 private:
51 string message;
52 };
53
54 // matrix size mismatch
55 class matrixSizeMismatch
56 {
57 public:
58 matrixSizeMismatch(string theMessage =
59 "The size of the two matrics doesn't match")
60 {message = theMessage;}
61 void outputMessage() {cout << message << endl;}
62 private:
63 string message;
64 };
65
66 // stack is empty
67 class stackEmpty
68 {
69 public:
70 stackEmpty(string theMessage =
71 "Invalid operation on empty stack")
72 {message = theMessage;}
73 void outputMessage() {cout << message << endl;}
74 private:
75 string message;
76 };
77
78 // queue is empty
79 class queueEmpty
80 {
81 public:
82 queueEmpty(string theMessage =
83 "Invalid operation on empty queue")
84 {message = theMessage;}
85 void outputMessage() {cout << message << endl;}
86 private:
87 string message;
88 };
89
90 // hash table is full
91 class hashTableFull
92 {
93 public:
94 hashTableFull(string theMessage =
95 "The hash table is full")
96 {message = theMessage;}
97 void outputMessage() {cout << message << endl;}
98 private:
99 string message;
100 };
101
102 // edge weight undefined
103 class undefinedEdgeWeight
104 {
105 public:
106 undefinedEdgeWeight(string theMessage =
107 "No edge weights defined")
108 {message = theMessage;}
109 void outputMessage() {cout << message << endl;}
110 private:
111 string message;
112 };
113
114 // method undefined
115 class undefinedMethod
116 {
117 public:
118 undefinedMethod(string theMessage =
119 "This method is undefined")
120 {message = theMessage;}
121 void outputMessage() {cout << message << endl;}
122 private:
123 string message;
124 };
125
126 // the key inexistence,dictionary
127 class keyInexistence
128 {
129 public:
130 keyInexistence(string theMessage =
131 "the key inexistence")
132 {message = theMessage;}
133 void outputMessage() {cout << message << endl;}
134 private:
135 string message;
136 };
137
138 #endif
类 arrayList 的定义在 arrayList.h 中:
1 #pragma once
2 #include <iostream>
3 #include <sstream>
4 #include <iterator>
5 #include <string>
6 #include <algorithm>
7 #include "linearList.h"
8 #include "myExceptions.h"
9
10 template<typename T>
11 class arrayList : public linearList<T>
12 {
13 public:
14 arrayList(int cArrayLenth = 20);
15 arrayList(const arrayList<T> &cArrayList);
16 ~arrayList();
17 bool empty() const;
18 int size() const;
19 T &get(int Index) const;
20 int indexOf(const T &theElement) const;
21 void erase(int theIndex);
22 void insert(int theIndex, T &theElement);
23 void output(std::ostream &out);
24 protected:
25 void checkIndex(int theIndex) const;
26 void changeLenth(T* &theElement, int oldLenth, int newLenth);
27
28 T * element;
29 int arrayLenth;
30 int listSize;
31 };
32
33 template<typename T>
34 arrayList<T>::arrayList(int cArrayLenth)
35 {
36 if (1 > cArrayLenth)
37 {
38 std::ostringstream s;
39 s << "cArrayLenth = " << cArrayLenth << "太小!" << endl;
40 throw illegalParameterValue(s.str());
41 }
42 element = new T[cArrayLenth];
43 arrayLenth = cArrayLenth;
44 listSize = 0;
45 }
46
47 template<typename T>
48 arrayList<T>::arrayList(const arrayList<T> &cArrayList)
49 {
50 arrayLenth = cArrayList.arrayLenth;
51 element = new T[arrayLenth];
52 listSize = cArrayList.listSize;
53 copy(cArrayList.element, cArrayList.element + listSize, element);
54 }
55
56 template<typename T>
57 arrayList<T>::~arrayList()
58 {
59 delete[] element;
60 }
61
62 template<typename T>
63 void arrayList<T>::checkIndex(int theIndex) const
64 {
65 if (theIndex < 0 || theIndex >= listSize)
66 {
67 std::ostringstream s;
68 s << "theIndex = " << theIndex << "ERROR" << endl;
69 throw illegalIndex(s.str());
70 }
71 }
72
73 template<typename T>
74 void arrayList<T>::changeLenth(T* &theElement, int oldLenth, int newLenth)
75 {
76 if (newLenth < 0)
77 {
78 std::ostringstream s;
79 s << "newLenth = " << newLenth << "must > 0" << endl;
80 throw illegalParameterValue(s.str());
81 }
82 T *Tmp = new T[newLenth];
83 int minux = min(oldLenth, newLenth);
84 copy(theElement, theElement + minux, Tmp);
85 delete[] theElement;
86 theElement = Tmp;
87 }
88
89 template<typename T>
90 bool arrayList<T>::empty() const
91 {
92 return listSize == 0;
93 }
94
95 template<typename T>
96 int arrayList<T>::size() const
97 {
98 return listSize;
99 }
100
101 template<typename T>
102 T &arrayList<T>::get(int Index) const
103 {
104 checkIndex(Index);
105 return element[Index];
106 }
107
108 template<typename T>
109 int arrayList<T>::indexOf(const T &theElement) const
110 {
111 int Index = (int)(find(element, element + listSize, theElement) - element);
112 if (Index == listSize)
113 return -1;
114 return Index;
115 }
116
117 template<typename T>
118 void arrayList<T>::erase(int theIndex)
119 {
120 checkIndex(theIndex);
121 copy(element + theIndex + 1, element + listSize, element + theIndex);//copy函数,从左端开始移动
122 element[--listSize].~T();
123 }
124
125 template<typename T>
126 void arrayList<T>::insert(int theIndex, T &theElement)
127 {
128 if (0 > theElement || theElement > listSize)
129 {
130 std::ostringstream s;
131 s << "theIndex = " << theIndex << "error !" << endl;
132 throw illegalIndex(s.str());
133 }
134 //数组倍增
135 if (listSize == arrayLenth)
136 {
137 changeLenth(element, arrayLenth, arrayLenth * 2);
138 }
139 copy_backward(element + theIndex, element + listSize, element + listSize + 1);
140 element[theIndex] = theElement;
141 listSize++;
142 }
143
144 template<typename T>
145 void arrayList<T>::output(std::ostream &out)
146 {
147 copy(element, element + listSize, std::ostream_iterator<T>(cout, " "));
148 }
149
150 template<typename T>
151 std::ostream &operator<<(std::ostream &out, arrayList<T> &cArray)
152 {
153 cArray.output(out);
154 return out;
155 }
参考文献:
[1].Sartaj Sahni. 数据结构、算法与应用[M]. 机械工业出版社, 2000.