数据结构之动态数组的代码实现（新手小白也能懂/C语言版）

来源：叨叨游戏网

前言：动态数组的代码实现与解析

计算机专业，数据结构是你绕不过的一道坎，在编程中，数组是一种常见的数据结构，用于存储固定大小的同类型元素集合。然而，有时候我们需要一个能够根据需要动态调整大小的数组，这就是动态数组（也称为动态数组或可扩展数组）。在C语言中，由于没有内置的动态数组类型，我们通常需要通过自己编写代码来实现它。（注：数据结构本身与编程语言没有任何关系，所以在学习数据结构的时候不要纠结用哪种语言去学习，把其中的思想搞懂之后，你用任何一种语言都可以来实现你需要的数据结构，所谓是高手不会在乎使用什么语言，但我是菜狗。）

一、代码具体实现

1.定义结构体

首先，我们定义了一个dynamic_array结构体，用于表示动态数组。

// 定义一个动态数组结构体存储其数组以及大小；
typedef struct
{
	int* array;
	size_t size;
	size_t capacity;
 } dynamic_array;

该结构体包含三个成员：

int* array;
- 含义：这是一个指向int类型的指针，用于指向动态分配的内存区域，这个区域存储了数组的元素。
- 作用：通过这个指针，可以访问和操作数组中的元素。由于是动态分配的，所以数组的大小可以在运行时改变，提供了比静态数组更大的灵活性。
size_t size;
- 含义：这是一个size_t类型的变量，用于存储数组中当前存储的元素数量。
- 作用：size成员让程序能够知道数组中当前有多少个有效元素。这对于遍历数组、添加或删除元素等操作至关重要。size_t是一个无符号整数类型，通常用于表示对象的大小。
size_t capacity;
- 含义：这也是一个size_t类型的变量，用于存储数组当前的容量，即数组可以存储的最大元素数量，而不必重新分配内存。
- 作用：capacity成员表示了数组当前分配的内存空间可以容纳的元素数量。当数组中的元素数量达到capacity时，如果还需要添加更多元素，就需要重新分配更大的内存空间，并相应地更新capacity的值。有助于管理内存使用，避免内存溢出，同时减少不必要的内存分配操作。

总的来说，dynamic_array结构体通过这三个成员提供了一个灵活且高效的动态数组实现，允许在运行时根据需要动态地增加或减少数组的大小，同时提供了对当前元素数量和最大容量的跟踪，以便于管理和操作数组。

2.创建动态数组

create_array函数用于创建一个新的动态数组，并初始化其容量。

 //  函数：用于创建一个动态数组并进行初始化；
 dynamic_array* create_array(size_t initial_capacity)
 {
 	dynamic_array* arr = (dynamic_array*)malloc(sizeof(dynamic_array));
 	if(arr == NULL)
 	{
 		printf("Error：Failed to allocate memory for dynamic array structure.\n");
 		return NULL;
	 }
	arr->array = (int*)malloc(initial_capacity * sizeof(int));
	if(arr->array == NULL)
	{
		printf("Error:Failed to allocate memory for the internal integer array.\n");
		free(arr);
		return NULL;
	}
	arr->size = 0;
	arr->capacity = initial_capacity; 
	return arr;
	
  }

首先为dynamic_array结构体分配内存，然后为内部的整数数组分配内存。如果内存分配失败，它会打印错误信息并返回NULL。

基础知识解读

->在C语言中，以下是对本文提供的create_array函数中涉及的基础知识进行的详细解读：

1. 指针运算符

->（结构体指针成员访问运算符）：用于通过结构体指针访问其成员。例如，arr->array表示访问arr指针所指向的dynamic_array结构体中的array成员。

2. 结构体成员访问

在C语言中，结构体是一种用户定义的数据类型，它允许将多个不同类型的数据项组合成一个单一的类型。通过结构体，可以方便地存储和操作相关数据。
访问结构体成员通常使用.运算符（当结构体变量直接可用时）或->运算符（当通过结构体指针访问时）。例如，如果有一个dynamic_array类型的变量my_array，则可以通过my_array.array访问其array成员；而如果有一个指向dynamic_array的指针arr，则通过arr->array访问。

3. malloc和free函数的介绍

malloc函数用于动态分配内存。它接受一个size_t类型的参数，表示要分配的字节数，并返回一个指向分配的内存区域的指针。如果分配失败，则返回NULL。

在本文代码中，malloc(sizeof(dynamic_array))用于为dynamic_array结构体分配内存，而malloc(initial_capacity * sizeof(int))用于为结构体中的array成员（一个整数数组）分配内存。
free函数用于释放之前通过malloc、calloc或realloc函数分配的内存。它接受一个指针作为参数，该指针指向要释放的内存区域。

在本文代码中，如果为array成员分配内存失败，则会先使用free(arr)释放为dynamic_array结构体分配的内存，然后返回NULL。这是为了避免内存泄漏。

4. 函数create_array的详细解读

函数定义：dynamic_array* create_array(size_t initial_capacity)。该函数接受一个size_t类型的参数initial_capacity，表示动态数组的初始容量，并返回一个指向dynamic_array结构体的指针。
函数体：

3.读取动态数组元素

read_array函数用于从动态数组中读取指定索引处的元素。如果索引超出数组范围，它会打印错误信息并返回-1。

// 函数；用于读取数组中的某一个元素；
int read_array(dynamic_array* arr, size_t index)
{
	if(index < arr->size)
  		return arr->array[index];
  	else
  	{
  		printf("Error:index out of bounds:%d.\n", index);
  		return -1;
	}
}

都是基础语法，懒得解释了，看不懂直接回炉重造吧。

4.更新动态数组元素

update_array函数用于更新动态数组中指定索引处的元素。如果索引超出数组范围，它会打印错误信息并返回。

// 函数：用于更新数组中的某一个元素的值；
void update_array(dynamic_array* arr, size_t index, int value)
{
	if(index < arr->size)
	{
		arr->array[index] = value;
	}
	else
	{
		printf("Error:index out of bounds>:%d.\n", index);
	}
 }

该函数接受三个参数：

dynamic_array* arr：指向动态数组结构体的指针。这个结构体应该包含一个指向实际数组数据的指针（例如 int* array）以及一个表示数组大小的成员（例如 size_t size）。
size_t index：要更新的元素在数组中的索引位置。
int value：新值，将用于替换原数组中对应索引位置的值。

函数执行过程如下：

检查索引有效性：首先检查传入的索引值（index）是否小于动态数组的大小（arr->size）。这是为了确保索引在数组的有效范围内，从而避免越界访问。
- 如果索引有效（即 index < arr->size），则继续下一步操作。
- 如果索引超出数组边界（即 index >= arr->size），函数会输出错误信息 "Error: index out of bounds: %d\n"，其中 %d 会被替换为实际的非法索引值。
更新数组元素：如果索引有效，函数将整数 value 赋给数组中对应索引位置的元素，通过表达式 arr->array[index] = value 完成更新操作。
错误处理：如果索引超出数组边界，函数仅输出错误信息，并不会改变数组的状态。这样做提供了对动态数组元素进行安全更新的能力，并在尝试访问不存在的元素时给出错误提示。

5.追加元素到动态数组

append_array函数用于向动态数组追加一个新元素。如果数组已满，会先进行数组扩容，并重新分配内存。然后，它将新元素添加到数组的末尾，并更新数组大小。

 // 函数：给数组追加一个新的元素；
 int append_array(dynamic_array* arr, int value) 
 {
 	if(arr->size >= arr->capacity)
 	{
 		size_t new_capacity = arr->capacity * 2;
		int* new_array = (int*)realloc(arr->array, new_capacity * sizeof(int));
		if (new_array == NULL)
		{
			printf("Error:Failed to reallocate memory for the internal integer array.\n");
			return -1;
		}
		arr->array = new_array;
		arr->capacity = new_capacity;
	 }
	 arr->array[arr->size] = value;
	 arr->size++;
	 return 0;
 }

该函数接受两个参数：

dynamic_array* arr：指向动态数组结构体的指针。
int value：要追加到数组末尾的新元素的值。

函数执行过程如下：

检查容量：首先检查动态数组的当前大小（arr->size）是否已经达到其容量（arr->capacity）。如果数组已满（即 arr->size >= arr->capacity），则需要进行内存重新分配以扩展数组容量。
- 计算新的容量：通常，新的容量是原容量的两倍（new_capacity = arr->capacity * 2），这样可以减少因频繁重新分配内存而导致的性能开销。
- 使用 realloc 函数重新分配内存：调用 realloc 函数，尝试将 arr->array 指向的内存块扩展到 new_capacity * sizeof(int) 大小。realloc 返回指向新内存块的指针，如果内存分配失败，则返回 NULL。
- 错误处理：如果 realloc 返回 NULL，表示内存重新分配失败。此时，函数会输出错误信息 "Error: Failed to reallocate memory for the internal integer array.\n" 并返回 -1，以指示发生了错误。
- 更新数组指针和容量：如果内存重新分配成功，将 arr->array 更新为指向新内存块的指针，并将 arr->capacity 更新为新的容量值。
追加元素：在确认数组有足够的容量后，将新元素 value 追加到数组的末尾。这通过 arr->array[arr->size] = value 实现，然后将数组的大小（arr->size）递增 1。
成功返回：如果整个过程成功完成，函数返回 0，以指示元素已成功追加到数组中。

6.在动态数组中插入元素

insert_array_element函数用于在动态数组的指定索引处插入一个新元素。它首先检查索引是否有效，然后确保有足够的空间。如果需要，它会重新分配内存。接着，它将插入点之后的元素向右移动一位，以腾出空间，并将新元素插入到指定位置。

// 函数：用于在任意索引位置插入一个元素；
 int insert_array(dynamic_array* arr, size_t index, int value)
 {
 	if(index > arr->size)
 	{
 		printf("Error:index out of bounds for insertion:%d.\n", index);
 		return -1;
	 }
	
	// 若是末尾插入，直接调用上面写的追加函数；
	if(index == arr->size)
		return append_array(arr, value);
	
	// 确保有足够的空间；
	if(arr->size >= arr->capacity)
	{
		size_t new_capacity = arr->capacity * 2;
		int* new_array = (int*)realloc(arr->array, new_capacity * sizeof(int));
		if(new_array == NULL)
		{
			printf("Error:Failed to reallocate memory for the internal integer array.\n");
			return -1;
		}
		arr->array = new_array;
		arr->capacity = new_capacity;
	 } 
	 
	// 元素右移腾出空间；
	for(size_t i = arr->size; i > index; i--)
	{
		arr->array[i] = arr->array[i - 1];
	 } 
	
	// 插入新的元素；
	arr->array[index] = value;
	arr->size++;
	
	return 0; 
 }

该函数接受三个参数：

dynamic_array* arr：指向动态数组结构体的指针。
size_t index：要插入新元素的位置索引。
int value：要插入的新元素的值。

函数执行过程如下：

检查索引有效性：首先检查传入的索引值（index）是否大于动态数组的当前大小（arr->size）。如果是，则表示索引超出数组的有效范围，函数会输出错误信息 "Error: index out of bounds for insertion: %d.\n"，并返回 -1。
末尾插入优化：如果索引恰好等于数组的当前大小（index == arr->size），则直接调用之前定义的 append_array 函数来追加新元素，并返回其返回值。这是一种优化，因为末尾插入实际上与追加元素是等价的。
检查容量并重新分配内存：如果数组的当前大小已经达到其容量，函数会计算新的容量（通常是原容量的两倍），并使用 realloc 函数尝试重新分配内存。如果内存重新分配失败，函数会输出错误信息并返回 -1。
元素右移：为了确保新元素能够插入到指定位置，函数会遍历数组，从数组的末尾开始，将每个元素向右移动一个位置，直到到达插入位置的前一个位置。
插入新元素：在指定索引位置插入新元素，并通过递增数组的大小（arr->size）来更新数组的状态。
成功返回：如果整个过程成功完成，函数返回 0，以指示元素已成功插入到数组中。

7.在动态数组中移除元素

remove_array_element函数用于从动态数组中移除指定索引处的元素。它首先将移除点之后的元素向左移动一位，以覆盖被移除的元素，并更新数组大小。

 // 函数：用于移除数组中的某一个元素；
 int remove_array_element(dynamic_array* arr, size_t index)
 {
 	if(index > arr->size)
 	{
 		printf("Error:index out of bounds:%d.\n", index);
 		return -1;
	 }
	for(size_t i = index; i < arr->size; i++)
	{
		arr->array[i] = arr->array[i + 1];
	}
	arr->size--;
	return 0;
  }

函数执行流程：

索引有效性检查：首先，函数会验证传入的索引值是否有效。如果索引超出了数组的当前大小（index > arr->size），则函数会输出错误信息 "Error: index out of bounds: %d.\n"，并返回 -1 以表示失败。
元素左移：为了确保移除元素后数组的连续性，函数会从要移除的元素开始，遍历数组的剩余部分，将每个元素向左移动一个位置。这个操作是通过循环实现的，循环体内将 arr->array[i] 设置为 arr->array[i + 1] 的值。

需要注意的是，在循环的最后一次迭代中，由于 i + 1 已经超出了数组的当前大小，实际上会有一个“空洞”或未定义的值留在数组的末尾。但由于我们已经将数组的大小（arr->size）递减，这个“空洞”将不会被视为数组的有效部分。
更新数组大小：完成元素左移后，函数会递减数组的大小（arr->size），以反映元素已被移除的事实。
成功返回：如果整个移除过程成功完成，函数将返回 0 以表示成功。

8.打印动态数组

print_array函数用于打印动态数组中的所有元素。它遍历数组，并打印每个元素。

  // 函数：打印动态数组；
void print_array(dynamic_array* arr)
{
	for(size_t i = 0; i < arr->size; i++)
	{
		printf("%d ", arr->array[i]);
	}
	printf("\n");
}

9.删除动态数组

delete_array函数用于删除动态数组。它首先释放内部整数数组的内存，然后释放dynamic_array结构体的内存。

// 函数：删除动态数组；
void delete_array(dynamic_array* arr)
{
	free(arr->array);
	arr->array = NULL;
	free(arr);
	arr = NULL;
 }

二、代码实力演示

 // main:主函数；
 int main(void)
 {
 	dynamic_array* arr = create_array(6);
 	
 	// 追加元素测试：
 	puts("追加元素测试...");
	append_array(arr, 10); 
	append_array(arr, 20); 
	append_array(arr, 30); 
	append_array(arr, 40); 
	
	// 打印数组测试；
	puts("打印数组测试...");
	print_array(arr);
	
	// 插入元素测试；
	insert_array(arr, 3, 999);
	puts("插入元素测试...");
	printf("%d\n", arr->array[3]);
	
	// 移除元素测试；
	puts("移除元素测试...");
	remove_array_element(arr, 2);
	print_array(arr);
	
	//删除数组测试；
	puts("删除数组测试...");
	delete_array(arr);
	
	 
 	return 0;
  }

功能概述：
main 函数是程序的起始执行点。在此函数中，创建了一个动态数组，并对其执行了一系列的操作，包括追加、插入、移除元素，并最终删除了该数组。这些操作旨在展示动态数组的基本功能和灵活性。

执行流程：

创建动态数组：
使用 create_array 函数创建了一个初始容量为6的动态数组，并将返回的数组指针存储在 arr 变量中。
追加元素测试：
通过调用 append_array 函数四次，依次向数组中追加了10、20、30和40这四个元素。随后，使用 puts 函数输出提示信息，表明正在执行追加元素测试。
打印数组测试：
调用 print_array 函数，打印当前数组中的所有元素，以验证追加操作是否成功。
插入元素测试：
使用 insert_array 函数在数组的索引3位置插入了值999。之后，通过 puts 函数输出提示信息，并使用 printf 函数打印插入位置的值，以验证插入操作是否按预期进行。
移除元素测试：
通过调用 remove_array_element 函数，移除了数组中索引为2的元素。随后，再次调用 print_array 函数，打印移除元素后的数组，以验证移除操作是否成功。
删除数组测试：
最后，使用 delete_array 函数删除了动态数组，并释放了其所占用的内存资源。通过 puts 函数输出提示信息，表明正在执行删除数组测试。

三、总结

完整代码如下，在实际应用中，由于编译环境和个人的需求不同，我们可以根据适当对其进行扩展和优化。

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

// 定义一个动态数组结构体存储其数组以及大小；
typedef struct
{
	int* array;
	size_t size;
	size_t capacity;
 } dynamic_array;
 
 //  函数：用于创建一个动态数组并进行初始化；
 dynamic_array* create_array(size_t initial_capacity)
 {
 	dynamic_array* arr = (dynamic_array*)malloc(sizeof(dynamic_array));
 	if(arr == NULL)
 	{
 		printf("Error：Failed to allocate memory for dynamic array structure.\n");
 		return NULL;
	 }
	arr->array = (int*)malloc(initial_capacity * sizeof(int));
	if(arr->array == NULL)
	{
		printf("Error:Failed to allocate memory for the internal integer array.\n");
		free(arr);
		return NULL;
	}
	arr->size = 0;
	arr->capacity = initial_capacity; 
	return arr;
	
  } 
  
// 函数；用于读取数组中的某一个元素；
int read_array(dynamic_array* arr, size_t index)
{
	if(index < arr->size)
  		return arr->array[index];
  	else
  	{
  		printf("Error:index out of bounds:%d.\n", index);
  		return -1;
	}
} 
   
// 函数：用于更新数组中的某一个元素的值；
void update_array(dynamic_array* arr, size_t index, int value)
{
	if(index < arr->size)
	{
		arr->array[index] = value;
	}
	else
	{
		printf("Error:index out of bounds>:%d.\n", index);
	}
 } 
 
 // 函数：给数组追加一个新的元素；
 int append_array(dynamic_array* arr, int value) 
 {
 	if(arr->size >= arr->capacity)
 	{
 		size_t new_capacity = arr->capacity * 2;
		int* new_array = (int*)realloc(arr->array, new_capacity * sizeof(int));
		if (new_array == NULL)
		{
			printf("Error:Failed to reallocate memory for the internal integer array.\n");
			return -1;
		}
		arr->array = new_array;
		arr->capacity = new_capacity;
	 }
	 arr->array[arr->size] = value;
	 arr->size++;
	 return 0;
 }
 
 // 函数：用于在任意索引位置插入一个元素；
 int insert_array(dynamic_array* arr, size_t index, int value)
 {
 	if(index > arr->size)
 	{
 		printf("Error:index out of bounds for insertion:%d.\n", index);
 		return -1;
	 }
	
	// 若是末尾插入，直接调用上面写的追加函数；
	if(index == arr->size)
		return append_array(arr, value);
	
	// 确保有足够的空间；
	if(arr->size >= arr->capacity)
	{
		size_t new_capacity = arr->capacity * 2;
		int* new_array = (int*)realloc(arr->array, new_capacity * sizeof(int));
		if(new_array == NULL)
		{
			printf("Error:Failed to reallocate memory for the internal integer array.\n");
			return -1;
		}
		arr->array = new_array;
		arr->capacity = new_capacity;
	 } 
	 
	// 元素右移腾出空间；
	for(size_t i = arr->size; i > index; i--)
	{
		arr->array[i] = arr->array[i - 1];
	 } 
	
	// 插入新的元素；
	arr->array[index] = value;
	arr->size++;
	
	return 0; 
 } 
 
 // 函数：用于移除数组中的某一个元素；
 int remove_array_element(dynamic_array* arr, size_t index)
 {
 	if(index > arr->size)
 	{
 		printf("Error:index out of bounds:%d.\n", index);
 		return -1;
	 }
	for(size_t i = index; i < arr->size; i++)
	{
		arr->array[i] = arr->array[i + 1];
	}
	arr->size--;
	return 0;
  } 
  
  // 函数：打印动态数组；
void print_array(dynamic_array* arr)
{
	for(size_t i = 0; i < arr->size; i++)
	{
		printf("%d ", arr->array[i]);
	}
	printf("\n");
}

// 函数：删除动态数组；
void delete_array(dynamic_array* arr)
{
	free(arr->array);
	arr->array = NULL;
	free(arr);
	arr = NULL;
 } 
 
 // main:主函数；
 int main(void)
 {
 	dynamic_array* arr = create_array(6);
 	
 	// 追加元素测试：
 	puts("追加元素测试...");
	append_array(arr, 10); 
	append_array(arr, 20); 
	append_array(arr, 30); 
	append_array(arr, 40); 
	
	// 打印数组测试；
	puts("打印数组测试...");
	print_array(arr);
	
	// 插入元素测试；
	insert_array(arr, 3, 999);
	puts("插入元素测试...");
	printf("%d\n", arr->array[3]);
	
	// 移除元素测试；
	puts("移除元素测试...");
	remove_array_element(arr, 2);
	print_array(arr);
	
	//删除数组测试；
	puts("删除数组测试...");
	delete_array(arr);
	
	 
 	return 0;
  }

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部频道

数据结构之动态数组的代码实现（新手小白也能懂/C语言版）

前言：动态数组的代码实现与解析

一、代码具体实现

1.定义结构体

2.创建动态数组

3.读取动态数组元素

4.更新动态数组元素

5.追加元素到动态数组

6.在动态数组中插入元素

7.在动态数组中移除元素

8.打印动态数组

9.删除动态数组

二、代码实力演示

三、总结