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
| //預設初始化大小
#define INIT_SIZE 10
//預設擴展大小
#define EXT_SIZE 5
//定義陣列中每一個元素的資料型態
typedef int ElemType;
//結構成員定義
struct ArrayList {
ElemType *data;//陣列
size_t size;//目前陣列中數量，由1開始
size_t capacity;//陣列最大容量
};
/**
索引是否介於0... size-1
*/
bool checkIndex(const ArrayList& list, const size_t index) {
return index < list.size;
}
/**
清空list
*/
void ClearList(ArrayList& list) {
list.size = 0;
//代入的是陣列的最大容量list.capacity
memset(&list, 0, sizeof(ElemType) * list.capacity);
}
void initList(ArrayList& list) {
list.capacity = INIT_SIZE;
list.data = new ElemType[list.capacity];
ClearList(list);
}
void destroyList(ArrayList& list) {
delete [] list.data;
list.data = nullptr;
list.capacity = 0;
list.size = 0;
}
bool extList(ArrayList& list) {
int new_size = list.capacity + EXT_SIZE;
//建立新的陣列(容量比較大的陣列)
ElemType *new_data = new (std::nothrow) ElemType[new_size];
//如果記憶體分配失敗
if(new_data == nullptr) return false;
//清空新的陣列
memset(new_data, 0, sizeof(ElemType) * new_size);
//拷貝舊的陣列到新的陣列
memcpy(new_data, list.data, sizeof(ElemType) * list.size);
//把舊的陣列進行記憶體釋放
delete [] list.data;
//把結構中的陣列，指向新的陣列記憶體位址
list.data = new_data;
//重新定義結構中最大容量
list.capacity = new_size;
return true;
}
/**
插入元素
成功返回true，失敗返回false
index為陣列索引，介於0 - list.size之間，index為list.size也可以插入
element為插入元素
搬移
list[index...] -> list[index + 1 ...]
*/
bool insert(ArrayList& list, const size_t index, const ElemType& element) {
//判斷是否超出最大容量
if(list.size == list.capacity) {
//超出容量就擴展容量
if(!extList(list)) {
//若返回是false，代表建立新陣列記憶體配置產生問題
return false;
}
}
//檢查插入索引
if(index > list.size) {
cout << "insert的索引介於0-" << list.size << endl;
return false;
}
//insert的索引在中間，並非最後一個
//若插入的索引 == size，不用搬移資料，直接在最後面新增資料。
if(index < list.size) {
//搬移資料
//list[index...] -> list[index + 1 ...]
memmove(list.data + (index + 1), list.data + index , (list.size - index) * sizeof(ElemType));
}
//插入資料
memcpy(&list.data[index], &element, sizeof(ElemType));
//list的增加一個
list.size++;
return true;
}
/**
刪除元素
成功返回true，失敗返回false
index為陣列索引，介於0 - (list.size-1)
list[index+1...] 拷貝至-> list[index ...]
*/
bool del(ArrayList& list, const size_t index) {
//大小為0，不用刪除任何資料
if(list.size == 0) return false;
//檢查刪除索引
if(!checkIndex(list, index)) {
cout << "delete索引介於0-" << list.size - 1 << endl;
return false;
}
//若index不為最後一筆，要進行搬移
if(index < (list.size - 1)) {
//list[index + 1 ...] 拷貝-> list[index ...]
memmove(list.data + index, list.data + (index + 1), (list.size - index - 1) * sizeof(ElemType));
}
//總數量減1
list.size--;
return true;
}
void printList(const ArrayList& list) {
for(size_t i = 0; i < list.size; i++) {
cout << list.data[i] << endl;
}
}
/**
返回索引
找不到就返回-1
*/
int findElem(const ArrayList& list, const ElemType& e) {
for(int i = 0; i < list.size; i++) {
if(list.data[i] == e) return i;
}
return -1;
}
/**
取得元素
參數2index:索引
參數3:e 返回元素
*/
bool getElem(const ArrayList& list, const size_t index,ElemType& e) {
if(!checkIndex(list, index)) return false;
e = list.data[index];
return true;
}
int main() {
ArrayList list; //建立ArrayList
initList(list);//初始化
//ElemType是int
ElemType element;
element = 11;
//在索引0插入元素
insert(list, 0, element);
element = 12;
//在索引0插入元素
insert(list, 0, element);
element = 13;
//在索引0插入元素
insert(list, 0, element);
element = 14;
//在索引0插入元素
insert(list, 0, element);
element = 15;
//在索引0插入元素
insert(list, 0, element);
element = 16;
//在索引0插入元素
insert(list, list.size, element);
printList(list);
cout << "---------------------" << endl;
del(list,0);
printList(list);
destroyList(list);
return 0;
}
|
