Posts Tagged 模板类
二叉查找树及一个封装拙劣的BST类
Posted by kingsamchen in PROGRAMMING on 2011 年 02 月 27 日
二叉查找树（Binary Search Tree, BST）是一种特殊的二叉树，常常用来作为进行数据查找的存储结构。
对于长度为n的线性表来说，搜索一个数据的时间是O(n)，而对于BST，搜索的运行时间复杂度和高度成正比。
由二叉树的性质可以知道，当二叉树比较平衡时（比如完全二叉树），其高度h近似等于logn，n为结点数。所以，较为平衡的BST的搜索时间复杂度可以达到O(logn)。
1. 二叉查找树（BST）
BST通常用链表表示，每个结点至少会包含：parent,left,right和key等附加的数据域。如果孩子结点或者父结点不存在，则用NULL表示。
易知，树根结点是唯一一个父结点为NULL的结点。
BST有一个如下所述的重要存储性质：
在一个BST中，对任何结点x，其左子树中的key不大于x的key，其右子树中的key不小于x的key。即
如图为一棵BST
根据BST的性质可以知道，如果对BST进行中序遍历（Inorder Traverse），可以将BST中所有元素按有序输出
遍历一棵含有n个结点的BST所需要的时间复杂度是O(n)，因为每个结点都会被访问。
2. BST类的设计
可以利用C++将BST封装成一个类，便于以后调用。且为了使得这个类通用，我们将类写成模板类
我们需要一个Node结构和一个控制结构的类CBinSearch。
为了尽可能地遵循封装思想，我们将Node类写在CBinSearch类的protected成员中，这样Node结构对外界是透明的。
考虑到某些函数要求客户传入一个指向Node结点的指针，我们仿照STL的iterator，定义出两个公共的结点指针类型
typedef Node* pos; typedef const Node* const_pos;
所以，最后我们的类声明大概是这样的
Read the rest of this entry »
栈与队列
Posted by kingsamchen in PROGRAMMING on 2010 年 08 月 23 日
栈（stack）和队列（queue）是最常见的线性表数据结构之一，用途十分广泛。而且可以使用数组或者链表作为其存储容器
1.栈
栈是一种先进后出（First-In-Last-Out FILO）的数据结构。数据进入栈的操作称为“压栈（Push）”，而出栈的操作称为“出栈（Pop）”。
FILO线性表的特点是：存取元素的操作只在一段进行。即：先压栈的元素必定后出栈。
就好象常见的桶装饼干，最底层的饼干一定是最先装进去的，而我们先拿出来吃的饼干，则是最后装入的。
栈的最顶部称为栈顶，压栈和出栈都在这里进行。而底部由于没有什么大用途，所以也没有赋予特定的名称
如图，是一个栈的简单示意图
栈的应用包括函数的调用以及回文识别等等。
2.栈的实现
为了方便使用，在C++中，我们设计一个CStack
关于模板函数和模板类，请参见模板函数和模板类
Read the rest of this entry »
简述模板函数和模板类
Posted by kingsamchen in PROGRAMMING on 2010 年 07 月 15 日
自从OO（Object-Oriented）出现之后，随着思想模型的逐步确立和SE开发的需要，泛型编程开始并逐渐成为一种重要的编码手段。
使用泛型的好处是，可以将源程序的具体行为和具体的类型无关，最终的类型确定要到最后阶段的绑定。这有点像类中的多态。
而模板是泛型编程的基础，很难想象没有模板的泛型会成为啥样子。
本文旨在帮助你了解熟悉并掌握如何编写自己简单的模板函数和模板类
1.模板是什么
其实，如过你本身对C++没有什么了解，我很难告诉你什么是模板……
模板在语言中的意思大致是“生产一类具有相同功能的模子和器具”，比如民间传统手工作品中制作泥塑的模子，当你把一坨像shit一样的泥巴放入泥塑模子中，然后经过一堆工序，最终出来的就是特定的泥塑作品了。而C++中的模板也有如此的作用。
如果你用过STL中的容器，就可能会接触过vector/deque/lis/map等容器，他们都是利用模板特性设计的。而这些容器的好处是，好多好多的类型都可以通吃而不会产生消化不良的症状。
2. 为什么要用模板
这是一个很有趣的问题，也是一个很严肃的问题。
在还是C的时代，数据结构重用是很让程序员头疼的一个问题，比如你写了一个以int为操作类型的堆栈，那么这个堆栈是不能用来操作char甚至是double(不考虑类型转换)。如果你需要操作其他类型的堆栈，那么基本上只能重写一次了。
所以通常Coder们都用ElementType来代替具体的类型，然后在使用这个数据结构的文件的某处写上typedef int ElementType
俗话说，躲得过初一，躲不过十五，于是新的问题随之而来，这样的做法不能在一个文件中同时对两种数据类型生效。
Read the rest of this entry »
LICENCE
COMMENTS