006.1 数据结构
2016-10-31 14:02:43 23 举报AI智能生成
数据结构
作者其他创作
大纲/内容
数据结构实现基础
数组（Array）
对象（Object）
基本数据结构
线性表（list）
线性表的顺序存储结构
数组（Array）
线性表的链式存储结构
单链表（linked list）
链表的反转
原地法
栈法
递归法
单循环法
循环链表（circular linked list）
双向链表（double linked list）
双向循环链表（double circular linked list）
多重链表
十字链表
队列（queue）
栈（stack）
集合（Set）
串（String）
字典（Dictionary）
散列表（Hash）
散列函数的构造方法
直接定址法
数字分析法
平方取中法
折叠法
除留余数法
随机数法
散列冲突的处理方法
开放定址法
线性探测法
二次探测法
随机探测法
再散列函数法
链地址法
公共溢出区法
散列表查找性能分析
散列函数是否均匀
处理冲突的方法
散列表的装填因子
树（Tree）
术语
树的特性
节点
度（degree）
层次（level）
节点类别
根节点
内部节点
叶节点或终端节点
节点间关系
双亲（parent）
孩子（child）
兄弟（sibling）
度（degree）
深度（depth）
森林（forest）
树的存储结构
双亲表示法
孩子表示法
孩子兄弟表示法
多重链表表示法
树的分类
有序数
二叉树
常用性质
一棵二叉树第 i 层的最大结点数为 2^( i-1), i>1
深度为 k 的二叉树有最大节点数 2^k - 1, k>1（等比数列求和：s = (a1 - an*q) / (1- q), q != 1）
对于任何非空的二叉树 T，若 n0 表示叶节点的个数， n2 表示度为 2 的非叶结点个数，那么两者满足关系 n0 = n2 + 1（结点总数 n = n0 + n1 + n2 = B + 1 = n1 + 2*n2 + 1，B 为边的数量）
二叉树的存储结构
顺序存储
链表存储
二叉树的种类
结构分类
完美二叉树（prefect binary tree）
第 4 层的最大结点数为 2^( 4-1) = 8
最大节点数 2^4 - 1 = 15
n0 = 8, n1 = 0, n2 = 7
n0 + n1 + n2 = n1 + 2*n2 + 1; n0 = n2 + 1
n0 + n1 + n2 = n1 + 2*n2 + 1; n0 = n2 + 1
完全二叉树（complete binary tree）
完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。
完美(Perfect)二叉树 VS 完全(Complete)二叉树
将上图中的编号为 15, 14, 13, 12, 11 叶子结点都拿掉(从右到左的顺序)
上图就不是一棵完全(Complete)二叉树
完满二叉树(Full Binary Tree)
所有非叶子结点的度都是2（只要你有孩子，你就必然是有两个孩子）
完满(Full)二叉树 VS 完全(Complete)二叉树 VS 完美(Perfect)二叉树
斜二叉树（skewed binary tree）
平衡二叉树（balanced binary tree）也称 AVL 树
节点序列分类
二叉搜索树（binary search tree）也称二叉排序树或二叉查找树
性质
节点 N 左子树上的所有节点的值都小于等于节点 N 的值
节点 N 右子树上的所有节点的值都大于等于节点 N 的值
左子树和右子树也都是 BST
操作
遍历
中序遍历
得到从小到大顺序的序列
操作
插入
查找
删除
遍历
先序遍历
10,5,4,8,19,13,24
中序遍历
4,5,8,10,13,19,24
后续遍历
4,8,5,13,24,19,10
层序遍历
10,5,19,4,8,13,24
霍夫曼树
无序树（自由树）
堆（Heap），也称优先队列（priority queue）
最小堆（minHeap）
最大堆（maxHeap）
图（Graph）
图的存储结构
邻接矩阵
邻接表
操作
深度优先搜索(dfs)：假设初始状态是图中所有顶点均未被访问，则从某个顶点 v 出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和 v 有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
A -> C -> B -> D -> F -> G -> E
广度优先搜索(bfs)：从图中某顶点 v 出发，在访问了 v 之后依次访问 v 的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
A -> C -> D -> F -> B -> G -> E
0 条评论
下一页
