# MyDataStructure

**Repository Path**: xxyQwQ/my-data-structure

## Basic Information

- **Project Name**: MyDataStructure
- **Description**: 一只蒟蒻的数据结构代码合集
- **Primary Language**: C++
- **License**: EPL-1.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2022-02-25
- **Last Updated**: 2022-03-24

## Categories & Tags

**Categories**: Uncategorized

**Tags**: 数据结构

## README

# MyDataStructure

#### 项目介绍
一只蒟蒻的数据结构代码合集

#### 实现进度

1. 线性表
    + 线性表抽象类
    + 顺序表类
        - 自动扩容：$O(N)$
        - 清空重置：$O(1)$
        - 长度查询：$O(1)$
        - 随机下标访问：$O(1)$
        - 指定下标的单点增删：$O(N)$
        - 尾部的增删：$O(1)$
        - 查找指定元素：$O(N)$
        - 遍历输出：$O(N)$
    + 单链表类
        - 清空重置：$O(N)$
        - 长度查询：$O(1)$
        - 随机下标访问：$O(N)$
        - 指定下标的单点增删：$O(N)$
        - 尾部的追加：$O(N)$
        - 查找指定元素：$O(N)$
        - 遍历输出：$O(N)$
        - 指定内容的元素删除：$O(N)$
    + 双链表类
        - 清空重置：$O(N)$
        - 长度查询：$O(1)$
        - 随机下标访问：$O(N)$
        - 指定下标的单点增删：$O(N)$
        - 头部的追加：$O(1)$
        - 尾部的追加：$O(N)$
        - 查找指定元素：$O(N)$
        - 遍历输出：$O(N)$
        - 链表反转：$O(N)$
    + 大整数类
        - 字符串构造：$O(L)$
        - 整数构造：$O(L)$
        - 大小比较：$O(L)$
        - 四则运算：$O(L)$
        - 乘方运算：$O(L\log K)$
2. 栈
    + 栈抽象类
    + 顺序表实现栈类
        - 自动扩容：$O(N)$
        - 非空查询：$O(1)$
        - 栈顶增删：$O(1)$
        - 栈顶查询：$O(1)$
        - 清空重置：$O(1)$
    + 链表实现栈类
        - 非空查询：$O(1)$
        - 栈顶增删：$O(1)$
        - 栈顶查询：$O(1)$
        - 清空重置：$O(N)$
3. 队列
    + 队列抽象类
    + 顺序表实现队列类（循环队列）
        - 自动扩容：$O(N)$
        - 非空查询：$O(1)$
        - 队首弹出：$O(1)$
        - 队尾压入：$O(1)$
        - 队首查询：$O(1)$
        - 清空重置：$O(1)$
    + 链表实现队列类（单向队列）
        - 非空查询：$O(1)$
        - 队首弹出：$O(1)$
        - 队尾压入：$O(1)$
        - 队首查询：$O(1)$
        - 清空重置：$O(N)$
4. 字符串
    + 顺序表实现字符串类
        - 字符串构造：$O(L)$
        - 字典序比较：$O(L)$
        - 长度查询：$O(1)$
        - 子串切片：$O(L)$
        - 指定下标的子串增删：$O(L)$
        - 随机下标访问字符：$O(1)$
        - 查找指定子串：$O(L)$
    + 链表实现字符串类
        - 字符串构造：$O(L)$
        - 字典序比较：$O(L)$
        - 长度查询：$O(1)$
        - 子串切片：$O(L)$
        - 指定下标的子串增删：$O(L)$
        - 随机下标访问字符：$O(L)$
5. 二叉树
    + 二叉树抽象类
    + 链表实现二叉树类（依赖链表实现队列类）
        - 交互创建二叉树：$O(N)$
        - 清空重置：$O(N)$
        - 判断非空：$O(1)$
        - 查询根节点：$O(1)$
        - 指定节点查询父子节点：$O(N)$
        - 查询节点总数：$O(N)$
        - 查询树高：$O(N)$
        - 指定节点子树增删：$O(N)$
        - 先序/中序/后序/层次遍历：$O(N)$
        - 输出全部二叉树结构：$O(N)$