一道笔试题——输入二叉树的前序和中序遍历序列，输出后序遍历序列

Cloned — Thu, 02 Dec 2010 10:49:00 GMT

算法：

1 如果输入序列长度小于等于0，结束

2 输入的前序序列的第一个节点是后序遍历的最后一个节点，将这个节点保存到output变量中

3 把输入的两个序列拆成4部分，output节点的左子树的前序和中序序列，output节点右子树的前序和中序序列

4 用3中的结果先左后右递归调用该算法

5 输出output

代码如下

1 void LastTree::ShowLast(const char *po, const char *mo, int n) 2 { 3 //递归结束条件 4 if(n <= 0) 5 { 6 return; 7 } 8 9 //输出值 10 char output = *po; 11 12 //output节点的左子树中序序列 13 int i = 0; 14 char *lmct = (char*)malloc(n*sizeof(char)); 15 memset(lmct, 0, n); 16 while(*(mo + i) != output) 17 *(lmct + i) = *(mo + i++); 18 int lnum = i; 19 i++; 20 21 //output节点的右子树中序序列 22 int j = 0; 23 char *rmct = (char*)malloc(n*sizeof(char)); 24 memset(rmct, 0, n); 25 while(*(mo + i) != NULL) 26 { 27 *(rmct + j++) = *(mo + i++); 28 } 29 30 //output节点的左子树前序序列 31 char *lpct = (char*)malloc(n*sizeof(char)); 32 memset(lpct, 0, n); 33 int k = 0; 34 35 for(int a = 0; *(po + a); a++) 36 { 37 for(int b = 0; *(lmct + b); b++) 38 { 39 if(*(po + a) == *(lmct + b)) 40 { 41 *(lpct + k++) = *(po + a); 42 break; 43 } 44 45 } 46 } 47 48 //output节点的右子树前序序列 49 char *rpct = (char*)malloc(n*sizeof(char)); 50 memset(rpct, 0, n); 51 k = 0; 52 53 for(int a = 0; *(po + a); a++) 54 { 55 for(int b = 0; *(rmct + b); b++) 56 { 57 if(*(po + a) == *(rmct + b)) 58 { 59 *(rpct + k++) = *(po + a); 60 break; 61 } 62 63 } 64 } 65 66 //先左后右递归 67 ShowLast(lpct, lmct, lnum); 68 ShowLast(rpct, rmct, n - lnum - 1); 69 70 //输出当前节点 71 std::cout<<output; 72 73 free(lmct); 74 free(rmct); 75 free(lpct); 76 free(rpct); 77 lpct = NULL; 78 rpct = NULL; 79 lmct = NULL; 80 rmct = NULL; 81 return; 82 }

测试用例：

 1 void main()
 2 {
 3     LastTree lt;
 4     const char *po = "ABCDEFG";
 5     const char *mo = "CBDAEGF";
 6 
 7     lt.ShowLast(po, mo, 7);
 8 
 9     _getch();
10 }

输出结果为：CDBGFEA

Cloned 2010-12-02 18:49 发表评论

MFC中自定义类访问主对话框控件

Cloned — Tue, 17 Aug 2010 06:52:00 GMT

在使用mfc的时候经常遇到自定义类访问主对话框控件的问题，例如自定义类中的方法要输出一段字符串到主对话框的EDIT控件、控制对话框的进度条等。

要在自定义的类中访问主对话框空间，须获得主对话的指针。主对话框的对象在app类的InitInstance()方法中声明。查看app类的cpp文件，在InitInstance()方法中有如下语句：

    CAppDlg dlg;
    m_pMainWnd = &dlg;

主对话框指针被传给m_pMainWnd 成员，按f12查看其定义，发现m_pMainWnd 是在afxwin.h中声明的成员：

    CWnd* m_pMainWnd;       // main window (usually same AfxGetApp()->m_pMainWnd)

由于MFC中的自定义类会自动包含stdafx.h头文件，且stdafx.h包含afxwin.h，因此根据注释，在自定义类中可以直接使用

    AfxGetApp()->m_pMainWnd

来获取主对话框的指针。之后可通过

    AfxGetApp()->m_pMainWnd->GetDlgItem( )；

来获得要访问的主对话框控件的指针，以对其进行访问。

Cloned 2010-08-17 14:52 发表评论

C++博客-cloned

一道笔试题——输入二叉树的前序和中序遍历序列，输出后序遍历序列

MFC中自定义类访问主对话框控件