- 线性表Linear List//n个元素的有限序列
- 线性表的关系：描述线性表中，任意量相邻元素的关系：先行元素ai，后记元素ai-1
- 按照内存存储方式，分为两种：
- 静态数据结构or密集表Dense List
- 使用连续分配的内存空间存储有序表中数据，编译时给相关变量分配好内存，需要实现申明最大可能占用空间，可能存在内存浪费，eg:数组
- 优点：设计简单，读取和修改，O（1）
- 缺点：增加和删除，O(n+1)/2//需要移动大量数据
- 使用连续分配的内存空间存储有序表中数据，编译时给相关变量分配好内存，需要实现申明最大可能占用空间，可能存在内存浪费，eg:数组
- 动态数据结构or链表Linked List
- 使用不连续内存空间存储具有线性表特性的数据
- 优点：插入删除方便O（1）
- 缺点：设计复杂,查找数据O（n）
- 使用不连续内存空间存储具有线性表特性的数据
- 静态数据结构or密集表Dense List
- 应用在：
- 线性数据结构（如数组、链表、栈和队列等）
- 数组Array
- 特点
- 随机访问时性能最好
- 链表
- 特点：各元素和数据项不必存储在连续的内存中，动态分配内存，只需考虑逻辑上的顺序即可
- 优缺点
- 优点：擅长做增加和删除
- 缺点
- 程序结束前必须释放分配的内存空间，否则会造成内存泄漏，
- 程序运行性能较低（所需内存要在程序执行时才能分配）
- 有可能应为指向动态内存分配空间的指针在未释放该空间时又指向其他内存空间，导致原来指向的空间无法被释放，造成内存泄漏。
- 单向链表
- 组成：
- 数据字段
- 指针
- 特点：
- 第一个节点是“链表 头指针”，指向最后一个节点的指针设为null，链表尾
- 所有节点都知道节点本身的下一个节点在哪，但不知道上一个节点，要查找前一个节点，必须从头指针开始，遍历链表。
- Java中没有指针类型，可声明链表为类如
//模拟链表节点
class node
{
int data;
Node next;
public Node(int data) //声明节点的构造函数
{
this.data = data;
this.next = null;
}
}
//声明链表类
class LinkedList
{
private Node first;
private Node last;
//定义类的方法
}
- 组成：
- 栈
- 运算受限的元素，仅允许在表的一端进行插入和删除
- 先进后出
- 底层可以用数组存，也可以用链表
- 队列
- 特殊线性表，只允许在表后端进行插入，在前端删除
- 分类：
- 单向队列：先进先出FIFO，只能从队尾插入数据，从队头删数据
- 双向队列：可从两端插删数据
- 数组Array
- 非线性数据结构（如哈希表、树和图等）
- 哈希表
- 元素的值和索引存在对应关系//按照hash函数将元素的键索引到桶中索引位置，每个桶又是一个链表头节点
- 优点：存查性能高//根据元素hashcode之际计算出元素存储位置
- 树
- 优点：适合范围查找，一般做索引
- 分类：
- 二叉树
- 满二叉树
- 完全二叉树
- 二叉搜索树
- 平衡二叉树
- 多叉树
- 二叉搜索树
- 红黑树
- 平衡树
- B树
- 堆
- Tried树
- 二叉树
- 图
- 无向图
- 有向图
- 无权图
- 带权图
- 稠密图
- 稀疏图
- 连通图
- 强连通图
- 无环图
- 有环图
- 完全图
- 哈希表
338 次浏览