顺序表的动态分配代码分析

顺序表的动态分配代码分析

引用

CSDN

1.

https://blog.csdn.net/m0_74195174/article/details/137735310

引言

本文将对顺序表的动态分配代码进行详细分析。顺序表是一种线性数据结构，其特点是数据元素在内存中是连续存储的。为了实现顺序表的动态扩展，我们需要使用动态内存分配技术。下面将通过一个具体的代码示例，深入解析顺序表的初始化、内存分配、扩容等关键步骤。

一、代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<stdlib.h>
#define InitSize  10
typedef struct {
    int *data;
    int MaxSize;
    int length;
}SeqList;
void InitList(SeqList& L) 
{
    L.data = (int*)malloc( InitSize * sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}
void IncreaseSize(SeqList& L, int len)
{
    int* p = L.data;
    L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));
    for (int i = 0; i < L.length; i++) 
    {
        L.data[i] = p[i];
    }
    L.MaxSize = L.MaxSize + len;
    free(p);
}
int main()
{
    SeqList L;
    InitList(L);
    IncreaseSize(L, 5);
}

二、代码分析

下面是拆分后的代码，以及对每一步骤的分析：

步骤1：

#define _CRT_SECURE_NO_WARNINGS

分析：
定义了一个宏 _CRT_SECURE_NO_WARNINGS，用于消除某些编译器关于安全性的警告，例如在使用 malloc 等函数时可能出现的警告。

步骤2：

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

分析：
包含了标准输入输出库 stdio.h 和标准库 stdlib.h，前者用于输入输出操作，后者提供了内存分配函数如 malloc 和 free。

步骤3：

#define InitSize  10

分析：
定义了一个宏 InitSize，值为10，用于初始化顺序表（SeqList）的初始大小。

步骤4：

typedef struct {
    int *data;
    int MaxSize;
    int length;
} SeqList;

分析：
定义了一个结构体类型 SeqList，包含一个整型指针 data 用于存储数据，整型 MaxSize 用于存储顺序表的最大容量，整型 length 用于存储顺序表当前的长度。

指针 data

在结构体类型 SeqList 中，整型指针 data 用于存储顺序表中实际数据的内存地址。具体来说，data 是一个指向整型数据的指针，它指向一个动态分配的内存区域，该区域用于存储顺序表中的元素。

在顺序表中，我们通常不知道事先需要存储多少个元素，或者元素的数量可能会在运行过程中变化。因此，使用动态内存分配（如 malloc）来分配存储空间是一个灵活且有效的方法。

data 指针就是用来管理这块动态分配的内存的。当创建或初始化一个 SeqList 对象时，我们通常会为 data 指针分配一块足够大的内存空间来存储初始的元素。随着顺序表中元素的增加或减少，我们可能需要重新分配 data 指针所指向的内存空间，以适应新的存储需求。这时，我们会使用 realloc 或再次调用 malloc 来重新分配内存，并更新 data 指针的指向。

通过 data 指针，我们可以方便地访问和修改顺序表中的元素。例如，通过计算元素的索引和 data 指针的偏移量，我们可以直接定位到某个元素的内存位置，并进行读取或写入操作。

总之，data 指针在 SeqList 结构体中起到了桥梁的作用，它连接了顺序表的逻辑结构和实际存储数据的内存空间。

整型 MaxSize

在 SeqList 结构体中，整型 MaxSize 用于表示顺序表当前分配的最大容量。这个值通常用于在动态内存管理中跟踪已经为顺序表分配了多少内存空间。

具体来说，MaxSize 的作用体现在以下几个方面：

1. 内存分配参考：当需要增加顺序表的容量时（例如，通过调用 IncreaseSize 函数），MaxSize 会被用来计算需要分配多少额外的内存空间。这样，程序可以确保在扩展顺序表时分配足够的内存。

2. 防止越界访问：在添加新元素到顺序表之前，通常会检查顺序表的当前长度是否已经达到 MaxSize。如果达到或超过 MaxSize，那么程序会知道需要增加顺序表的容量，以避免越界访问内存，这是一种常见的内存安全错误。

3. 优化内存使用：通过跟踪 MaxSize，程序可以更有效地管理内存。例如，如果顺序表的大小经常变化，但变化不大，那么可以通过适当地调整 MaxSize 来减少频繁的内存分配和释放操作，从而提高性能。

4. 容量监控：MaxSize 也可以用于监控顺序表的内存使用情况。通过比较 MaxSize 和顺序表的当前长度，程序可以了解顺序表是否接近满载，从而决定是否需要进行容量调整。

优化内存具体来说是在实际应用中，如果顺序表（例如一个动态数组）的大小经常会在一个较小的范围内变动，那么频繁地进行内存分配和释放操作可能会成为性能瓶颈。

为了优化性能，我们可以采取一种策略，即不是每次顺序表大小稍有变化就立即重新分配内存，而是预留一些额外的空间，即适当增加 MaxSize 的值。

具体来说，当顺序表需要增加元素时，我们并不立即按照新的大小重新分配内存，而是检查当前预留的空间是否足够。如果足够，我们就不会进行内存分配操作，而是直接在预留的空间中添加新元素。

只有当预留的空间不足时，我们才会进行一次较大的内存分配操作，以满足未来一段时间内可能的增长需求。

这种策略可以减少内存分配和释放的次数，因为内存分配和释放通常涉及系统调用和可能的内存碎片问题，这些操作相对耗时。

通过适当调整 MaxSize 的值，我们可以在一定程度上平滑这些操作对性能的影响，从而提高程序的执行效率。

需要注意的是，预留过多的空间也会浪费内存资源，因此需要在性能和内存使用之间找到一个平衡。这通常需要根据具体的应用场景和需求来决定。

总的来说，MaxSize 在 SeqList 结构体中是一个重要的元数据成员，它帮助程序更好地管理顺序表的内存使用，确保内存安全，并优化性能。

整型 length

在顺序表（如 SeqList）的数据结构中，整型 length 通常用于表示顺序表当前实际存储的元素个数，也就是顺序表的当前长度。这个值对于顺序表的操作和管理至关重要，具体体现在以下几个方面：

1. 元素访问：通过 length，我们可以快速知道顺序表中当前有多少个元素，从而安全地访问这些元素。例如，当我们要读取或修改顺序表中的某个元素时，需要确保该元素的索引在有效范围内（即小于 length）。

2. 添加和删除元素：当向顺序表中添加元素时，我们需要更新 length 以反映新添加的元素。同样地，当从顺序表中删除元素时，也需要减少 length 的值。通过 length，我们可以方便地追踪顺序表的当前状态。

3. 容量与长度比较：length 和 MaxSize 的比较是顺序表管理中常见的操作。通过比较这两个值，我们可以判断顺序表是否已满（即 length 是否等于 MaxSize），从而决定是否需要进行扩容操作。

4. 空间效率监控：length 也用于监控顺序表的空间使用情况。例如，如果 length 远小于 MaxSize，这可能意味着顺序表分配了过多的内存，存在空间浪费的情况。根据应用的需求，可以考虑是否需要进行内存收缩操作。

总之，整型 length 在顺序表的数据结构中扮演了记录当前元素数量、辅助元素访问和修改、管理内存空间等重要角色。它是顺序表实现中不可或缺的一部分。

步骤5：

void InitList(SeqList& L) {
    L.data = (int*)malloc(InitSize * sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}

分析：
定义了初始化顺序表的函数 InitList，它接受一个 SeqList 类型的引用 L 作为参数。函数内部使用 malloc 为 L.data 分配了 InitSize 个整数的空间，最后将 L.length 和 L.MaxSize 分别初始化为0和 InitSize。

L.data = (int*)malloc(InitSize * sizeof(int));

这行代码是C语言中用于动态内存分配的一行关键代码，它用于为一个顺序表（在这里是 SeqList 类型的对象 L）分配初始的内存空间。具体地，这一行代码做了以下几件事：

1. malloc(InitSize * sizeof(int))：

• malloc 是一个标准库函数，用于在堆上动态分配指定字节大小的内存。
• InitSize 是一个变量（或常量），表示要分配的整型元素（int）的数量。
• sizeof(int) 是一个运算符，返回 int 类型在特定系统或编译器上所占用的字节数。
• InitSize * sizeof(int) 计算了总共需要分配的字节数。

2. (int*)：

• 这是一个类型转换（或称为强制类型转换）。
• malloc 函数返回的是一个指向 void 的指针（void*），因为 malloc 可以分配任何类型的内存。
• 但是在C语言中，我们不能直接将 void* 类型的指针赋给其他类型的指针。因此，这里使用 (int*) 将 void* 类型的指针转换为 int* 类型的指针。这样，我们就可以将这个指针赋值给指向整型的指针变量。

3. L.data = ...：

• L 是一个 SeqList 类型的对象。
• L.data 是 SeqList 结构体中的一个成员，它是一个指向整型的指针，用于存储顺序表数据的实际内存地址。
• 这一行代码将 malloc 返回的指针（即新分配的内存地址）赋值给 L.data，这样 L.data 就指向了新分配的内存区域。

综上所述，这一行代码的目的是为顺序表 L 分配一个可以存储 InitSize 个整数的内存区域，并将这块内存的地址赋值给 L.data。此后，顺序表 L 就可以通过 L.data 指针来访问和操作这些内存中的元素了。

需要注意的是，在使用 malloc 分配内存后，应始终检查返回值是否为 NULL，以确保内存分配成功。此外，当不再需要这块内存时，应使用 free 函数来释放它，以防止内存泄漏。

步骤6：

void IncreaseSize(SeqList& L, int len) {
    int* p = L.data;
    L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));

分析：
定义了增加顺序表大小的函数 IncreaseSize，它接受一个 SeqList 类型的引用 L 和一个整数 len 作为参数。首先，它保存了 L.data 的当前地址到指针 p 中，以便稍后释放这块内存。然后，它使用 malloc 为 L.data 重新分配了一块更大的内存空间，新的大小是原来的 L.MaxSize 加上增加的 len 个整数的大小。

步骤7：

    for (int i = 0; i < L.length; i++) {
        L.data[i] = p[i];
    }

分析：
使用循环遍历原顺序表 L 的每一个元素，并将这些元素复制到新分配的内存空间中。

步骤8：

    L.MaxSize = L.MaxSize + len;
    free(p);
}

分析：
更新顺序表 L 的最大容量 L.MaxSize，然后释放原来 L.data 指向的内存空间。

步骤9：

int main() {
    SeqList L;
    InitList(L);
    IncreaseSize(L, 5);
}

分析：
定义了程序的主函数 main。首先，创建了一个 SeqList 类型的变量 L，然后调用 InitList 函数初始化 L，最后调用 IncreaseSize 函数将 L 的大小增加5个单位。