博文
数据结构学习（C++）——循环链表(2007-04-02 06:17:00)
摘要：原书对循环链表的介绍很简略，实现部分也不完整（当然了，如果完整就又是重复建设）。而我也没觉得循环链表有什么别的用，他更应该是为了一个特殊的问题而产生的，这只是个人的看法。我从链表类派生出了循环链表，这需要注意几个细节。
1. 构造函数：派生类实例化时，先调用基类的构造函数；因此，初始化循环链表的工作就是将带表头的空链表的表头节点的link指向表头节点，从而构成一个圈。
2. 析构函数：释放对象时，先调用派生类的析构函数，然后调用基类的析构函数。因此，释放循环链表只需要将循环链表变成普通的单链表，然后这个单链表会被基类的析构函数释放。这里假定不使用这种语句Base *p = new Drived;delete p;因为我在~List()前面没有加virtual。你可以参阅各种C++书籍搞清这类问题。
3. 判空函数：条件不是检测头节点的link是否为空，而是是否指向头节点。
4. 置空函数：原来的显然不能工作了，实际上只要从表头位置不断后删直到表空就可以了。
5. Next()：遇到表头节点要跳过去。
6. Remove()：当前节点是表头节点时不能删，删了表头节点的后果自己想吧（因为在循环链表中prior指针不一定为空——其实应该是一定不空，但是由于继承部分List函数，所以就是不一定了，以至于原来的Remove()检查可能无效）；如果删除的是表尾节点，删除后当前指针将指向表头节点，要跳过去指向下一个。总之，使用Next()和Remove()时，不能让外界觉察到表头节点的存在，否则，当你循环计数时，表头节点就被算进去了。
7. “<<”必须重写，否则，当你执行co......
数据结构学习（C++）——序言(2007-04-02 06:16:00)
摘要：题外话：先前有一篇文章叫《用C++模板描述的链表、栈、队列（声明与实现）》，当时是第一次发表文章（我才注册没几天），很不成熟，改了又改不说，还弄的老长，不利于阅读。于是我重写了一下，并且想做成一个系列，这从我的标题可以看出来。好，言归正传。
本篇为后面一系列文章的序言，旨在说明写作的目的，以及写作的风格；或者说是为自己可能的错误，预先给个托词。如果您不想听我在这废话，请跳过本篇，直接阅读后面的文章。但是这样，我不能保证，您在阅读的同时，不会骂我白痴。
为什么写这些文章
这些文章可以说是《数据结构（用面向对象方法与C++描述）》这本书的读书笔记，但也不完全是。数据结构是计算机专业必修课——几乎每个计算机专业的学生都会推崇他的重要；同时，也是其他专业转修计算机专业的一个难点。
从学习的角度来说，严蔚敏的《数据结构（C语言版）》是本不错的书。但是，C语言不是描述的理想工具。《数据结构（C语言版）》的前言里是这样说的：“虽然C语言不是抽象数据类型的理想描述工具，但鉴于目前和近一、二年内，……并增添了C++语言的引用调用参数传递方式等，构成了一个类C描述语言。”
从抽象数据类型的定义——一个数学模型以及定义在该模型上的一组操作——可以看出，面向对象语言中类的概念和这个定义很接近，加之C语言的普及，用C++来描述于是就成了顺理成章的事情。
于是，清华在2002年的考研参考书目中对《数据结构》的参考书做了改变，使用《数据结构（用面向对象方法与C++描述）》（殷人昆等编著，ISBN 7-302-03405-2/TP1845）作为参考书，而实际上考的也是（废话，不是那叫误导）。坦白的讲，原书把教学目的和提供实例的目的搞混了，结果是个四不象：作为教科书，条理不清晰；提供各个方法的实现，也不是很实用，相反，重复建设太多。至于错误，可能有些是笔误，比如少个友元声明了，不是继承而使用别的类的成员函数没有指明了；还有一些，就是考虑不够周全。
不管怎么说，现在不是挑书的时候，你想考清华的计算机专业研究生吗，这本书是你不二的选择。我发现读懂此书淖詈梅椒ǎ褪亲约喊凑帐樯系乃悸罚约笆导视τ玫姆治觯约褐匦率迪指髦殖橄笫堇嘈汀Ｕ庋龌褂幸桓龊么Γ约航椿垡坏悴聘弧?/SPAN>
我的写作风格
编译器我选用的是VC6，因此，我不保证我提供的代码在别的编译器也能通过——从......
数据结构学习（C++）——单链表（定义与实现）(2007-04-02 06:16:00)
摘要：
节点类
#ifndef Node_H
#define Node_H
template <class Type> class Node //单链节点类
{
public:
Type data;
Node<Type> *link;
Node() : data(Type()), link(NULL) {}
Node(const Type &item) : data(item), link(NULL) {}
Node(const Type &item, Node<Type> *p) : data(item), link(p) {}
};
#endif
【说明】因为数据结构里用到这个结构的地方太多了，如果用原书那种声明友元的做法，那声明不知道要比这个类的本身长多少。不如开放成员，事实上，这种结构只是C中的struct，除了为了方便初始化一下，不需要任何的方法，原书那是画蛇添足。下面可以看到，链表的public部分没有返回Node或者Node*的函数，所以，别的类不可能用这个开放的接口对链表中的节点操作。
【重要修改】原书的缺省构造函数是这样的Node() : data(NULL), link(NULL) {} 。我原来也是照着写的，结果当我做扩充时发现这样是不对的。当Type为结构而不是简单类型（int、……），不能简单赋NULL值。这样做使得定义的模板只能用于很少的简单类型。显然，这里应该调用Type的缺省构造函数。 这也要求，用在这里的类一定要有缺省构造函数。在下面可以看到构造链表时，使用了这个缺省构造函数。当然，这里是约定带表头节点的链表，不带头节点的情况请大家自己思考。
【闲话】请不要对int *p......
数据结构学习（C++）——如何在一个链表中链入不同类型的对象(2007-04-02 06:15:00)
摘要：乎你也注意到了，不管怎么定义，好像一个链表中的对象都是同一类型的。而实际上，这也是必须的，否则，返回节点中的数据这样的函数的返回值的类型是什么呢？但是，人的要求是无止境的……（省略本人感慨若干百字）。把不同的对象链在一个链表中的目的是为了方便使用，现在一定记住这个原则，后面的讨论都是基于这个原则的，否则，我们就是技术狂人了——偏偏实现一些看起来不可能的事情。
达到这个目标的原理其实很简单，只要把不同类型的对象变成同样的类型就可以了。看下面的结构定义：
struct Mobject
{
void *p;
int ObjectType;
};
将一个对象链入链表时，将指向这个对象的指针赋给p，同时记录对象类型。当取得这个节点的时候，根据ObjectType的值来确定p指的对象类型，从而还原指针类型，也就得到了原来的对象。
后面讲到的广义表实际上采用的就是这种方法。显而易见的，这样的Mobject支持的对象是预先确定的，你将自己维护ObjectType列表，每添加一种类型的支持，你需要在ObjectType列表中给出它的替代值，然后在相应的switch(ObjectType)给出这种类型的case语句。很烦人是吧，下面给出另一种方法，其实还是这个原理，不同的是，把这个烦人的工作交给编译器了。
还记得前边强调的原则吗，为什么我们将不同类型的对象放在一个链表中呢？很显然，我们想达到这样的一个效果：比如说，我们在一个链表中储存了三角形，直线，圆等图形的参数，我们希望对某个节点使用Draw()方法，就重绘这个图形；使用Get()则得到这个图形的各个参数；使用Put()则修改图形的参数。可以看出，这些不同的对象实际上有同样的行为，只是实现的方法不同。
C++的多态性正好可以实现我们的构想。关于这方面，请参阅相关的C++书籍（我看的是《C++编程思想》）。请看如下的例子：
#ifndef Shape_H
#define Shape_H
class Shape
{
public:
virtual void ......
数据结构学习（C++）——队列应用（事件驱动模拟）(2007-04-02 06:14:00)
摘要：看的两本教科书（《数据结构（C语言版）》还有这本黄皮书）都是以这个讲解队列应用的，而且都是银行营业模拟（太没新意了）。细比较，这两本书模拟的银行营业的方式还是不同的。1997版的《数据结构（C语言版）》的银行还是老式的营业模式（毕竟是1997年的事了），现在的很多地方还是这种营业模式——几个窗口同时排队。这种方式其实不太合理，经常会出现先来的还没有后来的先办理业务（常常前面一个人磨磨蹭蹭，别的队越来越短，让你恨不得把前面那人干掉）。1999版的这本黄皮书的银行改成了一种挂牌的营业方式，每个来到的顾客发一个号码，如果哪个柜台空闲了，就叫号码最靠前的顾客来办理业务；如果同时几个柜台空闲，就按照一种法则来决定这几个柜台叫号的顺序（最简单的是按柜台号码顺序）。这样，就能保证顾客按照先来后到的顺序接受服务——因为大家排在一个队里。这样的营业模式我在北京的西直门工商银行见过，应该说这是比较合理的一种营业模式。不过，在本文中最重要的是，这样的营业模式比较好模拟（一个队列总比N个队列好操作）。
原书的这部分太难看了，我看的晕晕的，我也不知道按照原书的方法能不能做出来，因为我没看懂（旁白：靠，你小子这样还来现眼）。我按照实际情况模拟，实现如下：
#ifndef Simulation_H
#define Simulation_H
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
class Teller
{
public:
int totalCustomerCount;
int totalServiceTime;
int finishServiceTime;
Teller() :totalCustomerCount(0), totalServiceTime(0),
&nbs......
数据结构学习（C++）——栈应用（表达式求值）(2007-04-02 06:14:00)
摘要：栈的应用很广泛，原书只讲解了表达式求值，那我也就只写这些。其实，栈的最大的用途是解决回溯问题，这也包含了消解递归；而当你用栈解决回溯问题成了习惯的时候，你就很少想到用递归了，比如迷宫求解。另外，人的习惯也是先入为主的，比如树的遍历，从学的那天开始，就是递归算法，虽然书上也教了用栈实现的方法，但应用的时候，你首先想到的还是递归；当然了，如果语言本身不支持递归（如BASIC），那栈就是唯一的选择了——好像现在的高级语言都是支持递归的。
如下是表达式类的定义和实现，表达式可以是中缀表示也可以是后缀表示，用头节点数据域里的type区分，这里有一点说明的是，由于单链表的赋值函数，我原来写的时候没有复制头节点的内容，所以，要是在两个表达式之间赋值，头节点里存的信息就丢了。你可以改写单链表的赋值函数来解决这个隐患，或者你根本不不在两个表达式之间赋值也行。
#ifndef Expression_H
#define Expression_H
#include "List.h"
#include "Stack.h"
#define INFIX 0
#define POSTFIX 1
#define OPND 4
#define OPTR 8
template <class Type> class ExpNode
{
public:
int type;
union { Type opnd; char optr;};
ExpNode() : type(INFIX), optr('=') {}
ExpNode(Type opnd) : type(OPND), opnd(opnd) {}
ExpNode(char optr) : type(OPTR), optr(optr) {}
};
template <cla......
四则运算实现(2007-04-02 06:13:00)
摘要：#include"conio.h"
#include "stdio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef char SElemType;
typedef int Status;
#define OK 1
#define OVERFLOW 0
#define ERROR 0
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &s){//构造一个空栈
s.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!s.base)exit(OVERFLOW);
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return OK;
}//InitStack
SElemType Getop(SqStack s){//若栈不空,则返回用e返回s栈元素
SElemType e;
if(s.top==s.base)return ERROR;
e=*(s.top-1);
return e;
}//Getop
Status&nbs......
数据结构学习（C++）——栈和队列（定义和实现）(2007-04-02 06:12:00)
摘要：栈和队列是操作受限的线性表，好像每本讲数据结构的数都是这么说的。有些书按照这个思路给出了定义和实现；但是很遗憾，这本书没有这样做，所以，原书中的做法是重复建设，这或许可以用不是一个人写的这样的理由来开脱。
顺序表示的栈和队列，必须预先分配空间，并且空间大小受限，使用起来限制比较多。而且，由于限定存取位置，顺序表示的随机存取的优点就没有了，所以，链式结构应该是首选。
栈的定义和实现
#ifndef Stack_H
#define Stack_H
#include "List.h"
template <class Type> class Stack : List<Type>//栈类定义
{
public:
void Push(Type value)
{
Insert(value);
}
Type Pop()
{
Type p = *GetNext();
RemoveAfter();
return p;
......
数据结构学习（C++）——稀疏矩阵（十字链表【2】）(2007-04-02 06:11:00)
摘要：如果你细想想，就会发现，非零元节点如果没有指示位置的域，那么做加法和乘法时，为了确定节点的位置，每次都要遍历行和列的链表。因此，为了运算效率，这个域是必须的。为了看出十字链表和单链表的差异，我从单链表派生出十字链表，这需要先定义一种新的结构，如下：
class MatNode
{
public:
int data;
int row, col;
union { Node<MatNode> *down; List<MatNode> *downrow; };
};
另外，由于这样的十字链表是由多条单链表拼起来的，为了访问每条单链表的保护成员，要声明十字链表类为单链表类的友元。即在class List的声明中添加friend class Matrix;
稀疏矩阵的定义和实现
#ifndef Matrix_H
#define Matrix_H
#include "List.h"
class MatNode
{
public:
int data;
int row, col;
union { Node<MatNode> *down; List<MatNode> *downrow; };
MatNode(int value = 0, Node<MatNode> *p = NULL, int i = 0, int j = 0)
: data(value), down(p), row(i), ......
数据结构学习（C++）——线性链式结构总结（代后记）【1】(2007-04-02 06:11:00)
摘要：看到这个标题，有些人一定松了一口气——这小子可算白话完了，当然了，你要是略有惋惜之情，我真是受宠若惊。但不论你怎么想，写到这里只是告一段落，并没有完，后面还有很大一部分呢，比如树、图、查找、排序——这么多年了，还是这点东西。代后记的意思是，我觉得对前面线性链式结构的总结，对后面的学习有指导意义：从前面的学习中，你能得出如何学习数据结构，以及如何正确看待这门课——如果你能从重复建设中看到这样做的价值，你才能真正理解这门课的意义。
在开始总结前，先整理一下以前的代码，假定你使用的是VC6，你的工程中现在应该有这几个主要文件：Node.h、List.h、Stack.h、Queue.h、CircList.h、DblList.h、Polynomial.h、Expression.h、Matrix.h，一个含有main()的cpp文件。其他的是一些测试文件和一些应用，比如Simulation.h。如果你用的不是VC6，你一定背地里咒骂我多少次了，因为一大堆error和warning。我当初发布的时候，并没有考虑到不同编译器的差异，我觉得只要光使用标准库（仅仅用了iostream.h和stdlib.h），不写怪怪的代码，通用性应该不是问题，但实际上不是这样。所以，我不得不花一些篇幅介绍如何修改以前的代码，所以，这篇文章就只能是【1】了；不过，后面有一个计时器类的源码，就算是一点补偿吧。
VC6、BCB6、Dev-cpp的编译器的差异
这些应该是目前Win32下最常用的IDE环境了，各自的编译器分别是CL.exe、BCC32.exe、G++.exe（就是GNU C++）。我没装BCB6，所以只是拿BCC32来代替。VC6时间比较早（98年），对C++标准支持不是很完善，例如下面的代码：
for (int i = 1; i < 10; i++); for (int i = 1; i < 10; i++);
按照C++标准，i的作用域应该是for循环内。但是在VC6中，出了定义i的for循环，仍然有效，所以，这段代码在VC6中被认为是重复定义。我为了省事，在并列的第二个循环内，把int省略了。现在到了BCC32，它在这方面对于C++标准倒是很支持，于是，象我那样的做法，就是第二个i没定义。让这样的代码同时适应两个编译器的解决办法，要么第2个循环变量换个名字，要么退回......