动态数组
- 代码链接：https://pan.baidu.com/s/1Y9wAr9k-ZBSZs-GXRxAZdQ 提区码：ASDF
- 采用类模板动态数组
- 模板在编译时必须拿到完整的类型，所以声明定义一般都得再头文件内
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
101template<typename E>
class ArrayList //动态数组
{
private:
static const int DEFAULT_CAPACITY = 10; //默认容量
int size=0; //元素数量
E* elements= EMPTY_ELEMENTDATA; //元素数组
int length=0; //数组长度
public:
//有参构造，传入Capacity，会根据Capacity大小创建数组
inline ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this->elements = new E[initialCapacity] ;
length = initialCapacity;
}
else if(initialCapacity==0)
{
this->elements = EMPTY_ELEMENTDATA;
}
else
{
//...抛出异常
}
}
//无参构造数组为空
inline ArrayList() {
this->elements = EMPTY_ELEMENTDATA;
}
//list死亡释放
~ArrayList() {
delete[] elements;
}
public:
//返回数组元素
inline int getSize() {
return size;
}
//判断数组是否为空
inline bool isEmpty() {
return size == 0;
}
//是否包含元素 element
bool contains(E element) {
return indexOf(element) >= 0;
}
//返回元素element的索引
int indexOf(E element) {
return indexOfRange(element, 0, size);
}
//返回index索引处元素
E get(int index) {
checkIndex(index);
return elements[index];
}
//添加元素
void add(E e) {
add(e, elements, size);
}
//设置index索引处元素，返回旧值
E set(int index, E element);
//从start开始直到end范围查找element
int indexOfRange(E element, int start, int end);
//往index处添加element
void add(int index, E element);
private:
static const int MAX_VALUE =INT_MAX; //int类型最大值
static const int MAX_ARRAY_SIZE = MAX_VALUE - 8; //最大数组容量
//添加元素
void add(E e, E* elementData, int s);
//扩容
E* grow();
//扩容
E* grow(int minCapacity);
//扩容容量
int newCapacity(int minCapacity);
//返回容量
static int hugeCapacity(int minCapacity);
//拷贝数组
void arraycopy(E* elements1, int start1, E* elements2, int start2, int count);
//创建新数组并拷贝elementDate所有元素，并返回
E* copyOf(E* elementDate,int capacity);
//检查添加
void rangeCheckForAdd(int index);
//检查索引
void checkIndex(int index);
//异常处理
void outOfBounds(int index);
//返回最大值
int max(int val, int va2) {
return val > va2 ? val : va2;
}
};
indexOfRange
- 从start到end范围寻找元素element
1
2
3
4
5
6
7
8
9template<typename E>
int ArrayList<E>::indexOfRange(E element, int start, int end) {
E* es = elements;
for (int i = start; i < end; i++) {
if (es[i] == element)
return i;
}
return -1;
}
set
- 保存旧值赋值新值并返回
1
2
3
4
5
6template<typename E>
E ArrayList<E>::set(int index, E element) {
E oldValue = elements[index];
elements[index] = element;
return oldValue;
}add
- 扩容时机：当数组满的时候,与Java不同的是，在我们扩容后要对旧数组进行释放，而且要用delete[] 数组方式释放，因为在new E[]时候，会在内存保存一个值，他记录你创建的容量，在进行调用delete []时候会根据这个值进行相次数E的析构函数。
- 扩容为原来的1.5倍。
- 如果在使用的时候用的是你自己创建的类型，请设计好相对应的析构函数，防止内存泄漏。
- 使用方式:如果你不想根据索引值添加，只想在默认数组尾添加，只需要传入添加的元素即可。如果想根据你的索引添加元素，则索引必须满足0~size
- 数组索引从0开始
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
27template<typename E>
void ArrayList<E>::add(E e, E* elementData, int s) {
if (s == length)
{
E* oldelements = elements;
elements = grow();
delete[] oldelements;
}
elementData[s] = e;
size = s + 1;
}
template<typename E>
void ArrayList<E>::add(int index, E element) {
rangeCheckForAdd(index);
int s;
E* elementData=elements;
if ((s = size) == length)
{
E* oldelements = elements;
elements = grow();
delete[] oldelements;
}
arraycopy(elementData, index, elementData, index + 1, s - index);
elementData[index] = element;
size = s + 1;
}
arraycopy
- 这里我所设计的arraycopy只是简单满足一下上面进行数组拷贝，在根据索引插入元素时，会让其索引处到元素尾整体往后移动一格单位。同时我也不改变elements的指针，所以上面我就只用拷贝从索引处开始拷贝元素到索引后一位的位置起。
1
2
3
4
5
6
7
8
9template<typename E>
void ArrayList<E>::arraycopy(E* elements1, int start1, E* elements2, int start2, int count) {
int n1 = start1 + count-1;
int n2 = start2 + count-1;
while(n1>start1)
{
elements2[n2--] = elements1[n1--];
}
}
扩容
- 在这里扩容我是按一下规则（newCapacity一开始为原数组容量1.5倍)：
- newCapacity 少于等于 minCapacity
- 原数组为空,返回DEFAULT_CAPACITY，minCapacity之间最大值
- minCapacity < 0：代表minCapacity超过int整形允许的最大值，也就是发生”overflow”，这是我会让程序不正常地结束。
- 无以上情况就返回minCapacity
- newCapacity大于minCapacity
- newCapacity <= MAX_ARRAY_SIZE返回newCapacity
- newCapacity和minCapacity都上溢出了，那么就会终止程序
- newCapacity只要大于MAX_ARRAY_SIZE都会返回
MAX_VALUE(你所处平台地int允许最大值) - 不是以上情况(也就是等于MAX_ARRAY_SIZE)，则返回MAX_ARRAY_SIZE。
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
57static const int MAX_VALUE =INT_MAX; //int类型最大值
static const int MAX_ARRAY_SIZE = MAX_VALUE - 8; //最大数组容量
template<typename E>
E* ArrayList<E>::grow() {
return grow(size + 1);
}
template<typename E>
E* ArrayList<E>::grow(int minCapacity) {
return elements =copyOf(
elements, newCapacity(minCapacity)
);
}
template<typename E>
int ArrayList<E>::newCapacity(int minCapacity) {
int oldCapacity = length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elements ==EMPTY_ELEMENTDATA)
return max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
{
std::cout << "overflow" << std::endl;
exit(-1);
}
std::cout << "扩容为:" << newCapacity << std::endl;
return minCapacity;
}
return (newCapacity - ArrayList<E>::MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
template<typename E>
int ArrayList<E>::hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
{
std::cout << "overflow" << std::endl;
exit(-1);
}
return (minCapacity > ArrayList<E>::MAX_ARRAY_SIZE)
? ArrayList<E>::MAX_VALUE
: ArrayList<E>::MAX_ARRAY_SIZE;
}
template<typename E>
E* ArrayList<E>::copyOf(E* elementDate, int capacity) {
E* newelements = new E[capacity];
for (int i = 0; i < size; i++) {
newelements[i] = elementDate[i];
}
this->length = capacity;
std::cout << "数组容量更改为:" << capacity << std::endl;
return newelements;
}
- newCapacity 少于等于 minCapacity
异常情况
1 | template<typename E> |