宝杉的博客

UNIX/LINUX;ACE;SNMP;C++
posts - 33, comments - 23, trackbacks - 0, articles - 0

预编译头的概念<转>

     所谓的预编译头就是把一个工程中的那一部分代码,预先编译好放在一个文件里(通常是

以.pch为扩展名的)，这个文件就称为预编译头文件这些预先编译好的代码可以是任何的

C/C++代码--------甚至是inline的函数，但是必须是稳定的，在工程开发的过程中不会

被经常改变。如果这些代码被修改，则需要重新编译生成预编译头文件。注意生成预编

译头文件是很耗时间的。同时你得注意预编译头文件通常很大，通常有6-7M大。注意及

时清理那些没有用的预编译头文件。

也许你会问：现在的编译器都有Time stamp的功能，编译器在编译整个工程的时候，它

只会编译那些经过修改的文件，而不会去编译那些从上次编译过，到现在没有被修改过

的文件。那么为什么还要预编译头文件呢？答案在这里，我们知道编译器是以文件为单

位编译的，一个文件经过修改后，会重新编译整个文件，当然在这个文件里包含的所有

头文件中的东西（.eg Macro, Preprocesser ）都要重新处理一遍。VC的预编译头文件

保存的正是这部分信息。以避免每次都要重新处理这些头文件。

预编译头的作用：

根据上文介绍，预编译头文件的作用当然就是提高便宜速度了，有了它你没有必要每次

都编译那些不需要经常改变的代码。编译性能当然就提高了。

预编译头的使用：

要使用预编译头，我们必须指定一个头文件，这个头文件包含我们不会经常改变的

代码和其他的头文件，然后我们用这个头文件来生成一个预编译头文件（.pch文件）

想必大家都知道 StdAfx.h这个文件。很多人都认为这是VC提供的一个“系统级别”的

，编译器带的一个头文件。其实不是的，这个文件可以是任何名字的。我们来考察一个

典型的由AppWizard生成的MFC Dialog Based　程序的预编译头文件。（因为AppWizard

会为我们指定好如何使用预编译头文件，默认的是StdAfx.h，这是VC起的名字）。我们

会发现这个头文件里包含了以下的头文件：

#include <afxwin.h> // MFC core and standard components

#include <afxext.h> // MFC extensions

#include <afxdisp.h> // MFC Automation classes

#include <afxdtctl.h> // MFC support for Internet Explorer 4

Common Controls

#include <afxcmn.h>

这些正是使用MFC的必须包含的头文件，当然我们不太可能在我们的工程中修改这些头文

件的，所以说他们是稳定的。

那么我们如何指定它来生成预编译头文件。我们知道一个头文件是不能编译的。所以我

们还需要一个cpp文件来生成.pch 文件。这个文件默认的就是StdAfx.cpp。在这个文件

里只有一句代码就是：#include “Stdafx.h”。原因是理所当然的，我们仅仅是要它能

够编译而已?D?D?D也就是说，要的只是它的.cpp的扩展名。我们可以用/Yc编译开关来指

定StdAfx.cpp来生成一个.pch文件，通过/Fp编译开关来指定生成的pch文件的名字。打

开project ->Setting->C/C++ 对话框。把Category指向Precompiled Header。在左边的

树形视图里选择整个工程　

Project Options(右下角的那个白的地方)可以看到 /Fp “debug/PCH.pch”，这就是指

定生成的.pch文件的名字，默认的通常是　<工程名>.pch（我的示例工程名就是PCH）。

然后，在左边的树形视图里选择StdAfx.cpp.//这时只能选一个cpp文件！

这时原来的Project Option变成了 Source File Option（原来是工程，现在是一个文件

，当然变了）。在这里我们可以看到 /Yc开关，/Yc的作用就是指定这个文件来创建一个

Pch文件。/Yc后面的文件名是那个包含了稳定代码的头文件，一个工程里只能有一个文

件的可以有YC开关。VC就根据这个选项把 StdAfx.cpp编译成一个Obj文件和一个PCH文件

。

然后我们再选择一个其它的文件来看看，//其他cpp文件

在这里，Precomplier 选择了 Use ⋯⋯⋯一项，头文件是我们指定创建PCH 文件的stda

fx.h

文件。事实上，这里是使用工程里的设置，（如图1）/Yu”stdafx.h”。

这样，我们就设置好了预编译头文件。也就是说，我们可以使用预编译头功能了。以

下是注意事项：

1):如果使用了/Yu，就是说使用了预编译，我们在每个.cpp文件的最开头，我强调一遍

是最开头，包含 你指定产生pch文件的.h文件（默认是stdafx.h）不然就会有问题。如

果你没有包含这个文件，就告诉你Unexpected file end. 如果你不是在最开头包含的，

你自己试以下就知道了，绝对有很惊人的效果⋯..

fatal error C1010: unexpected end of file while looking for precompiled

header directive

Generating Code...

2）如果你把pch文件不小心丢了，编译的时候就会产生很多的不正常的行为。根据以上

的分析，你只要让编译器生成一个pch文件。也就是说把 stdafx.cpp（即指定/Yc的那个

cpp文件）从新编译一遍。当然你可以傻傻的 Rebuild All。简单一点就是选择那个cpp

文件，按一下Ctrl + F7就可以了。不然可是很浪费时间的哦。

posted @ 2007-04-26 11:55 宝杉 阅读(816) | 评论 (0) | 编辑 收藏

九宫问题求解<转>

2007-02-16 13:35

　　昨日偶然玩了会手机游戏--拼图正是九宫问题。大二小学期的vb程序设计就是这个题目，当时没有仔细研究。现在从新来看看这个问题。

<一下文字 摘自http://www.qqgb.com/Program/VC/VCarithmetic/Program_55328.html>

一、题目说明：
　　（九宫问题）在一个３×３的九宫中有１－８这８个数及一个空格随机的摆放在其中的格子里，如图１－１所示。现在要求实现这个问题：将该九宫格调整为如图１－１右图所示的形式。调整的规则是：每次只能将与空格（上、下、或左、右）相邻的一个数字平移到空格中。试编程实现这一问题的求解。

　　（图１－１）

二、题目分析：
　　九宫问题是人工智能中的经典难题之一，问题是在３×３方格棋盘中，放８格数，剩下的没有放到的为空，每次移动只能是和相邻的空格交换数。程序自动产生问题的初始状态，通过一系列交换动作将其转换成目标排列（如下图１－２到图１－３的转换）。

         （图１－２）                   （图１－３）

 　九宫问题中，程序产生的随机排列转换成目标共有两种可能，而且这两种不可能同时成立，也就是奇数排列和偶数排列。我们可以把一个随机排列的数组从左到右从上到下用一个一维数组表示，如上图１－２我们就可以表示成｛８，７，１，５，２，６，３，４，０｝其中０代表空格。
在这个数组中我们首先计算它能够重排列出来的结果，公式就是：

∑（Ｆ（Ｘ））＝Ｙ，其中Ｆ（Ｘ）

　　就是一个数他前面比这个数小的数的个数，Ｙ为奇数和偶数个有一种解法。那么上面的数组我们就可以解出它的结果。

Ｆ（８）＝０；
Ｆ（７）＝０；
Ｆ（１）＝０；
Ｆ（５）＝１；
Ｆ（２）＝１；
Ｆ（６）＝３；
Ｆ（３）＝２；
Ｆ（４）＝３；
Ｙ＝０＋０＋０＋１＋１＋３＋２＋３＝１０

　　Ｙ＝１０是偶数，所以他的重排列就是如图１－３的结果，如果加起来的结果是奇数重排的结果就是如图１－１最右边的排法。


 

注：将一个八数码的状态对应到一个序列，例如：
1 2 3 
4 5 6 
8 7 
可对应于序列：1 2 3 4 5 6 8 7 

对于空格的左移/右移操作，对应序列不变（逆序数也就不变）
对于空格的上移/下移操作，相当于序列的某个数字前移/后移两位，该序列的逆序数奇偶性不变。

综上所述，两个互相可达的状态对应序列逆序数的奇偶性应该相同

1 2 3 4 5 6 8 7奇偶性为1
1 2 3 4 5 6 7 8奇偶性为0
所以两状态相互不可达  

 

三、算法分析
　　九宫问题的求解方法就是交换空格（０）位置，直至到达目标位置为止。图形表示就是：

（图３－１）

　　要想得到最优的就需要使用广度优先搜索，九宫的所以排列有９！种，也就是３６２８８０种排法，数据量是非常大的，我使用的广度搜索，需要记住每一个结点的排列形式，要是用数组记录的话会占用很多的内存，我们把数据进行适当的压缩。使用ＤＷＯＲＤ形式保存，压缩形式是每个数字用３位表示，这样就是３×９＝２７个字节，由于８的二进制表示形式１０００，不能用３位表示，我使用了一个小技巧就是将８表示位０００，然后用多出来的５个字表示８所在的位置，就可以用ＤＷＯＲＤ表示了。用移位和或操作将数据逐个移入，比乘法速度要快点。定义了几个结果来存储遍历到了结果和搜索完成后保存最优路径。

 

 错误纠正：DWORD是32bit（当然是在WIN32下），上述段落把bit（位）说成了字。每个数字0—8都是用二进制表示的，占3位，共9个。故存储一个状态已占3*9=27位，还剩5位，用来表示8所在位置。

　　关于把（8）10=（1000）2表示成000是如何与（0）10区分的，我还没有看懂。也许下面的代码会更解释的更加清楚。今天先休息了，下午还要去超市。晚上有时间把代码看完，然后加上注释。

 

 

类结构如下：

class CNineGird
{
public:
struct PlaceList
    {
DWORD Place;
PlaceList* Left;
PlaceList* Right;
    };
struct Scanbuf
{
DWORD Place;
int ScanID;
};
struct PathList
{
unsigned char Path[9];
};

private:
PlaceList *m_pPlaceList;
Scanbuf *m_pScanbuf;
RECT m_rResetButton;
RECT m_rAutoButton;

public:
int m_iPathsize;
clock_t m_iTime;
UINT m_iStepCount;
unsigned char m_iTargetChess[9];
unsigned char m_iChess[9];
HWND m_hClientWin;
PathList *m_pPathList;
bool m_bAutoRun;

private:
inline bool AddTree(DWORD place , PlaceList*& parent);
void FreeTree(PlaceList*& parent);
inline void ArrayToDword(unsigned char *array , DWORD & data);
inline void DwordToArray(DWORD data , unsigned char *array);
inline bool MoveChess(unsigned char *array , int way);
bool EstimateUncoil(unsigned char *array);
void GetPath(UINT depth);

public:
void MoveChess(int way);
bool ComputeFeel();
void ActiveShaw(HWND hView);
void DrawGird(HDC hDC , RECT clientrect);
void DrawChess(HDC hDC , RECT clientrect);
void Reset();
void OnButton(POINT pnt , HWND hView);

public:
CNineGird();
~CNineGird();
};

　　计算随机随机数组使用了vector模板用random_shuffle（，）函数来打乱数组数据，并计算目标结果是什么。代码：

void CNineGird::Reset()
{
if(m_bAutoRun) return;
vector vs;
int i;
for (i = 1 ; i < 9 ; i ++)
vs.push_back(i);
vs.push_back(0);
random_shuffle(vs.begin(), vs.end());
random_shuffle(vs.begin(), vs.end());
for ( i = 0 ; i < 9 ; i ++)
{
m_iChess[i] = vs[i];
}

if (!EstimateUncoil(m_iChess))
{
unsigned char array[9] = {1,2,3,8,0,4,7,6,5};
memcpy(m_iTargetChess , array , 9);
}
else
{
unsigned char array[9] = {1,2,3,4,5,6,7,8,0}

memcpy(m_iTargetChess , array , 9);
}

m_iStepCount = 0;
}

 

数据压缩函数实现：

inline void CNineGird::ArrayToDword(unsigned char *array , DWORD& data)
{
unsigned char night = 0;
for ( int i = 0 ; i < 9 ; i ++)
{
if (array[i] == 8)
{
night = (unsigned char)i;
break;
}
}

array[night] = 0;
data = 0;
data = (DWORD)((DWORD)array[0] << 29 | (DWORD)array[1] << 26 |
(DWORD)array[2] << 23 | (DWORD)array[3] << 20 |
(DWORD)array[4] << 17 | (DWORD)array[5] << 14 |
(DWORD)array[6] << 11 | (DWORD)array[7] <<  8 |
(DWORD)array[8] <<  5 | night);

array[night] = 8;
}

解压缩时跟压缩真好相反，解压代码：

inline void CNineGird::DwordToArray(DWORD data , unsigned char *array)
{
unsigned char chtem;
for ( int i = 0 ; i < 9 ; i ++)
{
chtem = (unsigned char)(data >> (32 - (i + 1) * 3) & 0x00000007);
array[i] = chtem;
}
chtem = (unsigned char)(data & 0x0000001F);
array[chtem] = 8;
}

　　由于可扩展的数据量非常的大，加上我在保存的时候使用的是ＤＷＯＲＤ类型，将每一步数据都记录在一个排序二叉树中，按从小到大从左到有的排列，搜索的时候跟每次搜索将近万次的形式比较快几乎是Ｎ次方倍，把几个在循环中用到的函数声明为内联函数，并在插入的时候同时搜索插入的数据会不会在树中有重复来加快总体速度。二叉树插入代码：

inline bool CNineGird::AddTree(DWORD place , PlaceList*& parent)
{
if (parent == NULL)
{
parent = new PlaceList();
parent->Left = parent->Right = NULL;
parent->Place = place;
return true;
}
if (parent->Place == place)
return false;

if (parent->Place > place)
{
return AddTree(place , parent->Right);
}
return AddTree(place , parent->Left);
}

计算结果是奇数排列还是偶数排列的代码：

bool CNineGird::EstimateUncoil(unsigned char *array)
{
int sun = 0;
for ( int i = 0 ; i < 8 ; i ++)
{
for ( int j = 0 ; j < 9 ; j ++)
{
if (array[j] != 0)
{
if (array[j] == i +1 )
break;
if (array[j] < i + 1)
sun++;
}
}
}
if (sun % 2 == 0)
return true;
else
return false;
}

　　移动到空格位的代码比较简单，只要计算是否会移动到框外面就可以了，并在移动的时候顺便计算一下是不是已经是目标结果，这是用来给用户手工移动是给与提示用的，代码：

inline bool CNineGird::MoveChess(unsigned char *array , int way)
{
int zero , chang;
bool moveok = false;
for ( zero = 0 ; zero < 9 ; zero ++)
{
if (array[zero] == 0)
break;
}
POINT pnt;
pnt.x = zero % 3;
pnt.y = int(zero / 3);
switch(way)
{
case 0 : //up
if (pnt.y + 1 < 3)
{
chang = (pnt.y + 1) * 3 + pnt.x ;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
case 1 : //down
if (pnt.y - 1 > -1)
{
chang = (pnt.y - 1) * 3 + pnt.x ;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
case 2 : //left
if (pnt.x + 1 < 3)
{
chang = pnt.y * 3 + pnt.x + 1;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
case 3 : //right
if (pnt.x - 1 > -1)
{
chang = pnt.y * 3 + pnt.x - 1;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
}
if (moveok && !m_bAutoRun)
{
m_iStepCount ++ ;

DWORD temp1 ,temp2;
ArrayToDword(array , temp1);
ArrayToDword(m_iTargetChess , temp2);
if (temp1 == temp2)
{
MessageBox(NULL , "你真聪明这么快就搞定了!" , "^_^" , 0);
}
}
return moveok;
}

　　我在进行广度搜索时候，将父结点所在的数组索引记录在子结点中了，所以得到目标排列的时候，我们只要从子结点逆向搜索就可以得到最优搜索路径了。用变量m_iPathsize来记录总步数，具体函数代码：

void CNineGird::GetPath(UINT depth)
{
int now = 0 , maxpos = 100 ;
UINT parentid;
if (m_pPathList != NULL)
{
delete[] m_pPathList;
}
m_pPathList = new PathList[maxpos];
parentid = m_pScanbuf[depth].ScanID;

DwordToArray(m_pScanbuf[depth].Place , m_pPathList[++now].Path);

while(parentid != -1)
{
if (now == maxpos)
{
maxpos += 10;
PathList * temlist = new PathList[maxpos];
memcpy(temlist , m_pPathList , sizeof(PathList) * (maxpos - 10));
delete[] m_pPathList;
m_pPathList = temlist;
}
DwordToArray(m_pScanbuf[parentid].Place , m_pPathList[++now].Path);
parentid = m_pScanbuf[parentid].ScanID;
}
m_iPathsize = now;
}

 

　　动态排列的演示函数最简单了，为了让主窗体有及时刷新的机会，启动了一个线程在需要主窗体刷新的时候，用Ｓｌｅｅ（ＵＩＮＴ）函数来暂停一下线程就可以了。代码：

unsigned __stdcall MoveChessThread(LPVOID pParam)
{
CNineGird * pGird = (CNineGird *)pParam;
RECT rect;
pGird->m_iStepCount = 0;
::GetClientRect(pGird->m_hClientWin , &rect);
for ( int i = pGird->m_iPathsize ; i > 0 ; i --)
{
memcpy(pGird->m_iChess , pGird->m_pPathList[i].Path , 9);
pGird->m_iStepCount ++;
InvalidateRect( pGird->m_hClientWin , &rect , false);
Sleep(300);
}
char msg[100];
sprintf(msg , "^_^ ! 搞定了!\r\n计算步骤用时%d毫秒" , pGird->m_iTime);
MessageBox(NULL , msg , "~_~" , 0);
pGird->m_bAutoRun = false;
return 0L;
}

　　最后介绍一下搜索函数的原理，首先得到源数组，将其转换成ＤＷＯＲＤ型，与目标比较，如果相同完成，不同就交换一下数据和空格位置，加入二叉树，搜索下一个结果，直到没有步可走了，在搜索刚刚搜索到的位置的子位置，这样直到找到目标结果为止，函数：

bool CNineGird::ComputeFeel()
{
unsigned char *array = m_iChess;
UINT i;
const int MAXSIZE = 362880;
unsigned char temparray[9];

DWORD target , fountain , parent , parentID = 0 , child = 1;
ArrayToDword(m_iTargetChess , target);
ArrayToDword(array , fountain);
if (fountain == target)
{
return false;
}
if (m_pScanbuf != NULL)
{
delete[] m_pScanbuf;
}
m_pScanbuf = new Scanbuf[MAXSIZE];
AddTree(fountain ,m_pPlaceList);
m_pScanbuf[ 0 ].Place = fountain;
m_pScanbuf[ 0 ].ScanID = -1;
clock_t tim = clock();
while(parentID < MAXSIZE && child < MAXSIZE)
{
parent = m_pScanbuf[parentID].Place;
for ( i = 0 ; i < 4 ; i ++)　// 0 :UP , 1:Down ,2:Left,3:Right
{
DwordToArray(parent , temparray);
if (MoveChess(temparray,i)) //是否移动成功
{
ArrayToDword(temparray , fountain);
if (AddTree(fountain, m_pPlaceList)) //加入搜索数
{
m_pScanbuf[ child ].Place = fountain;
m_pScanbuf[ child ].ScanID = parentID;
if (fountain == target) //是否找到结果
{
m_iTime = clock() - tim;
GetPath(child);//计算路径
FreeTree(m_pPlaceList);
delete[] m_pScanbuf;
m_pScanbuf = NULL;
return true;
}
child ++;
}
}
} // for i
parentID++;
}
m_iTime = clock() - tim;

FreeTree(m_pPlaceList);
delete[] m_pScanbuf;
m_pScanbuf = NULL;
return false;
}

 

 

 

 

 

 

posted @ 2007-04-26 11:45 宝杉 阅读(769) | 评论 (0) | 编辑 收藏

CString,string,char*之间的转换

这几天经常用到的，不如记下吧。

这三种类型各有各的优点，比如CString比较灵活，是基于MFC常用的类型，安全性也最高，但可移植性最差。string是使用STL时必不可少的类型，所以是做工程时必须熟练掌握的；char*是从学习C语言开始就已经和我们形影不离的了，有许多API都是以char*作为参数输入的。所以熟练掌握三者之间的转换十分必要。

以下我用简单的图示指出三者之间的关系，并以标号对应转换的方法。

 

change.JPG

1 string to CString   

  CString.format("%s",string.c_str()); 

2 CString to string

string str(CString.GetBuffer(str.GetLength()));

3 string to char *

char *p=string.c_str();

4 char * to string

string str(char*);

5 CString to char *

strcpy(char,CString,sizeof(char));

6 char * to CString

CString.format("%s",char*);

 CString的format方法是非常好用的。string的c_str()也是非常常用的，但要注意和char *转换时，要把char定义成为const char*，这样是最安全的。

posted @ 2007-04-26 11:43 宝杉 阅读(31013) | 评论 (12) | 编辑 收藏

仅列出标题
共4页: 1 2 3 4