avatar
文章
22
标签
8
分类
1
首页
时间轴
标签
分类
关于
清单
Aemonair
首页
时间轴
标签
分类
关于
清单
数据结构C语言实现7.动态数组
|Study
阅读量:

引言：

我们之前提到过 数组（Array），是一种数据结构，是数据元素（elements）的集合。

数组的特点：

1
2
3
4
5
6
7
8
//数组的缺点：
//
//    1.一旦数组定义，则大小固定，无法进行修改（数组的大小）。
//    2.数组插入和删除的效率太低，时间复杂度O（n）。
//    
// 数组的优点：
//    
//    1.下标访问，速度快，时间复杂度是O（1）

数组的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
//方法1
int array1[10] = {0};    

//方法2
int array2[] = {12, 23, 34, 45, 56, 67, 78};  

//方法3
int *array3 = NULL;
array3 = (int *)malloc(sizeof(int) * 100);   
if(array3 != NULL){
     fprintf(stderr, "the memory is full!\n");
     exit(1);
}

当初，我们说array1和array2都在定义时直接分配了栈上的内存空间;
而array3是一个int类型的指针，指向我们在堆上用malloc分配的4bytes ×100 = 400 bytes大小的空间。

普通情况下这样数组虽然在O(1)的时间复杂度访问下标进行数据存取查找，可是一般数组定义后，大小不能够进行动态变化，且插入删除效率过低，时间复杂度为O(n).
当初，为了弥补这些不足，我们又学习到了链表。而链表失去了很多数组的优点。
那怎么样才可以兼顾数组和链表的优点呢？今天我们将要学习动态数组。动态数组，是一种可以在任何时候改变大小的数组裝置。

一、动态数组基

动态数组是指在编译时不能确定数组长度，程序在运行时需要动态分配内存空间的数组。

我们要怎么样为数组分配到用来存储数据的空间呢。

1
2
3
4
5
6
7
8
9
10
NAME
       malloc, free, calloc, realloc - allocate and free dynamic memory

SYNOPSIS
       #include <stdlib.h>

       void *malloc(size_t size);
       void free(void *ptr);
       void *calloc(size_t nmemb, size_t size);
       void *realloc(void *ptr, size_t size);
  1. void *malloc(size_t size);
    malloc 向系统申请分配指定size个字节的内存空间。返回类型是 void* 类型。void* 表示未确定类型的指针。C,C++规定，void* 类型可以强制转换为任何其它类型的指针。
  2. void free(void *ptr);
    释放malloc(或calloc、realloc)函数给指针变量分配的内存空间的函数,释放申请的动态内存。
    使用后该指针变量一定要重新指向NULL，防止野指针出现，有效规避误操作。（另：对于free(p)这句语句，如果p 是NULL 指针，那么free 对p 无论操作多少次都不会出问题。如果p 不是NULL 指针，那么free 对p连续操作两次就会导致程序运行错误。）
  3. void *calloc(size_t nmemb, size_t size);
    在内存的动态存储区中分配n个长度为size的连续空间，函数返回一个指向分配起始地址的指针；如果分配不成功，返回NULL。
    一般使用后要使用 free(起始地址的指针) 对内存进行释放，不然内存申请过多会影响计算机的性能，以至于得重启电脑。如果使用过后不清零，还可以使用指针对该块内存进行访问。
  4. void *realloc(void *ptr, size_t size);
    realloc函数功能为先判断当前的指针是否有足够的连续空间，如果有，扩大mem_address指向的地址，并且将mem_address返回，如果空间不够，先按照newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来mem_address所指内存区域，同时返回新分配的内存区域的首地址，即重新分配存储器块的地址。
  1. 我们看到用malloc()可以自己在堆上定义大小分配的空间，所以我们可以用malloc()为我们提供分配内存的方法。
  2. 如果已分配的内存不够我们可以使用relloc()函数,再次申请内存。

于是，照常我们将这些需要经常使用的函数，放入工具类定义：
tools.h

1
2
3
4
5
6
7
8
9
10
11
12
13
#ifndef _TOOLS_H_
#define _TOOLS_H_

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


//工具类接口
void *Malloc(size_t size);
void swap(void *a, void *b, int length);
void *Realloc(void *ptr, size_t size);
#endif

tools.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
#include "tools.h"

void *Malloc(size_t size)
{
    void *result = malloc(size);
    if(result == NULL){
        fprintf(stderr, "the memory is full!\n");
        exit(1);
    }
    return result;
}

void swap(void *a, void *b, int length)
{
    void *temp = Malloc(length);
 
    memcpy(temp, a, length); 
    memcpy(a, b, length); 
    memcpy(b, temp, length);    

    free(temp);
}

void *Realloc(void *ptr, size_t size)
{
    void *result = realloc(ptr, size);
    if(result == NULL)
    {
        fprintf(stderr, "the memory is full !\n");
        exit(1);
    }
    return result;
}

照例可以使用迭代器：

iterator.h

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
#ifndef _ITERATOR_H_
#define _ITERATOR_H_

typedef struct Iterator
{
    void   *ptr;
    int   index;
    int    size;
}Iterator;

typedef Iterator iter;
/*
 *正向迭代器
 * container(list、array、stack)容器
 */

#define FOREACH(iter, container) \
    for(container->iter_head(&(iter), container); \
    (iter).ptr; \
    container->iter_next(&(iter), container))

#define foreach FOREACH

#define FOREACH_REVERSE(iter, container) \
    for(container->iter_tail(&(iter), container); \
    (iter).ptr; \
    container->iter_prev(&(iter), container))

#define foreach_reverse FOREACH_REVERSE

#endif

二、动态数组定义

dynamic_array.h

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
#ifndef _ARRAY_H_
#define _ARRAY_H_

#include "iterator.h"

#define TRUE       (1)
#define FALSE      (0)
#define MODE_SIZE  (32)
#define ZERO       (0)

typedef unsigned char Boolean;
typedef struct Array Array;

struct Array
{
    void    **data;    //1.存储实体
    int   capacity;    //2.动态数组申请大小
    int      count;    //3.当前元素个数

    //4.拷贝函数指针
    void *(*copy)(void *src_value);
    //5.匹配函数指针
    Boolean (*match)(void *value1, void *value2);
    //6.释放函数指针
    void (*free)(void *ptr);
    
    //7.头部插入
    Boolean (*push_front)(Array *array, void *value);
    //8.尾部插入
    Boolean (*push_back)(Array *array, void *value);
    //9.头部删除
    Boolean (*pop_front)(Array *array);
    //10.尾部删除
    Boolean (*pop_back)(Array *array);
    //
    //迭代器操作
    //11.指向数组头部的位置
    void *(*iter_head)(Iterator *iter, Array *array);
    //12.指向数组尾部的位置
    void *(*iter_tail)(Iterator *iter, Array *array);
    //13.指向后一个元素的位置
    void *(*iter_next)(Iterator *iter, Array *array);
    //14.指向前一个元素的位置
    void *(*iter_prev)(Iterator *iter, Array *array);
};

//动态数组接口
//1.初始化
Array *init_array(int init_size);
//2.销毁
void destroy_array(Array **array);
//3.清空
void clean_array(Array *array);
//4.插入到指定下标的前面
Boolean array_insert_prev(Array *array,
                         int index, void *value);
//5.插入到指定下标的后面
Boolean array_insert_next(Array *array,
                         int index, void *value);
//6.得到数组个数
int get_array_count(Array *array);
//7.得到指定下标元素
void *get_index_value(Array *array, int index);
//8.删除指定下标元素
Boolean delete_index_value(Array *array, int index);
//9.删除指定下标范围的元素
Boolean delete_range_value(Array *array, int begin, int end);
//10.查找指定元素的下标
int find_array_value(Array *array, void *value);

#endif

三、动态数组接口实现

dynamic_array.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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
#include "dynamic_array.h"
#include "tools.h"

//前插、尾插、前删、尾删、
static Boolean array_push_front(Array *array, void *value);
static Boolean array_push_back(Array *array, void *value);
static Boolean array_pop_front(Array *array);
static Boolean array_pop_back(Array *array);

//迭代器 头、尾、下一个、前一个
static void *array_iter_head(Iterator *iter, Array *array);
static void *array_iter_tail(Iterator *iter, Array *array);
static void *array_iter_next(Iterator *iter, Array *array);
static void *array_iter_prev(Iterator *iter, Array *array);

//封装数组增长函数
static void array_grow(Array *array, int size);
static int  adjust_size(int size);

//1. 数字调整
static int  adjust_size(int size)
{
    //MODE_SIZE == 32
    size += (MODE_SIZE -1);    //100 -> 100 +31
    size /= (MODE_SIZE);       //131 -> 131 /32 == 4
    size *= (MODE_SIZE);       //4   -> 4 * 32  == 128
                               //将其size增长到离size最近的32的倍数处
    return size;
}
//2.调整数组大小
static void array_grow(Array *array, int size)
{
    int adjust = 0;

    if(array->capacity < size)
    {
        adjust = adjust_size(size); //增长
        array->capacity = adjust;

        if(array->data != NULL)
        {
            array->data = Realloc(array->data,
                              sizeof(void *)*adjust);
        }
        else
        {
            array->data = Malloc(sizeof(void *)*adjust);
        }
    }
}

//数组的插入删除操作
//1.前插
static Boolean array_push_front(Array *array, void *value)
{
    return array_insert_prev(array, 0, value);
}
//2.尾插
static Boolean array_push_back(Array *array, void *value)
{
    if(array ==NULL || value == NULL)
    {
        return FALSE;
    }

    //如果数组容量不够，增长
    if(array->count >= array->capacity)
    {
        array_grow(array, array->count + MODE_SIZE);
    }

    array->data[array->count] = value ;
    array->count ++;

    return TRUE;
}
//3.前删
static Boolean array_pop_front(Array *array)
{
    int i =0 ;
    void *delete = NULL;
  
    if(array == NULL || array->count == ZERO)
    {
        return FALSE; 
    }
    array->count -- ;
  
    delete = array->data[0];
    if(array->free != NULL)
    {
        array->free(delete);
    }

    while(i < array->count)
    {
        array->data[i] = array->data[i+1];
        ++i;
    }

    array->data[i] = NULL;
    return TRUE;
}
//4.尾删
static Boolean array_pop_back(Array *array)
{
    void *delete = NULL;
    if(array == NULL || array->count == ZERO)
    {
        return FALSE; 
    }
    array->count -- ;
    delete = array->data[array->count];
    if(array->free != NULL)
    {
        array->free(delete);
    }
    
    array->data[array->count] = NULL;
    return TRUE;

}

//迭代器操作接口
//1. 迭代器头
static void *array_iter_head(Iterator *iter, Array *array)
{
    if(iter == NULL || array == NULL)
    {
        return NULL;
    }
    iter->index = 0;
    iter->size = array->count;
    if(array->data == NULL || array->count == ZERO)
    {
        iter->ptr = NULL;
    }
    else
    {
        iter->ptr = array->data[0];
    }
    return iter->ptr;
}
//2. 迭代器指向尾
static void *array_iter_tail(Iterator *iter, Array *array)
{
    if(iter == NULL || array == NULL)
    {
        return NULL;
    }
    iter->index = array->count -1;
    iter->size = array->count;
    if(array->data == NULL || array->count == ZERO)
    {
        iter->ptr = NULL;
    }
    else
    {
        iter->ptr = array->data[iter->index];
    }
    return iter->ptr;
}
//3. 迭代器 只想下一个数组元素
static void *array_iter_next(Iterator *iter, Array *array)
{
    if(iter == NULL || array == NULL)
    {
        return NULL;
    }
    iter->index ++;
    iter->size = array->count;
    if( iter->index >= iter->size)
    {
        iter->ptr = NULL;
    }
    else
    {
        iter->ptr = array->data[iter->index];
    }
    return iter->ptr;
}
//4. 迭代器 指向前一个数组元素
static void *array_iter_prev(Iterator *iter, Array *array)
{
    if(iter == NULL || array == NULL)
    {
        return NULL;
    }
    iter->index --;
    iter->size = array->count;
    if( iter->index <= ZERO)
    {
        iter->ptr = NULL;
    }
    else
    {
        iter->ptr = array->data[iter->index];
    }
    return iter->ptr;
}
//动态数组接口
//1.动态数组初始化
Array *init_array(int init_size)
{
    Array *array = (Array *)Malloc(sizeof(Array));
    //对控制信息成员进行初始化
    array->count = 0;

    //数组元素拷贝、比较、释放指针初始化为NULL
    array->free = NULL;
    array->match = NULL;
    array->copy = NULL;

    //头插、尾插、头删、尾删
    array->push_front = array_push_front;
    array->push_back  =  array_push_back;
    array->pop_front  =  array_pop_front;
    array->pop_back   =   array_pop_back;

    //迭代器操作
    array->iter_head = array_iter_head;
    array->iter_tail = array_iter_tail;
    array->iter_next = array_iter_next;
    array->iter_prev = array_iter_prev;

    array->data = NULL;
    array->capacity = 0;

    if(init_size > 0)
    {
        array_grow(array, init_size);
    }
    return array;
}
//2.动态数组的销毁
void destroy_array(Array **array)
{
    //释放数组元素对应的空间
    //释放data
    //释放array
    if(array == NULL)
    {
        return ;
    }
    delete_range_value(*array, 0, get_array_count(*array));

    free(*array);
    *array = NULL;
}
//3.动态数组清空
void clean_array(Array *array)
{
    if(array == NULL)
    {
        return ;
    }
    int i = 0 ;
    while(i < array->count)
    {
        array->data[i] =  NULL;
        ++i;
    }
}
//4.插入到指定下标的前面
Boolean array_insert_prev(Array *array, int index, void *value)
{
    int i = 0;
    if(array == NULL || value == NULL
                     || index > get_array_count(array))
    {
        return FALSE;
    }

    //如果数组容量不够，增长
    if(array->count+1 >= array->capacity)
    {
        array_grow(array, array->count + MODE_SIZE);
    }
    i = array->count;
    //index及以后的元素向后推移
    while(i > index)
    {
        array->data[i] = array->data[i-1];
        --i;
    }
    //插入元素
    array->count ++;
    array->data[i] = value;
    return TRUE;
}
//5.插入到指定下标的后面
Boolean array_insert_next(Array *array,
                         int index, void *value)
{
    int i = 0;
    if(array == NULL || value == NULL
                     || index > get_array_count(array))
    {
        return FALSE;
    }

    //如果数组容量不够，增长
    if(array->count+1 >= array->capacity)
    {
        array_grow(array, array->count + MODE_SIZE);
    }
    i = array->count;
    //index及以后的元素向后推移，从后向前防止被覆盖
    while(i > index)
    {
        array->data[i] = array->data[i-1];
        --i;
    }
    //插入元素
    array->count ++;
    array->data[i] = value;
    return TRUE;
}
//6.得到数组个数
int get_array_count(Array *array)
{
    if(array == NULL)
    {
        return -1;
    }
    return array->count;
}
//7.得到指定下标元素
void *get_index_value(Array *array, int index)
{
    if(array == NULL || index > get_array_count(array))
    {
        return NULL;
    }
    return array->data[index];
}
//8.删除指定下标元素
Boolean delete_index_value(Array *array, int index)
{
    int i = 0;
    if(array == NULL || index > get_array_count(array))
    {
        return FALSE;
    }

    i = index;
    //数组元素的移动，将其覆盖
    while(i < array->count)
    {
        array->data[i] = array->data[i+1];
        ++i;
    }
    //删除最后一个
    if(array->free != NULL)
    {
        free(array->data[array->count]);
    }
    array->data[array->count] = NULL;
    array->count --;
    return TRUE;
}
//9.删除指定下标范围的元素
Boolean delete_range_value(Array *array, int begin, int end)
{
#if 1
    int i = begin;
    int diff = end - begin + 1;
    int count = get_array_count(array);
// 0 1 2 3 4 5 6 7 8 9 
//     x x x           count:10  begin:2    end:4   diff:3
// 0 1 5 6 7 8 9 x x x
    if(array == NULL || begin > count || begin < 0 || end < 0
         || end > count || diff < 0 )
    {
        return FALSE;
    }

    //后面diff个元素向前推移
    while(i < count-diff)
    {
        array->data[i] = array->data[i+diff];
        ++i;
    }

    if(array->free != NULL)
    {
        i = array->count;
        while(i-- > count - diff)
        {
            free(array->data[i]);
            array->data[i] = NULL;
        }
    }
    array->count -= diff;
    return TRUE;
#endif
}
//10.查找指定元素的下标
int find_array_value(Array *array, void *value)
{
    int i = 0 ;
    int count = get_array_count(array);
    //printf("array_count:%d\n",count);
    if(array == NULL || value == NULL)
    {
        return -1;
    }
    #if 1
    //这里通过元素是否相同做比较
    while(i++ < count)
    {
        if(*((int *)(&array->data[i])) == *((int *)value))
        {
            return i;
        }
    }
    //或者通过匹配指针函数match
    #else
    for(i = 0 ; i < count; ++i)
    {
        if(array->match!=NULL)
        {
            if(array->match(array->data[i], value))
            {
                return i;
            }
        }
        else
        {
            if(array[data[i] == value)
            {
                return i;
            }
        }
    }
    return -1;
}

四、函数功能实现

文件结构：

1
2
3
4
5
6
7
8
├── dynamic_array
├── dynamic_array.c
├── dynamic_array.h
├── iterator.h
├── main
├── main.c
├── tools.c
└── tools.h

main.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
#include <stdio.h>
#include "iterator.h"
#include "dynamic_array.h"

int main(int argc, char **argv)
{
    int i = 0;
    Array *array= init_array(30);
    int a[] = {1, 2, 3, 4, 5};
    int length = sizeof(a)/sizeof(a[0]);
 
    for(i = 0; i < length; ++i)
    {
        array_insert_prev(array, i, &a[i]);
    }

    for(i = 0; i < length; ++i)
    {
        array_insert_next(array, i, &a[i]);
    }

    printf("array_count:");
    printf("%d \n",get_array_count(array));

    length = get_array_count(array);
    printf("length:%d\n",length);
    printf("Array :\n");
    for(i = 0; i < length; ++i)
    {
        printf("%d ",*(int *)array->data[i]);
    }
    printf("\n");
    printf("array_index_count_2:");
    printf("%d \n",*(int *)get_index_value(array, 2));


    printf("delete_index_value(array, 2):\n");
    delete_index_value(array, 2);

    length = get_array_count(array);
    for(i = 0; i < length; ++i)
    {
        printf("%d ",*(int *)array->data[i]);
    }
    printf("\n");
    
    delete_range_value(array, 1, 3);
    length = get_array_count(array);
    for(i = 0; i < length; ++i)
    {
        printf("%d ",*(int *)array->data[i]);
    }
    printf("\n");
/*    foreach(iter, array)
    {
        printf("%d ",*(int *)array->data[i]);
   }
 */
    printf("find_array_value(array, ?)\n");
    printf("array[5]: %d \n",find_array_value(array, &array->data[5]));
    printf("array[3]:%d \n",find_array_value(array, &array->data[3]));
    printf("\n");

    printf("clean_array(array)\n");
    clean_array(array);
    length = get_array_count(array);
    for(i = 0; i < length; ++i)
    return 0;
}

运行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
root@aemonair:# cc.sh *.c 
Compiling ...
-e CC      dynamic_array.c main.c tools.c -g -lpthread
-e         Completed .
-e         Fri Jun 24 11:51:10 CST 2016

root@aemonair:~# ./dynamic_array 
array_count:10 
length:10
Array :
1 2 3 4 5 1 2 3 4 5 
array_index_count_2:3 
delete_index_value(array, 2):
1 2 4 5 1 2 3 4 5 
1 1 2 3 4 5 
find_array_value(array, ?)
array_count:6
array[5]: 5 
array_count:6
array[3]:3 

clean_array(array)

总结

至此，我们已经完成了动态数组的实现。
我们可以从中看到，C语言可以用来实现各种各样的数据结构，同时，作为动态数组，我们多次使用malloc和free等函数，需要对内存的申请释放特别注意。
我们在其中所使用的各种通用思想，以及迭代器的方法，需要再深入理解。通过我们的新鲜知识对旧的知识点进行进一步拓展和提升。

文章作者: Air
文章链接: http://aemonair.github.io/2016/06/24/Data_Structure_07_Dynamic_array/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Aemonair！
DataStructArray
相关推荐
2020-04-29
数据结构C语言实现1.单链表
2020-04-29
数据结构C语言实现2.带控制信息的链表
2020-04-29
数据结构C语言实现4.进一步封装的双向链表
2020-04-29
数据结构C语言实现5.通用栈
2020-04-29
数据结构C语言实现6.通用队列
2020-04-29
数据结构C语言实现8.广义表
简