Please enable JavaScript.

Coggle requires JavaScript to display documents.

数据结构 (数据 (数据类型 (抽象数据类型（ADT） (三元组 (数据关系, 基本操作集)), 值的集合和一组操作), 基本单位 (数据元素…

- - - - 三元组
        
        数据关系
        
        基本操作集
  - - - 复杂的多个数据项
        
        数据项
        
        构成数据元素的不可分割的最小单位
        
        数据项
        
        数据项
        
        类比于字段
      - 学生记录（数据元素）
        
        学号（数据项）
        
        姓名
        
        性别
        
        \(\cdots\)
      - 具有相同性质的数据元素的集合
      - 类比于记录
      - 简单的整数字符
  - - - 类比于表
- - - - 把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
      - 优点：可以实现随机存取，每个元素占据最少的存储单元
      - 缺点：只能使用相邻的一整块存储单元，可能会产生外部碎片
    - - 借助指示元素存储地址的指针来表示元素之间的逻辑关系
      - 优点：不会出现碎片现象
      - 缺点：每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取
    - - 根据元素的关键字直接计算出该元素的存储地址
      - 优点：检索、增加和删除节点的操作都很快
      - 缺点：若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销
  - - - 线性表
    - - 集合
      - 树
      - 图
- - - - 时间复杂度
        
        语句的频度：最深层原操作执行的次数
        
        一般按最坏时间复杂度计算
        
        \( O(1) < O(\log_2^n) < O(n) < O(n\log_2^n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)\)
        
        常见问题规模考察
        
        如果循环中\(i = i*2\)，则时间复杂度为对数阶
      - 空间复杂度
        
        \(算法\color\red{原地工作}是指算法所需要的辅助空间为常量，即O(1)\)
        
        算法的存储量
        
        输入数据所占空间当输入只取决于问题本身，而与算法无关，只考虑辅助空间
        
        程序本身所占空间
        
        辅助变量所占空间原地工作（r如冒泡中i，j，change等变量
        ）
        
        若所需辅助空间相对于输入数据来说是一个常数，则称此算法为原地工作
- - - - 数据元素是单个字母字符
      - 一个数据元素由若干个数据项组成，这种情况下，常把数据元素称之为记录
      - 含有大量记录的线性表又称文件
    - - 优点：随机存取，时间复杂度为O(1)
      - 缺点：插入删除,union，merge需要LocateElem时间复杂度为O(n)
      - 实现
        
        顺序存储结构
      - 联系实际生活
        
        游戏中用户列表，注册登录。
    - - 优点：在插入删除时，不需要大量移动元素，时间复杂度为O(1)
      - 缺点：由于物理位置上不相邻，所以查找需要的时间复杂度上升，无法随机存取
      - 实现：
        
        单链表尾进头出
        
        静态链表
        
        双向链表
        
        循环链表
      - 联系实际生活
        
        游戏中武器频繁的更换。
        
        医院的拿号候诊
    - - 栈和队列
        
        \(后进先出（Last\ In\ First\ Out）\)
        
        栈
        
        数学性质
        
        \(\frac{1}{n+1}C_{2n}^{n}\)
        
        联系实际生活
        
        弹夹式手枪，先安装的子弹要到最后才能取出，而最后装入的子弹直接就能取出。
        
        基本操作
        
        入栈（压栈）
        
        出栈（弹栈）
        
        进出栈顺序，如果最后一个进的是第一个出的，那就代表之前的都还只是压在栈内，就等同于之前的元素之执行了进栈操作，所以123进栈，不可能312出。
        
        顺序存储实现
        
        基本概念
        
        栈空栈满
        
        2 more items...
        
        2 more items...
        
        基本运算
        
        代码
        
        图示
        
        两栈共享空间
        
        联系实际生活
        
        合租
        
        股票
        
        2 more items...
        
        实现
        
        使用一个数组来存两个栈
        
        3 more items...
        
        特点
        
        通常用在两个栈的空间需求相反
        
        两个栈数据类型相同
        
        链式存储实现
        
        不需要头结点
        
        意义
        
        栈的引入简化了程序设计的问题，划分了不同的关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题的核心。反之，像数组等，因为要分散精力去考虑数组的下标增减等细节问题，反而掩盖了问题的本质。
        
        应用
        
        递归
        
        优缺点
        
        2 more items...
        
        前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址都被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。
        
        四则运算表达式求值
        
        \(后缀（逆波兰）表示法定义\)
        
        中缀表达式转化为后缀表达式
        
        2 more items...
        
        运算规则
        
        1 more item...
        
        \(先进先出（First\ In\ First\ Out）\)
        
        \(队列\)
        
        联系实际生活
        
        电脑卡机，不管什么操作都没反应，然后突然把刚才的操作全部执行一遍。
        
        打电话给客服人员，发现占线，或需要排队等候。
        
        键盘进行各种字母或字符的输入
        
        记事本软件向显示器的输出
        
        基本概念
        
        队头
        
        出队
        
        3 more items...
        
        O(n)
        
        队尾
        
        入队
        
        3 more items...
        
        O(1)
        
        链式存储及其实现
        
        队空
    - - \( InitList( \& L) \)
      - \( LocateElem(SqList\ L,ElemType\ e) \)
      - \(GetElem(L,i)\)
      - \(ListInsert(\&L ,i ,e )\)
      - \(ListDelete(SqList\ *L,int\ i,ElemType\ *e)\)
  - - - 销毁操作
      - 引用操作
        
        ListEmpth(L)
        
        ListLength(L)
        
        PriorElem(L,cur_e,&&pre_e)
        
        NextElem(L,cur_e,&next_e)
        
        GetElem(L,i,&e)
        
        LocateElem(L,e,compare())
        
        ListTraverse()
      - 加工型操作
        
        ClearList(&L)
        
        PutElem(L,i,&e)
        
        ListInsert(&L,i,e)
        
        联系实际生活
        
        插队
        
        ListDelete(&L,i,&e)
      - 初始化操作