数据结构知识点简结-记忆所用

一、概述

1. 数据

2. 数据元素

3. 数据项：

(1). 初等项
(2). 组合项

4. 数据对象(数据元素类)

5. 数据结构：相互之间存在一种或多种关系的数据元素的集合。

6. 数据的逻辑结构：

(1). 线性结构-其余也叫非线性结构
(2). 树型结构
(3). 图型结构
(4). 集合

7. 数据的存储结构:

(1). 顺序存储
(2). 链式存储
(3). 索引存储：稀疏索引、稠密索引
(4). 散列存储

8. 注：

(1). 不同的逻辑结构和不同的存储结构形成不同的数据结构。
(2). 不同的操作限制也形成不同的数据结构。

二、算法简介

1. 算法的五个特性

(1). 输入
(2). 输出
(3). 有穷
(4). 确定
(5). 可行

2. 算法设计的要求

(1). 正确
(2). 健壮
(3). 可读
(4). 可拓展
(5). 高效

3. 常见时间复杂度

常数阶O(1)，对数阶O(logn)，线性阶O(N)，n*logn阶O(nlogn)，平方阶O(n²)，立方阶O(n³)，指数阶O(2ⁿ)，阶乘，幂阶

4. 常用算法设计方法

蛮力法、减治法、分治法、动态规划、贪心算法、回溯法、分支界限

三、线性表

是n个数据元素的有限序列。

1. 顺序表

线性表的顺序存储是指用连续的地址空间顺序存储元素，称为顺序表。

2. 链表

线性表的元素用离散的存储空间存放，称为链表。
链表一般由头指针，数据域，指针域组成。
(1). 单链表
(2). 单向循环链表
(3). 双向链表
(4). 双向循环链表

3. 顺序表和链表的区别

(1). 顺序表的存储空间可动可静、链表是动态的。
(2). 顺序表支持随机，顺序访问、链表只能顺序访问。
(3). 顺序表修改效率高，链表存取效率低。
(4). 顺序表删除/插入平均移动一半元素、而链表则不需移动。
(5). 存储密度：顺序表 = 1，链表 < 1。

四、栈和队列

A. 栈

限定在一端进行插入/删除操作的线性表，具有先进后出的特征。

1. 顺序栈

(1). 静态、动态

2. 链栈

(1). 一般采用在链头进行插入删除。只需要操作头指针即可。
(2). 动态，空间可扩充。

B. 队列

只允许在一端入队，另一端出队的受限的线性表。具有先进先出的特征。