数据结构
2016-12-31 11:50:11 0 举报AI智能生成
数据结构最全知识点
作者其他创作
大纲/内容
二、线性结构
一般线性表
定义（4个唯一）
顺序表
特性
存储结构定义
3个域的结构体
算法
插入
平均移动n/2个元素
删除
平均移动n-1/2个元素
查找（方便）
随机存取（与表长度无关）
时间复杂度O（1）
链表
单链表
查找
T（n）=O（n）
插入（方便）
告诉位置O（1）、不告诉位置O（n）
删除（方便）
静态链表（不要求代码）
循环链表
尾指针指向头指针
什么时候终止
什么时候为空
终止条件不同
双向链表
插入、删除语句
多种存储结构的比较
栈和队列（操作受限）
栈
定义
后进先出
仅在表尾进行插入或删除
存储结构
顺序栈
顺序栈： 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置。
链栈
应用
表达式求值（了解）
递归（二叉树用的多）
括号匹配（了解）
... ...
队列
队尾插入、队头删除
先进先出
链队列
入队、出队
循环队列（数组）
提出的意义
解决假溢出
队列为空的条件
队列为满的条件
出队
入队
队列长度
串（数据受限）
长度、相等、空串...
定长顺序存储
随机取子串方便
长度固定，地址连续
堆分配存储
空间动态分配，地址连续
块链存储
链表存储
优点：便于插入、删除
缺点：空间利用率低
模式匹配
朴素的模式匹配
KMP算法（太难）
数组和广义表
数组
矩阵的压缩存储（不考运算）
特殊矩阵
对称矩阵
无向图的邻接矩阵表示法
三角矩阵
对角矩阵
稀疏矩阵
三元组顺序存储
画出对应结构
行逻辑连接的顺序表
链式存储结构
十字链表（会画）
广义表
四个概念（表头、表尾、长度、深度）
三、非线性结构
树形结构
二叉树
5个性质
顺序存储
二叉链表
遍历（代码）递归
先序
中序
后序
层序
线索化
将空指针利用起来
左指针、右指针
树
树的存储
双亲表示法
孩子表示法
孩子兄弟表示法
相互转换
哈夫曼树
构造哈夫曼树
哈夫曼编码
左写0右写1
WPL计算
图形结构
邻接矩阵
无向图可以压缩存储
邻接表
出度、入度
十字链表
邻接多重表
图的遍历
深度优先遍历DFS
类似先序
广度优先遍历BFS
类似层序
最小生成树
拓扑排序
关键路径
最短路径
数据结构
一、绪论
基本概念
逻辑结构
时间复杂度
空间复杂度
四、算法
静态查找
顺序查找
折半查找
索引查找（分块查找）
动态查找
二叉排序树
建树、查找、插入、删除
平衡二叉树
B树
哈希表
哈希造表
会造、会查
冲突处理
查找ASL
排序（九种）过程、结论
插入排序
直接插入排序
折半插入排序
希尔排序
交换排序
起泡排序
快速排序
选择排序
简单选择排序
堆排序
归并排序
2路归并排序
基数排序（多关键字）
链式基数排序
职业：学生
0 条评论
回复 删除
下一页
