标签归档:C++

奇怪的C语言数组形式

想起以前读『C陷阱与缺陷』时颠覆过我对数组认知的一个栗子: "0123456789"[n] 居然是一个合法的数组形式。

1
printf("%c", "0123456789"[0]);

以上代码运行后打印字符‘0’,依次类推,printf("%c", "0123456789"[1])打印字符‘1’,printf("%c", "0123456789"[2])打印字符‘2’……这种用法用来解决某些机器的字符集里数字不是顺序排列的问题。例如ASCII码表里字符‘0’-‘9’分别对应着编码0x30-0x39,但有些机器里不是这么按顺序排的……犹记得『K&R』也有提到某些架构的机器上不宜用c+‘0'这样方法来求c的数字表示,原因也是如此,不过具体哪些类型机器会采取这种策略就不得而知了。
  
C语言里,一个字符串常量可以用来表示一个字符数组,所以在数组名出现的地方都可以用字符串常量来替换。

--EOF--

设计模式 —— Observer(观察者模式)

Observer模式(观察者模式)在GoF归纳的23种设计模式里还算是比较容易理解的一种,它适用于一种一对多的环境下,"一"和"多"之间存在依赖关系,当"一"的状态发生改变时,依赖于它的"多"都会得到通知并自动更新自己。Observer模式的对象有两类,一类为目标,就是上述关系中的"一",另一类为观察者,是上述关系中的"多"。

观察者模式的结构图如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 +-----------+ obervers                 +------------+
 |  Subject  |------------------------->|  Observer  |
 +===========+                          +============+
 |  attach() |   +------------------+   |  Update()  |
 |  detach() |   |foreach observers{|   +------^-----+
 |  notify() |-->|   o->Updata()    |          |
 +-----^-----+   |}                 |          |
       |         +------------------+ +----------------+
       |                              |ConcreteObserver|   +--------------------+
+---------------+             subject +================+   |observerState =     |
|ConcreteSubject|<--------------------|   Update()     |-->| subject->GetState()|
+===============+                     | observerState  |   +--------------------+
|  GetStatus()  |                     +----------------+
|  SetStatus()  |
+---------------+

图1 观察者模式结构图
(Download ASCII Picture)

如图所示,观察者模式的参与者分为4类:
1、Subject(目标)
Suject至少需提供3个接口,Attach()和Detach()用于注册和解除观察者对象。Notify()用于在状态改变时通知所有观察者对象。
2、Observer(观察者)
Observer至少需要提供一个Update()接口,用于更新具体观察者对象的状态。
3、ConcreteSubject(具体目标)
ConcreteSubject除了必须实现Subject接口中的方法之外,还必须提供一个"注册中心",所有观察者对象都必须在这个注册中心进行注册,方便在目标状态发生改变时受到通知。
4、ConcreteObserver(具体观察者)
ConcreteObserver维护着一个自身的状态,该状态与ConcreteSubject中的状态要一致,要达到这个目的,还要维护一个指向ConcreteSubject的引用。

观察者模式几个常见的应用场景比如Web开发中的MVC架构,Model作为一个目标(Subject),View组件就是观察者(Observer),一个Model可能会对应多个View组件,因此当Model中数据更新时就通过观察者模式来通知View,从而使得各个View能保持数据的一致性。另一个应用场景如GoF中举例的图形用户界面工具箱。它将数据和界面分离,当数据有更新时,多个界面(表格,柱状图,饼图)均能得到更新。此外,C#中的委托机制也采用了观察者设计模式,委托给一个delegate类的函数就是观察者模式中的Observer角色,delegate类通过"+="和"-="运算符来注册和解除观察者对象,参见『C#的委托和事件』

以下的程序是一个Observer模式的简单实现,其功能与GoF中举例的GUI工具箱类似,目标类为一个数据源(DataSourceMng),观察者类有三个:TableGraph、PieGraph、BarGraph分别表示不同的数据展示方式:表格,饼图,柱状图。数据源中的数据可由数据源本身修改,也可由观察者类进行修改,但无论是谁对其进行修改,目标类都有责任调用Notify()通知向它注册过的所有观察者发送通知。特别当观察者类修改数据源数据时,要注意这个观察者类自身的状态需要由目标类的Notify()统一进行修改,而不是直接擅自进行修改,这也是出于保证数据一致性的重要考虑。

1、Suject类

1
2
3
4
5
6
7
package cn.edu.zju.dp.observer;
 
public interface Subject {
    public void Attach(Observer o);
    public void Detach(Observer o);
    public void Notify();
}

2、Observer类

1
2
3
4
5
6
package cn.edu.zju.dp.observer;
 
public interface Observer {
    public void Updata();
    public void QueryData();
}

3、ConcreteSuject类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package cn.edu.zju.dp.observer;
 
import java.util.LinkedList;
import java.util.List;
 
public class DataSourceMng implements Subject {
    private double               rate = 0.0;
    private final List<Observer> list = new LinkedList<Observer>();
 
    public void setRate(double rate) {
        this.rate = rate;
        Notify();
    }
 
    public double getRate() {
        return this.rate;
    }
 
    @Override
    public void Attach(Observer o) {
        list.add(o);
    }
 
    @Override
    public void Detach(Observer o) {
        list.remove(o);
    }
 
    @Override
    public void Notify() {
        for (Observer o : list) {
            o.Updata();
        }
    }
}

4、ConcreteObserver类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class TableGraph implements Observer {
    private final Subject datasource;
    private double        rate;
 
    public TableGraph(Subject datasource) {
        this.datasource = datasource;
    }
 
    @Override
    public void Updata() {
        this.rate = ((DataSourceMng) datasource).getRate();
    }
 
    @Override
    public void QueryData() {
        System.out.println("TableGraph's Rate = " + rate);
    }
 
    public void ModifyRate(double rate) {
        ((DataSourceMng) datasource).setRate(rate);
    }
}

因PieGraph和BarGraph的实现与TableGraph完全一致,故不重复贴出。

5、测试程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 衔山的博客 - http://fengchj.com
 * Copyright (c) 2011 All Rights Reserved.
 */
package cn.edu.zju.dp.observer;
 
/**
 * 
 * @author 衔山
 * @version $Id: ObserverPatternTest.java, v 0.1 2011-10-23 下午03:01:49
 */
public class ObserverPatternTest {
    public static void main(String[] args) {
        Subject datasource = new DataSourceMng();
 
        Observer table = new TableGraph(datasource);
        Observer pie = new PieGraph(datasource);
        Observer bar = new BarGraph(datasource);
 
        //在目录类中注册观察者类
        datasource.Attach(table);
        datasource.Attach(pie);
        datasource.Attach(bar);
 
        //观察者类修改数据源
        ((TableGraph) table).ModifyRate(0.75);
 
        //所有观察者类的状态得到修改
        table.QueryData(); //TableGraph's Rate = 0.75
        pie.QueryData(); //PieGraph's Rate = 0.75
        bar.QueryData(); //BarGraph's Rate = 0.75
    }
}

Reference:
[1] GoF. 设计模式:可复用面向对象软件的基础[M], 机械工业出版社, 2006-07.

--EOF--

在一个有序数组中查找给定数

题目要求为在一个有序数组中查找一个给定值的数,这个数组是升序还是降序未知。这样就比普通的二分查找要多一步骤,用于判定该数组是升序还是降序,其余就跟普通二分查找一样了。

详见代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/***
 * args:	IN num[]: 有序数组
 *		IN start: 起始下标
 *		IN end: 终点下标
 *		IN value: 待查数值
 *		OUT pos: 待查数值下标
 * return:	true:命中 false:未命中
 */
bool binary_search(int num[], int start, int end, int value, int& pos)
{
    int order = 1; //顺序标记,默认升序
 
    if (num[start] > num[end-1])
    {
        order = 0; //逆序
    }
 
    while (start <= end)
    {
        int mid = (start+end)/2;
 
        if(num[mid] == value){
            pos = mid;
            return true;
        }else{
            if (order == 1) //如果是升序数组
            {
                if (value < num[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } 
            else //如果是降序数组
            {
                if (value < num[mid]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
    }
 
    return false;
}

--EOF--

二叉树根据前序中序得到后序序列

根据二叉树的前序和中序序列,能求得它的后序序列,同样道理,根据中序和后序序列,能求得它的前序序列。但是根据前序和后序序列,无法求得它的中序序列,因为单凭前序和后序序列无法唯一确定一颗二叉树。

以下是根据二叉树的前序和中序序列求其后序序列的算法思想和实现。
关于二叉树的题,最先想到的总是递归。根据二叉树的前序、中序和后序定义,可以找出规律:
1、前序序列的第一个元素肯定是根节点。
2、中序序列中,根节点左边的序列都属于左子树,根节点右边的序列都属于右子树。如此一来,中序序列都划分成三个部分:左子树节点集合、根节点、右子树节点集合。
3、根据中序的三个部分,前序的序列也可以划分成:根节点、左子树节点集合、右子树节点集合。
4、分别对前序和中序序列中的左子树节点集合和右子树节点集合重复步骤1~3。
5、根据后序定义,当左右子树处理完毕后,最后才输出根节点。

对于某前序序列(1245673),中序序列(4265713),根据以上步骤,首先,用根节点1将中序序列分成三个部分(42657-1-3),同时,这样一来,前序序列也可以分成三部分了(1-24567-3),然后分别对子序列(24567)和(3)重复以上步骤,最后输出根节点1。over~~

C++程序实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 *根据二叉树的前序、中序序列得到其后序遍历序列
 *preorder:前序序列 inorder:中序序列 len:序列长度
 */
void process(char* preorder, char* inorder, int len)
{
    int i;
    //当前层次为不再包含元素,退出递归
    if (len <= 0) {
        return;
    }
    //得到当前层次root节点(前序0号元素)在中序的位置
    for(i=0; inorder[i]!=preorder[0]; i++); 
    //递归处理左子树
    process(preorder+1, inorder, i);
    //递归处理右子树
    process(preorder+i+1, inorder+i+1, len-i-1);
    //打印根节点root。
    cout << preorder[0];
}

根据中序和后序序列求前序序列也一样道理,C++实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 *根据二叉树的中序、后序序列得到其前序遍历序列
 *inorder:中序序列 postorder:后序序列 len:序列长度
 */
void process2(char*inorder, char* postorder, int len)
{
    int i;
    if(len <= 0){
        return;
    }
 
    for (i = 0; inorder[i]!=postorder[len-1]; i++);
    cout << postorder[len-1];
    process2(inorder, postorder, i);
    process2(inorder+i+1, postorder+i, len-i-1);
}

测试程序见附件: 源代码

--EOF--

C/C++函数默认返回值

之前有个误区,认为凡是声明了返回值类型(非void)的函数,要是在函数体中没有显式return相应类型的返回值时,编译器会报错的。今天读别人写的程序发现一个声明了返回类型是int的函数,它最后没有显式调用return返回值,但是程序流程走下来发现也没有bug,不解。遂查了下资料,解开疑惑。

C/C++不像Java中的方法,声明了非void类型的方法必须要返回一个确定类型返回值。在我使用的MSVC编译器中,一个有返回类型的函数如果函数体中没有显式调用return语句,编译器会给出一个C4716的警告(warning): warning C4716: 'func' : must return a value。那么这种情况下函数会返回什么值呢?首先的想法就是编译器帮你插入一条默认返回值。然而实际上不是这样的,C/C++函数没有默认的返回值,C/C++标准中没这种说法,因此本文题目其实起得就不够严谨。可是不写return语句确实又能返回,写一个简单的测试程序其实就能测出,没有return语句的函数会返回一个随机数,类似一个未初始化局部变量那样的数,这个数哪里来的呢?实际上,把一段程序经编译后生成汇编代码,就能看见真相。

这是一个C/C++的函数定义,它什么都不干,就返回一个整数1234。

1
2
3
4
int func()
{
    return 1234;
}

经编译后,这段函数定义会被编译成如下汇编代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
3:    int func()
4:    {
00401020   push        ebp
00401021   mov         ebp,esp
00401023   sub         esp,40h
00401026   push        ebx
00401027   push        esi
00401028   push        edi
00401029   lea         edi,[ebp-40h]
0040102C   mov         ecx,10h
00401031   mov         eax,0CCCCCCCCh
00401036   rep stos    dword ptr [edi]
5:        return 1234;
00401038   mov         eax,4D2h
6:    }
0040103D   pop         edi
0040103E   pop         esi
0040103F   pop         ebx
00401040   mov         esp,ebp
00401042   pop         ebp
00401043   ret
...

其他不用考虑,直接看第14行、15行。可以看到return 1234被编译成了mov eax,4D2h,由此可见,其实编译器在处理函数返回值的时候,其实是把待返回的值放在eax寄存器中,然后调用函数再从该寄存器中将值(被调函数的返回值)取出。

这点可再次通过程序验证一下,直接在被调函数体中内嵌汇编代码,为eax寄存器赋值,查看程序执行结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
 
int func() 
{
    _asm{
        mov eax, 1234;
    }
}
 
int main() 
{
    printf("%d\n", func()); //打印func()函数返回值1234。
    return 0;
}

回到上面问题,如果没有显示调用return返回语句,那么在调用程序中还是会去eax寄存器中取值,只是这时的eax寄存器中值是不确定的,因此会打印一串无意义的数字,于是程序就有了潜在的bug。 (衔山)

--EOF--