datetime:2022-04-09 17:46
author:nzb

数据结构与算法

绪论

  • 基本概念

    • 数据

    • 数据元素、数据项

    • 数据对象、数据结构

    • 数据类型、抽象数据类型（ADT）

  • 数据结构三要素

    • 逻辑结构

      • 集合

      • 线性结构

      • 树形结构

      • 图状结构（网状结构）

    • 物理结构（存储结构）

      • 顺序存储

        物理内存中是连续的

      • 非顺序存储

        物理内存中是分散的

        • 链式存储

        • 索引存储

        • 散列存储

    • 数据的运算

  • 学习建议

    • 概念多，比较无聊。抓大放小，重要的是形成框架，不必纠结细节概念。

队列

  • 定义

    • 一种操作受限的线性表，只能在队尾插入、在队头删除

    • 特性：先进先出（FIFO）

    • 术语：队头、队尾、空队列、队头元素、队尾元素

  • 基本操作

    • 创、销

    • 增、删（入队、出队、只能在规定的一段进行）

    • 查（获得队头元素，但不删除）

    • 判空

  • 队列的顺序实现

    • 实现思路

      • 用静态数组存放数据 元素，设置队头/队尾（front、rear）指针

      • 循环队列：用模运算（取余）将存储空间在逻辑上变为“环状”

      • Q.rear = (Q.rear + 1) % MaxSize

    • 重要考点

      • 如何初始化、入队、出队

      • 如何判空、判满

      • 如何计算队列的长度

    • 分析思路

      • 确定 front、rear 指针的指向

        • rear 指向队尾元素后一个位置

        • rear 指向队尾元素

      • 确定判空判满的方法

        • 牺牲一个存储单元

        • 增加 size 变量记录队列长度

        • 增加 tag = 0/1 用于标记最近的一次操作是出队/入队

  • 队列的链式实现

    • 区别

      • 带头结点

      • 不带头结点

    • 基本操作

      • 创（初始化）

      • 增（入队）

        注意第一个元素入队

      • 删（出队）

        注意 最后一个元出队

      • 查（获取队头元素）

      • 判空

      • 判满？不存在的，可以无限加（内存足够）

  • 队列变种

    • 双端队列

      允许从两端插入、两端删除的队列

    • 输入受限的双端队列

      允许从两端删除、从一端插入的队列

    • 输出受限的双端队列

      允许从两端插入、从一端删除的队列

  • 队列应用

    • 树的层次遍历

    • 图的广度优先遍历

    • 操作系统的应用

      • CPU资源的分配：多个进程运行（浏览器、QQ、微信）

      • 打印数据缓冲区

results matching ""

    No results matching ""