动态数组

短命女 2022-04-22 13:44 188阅读 0赞

## 动态数组实现原理 ##

1.  插入元素，如果发现空间不足，则申请一块更大的内存空间
2.  将原来的数组内容搬移到新内存空间
3.  释放原来的内存空间
4.  跟新数组的信息（capacity，首地址等）

## 动态数组的代码实例 ##

DynamicArray.h

#ifndef DYNAMIC_ARRAY_H
    #define DYNAMIC_ARRAY_H
    
    typedef struct DYNAMIC_ARRAY_H
    { 
    		int* pAddr;
    		int size;
    		int capacity;
    }dynamic_array;
    
    
    
    dynamic_array* Init_Array(); //初始化动态数组
    
    void Push_Back_Array(dynamic_array* arr, int value);//插入元素
    
    void RemoveByPos_Array(dynamic_array* arr, int pos);//通过位置删除元素
    
    void RemoveByValue_Array(dynamic_array* arr, int value); //通过值删除元素
    
    void FreeSpace_Array(dynamic_array* arr);//释放整个动态数组
    
    int Find_Array(dynamic_array* arr, int value);//返回值为value的位置
    
    void Print_Array(dynamic_array* arr); //打印动态数组的内容
    
    void Clear_Array(dynamic_array* arr);//清空动态数组
    
    int Capacity_Array(dynamic_array* arr);//返回动态数组的capacity
    
    int Size_Array(dynamic_array* arr);//返回 动态数组的size
    
    int At_Array(dynamic_array* arr, int pos); //返回pos处的值
    
    
    #endif

DynamicArray.c

#include "../include/DynamicArray.h"
    #include <string.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    
    //初始化动态数组
    dynamic_array* Init_Array()
    { 
    	dynamic_array* MyArray =(dynamic_array*) malloc(sizeof(dynamic_array)); 
    	MyArray->size=0;
    	MyArray->capacity=20;//初始化的capacity为20
    	MyArray->pAddr = (int*)malloc(sizeof(int)*MyArray->capacity);
    
    	return MyArray;
    }
    
    
    
    //插入元素
    void Push_Back_Array(dynamic_array* arr, int value)
    { 
    	if(arr==NULL)return;
    
    	if(arr->size == arr->capacity)//元素个数等于容量的大小，得重新开辟内存空间
    	{ 
    			int* newspace =(int*) malloc(sizeof(int)*arr->capacity*2);
    			memcpy(newspace,arr->pAddr,arr->capacity*sizeof(int));//拷贝数据
    			free(arr->pAddr);//释放原来内存地址
    
    			arr->capacity =arr->capacity*2;
    			arr->pAddr=newspace;//赋值新地址
    	}
    
    	arr->pAddr[arr->size]=value;
    	arr->size++;
    		
    }
    
    
    
    //通过位置删除元素
    void RemoveByPos_Array(dynamic_array* arr, int pos)
    { 
    		if(arr==NULL)
    			return;
    
    		if(pos<0||pos>=arr->size)
    		    return;
    
    		for(int i=pos; i<arr->size;i++)
    		{ 
    				arr->pAddr[i]=arr->pAddr[i+1];
    		}
    		arr->size--;		
    }
    
    
    
    //通过值删除元素
    void RemoveByValue_Array(dynamic_array* arr, int value)
    { 
    		int pos=0;
    		if(arr==NULL)
    				return;
    
    		for(int i=0;i<arr->size;i++)
    		{ 
    				if(arr->pAddr[i]==value)
    				{ 
    						pos=i;
    						break;
    				}
    		}
    
    		RemoveByPos_Array(arr,pos);
    		
    }
    
    
    
    
    //释放动态数组
    void FreeSpace_Array(dynamic_array* arr)
    { 
    	if(arr==NULL) return;
    
    	if(arr->pAddr != NULL)
    			free(arr->pAddr);//数组的空间
    	free(arr);//存放动态数组结构体的空间
    }
    
    
    
    //找value的位置
    int Find_Array(dynamic_array* arr, int value)
    { 
    		if(arr==NULL)
    				return -1;
    
    		int pos=-1;
    		for(int i=1;i<arr->size;i++)
    		{ 
    				if(arr->pAddr[i]==value)
    				{ 
    						pos=i;
    						break;
    				}
    		}
    
    		return pos;
    }
    
    
    
    
    //打印动态数组
    void Print_Array(dynamic_array* arr)
    { 
    	for(int i=0; i<arr->size; i++)
    	{ 
    			printf("%d ",arr->pAddr[i]);
    	}
    
    	printf("\n");
    
    }
    
    //清除动态数组
    void Clear_Array(dynamic_array* arr)
    { 
    	if(arr==NULL)
    	{ 
    		return;
    	}
    
    	arr->size=0;	
    
    }
    
    
    
    //获取动态数组的capacity
    int Capacity_Array(dynamic_array* arr)
    { 
    	if(arr == NULL)
    			return 0;
    
    		return arr->capacity;
    }
    
    
    //获取动态数组的size
    int Size_Array(dynamic_array* arr)
    { 
    	if(arr ==NULL)	
    		return 0;
    
    	return arr->size;
    }
    
    
    
    //返回pos处的值
    int At_Array(dynamic_array* arr, int pos)
    { 
    	if(arr==NULL)
    		return 0;
    	return arr->pAddr[pos];
    }

main.c

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #include "../include/DynamicArray.h"
    
    
    
    
    int main(void)
    { 
    
    		dynamic_array* MyArray=Init_Array();
    
    		printf("%d\n ",Capacity_Array(MyArray));
    		printf("%d\n ",Size_Array(MyArray));
    
    		//内存不够申请两倍
    		for(int i=0;i<30;i++)
    		{ 
    				Push_Back_Array(MyArray,i);
    		}
    
    		 Print_Array(MyArray);
    		printf("%d \n",Capacity_Array(MyArray));
    		printf("%d \n",Size_Array(MyArray));
    		
    
    		// 删除
    		RemoveByPos_Array(MyArray,0);//删除位置0的元素
    		RemoveByValue_Array(MyArray,1);//删除第一个值为1的元素
    		Print_Array(MyArray);
    	
    		//查找
    		int pos = Find_Array(MyArray,5);
    		printf("%d 的位置是：%d",At_Array(MyArray,pos),pos);
    	     
    	      //释放
                  FreeSpace_Array(MyArray);
    		return 0;
    }

结果：

20  //初始capacity
    0  //初始size
    0 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 
    40 //插入30个元素，capacity不够，申请2倍大小capacity
    30 //插入30个元素，size是30
    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   //删除位置0的元素，和1的值
    5 的位置是：3   //得到5的位置是3