歸并排序      摘要: 歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法。
　　申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
　　設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
　　比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
　　重復步驟3直到某一指針達到序列尾   閱讀全文

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

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

各種查找算法的實現

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

哈夫曼樹      摘要: 哈夫曼樹定義為：給定n個權值作為n個葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman tree)。
1、那么什么是權值？什么是路徑長度？什么是帶權路徑長度呢？
權值：哈夫曼樹的權值是自己定義的，他的物理意義表示數據出現的次數、頻率。可以用樹的每個結點數據域data存放一個特定的數表示它的值。

路徑長度：在一棵樹中，從一個結點往下可以達到的孩子或子孫結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1。

結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。 樹中所有葉子節點的帶權路徑長度之和，WPL=sigma(w*l)

  閱讀全文

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

  閱讀全文

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

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

  閱讀全文