KISS(Keep It Simple, Standard)

這步還有句要說的就是：（在把ＯＰＥＮ表中最優值的節點插入　ＣＬＯＳＥ表中時如果在ＣＬＯＳＥ表中已經存在那就要比較，如果存在的節點的權值比要插入的大，就要把存在的替換掉（節點中所有內容），否則就忽略）．

第３步：就是重復第２步驟（示例圖如下）

我想因該明白了吧！










好了最后一張完工！

終點（12節點）找到了是吧！我想因該明白了吧！

最近做了路徑搜索,看了網上的描述真是晦澀,所以自己就整理下!
圖畫的不太好, :)
綠色的是節點,紅色的為權值,箭頭為可通行的標志.

現在我們要從 0 節點 到 12 節點 找一條最優路徑:
首先咱們要解決NODE點存貯的信息(結構):
struct NodeBaseInfo
{
   unsigned short nNodeID;　　　//番號
   unsigned long  nMeasure;            //權值
   NodeBaseInfo *pParent;            //父節點
};

我寫了簡單的結構大家可以根據自己需要定義（定義這個結構是為了更好理解）
下面講的是最主要的了：
DIJKSTAR算法中要定義兩個表：OPEN 和 CLOSE  （其實可以看作鏈表）
他的原理就是把沒有遍歷的點放在 OPEN 表中，把從 OPEN表中遍歷到的最短權值的點放入
CLOSE 表中，當插入 CLOSE表中的節點的番號于我們要的重點時算法結束；然后按照父節點（pParent）
向上遞歸就可以得到我們要的最優路徑了。

第一步：應為 OPEN 和CLOSE表都是空的，把起點（0節點）插入CLOSE標中，它的權值為0。把起點（0節點）附近的節點（因該為可通行的）插入OPEN 表中（最好按權值從大道小的順序插入，這樣取得最優值時，這樣速度就會很快）。（如示例圖）

第2步：從OPEN表中找到權值最小的節點，把它插入CLOSE 表中, 把這個節點的可連通的節點查入ＯＰＥＮ
表，（如果ＯＰＥＮ表中存在要查入的點，如果要插入的節點的權值比已經存在的小，就把已經查入的權值該為最小的，如果要插入的節點的權值比已經存在的大，就忽落它．）
（為了更好的理解我把父節點也加入了，如示例圖）

本算法只采用移位、加減法、判斷和循環實現，因為它不需要浮點運算，也不需要乘除運算，因此可以很方便地運用到各種芯片上去。

我們先來看看10進制下是如何手工計算開方的。
先看下面兩個算式，
x = 10*p + q  (1)
公式(1)左右平方之后得：
x^2 = 100*p^2 + 20pq + q^2 (2)
現在假設我們知道x^2和p，希望求出q來，求出了q也就求出了x^2的開方x了。
我們把公式(2)改寫為如下格式：
q = (x^2 - 100*p^2)/(20*p+q) (3)

這個算式左右都有q，因此無法直接計算出q來，因此手工的開方算法和手工除法算法一樣有一步需要猜值。

我們來一個手工計算的例子：計算1234567890的開方

首先我們把這個數兩位兩位一組分開，計算出最高位為3。也就是(3)中的p，最下面一行的334為余數，也就是公式(3)中的(x^2 - 100*p^2)近似值
    3
  ---------------
 / 12 34 56 78 90
    9
  ---------------
 /  3 34

下面我們要找到一個0-9的數q使它最接近滿足公式(3)。我們先把p乘以20寫在334左邊：
                           3  q
                         ---------------
                        / 12 34 56 78 90
                           9
                         ---------------
(20*3+q)*q      /  3 34

我們看到q為5時(60+q)*q的值最接近334，而且不超過334。于是我們得到：
      3  5
    ---------------
   / 12 34 56 78 90
      9
    ---------------
65 /  3 34
      3 25
    ---------------
         9 56

接下來就是重復上面的步驟了，這里就不再啰嗦了。

這個手工算法其實和10進制關系不大，因此我們可以很容易的把它改為二進制，改為二進制之后，公式(3)就變成了：
q = (x^2 - 4*p^2)/(4*p+q) (4)

我們來看一個例子，計算100(二進制1100100)的開方：
       1  0  1  0
      -----------
     / 1 10 01 00
       1
      -----------
 100 / 0 10
       0 00
      -----------
1001 /   10 01
         10 01
      -----------
          0 00

這里每一步不再是把p乘以20了，而是把p乘以4，也就是把p右移兩位，而由于q的值只能為0或者1，所以我們只需要判斷余數(x^2 - 4*p^2)和(4*p+1)的大小關系，如果余數大于等于(4*p+q)那么該上一個1，否則該上一個0。

下面給出完成的C語言程序，其中root表示p，rem表示每步計算之后的余數，divisor表示(4*p+1)，通過a>>30取a的最高 2位，通過a<<=2將計算后的最高2位剔除。其中root的兩次<<1相當于4*p。程序完全是按照手工計算改寫的，應該不難理解。
unsigned short sqrt(unsigned long a){
  unsigned long rem = 0;
  unsigned long root = 0;
  unsigned long divisor = 0;
  for(int i=0; i<16; ++i){
    root <<= 1;
    rem = ((rem << 2) + (a >> 30));
    a <<= 2;
    divisor = (root<<1) + 1;
    if(divisor <= rem){
      rem -= divisor;
      root++;
    }
  }
  return (unsigned short)(root);
}

void TransparentBlt(CDC *pDestDC, int nXDest, int nYDest, int nWidth, int nHeight, CBitmap * pBitmap, int nXsrc, int nYsrc, COLORREF clr)
{
 CDC maskDC, ImageDC;
 maskDC.CreateCompatibleDC(pDestDC);
 ImageDC.CreateCompatibleDC(pDestDC);

 CBitmap maskBMP;
 maskBMP.CreateBitmap(nWidth, nHeight, 1, 1, NULL);//創建單色掩碼位圖
 CBitmap *pOldBMP = ImageDC.SelectObject(pBitmap);
 CBitmap *maskOldBMP = maskDC.SelectObject(&maskBMP);
 
 ImageDC.SetBkColor(clr);// 設置透明色
 maskDC.BitBlt(0, 0, nWidth, nHeight, &ImageDC, nXsrc, nYsrc, SRCCOPY);

 //設置背景色為黑色，前景色為白色，將掩碼位圖與原位圖相"與"
 ImageDC.SetBkColor(RGB(0, 0, 0));
 ImageDC.SetTextColor(RGB(255, 255, 255));
 ImageDC.BitBlt(0, 0, nWidth, nHeight, &maskDC, nXsrc, nYsrc, SRCAND);

 //設置背景色為白色，前景色為黑色，將掩碼位圖與背景進行“與”運算
 pDestDC->SetBkColor(RGB(255, 255, 255));
 pDestDC->SetTextColor(RGB(0, 0, 0));
 pDestDC->BitBlt(nXDest, nYDest, nWidth, nHeight, &maskDC, nXsrc, nYsrc, SRCAND);
 // "或"運算,生成最終效果
 pDestDC->BitBlt(nXDest, nYDest, nWidth, nHeight, &ImageDC, nXsrc, nYsrc, SRCPAINT);

 if (pOldBMP) ImageDC.SelectObject(pOldBMP);
 ImageDC.DeleteDC();
 if (maskOldBMP) maskDC.SelectObject(maskOldBMP);
 maskDC.DeleteDC();
 if (maskBMP.m_hObject) maskBMP.DeleteObject();
}

我就不怎么解釋了!如不理解,請看我轉的(透明位圖的顯示中的(二、實現TransparentBlt函數)的原理),其他部分都就什么必要了!呵呵!

包含透明色的位圖的繪制方法有多種，最簡單的方法是調用現成的函數：TransparentBlt,也可以通過自己的代碼實現類似 TransparentBlt的功能，實現過程也有兩種形式，一種是事先做一張掩碼位圖，另一種是動態生成掩碼位圖。本文將介紹動態生成掩碼位圖繪制具有透明區域位圖的方法。

一、TransparentBlt 函數的使用

TransparentBlt 函數在Windows98/Windows2000以上版本運行，系統中需要包含 Msimg32.dll，使用時可以鏈接 Msimg32.lib。
Windows98下的TransparentBlt會產生資源泄漏，所以不建議在WIN98下使用該函數。
TransparentBlt函數原型如下:

BOOL TransparentBlt(
HDC hdcDest,      // 目標DC
int nXOriginDest,   // 目標X偏移
int nYOriginDest,   // 目標Y偏移
int nWidthDest,     // 目標寬度
int hHeightDest,    // 目標高度
HDC hdcSrc,         // 源DC
int nXOriginSrc,    // 源X起點
int nYOriginSrc,    // 源Y起點
int nWidthSrc,      // 源寬度
int nHeightSrc,     // 源高度
UINT crTransparent  // 透明色,COLORREF類型
);

使用示例:

CBitmap FootballBMP;
FootballBMP.LoadBitmap(IDB_FOOTBALLBMP);
CDC ImageDC;
ImageDC.CreateCompatibleDC(pDC);
CBitmap *pOldImageBMP = ImageDC.SelectObject(&FootballBMP);
TransparentBlt(pDC->m_hDC, 0, 0, 218, 199, ImageDC.m_hDC, 0, 0, 218, 199, RGB(0,0,0xff));
ImageDC.SelectObject(pOldImageBMP);

二、實現TransparentBlt函數

為了理解具有透明色位圖的繪制過程，我們來親手建立一個具有同TransparentBlt功能一致的實驗函數，稱之為TransparentBlt2。

實驗素材：有兩張位圖：bk.bmp是背景位圖，football.bmp包含透明區域，透明色為藍色RGB(0,0,0xff)
實驗目的：以bk.bmp為背景，將football.bmp繪制到背景中，形成如下的最終效果圖。

 

2.1 透明位圖繪制原理
假設football.bmp ->載入 HBITMAP hImageBMP -> 選入 HDC hImageDC

2.1.1 生成足球的單色掩碼位圖，透明區域為白色（全1），非透明區域為黑色（全0)

HBITMAP hMaskBMP = CreateBitmap(nWidthDest, nHeightDest, 1, 1, NULL); // 建立單色位圖
SetBkColor(hImageDC, RGB(0,0,0xff)); // 設置背景色為藍色
BitBlt(hMaskDC, 0, 0, nWidthDest, nHeightDest, hImageDC, 0, 0, SRCCOPY); // 拷貝到hMaskDC

這樣足球位圖中藍色區域在掩碼位圖中成了白色，其它區域為黑色，此時hMaskBMP 如下圖:
(圖一)

2.1.2 設置背景色為黑色，前景色為白色，將掩碼位圖(圖一)與足球位圖相"與"

SetBkColor(hImageDC, RGB(0,0,0));
SetTextColor(hImageDC, RGB(255,255,255));
BitBlt(hImageDC, 0, 0, nWidthDest, nHeightDest, hMaskDC, 0, 0, SRCAND);

這樣，掩碼位圖中背景色（黑色）的區域在hImageBMP中被保留，前景色（白色）的部分變為黑色。 此時hImageBMP 如下圖:
(圖二)

2.1.3 設置背景色為白色，前景色為黑色，將掩碼位圖(圖一)與背景進行“與”運算

SetBkColor(hdcDest,RGB(255,255,255));
SetTextColor(hdcDest,RGB(0,0,0));
BitBlt(hdcDest, nXOriginDest, nYOriginDest, nWidthDest, nHeightDest, hMaskDC, 0, 0, SRCAND);

掩碼中白色區域（數據與1相“與”結果不變）使背景保持不變，黑色區域變成黑色，此時背景顯示如下:
(圖三)

2.1.4 將hImageBMP(圖二)與背景(圖三)進行“或”運算

BitBlt(hdcDest, nXOriginDest, nYOriginDest, nWidthDest, nHeightDest, hImageDC, 0, 0, SRCPAINT);

這樣就將足球繪制到背景上了。

2.2 TransparentBlt2函數全部實現代碼

void TransparentBlt2( HDC hdcDest,      // 目標DC
int nXOriginDest,   // 目標X偏移
int nYOriginDest,   // 目標Y偏移
int nWidthDest,     // 目標寬度
int nHeightDest,    // 目標高度
HDC hdcSrc,         // 源DC
int nXOriginSrc,    // 源X起點
int nYOriginSrc,    // 源Y起點
int nWidthSrc,      // 源寬度
int nHeightSrc,     // 源高度
UINT crTransparent  // 透明色,COLORREF類型
)
{
HBITMAP hOldImageBMP, hImageBMP = CreateCompatibleBitmap(hdcDest, nWidthDest, nHeightDest);	// 創建兼容位圖
HBITMAP hOldMaskBMP, hMaskBMP = CreateBitmap(nWidthDest, nHeightDest, 1, 1, NULL);			// 創建單色掩碼位圖
HDC		hImageDC = CreateCompatibleDC(hdcDest);
HDC		hMaskDC = CreateCompatibleDC(hdcDest);
hOldImageBMP = (HBITMAP)SelectObject(hImageDC, hImageBMP);
hOldMaskBMP = (HBITMAP)SelectObject(hMaskDC, hMaskBMP);
// 將源DC中的位圖拷貝到臨時DC中
if (nWidthDest == nWidthSrc && nHeightDest == nHeightSrc)
BitBlt(hImageDC, 0, 0, nWidthDest, nHeightDest, hdcSrc, nXOriginSrc, nYOriginSrc, SRCCOPY);
else
StretchBlt(hImageDC, 0, 0, nWidthDest, nHeightDest,
hdcSrc, nXOriginSrc, nYOriginSrc, nWidthSrc, nHeightSrc, SRCCOPY);
// 設置透明色
SetBkColor(hImageDC, crTransparent);
// 生成透明區域為白色，其它區域為黑色的掩碼位圖
BitBlt(hMaskDC, 0, 0, nWidthDest, nHeightDest, hImageDC, 0, 0, SRCCOPY);
// 生成透明區域為黑色，其它區域保持不變的位圖
SetBkColor(hImageDC, RGB(0,0,0));
SetTextColor(hImageDC, RGB(255,255,255));
BitBlt(hImageDC, 0, 0, nWidthDest, nHeightDest, hMaskDC, 0, 0, SRCAND);
// 透明部分保持屏幕不變，其它部分變成黑色
SetBkColor(hdcDest,RGB(255,255,255));
SetTextColor(hdcDest,RGB(0,0,0));
BitBlt(hdcDest, nXOriginDest, nYOriginDest, nWidthDest, nHeightDest, hMaskDC, 0, 0, SRCAND);
// "或"運算,生成最終效果
BitBlt(hdcDest, nXOriginDest, nYOriginDest, nWidthDest, nHeightDest, hImageDC, 0, 0, SRCPAINT);
// 清理、恢復
SelectObject(hImageDC, hOldImageBMP);
DeleteDC(hImageDC);
SelectObject(hMaskDC, hOldMaskBMP);
DeleteDC(hMaskDC);
DeleteObject(hImageBMP);
DeleteObject(hMaskBMP);
}

2.3 TransparentBlt的另外一個版本:TransparentBltU

TransparentBltU是Christian Graus 在WinDEV發表的一個函數，功能與TransparentBlt一致，以下是全部實現代碼:

bool TransparentBltU(
HDC dcDest,         // handle to Dest DC
int nXOriginDest,   // x-coord of destination upper-left corner
int nYOriginDest,   // y-coord of destination upper-left corner
int nWidthDest,     // width of destination rectangle
int nHeightDest,    // height of destination rectangle
HDC dcSrc,          // handle to source DC
int nXOriginSrc,    // x-coord of source upper-left corner
int nYOriginSrc,    // y-coord of source upper-left corner
int nWidthSrc,      // width of source rectangle
int nHeightSrc,     // height of source rectangle
UINT crTransparent  // color to make transparent
)
{
if (nWidthDest < 1) return false;
if (nWidthSrc < 1) return false;
if (nHeightDest < 1) return false;
if (nHeightSrc < 1) return false;
HDC dc = CreateCompatibleDC(NULL);
HBITMAP bitmap = CreateBitmap(nWidthSrc, nHeightSrc, 1, GetDeviceCaps(dc,
BITSPIXEL), NULL);
if (bitmap == NULL)
{
DeleteDC(dc);
return false;
}
HBITMAP oldBitmap = (HBITMAP)SelectObject(dc, bitmap);
if (!BitBlt(dc, 0, 0, nWidthSrc, nHeightSrc, dcSrc, nXOriginSrc,
nYOriginSrc, SRCCOPY))
{
SelectObject(dc, oldBitmap);
DeleteObject(bitmap);
DeleteDC(dc);
return false;
}
HDC maskDC = CreateCompatibleDC(NULL);
HBITMAP maskBitmap = CreateBitmap(nWidthSrc, nHeightSrc, 1, 1, NULL);
if (maskBitmap == NULL)
{
SelectObject(dc, oldBitmap);
DeleteObject(bitmap);
DeleteDC(dc);
DeleteDC(maskDC);
return false;
}
HBITMAP oldMask =  (HBITMAP)SelectObject(maskDC, maskBitmap);
SetBkColor(maskDC, RGB(0,0,0));
SetTextColor(maskDC, RGB(255,255,255));
if (!BitBlt(maskDC, 0,0,nWidthSrc,nHeightSrc,NULL,0,0,BLACKNESS))
{
SelectObject(maskDC, oldMask);
DeleteObject(maskBitmap);
DeleteDC(maskDC);
SelectObject(dc, oldBitmap);
DeleteObject(bitmap);
DeleteDC(dc);
return false;
}
SetBkColor(dc, crTransparent);
BitBlt(maskDC, 0,0,nWidthSrc,nHeightSrc,dc,0,0,SRCINVERT);
SetBkColor(dc, RGB(0,0,0));
SetTextColor(dc, RGB(255,255,255));
BitBlt(dc, 0,0,nWidthSrc,nHeightSrc,maskDC,0,0,SRCAND);
HDC newMaskDC = CreateCompatibleDC(NULL);
HBITMAP newMask;
newMask = CreateBitmap(nWidthDest, nHeightDest, 1,
GetDeviceCaps(newMaskDC, BITSPIXEL), NULL);
if (newMask == NULL)
{
SelectObject(dc, oldBitmap);
DeleteDC(dc);
SelectObject(maskDC, oldMask);
DeleteDC(maskDC);
DeleteDC(newMaskDC);
DeleteObject(bitmap);
DeleteObject(maskBitmap);
return false;
}
SetStretchBltMode(newMaskDC, COLORONCOLOR);
HBITMAP oldNewMask = (HBITMAP) SelectObject(newMaskDC, newMask);
StretchBlt(newMaskDC, 0, 0, nWidthDest, nHeightDest, maskDC, 0, 0,
nWidthSrc, nHeightSrc, SRCCOPY);
SelectObject(maskDC, oldMask);
DeleteDC(maskDC);
DeleteObject(maskBitmap);
HDC newImageDC = CreateCompatibleDC(NULL);
HBITMAP newImage = CreateBitmap(nWidthDest, nHeightDest, 1,
GetDeviceCaps(newMaskDC, BITSPIXEL), NULL);
if (newImage == NULL)
{
SelectObject(dc, oldBitmap);
DeleteDC(dc);
DeleteDC(newMaskDC);
DeleteObject(bitmap);
return false;
}
HBITMAP oldNewImage = (HBITMAP)SelectObject(newImageDC, newImage);
StretchBlt(newImageDC, 0, 0, nWidthDest, nHeightDest, dc, 0, 0, nWidthSrc,
nHeightSrc, SRCCOPY);
SelectObject(dc, oldBitmap);
DeleteDC(dc);
DeleteObject(bitmap);
BitBlt( dcDest, nXOriginDest, nYOriginDest, nWidthDest, nHeightDest,
newMaskDC, 0, 0, SRCAND);
BitBlt( dcDest, nXOriginDest, nYOriginDest, nWidthDest, nHeightDest,
newImageDC, 0, 0, SRCPAINT);
SelectObject(newImageDC, oldNewImage);
DeleteDC(newImageDC);
SelectObject(newMaskDC, oldNewMask);
DeleteDC(newMaskDC);
DeleteObject(newImage);
DeleteObject(newMask);
return true;
}

說明：本文提供的TransparentBlt2函數旨在說明透明位圖的顯示原理，在Windows2000以上環境實際運用中建議使用現成的TransparentBlt函數來繪制透明位圖。

#ifndef _DOUBLE_H_
#define _DOUBLE_H_

template<class T>
class Double;

template<class T>
class DoubleNode
{
 friend class Double<T>;
private:
 T data;
 DoubleNode<T> *pre;
 DoubleNode<T> *next;
};

template<class T>
class Double
{
 public:
  Double();//{head=end=NULL;}
  ~Double();
  void Erase();
  void reverse();
  int GetLength()const;
  bool IsEmpty()const;
  bool Find(int k, T& x)const;
  int Search(T& x)const;
  Double<T>& Delete(int k, T& x);
  Double<T>& Insert(int k, const T& x);
  void output(ostream& out)const;
  friend ostream& operator << (ostream& out, const Double<T>& x);
 private:
  DoubleNode<T> *head;
  DoubleNode<T> *end;
  int length;
};

template<class T>
Double<T>::Double()
{
 head = new DoubleNode<T>;
 end = new DoubleNode<T>;
 head->pre = NULL;
 head->next = end;
 end->pre = head;
 end->next = NULL;

 length = 0;
}

template<class T>
Double<T>::~Double()
{
 Erase();
}

template<class T>
void Double<T>::Erase()
{
 DoubleNode<T> *current = head;
 while (current)
 {
  head = head->next;
  delete current;
  current = head;
 }
 length = 0;
}

template<class T>
int Double<T>::GetLength()const
{
 return length;
}

template<class T>
bool Double<T>::IsEmpty()const
{
 return length == 0;
}

template<class T>
bool Double<T>::Find(int k, T& x)const
{

 if (length == 0)
 {
  throw exception("DoubleNode is empty!");
 }
 else if(k<1 || k>length)
 {
  throw exception("no find the position of k");
 }

 DoubleNode<T> *current = head->next;
 for (int i=1; (i<k)&&current; ++i)
 {
  current = current->next;
 }

 if (current)
 {
  x = current->data;
  return true;
 }

 return false;
}

template<class T>
int Double<T>::Search(T& x)const
{
 int nIndex = 1;
 DoubleNode<T> *current = head->next;
 while (current && current->data != x)
 {
  ++nIndex;
  current = current->next;
 }

 if (current)
 {
  return nIndex;
 }

 return -1;
}

template<class T>
Double<T>& Double<T>::Delete(int k, T& x)
{
 if (length == 0)
 {
  throw exception("DoubleNode is empty!");
 }
 else if(k<1 || k>length)
 {
  throw exception("no find the position of k, so can't delete!");
 }

 DoubleNode<T> *current = head->next; 
 for (int i=1; (i<k)&&current; ++i)
 {
  current = current->next;
 }

 DoubleNode<T> * p = current;
 current->pre->next = current->next;
 current->next->pre = current->pre;

 x = p->data;
 delete p;
 p = NULL;
 --length;

 return *this;
}

template<class T>
Double<T>& Double<T>::Insert(int k, const T& x)
{
 if (k>=0 && k<= length)
 {
  DoubleNode<T> *newNode = new DoubleNode<T>;
  newNode->data = x;

  DoubleNode<T> *current = head;
  for (int i=0; i<k; ++i)
  {
   current = current->next;
  }

  newNode->pre = current;
  newNode->next = current->next;
  current->next->pre = newNode;
  current->next = newNode;
  
  
  ++length;
 }
 else
 {
  throw exception("no find the position of k, so can't insert!");
 }

 return *this;
}

template<class T>
void Double<T>::output(ostream& out)const
{
 DoubleNode<T> *current = head->next;
 while (current!=end)
 {
  out << current->data << " ";
  current = current->next;
 }
}

template<class T>
ostream& operator<< (ostream& out, const Double<T>& x)
{
 x.output(out);
 return out;
}

template<class T>
void Double<T>::reverse()
{
 DoubleNode<T> *p1 = head;
 DoubleNode<T> *p2 = NULL;
 DoubleNode<T> *pNode;

 while (p1 != NULL)
 {
  pNode = p1;
  pNode->pre = p1->next;
  p1 = p1->next;
  pNode->next = p2;
  p2 = pNode;
 }

 end = head;
 head = p2;
}

#endif

以上為雙鏈表的基本操作，代碼已經測試過了，可以直接用！
其中，head. end在構造函數時，New了兩個對象，是為了Insert 和 Delete操作的方便！
更好的方式是:把指針和數據分開，這樣head,end就可以節省存貯空間了！
方式如下：
//指針數據部分（后續指針和前驅指針）
struct Node_base
{
 Node_base *next;
 Node_base *pre;
};

//添加實際數據部分
template <class T>
struct Node : public Node_base
{
 T m_data;
};