cloned

 

2010年12月2日

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

算法:
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

posted @ 2010-12-02 18:49 Cloned 阅读(719) | 评论 (0)编辑 收藏

2010年8月17日

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

在使用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(  );

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

posted @ 2010-08-17 14:52 Cloned 阅读(530) | 评论 (0)编辑 收藏

仅列出标题  

导航

统计

常用链接

留言簿

随笔档案

友情链接

搜索

最新评论

阅读排行榜

评论排行榜