数组
内存结构
数组是一种顺序存储的结构,他所占用的空间是固定的,不能随意增加或减小,其中所有元素以特定的方式按顺序排列下来,各个元素的位置都是固定的.因此数组是一种有序的线性结构
数组的随机访问性能优秀,因为只需要对首地址进行加减运算就能得到任意位置处的值
1
2
3
4
5
6
7
8
9
10
11
12
| int a[100];
for(int i=0;i<100;i++){
a[i] = i + 1;
}
cout << a[50] << endl;
除此之外,我们也可以使用地址直接获取元素的值
int a[100];
for(int i=0;i<100;i++){
a[i] = i;
}
cout << *(a + 50) << endl;
|
插入与删除
当从一个数组中删除第10个元素时,原本的第11个元素成了新的第10个元素,因此需要对10之后的元素进行移动操作
而在插入元素时,同样需要对数组里的元素进行移动操作
1
2
3
4
5
6
7
8
9
10
11
12
| int a[100];
void remove(int p){
for(int i=p+1;i<100;i++){
a[i-1] = a[i];
}
}
void add(int p, int num){
for(int i=98;i>=p;i--){
a[i+1] = a[i];
}
a[p] = num;
}
|
因此数组并不适合需要大量增删的场景,更适合于元素位置不会轻易改变的场景
堆栈
堆栈是一种先进后出的线性结构,他只能从数组的尾部进行增删.例如一个长度为100的数组,其中有10个元素,那么新的元素必须添加到11的位置上
堆栈类似于一个集装箱,每次都必须先把门口的货物搬走,才能搬里面的货物
在STL中已经有了堆栈容器,这里为了演示实现原理,采用结构体编写代码
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
| #define Length 100
#define Error -1
struct Stack{
int list[Length];
int count;
};
bool push(Stack * stack, int num){
if(stack->count < Length){
stack->list[stack->count] = num;
++(stack->count);
return true;
}else{
return false;
}
}
int pop(Stack * stack){
if(stack->count != 0){
--(stack->count);
return stack->list[stack->count];
}else{
return Error;
}
}
int main() {
Stack * stack = (Stack*) malloc(sizeof(Stack));
stack->count = 0;
push(stack,1);
push(stack,3);
push(stack,5);
cout << pop(stack) << endl;
cout << pop(stack) << endl;
cout << pop(stack) << endl;
return 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
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
| #define Length 5
#define Error -1
struct Queue{
int list[Length];
int front;
int rear;
int count;
};
bool push(Queue * queue, int num){
if(queue->count == Length){
return false;
}else{
queue->rear = (queue->rear + 1) % Length;
queue->list[queue->rear] = num;
++(queue->count);
return true;
}
}
int pop(Queue * queue){
if(queue->count == 0){
return Error;
}else{
int result = queue->list[queue->front];
queue->front = (queue->front + 1) % Length;
--(queue->count);
return result;
}
}
int main() {
Queue * queue = (Queue*) malloc(sizeof(Queue));
queue->count = 0;
queue->front = 0;
queue->rear = Length - 1;
for(int i=0;i<10;i++){
push(queue, i);
}
for(int i=0;i<10;i++){
cout << pop(queue) << " ";
}
return 0;
}
|
