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

数据结构------线性表

一、线性表顺序存储详解


(一)线性表核心概念

1. 结构定义
// 数据元素类型
typedef struct person {
    char name[32];
    char sex;
    int age;
    int score;
} DATATYPE;

// 顺序表结构
typedef struct list {
    DATATYPE *head;  // 存储空间基地址
    int tlen;        // 表总长度
    int clen;        // 当前元素个数
} SeqList;
2. 核心特性
  • 有限性:元素个数n ≥ 0
  • 有序性:元素位置由序号确定(a₁~aₙ)
  • 同类型:所有元素属于同一数据类

(二)基本操作接口

1. 创建/销毁
// 创建顺序表
SeqList *CreateSeqList(int len) {
    SeqList *list = (SeqList *)malloc(sizeof(SeqList));
    list->head = (DATATYPE *)malloc(len * sizeof(DATATYPE));
    list->tlen = len;
    list->clen = 0;
    return list;
}

// 销毁顺序表
int DestroySeqList(SeqList *list) {
    free(list->head);
    free(list);
    return 0;
}
2. 状态判断
// 判断表满
int IsFullSeqList(SeqList *list) {
    return list->clen >= list->tlen;
}

// 判断表空
int IsEmptySeqList(SeqList *list) {
    return list->clen == 0;
}

(三)核心操作实现

1. 插入操作
// 尾部插入
int InsertTailSeqList(SeqList *list, DATATYPE data) {
    if (IsFullSeqList(list)) return -1;
    list->head[list->clen++] = data;
    return 0;
}

// 指定位置插入
int InsertPosSeqList(SeqList *list, DATATYPE data, int pos) {
    if (pos < 0 || pos > list->clen) return -1;
    if (IsFullSeqList(list)) return -1;
    
    // 移动后续元素
    for(int i = list->clen; i > pos; i--) {
        list->head[i] = list->head[i-1];
    }
    
    list->head[pos] = data;
    list->clen++;
    return 0;
}
2. 删除操作
// 按姓名删除
int DeleteSeqList(SeqList *list, char *name) {
    for(int i = 0; i < list->clen; i++) {
        if(strcmp(list->head[i].name, name) == 0) {
            // 前移后续元素
            for(int j = i; j < list->clen-1; j++) {
                list->head[j] = list->head[j+1];
            }
            list->clen--;
            return 0;
        }
    }
    return -1;
}

(四)性能分析

1. 时间复杂度对比
操作最好情况最坏情况平均情况
随机访问O(1)O(1)O(1)
插入/删除O(1)O(n)O(n)
查找O(1)O(n)O(n)
2. 空间复杂度
  • 存储空间:O(n)
  • 额外空间:O(1)

(五)内存管理实践

1. 内存管理要点
  1. malloc/free配对:确保每个分配都有释放
  2. 越界访问检查:严格验证索引范围
  3. 野指针处理:释放后置空指针
    free(list->head);
    list->head = NULL;  // 重要!
    

(六)顺序存储优劣分析

1. 优势场景
  • 高频随机访问:学生成绩快速查询
  • 数据规模稳定:固定长度的传感器数据缓存
  • 内存敏感场景:无额外指针开销
2. 局限场景
  • 动态数据管理:实时消息队列
  • 高频插入删除:聊天记录管理
  • 超大稀疏数据:地图坐标存储


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

相关文章:

  • EDAS:投稿经验-word版本-问题解决
  • C语言_数据结构总结9:树的基础知识介绍
  • 51单片机的工作方式
  • 直方图梯度提升:大数据时代的极速决策引擎
  • Windows编译Flash-attention模块
  • 于 Hexo + GitHub Pages 的搭建个人博客网站的详细教程
  • 失败的面试经历(ʘ̥∧ʘ̥)
  • 如何利用物理按键控制LVGL控件的大小与状态
  • 六十天前端强化训练之第二十天React Router 基础详解
  • python-数据类型字符串和列表
  • java学习总结(四)MyBatis多表
  • linux命令-wget与curl命令详解
  • 【Agent】OpenManus-Agent-BaseAgent详细分析
  • 85.HarmonyOS NEXT 网络请求与数据处理:构建可靠的数据层
  • 剖析sentinel的限流和熔断
  • “driver-class-name: com.mysql.cj.jdbc.Driver“报错问题的解决
  • Gitee重新远程连接仓库(Linux)
  • 【Redis】缓存穿透、缓存击穿、缓存雪崩
  • Leetcode2272:最大波动的子字符串
  • 文档搜索引擎