动态数组与链表：内存分配与检索链表解析

本资源主要介绍了动态数组与链表的概念，包括内存的三种分配方式：静态存储、栈分配和堆分配。重点讲述了动态内存分配，包括动态数组的使用场景、动态内存分配函数如malloc、calloc、free和realloc的用法，并提供了一个简单的C语言示例。 在计算机编程中，动态数组和链表是两种重要的数据结构，它们在处理不确定数量的数据时特别有用。动态数组允许根据需要调整其大小，而链表则是一种非连续存储的数据结构，通过指针连接各个元素。 1. **动态数组**： - **内存分配**：动态数组是在运行时根据需要分配内存，可以解决静态数组固定大小带来的问题。例如，当需要存储不确定数量的数据时，静态分配可能导致内存浪费，而动态分配可以根据实际需求分配内存。 - **动态分配函数**：`malloc`函数用于动态分配指定大小的内存，返回一个指向分配内存的指针。`calloc`函数用于分配多个相同大小的元素，返回一个指向连续内存块的指针。`free`函数用于释放由`malloc`或`calloc`分配的内存。`realloc`函数用于改变已分配内存的大小，可以在不丢失原有数据的情况下扩展或缩小内存块。 2. **链表**： - **检索链表**：在给定的代码段中，`retrieve`函数用于在链表中查找具有特定值(x 和 y)的节点。它通过遍历链表直到找到匹配项或到达链表末尾来实现。如果找到匹配项，打印"FOUND"，否则打印"NO FOUND"。这展示了链表的基本操作，即遍历和搜索。 - **链表的优点**：相比于数组，链表不需要连续的内存空间，因此在插入和删除元素时更灵活，不需要移动其他元素。 3. **内存分配方式**： - **静态存储区域**：全局变量和静态变量在此分配，它们在整个程序运行期间都存在。 - **栈分配**：函数内部的局部变量在函数调用时分配，结束后自动释放，速度快但容量有限。 - **堆分配**：使用`malloc`、`calloc`、`realloc`和`free`进行分配和释放，内存管理更灵活但需要程序员手动管理内存，可能导致内存泄漏。 示例代码中，`malloc`和`calloc`的用法展示了如何根据用户输入的班级人数动态分配浮点数数组。在C语言中，使用`#include<stdio.h>`和`#include<malloc.h>`头文件来使用这些函数。程序首先读取班级人数和每个学生的分数，然后动态分配内存存储这些分数，最后计算平均分。 动态数组和链表都是数据结构的重要组成部分，它们在处理动态数据和内存管理中发挥着关键作用。理解它们的工作原理和使用方法对于任何程序员来说都是至关重要的。