向量和列表都是逻辑上线性数据结构，在物理上向量是顺序存储，列表是链式存储。
向量（Vector）接口描述
概述
- 内部使用数组封装，支持随机访问
- 空间复杂度
- 插入时，若容量不足会翻倍
- 删除时，目前不会缩小占用内存
构造函数和析构函数
- Vector(int c = DEFAULT_CAPACITY);
- 构造一个Vector，容量为c
- Vector(Vector &s);
- 复制构造函数，包括_elem指向的内容也会拷贝
- ~Vector();
- 析构函数，会delete[] _elem
整体属性
- int size();
- 返回Vector中元素个数
- int capacity();
- 返回Vector的最大容量
- bool empty();
- 判断是否为空。为空返回true
- bool disordered();
- 是否非降序排列（true乱序 false有序）
元素操作
- T& operator;
- 返回秩为r的元素的引用
- 不检查数组越界
- T get(int r);
- 返回秩为r的元素
- 如果r超出范围，返回的是0
- T last();
- 返回最后一个元素
- 不检查数组越界
- bool put(int r, T e);
- 将位置r处元素替换为e
- 若r越界，返回false
- bool insert(int r, T e);
- 在位置r处插入e 后面元素的后移
- r的范围为0到size，越界返回false
- 若容量不足，会按照2倍大小扩容
- bool push_back(T e);
- 在最后面添加元素e
- 若容量不足，会按照2倍大小扩容
- T remove(int r);
- 删除秩为r的元素，并返回删除的元素
- 如果r不符合范围，返回的是0
排序查找
- void sort(enum sort_method method = QUICK);
- 按照非降排序
- 需要使用<运算符进行比较
- 参数指定排序方法 默认为快速排序
- 可选方法：
- 冒泡：BUBBLE
- 快速排序（默认）：QUICK
- 归并排序：MERGE
- int find(T e);
- 查找e 返回下标
- 若找不到 返回的是-1
- int search(T e);
- 必须有序才能使用 返回不大于e的最大元素的位置
- 返回值范围是-1到size-1
遍历
- void travser(VST &visit);
- 遍历元素，对每个元素执行visit()操作
向量C++实现
最新的代码见Github。vector.h是实现文件，vector.cpp是简单的演示。
yalewoo/cpp-data-structure · GitHub
下面的代码可能不会及时更新
vector.h
|
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 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 |
#ifndef MY_VECTOR_H #define MY_VECTOR_H #include <cstdlib> using std::rand; #define DEFAULT_CAPACITY 20 enum sort_method{ BUBBLE, INSERT, QUICK, MERGE }; template <typename T> class Vector{ protected: int _size; //当前元素个数 int _capacity; //最大容量 T* _elem; //存放向量元素 void expand(); //扩容为原来的2倍 void decrease(); //收缩容量为二分之一 void copyFrom(T a[], int lo, int hi); //把a数组[lo,hi)部分复制到_elem void bubbleSort(); //冒泡排序 int partition(int lo, int hi); //快速排序的划分 void quicksort(int lo, int hi); //快速排序 void merge(int lo, int mid, int hi); void mergesort(int lo, int hi); void swap(T &a, T &b){T tmp = a; a = b; b = tmp;} public: Vector(int c = DEFAULT_CAPACITY) { _size = 0; _capacity = c; _elem = new T[c]; } Vector(Vector &s) { copyFrom(s._elem, 0, s._size); } ~Vector() { if (_elem) delete[] _elem; } template <typename VST> void travser(VST &visit); //遍历 int size() {return _size;} //返回当前元素总数 int capacity() {return _capacity;} bool empty() {return !_size;} T get(int r); //返回秩为r的元素 T & operator[](int n) { return _elem[n]; } T last() { return _elem[_size-1]; } bool put(int r, T e); //将位置r处元素替换为e bool insert(int r, T e); //在位置r处插入e 后面的后移 bool push_back(T e) { return insert(_size, e); } T remove(int r); //删除秩为r的元素，并返回 bool disordered(); //是否非降序排列（true乱序 false有序） void sort(enum sort_method method = QUICK); //按照非降排序 int find(T e); //查找e 返回下标 int search(T e); //有序查找 返回不大于e的最大元素的位置 int findInRange(T e, int lo, int hi); //查找e 返回下标 int searchInRange(T e, int lo, int hi); //有序查找 返回不大于e的最大元素的位置 int deduplicate(); //无序向量去重 int uniquify(); //有序向量去重 }; //把a[]的[lo, hi)复制到类中 template <typename T> void Vector<T>::copyFrom(T a[], int lo, int hi) { _capacity = 2 * (lo - hi); _elem = new T[_capacity]; _size = 0; while (lo < hi) { _elem[_size++] = a[lo++]; } } template <typename T> template <typename VST> void Vector<T>::travser(VST &visit) { for (int i = 0; i < _size; ++i) visit(_elem[i]); } template <typename T> bool Vector<T>::insert(int r, T e) { if (r > _size || r < 0) return false; if (_size == _capacity) expand(); int i = _size++; while (i > r) { _elem[i] = _elem[i-1]; --i; } _elem[i] = e; return true; } //返回秩为r的元素 template <typename T> T Vector<T>::get(int r) { if (r >= 0 && r < _size) return _elem[r]; else return 0; } //将位置r处元素替换为e template <typename T> bool Vector<T>::put(int r, T e) { if (r < 0 || r >= _size) return false; _elem[r] = e; return true; } //删除秩为r的元素，并返回 template <typename T> T Vector<T>::remove(int r) { if (r < 0 || r >= _size) return 0; T tmp = _elem[r]; int i; for (i = r; i < _size-1; ++i) { _elem[i] = _elem[i+1]; } --_size; return tmp; } //是否非降序排列（true乱序 false有序） template <typename T> bool Vector<T>::disordered() { for (int i = 0; i < _size-1; ++i) { if (_elem[i+1] < _elem[i]) return true; } return false; } //冒泡排序 template <typename T> void Vector<T>::bubbleSort() { int i, j, temp; for (i = _size-1; i > 0; --i) { int flag = 0; for (j = 0; j < i; ++j) { if (_elem[j+1] < _elem[j]) { temp = _elem[j]; _elem[j] = _elem[j+1]; _elem[j+1] = temp; flag = 1; } } if (flag == 0) return; } } //按照非降排序 template <typename T> void Vector<T>::sort(enum sort_method method) { switch (method) { case BUBBLE: bubbleSort(); break; case INSERT: break; case QUICK: quicksort(0, _size); break; case MERGE: mergesort(0, _size); break; default: break; } } //无序时查找 template <typename T> int Vector<T>::findInRange(T e, int lo, int hi) { for (int i = lo; i < hi; ++i) { if (_elem[i] == e) return i; } return -1; } //有序查找 返回不大于e的最大元素的位置 template <typename T> int Vector<T>::searchInRange(T e, int lo, int hi) { while (lo < hi) { int mid = lo + (hi - lo) / 2; if (e < _elem[mid]) { hi = mid; } else { lo = mid + 1; } } return lo-1; } template <typename T> int Vector<T>::search(T e) { return searchInRange(e, 0, _size); } template <typename T> int Vector<T>::find(T e) { return findInRange(e, 0, _size); } //无序向量去重 返回重复个数 template <typename T> int Vector<T>::deduplicate() { int oldsize = _size; for (int i = 0; i < _size; ++i) { if (findInRange(_elem[i], 0, i) >= 0) remove(i); } return oldsize - _size; } //有序向量去重 template <typename T> int Vector<T>::uniquify() { int oldsize = _size; int i = _size - 2; while (i >= 0) { if (_elem[i] == _elem[i+1]) remove(i+1); --i; } return oldsize - _size; } //快速排序的划分 template <typename T> int Vector<T>::partition(int lo, int hi) { int r = rand() % (hi - lo + 1) + lo; int x = _elem[r]; _elem[r] = _elem[lo]; while (lo < hi) { while (hi > lo && !(_elem[hi] < x)) --hi; _elem[lo] = _elem[hi]; while (lo < hi && !(x < _elem[lo])) ++lo; _elem[hi] = _elem[lo]; } _elem[lo] = x; return lo; } //快速排序 template <typename T> void Vector<T>::quicksort(int lo, int hi) { if (hi - lo < 2) return; int mid = partition(lo, hi - 1); quicksort(lo, mid); quicksort(mid+1, hi); } template <typename T> void Vector<T>::merge(int lo, int mid, int hi) { T * L = new int[mid-lo]; int i; int lenL = mid - lo; for (i = lo; i < mid; ++i) L[i-lo] = _elem[i]; i = 0; int j = mid; int k = lo; while (i < lenL && j < hi) { if (!(_elem[j] < L[i])) _elem[k++] = L[i++]; else _elem[k++] = _elem[j++]; } while (i < lenL) _elem[k++] = L[i++]; delete[] L; } template <typename T> void Vector<T>::mergesort(int lo, int hi) { if (hi - lo < 2) return; int mid = lo + (hi - lo) / 2; mergesort(lo, mid); mergesort(mid, hi); merge(lo, mid, hi); } template <typename T> void Vector<T>::expand() { _capacity *= 2; T *old = _elem; _elem = new T[_capacity]; for (int i = 0; i < _size; ++i) { _elem[i] = old[i]; } delete[] old; } template <typename T> void Vector<T>::decrease() { _capacity /= 2; T *old = _elem; _elem = new T[_capacity]; for (int i = 0; i < _size; ++i) { _elem[i] = old[i]; } delete[] old; } #endif |
vector.cpp
|
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 |
#include <iostream> #include "Vector.h" using namespace std; template <typename T> class MyPrint { public: void operator()(T e) { cout << e << " "; } }; int main() { Vector<int> a(5); a.insert(0, 2); a.insert(0, 6); a.insert(0, 7); // cout << a.capacity() << endl; a.insert(0, 4); a.insert(0, 4); a.insert(0, 5); a.insert(0, 9); a.insert(0, 9); a.insert(0, 5); a.insert(0, 5); a.insert(0, 9); a.insert(0, 9); a.insert(0, 5); // cout << a.capacity() << endl; MyPrint<int> visit; // a.travser(visit); a.sort(); a.travser(visit); cout << endl; cout << a.search(1) << endl; cout << a.search(2) << endl; cout << a.search(3) << endl; //cout << "uniquify " << a.uniquify() << endl; //cout << "deduplicate " << a.deduplicate() << endl; //cout << a.search(7, 0, a.size()); //cout << a.search(8, 0, a.size()); return 0; } |
列表（List）接口
概述
- 使用链表实现
- 一个初始的List包含了哨兵头结点和尾结点
构造函数和析构函数
- List()
- 大小初始化为0，头结点和尾结点互相指向
- ~List()
- 释放链表中所有结点的内存
整体属性
- int size();
- 返回元素个数
- bool empty();
- 判断列表是否为空
- bool disordered();
- 如果不是有序的，返回true
元素操作
- Posi(T) first();
- 返回第一个元素的位置
- 若列表为空 返回的是尾结点的位置
- Posi(T) last();
- 返回最后一个元素的位置
- 若列表为空，返回的是头结点的位置
- Posi(T) insertAsFirst(T e);
- 把e插入到列表的头部
- 返回新插入结点的位置
- Posi(T) insertAsLast(T e);
- 把e插入到列表的尾部
- 返回新插入结点的位置
- Posi(T) insertAfter(Posi(T) p, T e);
- 把e插入到p指向结点的后面
- 不检查p是否有效
- Posi(T) insertBefore(Posi(T) p, T e);
- 把e插入到p指向结点的前面
- 不检查p是否有效
- T remove(Posi(T) p);
- 删除p指向的结点
- 不检查p是否有效
排序查找
- void sort();
- 按照非降顺序进行插入排序
- Posi(T) find(T e);
- 查找元素e，返回第一个e的结点指针
- 找不到时，返回NULL
- Posi(T) search(T e);
- 有序列表查找，返回不大于e的最后一个元素结点位置
遍历
- void travser(VST &visit);
- 遍历，对结点中每个元素执行visit()
C++实现
最新的代码见Github。list.h是实现文件，list.cpp是简单的演示。
yalewoo/cpp-data-structure · GitHub
下面的代码可能不会及时更新
list.h
|
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 |
#ifndef MY_LIST_H #define MY_LIST_H #include <iostream> #define Posi(T) ListNode<T>* template <typename T> struct ListNode { T data; Posi(T) pred; Posi(T) next; ListNode() = default; ListNode(T e, Posi(T) p = NULL, Posi(T) n = NULL) : data(e), pred(p), next(n) { } Posi(T) insertPred(T e); Posi(T) insertNext(T e); }; template <typename T> class List { protected: int _size; ListNode<T> head; ListNode<T> tail; public: List(); ~List(); int size() {return _size; } bool empty() {return !_size; } Posi(T) first() {return head.next;} Posi(T) last() {return tail.pred;} Posi(T) insertAsFirst(T e); Posi(T) insertAsLast(T e); template <typename VST> void travser(VST &visit); //遍历 Posi(T) insertAfter(Posi(T) p, T e); Posi(T) insertBefore(Posi(T) p, T e); T remove(Posi(T) p); bool disordered(); void sort(); Posi(T) find(T e); Posi(T) search(T e); }; template <typename T> List<T>::~List() { Posi(T) x = head.next; Posi(T) x1 = x; while (x != &tail) { x1 = x; x = x->next; delete x1; } } template <typename T> Posi(T) ListNode<T>::insertPred(T e) { Posi(T) x = new ListNode(e, this->pred, this); this->pred->next = x; this->pred = x; return x; } template <typename T> Posi(T) ListNode<T>::insertNext(T e) { Posi(T) x = new ListNode(e, this, this->next); this->next->pred = x; this->next = x; return x; } template <typename T> List<T>::List() { _size = 0; head.next = &tail; tail.pred = &head; head.pred = NULL; tail.next = NULL; } template <typename T> Posi(T) List<T>::insertAsFirst(T e) { Posi(T) x = new ListNode<T> (e, &head, head.next); head.next->pred = x; head.next = x; ++_size; return x; } template <typename T> Posi(T) List<T>::insertAsLast(T e) { Posi(T) x = new ListNode<T> (e, tail.pred, &tail); tail.pred->next = x; tail.pred = x; ++_size; return x; } template <typename T> template <typename VST> void List<T>::travser(VST &visit) { Posi(T) x = head.next; while (x != &tail) { visit(x->data); x = x->next; } } template <typename T> Posi(T) List<T>::insertAfter(Posi(T) p, T e) { Posi(T) x = new ListNode<T> (e, p, p->next); p->next = x; x->next->pred = x; ++_size; return x; } template <typename T> Posi(T) List<T>::insertBefore(Posi(T) p, T e) { Posi(T) x = new ListNode<T> (e, p->pred, p); p->pred = x; x->pred->next = x; ++_size; return x; } template <typename T> T List<T>::remove(Posi(T) p) { T tmp = p->data; p->pred->next = p->next; p->next->pred = p->pred; delete p; --_size; return tmp; } template <typename T> bool List<T>::disordered() { Posi(T) p = head.next; T e = p->data; while (p != &tail) { if (p->data < e) return true; e = p->data; p = p->next; } return false; } template <typename T> void List<T>::sort() { Posi(T) i = head.next; Posi(T) j = i; while (i != &tail) { for (j = head.next; j != i && j->data <= i->data; j = j->next) ; Posi(T) newi = i->next; j->insertPred(i->data); remove(i); i = newi; } } template <typename T> Posi(T) List<T>::find(T e) { Posi(T) x = head.next; while (x != &tail) { if (x->data == e) return x; x = x->next; } return 0; } //return the largest x which is not bigger than e //so we can use List.insertAfter(List.search(e), e) to insert e in a sorted list template <typename T> Posi(T) List<T>::search(T e) { Posi(T) x = head.next; while (x != &tail && x->data <= e) { x = x->next; } return x->pred; } #endif |
list.cpp
|
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 |
#include <iostream> #include "List.h" using namespace std; template <typename T> class MyPrint { public: void operator()(T e) { cout << e << " "; } }; int main() { List<int> l; l.insertAsFirst(5); Posi(int) p = l.insertAsFirst(4); l.insertAsFirst(3); l.insertAsFirst(8); l.insertAsFirst(22); l.insertBefore(l.insertAsFirst(2), 9); MyPrint<int> visit; l.travser(visit); l.remove(p); cout << endl; l.travser(visit); cout << endl; //cout << l.disordered(); l.sort(); l.insertAfter(l.search(7), 7); l.travser(visit); return 0; } |
支付宝打赏 
微信打赏