首页算法

    我是基于ChatGPT-turbo-3.5实现的AI助手，在此网站上负责整理和概括文章

    本文总结了算法导论基础中几种基本数据结构，包括栈、队列、链表、指针和对象、有根树。栈是后进先出，插入删除分别为压入和弹出；队列是先进先出，插入删除分别为入队和出队；链表包括双向链表和双向循环链表；指针和对象有多数组表示和单数组表示，以及对象的分配与释放过程；有根树即二叉树，包括根、左孩子和右孩子。

    ---

    # 1 栈（后进先出）

    特点：

    • 插入（insert）-- 压入（push），新元素总是在最顶层
    • 删除（delete）-- 弹出（pop），新元素总是第一个删除

    图示：
    栈操作示意图

    # 2 队列（先进先出）

    特点

    • 插入（insert）-- 入队（ENQUEUE）, 新元素总在最末尾
    • 删除（delete）-- 出队（DEQUEUE）, 弹出的元素总是最旧的那个

    图示：
    队列操作示意图
    注明：队列为卷绕型，若 tail [Q]=length [Q], 则 tail [Q]=1；

    上溢：对一个满序列插入一个新元素
    下溢：对一个空序列删除一个元素

    # 3 链表

    双向链表：每一个元素都是一个对象，一个对象包含一个关键字域合两个指针域（next，prev）

    图示：
    双向链表图示

    双向循环链表：带有哨兵，用于简化边界条件的处理

    图示：
    双向循环链表图示

    # 4 指针和对象

    prev,key,next 在这里作为指针

    1. 对象的多数组表示（三个数组 prev,key,next）
    对象的多数组图示
    2. 对象的单数组表示
    对象的单数组图示
    3. 对象的分配与释放

    • 将多数组中剩余的对象（free）组成一个单链表，称为自由表

    • 自由表类似于一个栈，可以通过栈操作 PUSH 和 POP 来对自由表实现分配（ALLOCATE）和释放（FREE）过程

    图示：
    对象的分配与释放图示

    # 5 有根树

    就是二叉树。结构包括根（root），left（左孩子），right（右孩子）
    图示：
    有根树图示