第一章

前言

1.1  所选教材

我所选择的教材是《数据结构与算法分析——C语言描述》(原书第2版),英文版的名称是《Data Structures and Algorithm Analysis in C》,作者是:(美)Mark Allen Weiss。原书曾被评为20世纪顶尖的30部计算机著作之一。之所以选这本书,还因为它的简体中文版翻译得相当不错,几乎没有给我的阅读带来什么障碍。^_^

这本教科书所使用的是C语言,也许很多人会说C语言已经过时了,但是,我认为在数据结构的学习中,应该用尽量简单的语言,以免进入了语言的细枝末节中,反而冲淡了主题。实际上在国外的许多大学中(甚至中学),数据结构和算法分析的课程是选用Scheme的,例如MIT麻省理工大学极其著名的SICP课程。呵呵,语言又能说明什么呢?

1.2  写作原因

数据结构与算法分析是计算机专业的必修课——但遗憾的是,我在大学阶段并不是计算机专业的学生,以至于没有系统地跟着老师学习过这门课程。现在我已经工作了,在实际的工作中,我经常感到自己的基础知识不够,有很多问题无法解决。在经历了一段痛苦的斗争后,我选择了自学的道路,想把这门课程扎扎实实地学好。

教科书中已经给出了大部分的代码,因此,我基本上也只是重复敲入了一次而已(或者是改写成C++),但这并不是没有意义的。我们在看书的时候经常会觉得自己已经懂了,但如果真的要亲自动手去做了,却会感到无法下手。我认为,亲自输入一次代码并调试通过,比任何空谈都有效。

在具体的代码实现上,我可能会参考MFC、STL……但也可能会进行一定的修改。

1.3  一些约定

我使用的是Visual C++ 6.0编译器,并将会用C/C++来撰写代码(我可能会用C++改写原书中的例子,以便能用在工作中,但一些地方还是会用C),不会使用任何与平台相关的特性(因此可以保证有比较好的移植性)。原书中的代码风格跟我平时的代码风格非常相近,但有一些地方我可能会进行一些改动。

我认为数据结构的代码不需要任何界面,因此,请您新建一个工程,类型为Win32 Console Application,即控制台工程。然后添加一个.h头文件和一个.c/.cpp文件。头文件中,我一般会写3行固定格式的预编译语句,如下:

#ifndef __LIST_H__
#define __LIST_H__

// TODO: Add header body code here

#endif  // __LIST_H__

表示这是一个list.h。

另外,C++操作符new的实现在不同的编译器中都不太一样,在VC6中,如果new失败,则会返回NULL,程序中我用检测返回值是否为NULL来判断new是否成功,但如果这个代码是用别的编译器编译的,则要特别注意别的编译器是否也是用NULL来表示new失败的,否则很可能会导致无法意料的结果。

为了方便调试内存泄漏,我会在一些地方写入这样的代码:

#include <assert.h>
#include <crtdbg.h>

#ifdef _DEBUG
#define DEBUG_NEW new (_NORMAL_BLOCK, THIS_FILE, __LINE__)
#endif

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

#ifdef _DEBUG
#ifndef ASSERT
#define ASSERT  assert
#endif
#else   // not _DEBUG
#ifndef ASSERT
#define ASSERT
#endif
#endif  // _DEBUG

以及:

#ifdef _DEBUG
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

在阅读时不用管它们,直接略过即可。

1.4  历史记录

[2005-01-30] 图的遍历一章。
[2005-01-28] 图的储存一章。
[2005-01-24] 排序一章。
[2005-01-21] AVL树一章。
[2005-01-18] 二叉搜索树一章。
[2005-01-14] 二叉树一章。
[2005-01-09] 递归一章。
[2005-01-08] 队列一章。
[2005-01-07] 栈一章。
[2005-01-05] 循环链表一章。
[2005-01-04] 双链表一章。
[2004-12-30] 单链表一章。

1.5  联系方式

作者:罗聪
主页:http://www.luocong.com
E-Mail:admin[AT]luocong.com