小工具知识网

当前位置: 首页 > 行业知识 > C语言数据结构一:动态数组

行业知识

C语言数据结构一:动态数组

2026-11-18 01:40:00 来源:互联网转载

一、概念认知

先说一个���念:数组是一段连续的内存空间。存储相同的数据类型。

()

数组的两个关键点:

  1. 连续内存;
  2. 相同类型。

第一个特征:起点。

首先连续内存:所以为了找到动态数组我们必须找到一个首元素地址。(内存首地址。)

()

如果不知道首地址,那无法找到并操作内存空间。

第二个特征:容量。

知道首地址了,我们需要知道元素的个数。动态数组:动态,可以动态插入、删除、扩展容量。所以我们必须有个初始容量。开辟多大空间,放多少个元素。除了容量,最好还有一个状态量:表示当前的数据量:也就是说长度。

  • 容量说的是:可以放多少数据。
  • 长度说的是:当前有多少数据。

    我的钱包(=银行)(容量)无限大,而我当前拥有的钱有限(长度)。

    第三个特征:类型。

    我们虽然有了首地址,也有了元素个数,但是我们还是不知道开辟多大空间。因为我们还需要元素的大小。元素所占内存的大小,其实就是元素的类型。可是:

    C语言无法动态获取数据的类型。

    好在我们还有void*类型可以指向任意类型的指针。

    所以我们虽然不知道具体元素的类型,但是我们可以定义一个通用的指针类型,指向我们的元素的地址即可。所以我们的元素就是地址。

    所以我们的元素类型就是void*。所以我们的数组指针就是void**类型。


     二、实现

    动态数组其实就是一种结构体。 一种自定义类型。

    2.1定义数据结构。

    先写数据信息结构。

     首地址,就像存储字符串数组一样。

    char * arr[] = {"aaa", "bbb", "ccc"};

     arr数组中每个元素都是char*类型,那么arr如果写入结构体中,可以定义为:

    struct DemoStruct{    char ** arr;    int b;}

     同样道理:元素类型为void*。那么定义数组则为void** arr;

    //1. 先把所需要的数据信息结构定义下来struct DynamicArray{//数组存储元素的空间的首地址void **addr;//存储数据的内存中最大能够容纳多少元素int capacity; //容量//当前存储数据的内存中有多少个元素int size; //大小};

    2.2 头文件

    #pragma once#include#include#include#ifdef __cplusplusextern "C"{#endif//1. 先把所需要的数据信息结构定义下来struct DynamicArray{//数组存储元素的空间的首地址void **addr;//存储数据的内存中最大能够容纳多少元素int capacity; //容量//当前存储数据的内存中有多少个元素int size; //大小};//初始化数组struct DynamicArray *Init_DynamicArray(int capacity);//插入元素void Insert_DynamicArray(struct DynamicArray *arr, int pos, void *data);//遍历void Foreach_DynamicArray(struct DynamicArray *arr, void(*_callback)(void *));//位置删除void RemoveByPos_DynamicArray(struct DynamicArray *arr, int pos);//按值删除void RemoveByValue_DynamicArray(struct DynamicArray *arr, void *data, int(*compare)(void*, void *));//销毁数组void Destroy_DynamicArray(struct DynamicArray *arr);#ifdef __cplusplus}#endif

    头文件中,我们要写入关于这个数组结构体的一些方法声明,然后去.c源文件中去实现。


    2.3初始化

    首先是初始化数组。给数组分配内存,也就是给这个结构体分配内存。

    我们的动态数组初始化也是:struct DynamicArray * arr = malloc(sizeof(struct DynamicArray));

    arr这个指针指向这个数组的结构体:即动态数组。

    动态数组其实就是一种结构体。 

    然后这个结构体的一个属性:首地址:首地址指向整个数组地址。为整个数组开辟空间。就像是char * arr = malloc(sizeof(char*)*Num)一样操作。

    arr->addr = malloc(sizeof(元素类型)* Num);这里Num为Capacity。元素类型为void*由使用方指定。

    arr->addr = malloc(sizeof(void*)*arr->capacity);

    此时没有插入值,所以size为零。

    //初始化数组struct DynamicArray *Init_DynamicArray(int capacity){if (capacity capacity = capacity;arr->addr = malloc(sizeof(void *)*arr->capacity);arr->size = 0;return arr;}

    2.4插入元素 

    此时注意我们输入函数的是结构体指针。

    //插入元素void Insert_DynamicArray(struct DynamicArray *arr, int pos, void *data){if (NULL == arr){return;}if (NULL == data){return;}if (pos  arr->size){        // 如果插入时,pos大于当前的长度,则直接把数据放在数组最后面。pos = arr->size;}//判断空间是否足够if (arr->size >= arr->capacity){//1. 申请一块更大的内存空间int newcapacity = arr->capacity * 2;   // C#中动态数组也是如此操作的。void **newspace = malloc(sizeof(void *)* newcapacity);//2. 将原来空间的数据拷贝到新空间memcpy(newspace, arr->addr, sizeof(void *)* arr->capacity);//3. 释放原来空间的内存free(arr->addr);//4. 更新addr指向arr->addr = newspace;arr->capacity = newcapacity;}//移动元素,给pos位置空出位置来for (int i = arr->size - 1; i >= pos; --i){arr->addr[i + 1] = arr->addr[i];}//将新元素插入到pos位置arr->addr[pos] = data;arr->size++;}

    2.5遍历查看 

    遍历时,我们不知道元素的内部结构(数据结构),所以这个打印查看函数,需要使用方提供,

    使用方调用我们这个方法,我们这个方法反向回调使用方的提供的函数。因为我们不知道使用方使用什么类型,使用方自己知道如何打印自己的数据结构(数据信息)。

    回调函数定义方法:

    返回值类型(*回调函数名称)(参数列表)

    //遍历void Foreach_DynamicArray(struct DynamicArray *arr, void(*_callback)(void *)){if (NULL == arr){return;}if (NULL == _callback){return;}for (int i = 0; i size; ++i){_callback(arr->addr[i]);}}

    2.6删除

    //位置删除void RemoveByPos_DynamicArray(struct DynamicArray *arr, int pos){if (NULL == arr){return;}if (pos  arr->size - 1){return;}for (int i = pos; i size - 1; ++i){arr->addr[i] = arr->addr[i + 1];}arr->size--;}
    //按值删除void RemoveByValue_DynamicArray(struct DynamicArray *arr, void *data, int(*compare)(void*, void *)){if (NULL == arr){return;}if (NULL == data){return;}if (NULL == compare){return;}for (int i = 0; i size; ++i){if (compare(arr->addr[i], data)){RemoveByPos_DynamicArray(arr, i);break;}}}

    2.7销毁

    //销毁数组void Destroy_DynamicArray(struct DynamicArray *arr){if (NULL == arr){return;}if (arr->addr != NULL){free(arr->addr);arr->addr = NULL;}free(arr);arr = NULL;}

    原则上,谁molloc的,谁free,但是具体元素数据指向哪里,我们并不知道,且使用方知道,使用方也必须开辟,使用方开辟,那就由使用方释放。我们只free我们自己开辟的,开辟从外到内,释放是从内到外:先释放内部属性的指针:arr->addr的内存,然后再释放整个结构体指针。

    使用方测试:

    #define _CRT_SECURE_NO_WARNINGS#include#include#include#include"DynamicArray.h"struct Person{char name[64];int age;};void myPrint(void *data){struct Person *person = (struct Person *)data;printf("Name:%s Age:%d\n", person->name,person->age);}int myCompare(void *d1,void *d2){struct Person *p1 = (struct Person *)d1;struct Person *p2 = (struct Person *)d2;return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;}void test(){//创建动态数组struct DynamicArray *da = Init_DynamicArray(5);//动态数组添加元素struct Person p1 = { "aaa", 10 };struct Person p2 = { "bbb", 20 };struct Person p3 = { "ccc", 30 };struct Person p4 = { "ddd", 40 };struct Person p5 = { "eee", 50 };struct Person p6 = { "fff", 60 };Insert_DynamicArray(da, 0, &p1);Insert_DynamicArray(da, 0, &p2);Insert_DynamicArray(da, 0, &p3);Insert_DynamicArray(da, 1, &p4);Insert_DynamicArray(da, 1, &p5);printf("capacity:%d\n",da->capacity);Insert_DynamicArray(da, 100, &p6);  //3 5 4 2 1 6printf("capacity:%d\n", da->capacity);Foreach_DynamicArray(da, myPrint);printf("---------------\n");RemoveByPos_DynamicArray(da,2);//3 5 2 1 6Foreach_DynamicArray(da, myPrint);printf("---------------\n");struct Person pDel = { "aaa", 10 };RemoveByValue_DynamicArray(da, &pDel, myCompare);//da->addr = NULL;Foreach_DynamicArray(da, myPrint);//销毁Destroy_DynamicArray(da);}int main(){test();system("pause");return EXIT_SUCCESS;}

    反思:

    这样的一个写法有个问题:我们直接把我们的结构体暴露了在外面,任何人都可以修改访问。这样是不安全的。

    我们初始化函数时,返回的是我们的结构体指针。直接把结构体返回了。

    解决方案是我们的函数体返回时,返回void*,无类型指针。这样其他函数插入参数时,也是void*类型。然后在函数里面做个强制类型转换即可。避免别人在外面直接调用结构指针。

    此时考虑面向对象的封装特性。

上一篇:如何下载闹钟应用

下一篇:土地抵押备案证明怎么写的