线性表

线性表是具有n个 数据元素 的有限序列(n>0)

循环队列

假设A[]存放循环队列的元素 其头尾指针分别为front和rear则队列中的元素个数为(rear-front+m )%m

入队操作:

循环队列存储数组A[] 入队时候的操作为 rear = (rear +1) mod(m+1)

稀疏矩阵压缩存储方法

三元顺序表

当计算所需字节数的时候

别忘记上 第0行的 三个字节

例题:

快速转置法

广义表

取Tail操作

取表头操作:

只有单个元素的表头 取操作

第六章 树和二叉树

一些基本概念

结点的度 ： 结点所连孩子的数量

• 树的度 : 一棵树中最大的结点度数
• 树的深度 : 树中结点的最大层数

二叉树

二叉树不是树的特殊情况,他们是不同的概念

二叉树的性质:

• 性质1 ： 在二叉树第i层上 最多有2^(i-1)结点(画一个短的二叉树就可以发现了)
• 性质2 : 深度为k的二叉树至多有2^k - 1 个结点
• 性质3 : 对任何一棵二叉树T ， 其终端结点数为n[0] 度为2的结点数为 n[2] ,则n[0] = n[2]+1

满二叉树

满结点的二叉树 为 满二叉树

是 完全二叉树 的特例

完全二叉树

特点;

所有的叶节点 都出现在第K层或K-1层

• 性质4: 具有n个结点的完全二叉树的深度为 [log2|n] +1
  
  答案: 501

存储结构

顺序存储结构

就和 树状数组一样

链式存储结构

二叉链表(左右孩子)

三叉链表(左右孩子双亲)
线索链表

遍历二叉树

• 投影法求前中后遍历

• 层次遍历

二叉树求表达式

由结点线序遍历和中序遍历 构造对应的二叉树

按先序遍历序列建立二叉树

树和森林

树的存储方式

1.双亲表示法

2.孩子表示法

3.孩子兄弟表示法

二叉树和树的转换

树转换成二叉树

树转换成二叉树 反过来即可

左孩子代表 是孩子结点
右孩子代表 是兄弟结点

森林转换成二叉树
先将森林转换成二叉树
森林转换成二叉树 反过来即可

然后以第一个二叉树为根节点直接拼接上即可

树的遍历

先根遍历:
先访问根节点在访问子树

后根遍历:
先访问子树再访问根节点

Huffman树

• 计算wpl

• 构建Huffman树

树的习题

图

一些概念:

连通分量
非连通图的极大连通子图

含有n个结点的有向完全图 边数为:
n*(n-1)
有向图则是 /2

邻接多重表 用于表示 无向图
十字链表 用于 存储表示 有向图

遍历图(DFS,BFS)

最小生成树

prim算法

Kruskal算法

排序 --> 放

拓扑排序

记录入度 入度为0 继续while

关键路径(最长路径)

最短路径

查找

顺序查找

折半查找法

分块查找法

分块最好是分成 √n

动态查找表

二叉排序树

构建 小的放左 大的放右

删除操作

如果有只有一个孩子 直接把孩子拿上来即可

如果有两个孩子 那么比较一下 放着即可

ASL
当前层数 * 结点个数 / 结点总数

平衡二叉树

ASL 是 log 级别的

左旋右旋

动态查找表

哈希表

• 除留余数法

处理冲突

• 链地址法
  

内部排序

直接插入排序

将数一个一个插入到表中

每次插入都需要判断插前 or 插后

折半插入排序

就是利用 二分让他找的更快而已

希尔排序(缩小增量法)

每次将距离为d的分组 然后对组内排序

依次缩小d 最后合并

快速排序

选择关键字 然后将大于他的放左边 小于他的放右边

最后在对后面的区间进行同样的操作即可

堆排序(最坏情况下 Onlogn)

• 如何由一个无序序列建成一个堆

• 如何在输出堆顶元素之后调整剩余元素使之成为一个新的堆

取ans
将堆顶元素和末尾元素交换 堆顶元素弹出

现在的栈顶元素 和 左右子树较小的根结点互换 一路下取即可

建堆
以序列第一个元素为根建立二叉树,如果当前元素大于根结点则放左边,否则放右边

然后我们从n/2 -> 1 个结点 处理 将当前结点进行交换处理 如果比自己小那么我们就交换

二路归并:(nlogn 稳定的排序算法)

也是分组然后合并

结论:

直接插入排序最快
在基本有序或n值较小的情况下

简答排序是稳定的

直接插入排序

折半插入排序

冒泡排序

简单选择排序

杂项

顺序存储方式 并不仅仅用于 存储线性结构
(用数组来存树形结构(非线性))