数据结构

数据结构思维导图， 如 数据类型是一个值的集合和定义在此集合上的一组操作的总称，刚开始复习没记完，一起来看看吧。

数据结构

• 绪论
• 线性数据结构
  • 线性表
    • 逻辑结构
    • 线性表的定义
      • 相同数据类型、有限序列
        • 表长、空表
        • 表头、表尾
        • 前驱、后继
        • 位序
          • 位序从1开始，数组下标从0开始
    • 线性表的基本操作
      • 初始化表
        • InitList(&L)
      • 销毁操作
        • DestroyList(&L)
      • 插入操作
        • ListInsert(&L,i,e)
      • 删除操作
        • ListDelete(&L,i,&e)
      • 按值查找
        • LocateElem(&L,e)
      • 按位查找
        • GetElem(&L,i)
      • 其他常用操作
        • 求表长
          • Length(L)
        • 输出操作
          • PrintList(L)
        • 判空操作
          • Empty(L)
      • 注意： ①对数据的操作（记忆方式）—> 创建、销毁，增删改查； ②命名要有可读性； ③对参数的修改结果需要“带回来”，要传入参数的引用“&”
    • 线性表的实现
      • 存储结构（物理结构）
      • 顺序表（顺序存储）
        • 定义
          • 逻辑上相邻、物理位置上也相邻
            • sizeof(ElemType)：获取一个数据元素的大小
        • 实现
          • 静态分配
            • • 内存中有遗留的“脏数据”；初始化顺序表时，须将length赋0
          • 动态分配
            • • C语言动态申请和释放内存空间
                • malloc、free函数所在的头文件：#include<stdlib.h>
                • malloc函数
                  • L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);
                    • data指针指向所分配的一整片连续存储空间的起始地址
                • free函数
                  • free(ElemType *p)
              • C++动态申请和释放内存空间
        • 特点
          • ①随机访问
            • 能在O(1)时间内找到第i个元素
          • ②存储密度高
            • 每个节点只存储数据元素
          • ③拓展容量不方便
          • ④插入、删除操作不方便
            • 需移动大量元素
        • 基本操作
          • 注意位序和数组下标之间的关系
          • 插入
            • • 时间复杂度
                • 最好情况：插到表尾
                  • 最好时间复杂度=O(1)
                • 最坏情况：插到表头
                  • 最坏时间复杂度=O(n)
                • 平均情况
          • 删除
            • 【图库：插入操作】
              • 时间复杂度
          • 查找
            • 按位查找
              • 【图库：按位查找】
                • 时间复杂度：O(1)
            • 按值查找
              • C语言中，结构体比较不能直接用“==”
              • 【图库：按值查找】
                • 时间复杂度
      • 链表（链式存储）
• 非线性数据结构