数组
数组是一种线性表数据结构。它用一组连续内存空间，来存储一组具有相同数据类型数据。
1.线性表：数据存储像一条线一样的结构，每个线性表上的数据最多只有前和后的两个方向，如数组、链表、队列、栈等都是这种结构，所以实现的数组的动态操作，其他结构也可轻易的类似实现。更重要的是，在这之后看源码就可大大降低难度。（博主自己看的是STL源码剖析）
2.非线性表：如二叉树、堆、图等。
3连续内存空间和相同数据类型：当数组作插入、删除操作时，为了保证数据的连续性，往往需要做大量的数据搬移工作，效率很低。
动态数组功能实现
1.数组初始化
考虑到扩容时数据搬移可能会发生的内存泄露，博主这里采用两只手的原则，即设定一个内存标志位 ItemsFlag 。当 ItemsFlag = 0，using preitems；当 ItemsFlag = 1，using items。下文扩容部分有具体实现。默认数组容量10。
|
1
2
3
4
5
6
7
8
9
|
enum { MAX = 10 };explicit GenericArray(int ss = MAX);template<class T>GenericArray<T>::GenericArray(int ss) : capacity(ss),counts(0){ itemsFlag = 0; preitems = new T[capacity]; items = nullptr;} |
2.析构函数
释放内存。
|
1
2
3
4
5
6
7
8
|
template<class T>GenericArray<T>::~GenericArray(){ if (preitems != nullptr) delete[]preitems; if (items != nullptr) delete[]items;} |
3.检查下标
检查要操作的下标是否在数组容量范围内。
|
1
2
3
4
5
6
7
8
9
10
11
12
|
template<class T>bool GenericArray<T>::checkIndex(int index){ if (index < 0 || index >= capacity) { int cap = capacity - 1; cout << "Out of the range! Please ensure the index be in 0 ~ " << cap << '\n'; return false; } return true;} |
4.获取元素数目和容量、判断数组空和满
|
1
2
3
4
|
int count()const { return counts; }int getCapacity()const { return capacity; }bool isEmpty()const { return counts == 0; }bool isFull()const { return counts >= capacity; } |
5.取索引对应值、按索引修改值、打印输出、是否包含某值
|
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
|
template<class T>T GenericArray<T>::get(int index){ if (!itemsFlag) return preitems[index]; else return items[index];}void GenericArray<T>::set(int index, T elem){ if(checkIndex(index)) { if (!itemsFlag) preitems[index] = elem; else items[index] = elem; return; }}template<class T>void GenericArray<T>::printArray()const{ for (int i = 0; i < counts; i++) if (!itemsFlag) cout << preitems[i] << '\t'; else cout << items[i] << '\t'; cout << '\n'; return;}template<class T>bool GenericArray<T>::contains(T arr){ for (int i = counts - 1; i >= 0; i--) if (!itemsFlag) { if (arr == preitems[i]) return true; } else { if (arr == items[i]) return true; } return false;} |
6.查找某值下标、删除某值
查找某值的下标时，要考虑到该值在数组中是否重复，所以博主用了一个结构体 findArrIndex 来存储该值重复的次数和对应的下标。
|
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
|
struct findArrIndex{ int numIndex; int *findIndex;};template<class T>void GenericArray<T>::find(T arr, findArrIndex *ps){ ps->findIndex = new int[counts]; ps->numIndex = 0; for (int i = 0, j = 0; i < counts; i++, j++) if (!itemsFlag) { if (arr == preitems[i]) { (ps->findIndex)[j] = i; (*ps).numIndex++; cout << i << '\t'; } } else if (arr == items[i]) { (ps->findIndex)[j] = i; (*ps).numIndex++; cout << i << '\t'; } cout << '\n'; return;}template<class T>void GenericArray<T>::removeElement(findArrIndex *ps){ for (int i = ps->numIndex; i > 0; i--) remove((ps->findIndex)[i - 1]); delete[](ps->findIndex);}template<class T>void GenericArray<T>::set(int index, T elem){ if(checkIndex(index)) { if (!itemsFlag) preitems[index] = elem; else items[index] = elem; return; }} |
7.扩容
添加数据操作时需判断数组容量是否足够，若不够需考虑扩容。
|
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
|
template<class T>void GenericArray<T>::renewCapacity(){ cout << "The array's capacity is small! Renew capacity.\n"; if (capacity < 1000) capacity = capacity << 1; else capacity = capacity >> 1 + capacity; if (!itemsFlag) { itemsFlag = 1; items = new T[capacity]; for (int i = 0; i<counts; i++) *(items + i) = *(preitems + i); //items[i]=proitems[i]; //cout << items << '\n'; //cout << preitems << '\n'; delete[]preitems; preitems = nullptr; } else { itemsFlag = 0; preitems = new T[capacity]; for (int i = 0; i<counts; i++) *(preitems + i) = *(items + i); delete[]items; items = nullptr; }} |
8.添加数据：数组添加数据包括按索引下标插值、数组头插值、数组尾插值。实质上后两种都可以通过调用按索引下标插值函数实现。前文也提到过，数组添加操作中复杂的是大量的数据搬移工作：将某个元素按索引下标插入到数组第k个位置，需要将k ~ n部分的元素向后搬移一位，然后插入元素，更新元素数目。若插入到数组尾，时间复杂度O(1)；插入到数组头，时间复杂度O(n)；插入的平均时间复杂度为（1+2+…+n）/n = O(n)。
另外，还有一个优化问题：若数组是无序数组，则插入时不需要搬移数据：若将某个元素插入到数组第k个位置，首先将该位置的元素移动到数组末尾，然后将待插入元素插入到第k个位置，时间复杂度O(1)。
|
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
|
template<class T>void GenericArray<T>::add(int index, T elem){ if (isFull()) { cout << "Array is full!" << '\n'; renewCapacity(); } if (checkIndex(index)) if(!itemsFlag) { for (int i = counts; i > index; i--) preitems[i] = preitems[i - 1]; preitems[index] = elem; } else { for (int i = counts; i > index; i--) items[i] = items[i - 1]; items[index] = elem; } counts++; return;}template<class T>void GenericArray<T>::addFirst(T elem){ add(0, elem);}template<class T>void GenericArray<T>::addLast(T elem){ add(counts, elem);} |
9.删除数据：数组删除数据包括按索引下标删除、数组头删除、数组尾删除。实质上后两种都可以通过调用按索引下标删除函数实现。与前文类似，数组删除操作中复杂的也是大量的数据搬移工作：按索引下标将某个元素删除，需要将k+1 ~ n部分的元素向前搬移一位，更新元素数目。若删除数组尾，直接元素数目减一即可，时间复杂度O(1)；删除数组头，时间复杂度O(n)；删除的平均时间复杂度（1+2+…+n）/n = O(n)。
另外，有一个优化问题：如果想多次删除数组中的值，可以先对要删除的值做好标记，做完标记后一次删除，这样就大大减少了搬移的次数。
|
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
|
template<class T>T GenericArray<T>::remove(int index){ if (!isEmpty()) { if (checkIndex(index)) { if (!itemsFlag) { T temp = preitems[index]; for (int i = index+1; i < counts; i++) preitems[i - 1] = preitems[i]; counts--; return temp; } else { T temp = items[index]; for (int i = index + 1; i < counts; i++) items[i - 1] = items[i]; counts--; return temp; } } } else { cout << "Array is empty!" << '\n'; return -1; }}template<class T>T GenericArray<T>::removeFirst(){ return remove(0);}template<class T>T GenericArray<T>::removeLast(){ return remove(counts - 1);} |
好啦，基本上就这么多了。
最后总结一下，多看源码还是很重要的。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/weixin_43428242/article/details/83989513
