线性表-动态数组ArrayList

C语言构建类似java的动态数组

1、定义

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
#define InitSize 10 //初始化长度
typedef int ElemType ;
 struct _ArrayList{
    ElemType *node;//节点
    int length;//链表长度
    int size;//链表有效个数大小
};
typedef struct _ArrayList ArrayList;

2、初始化

/**
 * 功能：初始化链表
 * 参数：链表地址
 * 返回值：如果成功，true，如果失败 false
 */
bool Init_List(ArrayList *pList){
    pList->node=(ElemType*)malloc(sizeof(ElemType)*InitSize);//分配节点初始化空间
    if(pList->node==NULL){
        printf("pList->node动态内存分配失败！\n");
        return false;
    }

    pList->length=InitSize;
    pList->size=0;
    printf("初始化成功\n");
    return true;
}

3、判断空表

/**
 * 功能：判断链表是否是空表
 * 参数：链表地址
 * 返回值：true 是  false 否
 */
bool IsEmpty(ArrayList *pList){
    if(pList->size==0){
        return true;
    }
    return false;
}

4、获取已分配的长度

/**
 * 功能：获取已分配的长度
 * 参数：链表地址
 * 返回值
 */
int Length_List(ArrayList *pList){
    return pList->length;
}

5、获取有效长度

/**
 * 功能：获取有效长度
 * 参数：链表地址
 * 返回值
 */
int Size_List(ArrayList *pList){
    return pList->size;
}

6、插入操作

  /**
 * 功能：向链表插入数据元素 前置条件:链表已初始化，1<=index<=pList->size+1
 * 参数：链表地址 下标  插入的元素
 * 返回值：链表长度
 */
bool Insert_List(ArrayList *pList,int index, ElemType e){
    if(pList->node==NULL){
        printf("链表未初始化\n");
        return false;
    }
    if(index<1||index>pList->size+1){
        printf("下标越界\n");
        return false;
    }
    //判断是否需要动态添加空间
    if(pList->length==pList->size){
        int newLength=(pList->length*3)/2+1;
        pList->node=realloc(pList->node,sizeof(ElemType)*newLength);
        pList->length=newLength;
    }
    if(!IsEmpty(pList) && index<pList->size+1){
        //插入数据时从最后一个开始到index的位置向后面移动一个位置
        for(int i=pList->size;i>=index;i--){
            pList->node[i]=pList->node[i-1];
        }
    }
    pList->node[index-1]=e;
    pList->size++;
    return true;
}

7、删除操作

   /**
 * 功能：删除某个下标的值 前置条件:链表已初始化，1<=index<=pList->size
 * 参数：链表地址 下标 返回删除的长度
 * 返回值：true 成功 false 失败
 */
bool Delete_List(ArrayList *pList,int index, ElemType *e){
    if(pList->node==NULL){
        printf("链表未初始化\n");
        return false;
    }
    if(index<1||index>pList->size){
        printf("下标越界\n");
        return false;
    }

    *e=pList->node[index-1];
    for(int i=index-1;i<pList->size-1;i++){
        pList->node[i]=pList->node[i+1];
    }
    pList->size--;
    if((pList->length-pList->size)>(InitSize*2)){
       int newLength=pList->length-InitSize;
       pList->node=realloc(pList->node,sizeof(ElemType)*newLength);
       pList->length=newLength;
    }
    return true;
}

8、查找元素

/**
 * 功能：查找元素，返回下标
 * 参数：链表地址 元素
 * 返回值: 下标 -1 为查找不到
 */
int Search_List(ArrayList *pList,ElemType e){
    if(IsEmpty(pList)){
        return -1;
    }
    for(int i=0;i<pList->size;i++){
        if(pList->node[i]==e){
            return i+1;
        }
    }
    return -1;
}

9、获取下标的元素

/**
 * 功能：获取某个下标的元素
 * 参数：链表地址 下标
 * 返回值: 元素
 */
bool GetElem(ArrayList *pList,int index,ElemType *e){
    if(IsEmpty(pList)){
        return false;
    }
    if(index<1||index>pList->size){
         printf("数组下标越界\n");
         return false;
    }
    *e=pList->node[index-1];
    return true;

}

10、遍历

/**
 * 功能：遍历链表
 * 参数：链表地址
 */
void Show_List(ArrayList *pList){
    if(IsEmpty(pList)){
        printf("[]\n");
        return ;
    }
    bool flag=true;
    printf("[");
    for(int i=0;i<pList->size;i++){
        if(flag){
            printf("%d",pList->node[i]);
            flag=false;
        }else{
            printf(",%d",pList->node[i]);
        }
    }
    printf("]\n");
}

11、追加元素

  /**
 * 功能：向链表追加一个数据元素
 * 参数：链表地址 插入的元素
 * 返回值：true false
 */
bool Append_List(ArrayList *pList, ElemType e){
    return Insert_List(pList,pList->size+1,e);
}

12、清空线性表

/**
 * 功能：清空线性表
 * 参数：pList：链表地址
 * 返回值：true false
 */
bool List_Clear(ArrayList *pList){
    ElemType* node=pList->node;
    pList->node=NULL;
    free(node);
    pList->length=0;
    pList->size=0;
    return true;
}

测试

int main()
{
    ArrayList pList;
    Init_List(&pList);
    Insert_List(&pList,1,5);
        Insert_List(&pList,1,4);
        Insert_List(&pList,1,5);
        Insert_List(&pList,1,7);
        Insert_List(&pList,1,7);
        Insert_List(&pList,1,4);
        Insert_List(&pList,1,7);
        Insert_List(&pList,1,56);
        Insert_List(&pList,1,8);
        Insert_List(&pList,1,3);
        Insert_List(&pList,7,3);
    printf("length:%d,size:%d\n",pList.length,pList.size);
    Insert_List(&pList,1,4);
    printf("length:%d,size:%d\n",pList.length,pList.size);
    Insert_List(&pList,1,1);
    printf("length:%d,size:%d\n",pList.length,pList.size);
    Show_List(&pList);
    int val;
    Delete_List(&pList,5,&val);
    printf("删除的元素%d\n",val);
    printf("length:%d,size:%d\n",pList.length,pList.size);

    Show_List(&pList);
    printf("开始清除\n");
    List_Clear(&pList);
    Show_List(&pList);
    Append_List(&pList,10000);
    Init_List(&pList);
    Append_List(&pList,23432);
    Show_List(&pList);
   int index=Search_List(&pList,3);
    printf("下标为%d\n",index);
    GetElem(&pList,5,&val);
    printf("获取的元素%d\n",val);
    return 0;
}