/
my_list.c
137 lines (119 loc) · 3.16 KB
/
my_list.c
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
#include <stdio.h>
#include<stdlib.h>
#include<assert.h>
/* 列表类 */
typedef struct {
int *arr; // 数组(存储列表元素)
int capacity; // 列表容量
int size; // 列表大小
int extendRatio; // 列表每次扩容的倍数
} MyList;
int *toArray();
MyList *newMyList();
void delMyList(MyList *nums);
int size(MyList *nums);
int capacity(MyList *nums);
int get(MyList *nums, int index);
void set(MyList *nums, int index, int num);
void add(MyList *nums, int num);
void insert(MyList *nums, int index, int num);
int removeItem(MyList *nums, int index) ;
void extendCapacity(MyList *nums) ;
int *toArray(MyList *nums);
/* 构造函数 */
MyList *newMyList() {
MyList *nums = malloc(sizeof(MyList));
nums->capacity = 10;
nums->arr = malloc(sizeof(int) * nums->capacity);
nums->size = 0;
nums->extendRatio = 2;
return nums;
}
/* 析构函数 */
void delMyList(MyList *nums) {
free(nums->arr);
free(nums);
}
/* 获取列表长度 */
int size(MyList *nums) {
return nums->size;
}
/* 获取列表容量 */
int capacity(MyList *nums) {
return nums->capacity;
}
/* 访问元素 */
int get(MyList *nums, int index) {
assert(index >= 0 && index < nums->size);
return nums->arr[index];
}
/* 更新元素 */
void set(MyList *nums, int index, int num) {
assert(index >= 0 && index < nums->size);
nums->arr[index] = num;
}
/* 在尾部添加元素 */
void add(MyList *nums, int num) {
if (size(nums) == capacity(nums)) {
extendCapacity(nums); // 扩容
}
nums->arr[size(nums)] = num;
nums->size++;
}
/* 在中间插入元素 */
void insert(MyList *nums, int index, int num) {
assert(index >= 0 && index < size(nums));
// 元素数量超出容量时,触发扩容机制
if (size(nums) == capacity(nums)) {
extendCapacity(nums); // 扩容
}
for (int i = size(nums); i > index; --i) {
nums->arr[i] = nums->arr[i - 1];
}
nums->arr[index] = num;
nums->size++;
}
/* 删除元素 */
// 注意:stdio.h 占用了 remove 关键词
int removeItem(MyList *nums, int index) {
assert(index >= 0 && index < size(nums));
int num = nums->arr[index];
for (int i = index; i < size(nums) - 1; i++) {
nums->arr[i] = nums->arr[i + 1];
}
nums->size--;
return num;
}
/* 列表扩容 */
void extendCapacity(MyList *nums) {
// 先分配空间
int newCapacity = capacity(nums) * nums->extendRatio;
int *extend = (int *)malloc(sizeof(int) * newCapacity);
int *temp = nums->arr;
// 拷贝旧数据到新数据
for (int i = 0; i < size(nums); i++)
extend[i] = nums->arr[i];
// 释放旧数据
free(temp);
// 更新新数据
nums->arr = extend;
nums->capacity = newCapacity;
}
/* 将列表转换为 Array 用于打印 */
int *toArray(MyList *nums) {
return nums->arr;
}
int main(){
MyList *nums = malloc(sizeof(MyList));
nums->capacity = 10;
nums->arr = malloc(sizeof(int) * nums->capacity);
nums->size = 0;
nums->extendRatio = 2;
add(nums,10);
add(nums,9);
add(nums,8);
add(nums,7);
printf("%d\n", size(nums));
printf("%d\n", get(nums,0));
return 0;
}