设计自己的C语言版ArrayList

àì夳堔傛蜴生んèń 2022-06-09 04:09 164阅读 0赞

/\*  
时间：2012/06/24  
目的：设计自己的ArrayList  
\*/  
\# include <stdio.h>  
\# include <malloc.h>  
\# include <stdlib.h> //支持realloc函数  
//\# include <alloc.h>  //某些编译器用realloc函数用此库文件

struct Array//定义了一个数组类型  
\{  
 int \* pArr;//数组名  
 int len;//数组的长度  
 int cnt;//有效元素的个数  
 double increment;//增长因子（为大于0小于1） 当数组满了的时候，新数组长度 = 当前长度 \* (1+增长因子);  
\};

bool init(struct Array \* arr, int len);  
bool isEmpty(struct Array \* arr);  
bool isFull(struct Array \* arr);  
void showElements(struct Array \* arr);  
void showAllElements(struct Array \* arr);  
bool appendElement(struct Array \* arr, int val);  
bool insertElement(struct Array \* arr, int index, int val);  
bool deleteElement(struct Array \* arr, int index, int \* val);  
int get(struct Array \* arr, int index);  
void sort(struct Array \* arr);  
void inverse(struct Array \* arr);  
void increment(struct Array \* arr);

int main(void)  
\{  
 struct Array arr;  
 int len = 5;  
 init(&arr, len);  
 appendElement(&arr, 1);  
 appendElement(&arr, 3);  
 appendElement(&arr, 4);  
 bool isOk = insertElement(&arr, 1, 2);  
 printf("isOk = %d\\n", isOk);  
 insertElement(&arr, 4, 5);

insertElement(&arr, 5, 6);  
 showElements(&arr);  
 //showAllElements(&arr);

insertElement(&arr, 6, 7);  
 appendElement(&arr, 8);  
 appendElement(&arr, 9);  
 appendElement(&arr, 10);  
 showElements(&arr);

int val;//被删除的元素  
 deleteElement(&arr, 3, &val);  
 showElements(&arr);  
 printf("被删除的元素是：%d\\n", val);

inverse(&arr);  
 showElements(&arr);

sort(&arr);  
 showElements(&arr);

int num = get(&arr, 3);  
 printf("取出的数是：%d\\n",num);

return 0;  
\}

bool init(struct Array \* arr, int len)//初始化数组  
\{  
 if (len < 1)//处理不合法的数组长度  
 \{  
  printf("数组的长度必须大于0\\n");  
  exit(-1);//结束程序  
 \}

arr->pArr = (int \*)malloc(sizeof(int) \* len);

if (NULL == arr->pArr)//内存分配失败   【注】 NULL 大写  
 \{  
  printf("sorry,内存分配失败0\\n");  
  exit(-1);//结束程序  
 \}

arr->len = len;  
 arr->cnt = 0;  
 arr->increment = 0.5;//每次数组满了的时候，增长原来空间的一半的空间

return true;  
\}

bool isEmpty(struct Array \* arr)  
\{  
 if (0 == arr->cnt)  
  return true;  
 else  
  return false;  
\}

bool isFull(struct Array \* arr)  
\{  
 if (arr->len == arr->cnt)  
  return true;  
 else  
  return false;  
\}

void showElements(struct Array \* arr)  
\{  
 if ( isEmpty(arr) )  
 \{  
  printf("数组为空！\\n");  
  return;//退出函数  
 \}

for (int i=0; i<arr->cnt; i++)//只输出有效的元素  
 \{  
  if (i!=0 && i%5==0)//每行输出五个元素  
   printf("\\n");  
  printf("%d ", arr->pArr\[i\]);  
 \}  
 printf("\\n");  
\}

void showAllElements(struct Array \* arr)  
\{  
 if ( isEmpty(arr) )  
 \{  
  printf("数组为空！\\n");  
  return;//退出函数  
 \}

for (int i=0; i<arr->len; i++)//输出所有的元素  
 \{  
  if (i!=0 && i%5==0)//每行输出五个元素  
   printf("\\n");  
  printf("%d ", arr->pArr\[i\]);  
 \}  
 printf("\\n");  
\}

bool appendElement(struct Array \* arr, int val)//在数组末尾增加一个元素  
\{  
 if ( isFull(arr) )  
 \{  
  printf("数组已满了，开始自动扩容。\\n");  
  increment(arr);  
 \}  
   
 arr->pArr\[arr->cnt\] = val;//在数组末尾增加一个元素val  
 arr->cnt++;//数组实际个数加1

return true;  
\}

bool insertElement(struct Array \* arr, int index, int val)//在数组下标为index处插入一个元素  
\{  
 if (index<0 || index>arr->cnt)//处理不合法的数组长度  
 \{  
  printf("插入元素的位置只能从0到%d\\n", arr->cnt);  
  return false;  
 \}

if ( isFull(arr) )  
 \{  
  printf("数组已满了，开始自动扩容。\\n");  
  increment(arr);  
 \}  
   
 for (int i=arr->cnt; i>index; i--)//从index下标开始的元素各自向后移一位。  
  arr->pArr\[i\] = arr->pArr\[i-1\];

arr->pArr\[index\] = val;//在数组下标为index处插入一个元素val  
 arr->cnt++;//数组实际个数加1

return true;  
\}

bool deleteElement(struct Array \* arr, int index, int \* val)//删除数组中下标为index的元素  
\{  
 if (index<0 || index>=arr->cnt)//处理不合法的数组长度  
 \{  
  printf("删除元素的位置只能从0到%d\\n", arr->cnt - 1);  
  return false;  
 \}

\*val = arr->pArr\[index\];//把被删除的数发送给主调函数中的val变量。  
   
 for (int i=index; i < (arr->cnt - 1); i++)//从index下标开始的元素各自向后移一位。  
  arr->pArr\[i\] = arr->pArr\[i+1\];

free( &(arr->pArr\[arr->cnt-1\]) );//释放数组最后一个元素的内存

arr->cnt--;//数组实际个数减1  
 arr->len--;//数组实际长度减1

return true;   
\}

int get(struct Array \* arr, int index)//获得数组下标为index的元素  
\{  
 if (index<0 || index>=arr->len)//处理不合法的数组长度  
 \{  
  printf("获取元素的位置只能从0到%d\\n", arr->len - 1);  
  exit(-1);//结束程序  
 \}

return arr->pArr\[index\];  
\}

void inverse(struct Array \* arr)//把有效的元素倒置  
\{  
 int i = arr->cnt-1;  
 int j = 0;  
 int tmp;

while (i > j)  
 \{  
  tmp = arr->pArr\[i\];  
  arr->pArr\[i\] = arr->pArr\[j\];  
  arr->pArr\[j\] = tmp;  
  i--;  
  j++;  
 \}  
\}

void increment(struct Array \* arr)  
\{  
 int newLen = arr->len \* (1 + arr->increment);  
 printf("newLen = %d\\n", newLen);  
 printf("原数组的地址是%p\\n", arr->pArr);  
 arr->pArr = (int \*)realloc(arr->pArr, newLen\*sizeof(int) );//此函数会自动保留之前数组中的元素。【注】千万别忘了\*sizeof(int)，因为newLen是新数组的长度，而不是所占的内存大小  
 printf("新的原数组的地址是%p\\n", arr->pArr);

if (NULL == arr->pArr)  
 \{  
  printf("重新分配内存失败，程序已终止。");  
  exit(-1);  
 \}  
   
 arr->len = newLen;//千万别忘了修改原数组的长度。  
\}

void sort(struct Array \* arr)  
\{  
 bool flag;  
 int i, j;  
 int tmp;

for (i=0; i<arr->len; ++i)  
 \{  
  flag = true;//提高效率  
  for (j=0; j < (arr->len - i - 1); ++j)  
  \{  
   if ( arr->pArr\[j\] > arr->pArr\[j+1\])//按成绩升序  
   \{  
    flag = false;//有元素进行了大小交换。  
    tmp = arr->pArr\[j\];  
    arr->pArr\[j\] = arr->pArr\[j+1\];  
    arr->pArr\[j+1\] = tmp;  
   \}  
  \}  
  if (flag)//所有元素本次都没有进行大小交换，说明排序已经完成。因此跳出最外层的循环。  
   break;  
 \}  
\}  
/\*  
程序运行的结果：  
===========================================================================  
isOk = 1  
数组已满了，开始自动扩容。  
newLen = 7  
原数组的地址是00790F08  
新的原数组的地址是00790F08  
1 2 3 4 5  
6  
数组已满了，开始自动扩容。  
newLen = 10  
原数组的地址是00790F08  
新的原数组的地址是00790F08  
1 2 3 4 5  
6 7 8 9 10  
1 2 3 5 6  
7 8 9 10  
被删除的元素是：4  
10 9 8 7 6  
5 3 2 1  
1 2 3 5 6  
7 8 9 10  
取出的数是：5  
===========================================================================

总结：  
\---------------------------------------------------------------------------------------  
struct Array//定义了一个数组类型  
\{  
 int \* pArr;//数组名  
 int len;//数组的长度  
 int cnt;//有效元素的个数  
 double increment;//增长因子（为大于0小于1） 当数组满了的时候，新数组长度 = 当前长度 \* (1+增长因子);  
\};

精华为此结构体的定义  
它体现了封装的思想  
\---------------------------------------------------------------------------------------  
\*/