顺序表与链表
顺序表
自动扩容，模仿C++ STL中Vector。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
using namespace std;
/*
* data -> 数据域
* size -> 顺序表大小
* length-> 已有元素
*/
typedef struct {
int *data;
int size, length;
}Vector;
//初始化大小为n的顺序表
Vector *init(int n) {
Vector *v = (Vector *)malloc(sizeof(Vector));
v->data = (int *)malloc(n * sizeof(int));
v->size = n;
v->length = 0;
return v;
}
/*
* 扩容操作
* malloc -> 开辟连续存储空间，并返回首地址
* calloc -> 动态分配内存，并将每块空间赋值为0
* realloc-> 重新分配内存，并将原来的内容拷贝进去，其返回值有两种：
* 1.返回空，2.返回这片空间的首地址
* 但是realloc实际很危险，当成功获得原空间n倍大小的空间后，此种情况均无问题
* 若新开辟的空间正好在原空间之后，加上原空间正好是n倍大小，
* 若原空间后面的空间不足，则需要重新开辟一片n倍大小的空间，
* 将原空间的数据拷贝进去，并会将原空间释放掉，
* 但若是分配空间失败，则会返回空地址
* 在这种情况下若v->data获取到空地址，则后面一段有数据的区域则会丢失，会出现严重bug
* 需要注意
*/
int expand(Vector *v) {
/*
* 危险的写法
* v->size *= 2;
* v->data = (int *)realloc(v->data, v->size * sizeof(int));
*/
int extr_size = v->size;
int *p;
while (extr_size) {
p = (int *)realloc(v->data, (v->size + extr_size) * sizeof(int));
//开辟成功，返回值不为空则退出，否则空间减半进行重新开辟空间的尝试
if (p) break;
extr_size /= 2;
}
//若尝试后都开辟不了则退出
if (p == NULL) return 0;
v->size += extr_size;
v->data = p;
return 1;
}
//在ind处往v插入值为val的元素
int insert(Vector *v, int ind, int val) {
if (v == NULL) return 0;
if (ind < 0 || ind > v->length) return 0;
//若已达到上线，则进行扩容操作
if (v->size == v->length) {
if (!expand(v)) return 0;
printf("Expand Vector size = (%d)\n", v->size);
}
for (int i = v->length + 1; i > ind; i --) {
v->data[i] = v->data[i - 1];
}
v->data[ind] = val;
v->length ++;
return 1;
}
//删除位于ind处的元素
int erase(Vector *v, int ind) {
if (v == NULL) return 0;
if (ind < 0 || ind >= v->length) return 0;
for (int i = ind + 1; i < v->length; i ++) {
v->data[i - 1] = v->data[i];
}
v->length --;
return 1;
}
void output(Vector *v) {
printf("Vector(%d) = [", v->length);
for (int i = 0; i < v->length; i ++) {
i && printf(",");
printf("%d", v->data[i]);
}
printf("]\n");
return ;
}
//释放顺序表
void clear(Vector *v) {
if (v == NULL) return ;
free(v->data);
free(v);
return ;
}
int main() {
//随机化测试
srand(time(0));
Vector *v = init(1);
//最大操作次数
int op, ind, val;
for (int i = 0; i < MAX_OP; i ++) {
op = rand() % 4;
//使其出现不合法的下标进行随机测试
ind = rand() % (v->length + 3) - 1;
val = rand() % 100;
switch(op) {
//使插入的概率比删除的概率大
case 3:
case 2:
case 0: {
int check = insert(v, ind, val);
printf("Insert val: %d at ind: %d into Vector %s\n", val, ind, check ? "successfully!" : "failed!");
output(v);
} break;
case 1: {
int check = erase(v, ind);
printf("Erase element at %d from Vector %s\n", ind, check ? "successfully!" : "failed!");
output(v);
} break;
}
puts("");
}
return 0;
}