读书笔记之《数据结构与算法分析——c语言描述》(原书第版)

《读书笔记之《数据结构与算法分析——c语言描述》(原书第版)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构处算法分析――读书笔记　第一章前言1.1所选教材我所选择的教材是《数据结构与算法分析——C语言描述》（原书第2版），英文版的名称是《DataStructuresandAlgorithmAnalysisinC》，作者是：(美)MarkAllenWeiss。原书曾被评为20世纪顶尖的30部计算机著作之一。之所以选这本书，还因为它的简体中文版翻译得相当不错，几乎没有给我的阅读带来什么障碍。^_^这本教科书所使用的是C语言，也许很多人会说C语言已经过时了，但是，我认为在数据结构的学习中，应该用尽量简单的语言，以免进入了语言的细枝末节中

2、，反而冲淡了主题。实际上在国外的许多大学中（甚至中学），数据结构和算法分析的课程是选用Scheme的，例如MIT麻省理工大学极其著名的SICP课程。呵呵，语言又能说明什么呢？1.2写作原因数据结构与算法分析是计算机专业的必修课——但遗憾的是，我在大学阶段并不是计算机专业的学生，以至于没有系统地跟着老师学习过这门课程。现在我已经工作了，在实际的工作中，我经常感到自己的基础知识不够，有很多问题无法解决。在经历了一段痛苦的斗争后，我选择了自学的道路，想把这门课程扎扎实实地学好。教科书中已经给出了大部分的代码，因此，我基本上也只是重复敲入了一

3、次而已（或者是改写成C++），但这并不是没有意义的。我们在看书的时候经常会觉得自己已经懂了，但如果真的要亲自动手去做了，却会感到无法下手。我认为，亲自输入一次代码并调试通过，比任何空谈都有效。在具体的代码实现上，我可能会参考MFC、STL……但也可能会进行一定的修改。1.3一些约定我使用的是VisualC++6.0编译器，并将会用C/C++来撰写代码（我可能会用C++改写原书中的例子，以便能用在工作中，但一些地方还是会用C），不会使用任何与平台相关的特性（因此可以保证有比较好的移植性）。原书中的代码风格跟我平时的代码风格非常相近，但有

4、一些地方我可能会进行一些改动。我认为数据结构的代码不需要任何界面，因此，请您新建一个工程，类型为Win32ConsoleApplication，即控制台工程。然后添加一个.h头文件和一个.c/.cpp文件。头文件中，我一般会写3行固定格式的预编译语句，如下：#ifndef__LIST_H__#define__LIST_H__//TODO:Addheaderbodycodehere#endif//__LIST_H__表示这是一个list.h。另外，C++操作符new的实现在不同的编译器中都不太一样，在VC6中，如果new失败，则会返回N

5、ULL，程序中我用检测返回值是否为NULL来判断new是否成功，但如果这个代码是用别的编译器编译的，则要特别注意别的编译器是否也是用NULL来表示new失败的，否则很可能会导致无法意料的结果。为了方便调试内存泄漏，我会在一些地方写入这样的代码：#include#include#ifdef_DEBUG#defineDEBUG_NEWnew(_NORMAL_BLOCK,THIS_FILE,__LINE__)#endif#ifdef_DEBUG#definenewDEBUG_NEW#undefTHIS

6、_FILEstaticcharTHIS_FILE[]=__FILE__;#endif#ifdef_DEBUG#ifndefASSERT#defineASSERTassert#endif#else//not_DEBUG#ifndefASSERT#defineASSERT#endif#endif//_DEBUG以及：#ifdef_DEBUG_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF

7、_CRTDBG_LEAK_CHECK_DF);#endif在阅读时不用管它们，直接略过即可。第二章单链表链表是最常用、最简单和最基

8、本的数据结构之一。我们先来看看单链表的实现。2.1代码实现单链表的实现如下：///////////////////////////////////////////////////////////////////////////////////FileName:slist.h//Version:0.10//Author:LuoCong//Date:2004-12-299:58:38//Comment://///////////////////////////////////////////////////////////////////

9、////////////#ifndef__SINGLE_LIST_H__#define__SINGLE_LIST_H__#include#include#ifdef_DEBUG#d