投稿
  1. 何大锤的博客首页
  2. 编程导航
  3. 数据结构

07 – 第二章数据结构线性表 – 顺序表总结

何大锤 • • 数据结构 • 阅读 2

顺序表代码实现

一、动态分配方式实现的所有功能

dynamic_list.c

#include "dynamic_list.h"

// 初始化顺序表（考研重点操作）
bool InitList(DynamicList *L) {
    // 分配初始容量内存
    L->data = (int *)malloc(INIT_SIZE * sizeof(int));
    if (L->data == NULL) return false;  // 内存分配失败
    
    L->length = 0;         // 初始长度为0
    L->capacity = INIT_SIZE;  // 初始容量
    return true;
}

// 插入操作（核心算法，考研常考边界条件）
bool ListInsert(DynamicList *L, int i, int e) {
    // 1. 检查位序合法性（i范围：1~length+1）
    if (i < 1 || i > L->length + 1) return false;
    
    // 2. 检查是否需要扩容
    if (L->length >= L->capacity) {
        // 重新分配更大的内存（考研要求掌握realloc使用）
        int *new_data = (int *)realloc(L->data, (L->capacity + INCREMENT) * sizeof(int));
        if (new_data == NULL) return false;  // 扩容失败
        
        L->data = new_data;       // 更新基址指针
        L->capacity += INCREMENT; // 更新容量
    }
    
    // 3. 移动元素（从后往前移，避免覆盖）
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j-1];
    }
    
    // 4. 插入元素，更新长度
    L->data[i-1] = e;  // 位序i对应数组下标i-1
    L->length++;
    return true;
}

// 删除操作（考研重点，需返回被删除值）
bool ListDelete(DynamicList *L, int i, int *e) {
    // 1. 检查位序合法性（i范围：1~length）
    if (i < 1 || i > L->length) return false;
    
    // 2. 保存被删除元素
    *e = L->data[i-1];
    
    // 3. 移动元素（从前往后移）
    for (int j = i; j < L->length; j++) {
        L->data[j-1] = L->data[j];
    }
    
    // 4. 更新长度
    L->length--;
    return true;
}

// 按位查找（随机访问，时间复杂度O(1)，顺序表优势）
int GetElem(DynamicList L, int i) {
    if (i < 1 || i > L->length) return -1;  // 位序非法（假设元素为正整数）
    return L->data[i-1];  // 位序i对应下标i-1
}

// 按值查找（顺序查找，时间复杂度O(n)）
int LocateElem(DynamicList L, int e) {
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] == e) {
            return i + 1;  // 数组下标转位序（+1）
        }
    }
    return 0;  // 未找到
}

// 遍历输出所有元素
void PrintList(DynamicList L) {
    for (int i = 0; i < L->length; i++) {
        printf("%d ", L->data[i]);
    }
    printf("\n");
}

// 销毁顺序表（释放动态内存）
void DestroyList(DynamicList *L) {
    free(L->data);    // 释放存储区
    L->data = NULL;   // 防止野指针
    L->length = 0;
    L->capacity = 0;
}

dynamic_list.h

#ifndef DYNAMIC_LIST_H
#define DYNAMIC_LIST_H

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>  // 使用bool类型需要包含此头文件

#define INIT_SIZE 10    // 初始容量
#define INCREMENT 5     // 扩容增量（考研常用倍增或固定增量，此处用固定增量示例）

// 动态顺序表结构体定义（考研标准写法）
typedef struct {
    int *data;          // 动态分配的存储基址
    int length;         // 当前长度（已用元素个数）
    int capacity;       // 总容量（最大可存储元素个数）
} DynamicList;

// 初始化顺序表
bool InitList(DynamicList *L);

// 插入元素（位序i，从1开始）
bool ListInsert(DynamicList *L, int i, int e);

// 删除元素（位序i，返回被删除元素）
bool ListDelete(DynamicList *L, int i, int *e);

// 按位查找（返回第i个元素）
int GetElem(DynamicList *L, int i);

// 按值查找（返回第一个等于e的位序，不存在返回0）
int LocateElem(DynamicList *L, int e);

// 遍历输出所有元素
void PrintList(DynamicList L);

// 销毁顺序表
void DestroyList(DynamicList *L);

#endif

relloc函数

realloc 是 C 语言标准库中用于重新调整已分配内存块大小的函数，主要用于动态内存管理（头文件 <stdlib.h>）。

void* realloc(void* ptr, size_t new_size);

ptr：指向待调整大小的原内存块的指针（若为 NULL，效果等价于 malloc(new_size)）。

new_size：调整后的新内存块大小（单位：字节）。若 new_size 为 0，效果等价于 free(ptr)（此时返回值通常为 NULL）。

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

int main() {
    // 初始分配 4 字节（存 int）
    int* arr = malloc(4 * sizeof(int)); 
    if (!arr) { /* 处理分配失败 */ }

    // 重新分配为 8 字节（扩展存 8 个 int）
    int* new_arr = realloc(arr, 8 * sizeof(int));
    if (!new_arr) {
        free(arr); // realloc 失败时，原 arr 仍有效，需手动释放
        return -1;
    }
    // 此时 arr 可能已被释放，使用 new_arr
    arr = new_arr;

    // 使用扩展后的内存...

    free(arr); // 最终释放调整后的内存
    return 0;
}

main.c

#include "dynamic_list.h"

int main() {
    DynamicList L;
    
    // 初始化测试
    if (InitList(&L)) {
        printf("顺序表初始化成功！初始容量：%d\n", L.capacity);
    } else {
        printf("顺序表初始化失败！\n");
        return 1;
    }

    // 插入测试（插入10个元素触发扩容）
    printf("\n=== 插入测试 ===\n");
    for (int i = 1; i <= INIT_SIZE + 2; i++) {  // 插入12个元素（超过初始容量10）
        if (ListInsert(&L, i, i*10)) {
            printf("插入位序%d，值%d成功！当前长度：%d\n", i, i*10, L.length);
        } else {
            printf("插入位序%d失败！\n", i);
        }
    }
    printf("插入后顺序表内容：");
    PrintList(L);
    printf("当前容量：%d\n", L.capacity);  // 应输出15（初始10+增量5）

    // 按位查找测试
    printf("\n=== 按位查找测试 ===\n");
    int pos = 5;
    int elem = GetElem(L, pos);
    printf("第%d个元素的值是：%d\n", pos, elem);

    // 按值查找测试
    printf("\n=== 按值查找测试 ===\n");
    int target = 70;
    int found_pos = LocateElem(L, target);
    if (found_pos) {
        printf("值%d出现在位序%d\n", target, found_pos);
    } else {
        printf("值%d未找到\n", target);
    }

    // 删除测试
    printf("\n=== 删除测试 ===\n");
    int del_pos = 3;
    int del_elem;
    if (ListDelete(&L, del_pos, &del_elem)) {
        printf("删除位序%d成功！被删除值：%d\n", del_pos, del_elem);
        printf("删除后顺序表内容：");
        PrintList(L);
        printf("当前长度：%d\n", L.length);
    } else {
        printf("删除位序%d失败！\n", del_pos);
    }

    // 销毁测试
    DestroyList(&L);
    printf("\n顺序表已销毁！\n");
    return 0;
}

代码说明（关键点）：

  1. 结构体定义：使用data指针、length（当前长度）、capacity（总容量）三要素，与教材完全一致。
  2. 初始化操作：显式分配初始内存，处理内存分配失败的情况（考研要求考虑鲁棒性）。
  3. 插入操作：
    • 检查位序合法性（1 ≤ i ≤ length+1）
    • 动态扩容使用realloc（考研重点函数），扩容策略为固定增量（符合教材示例）
    • 元素后移方向正确（从后往前避免覆盖）
  4. 删除操作：
    • 检查位序合法性（1 ≤ i ≤ length）
    • 保存被删除元素值（符合考研 “返回被删元素” 的要求）
    • 元素前移方向正确（从前往后避免覆盖）
  5. 查找操作：
    • 按位查找时间复杂度 O (1)（体现顺序表随机访问优势）
    • 按值查找时间复杂度 O (n)（顺序查找的标准实现）
  6. 内存管理：包含DestroyList函数释放动态内存，防止内存泄漏（考研隐含要求）。

测试代码验证场景：

  • 初始容量测试（插入超过初始容量时触发扩容）
  • 边界插入（头部 / 尾部插入）
  • 非法位序处理（自动过滤无效位置）
  • 动态扩容验证（容量从 10 变为 15）
  • 删除后元素前移验证
  • 内存释放验证（避免野指针）

二、静态分配方式实现的所有功能

static_list.c

#include "static_list.h"

// 初始化顺序表（静态分配无需动态内存，直接置长度为0）
bool InitList(StaticList *L) {
    L->length = 0;  // 初始长度为0（数组空间已静态分配）
    return true;    // 静态分配不会失败（区别于动态分配）
}

// 插入操作（核心算法，需处理容量已满的情况）
bool ListInsert(StaticList *L, int i, int e) {
    // 1. 检查位序合法性（i范围：1~length+1）
    if (i < 1 || i > L->length + 1) return false;
    
    // 2. 检查是否已满（静态分配核心限制）
    if (L->length >= MAX_SIZE) {
        printf("错误：顺序表已满，无法插入！\n");
        return false;
    }
    
    // 3. 移动元素（从后往前移，避免覆盖）
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j-1];
    }
    
    // 4. 插入元素，更新长度
    L->data[i-1] = e;  // 位序i对应数组下标i-1
    L->length++;
    return true;
}

// 删除操作（考研重点，需返回被删除值）
bool ListDelete(StaticList *L, int i, int *e) {
    // 1. 检查位序合法性（i范围：1~length）
    if (i < 1 || i > L->length) return false;
    
    // 2. 保存被删除元素
    *e = L->data[i-1];
    
    // 3. 移动元素（从前往后移）
    for (int j = i; j < L->length; j++) {
        L->data[j-1] = L->data[j];
    }
    
    // 4. 更新长度
    L->length--;
    return true;
}

// 按位查找（随机访问，时间复杂度O(1)，顺序表优势）
int GetElem(StaticList L, int i) {
    if (i < 1 || i > L->length) return -1;  // 位序非法（假设元素为正整数）
    return L->data[i-1];  // 位序i对应下标i-1
}

// 按值查找（顺序查找，时间复杂度O(n)）
int LocateElem(StaticList L, int e) {
    for (int j = 0; j < L->length; j++) {
        if (L->data[j] == e) {
            return j + 1;  // 数组下标转位序（+1）
        }
    }
    return 0;  // 未找到
}

// 遍历输出所有元素
void PrintList(StaticList L) {
    for (int j = 0; j < L->length; j++) {
        printf("%d ", L->data[j]);
    }
    printf("\n");
}

static_list.h

#ifndef STATIC_LIST_H
#define STATIC_LIST_H

#include <stdio.h>
#include <stdbool.h>  // 使用bool类型需要包含此头文件

#define MAX_SIZE 10    // 静态分配的最大容量（考研常用宏定义方式）

// 静态顺序表结构体定义（考研标准写法）
typedef struct {
    int data[MAX_SIZE];  // 静态分配的存储数组（固定大小）
    int length;          // 当前长度（已用元素个数）
} StaticList;

// 初始化顺序表
bool InitList(StaticList *L);

// 插入元素（位序i，从1开始）
bool ListInsert(StaticList *L, int i, int e);

// 删除元素（位序i，返回被删除元素）
bool ListDelete(StaticList *L, int i, int *e);

// 按位查找（返回第i个元素）
int GetElem(StaticList L, int i);

// 按值查找（返回第一个等于e的位序，不存在返回0）
int LocateElem(StaticList L, int e);

// 遍历输出所有元素
void PrintList(StaticList L);

#endif

main.c

#include "static_list.h"

int main() {
    StaticList L;
    
    // 初始化测试
    if (InitList(&L)) {
        printf("顺序表初始化成功！最大容量：%d\n", MAX_SIZE);
    } else {
        printf("顺序表初始化失败！\n");
        return 1;
    }

    // 插入测试（插入到最大容量验证）
    printf("\n=== 插入测试 ===\n");
    for (int i = 1; i <= MAX_SIZE + 2; i++) {  // 尝试插入12个元素（超过最大容量10）
        if (ListInsert(&L, i, i*10)) {
            printf("插入位序%d，值%d成功！当前长度：%d\n", i, i*10, L.length);
        } else {
            printf("插入位序%d失败！\n", i);
        }
    }
    printf("最终顺序表内容：");
    PrintList(L);

    // 按位查找测试
    printf("\n=== 按位查找测试 ===\n");
    int pos = 5;
    int elem = GetElem(L, pos);
    printf("第%d个元素的值是：%d\n", pos, elem);

    // 按值查找测试
    printf("\n=== 按值查找测试 ===\n");
    int target = 70;
    int found_pos = LocateElem(L, target);
    if (found_pos) {
        printf("值%d出现在位序%d\n", target, found_pos);
    } else {
        printf("值%d未找到\n", target);
    }

    // 删除测试（删除中间元素验证）
    printf("\n=== 删除测试 ===\n");
    int del_pos = 3;
    int del_elem;
    if (ListDelete(&L, del_pos, &del_elem)) {
        printf("删除位序%d成功！被删除值：%d\n", del_pos, del_elem);
        printf("删除后顺序表内容：");
        PrintList(L);
        printf("当前长度：%d\n", L->length);
    } else {
        printf("删除位序%d失败！\n", del_pos);
    }

    // 测试满删除（删除最后一个元素）
    printf("\n=== 满删除测试 ===\n");
    while (L.length > 0) {
        int temp;
        ListDelete(&L, L.length, &temp);
        printf("删除最后一个元素%d，当前长度：%d\n", temp, L.length);
    }
    return 0;
}

代码说明（关键点）：

  1. 结构体定义：使用data[MAX_SIZE]静态数组和length（当前长度）两要素，与教材《数据结构》（严蔚敏版）完全一致。
  2. 初始化操作：无需动态内存分配，直接将length置 0，体现静态分配 “空间预分配” 的特点。
  3. 插入操作：
    • 检查位序合法性（1 ≤ i ≤ length+1）
    • 核心限制：当length == MAX_SIZE时无法插入（静态分配的根本约束，考研常考此边界条件）
    • 元素后移方向正确（从后往前避免覆盖）
  4. 删除操作：
    • 检查位序合法性（1 ≤ i ≤ length）
    • 保存被删除元素值（符合考研 “返回被删元素” 的要求）
    • 元素前移方向正确（从前往后避免覆盖）
  5. 查找操作：
    • 按位查找时间复杂度 O (1)（体现顺序表随机访问优势）
    • 按值查找时间复杂度 O (n)（顺序查找的标准实现）
  6. 内存特性：无需显式销毁（静态数组由系统自动回收），区别于动态分配版本。

测试代码验证场景：

  • 容量限制测试（插入超过MAX_SIZE时失败）
  • 边界插入（头部 / 尾部插入）
  • 非法位序处理（自动过滤无效位置）
  • 满容量插入失败验证（第 11、12 次插入失败）
  • 删除后元素前移验证（删除中间元素后后续元素前移）
  • 空表 / 满表边界操作（删除至空表的过程验证）

本网站原创文章版权归何大锤的狂飙日记所有。发布者：何大锤，转转请注明出处：何大锤的博客

赞 (0)
何大锤的头像何大锤管理团队
0 0

相关推荐

  • 08 - 数据结构基础知识补充 数据结构

    08 – 数据结构基础知识补充

    内存分类 一、静态 / 全局内存（程序运行期间一直存在） 特点：全局变量和静态变量（用static声明）的内存，在程序启动时分配，程序结束才释放。通俗理解：像「公共仓库」，一旦创建就一直存在，所有需要的地方都能访问（全局变量），或在特定范围内持续保留（静态变量）。 解释： 二、自动内存（栈内存，函数调用时临时创建） 特点：函数内的普通局部变量（不用stati…

    何大锤的头像 何大锤
    2025年6月6日
    400
  • 06 - 第二章数据结构线性表 - 顺序表代码实现（顺序表查找操作） 数据结构

    06 – 第二章数据结构线性表 – 顺序表代码实现（顺序表查找操作）

    线性表的基本操作（GetElem&LocateElem） 一、GetElem(L,i,&e) 按位查找：获取表L中第 i 个位置元素的值 代码实现1 – 静态分配方式 运行结果： 代码实现2 – 动态分配方式 运行结果： 代码说明： 注意点： 动态顺序表（SeqList） 静态顺序表（SqList） 二、LocateE…

    何大锤的头像 何大锤
    2025年5月27日
    000
  • 05 - 第二章数据结构线性表 - 顺序表代码实现（插入和删除操作） 数据结构

    05 – 第二章数据结构线性表 – 顺序表代码实现（插入和删除操作）

    线性表的基本操作(ListInsert&ListDelete） 1、ListInsert(&L,i,e) 功能：1、插入操作实现，在表L中的第i个位置上插入指定元素e。2、静态分配方式插入操作 定义插入操作关键步骤1. 检查表是否已满（静态分配的核心限制）2. 检查插入位置有效性（i的合法范围：1 ≤ i ≤ length+1）3. 从最后一…

    何大锤的头像 何大锤
    2025年5月26日
    100
  • 04 - 第二章数据结构线性表 - 顺序表代码实现（初始化线性表和销毁操作） 数据结构

    04 – 第二章数据结构线性表 – 顺序表代码实现（初始化线性表和销毁操作）

    线性表的基本操作（InitList&DestroyList） 1、InitList(&L) 功能：初始化表，构造一个空的线性表L，分配空间 运行结果： 2、DestroyList(&L) 销毁操作。销毁线性表，并释放线性表L所占用的内存空间 运行结果： 注意点： 操作符 L 的类型 示例代码 等价写法 -> 结构体指针 SeqL…

    何大锤的头像 何大锤
    2025年5月26日
    600
  • 03 - 第二章数据结构线性表 - 顺序表 数据结构

    03 – 第二章数据结构线性表 – 顺序表

    2.1 线性表的定义和基本操作 2.1.1 线性表的定义 2.1.2 线性表的基础操作 InitList(&L) 初始化表。构造一个空的线性表L，分配内存空间。 DestroyList(&L) 销毁操作。销毁线性表，并释放线性表L所占用的内存空间 ListInsert(&L;i,e) 插入操作。在表L中的第i个位置上插入指定元素e。 …

    何大锤的头像 何大锤
    2025年5月26日
    400

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们

2211932694

在线咨询： QQ交谈

邮件：hdcblog1999@163.com

工作时间：周一至周五，9:30-18:30，节假日休息

关注微信
网站建设中ing......