当前位置： 首页 > article >正文

【数据结构】—— 顺序表的实现与优化：空间管理与增容策略

article 2025/1/20 11:13:28

文章目录

  • 顺序表的基本概念与结构
  • 顺序表的分类
    • 静态顺序表
    • 动态顺序表
  • 顺序表问题与思考
    • 插入与删除的时间复杂度
    • 增容的开销
    • 如何解决空间浪费问题？

顺序表作为一种常见的线性数据结构，广泛应用于各种编程任务中。它通过连续的物理内存存储数据元素，提供了高效的随机访问功能。在这篇博客中，我们将深入探讨顺序表的结构、分类、实现方法以及它的一些问题与优化策略，尤其是如何解决空间浪费和增容问题。

顺序表的基本概念与结构

顺序表（Sequential List）是一种线性数据结构，它使用一段连续的内存空间来存储数据元素，通常以数组的形式存储。顺序表的优点在于可以通过索引快速访问任意元素，时间复杂度为O(1)。但是，顺序表也有它的缺点，尤其是在元素的插入和删除时，因为它可能需要移动大量元素，导致时间复杂度达到O(N)。

顺序表与数组的区别在于，顺序表通常对数组进行了封装，提供了常用的增删改查等操作接口，使得开发者可以更方便地使用。

顺序表的分类

顺序表主要分为两种类型：静态顺序表和动态顺序表。

静态顺序表

静态顺序表使用固定大小的数组存储数据元素。在初始化时就为数组分配好一定的空间，因此它的容量是固定的。静态顺序表的缺点在于，当数据量较大时，空间可能不足；而当数据量较小且数组容量过大时，又会浪费大量空间。

#include <stdio.h>

#define MAX_SIZE 100 // 定义顺序表的最大容量

typedef int SeqListDataType; // 顺序表存储的数据类型

// 顺序表结构体
typedef struct {
    SeqListDataType data[MAX_SIZE]; // 存储数据的数组
    int size; // 当前顺序表中的有效元素个数
} SeqList;

// 初始化顺序表
void SeqListInit(SeqList* list);

// 销毁顺序表
void SeqListDestroy(SeqList* list);

// 打印顺序表中的所有元素
void SeqListPrint(SeqList* list);

// 获取指定位置的元素
SeqListDataType SeqListGet(SeqList* list, int index);

// 插入操作：在指定位置插入元素
void SeqListInsert(SeqList* list, int index, SeqListDataType value);

// 删除操作：删除指定位置的元素
void SeqListRemove(SeqList* list, int index);

// 查找元素：返回元素第一次出现的位置
int SeqListFind(SeqList* list, SeqListDataType value);

// 清空顺序表
void SeqListClear(SeqList* list);

#include <stdio.h>

#define MAX_SIZE 100 // 定义顺序表的最大容量

typedef int SeqListDataType; // 顺序表存储的数据类型

// 顺序表结构体
typedef struct {
    SeqListDataType data[MAX_SIZE]; // 存储数据的数组
    int size; // 当前顺序表中的有效元素个数
} SeqList;

// 初始化顺序表
void SeqListInit(SeqList* list) {
    list->size = 0; // 初始化时，顺序表为空
}

// 销毁顺序表
void SeqListDestroy(SeqList* list) {
    list->size = 0; // 重置顺序表大小
}

// 打印顺序表中的所有元素
void SeqListPrint(SeqList* list) {
    for (int i = 0; i < list->size; i++) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

// 获取指定位置的元素
SeqListDataType SeqListGet(SeqList* list, int index) {
    if (index >= 0 && index < list->size) {
        return list->data[index];
    } else {
        printf("Index out of bounds.\n");
        return -1; // 错误返回
    }
}

// 插入操作：在指定位置插入元素
void SeqListInsert(SeqList* list, int index, SeqListDataType value) {
    if (index < 0 || index > list->size || list->size == MAX_SIZE) {
        printf("Invalid index or sequence full.\n");
        return;
    }

    for (int i = list->size; i > index; i--) {
        list->data[i] = list->data[i - 1];
    }
    list->data[index] = value;
    list->size++;
}

// 删除操作：删除指定位置的元素
void SeqListRemove(SeqList* list, int index) {
    if (index < 0 || index >= list->size) {
        printf("Invalid index.\n");
        return;
    }

    for (int i = index; i < list->size - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->size--;
}

// 查找元素：返回元素第一次出现的位置
int SeqListFind(SeqList* list, SeqListDataType value) {
    for (int i = 0; i < list->size; i++) {
        if (list->data[i] == value) {
            return i;
        }
    }
    return -1; // 未找到
}

// 清空顺序表
void SeqListClear(SeqList* list) {
    list->size = 0;
}

int main() {
    SeqList list;
    SeqListInit(&list);
    
    SeqListInsert(&list, 0, 10);
    SeqListInsert(&list, 1, 20);
    SeqListInsert(&list, 2, 30);
    
    SeqListPrint(&list);
    
    SeqListRemove(&list, 1);
    SeqListPrint(&list);
    
    printf("Element at index 1: %d\n", SeqListGet(&list, 1));
    
    int index = SeqListFind(&list, 30);
    printf("Found 30 at index: %d\n", index);

    SeqListClear(&list);
    SeqListPrint(&list);

    return 0;
}

动态顺序表

动态顺序表通过按需申请内存空间来解决静态顺序表容量固定的问题。随着数据的增加，动态顺序表会自动扩展其容量，从而避免空间浪费。动态顺序表通常采用一个初始容量，当元素数量超过容量时，动态分配更大的内存空间。

动态顺序表的实现
下面是一个动态顺序表（SeqList）的实现。我们将通过一个简单的结构体和一些常见操作来展示其基本功能。

#define INIT_CAPACITY 4
typedef int SLDataType;

// 动态顺序表 -- 按需申请
typedef struct SeqList {
    SLDataType* a;
    int size;       // 有效数据个数
    int capacity;   // 空间容量
} SL;

// 初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);

// 扩容
void SLCheckCapacity(SL* ps);

// 头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);

// 指定位置插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);

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

#define INIT_CAPACITY 4 // 初始容量

typedef int SeqListDataType; // 顺序表存储的数据类型

// 动态顺序表结构体
typedef struct SeqList {
    SeqListDataType* data; // 存储数据的动态数组
    int size; // 当前顺序表中的有效元素个数
    int capacity; // 顺序表的总容量
} SeqList;

// 初始化顺序表
void SeqListInit(SeqList* list) {
    list->size = 0;
    list->capacity = INIT_CAPACITY;
    list->data = (SeqListDataType*)malloc(sizeof(SeqListDataType) * list->capacity);
}

// 销毁顺序表
void SeqListDestroy(SeqList* list) {
    free(list->data);
    list->size = 0;
    list->capacity = 0;
}

// 扩容
void SeqListCheckCapacity(SeqList* list) {
    if (list->size == list->capacity) {
        list->capacity *= 2;
        list->data = (SeqListDataType*)realloc(list->data, sizeof(SeqListDataType) * list->capacity);
    }
}

// 打印顺序表中的所有元素
void SeqListPrint(SeqList* list) {
    for (int i = 0; i < list->size; i++) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

// 获取指定位置的元素
SeqListDataType SeqListGet(SeqList* list, int index) {
    if (index >= 0 && index < list->size) {
        return list->data[index];
    } else {
        printf("Index out of bounds.\n");
        return -1; // 错误返回
    }
}

// 插入操作：在指定位置插入元素
void SeqListInsert(SeqList* list, int index, SeqListDataType value) {
    if (index < 0 || index > list->size) {
        printf("Invalid index.\n");
        return;
    }

    SeqListCheckCapacity(list); // 检查是否需要扩容

    for (int i = list->size; i > index; i--) {
        list->data[i] = list->data[i - 1];
    }
    list->data[index] = value;
    list->size++;
}

// 删除操作：删除指定位置的元素
void SeqListRemove(SeqList* list, int index) {
    if (index < 0 || index >= list->size) {
        printf("Invalid index.\n");
        return;
    }

    for (int i = index; i < list->size - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->size--;
}

// 查找元素：返回元素第一次出现的位置
int SeqListFind(SeqList* list, SeqListDataType value) {
    for (int i = 0; i < list->size; i++) {
        if (list->data[i] == value) {
            return i;
        }
    }
    return -1; // 未找到
}

// 清空顺序表
void SeqListClear(SeqList* list) {
    list->size = 0;
}

int main() {
    SeqList list;
    SeqListInit(&list);
    
    SeqListInsert(&list, 0, 10);
    SeqListInsert(&list, 1, 20);
    SeqListInsert(&list, 2, 30);
    
    SeqListPrint(&list);
    
    SeqListRemove(&list, 1);
    SeqListPrint(&list);
    
    printf("Element at index 1: %d\n", SeqListGet(&list, 1));
    
    int index = SeqListFind(&list, 30);
    printf("Found 30 at index: %d\n", index);

    SeqListClear(&list);
    SeqListPrint(&list);

    SeqListDestroy(&list);

    return 0;
}

顺序表问题与思考

虽然顺序表是一种高效的数据结构，但它也有一些问题，尤其是在空间管理和扩容方面。下面列出了一些主要问题及思考方向：

插入与删除的时间复杂度

顺序表中，头部和中间位置的插入删除操作需要移动大量元素，因此时间复杂度是O(N)。当数据量增大时，这些操作可能会变得非常慢。

增容的开销

顺序表的增容通常是通过重新分配更大的内存空间来实现的。为了减少频繁增容的开销，通常会选择将容量扩展为当前容量的2倍。但是，这种方式可能导致空间浪费。例如，当容量达到100时，扩容到200，之后只插入了5个数据，那么剩余的95个空间就会浪费。

如何解决空间浪费问题？

为了解决顺序表增容导致的空间浪费问题，我们可以考虑以下优化策略：
增容策略优化：可以选择增容策略，例如，当容量达到一定阈值时，增容的倍数可以适当减小，比如选择1.5倍或者更小的增容策略，来减少空间浪费。
懒惰释放：在某些情况下，可以通过延迟释放空间来避免频繁的内存申请和释放，尤其是在元素删除后。


http://www.kler.cn/a/510595.html

相关文章：

  • html全局遮罩，通过websocket来实现实时发布公告
  • 【大数据】机器学习------支持向量机（SVM)
  • SpringBoot多级配置文件
  • VUE3 vite下的axios跨域
  • 【Azure 架构师学习笔记】- Azure Function (2) --实操1
  • Ubuntu本地部署网站
  • 使用Python开发PPT文本提取工具
  • Spring的Bean详解=Bean别名+作用范围+使用场景
  • 4.Proto 3 语法详解
  • opencv笔记2
  • htmlcssJavaScript网页开发：年会手机号抽奖案例
  • ANSYS FLUENT学习笔记（八）-实战案例-网格划分
  • 使用 CFX 中的标量传输方程对染料冲洗数值建模：以主动脉弓血流为例
  • python轻量级框架-flask
  • 【AI论文】生成式视频模型是否通过观看视频学习物理原理？
  • 【Linux】Linux入门（2）常见指令
  • Jupter安装
  • vscode的字体图标库-icomoon
  • CSS 动画相关属性
  • 【分类】【损失函数】处理类别不平衡：CEFL 和 CEFL2 损失函数的实现与应用
  • 准备面试3个月，加油！
  • vue3+elementPlus之后台管理系统（从0到1）(day2)
  • 常用的UI自动化测试框架是哪些？有什么优缺点？如何选择？
  • 20250118 PPT画的论文插图如何导出高分辨率图片：修改电脑注册表
  • LeetCode：2266. 统计打字方案数（DP Java）
  • Swift语言的物联网