1.模式匹配

數(shù)幾個字母 畫表格 下面這些都是固定的

下面開始求

相等就寫前面的那個的nextval 不相等就寫自己的next值

2.畫二叉樹

線索

3.求葉子結(jié)點

n0就是葉子結(jié)點

4.建立二叉排序樹

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

（2） 查找54就看他在第幾層

100 比較了幾層

（3）層的值*該層結(jié)點個數(shù) 求和 再除以結(jié)點個數(shù)

再學(xué)習(xí)一些查找不成功的

5.廣義表

• 第一種類型

表頭是第一個逗號前面，如果有括號就帶括號

表尾第一個逗號后面所有內(nèi)容 最外層加個括號

長度看逗號分成了幾部分 分幾部分長度就是幾 注意括號里面的逗號不管

深度看括號最多的 最外層括號也算

• 第二種類型

1是代表廣義表 0代表原子

6.求存儲地址

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

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

7.代碼設(shè)計

8.哈夫曼樹

從小到大排序 找兩個最小的 用兩者和代替 兩個數(shù) 接著重復(fù)

編碼 ABCDEFG對應(yīng)順序7 19 ...順著來

右是1 左是0

9.最小生成樹

• 普里姆算法

一直找最小的 不能構(gòu)成環(huán)形

邊數(shù)=結(jié)點數(shù)-1

• 克魯斯卡爾算法

找邊 從最小開始

不能形成環(huán)路

10.深度遍歷 廣度遍歷 鄰接表

（1）一行一行看 不是無窮就代表有邊 畫過的就不用管了

無向圖直接看對角線上面的就行

如果圖是上面那種情況 1->2 2沒有路了就再退回到1 找路

（2）深度 找連接1的一個點 隨便寫1個

廣度 找連接1的多個點 都寫上

11.哈希表

• 線性探測法

下標(biāo) 從0開始

關(guān)鍵字 每個關(guān)鍵碼對n取余 是幾寫到幾下面 如果已經(jīng)有了 就往后挪一個 探測次數(shù)+1 挪兩個 探測次數(shù)+2

探測次數(shù)

成功概率 = 探測次數(shù)和/關(guān)鍵碼個數(shù)

• 鏈地址法

豎著畫n個頭結(jié)點 從0開始

然后還是 每個關(guān)鍵碼對n取余 是幾就在幾后面鏈接上該關(guān)鍵碼 如果已經(jīng)有了 就用頭插法插到以前關(guān)鍵碼前面

成功概率 =（看每列元素個數(shù) * 該列序號）/關(guān)鍵碼個數(shù)

12.排序

• 快速排序

拿出第一個來 依次比較 空作為分隔線

• 希爾排序

1.d=n/2

從前數(shù)d個數(shù) 后面的數(shù)按序列分組 分為 d組 比較每組 誰小誰放前面

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

方法一樣 繼續(xù)排

3.直到d=1 就不用分組了 直接一整個按從小到大的順序排

• 堆排序

需要在草稿紙上畫過程

按順序來

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

然后把最大的數(shù)89拿走 放到序列最后不動

把最后一個葉子結(jié)點45 拿到頂部作根 然后再進(jìn)行一次排序

在寫出排好的數(shù)

然后再把最大的58拿到 放序列最后 （注意89不動） 然后重復(fù)操作 剩余一個結(jié)點就不用再排了

共需要10趟排序 得出結(jié)果