C / C++ / 系统课时

用结构体封装一个顺序表

用结构体封装一个顺序表

直接使用动态数组时,数据指针、已用长度和容量很容易散落在多个变量中。把这三项状态封装进结构体,可以形成一个统一管理的顺序表,并为后续插入、删除、扩容和销毁操作建立稳定接口。

学习目标

  • 使用结构体保存顺序表的数据指针、长度和容量
  • 理解 length 与 capacity 各自承担的职责
  • 完成顺序表的初始化、追加访问和资源释放

顺序表需要保存哪些状态

一个动态顺序表至少需要三个成员:data 指向堆上的连续数组,length 表示当前已有多少个有效元素,capacity 表示当前已经申请了多少个元素位置。

任何正常状态都应满足 length <= capacity。插入元素时修改的是 length;只有空间不足并重新申请更大内存时,capacity 才会改变。

顺序表结构体与动态数组的关系

定义并初始化顺序表

下面实现一个固定容量版本。初始化时申请连续内存,追加时先检查剩余容量,销毁时释放内存并把状态恢复为空表。

c
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;
    size_t length;
    size_t capacity;
} SeqList;

bool seq_list_init(SeqList *list, size_t capacity) {
    if (list == NULL || capacity == 0) {
        return false;
    }

    list->data = malloc(capacity * sizeof *list->data);
    if (list->data == NULL) {
        list->length = 0;
        list->capacity = 0;
        return false;
    }

    list->length = 0;
    list->capacity = capacity;
    return true;
}

bool seq_list_push_back(SeqList *list, int value) {
    /* 固定容量版本没有自动扩容,写入前必须检查边界。 */
    if (list == NULL || list->data == NULL || list->length >= list->capacity) {
        return false;
    }

    list->data[list->length] = value;
    list->length++;
    return true;
}

void seq_list_destroy(SeqList *list) {
    if (list == NULL) {
        return;
    }

    free(list->data);
    /* 清空三个字段,避免继续把已释放内存当成有效顺序表使用。 */
    list->data = NULL;
    list->length = 0;
    list->capacity = 0;
}

int main(void) {
    SeqList list;

    if (!seq_list_init(&list, 5)) {
        return 1;
    }

    seq_list_push_back(&list, 10);
    seq_list_push_back(&list, 20);
    seq_list_push_back(&list, 30);

    printf("length=%zu capacity=%zu\n", list.length, list.capacity);
    printf("values=%d %d %d\n", list.data[0], list.data[1], list.data[2]);

    seq_list_destroy(&list);
    return 0;
}

预期输出

text
length=3 capacity=5
values=10 20 30

这里申请了 5 个 int 的空间,但只写入 3 个元素,所以 length 是 3,capacity 仍然是 5。剩余两个位置只是已分配空间,并不属于当前有效数据。

为什么不能只保存一个长度

如果只有 length,程序只知道当前元素数量,却不知道已分配内存还能容纳多少元素;每次插入都无法判断是否需要扩容。如果只有 capacity,又无法判断哪些位置已经保存有效数据。

把两者分开后,追加操作可以先比较 length 与 capacity。当 length < capacity 时直接写入;当两者相等时,固定容量版本返回失败,支持动态扩容的版本则可以调用 realloc 申请更大的连续空间。

封装后要维护状态一致性

结构体只是把状态集中起来,并不会自动保证正确性。所有修改函数都应维护几个基本约束:有效元素位于 data[0] 到 data[length - 1],始终满足 length <= capacity,释放内存后不再通过旧指针访问数据。

后续实现插入、删除和自动扩容时,都应通过操作这个 SeqList 对象维护这些约束,而不是在调用方分别修改指针、长度和容量。这样顺序表才真正成为一个可以统一管理的数据结构。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用结构体封装一个顺序表

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通