数据结构
2019-11-07 17:52:54 35 举报AI智能生成
数据结构
作者其他创作
大纲/内容
数组(Array)
索引
类型
一维数组
多维数组
基本操作
Insert——在指定索引位置插入一个元素
Get——返回指定索引位置的元素
Delete——删除指定索引位置的元素
Size——得到数组所有元素的数量
适用场景
频繁查询
对存储空间要求不大
很少增加和删除
栈(Stack)
LIFO（后进先出）
基本操作
Push——在顶部插入一个元素
Pop——返回并移除栈顶元素
isEmpty——如果栈为空，则返回true
Top——返回顶部元素，但并不移除它
适用场景
实现递归功能
例如斐波那契数列
队列(Queue)
FIFO（先进先出）
基本操作
Enqueue()——在队列尾部插入元素
Dequeue()——移除队列头部的元素
isEmpty()——如果队列为空，则返回true
Top()——返回队列的第一个元素
适用场景
多线程阻塞队列管理
链表(Linked List)
概念
链表是另一个重要的线性数据结构
链表就像一个节点链，其中每个节点包含着数据和指向后续节点的指针。
作用
文件系统
哈希表
邻接表
类型
单链表（单向）
双向链表（双向）
基本操作
InsertAtEnd - 在链表的末尾插入指定元素
InsertAtHead - 在链接列表的开头/头部插入指定元素
Delete - 从链接列表中删除指定元素
DeleteAtHead - 删除链接列表的第一个元素
Search - 从链表中返回指定元素
isEmpty - 如果链表为空，则返回true
适用场景
数据量较小
需要频繁增加删除
图(Graph)
概念
图是一组以网络形式相互连接的节点。
节点也称为顶点。
一对节点（x，y）称为边（edge），表示顶点x连接到顶点y。
类型
无向图
有向图
遍历算法
广度优先搜索
深度优先搜索
树(Tree)
概念
树形结构是一种层级式的数据结构，由顶点（节点）和连接它们的边组成。
区分树和图的重要特征是树中不存在环路。
基本术语
Root - 根节点
Parent - 父节点
Child - 子节点
Leaf - 叶子节点
Sibling - 兄弟节点
类型
N元树
平衡树
二叉树
二叉搜索树
AVL树
红黑树
2-3树
字典树（Trie）
概念
字典树，也称为“前缀树”，是一种特殊的树状数据结构，对于解决字符串相关问题非常有效。
适用场景
是链表和数组的优化方案
处理大批量动态数据
堆(Heap)
概念
堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，
性质
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
适用场景
一般用来做数组中的排序，称为堆排序。
散列表(Hash)
概念
哈希法（Hashing）是一个用于唯一标识对象并将每个对象存储在一些预先计算的唯一索引（称为“键（key）”）中的过程。
性能因素
哈希函数
哈希表的大小
碰撞处理方法
0 条评论
下一页
