【数据结构】动态数组

今天药忘吃喽~ 2022-05-16 08:45 237阅读 0赞

**1.头文件DynamicArray.h**

#ifndef DYNAMIC_ARRAY_H
    #define DYNAMIC_ARRAY_H
    
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    //定义存储int数据类型的动态数组
    //首先要有存放数据的地址 int* data
    //其次要记录当前容器中有多少个元素 int size
    //最后要记录容量 int capacity 显示当前容器所能承受的容量
    typedef struct {
    	int* data;//存放数据的地址
    	int size;//存放数据的个数
    	int capacity;//存放数据的容量
    }DynamicArray;
    //写一系列的相关对DYNAMICARRAY结构体操作的函数
    //初始化
    DynamicArray* initArray();
    //尾部插入
    void pushBack(DynamicArray* da, int value);
    //根据位置插入
    void insert(DynamicArray* da, int pos, int value);
    //删除最后一个元素
    void popBack(DynamicArray* da);
    //根据位置删除
    void deleteByPos(DynamicArray* da, int pos);
    //根据值删除,删除第一个匹配的值
    void deleteByValue(DynamicArray* da, int value);
    //查找
    int findByPos(DynamicArray* da, int pos);
    int getPositionByValue(DynamicArray* da, int value);
    //打印,传入一个用于打印的函数指针
    void printArray(DynamicArray* da);
    //释放动态数组的内存
    void releaseMemory(DynamicArray* da);
    //清空数组
    void clear(DynamicArray* da);
    //获得动态数组容量
    int getCapacity(DynamicArray* da);
    //获得动态数据当前元素个数
    int getSize(DynamicArray* da);
    //根据位置获得某个位置元素
    #endif

**2.实现文件DynamicArray.c**

#include "DynamicArray.h"
    //写一系列的相关对DynamicArray结构体操作的函数
    //初始化
    DynamicArray* initArray() {
    	//首先为结构体申请一片内存空间
    	DynamicArray* da = (DynamicArray*)malloc(sizeof(DynamicArray));
    	//设置元素数量为0
    	da->size = 0;
    	//设置初始容量为20
    	da->capacity = 20;
    	//为数据开辟一个内存空间
    	da->data = (int*)malloc(sizeof(int)*da->capacity);
    	return da;
    }
    //尾部插入
    void pushBack(DynamicArray* da, int value){
    	if (da == NULL) {
    		return;
    	}
    	//首先判断空间是否充足
    	if (da->size == da->capacity) {
    		//开辟两倍的内存空间
    		int* newMemory = (int*)malloc(sizeof(int)*2*da->capacity);
    		//将原来的数据复制到新的内存空间中
    		memcpy(newMemory, da->data, da->size);
    		//清空原内存
    		free(da->data);
    		da->data = newMemory;
    		da->capacity = 2 * da->capacity;
    	}
    	//保存数据
    	da->data[da->size]=value;
    	//size加一
    	da->size++;
    }
    //根据位置插入
    void insert(DynamicArray* da, int pos, int value) {
    	if (da == NULL) {
    		return;
    	}
    	//如果插入的位置不在指定的范围内就设置在末尾插入
    	if (pos < 0 || pos >= da->size) {
    		pos = da->size;
    	}
    	//插入数据
    	da->data[pos] = value;
    	da->size++;
    }
    //删除最后一个元素
    void popBack(DynamicArray* da) {
    	if (da == NULL) {
    		return;
    	}
    	//直接将size减一即可,我还让size位置处设置为默认0
    	da->data[da->size - 1] = 0;
    	da->size--;
    }
    //根据位置删除
    void deleteByPos(DynamicArray* da, int pos) {
    	if (da == NULL) {
    		return;
    	}
    	if (pos < 0 || pos >= da->size) {
    		return;
    	}
    	for (int i = pos; i < da->size - 1; i++) {
    		da->data[i] = da->data[i + 1];
    	}
    	//把最后一个设置为0
    	da->data[da->size - 1] = 0;
    	//size减1
    	da->size--;
    }
    //根据值删除,删除第一个匹配的值
    void deleteByValue(DynamicArray* da, int value) {
    	if (da == NULL) {
    		return;
    	}
    	//找出第一个匹配的值的位置
    	int pos=-1;
    	for (int i = 0; i < da->size; i++) {
    		if (value == da->data[i]) {
    			pos = i;
    			break;
    		}
    	}
    	//调用上面的函数进行删除
    	deleteByPos(da, pos);
    }
    //查找
    int findByPos(DynamicArray* da, int pos){
    	if (da == NULL) {
    		return -1;
    	}
    	if (pos < 0 || pos >= da->size) {
    		return -1;
    	}
    	return da->data[pos];
    }
    int getPositionByValue(DynamicArray* da,int value) {
    	if (da == NULL) {
    		return -1;
    	}
    	//找出第一个匹配的值的位置
    	int pos = -1;
    	for (int i = 0; i < da->size; i++) {
    		if (value == da->data[i]) {
    			pos = i;
    			break;
    		}
    	}
    	return pos;
    }
    //打印
    void printArray(DynamicArray* da) {
    	for (int i = 0; i < da->size; i++) {
    		printf("%d ", da->data[i]);
    		if (i%10 == 9) {
    			printf("\n");
    		}
    	}
    	printf("\n");
    }
    //释放动态数组的内存
    void releaseMemory(DynamicArray* da) {
    	if (da == NULL) {
    		return;
    	}
    	//先释放动态数组中的数据
    	if (da->data != NULL) {
    		free(da->data);
    	}
    	da->size = 0;
    	da->capacity = 0;
    	//最后释放数组
    	free(da);
    }
    //清空数组
    void clear(DynamicArray* da) {
    	if (da == NULL) {
    		return;
    	}
    	//直接把size该为0即可
    	da->size = 0;
    }
    //获得动态数组容量
    int getCapacity(DynamicArray* da) {
    	if (da == NULL) {
    		return -1;
    	}
    	return da->capacity;
    }
    //获得动态数据当前元素个数
    int getSize(DynamicArray* da) {
    	if (da == NULL) {
    		return -1;
    	}
    	return da->size;
    }