数据结构之静态顺序表和动态顺序表_动态顺序表和静态顺序表的区别

@Sock对静态顺序表和动态顺序表的总结

简单概括他们的异同点

相同点:内存空间连续, 数据顺序存储

不同点:它们所占内存空间的位置不同, 静态定义一个顺序表, 顺序表所占的内存空间开辟在内存的静态区, 即所谓的函数栈上, 随着函数调用的结束, 这块内存区域会被系统自动回收; 而动态生成一个顺序表, 顺序表所占的内存空间开辟在内存的动态区, 即所谓的堆内存上, 这块区域不会随着函数调用的结束被系统自动回收, 而是需要程序员主动去释放它.

各自优点(个人认为)

静态顺序表:操作简单, 不用手动释放其内存空间, 不存在内存泄漏

动态顺序表:可以动态开辟内存空间, 操作灵活, 避免不必要的开销

静态顺序表的实现

定义一个静态顺序表

//定义一个静态顺序表
#define MAXSIZE 100
typedef int ElemType;
ElemType SqList[MAXSIZE];
int len;
1
2
3
4
5

向静态顺序表中插入元素

//向静态顺序表中插入元素
void InsertElem(ElemType* S, int* len, int pos, ElemType e) {
   
	//判断插入位置是否合理
	if (*len == MAXSIZE || pos < 1 || pos > *len + 1) {
   
		printf("表满或插入位置不合理\n");
		exit(0);
	}
	//调整插入位置, 准备插入指定元素
	for (int i = *len - 1; i >= pos - 1; --i) {
   
		*(S + i + 1) = *(S + i);
	}
	//插入指定元素
	*(S + pos - 1) = e;
	//元素个数加 1
	++(*len);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

从静态顺序表中删除元素

//向静态顺序表中删除元素
void DelElem(ElemType* S, int* len, int pos) {
   
	//判断删除位置是否合理
	if (pos < 1 || pos > *len) {
   
		printf("删除位置不合理\n");
		exit(0);
	}
	//调整删除位置, 准备删除指定元素
	for (int i = pos; i < *len; ++i) {
   
		*(S + i - 1) = *(S + i);
	}
	//元素个数减 1
	--(*len);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

遍历静态顺序表

//遍历顺序表
void Traverse(ElemType* S) {
   
	for (int i = 0; i < len; ++i) {
   
		printf("%d ", *(S + i));
	}
	printf("\n");
}

1
2
3
4
5
6
7
8
9
10

测试

#include <stdio.h>
#include <windows.h>

//定义一个静态顺序表
#define MAXSIZE 100
typedef int ElemType;
ElemType SqList[MAXSIZE];
int len;

//向静态顺序表中插入元素
void InsertElem(ElemType* S, int* len, int pos, ElemType e) {
   
	//判断插入位置是否合理
	if (*len == MAXSIZE || pos < 1 || pos > *len + 1) {
   
		printf("表满或插入位置不合理\n");
		exit(0);
	}
	//调整插入位置, 准备插入指定元素
	for (int i = *len - 1; i >= pos - 1; --i) {
   
		*(S + i + 1) = *(S + i);
	}
	//插入指定元素
	*(S + pos - 1) = e;
	//元素个数加 1
	++(*len);
}

//向静态顺序表中删除元素
void DelElem(ElemType* S, int* len, int pos) {
   
	//判断删除位置是否合理
	if (pos < 1 || pos > *len) {
   
		printf("删除位置不合理\n");
		exit(0);
	}
	//调整删除位置, 准备删除指定元素
	for (int i = pos; i < *len; ++i) {
   
		*(S + i - 
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