1. AI技术聚合首页
  2. IT

【数据结构】顺序表的动态分配(步骤代码详解）

xiaoxingxing • • IT • 阅读 24

🎈个人主页：豌豆射手^
🎉欢迎 👍点赞✍评论⭐收藏
🤗收录专栏：数据结构
🤝希望本文对您有所裨益，如有不足之处，欢迎在评论区提出指正，让我们共同学习、交流进步！

【数据结构】顺序表的动态分配的实现步骤

  • 引言
  • 一 初始化顺序表结构体：
    • 1.1 代码：
    • 1.2 代码分析：
  • 二 分配内存空间：
    • 2.1 代码：
    • 2.2 代码分析：
  • 三 设置属性：
    • 3.1 代码：
  • 四 检查内存分配
  • 五 空间不足时重新分配：
    • 5.1 代码：
    • 5.2 代码分析
  • 六 元素操作：
    • 6.1 代码
    • 6.2 代码分析
  • 七 销毁顺序表：
  • 总结

引言

在计算机科学中，数据结构是组织和存储数据的方式，它决定了数据如何被存储、检索和操作。

顺序表作为一种线性数据结构，其内部元素在物理存储上按照顺序连续存放。然而，静态的顺序表在创建时就需要确定其大小，这在实际应用中往往不够灵活。

因此，实现顺序表的动态分配变得尤为重要。动态分配允许我们在运行时根据需要调整顺序表的大小，从而更加高效地管理和使用内存。

本文将详细阐述顺序表动态分配的实现步骤，包括初始化结构体、分配内存空间、设置属性、检查内存分配、空间不足时重新分配、元素操作以及销毁顺序表等关键步骤。

顺序表中的动态分配涉及一系列步骤以确保在程序执行时能够根据需要分配内存空间，从而管理线性表的数据元素。以下是顺序表动态分配的具体步骤：

一 初始化顺序表结构体：

首先，需要创建一个顺序表的结构体，其中通常包含指向动态分配数组的指针、顺序表的最大容量以及当前的长度等属性。

1.1 代码：

typedef struct {  
    int *data;        // 指向数据数组的指针  
    int length;       // 顺序表当前长度  
    int capacity;     // 顺序表最大容量  
} SeqList;

1.2 代码分析：

这段代码定义了一个名为SeqList的结构体，用于表示一个顺序表（线性表的顺序存储结构）。以下是每个步骤的详细介绍：

  1. 定义结构体类型：

    typedef struct {

    使用typedef关键字结合struct关键字定义了一个新的结构体类型SeqList。这样，后续代码中可以直接使用SeqList来声明该类型的变量，而不必每次都写出struct关键字。

  2. 数据数组指针：

    int *data;        // 指向数据数组的指针

    在结构体中定义了一个指向int类型的指针data。这个指针用于指向顺序表存储数据的数组。当顺序表被初始化时，data将指向一个动态分配的内存块，用于存储顺序表中的元素。

  3. 顺序表当前长度：

    int length;       // 顺序表当前长度

    length变量用于记录顺序表中当前存储的元素个数。它反映了顺序表的实际大小，与顺序表的容量（capacity）不同，容量是顺序表能够容纳的最大元素数量。

  4. 顺序表最大容量：

    int capacity;     // 顺序表最大容量

    capacity变量表示顺序表的最大容量，即它能够存储的元素的最大数量。这个值在顺序表初始化时确定，并且可以通过动态内存分配进行扩展。

  5. 结束结构体定义：

    } SeqList;

    这个分号标志着结构体定义的结束。此时，SeqList已经成为了一个有效的类型，可以在后续代码中用于声明变量。

通过使用SeqList这个结构体，可以方便地管理顺序表的存储和状态。通过修改data指针、length和capacity的值，可以实现顺序表的动态内存分配、元素的插入和删除等操作。同时，由于data是一个指针，顺序表可以灵活地调整其大小，以适应不同数量的元素存储需求。

二 分配内存空间：

使用malloc或类似的函数在内存中为顺序表的结构体和数据数组分配一块连续的空间。

这个空间的大小可以根据需要动态确定，通常初始时分配一个默认的大小。

2.1 代码：

SeqList* list = (SeqList*)malloc(sizeof(SeqList));  
if (list == NULL) {  
    perror("Failed to allocate memory for SeqList");  
    exit(EXIT_FAILURE);  
}  
list->data = (int*)malloc(INIT_CAPACITY * sizeof(int));  
if (list->data == NULL) {  
    perror("Failed to allocate memory for data array");  
    free(list);  
    exit(EXIT_FAILURE);  
}

2.2 代码分析：

这段代码实现了顺序表结构体的动态内存分配，以及顺序表内部数据数组的初始分配。以下是每个步骤的详细介绍：

  1. 分配顺序表结构体的内存：
SeqList* list = (SeqList*)malloc(sizeof(SeqList));

使用malloc函数为SeqList类型的结构体分配内存空间。

sizeof(SeqList)计算了SeqList结构体所占用的字节数。malloc函数根据这个大小在堆上分配内存，并返回指向这块内存的指针。该指针被强制类型转换为SeqList*类型，并赋值给list变量。

在C语言中，malloc 函数用于在堆上动态分配指定字节数的内存，并返回指向这块内存的指针。

这个返回的指针类型是 void*，即指向任意类型的指针。在C语言中，void* 类型的指针可以赋给任何其他类型的指针，但是为了避免类型不匹配导致的潜在问题，并且为了使代码更加清晰，通常我们会将 void* 类型的指针显式转换为目标类型的指针。

  1. 检查内存分配是否成功：
if (list == NULL) {  
    perror("Failed to allocate memory for SeqList");  
    exit(EXIT_FAILURE);  
}

检查malloc函数是否成功分配了内存。

如果malloc返回NULL，表示内存分配失败。这时，perror函数用于打印出系统错误信息，说明内存分配失败的原因。然后，程序调用exit(EXIT_FAILURE)终止执行，并返回非零的退出状态码，表示程序异常结束。

  1. 分配数据数组的内存：
list->data = (int*)malloc(INIT_CAPACITY * sizeof(int));

为顺序表的数据数组分配内存空间。INIT_CAPACITY是一个预先定义的常量，表示顺序表初始时的容量大小。`

malloc函数根据INIT_CAPACITY * sizeof(int)`计算出需要分配的总字节数，并在堆上分配相应的内存空间。

返回的指针被强制类型转换为int*类型，并赋值给list->data，即顺序表结构体的data成员。

list->data 这条语句在C语言中表示通过结构体指针 list 来访问其指向的结构体中的 data 成员。这里，list 是一个指向 SeqList 类型结构体的指针，而 data 是 SeqList 结构体中的一个成员，其类型为 int*（指向整数的指针）。

具体来说：

  • list 是一个指针，它存储了某个 SeqList 结构体在内存中的地址。
  • -> 是一个结构体指针的成员访问运算符。它用于通过结构体指针来访问其指向的结构体中的成员。
  • data 是 SeqList 结构体中的一个成员，它是一个指向整数数组的指针。

因此，list->data 的意思就是取 list 指针指向的 SeqList 结构体中的 data 成员的值，即这个结构体所关联的数据数组的指针。通过这个指针，你可以访问或修改顺序表中的数据。

例如，如果你想访问顺序表中的第一个元素，你可以这样做：

int firstElement = *(list->data);

这里，list->data 获取数据数组的指针，* 运算符用于解引用这个指针，从而得到数组中的第一个元素。

如果你想设置顺序表中的第一个元素为某个值，比如10，你可以这样做：

*(list->data) = 10;

这样，你就通过 list->data 成功地修改了顺序表中的数据。

  1. 再次检查内存分配是否成功：
if (list->data == NULL) {  
    perror("Failed to allocate memory for data array");  
    free(list);  // 释放之前为顺序表结构体分配的内存
    exit(EXIT_FAILURE);  
}

再次检查malloc函数是否成功分配了内存。

如果malloc返回NULL，说明数据数组的内存分配失败。

此时，程序首先调用free(list)释放之前为顺序表结构体分配的内存，避免内存泄漏。

然后，使用perror打印出错误信息，并通过exit(EXIT_FAILURE)终止程序执行。

通过上述步骤，代码成功地为顺序表结构体和数据数组分配了内存，并进行了必要的错误检查。如果所有内存分配都成功，那么list指针现在指向一个有效的顺序表结构体，其data成员指向一个能够存储INIT_CAPACITY个整数的数组。之后，就可以使用这个顺序表进行元素的插入、删除、查找等操作了。

三 设置属性：

将分配的内存地址赋值给顺序表结构体的相应指针，并设置顺序表的最大容量和当前长度为初始值。

3.1 代码：

list->length = 0;  
list->capacity = INIT_CAPACITY;

四 检查内存分配

在每次内存分配后，都需要检查是否分配成功。如果malloc返回NULL，则表示内存分配失败，此时需要进行错误处理，如打印错误信息并退出程序。上面的代码已经包含了这一步。

五 空间不足时重新分配：

随着顺序表中元素的增加，当空间不足时，需要动态地重新分配更大的内存空间。

我们需要执行以下步骤：

1 分配新的内存块，大小为所需的新容量。

2 将旧内存块中的数据复制到新内存块中。

3 释放旧内存块。

4 更新指针和容量。

5.1 代码：

if (list->length >= list->capacity) {    
    int new_capacity = list->capacity * 2; // 扩大为原来的两倍    
    int *new_data = (int*)malloc(new_capacity * sizeof(int));    
    if (new_data == NULL) {    
        perror("Failed to allocate memory for new data array");    
        free(list->data);    
        free(list);    
        exit(EXIT_FAILURE);    
    }  
      
    // 将旧数据复制到新分配的内存中  
    for (int i = 0; i < list->length; i++) {  
        new_data[i] = list->data[i];  
    }  
      
    // 释放旧内存  
    free(list->data);  
      
    // 更新指针和容量  
    list->data = new_data;  
    list->capacity = new_capacity;  
}

5.2 代码分析

这段代码的主要目的是在动态数组（或称为顺序表）list的当前容量不足以存储更多元素时，对其容量进行扩展。以下是代码各步骤的详细解释：

  1. 检查容量是否足够：

    if (list->length >= list->capacity) {

    这行代码检查list的当前长度（list->length）是否已经达到或超过了其当前容量（list->capacity）。如果是，则需要进行内存扩展。

  2. 计算新容量：

    int new_capacity = list->capacity * 2; // 扩大为原来的两倍

    这里将新容量设置为当前容量的两倍。这是一种常见的扩展策略，因为它简单且通常足够应对增长需求。然而，具体的扩展策略可能会根据应用需求的不同而有所变化。

  3. 分配新内存：

    int *new_data = (int*)malloc(new_capacity * sizeof(int));

    使用malloc函数为新的数据数组分配内存。new_capacity * sizeof(int)计算了新数组所需的字节数。如果malloc成功，它将返回一个指向新分配内存的指针，否则返回NULL。

  4. 检查内存分配是否成功：

    if (new_data == NULL) {
    perror("Failed to allocate memory for new data array");
    free(list->data);
    free(list);
    exit(EXIT_FAILURE);
}

    如果malloc返回NULL，说明内存分配失败。此时，代码打印一个错误消息，释放任何已经分配给list和list->data的内存，然后退出程序。

  5. 复制旧数据到新内存：

    for (int i = 0; i < list->length; i++) {
    new_data[i] = list->data[i];
}

    通过一个循环，将旧数据数组list->data中的元素逐个复制到新分配的内存new_data中。

  6. 释放旧内存：

    free(list->data);

    释放指向旧数据数组的指针所引用的内存。这是非常重要的步骤，因为如果不释放旧内存，就会导致内存泄漏。

  7. 更新指针和容量：

    list->data = new_data;
list->capacity = new_capacity;

    将list结构中的data指针更新为指向新分配的内存，并将capacity更新为新容量。这样，list现在就指向一个容量更大的数据数组，并且可以继续添加更多元素。

通过以上步骤，代码成功地在不改变原list结构指针的情况下，扩大了其内部数据数组的容量，并确保所有现有数据都被保留下来。这种技术在动态数据结构的实现中非常常见，特别是在处理可能快速增长的数据集时。

六 元素操作：

在动态分配的空间上执行顺序表的插入、删除、查找等操作。这些操作需要根据顺序表的当前状态（如长度和容量）来正确执行，并确保数据的完整性和一致性。

6.1 代码

元素操作的代码会根据具体的操作而有所不同，例如插入、删除和查找等。这里提供一个插入操作的示例：

int InsertList(SeqList *list, int index, int elem) {  
    if (index < 0 || index > list->length) {  
        return -1; // 插入位置无效  
    }  
    // 动态分配（如果必要）已在前面的步骤中完成  
    // 移动元素，为新元素腾出空间  
    for (int i = list->length; i > index; i--) {  
        list->data[i] = list->data[i - 1];  
    }  
    list->data[index] = elem; // 插入新元素  
    list->length++; // 更新顺序表长度  
    return 0;  
}

6.2 代码分析

这段代码定义了一个函数InsertList，用于在顺序表（或称为动态数组）list的指定位置index插入一个元素elem。顺序表通过结构体SeqList来定义，其中至少包含指向数据数组的指针data、数组当前长度length和数组容量capacity。下面是对代码中每个步骤的详细解释：

  1. 检查插入位置的有效性：

    if (index < 0 || index > list->length) {  
    return -1; // 插入位置无效  
}

    这里首先检查传入的index是否在有效的插入范围内。如果index小于0或者大于list的当前长度list->length，则意味着插入位置无效，函数返回-1表示错误。

  2. 注释：动态分配（如果必要）已在前面的步骤中完成：

    // 动态分配（如果必要）已在前面的步骤中完成

    这是一个注释，说明在调用InsertList函数之前，已经确保了list有足够的容量来存储新元素。这通常意味着在某个地方（可能是在插入操作之前，或者当添加元素导致list容量不足时）已经进行了内存分配或重新分配。由于这段代码没有直接包含这部分逻辑，所以这是一个前提假设。

  3. 移动元素，为新元素腾出空间：

    for (int i = list->length; i > index; i--) {  
    list->data[i] = list->data[i - 1];  
}

    这个循环的目的是将index位置及其之后的所有元素向后移动一个位置，从而为新元素腾出空间。循环从list->length开始（即数组的最后一个元素的下一个位置），逐步向前移动到index + 1。在每次迭代中，都将当前位置的元素值赋给其后面的位置，这样就实现了元素的向后移动。

  4. 插入新元素：

    list->data[index] = elem;

    在已经腾出的index位置上，将新元素elem的值赋给list->data[index]，从而完成了新元素的插入。

  5. 更新顺序表长度：

    list->length++;

    由于已经成功插入了一个新元素，因此需要更新list的长度。将list->length加1以反映新元素的添加。

  6. 返回成功标志：

    return 0;

    如果所有步骤都成功执行，函数返回0，表示插入操作成功。

整个InsertList函数遵循了顺序表插入操作的标准步骤：检查插入位置的有效性、为新元素腾出空间、插入新元素、更新长度，并返回操作结果。这样的设计保证了顺序表在插入操作后的正确性和一致性。

七 销毁顺序表：

当不再需要顺序表时，需要释放其占用的内存空间。这通常涉及使用free函数来释放之前通过malloc或realloc分配的内存块。

void DestroyList(SeqList *list) {  
    free(list->data); // 释放数据数组的内存  
    free(list); // 释放顺序表结构体的内存  
}

通过上述步骤，顺序表能够实现动态的内存分配和管理，从而根据程序的需求高效地存储和访问线性表的数据元素。需要注意的是，动态内存分配涉及到内存管理的复杂性，因此在编写代码时需要仔细处理各种边界条件和错误情况，以确保程序的正确性和稳定性。

总结

通过本文的详细阐述，我们了解了顺序表动态分配的实现步骤。从初始化顺序表结构体开始，到分配内存空间、设置属性、检查内存分配，再到空间不足时的重新分配、元素操作，以及最终的销毁顺序表，每一步都至关重要。

动态分配的实现使得顺序表在实际应用中更加灵活和高效，能够根据实际需求动态调整大小，避免了静态顺序表在大小确定上的局限性。

同时，我们也需要注意在内存分配和释放过程中的安全性和正确性，以避免内存泄漏和野指针等问题。

通过掌握这些实现步骤和注意事项，我们可以更好地利用顺序表这一数据结构，为实际应用提供有力的支持。

这篇文章到这里就结束了

谢谢大家的阅读！

如果觉得这篇博客对你有用的话，别忘记三连哦。

我是豌豆射手^，让我们我们下次再见

版权声明：本文为博主作者：豌豆射手^原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/m0_74195174/article/details/137248568

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
xiaoxingxing的头像xiaoxingxing管理团队
0
上一篇 2024年4月22日
下一篇 2024年4月22日

相关推荐