数据结构【动态数组】

数据结构【动态数组】

在堆中申请数组空间，扩容时realloc，注意不可增删改的情况并处理即可。
以下代码不一定完全正确。

1. #include <stdio.h>
2. #include <stdlib.h>
4. /**
5. * 声明动态数组，并提供相关的函数操作
6. */
9. // 动态数组结构体
10. typedef struct Array
11. {
13.     // 动态数组
14.     int *elementData;
16.     // 容量
17.     size_t capacity;
19.     // 长度
20.     size_t size;
22. } DynamicArray;
26. // 初始化动态数组
27. void initDynamicArray(DynamicArray *array, size_t initialCapacity);
28. // 释放动态数组内存
29. void destroyDynamicArray(DynamicArray *array);
30. // 调整动态数组内存大小
31. void resizeDynamicArray(DynamicArray *array, size_t newCapacity);
32. // 获取动态数组长度（元素个数）
33. size_t getLength(const DynamicArray *array);
34. // 在指定位置插入新元素
35. void insertAt(DynamicArray *array, size_t index, int element);
36. // 在末尾插入新元素
37. void insertEnd(DynamicArray *array, int element);
38. // 删除指定位置的元素并返回被删除的元素
39. int deleteAt(DynamicArray *array, size_t index);
40. // 删除末尾的元素并返回被删除的元素
41. int deleteEnd(DynamicArray *array);
42. // 遍历所有的元素
43. void print(DynamicArray *array);
46. /**
47. * 主函数
48. */
49. int main(int argc, char const *argv[])
50. {
51.     DynamicArray array;
52.     initDynamicArray(&array, 2);
53.     insertAt(&array, 0, 10);
54.     insertAt(&array, 0, 20);
55.     insertAt(&array, 0, 20);
56.     print(&array);
59.     getchar();
60.     return 0;
61. }
64. // 初始化动态数组
65. void initDynamicArray(DynamicArray *array, size_t initialCapacity){
67.     // 分配空间
68.     if (initialCapacity > 0) {
69.         array->elementData = (int *) malloc(initialCapacity * (sizeof(int)));
70.     } else if (initialCapacity == 0) {
71.         array->elementData = NULL;
72.     } else {
73.         printf("您输入的长度不合法。");
74.         return;
75.     }
77.     // 初始化capacity
78.     array->capacity = initialCapacity;
80.     // todo 初始化size
81.     array->size = 0;
82. }
83. // 释放动态数组内存
84. void destroyDynamicArray(DynamicArray *array){
85.     free(array->elementData);
86. }
88. // 扩容
89. void resizeDynamicArray(DynamicArray *array, size_t newCapacity){
90.     printf("1.5倍扩容启动\n");
91.     array->elementData = realloc(array->elementData, newCapacity*sizeof(int));
92.     array->capacity += array->capacity>>1;
93. }
95. // 获取动态数组长度（元素个数）
96. size_t getLength(const DynamicArray *array){
97.     return array->size;
98. }
100. // 在指定位置插入新元素
101. void insertAt(DynamicArray *array, size_t index, int element){
102.     // index 不符合规则的情况
103.     if(index < 0 || index > array->size){
104.         printf("无效的位置输入\n");
105.         return;
106.     }
107.     (array->size == array->capacity) ? resizeDynamicArray(array, array->capacity += array->capacity>>1) : 0;
108.     //
109.     for(int i = array->size; i>index; i--){
110.         array->elementData[i] = array->elementData[i-1];
111.     }
112.     array->elementData[index] = element;
113.     array->size++;
114. }
116. // 在末尾插入新元素
117. void insertEnd(DynamicArray *array, int element){
118.     insertAt(array, array->size, element);
119. }
121. // 删除指定位置的元素并返回被删除的元素
122. int deleteAt(DynamicArray *array, size_t index){
123.     if(index < 0 || index >= array->size){
124.         printf("无效的元素删除\n");
125.         return -1;
126.     }
127.     int temp = array->elementData[index];
128.     for(int i = index+1; i<array->size; i++){
129.         array->elementData[i-1] = array->elementData[i];
130.     }
131.     array->size--;
132.     return temp;
133. }
135. // 删除末尾的元素并返回被删除的元素
136. int deleteEnd(DynamicArray *array){
137.     return deleteAt(array, array->size-1);
138. }
140. // 遍历所有的元素
141. void print(DynamicArray *array){
142.     for(int i = 0; i<array->size; i++){
143.         printf("%d\n", array->elementData[i]);
144.     }
145.     printf("\n");
146. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！