动态数组C语言实现

时间:2021-08-27 04:15:34
/*
 * DynamicArray.h
 *
 *  Created on: 2019年7月22日
 *      Author: Jarvis
 */

#ifndef SRC_DYNAMICARRAY_H_
#define SRC_DYNAMICARRAY_H_

//动态增长内存 策略 将数据放到堆上
//动态数组 如果5个元素 申请内存 拷贝数据 释放内存
// 容量 capacity 表示我的这块内存空间一共可以存放多少个元素
// size  记录当前数组中具体的元素个数

//定义动态数组的结构体
typedef struct DYNAMICARRAY {
    int *pAddr;// 存放数据的地址
    int size;//当前有多少个元素
    int capacity;//容量, 容器当前能容纳多少个元素
}Dynamic_Array;

//操作函数
//初始化
Dynamic_Array *Init_Array();

//插入
void PushBack_Array(Dynamic_Array *arr, int value);

//根据位置删除
void RemoveByPos_Array(Dynamic_Array *arr, int pos);

//根据值删除
void RemoveByValue_Array(Dynamic_Array *arr, int value);

//查找
int Find_Array(Dynamic_Array *arr, int value);

//打印
void Print_Array(Dynamic_Array *arr);

//释放动态数组的内存
void FreeSpace_Array(Dynamic_Array *arr);

//清空数组
void Clear_Array(Dynamic_Array *arr);

//获得动态数组的容量
int Capacity_Array(Dynamic_Array *arr);

//获得动态数组当前元素的个数
int Size_Array(Dynamic_Array *arr);

//根据位置获得某个位置的元素
int At_Array(Dynamic_Array *arr, int pos);






#endif /* SRC_DYNAMICARRAY_H_ */
/*
 * DynamicArray.c
 *
 *  Created on: 2019年7月22日
 *      Author: Administrator
 */

#include <stdlib.h>



#include "DynamicArray.h"
Dynamic_Array *Init_Array() {
    Dynamic_Array *myArray = (Dynamic_Array *)malloc(sizeof(Dynamic_Array));
    myArray->size = 0;
    myArray->capacity = 20;
    myArray->pAddr = (int *)malloc(sizeof(int)*myArray->capacity);
    return myArray;
}

//插入
void PushBack_Array(Dynamic_Array *arr, int value) {
    if(arr == NULL){
        return;
    }
    //判断控件是否足够
    if(arr->size  == arr->capacity){
        //第一步 申请一块更大的内存空间 ,新空间是旧空间的2倍
        int *newSpace = 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 - 1; i++){
        arr->pAddr[i] = arr->pAddr[i+1];
    }
    arr->size--;

}

//根据值删除
void RemoveByValue_Array(Dynamic_Array *arr, int value) {
    if(arr == NULL){
        return;
    }
    //找到值的位置
    int pos = -1;
    for(int i = 0; i< arr->size; i++){
        if(arr->pAddr[i] == value){
            pos = i;
            break;
        }
    }
    //根据位置 删除值
    RemoveByPos_Array(arr, pos);
}

//查找
int Find_Array(Dynamic_Array *arr, int value) {
    if(arr == NULL){
            return -1;
        }
        //找到值的位置
        int pos = -1;
        for(int i = 0; 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 FreeSpace_Array(Dynamic_Array *arr) {
    if(arr == NULL){
        return;
    }
    if(arr->pAddr != NULL){
        free(arr->pAddr);
    }
    free(arr);

}
//清空数组
void Clear_Array(Dynamic_Array *arr) {
    if(arr == NULL){
        return;
    }
    arr->size = 0;
}

//获得动态数组的容量
int Capacity_Array(Dynamic_Array *arr) {
    if(arr == NULL){
        return -1;
    }
    return arr->capacity;
}


//获得动态数组当前元素的个数
int Size_Array(Dynamic_Array *arr) {
    if(arr == NULL){
        return 0;
    }
    return arr->size;
}

//根据位置获得某个位置的元素
int At_Array(Dynamic_Array *arr, int pos) {
    return arr->pAddr[pos];
}


/*
 * mian.c
 *
 *  Created on: 2019年7月22日
 *      Author: Administrator
 */


#include "DynamicArray.h"

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void test01(){
    //初始化动态数组
    Dynamic_Array *arr = Init_Array();

    //打印 capacity size
    printf("after create arr, capacity: %d, size: %d \n",arr->capacity, arr->size);
    //插入元素
    for(int i = 0; i < 10; i++){
        PushBack_Array(arr, i);
    }

    //打印
    printf("插入10个元素后 \n");
    Print_Array(arr);

    //插入元素

    for(int i = 0; i < 30; i++){
        PushBack_Array(arr, i);
    }
    //打印
    printf("重新插入30个元素后 \n");
    Print_Array(arr);

    //删除
    RemoveByPos_Array(arr, 0);
    RemoveByValue_Array(arr, 5);
    //
    printf("删除两个元素后 \n");
    Print_Array(arr);


    //查找
    int pos = Find_Array(arr, 30);
    printf("位置 5查找到  pos: %d  value: %d \n",pos, At_Array(arr, pos));
    //销毁
    FreeSpace_Array(arr);

}

int main(){
    printf("动态数组  \n");
    test01();
    system("pause");
    return 0;
}