C语言动态顺序表：从结构定义到全功能实现

顺序表概念及结构

顺序表采用物理地址连续的存储单元依次存放数据元素，通常以数组为底。其分类主要依据存储空间是否可变：

• 静态顺序表：编译时确定大小，用完即满且无法扩缩，存在空间不足或资源浪费的矛盾。
• 动态顺序表：底层使用指向动态开辟数组的指针。当空间满时进行增容（通常为原大小的2倍），解决了容量限制并优化了空间利用率。

动态顺序表的核心结构需维护三个关键状态：动态数组首地址、当前有效数据量以及当前总容量。

基本操作与接口定义

为实现完整的顺序表管理，需定义类型别名及结构体，并封装初始化和销毁函数以确保数据安全。

1. 结构体定义：使用 typedef struct 定义 SeqList，内部包含 SLDateType* a（指针域）、size_t size（有效大小）和 size_t capacity（总容量）。
2. 辅助函数：定义 Check_Capacity 专责检查并执行扩容逻辑，其他功能函数在此基础之上调用。
3. 核心接口：Init 初始化、Destroy 释放内存、Print 打印数据，以及针对头部、尾部及任意位置的插入与删除操作。

第1步：结构体与安全声明配置

在头文件中进行宏保护与依赖引入，建立类型别名以便于后续修改数据类型。

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int SLDateType;

typedef struct SeqList
{
	SLDateType* a;     // 维护动态开辟的数组
	size_t size;       // 有效数据的数量
	size_t capacity;   // 当前分配的总空间大小
}SeqList;

第2步：容量检查与自动扩容逻辑

所有涉及插入数据的操作前，必须调用此检查函数。若已满或初次插入，触发扩容并更新指针与容量值。

static void Check_Capacity(SeqList* ps)
{
    if (ps->capacity == ps->size) 
    {
        // 初次创建或满了都需要扩容，最少分配4个单位
        size_t NewCapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
        
        int* tmp = (int*)realloc(ps->a, NewCapacity * sizeof(int));
        if (tmp == NULL)
            exit(-1);
            
        ps->a = tmp;
        ps->capacity = NewCapacity;
    }
}

第3步：初始化与销毁的安全处理

初始化将所有指针置为空，计数归零；销毁时务必先释放动态内存再重置成员变量，防止野指针和内存泄漏。

void SeqListInit(SeqList* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->capacity = 0;
    ps->size = 0;
}

void SeqListDestroy(SeqList* ps)
{
    assert(ps);
    free(ps->a); // 必须先释放堆上内存
    ps->capacity = 0;
    ps->size = 0;
}

第4步：数据的插入与维护（头/尾插）

插入前均需先检查容量。尾插简单直接；头插需要将原有数据向后移动一位以腾出位置。

// 尾插法
void SeqListPushBack(SeqList* ps, SLDateType x)
{
    assert(ps);
    Check_Capacity(ps);
    ps->a[ps->size] = x;
    ps->size++;
}

// 头插法
void SeqListPushFront(SeqList* ps, SLDateType x)
{
    assert(ps);
    Check_Capacity(ps);
    // 将末尾之前的所有元素向后挪动
    int end = ps->size - 1;
    for (; end >= 0; end--)
        ps->a[end + 1] = ps->a[end];
    ps->a[0] = x; // 或者 ps->a[end + 1] = x;
    ps->size++;
}

第5步：数据删除与位置操作

删除时需验证链表非空。头删是将后续元素向前覆盖；指定位置插入/删除同样伴随大量的元素搬移操作，需注意边界条件验证。

// 尾删
void SeqListPopBack(SeqList* ps)
{
    assert(ps);
    assert(ps->size > 0);
    ps->size--;
}

// 指定位置插入
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
    assert(ps);
    assert(pos <= ps->size); // 防止越界访问
    Check_Capacity(ps);
    
    int end = ps->size - 1;
    int target = (int)pos;
    for (; end >= target; end--)
        ps->a[end + 1] = ps->a[end];
    ps->a[target] = x;
    ps->size++;
}

// 指定位置删除
void SeqListErase(SeqList* ps, size_t pos)
{
    assert(ps);
    assert(ps->size > 0);
    assert(pos < ps->size); 
    
    int begin = (int)pos + 1;
    int len = ps->size;
    for (; begin < len; begin++)
        ps->a[begin - 1] = ps->a[begin];
    ps->size--;
}

程序运行效果

在完成上述接口定义与功能实现后，在主函数中依次调用初始化、插入多个节点、查找、中间插入及删除等操作，最后打印验证输出结果是否正确反映了各次操作后的内存状态。

以上就是C语言动态顺序表的详细内容，更多关于C语言顺序表实现资料请关注本站其它相关文章！