首页 > 代码库 > GDI+学习笔记(九)带插件的排序算法演示器(MFC中的GDI+实例)

GDI+学习笔记(九)带插件的排序算法演示器(MFC中的GDI+实例)

带插件的排序算法演示器


本节将通过一个实例来说明GDI+在MFC中的应用。这个算法演示器其实是本人算法系列的一个开端,由于csdn没有树状的目录结构,咱也只好使用链表了不是?好了,废话不多说,开始今天的文章。


(一)功能说明

我们初步制定功能如下:

(1). 能够通过柱状图,自动展示排序算法的交换比较过程

(2). 能够使用插件的形式进行开发。即,当新完成一个算法后,只需要完成一个插件文件(我们这里使用动态库dll),由主程序加载插件,即可进行执行,而不再需要重新编译主程序。

(3). 保证主程序的独立性。即,进行主程序的时候,插件格式不变。

(4). 可以设置排序的规模。即,排序的数目。

(5). 可以暂停演示,并手动逐步进行上一步或下一步操作。


(二)插件原理

我们的插件采用了动态库。虽然对于加载动态库的方法,网上很多大牛都罗列了一二三,但个人觉得,如果你拥有一些简单的汇编知识就会发现,其实无论你是通过load静态库,包含头文件还是什么其他的方式加载动态库,其实原理都是一样的。

(1). 向编译器解释你的动态库

我们要告诉编译器,一些动态库的信息。这些动态库的信息应该包含:

1. 输出函数的调用约定。

约定的一般类型有以下几种:

__stdcall,__cdecl,__fastcall,__thiscall,__nakedcall,__pascal

其中除了最后一种_pascal之外,其他相同,它们与_pascal的区别在于:

a. 前者的参数顺序是,从右到左依次入栈(个人更喜欢认为pop的顺序从左到右,个人理解,如有偏差,请留言,谢谢。)后者相反。

b. 前者是调用者清除栈,后者是调用者返回后清除栈。


2. 函数地址

使用一个函数,我们还需要知道函数的地址。


3. 函数原型


有了以上三个部分,我们就可以成功的完成对动态库的调用。

(2)插件的实现

1. 返回一个算法实例

我们这里调用动态库的目的,是为了返回一个算法类实例的指针,动态库唯一的对外接口就是为了实现这个目的,下面是接口的实现代码:

BOOL WINAPI Plug_CreateObject(void ** pobj)
{
	*pobj = new CAlgorithmCls;
	return *pobj != NULL;
}
动态库仅仅需要输出上面的一个函数,其中WINAPI是告诉编译这个函数的调用约定,这个宏与_stdcall是一样的。

2. 主程中使用接口

对于每种算法,我们都需要通过这个接口获得我们所需要的类实例指针。在这之前,我们得加载动态库,加载方法如下:

	PLUG_ST stPs;
	ZeroMemory(&stPs, sizeof(stPs));
	stPs.hIns = LoadLibrary(strPlugPath);
	PFN_Plug_CreateObject pFunc = (PFN_Plug_CreateObject)GetProcAddress(stPs.hIns, "Plug_CreateObject");
这里有点陌生的东西,就是结构体PLUG_ST,这个结构的定义如下:

typedef struct{
	CPlugBase * pObj;
	HINSTANCE hIns;
}PLUG_ST, * LPPLUG_ST;
看名字,相信聪明的朋友已经猜出一二,它两个成员,pObj是返回的算法类的基类指针,稍后我们会做详细介绍;另一个是动态库的模块句柄,也就是LoadLibrary的返回值,我们可以认为,它就是动态库的一个身份证。

如果成功加载了,那么,我们就可以通过通过调用它的唯一接口,来获得结构体中的第一个成员,即算法实例指针,代码如下:

	if (pFunc!=NULL && pFunc((void **)&stPs.pObj))
	{
		m_vecPlugs.push_back(stPs);

		m_comboAlg.InsertString(0, strAlgName);
	}
乍一看,似乎有点复杂,其实分开了慢慢看,其实很简单。

首先,我们使用一个vector存储了所有的结构体。括号内的第二句话,只是向combo控件中插入了一个算法的名字

然后,条件中第一部分,要求pFunc非Null,pFunc是GetProcAddress的返回值,如果返回了空,那也就是说,我们没有成功的找到输出函数Plug_CreateObject,那么自然没法进行下一步运算。

最后,最终的就是调用我们刚才获得的函数指针pFunc,来对输出参数赋值,以得到算法的实例指针。

至此,我们就完成了插件的核心代码


3. 插件Base类

我们通过一个虚的插件Base类,来要求插件实现者,必须完成的插件功能。这个虚类的全部代码如下:

class CPlugBase 
{
public:
	CPlugBase(){};
	virtual ~CPlugBase(){;}

	virtual void SetData(int nCount, int *pData) = 0;
	virtual void Start() = 0;
	virtual bool GetNextOp(int &x, int &y, int &op) = 0;
	virtual bool GetLastOp(int &x, int &y, int &op) = 0;
	virtual void End() = 0;
};

我们简单说明一下,几个函数的功能。

SetData,主程序通过这个函数,向插件实现者提供排序的容量和排序的数据。

Start,主程序通过该函数,要求插件实现者,进行他自己的排序运算。当然,这个函数必须在设置完毕数据之后,才能够进行。

GetNextOp/GetLastOp,主程序通过这两个函数,向插件索取一次操作的内容,x,y分别是需要进行操作的两个数据的索引,op为操作类型,我们暂时将其定义为枚举,如下:

	enum AlgOp{
	ALG_SWAP = 0,
	ALG_COMPARE,
};

End,主程序通过这个函数,告知插件,可以进行清除工作。


我们每一次操作的步骤,会记录在一个结构体中,它包含了刚才参数中的三个值,插件实现者可以利用该结构,也可以自己写,甚至不用结构。以下是结构体的实现:

#pragma pack(push, 4)
struct AlgStep{
	AlgOp op;
	int nFirstIndex;	// 前者的交换索引
	int nNextIndex;		// 后者的交换索引


	AlgStep &operator = (const AlgStep &_algStep){
		op = _algStep.op;
		nFirstIndex = _algStep.nFirstIndex;
		nNextIndex = _algStep.nNextIndex;

		return *this;
	}
};
#pragma pack(pop)

这个结构体处,有两点非常重要。

a. 字节对齐。起初,我索引值获取的时候总是错的,调试之后也发现问题,修改对齐方式后,就正确了,当时没有仔细考虑。后来分析了一下,这里对齐方式并不会有太大影响,造成问题的原因可能是,之前的某次修改并没有进行重新编译,使用了旧的obj对象进行链接,导致实际执行的代码,和调试代码不匹配,所以才出现问题的。修改对齐方式后,进行了重新编译,所以没问题。

b. “=”的重载非常必要,这涉及到深拷贝和浅拷贝的问题。说起来好像很专业,其实很简单,就是默认的拷贝函数,只会拷贝结构体实例的地址,而不会结构体实例中具体的各个值传进去,所以有必要重载这个函数。


这样就完成了插件的基类,这个基类的作用是连接主程序与插件子类,插件实现者,通过重载该基类,实现对应的虚函数,就可以在这个算法演示器上,演示自己的排序算法。


4. 简单实现一个不是排序的排序算法

首先,需要新建一个dll库的项目,并将base.h包含进去,当然也可以自己重写一份,重写的时候只需要保证自己写的Base和原来的CPlugBase类的形式一模一样就行,即:类的函数成员的形式相同。这里,我们为了与主程序一致,将CPlugBase添加到了自定义的Include路径中。

然后,继承CPlugBase,实现各个纯虚函数。

(1)SetData,将排序规模和排序数据存入当前的数据成员中

void CAlgorithmCls::SetData( int nCount, int *pData )
{
	m_nCount = nCount;
	m_pData = http://www.mamicode.com/pData;>(2)Start,存入一些简单数据操作,我们这里仅仅是做一些比较,如果是完整的排序算法的话,需要完善该函数,代码如下:

void CAlgorithmCls::Start()
{
	for(int i=0; i<m_nCount-1; i++)
	{
		AlgStep as;
		as.nFirstIndex = i;
		as.nNextIndex = i+1;
		as.op = ALG_COMPARE;

		m_algSteps.push_back(as);
	}
	m_nCurStep = 0;
}

这里m_nCurStep,表示当前执行的步骤,每次计算的时候,我们需要将当前步骤清空至0.

(3)GetNextOp/GetLastOp,这两个函数,分别用于获得下一步/上一步操作内容,同时在该函数内执行交换操作。这里我们暂时没有写交换操作,但是数据的指针和交换数据的索引都知道,这不该是什么难事吧,代码如下:

bool CAlgorithmCls::GetNextOp( int &x, int &y, int &op )
{
	if (m_nCurStep++ < m_algSteps.size()-1)
	{
		x = m_algSteps[m_nCurStep].nFirstIndex;
		y = m_algSteps[m_nCurStep].nNextIndex;
		op = (int)m_algSteps[m_nCurStep].op;

		if (m_algSteps[m_nCurStep].op == ALG_SWAP)
		{
			// ...
		}
	}

	int n = sizeof(AlgOp);

	if (m_nCurStep >= m_algSteps.size())
	{
		return false;
	}

	return true;
}

如果返回了true,说明尚未完成排序,返回false,说明已经完成了所有排序的操作。

(4)End,这里我们暂时没有什么需要清理的数据,因为在类内我们没有分配数据,按照谁分配谁释放的原则,pData指针也交给外部去释放。

最后,将输出文件名改成算法名,我们这里改成了冒泡排序.dll

5. GDI+完成绘制

(1)GDI+的初始化,好像已经说了很多遍了,再重复一次吧,包含头文件<objbase.h>和头文件<gdiplus.h>,使用GdiPlus的名字控件,使用“#pragma comment(lib, "gdiplus.lib")”来完成静态库的加载。GDI+的初始化,OnInitDialog时,使用GdiplusStartup初始化GDI+,OnDestroy时,释放GDI+资源。OnPaint时,进行绘制。

(2)演示程序的绘制,先看代码再解释。

		CDC *pCDC = GetDlgItem(IDC_SHOWPIC)->GetDC();
		HDC hdc = pCDC->GetSafeHdc();
		Graphics grphics(hdc);

		RECT rect;
		GetDlgItem(IDC_SHOWPIC)->GetClientRect(&rect);

		Bitmap bitmap(rect.right-rect.left, rect.bottom-rect.top);
		Graphics grp(&bitmap);
		grp.Clear(Color::Black);

		int nWidth = (rect.right-rect.left)/m_nCount/2;
		int nOffset = (rect.right-rect.left-nWidth*2*m_nCount)/2;	// 整数运算造成的偏移
		int nBottom = 20;

		for(int i=0; i<m_nCount; i++)
		{
			RECT box;
			int nHeight = (rect.bottom-rect.top-nBottom)/m_nCount*(*(m_pData+i));
			box.left = nWidth + i*nWidth*2 + nOffset;
			box.right = box.left+nWidth;
			box.bottom = rect.bottom-nBottom;
			box.top = box.bottom - nHeight;

			if (i!= m_CurOp.nFirstIndex && i!= m_CurOp.nNextIndex)
			{
				SolidBrush sbrush(Color::Crimson);
				grp.FillRectangle(&sbrush, box.left, box.top, box.right-box.left,
					nHeight);
			}
			else
			{
				SolidBrush sbrush(m_Specialcolor);
				grp.FillRectangle(&sbrush, box.left, box.top, box.right-box.left,
					nHeight);
			}
		}
		
		grphics.DrawImage(&bitmap, 0, 0);

我们先在一张Bitmap中,进行绘制,然后将Bitmap的内容绘制到图形控件上(其实就是一个矩形的Static控件,本质只要是一个CWnd都可以进行绘制)。

因为我们从头到尾坐标使用的都是整数,一个柱形有一点点误差,没有问题,但是多了的话偏移就会很大,我们将所有的偏移计算一下,平均分配到两边,就不至于让最终的图像太靠向一边了。

柱形的size计算很简单,但是很罗嗦,大家看看就好,我就不做过多解释了。

每个柱形矩形的绘制,需要填充一个实画刷,然后用该画刷填充一个矩形,就完成了最终的绘制。

背景颜色,填充成了黑色。

至此,我们完成了最初图形的绘制,简单看看效果。



6. 手动执行上一步或者下一步

每次绘制的时候,我们需要记录当前的操作是什么,当前操作所对应的颜色是什么,获得上一步,下一步都需要完成这样的工作,先看一下下一步的代码:

void CAlgorithmDemoDlg::OnNextStep()
{
	m_Specialcolor = Color::Blue;

	int nOp;

	m_vecPlugs[m_nCurAlg].pObj->GetNextOp(m_CurOp.nFirstIndex, m_CurOp.nNextIndex,
		nOp);

	m_CurOp.op = (AlgOp)nOp;

	Invalidate(FALSE);
}

这里我们其实应该根据操作类型nOp来决定特殊的颜色,这里为了省事,我们直接定义成了蓝色。另外,我们的绘制是放在OnPaint函数中的,所以,在获得下一步的时候,我们应该告诉程序,该刷新图形框了。最直白的方法就是向程序发送一个OnPaint消息,这里我们使用Invalidate,这个函数会发送OnPaint函数,FALSE表示不擦除,如果TRUE的话,OnPaint就什么都不绘制了。当然我们也可以使用基类的Invalidate来重绘一个区域。

::InvalidateRect(m_hWnd, NULL, bErase);

我们目前相当于调用了上述代码,如果要重绘一个矩形,只需要将NULL替换成你需要重绘的RECT实例的指针即可。


7. 定时器与自动演示

MFC中的定时器很简单,我们只需要在开始自动演示时,设置一个定时器,演示完毕后,Kill掉这个定时器,然后完成OnTimer的消息响应就可以了。

自动演示消息

void CAlgorithmDemoDlg::OnBnClickedAutorun()
{
	SetTimer(1, 500, NULL);
}

OnTimer完成定时器的响应

void CAlgorithmDemoDlg::OnTimer(UINT_PTR nIDEvent)
{
	// TODO: 在此添加消息处理程序代码和/或调用默认值
	int nOp;
	bool bRet;
	switch(nIDEvent)
	{
	case 1:
		bRet = m_vecPlugs[m_nCurAlg].pObj->GetNextOp(m_CurOp.nFirstIndex, m_CurOp.nNextIndex,
			nOp);
		m_CurOp.op = (AlgOp)nOp;
		if (!bRet)
		{
			KillTimer(1);<span style="white-space:pre">	</span>// 算法演示完毕或失败,则停止自动演示
		}
		Invalidate(FALSE);
		break;
	}

	CDialog::OnTimer(nIDEvent);
}

看下效果:


至此,演示程序,基本完成,还有些细节,在这里就不再多说了。(为什么我上传的图片是静态的?说好的动态图嘞?。。。 好吧,最近有点偷懒,周末有空会对本文继续调整一下,到时候大家会看到动态的算法演示图片,另外,会出一份像样的接口文档。)


好啦,从此,我们就要开始排序算法的实现历程啦,目前打算先实现十种常用的排序算法。