抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

数组

内存结构

数组是一种顺序存储的结构,他所占用的空间是固定的,不能随意增加或减小,其中所有元素以特定的方式按顺序排列下来,各个元素的位置都是固定的。因此数组是一种有序的线性结构

数组的随机访问性能优秀,因为只需要对首地址进行加减运算就能得到任意位置处的值

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{
//堆栈已满,返回false
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;
//输出为:5 3 1
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;//元素个数初始为0
queue->front = 0;//首元素为数组的第0项
queue->rear = Length - 1;//末元素为最后一项,而不是第0项,因为当前没有元素
for(int i=0;i<10;i++){
push(queue, i);
}
for(int i=0;i<10;i++){
cout << pop(queue) << " ";
}
return 0;
}

评论