C / C++ / 系统课时
用结构体封装一个顺序表
用结构体封装一个顺序表
直接使用动态数组时,数据指针、已用长度和容量很容易散落在多个变量中。把这三项状态封装进结构体,可以形成一个统一管理的顺序表,并为后续插入、删除、扩容和销毁操作建立稳定接口。
学习目标
- 使用结构体保存顺序表的数据指针、长度和容量
- 理解
length与capacity各自承担的职责 - 完成顺序表的初始化、追加访问和资源释放
顺序表需要保存哪些状态
一个动态顺序表至少需要三个成员:data 指向堆上的连续数组,length 表示当前已有多少个有效元素,capacity 表示当前已经申请了多少个元素位置。
任何正常状态都应满足 length <= capacity。插入元素时修改的是 length;只有空间不足并重新申请更大内存时,capacity 才会改变。

定义并初始化顺序表
下面实现一个固定容量版本。初始化时申请连续内存,追加时先检查剩余容量,销毁时释放内存并把状态恢复为空表。
#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;
}预期输出
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 对象维护这些约束,而不是在调用方分别修改指针、长度和容量。这样顺序表才真正成为一个可以统一管理的数据结构。