【WIP】算法与数据结构回顾 - 广义表

【WIP】算法与数据结构回顾 - 广义表

图源:@Rella 《glow》 91882132

简述

广义表是线性表的一种推广。线性表要求表中元素拥有统一的类型,而广义表无此限制。需要注意的是,广义表和线性表长度一般认为是有限的,但广义表的深度可以是无限的(即递归表)。

广义表是一种数据结构。对广义表的常见操作包括:

  • 创建
  • 从字符串形式创建
  • 销毁
  • 复制
  • 取表头
  • 取表尾
  • 判空
  • 求长度
  • 求深度
  • 从表头插入
  • 从表头删除
  • 遍历

广义表是Lisp语言的基本数据结构。后文以Common Lisp和C++给出各基本操作的示例。

名词注解

长度

指广义表中的元素个数。举例如下:

例一

1
(a, b)

该表中共有两个元素:原子项a,原子项b。因而该表的长度为2。

例二

1
(a, (b, c))

该表中共有两个元素:原子项a,广义表(b, c)。因而该表的长度为2。

深度

指广义表中子表的嵌套层数。举例如下:

例一

1
(a, b)

该表中没有子表,因而该表的深度为1。

例二

1
(a, (b, c))

该表中嵌套了一个无嵌套的子表,因而该表的深度为2。

阅读更多

【持续更新】算法与数据结构回顾 - 大纲

由于高中接触过,大学本科期间又深入了些,以防忘记记一些注意事项、概念和模板之类的东西。

简单分类

数据结构

  • 一维:

    • 基础:数组(Array),链表(Linked list)

    • 高级:栈(Stack),队列(Queue),双端队列(Deque),集合(Set),映射(Map)等。

  • 二维:

    • 基础:树(Tree),图(Graph)

    • 高级:二叉搜索树(BST),堆(Heap),并查集(Disjoint Set),字典树(Trie)等。

  • 特殊结构:

    • 位运算(Bitwise),布隆过滤器(BloomFilter)

    • 缓存(LRU)

    • ……

  • ……

算法

  • 分支(if-else,switch)

  • 迭代(for,while)

  • 递归(分治法,回溯法等)

  • 搜索(深搜,广搜,A*等)

  • 动态规划

  • 二分查找

  • 贪心

  • 计算几何

  • ……

阅读更多
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×