c语⾔变长（动态）数组ArrayList
关于变长（动态）数组 ArrayList
缘起
在c语⾔的程序设计中，想要实现对⼀个数组的长度的动态变化其实是⽐较困难的，并且也是低效且不尽实⽤的。但是看到别⼈在做arraylist时，我决定将⽹课上所学习的变长数组放上来。另⼀⽅⾯，正是由于变长数组的缺点使得我们可以引⼊链表的学习。
代码
h⽂件中的代码样例
#ifndef __ARRAY_H__
#define __ARRAY_H__
typedef struct
{
int*array;
int size;
} Array;
Array array_create(int init_size);
void array_free(Array *a);
int array_size(const Array *a);
int*array_at(Array *a,int index);
void array_inflate(Array *a,int more_size);
#endif/* _____h */
c⽂件中的代码样例
#include"变长数组.h"
#include<stdio.h>
#include<stdlib.h>
#define BLOCK_SIZE 20
//typedef struct
//{
//    int *array;
//    int size;
//} Array;
Array array_create(int init_size)
{
Array a;
a.size = init_size;
a.array =(int*)malloc(sizeof(int)* a.size);
return a;
}
void array_free(Array *a)
{
free(a->array);
a->array =NULL;
a->size =0;
}
int array_size(const Array *a)
{
return a->size;
}
int*array_at(Array *a,int index)
{
if(index >= a->size)
array_inflate(a,(index / BLOCK_SIZE +1)* BLOCK_SIZE - a->size);
return&(a->array[index]);
}
void array_inflate(Array *a,int more_size)
{
c语言好的网课
int*p =(int*)malloc(sizeof(int)*(a->size + more_size));
for(int i =0; i < a->size;++i)
{
p[i]= a->array[i];
}
free(a->array);
a->array =NULL;
a->size += more_size;
}
缺点分析
1、变长
在进⾏较⼤的数组进⾏变长时，每次需要新建⼀个更⼤的数组（长度增⼤为 (index / BLOCK_SIZE + 1) * BLOCK_SIZE ，但是每次都需要进⾏拷贝操作，将原数组拷贝给更长的新数组然后释放原数组的内存。当变长操作需要多次重复的进⾏时，⽤变长数组的⽅式效率会⼤⼤降低。
2、内存
假设我们能使⽤的内存是有⼀定的⼤⼩限制的，使⽤变长数组的⽅式时，每次在原数组的后⾯新开⼀个更长的数组（若前⾯的已经被释放出的内存⾜够会在前⾯开）当数组长度⾮常⼤的时候，可能会因为前⾯的长度不够新开增长的数组，后⾯的内存⼜不够⽤，所以导致程序崩溃。也就是说，使⽤变长数组的⽅式进⾏储存，其实只能利⽤好所分配的内存的⼤约三分之⼀，这当然是⼀种既舍弃空间⼜缺乏时间的处理⽅式。
结语
由此，我们引⼊了链表这种数据结构。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。