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;
};