手撕数据结构一：线性表

手撕数据结构一：线性表

线性表可以理解为一维数组，数组即有一段连续的存储空间，可以存储任意类型的数据结构。数组还有两个属性，即数组大小(size)和数组内元素数量(length)，实现代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <map>
 7 #include <cmath>
 8 
 9 using namespace std;
10 
11 typedef struct Vector {
12     int *data;
13     int size, length;
14 } Vector;
15 
16 Vector *init(int n) {
17     Vector *v = (Vector *)malloc(sizeof(Vector));
18     v->data = (int *)malloc(sizeof(int) * n);
19     v->length = 0;
20     v->size = n;
21     return v;
22 }
23 
24 int insert(Vector *v, int ind, int val) {
25     if (ind < 0 || ind > v->length) return 0;
26     if (v->size == v->length) return 0;
27     for (int i = v->length - 1; i >= ind; i--) {
28         v->data[i + 1] = v->data[i];
29     }
30     v->data[ind] = val;
31     v->length += 1;
32     return 1;
33 }
34 
35 int erase(Vector *v, int ind) {
36     if (ind < 0 || ind > v->length) return 0;
37     for (int i = ind + 1; i < v->length; i++) {
38         v->data[i - 1] = v->data[i];
39     }
40     v->length -= 1;
41     return 1;
42 }
43 
44 void clear(Vector *v) {
45     if (v == NULL) return;
46     free(v->data);
47     free(v);
48     return;
49 }
50 
51 void output(Vector *v) {
52     cout << "arr = [ ";
53     for (int i = 0; i < v->length; i++) {
54         cout << v->data[i] << " ";
55     }
56     cout << "]" << endl;
57     return;
58 }
59 
60 int main() {
61     #define MAX_OP 20
62     int op, ind, val;
63     Vector *v = init(MAX_OP);
64     for (int i = 0; i < MAX_OP; i++) {
65         op = rand() % 4;
66         ind = rand() % (v->length + 3) - 1;
67         val = rand() % 100;
68         switch(op) {
69             case 0:
70             case 1:
71             case 2: {
72                 cout << "insert " << val << " to vector at " << ind << " = " << insert(v, ind, val) << endl;
73                 output(v);
74             } break;
75             case 3: {
76                 cout << "erase element at " << ind << " from vector = " << erase(v, ind) << endl;
77                 output(v);
78             } break;
79         }
80     }
81     clear(v);
82     return 0;
83 }

本博客为原创，如需转载请联系本人！

转载于:.html