数据结构期末考前救急

1.模式匹配

数几个字母 画表格 下面这些都是固定的

下面开始求

相等就写前面的那个的nextval 不相等就写自己的next值

2.画二叉树

线索

3.求叶子结点

n0就是叶子结点

4.建立二叉排序树

(1) 大的在右边 小的在左边

（2） 查找54就看他在第几层

100 比较了几层

（3）层的值*该层结点个数 求和 再除以结点个数

再学习一些查找不成功的

5.广义表

• 第一种类型

表头是第一个逗号前面，如果有括号就带括号

表尾第一个逗号后面所有内容 最外层加个括号

长度看逗号分成了几部分 分几部分长度就是几 注意括号里面的逗号不管

深度看括号最多的 最外层括号也算

• 第二种类型

1是代表广义表 0代表原子

6.求存储地址

=首地址+（i-1）*n+（j-1）*k

i 是1 j是2 n是列 k是元素长度

7.代码设计

8.哈夫曼树

从小到大排序 找两个最小的 用两者和代替 两个数 接着重复

编码 ABCDEFG对应顺序7 19 ...顺着来

右是1 左是0

9.最小生成树

• 普里姆算法

一直找最小的 不能构成环形

边数=结点数-1

• 克鲁斯卡尔算法

找边 从最小开始

不能形成环路

10.深度遍历 广度遍历 邻接表

（1）一行一行看 不是无穷就代表有边 画过的就不用管了

无向图直接看对角线上面的就行

如果图是上面那种情况 1->2 2没有路了就再退回到1 找路

（2）深度 找连接1的一个点 随便写1个

广度 找连接1的多个点 都写上

11.哈希表

• 线性探测法

下标 从0开始

关键字 每个关键码对n取余 是几写到几下面 如果已经有了 就往后挪一个 探测次数+1 挪两个 探测次数+2

探测次数

成功概率 = 探测次数和/关键码个数

• 链地址法

竖着画n个头结点 从0开始

然后还是 每个关键码对n取余 是几就在几后面链接上该关键码 如果已经有了 就用头插法插到以前关键码前面

成功概率 =（看每列元素个数 * 该列序号）/关键码个数

12.排序

• 快速排序

拿出第一个来 依次比较 空作为分隔线

• 希尔排序

1.d=n/2

从前数d个数 后面的数按序列分组 分为 d组 比较每组 谁小谁放前面

2.排完之后 再求d 用上次的d/2

方法一样 继续排

3.直到d=1 就不用分组了 直接一整个按从小到大的顺序排

• 堆排序

需要在草稿纸上画过程

按顺序来

上面是第一次排好后写出初始序列（可以不用写）

然后把最大的数89拿走 放到序列最后不动

把最后一个叶子结点45 拿到顶部作根 然后再进行一次排序

在写出排好的数

然后再把最大的58拿到 放序列最后 （注意89不动） 然后重复操作 剩余一个结点就不用再排了

共需要10趟排序 得出结果