当前位置:  编程技术>综合

[1]数据结构之二叉查找树

package cn.thj.data_structures;

/**
 * 二叉查找树
 * 
 * @author 谭恒杰
 */
public class BinarySearchTree<T extends Comparable<? super T>> {
	/**
	 * 构造方法
	 */
	public BinarySearchTree() {
		root = null;
	}

	// 节点类
	private static class BinaryNode<AnyType> {

		AnyType element; // 节点下的元素
		BinaryNode<AnyType> left; // 左孩子
		BinaryNode<AnyType> right; // 右孩子

		// 构造
		BinaryNode(AnyType theElement) {
			this(theElement, null, null);
		}

		BinaryNode(AnyType theElement, BinaryNode<AnyType> lt,
				BinaryNode<AnyType> rt) {
			element = theElement;
			left = lt;
			right = rt;
		}

	}

	// 树的根节点
	private BinaryNode<T> root;

	/**
	 * 插入一个节点
	 * 
	 * @param x
	 */
	public void insert(T x) {
		root = insert(x, root);
	}

	/**
	 * 移除一个节点
	 * 
	 * @param x
	 *            被移除的节点
	 * 
	 */
	public void remove(T x) {
		root = remove(x, root);
	}

	/**
	 * 查找树中的最小的节点
	 * 
	 * @return 最小的节点若树为空则返回null
	 */
	public T findMin() {
		if (isEmpty())
			throw new RuntimeException();
		return findMin(root).element;
	}

	/**
	 * 查找树中的最大的节点
	 * 
	 * @return 最大的节点若树为空则返回null
	 */
	public T findMax() {
		if (isEmpty())
			throw new RuntimeException();
		return findMax(root).element;
	}

	/**
	 * 查找节点
	 * 
	 * @return 存在则返回true 否则返回flase
	 */
	public boolean contains(T x) {
		return contains(x, root);
	}

	/**
	 * 创建一个空树
	 */
	public void makeEmpty() {
		root = null;
	}

	/**
	 * 判断树是否为空
	 * 
	 * @return 为空返回true否则返回false
	 */
	public boolean isEmpty() {
		return root == null;
	}

	/**
	 * 打印树中的节点
	 */
	public void printTree() {
		if (isEmpty())
			System.out.println("这是空树");
		else
			printTree(root);
	}

	/**
	 * 向树中插入一个节点
	 * 
	 * @param x
	 *            要插入的节点
	 * @param t
	 * @return 新树的根节点
	 */
	private BinaryNode<T> insert(T x, BinaryNode<T> t) {
		if (t == null)
			return new BinaryNode<T>(x, null, null);

		int compareResult = x.compareTo(t.element);

		if (compareResult < 0)
			t.left = insert(x, t.left);
		else if (compareResult > 0)
			t.right = insert(x, t.right);
		else
			; // Duplicate; do nothing
		return t;
	}

	/**
	 * 从树中移除一个节点
	 * 
	 * @param x
	 *            要移除的节点
	 */
	private BinaryNode<T> remove(T x, BinaryNode<T> t) {
		if (t == null)
			return t; // Item not found; do nothing

		int compareResult = x.compareTo(t.element);

		if (compareResult < 0)
			t.left = remove(x, t.left);
		else if (compareResult > 0)
			t.right = remove(x, t.right);
		else if (t.left != null && t.right != null) // Two children
		{
			t.element = findMin(t.right).element;
			t.right = remove(t.element, t.right);
		} else
			t = (t.left != null) ? t.left : t.right;
		return t;
	}

	/**
	 * 查找树中的最小的节点
	 * 
	 * @param 树的根点
	 * @return 最小节点.
	 */
	private BinaryNode<T> findMin(BinaryNode<T> t) {
		if (t == null)
			return null;
		else if (t.left == null)
			return t;
		return findMin(t.left);
	}

	/**
	 * 查找树中的最大的节点
	 * 
	 * @param 树的根点
	 * @return 最大节点.
	 */
	private BinaryNode<T> findMax(BinaryNode<T> t) {
		if (t != null)
			while (t.right != null)
				t = t.right;

		return t;
	}

	/**
	 * 判断树中是否包含节点
	 * 
	 * @param x
	 *            要查找的节点
	 * @param t
	 *            子树的根
	 * @return 要查找的节点
	 */
	private boolean contains(T x, BinaryNode<T> t) {
		if (t == null)
			return false;

		int compareResult = x.compareTo(t.element);

		if (compareResult < 0)
			return contains(x, t.left);
		else if (compareResult > 0)
			return contains(x, t.right);
		else
			return true; // Match
	}

	/**
	 * 按升序打印树
	 */
	private void printTree(BinaryNode<T> t) {
		if (t != null) {
			printTree(t.left);
			System.out.println(t.element);
			printTree(t.right);
		}
	}

	/**
	 * 返回树的高度
	 */
	private int height(BinaryNode<T> t) {
		if (t == null)
			return -1;
		else
			return 1 + Math.max(height(t.left), height(t.right));
	}

}

[2]icu4c-4_4_2 on mingw

http://apps.icu-project.org/icu-jsp/downloadPage.jsp?ver=4.4.1&base=c
http://site.icu-project.org/download/48
#8535 & #8537 (C only) Prebuilt binaries are usable on MinGW but the MinGW build is broken
http://site.icu-project.org/download/49#TOC-ICU4C-Download
get icu4c-4_4_2-src.zip


http://qt-project.org/wiki/Compiling-ICU-with-MinGW
bash.exe"-3.1$ ./runConfigureICU MinGW --prefix=$PWD/../dist
runConfigureICU: unrecognized platform "MinGW" (use --help for help)




copy from icu4c-49_1_2-src.zip\runConfigureICU
    MinGW               Use the GNU gcc/g++ compilers on MinGW
    MinGW)
        THE_OS="MinGW"
        THE_COMP="the GNU C++"
        RELEASE_CFLAGS='-O3'
        RELEASE_CXXFLAGS='-O3'
        ;;


ICU for C/C++ 4.4.2 is ready to be built.
=== Important Notes: ===
Data Packaging: library
 This means: ICU data will be linked with ICU. A shared data library will be built.
 To locate data: ICU will use the linked data library. If linked with the stub library located in st
ubdata/, the application can use udata_setCommonData() or set a data path to override.
Building ICU: Use a GNU make such as make to build ICU.
checking the version of "make"... 3.81 (we wanted at least 3.80)
ok


If the result of the above commands looks okay to you, go to the directory
source in the ICU distribution to build ICU. Please remember that ICU needs
GNU make to build properly...


 export PATH=/c/msys/bin:$PATH
 make CPPFLAGS=-D__MSVCRT__
make:
cd .. \
         && CONFIG_FILES=common/Makefile CONFIG_HEADERS= /bin/sh ./config.status
config.status: creating common/Makefile
make[1]: Leaving directory `/d/1/icu4c-4_4_2-src/icu/source/common'
make[1]: Entering directory `/d/1/icu4c-4_4_2-src/icu/source/common'
g++  -I. -I../i18n   "-DDEFAULT_ICU_PLUGINS=\"/d/1/icu4c-4_4_2-src/icu/source/../dist/lib/icu\" "  -
DU_COMMON_IMPLEMENTATION -DHAVE_CONFIG_H  -O3 -W -Wall -ansi -pedantic -Wpointer-arith -Wwrite-strin
gs -Wno-long-long -mthreads -fvisibility=hidden -c -DPIC  -o errorcode.o errorcode.cpp
In file included from unicode/errorcode.h:27:0,
                 from errorcode.cpp:18:
./unicode/uobject.h:120:55: error: 'operator new' takes type 'size_t' ('unsigned int') as first para
meter [-fpermissive]
./unicode/uobject.h:127:57: error: 'operator new' takes type 'size_t' ('unsigned int') as first para
meter [-fpermissive]
./unicode/uobject.h:152:68: error: 'operator new' takes type 'size_t' ('unsigned int') as first para
meter [-fpermissive]
make[1]: *** [errorcode.o] Error 1
make[1]: Leaving directory `/d/1/icu4c-4_4_2-src/icu/source/common'
make: *** [all-recursive] Error 2
install a new mingw




gcc  -I. -I../i18n   "-DDEFAULT_ICU_PLUGINS=\"/d/1/icu4c-4_4_2-src/icu/source/../dist/lib/icu\" "  -DU_COMMON_IMPLEMENTATION -DHAVE_CONFIG_H  -O3 -Wall -ansi -pedantic -Wshadow -Wpointer-arith -Wmissing-prototypes -Wwrite-strings -Wno-long-long -mthreads -fvisibility=hidden -c -DPIC  -o putil.o putil.c
putil.c:604:12: error: '_timezone' undeclared (first use in this function)
C:\MinGW-4.6.1\include\time.h
__MINGW_IMPORT long _timezone;
__MINGW_IMPORT char *_tzname[2];




gcc -D__MSVCRT__  -DU_COMMON_IMPLEMENTATION -DHAVE_CONFIG_H  -O3 -Wall -ansi -pedantic -Wshadow -Wpointer-arith -Wmissing-prototypes -Wwrite-strings -Wno-long-long -mthreads -fvisibility=hidden -c -DPIC  -o putil.o putil.c




loclikely.cpp:1050:18: error: '::_strnicmp' has not been declared
#include <string.h>
g++  -I. -I../i18n   "-DDEFAULT_ICU_PLUGINS=\"/d/1/icu4c-4_4_2-src/icu/source/../dist/lib/icu\" "  -D__cplusplus -D__MSVCRT__ -DU_COMMON_IMPLEMENTATION -DHAVE_CONFIG_H  -O3 -W -Wall -ansi -pedantic -Wpointer-arith -Wwrite-strings -Wno-long-long -mthreads -fvisibility=hidden -c -DPIC  -o loclikely.o loclikely.cpp
extern "C" _CRTIMP int __cdecl __MINGW_NOTHROW _strnicmp (const char*, const char*, size_t);




locdispnames.cpp:769:8: error: '::_stricmp' has not been declared
calendar.cpp:178:13: error: '::_stricmp' has not been declared
extern "C" _CRTIMP int __cdecl __MINGW_NOTHROW _stricmp (const char*, const char*);






gcc  -I. -I../i18n   "-DDEFAULT_ICU_PLUGINS=\"/d/1/icu4c-4_4_2-src/icu/source/../dist/lib/icu\" "  -D__MSVCRT__ -DU_COMMON_IMPLEMENTATION -DHAVE_CONFIG_H  -O3 -Wall -ansi -pedantic -Wshadow -Wpointer-arith -Wmissing-prototypes -Wwrite-strings -Wno-long-long -mthreads -fvisibility=hidden -c -DPIC  -o wintz.o wintz1.c
wintz.c:116:1: error: expected expression before '/' token
delete the comment
  // to bring it inline with the enum
//    return winType+1; 




D:\1\icu4c-4_4_2-src\icu\source\common\unicode\platform.h
/* U_CALLCONV is releated to U_EXPORT2 */
#define U_EXPORT2
D:\1\icu4c-4_4_2-src\icu\source\common\unicode\utypes.h
#define U_I18N_API     U_IMPORT
D:\1\icu4c-4_4_2-src\icu\source\i18n\unicode\regex.h
try:
#define U_I18N_API __declspec(dllexport)
the same. and the dll is working.

[3]协调多个对象之间的交互——中介者模式（四）

20.4 中介者与同事类的扩展

       Sunny软件公司CRM系统的客户对“客户信息管理窗口”提出了一个修改意见：要求在窗口的下端能够及时显示当前系统中客户信息的总数。修改之后的界面如图20-9所示：

图20-9 修改之后的“客户信息管理窗口”界面图

       从图20-9中我们不难发现，可以通过增加一个文本标签(Label)来显示客户信息总数，而且当用户点击“增加”按钮或者“删除”按钮时，将改变文本标签的内容。

      由于使用了中介者模式，在原有系统中增加新的组件（即新的同事类）将变得很容易，我们至少有如下两种解决方案：

       【解决方案一】增加一个界面组件类Label，修改原有的具体中介者类ConcreteMediator，增加一个对Label对象的引用，然后修改componentChanged()方法中其他相关组件对象的业务处理代码，原有组件类无须任何修改，客户端代码也需针对新增组件Label进行适当修改。

       【解决方案二】与方案一相同，首先增加一个Label类，但不修改原有具体中介者类ConcreteMediator的代码，而是增加一个ConcreteMediator的子类SubConcreteMediator来实现对Label对象的引用，然后在新增的中介者类SubConcreteMediator中通过覆盖componentChanged()方法来实现所有组件（包括新增Label组件）之间的交互，同样，原有组件类无须做任何修改，客户端代码需少许修改。

      引入Label之后“客户信息管理窗口”类结构示意图如图20-10所示：

图20-10 增加Label组件类后的“客户信息管理窗口”结构示意图

       由于【解决方案二】无须修改ConcreteMediator类，更符合“开闭原则”，因此我们选择该解决方案来对新增Label类进行处理，对应的完整类图如图20-11所示：

图20-11 修改之后的“客户信息管理窗口”结构图

      在图20-11中，新增了具体同事类Label和具体中介者类SubConcreteMediator，代码如下所示：

//文本标签类：具体同事类
class Label extends Component {
	public void update() {
		System.out.println("文本标签内容改变，客户信息总数加1。");
	}
}

//新增具体中介者类
class SubConcreteMediator extends ConcreteMediator {
	//增加对Label对象的引用
	public Label label;
	
	public void componentChanged(Component c) {
	    //单击按钮
if(c == addButton) {
			System.out.println("--单击增加按钮--");
			list.update();
			cb.update();
			userNameTextBox.update();
			label.update(); //文本标签更新
		}
        //从列表框选择客户
		else if(c == list) {
			System.out.println("--从列表框选择客户--");
			cb.select();
			userNameTextBox.setText();
		}
        //从组合框选择客户
		else if(c == cb) {
			System.out.println("--从组合框选择客户--");
			cb.select();
			userNameTextBox.setText();
		}
	}
}

       修改客户端测试代码：

class Client {
	public static void main(String args[]) {
        //用新增具体中介者定义中介者对象
		SubConcreteMediator mediator;
		mediator = new SubConcreteMediator();
		
		Button addBT = new Button();
		List list = new List();
	    ComboBox cb = new ComboBox();
	    TextBox userNameTB = new TextBox();
	    Label label = new Label();

		addBT.setMediator(mediator);
		list.setMediator(mediator);
		cb.setMediator(mediator);
		userNameTB.setMediator(mediator);
		label.setMediator(mediator);
		
		mediator.addButton = addBT;
		mediator.list = list;
		mediator.cb = cb;
		mediator.userNameTextBox = userNameTB;
		mediator.label = label;
			
		addBT.changed();
		System.out.println("-----------------------------");
		list.changed();
	}
}

       编译并运行程序，输出结果如下：

--单击增加按钮--

列表框增加一项：张无忌。

组合框增加一项：张无忌。

客户信息增加成功后文本框清空。

文本标签内容改变，客户信息总数加1。

-----------------------------

--从列表框选择客户--

组合框选中项：小龙女。

文本框显示：小龙女。

       由于在本实例中不同的组件类（即不同的同事类）所拥有的方法并不完全相同，因此中介者类没有针对抽象同事类编程，导致在具体中介者类中需要维持对具体同事类的引用，客户端代码无法完全透明地对待所有同事类和中介者类。在某些情况下，如果设计得当，可以在客户端透明地对同事类和中介者类编程，这样系统将具有更好的灵活性和可扩展性。

思考

如果不使用中介者模式，按照图20-3所示设计方案，增加新组件时原有系统该如何修改？

       在中介者