数据结构

数据是指对象的表示，即按照适合于通信解释或处理的方式所形成的关于事实，概念或指令的表示，数据元素之间的逻辑关系，从逻辑上描述数据，与数据存储无关。

吉大数据结构

• 绪论
  • 数据
    • 概念：是指对象的表示，即按照适合于通信解释或处理的方式所形成的关于事实，概念或指令的表示
    • 数据只是表示，而无含义
    • 数据元素（或称数据成分）：可称为元素结点或顶点
    • 数据最小单位是数据项
  • 数据的逻辑结构
    • 数据元素之间的逻辑关系，从逻辑上描述数据，与数据存储无关
    • 线性结构（线性表）
      • 一般线性表
      • 栈和队列
      • 串
      • 数组，广义表
    • 非线性结构
      • 集合
      • 树形结构
        • 一股数
        • 二叉树
      • 图状结构
        • 有向图
        • 无向图
  • 数据的存储结构（物理结构）
    • 顺序（数组）
    • 链接(如线性表可以采取链式存储方式）
    • 索引
    • 散列
    • 在图的邻接表表示法中，顶点表一般选用顺序存储方式，边表则常用链接存储方式
    • 线性表可以采用顺序存储或链式存储方式，说明这两种存储方式优缺点？
  • 对数据结构的操作
    • 插入
    • 删除
    • 修改
    • 排序
    • 查找
  • 算法
  • 时间复杂度
    • 0（1）
    • 0（n)
    • 0(logN)
    • 0(n^2)
• 线性表
  • 基本概念
    • 一个线性表是由零个或多个具有相同类型的结点组成的有序集合
    • 表示：（a0,a1,......an-1)
  • 基本操作
    • 创建线性表
      • InitList(&L)
    • 插入操作
      • ListInsert(&L,i,e)
    • 删除操作
      • ListDelete(&L,i,e) e为返回元素值
    • 查找，修改操作
      • LocateElem(L,e):按值查找
      • GetElem(L,i):按位查找
    • 销毁线性表
      • DestroyList(&L)
    • 其他常用操作
      • 求表长
        • Length(L)
      • 输出操作
        • Printlist(L)
      • 判空操作（判断线性表是否为空）
        • Empty(L)
  • 顺序存储
    • 在逻辑上相邻的数据在物理上也相邻，要求一块连续的存储区域
    • 优缺点分析：可以实现随机存取，每个存储单元只存储数据，但插入和删除操作需要大量移动元素
  • 链接存储
    • 逻辑上相邻的数据在物理上不一定相邻，不要求连续的存储区域
    • 优缺点分析：链式存储方式不支持随机存取，每个存储单元除了存储数据外，还需存储附设指针，空间开销大，但是插入和删除不需要移动大量元素，只需要修改指针即可
    • 类型：单链表，双向链表，循环链表
  • 算法实现
    • C语言
    • ADL