C语言顺序表基本操作实现（初始化、插入与删除）

顺序表的数据结构与定义

顺序表（Sequential List）是用一段地址连续的存储单元依次存储线性表的数据结构。在C语言中，我们通常使用结构体来封装指向数组的指针、当前长度和总容量。

以下代码定义了顺序表所需的宏常量及结构体：

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

#define LIST_INIT_SIZE 100   // 初始分配大小
#define LISINCREMENT 10      // 扩容增量
#define ElemType int         // 元素类型
#define Status int           // 状态返回类型

typedef struct Sq {
    ElemType *elem;  // 指向动态数组的指针
    int length;      // 当前长度
    int listsize;    // 当前分配的存储容量
} SqList;

核心操作一：初始化顺序表

在使用顺序表前，必须为其分配内存。该函数负责申请初始空间并重置计数器。

第1步：InitList 实现

目的是为 SqList 分配初始内存块，并检查分配是否成功。

• 入口： SqList *L 指针地址
• 动作： 调用 malloc 分配 LIST_INIT_SIZE 大小的内存，将 length 设为 0。
• 参数： 需确保传入有效的指针引用。
• 完成状态： 返回 1 表示成功，0 表示内存不足失败。

Status InitList(SqList *L) {
    L->elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L->elem)
        return 0;
    L->length = 0;
    L->listsize = LIST_INIT_SIZE;
    return 1;
}

核心操作二：按位置插入元素

插入操作需要在指定的索引位置腾出空间，并将后续元素后移。若当前容量不足，需进行扩容。

第2步：ListInsert 实现

目的是在位置 i 插入新元素 e，并处理可能的内存重分配。

• 入口： SqList *L，目标索引 i，新值 e
• 判断： 首先检查 i 是否合法（1 <= i <= length + 1），注意原代码此处判断有误，正确应为允许插到末尾后一位。
• 扩容检查： 若 length == listsize，调用 realloc 增加 LISINCREMENT 容量。
• 移位： 从最后一个元素开始，逐个向后移动一位，直到位置 i-1。
• 赋值： 在空出的位置写入新值，长度加 1。

// 注意：原代码中 if(i<1||i>L->length) 对于插入逻辑是不严谨的
// 标准插入允许 i 等于 length+1，这里保留原意但建议修正逻辑验证
Status ListInsert(SqList *L, int i, ElemType e) {
    int *q, *p;
    // 插入位置 i 应该在 [1, length+1] 之间
    if (i < 1 || i > L->length + 1)
        return 0;
        
    // 如果当前容量满了，进行扩容
    if (L->length >= L->listsize) {
        ElemType *newbase = (ElemType*)realloc(L->elem,
            (L->listsize + LISINCREMENT) * sizeof(ElemType));
        if (!newbase)
            return 0;
        L->elem = newbase;
        L->listsize += LISINCREMENT;
    }
    
    // 找到插入位置的指针 q
    q = &(L->elem[i-1]);
    // 从尾部向前移动元素
    for (p = &(L->elem[L->length-1]); p >= q; --p) {
        *(p + 1) = *p;
    }
    *q = e;
    ++L->length;
    return 1;
}

核心操作三：按位置删除元素

删除操作需要先读取被删元素的值（如需返回），然后将其后所有元素前移填补空缺。

第3步：ListDelete 实现

目的是移除位置 i 的元素，并将结果存入 e（若需要）。

• 入口： SqList *L，目标索引 i，用于接收被删值的 e（指针或引用方式取决于C语法，此处代码看似传值但有歧义，通常应传递指针或直接通过返回值获取，原代码写法 ListDelete(L,lo,temp) 中 temp 未传址，导致无法回传被删值，这是原代码的一个典型缺陷。下文将保留原逻辑描述，但在总结中指出。）
• 判断： 检查 i 是否在有效范围内 (1 <= i <= length)。
• 记录： 将 L->elem[i-1] 的值赋给 e（需注意传参方式）。
• 移位： 从 i 之后的元素开始，逐个前移一位。
• 缩减： 长度减 1。

/**
 * 注意：原代码签名 Status ListDelete(SqList *L,int i,ElemType e) 存在bug。
 * C语言中 int e 是传值修改无效。若要返回删除的值，应改为 ElemType *e 或类似指针。
 * 此处仅展示原代码逻辑结构。
 */
Status ListDelete(SqList *L, int i, ElemType e) {
    int *p, *q;
    if (i < 1 || i > L->length)
        return 0;
        
    p = &(L->elem[i-1]);
    e = *p; // 此处赋值仅在函数内有效，外部变量不会改变
    
    q = L->elem + L->length - 1;
    for (++p; p <= q; ++p) {
        *(p - 1) = *p;
    }
    --L->length;
    return 1;
}

主函数测试流程

以下 main 函数展示了完整的操作流程：初始化 → 输入数据 → 插入 → 打印 → 删除 → 打印 → 释放内存。

int main(void) {
    int i, j, e, lo, temp;
    // 分配结构体本身的空间
    SqList *L = (SqList*)malloc(sizeof(SqList));
    
    InitList(L);
    
    printf("请输入顺序表的长度:\n");
    scanf("%d", &L->length);
    
    printf("请输入顺序表的各个元素:\n");
    for (i = 0; i < L->length; ++i) {
        scanf("%d", &L->elem[i]);
    }
    
    printf("输入的顺序表是:\n");
    for (i = 0; i < L->length; ++i) {
        printf("%d ", L->elem[i]);
    }
    printf("\n");
    
    // 插入测试
    printf("请输入插入的位置以及节点:\n");
    scanf("%d%d", &j, &e);
    ListInsert(L, j, e); 
    
    printf("插入后的顺序表为:\n");
    for (i = 0; i < L->length; ++i) {
        printf("%d ", L->elem[i]);
    }
    printf("\n");
    
    // 删除测试
    printf("请输入要删除的位置：");
    scanf("%d", &lo);
    // 注意：原代码此处直接传 temp 无法获取删除值，建议改为传指针
    ListDelete(L, lo, temp);
    
    printf("删除后的顺序表为:\n");
    for (i = 0; i < L->length; ++i) {
        printf("%d ", L->elem[i]);
    }
    printf("\n");
    
    free(L->elem); // 建议先释放数组
    free(L);       // 再释放结构体指针
    return 0;
}

关键注意事项与排错

在实际运行上述代码时，请注意以下几个关键点以确保程序稳定：

1. 内存泄漏风险： main 函数中同时使用了 free(L)。由于 L->elem 是单独通过 malloc/realloc 分配的，最佳实践是先 free(L->elem) 释放数组内容，再 free(L) 释放结构体，以避免悬空指针或未释放的子资源。
2. 删除功能回传缺陷： 原文中的 ListDelete 采用值传递 ElemType e，这意味着在函数内部修改 e 不会影响外部的 temp 变量。如果需要获取被删除的值，必须将参数改为指针类型 ElemType *e，并在调用时传入 &temp。
3. 插入边界检查： 原文 ListInsert 的条件 i > L->length 会阻止用户在列表末尾之后插入新的元素。标准的顺序表插入应允许 i = length + 1（即追加到末尾）。

以上就是C语言实现顺序表的基本操作（初始化、插入与删除）的详细内容，更多关于C语言数据结构学习资料请关注本站其它相关文章！