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;
}
网友评论