数据结构
2019-04-20 13:52:57 0 举报AI智能生成
数据结构与算法脑图
作者其他创作
大纲/内容
基本概念
数据
概念：数据是信息的载体，是数、字符、符号的集合。
基本单位：数据元素
最小单位：数据项
数据类型
概念：数据类型是一个值的集合和定义在集合上一组操作的总称
原子类型
值可再分
结构类型
值不可再分
ADT：抽象数据类型
三元组
数据对象
数据关系
基本操作机
数据结构
概念：数据结构是互相之间存在一种或多种的特定关系的数据元素的集合
三要素
逻辑结构
概念：逻辑结构是数据元素之间的逻辑关系，独立于计算机之外
线性
一对一
一般线性表
栈和队列
数组
广义表
非线性
一对多
树
一般树
二叉树
多对多
图
无向图
有向图
存储（物理）结构
概念：存储结构是指数据结构在计算机中的表示
顺序存储
链接存储
散列（hash）存储
索引存储
数据的运算
算法
概念：特定问题的求解步骤，是指令的有限序列
五个特性
确定性
有穷性
可行性
输入
输出
四个评价标准
正确
可读性
健壮性
效率与低存储量需求
时空复杂度
时间复杂度
算法中所有语句被重复执行的次数（频度）之和的数量级
空间复杂度
算法所耗费的存储空间的数量级
原地工作指算法所需要的辅助空间是常量，即O(1)
线性结构（线性表）
概念：线性表是具有相同数据类型的n个数据元素的有限序列。
顺序表
基本操作
插入
移动次数n/2
删除
移动次数(n-1)/2
查找
移动次数(n+1)/2
定义
数组可看做顺序表的推广。
一维数组可看做顺序表。
二维数组可看做元素为顺序表的顺序表。
一维数组可看做顺序表。
二维数组可看做元素为顺序表的顺序表。
链表
单链表
双向链表
线性表的应用
栈
队列
树形结构
树的概念
树、二叉树、森林
树的遍历
先序
中序
后序
层次
树的应用
二叉排序树
平衡二叉树
哈夫曼树
图结构
图的基本概念
图的存储
图的遍历
广度优先
深度优先
图的应用
最小生成树
最短路径
拓扑排序
关键路径
查找
线性结构
顺序查找
折半查找
分块查找
非线性结构
二叉排序树
平衡二叉树
散列查找
构造散列函数
直接定址
除留余数法
······
冲突处理
开放定址法（公式？）
线性探测
平方探测法
再散列
伪随机数
拉链法
性能分析
散列函数
冲突处理方法
装填因子
B树
重要计算
ASL（成功、失败）
子主题
排序
交换排序
冒泡排序
两两比较后进行交换
快速排序
递归划分两部分进行交换排序
时间复杂度
nlogn
快些（希）归队
空间复杂度
稳定性
不稳定
快些（希）选堆
一次遍历能确定一个元素正确位置
所有的交换排序
堆排序
0 条评论
下一页
