文章目录

数据结构 - 线性表结构逻辑结构物理结构数组链表单链表循环链表双链表 算法泛生栈结构逻辑结构物理结构数组链表 算法应用 队列结构逻辑结构物理结构 算法 串结构逻辑结构物理结构 算法 引用

数据结构 - 线性表

结构

逻辑结构

线性表 (linear list)

存在唯一的一个"第一个"数据元素存在唯一的一个"最后一个"数据元素除"第一个"数据元素外,集合中每个数据元素都存在一个且只有一个的前躯数据元素除"最后一个"数据元素外,集合中每个数据元素都存在一个且只有一个的后继数据元素

物理结构

数组

用一组连续的存储单元依次存储线性表的数据元素. -　设线性表的每个元素需占l个存在储单元,并以所占的第一个单元的存储地址作为数据元素的存储位置.则线性表的第i个元素a_i的存储位置为LOC(a_i) = LOC(a_i) + (i-1)*l

优点: 对于读写操作时间复杂度为O(1) 缺点: 对于插入删除操作时间复杂度为O(n)

链表

用一组任意的存储单元存储线性表的数据元数(存储单元可以为连续或不连续),对于每个数据元素a_i与其直接后继a_i+1的逻辑关系以一个指示其直接后线的信息来表示.这两部分信息组数据元素a_i的存储映像,称为结点:其中存储数据元素的域称为数据域;存储直接后线存储位置的域称为指针域.

单链表

有一个头结点且指针域指向下一后继结点每个结点有且只有一个指向下一后继结点的指针域最后一个结点的指针域为空

循环链表

有一个尾结点且指针域指向下一后继结点最后一个结点的指针域为指向尾结点

双链表

有一个头结点, 后继指针域指向下一后继结点, 前置指针域为空每个结点有一个指向下一后继结点的后继结点的指针域和一个指向上一前置结点的前置指针域最后一个结点, 后继指针域为空, 前置指针域指向上一前置结点

优点: 对于插入删除操作时间复杂度为O(1) 缺点: 对于读写操作时间复杂度为O(n)

算法

泛生

栈

结构

逻辑结构

栈(stack)是符合LIFO结构(Last In First Out)的线性表 限定仅在表尾进行插入或删除操作的线性表. 对于栈来说,表尾端有其特殊含义,称为栈顶(top),表头端称为栈底(bottom) 不含元素的空表称为空栈

物理结构

如线性表, 增加LIFO限制

数组

链表

算法

应用

表达式求值括号校验递归

队列

结构

逻辑结构

队列(queue)是一种FIFO结构(First In First Out)的线性表 限定表的一端进行插入,另一端进行删除 允许插入的一端称为队尾(rear),允许删除的一端称为队头(front)

物理结构

如线性表, 增加FIFO限制

算法

串

结构

逻辑结构

串(String)由零个或多个字符组成的有限序列 其中字符的数目称为串的长度,零个字符的串称为空串

物理结构

如线性表

算法

KMP 模式匹配算法

克努斯-莫里斯-普拉特算法 - 维基百科，自由的百科全书 https://zh.wikipedia.org/zh-hant/克努斯-莫里斯-普拉特算法

引用

数据结构: C语言版/严蔚敏,吴伟民编着. --北京: 清华大学出版社, 2017 ISBN 978-7-302-14751-0单向链表 - 维基百科，自由的百科全书 https://zh.wikipedia.org/wiki/单向链表双向链表 - 维基百科，自由的百科全书 https://zh.wikipedia.org/wiki/双向链表