歸并排序      摘要: 歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法。
　　申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
　　設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
　　比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
　　重復(fù)步驟3直到某一指針達(dá)到序列尾   閱讀全文

B-樹(shù)及B＋樹(shù)      摘要: 1、B樹(shù)的定義
B樹(shù)是一種平衡的多分樹(shù)，通常我們說(shuō)m階的B樹(shù)，它必須滿足如下條件：
（1）每個(gè)結(jié)點(diǎn)至多有m個(gè)子結(jié)點(diǎn)；
（2）除根結(jié)點(diǎn)和葉結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有個(gè)子結(jié)點(diǎn)；
（3）若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩個(gè)子結(jié)點(diǎn)；
（4）所有的葉結(jié)點(diǎn)在同一層；
（5）有k個(gè)子結(jié)點(diǎn)的非根結(jié)點(diǎn)恰好包含k-1個(gè)關(guān)鍵碼。
  閱讀全文

平衡二叉樹(shù) （AVL樹(shù)）      摘要: 　在構(gòu)造二叉排序樹(shù)的過(guò)程中，每當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí)，首先檢查是否因插入而破壞了樹(shù)的平衡性，如果是因插入結(jié)點(diǎn)而破壞了樹(shù)的平衡性，則找出其中最小不平衡子樹(shù)，在保持排序樹(shù)特性的前提下，調(diào)整最小不平衡子樹(shù)中各結(jié)點(diǎn)之間的連接關(guān)系，以達(dá)到新的平衡。通常將這樣得到的平衡二叉排序樹(shù)簡(jiǎn)稱為 AVL 樹(shù)。
那么什么是 最小不平衡子樹(shù)
　　以離插入結(jié)點(diǎn)最近、且平衡因子絕對(duì)值大于 1 的結(jié)點(diǎn)作根結(jié)點(diǎn)的子樹(shù)。為了簡(jiǎn)化討論，不妨假設(shè)二叉排序樹(shù)的最小不平衡子樹(shù)的根結(jié)點(diǎn)為 A ，則調(diào)整該子樹(shù)的規(guī)律可歸納為下列四種情況：
  閱讀全文

各種查找算法的實(shí)現(xiàn)

二叉搜索樹(shù)（二叉排序樹(shù)）（二叉查找樹(shù)）      摘要: 1、二叉搜索樹(shù)是二叉樹(shù)的一種，樹(shù)的每個(gè)結(jié)點(diǎn)含有一個(gè)數(shù)據(jù)項(xiàng)，每個(gè)數(shù)據(jù)項(xiàng)有一個(gè)鍵值。結(jié)點(diǎn)的存儲(chǔ)位置是由鍵值的大小決定的，所以二叉搜索樹(shù)是關(guān)聯(lián)式容器。
(1)、 若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的鍵值均小于它的根結(jié)點(diǎn)的鍵值；
(2)、若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的鍵值均大于它的根結(jié)點(diǎn)的鍵值；
(3)、它的左、右子樹(shù)也分別為二叉排序樹(shù)。
注意：：：二叉排序樹(shù)是一種動(dòng)態(tài)樹(shù)表，樹(shù)的結(jié)構(gòu)通常不是一次生成的。而是在查找的過(guò)程中，當(dāng)樹(shù)中不存在關(guān)鍵字等于給定值的節(jié)點(diǎn)時(shí)再進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。
  閱讀全文

哈夫曼樹(shù)      摘要: 哈夫曼樹(shù)定義為：給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱為哈夫曼樹(shù)(Huffman tree)。
1、那么什么是權(quán)值？什么是路徑長(zhǎng)度？什么是帶權(quán)路徑長(zhǎng)度呢？
權(quán)值：哈夫曼樹(shù)的權(quán)值是自己定義的，他的物理意義表示數(shù)據(jù)出現(xiàn)的次數(shù)、頻率?？梢杂脴?shù)的每個(gè)結(jié)點(diǎn)數(shù)據(jù)域data存放一個(gè)特定的數(shù)表示它的值。

路徑長(zhǎng)度：在一棵樹(shù)中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長(zhǎng)度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)-1。

結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。 樹(shù)中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，WPL=sigma(w*l)

  閱讀全文

優(yōu)先隊(duì)列      摘要: 優(yōu)先隊(duì)列是不同于先進(jìn)先出隊(duì)列的另一種隊(duì)列。每次從隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素。每個(gè)元素都有一個(gè)優(yōu)先權(quán)或值
/////用堆實(shí)現(xiàn)優(yōu)先隊(duì)列
1、把優(yōu)先隊(duì)列中的元素按優(yōu)先級(jí)大小組織成堆，堆頂元素具有最大優(yōu)先級(jí)。
2、優(yōu)先隊(duì)列的插入與刪除可以用堆的插入與刪除實(shí)現(xiàn)。
3、優(yōu)先隊(duì)列在定義為priority_queue ，在STL中#include 中實(shí)現(xiàn)、
priority_queue, greater >qi2;
其中

  閱讀全文

posted @ 2011-10-02 11:22 Yu_ 閱讀(265) | 評(píng)論 (0)  編輯

堆排序      摘要: 估計(jì)還要問(wèn)問(wèn)：什么是堆，什么是堆排序？堆與計(jì)算機(jī)分配內(nèi)存的堆相同嗎？
很多資料給出：堆的定義是
（1）、n個(gè)關(guān)鍵字序列（Kl，K2，…，Kn）稱為(Heap)，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)(簡(jiǎn)稱為堆性質(zhì))：
ki≤K2i且ki≤K2i+1 或 Ki≥K2i且ki≥K2i+1 (1≤i≤ n) //ki相當(dāng)于二叉樹(shù)的非葉結(jié)點(diǎn)，K2i則是左孩子，k2i+1是右孩子

  閱讀全文