数据结构处算法分析读书笔记.docx
- 文档编号:17377953
- 上传时间:2023-07-24
- 格式:DOCX
- 页数:150
- 大小:56.01KB
数据结构处算法分析读书笔记.docx
《数据结构处算法分析读书笔记.docx》由会员分享,可在线阅读,更多相关《数据结构处算法分析读书笔记.docx(150页珍藏版)》请在冰点文库上搜索。
数据结构处算法分析读书笔记
数据结构处算法分析――读书笔记
第一章
前言
1.1所选教材
我所选择的教材是《数据结构与算法分析——C语言描述》(原书第2版),英文版的名称是《DataStructuresandAlgorithmAnalysisinC》,作者是:
(美)MarkAllenWeiss。
原书曾被评为20世纪顶尖的30部计算机著作之一。
之所以选这本书,还因为它的简体中文版翻译得相当不错,几乎没有给我的阅读带来什么障碍。
^_^
这本教科书所使用的是C语言,也许很多人会说C语言已经过时了,但是,我认为在数据结构的学习中,应该用尽量简单的语言,以免进入了语言的细枝末节中,反而冲淡了主题。
实际上在国外的许多大学中(甚至中学),数据结构和算法分析的课程是选用Scheme的,例如MIT麻省理工大学极其著名的SICP课程。
呵呵,语言又能说明什么呢?
1.2写作原因
数据结构与算法分析是计算机专业的必修课——但遗憾的是,我在大学阶段并不是计算机专业的学生,以至于没有系统地跟着老师学习过这门课程。
现在我已经工作了,在实际的工作中,我经常感到自己的基础知识不够,有很多问题无法解决。
在经历了一段痛苦的斗争后,我选择了自学的道路,想把这门课程扎扎实实地学好。
教科书中已经给出了大部分的代码,因此,我基本上也只是重复敲入了一次而已(或者是改写成C++),但这并不是没有意义的。
我们在看书的时候经常会觉得自己已经懂了,但如果真的要亲自动手去做了,却会感到无法下手。
我认为,亲自输入一次代码并调试通过,比任何空谈都有效。
在具体的代码实现上,我可能会参考MFC、STL……但也可能会进行一定的修改。
1.3一些约定
我使用的是VisualC++6.0编译器,并将会用C/C++来撰写代码(我可能会用C++改写原书中的例子,以便能用在工作中,但一些地方还是会用C),不会使用任何与平台相关的特性(因此可以保证有比较好的移植性)。
原书中的代码风格跟我平时的代码风格非常相近,但有一些地方我可能会进行一些改动。
我认为数据结构的代码不需要任何界面,因此,请您新建一个工程,类型为Win32ConsoleApplication,即控制台工程。
然后添加一个.h头文件和一个.c/.cpp文件。
头文件中,我一般会写3行固定格式的预编译语句,如下:
#ifndef__LIST_H__
#define__LIST_H__
//TODO:
Addheaderbodycodehere
#endif//__LIST_H__
表示这是一个list.h。
另外,C++操作符new的实现在不同的编译器中都不太一样,在VC6中,如果new失败,则会返回NULL,程序中我用检测返回值是否为NULL来判断new是否成功,但如果这个代码是用别的编译器编译的,则要特别注意别的编译器是否也是用NULL来表示new失败的,否则很可能会导致无法意料的结果。
为了方便调试内存泄漏,我会在一些地方写入这样的代码:
#include
#include
#ifdef_DEBUG
#defineDEBUG_NEWnew(_NORMAL_BLOCK,THIS_FILE,__LINE__)
#endif
#ifdef_DEBUG
#definenewDEBUG_NEW
#undefTHIS_FILE
staticcharTHIS_FILE[]=__FILE__;
#endif
#ifdef_DEBUG
#ifndefASSERT
#defineASSERTassert
#endif
#else//not_DEBUG
#ifndefASSERT
#defineASSERT
#endif
#endif//_DEBUG
以及:
#ifdef_DEBUG
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF|_CRTDBG_LEAK_CHECK_DF);
#endif
在阅读时不用管它们,直接略过即可。
第二章
单链表
链表是最常用、最简单和最基本的数据结构之一。
我们先来看看单链表的实现。
2.1代码实现
单链表的实现如下:
///////////////////////////////////////////////////////////////////////////////
//
//FileName:
slist.h
//Version:
0.10
//Author:
LuoCong
//Date:
2004-12-299:
58:
38
//Comment:
//
///////////////////////////////////////////////////////////////////////////////
#ifndef__SINGLE_LIST_H__
#define__SINGLE_LIST_H__
#include
#include
#ifdef_DEBUG
#defineDEBUG_NEWnew(_NORMAL_BLOCK,THIS_FILE,__LINE__)
#endif
#ifdef_DEBUG
#definenewDEBUG_NEW
#undefTHIS_FILE
staticcharTHIS_FILE[]=__FILE__;
#endif
#ifdef_DEBUG
#ifndefASSERT
#defineASSERTassert
#endif
#else//not_DEBUG
#ifndefASSERT
#defineASSERT
#endif
#endif//_DEBUG
template
classCNode
{
public:
Tdata;
CNode
CNode():
data(T()),next(NULL){}
CNode(constT&initdata):
data(initdata),next(NULL){}
CNode(constT&initdata,CNode
data(initdata),next(p){}
};
template
classCSList
{
protected:
intm_nCount;
CNode
public:
CSList();
CSList(constT&initdata);
~CSList();
public:
intIsEmpty()const;
intGetCount()const;
intInsertBefore(constintpos,constTdata);
intInsertAfter(constintpos,constTdata);
intAddHead(constTdata);
intAddTail(constTdata);
voidRemoveAt(constintpos);
voidRemoveHead();
voidRemoveTail();
voidRemoveAll();
T&GetTail();
TGetTail()const;
T&GetHead();
TGetHead()const;
T&GetAt(constintpos);
TGetAt(constintpos)const;
voidSetAt(constintpos,Tdata);
intFind(constTdata)const;
};
template
inlineCSList
:
CSList():
m_nCount(0),m_pNodeHead(NULL)
{
}
template
inlineCSList
:
CSList(constT&initdata):
m_nCount(0),m_pNodeHead(NULL)
{
AddHead(initdata);
}
template
inlineCSList
:
~CSList()
{
RemoveAll();
}
template
inlineintCSList
:
IsEmpty()const
{
return0==m_nCount;
}
template
inlineintCSList
:
AddHead(constTdata)
{
CNode
pNewNode=newCNode
if(NULL==pNewNode)
return0;
pNewNode->data=data;
pNewNode->next=m_pNodeHead;
m_pNodeHead=pNewNode;
++m_nCount;
return1;
}
template
inlineintCSList
:
AddTail(constTdata)
{
returnInsertAfter(GetCount(),data);
}
//ifsuccess,returnthepositionofthenewnode.
//iffail,return0.
template
inlineintCSList
:
InsertBefore(constintpos,constTdata)
{
inti;
intnRetPos;
CNode
CNode
CNode
pNewNode=newCNode
if(NULL==pNewNode)
{
nRetPos=0;
gotoExit0;
}
pNewNode->data=data;
//ifthelistisempty,replacetheheadnodewiththenewnode.
if(NULL==m_pNodeHead)
{
pNewNode->next=NULL;
m_pNodeHead=pNewNode;
nRetPos=1;
gotoExit1;
}
//isposrangevalid?
ASSERT(1<=pos&&pos<=m_nCount);
//insertbeforeheadnode?
if(1==pos)
{
pNewNode->next=m_pNodeHead;
m_pNodeHead=pNewNode;
nRetPos=1;
gotoExit1;
}
//ifthelistisnotemptyandisnotinsertedbeforeheadnode,
//seektotheposofthelistandinsertthenewnodebeforeit.
pTmpNode1=m_pNodeHead;
for(i=1;i { pTmpNode2=pTmpNode1; pTmpNode1=pTmpNode1->next; } pNewNode->next=pTmpNode1; pTmpNode2->next=pNewNode; nRetPos=pos; Exit1: ++m_nCount; Exit0: returnnRetPos; } //ifsuccess,returnthepositionofthenewnode. //iffail,return0. template inlineintCSList : InsertAfter(constintpos,constTdata) { inti; intnRetPos; CNode CNode pNewNode=newCNode if(NULL==pNewNode) { nRetPos=0; gotoExit0; } pNewNode->data=data; //ifthelistisempty,replacetheheadnodewiththenewnode. if(NULL==m_pNodeHead) { pNewNode->next=NULL; m_pNodeHead=pNewNode; nRetPos=1; gotoExit1; } //isposrangevalid? ASSERT(1<=pos&&pos<=m_nCount); //ifthelistisnotempty, //seektotheposofthelistandinsertthenewnodeafterit. pTmpNode=m_pNodeHead; for(i=1;i { pTmpNode=pTmpNode->next; } pNewNode->next=pTmpNode->next; pTmpNode->next=pNewNode; nRetPos=pos+1; Exit1: ++m_nCount; Exit0: returnnRetPos; } template inlineintCSList : GetCount()const { returnm_nCount; } template inlinevoidCSList : RemoveAt(constintpos) { ASSERT(1<=pos&&pos<=m_nCount); inti; CNode CNode pTmpNode1=m_pNodeHead; //headnode? if(1==pos) { m_pNodeHead=m_pNodeHead->next; gotoExit1; } for(i=1;i { //wewillgetthepreviousnodeofthetargetnodeafter //theforloopfinished,anditwouldbestoredintopTmpNode2 pTmpNode2=pTmpNode1; pTmpNode1=pTmpNode1->next; } pTmpNode2->next=pTmpNode1->next; Exit1: deletepTmpNode1; --m_nCount; } template inlinevoidCSList : RemoveHead() { ASSERT(0! =m_nCount); RemoveAt (1); } template inlinevoidCSList : RemoveTail() { ASSERT(0! =m_nCount); RemoveAt(m_nCount); } template inlinevoidCSList : RemoveAll() { inti; intnCount; CNode nCount=m_nCount; for(i=0;i { pTmpNode=m_pNodeHead->next; deletem_pNodeHead; m_pNodeHead=pTmpNode; } m_nCount=0; } template inlineT&CSList : GetTail() { ASSERT(0! =m_nCount); inti; intnCount; CNode nCount=m_nCount; for(i=1;i { pTmpNode=pTmpNode->next; } returnpTmpNode->data; } template inlineTCSList : GetTail()const { ASSERT(0! =m_nCount); inti; intnCount; CNode nCount=m_nCount; for(i=1;i { pTmpNode=pTmpNode->next; } returnpTmpNode->data; } template inlineT&CSList : GetHead() { ASSERT(0! =m_nCount); returnm_pNodeHead->data; } template inlineTCSList : GetHead()const { ASSERT(0! =m_nCount); returnm_pNodeHead->data; } template inlineT&CSList : GetAt(constintpos) { ASSERT(1<=pos&&pos<=m_nCount); inti; CNode for(i=1;i { pTmpNode=pTmpNode->next; } returnpTmpNode->data; } template inlineTCSList : GetAt(constintpos)const { ASSERT(1<=pos&&pos<=m_nCount); inti; CNode for(i=1;i { pTmpNode=pTmpNode->next; } returnpTmpNode->data; } template inlinevoidCSList : SetAt(constintpos,Tdata) { ASSERT(1<=pos&&pos<=m_nCount); inti; CNode for(i=1;i { pTmpNode=pTmpNode->next; } pTmpNode->data=data; } template inlineintCSList : Find(constTdata)const { inti; intnCount; CNode nCount=m_nCount; for(i=0;i { if(data==pTmpNode->data) returni+1; pTmpNode=pTmpNode->next; } return0; } #endif//__SINGLE_LIST_H__ 调用如下: /////////////////////////////////////////////////////////////////////////////// // //FileName: slist.cpp //Version: 0.10 //Author: LuoCong //Date: 2004-12-2910: 41: 18 //Comment: // /////////////////////////////////////////////////////////////////////////////// #include #include"slist.h" usingnamespacestd; intmain() { inti; intnCount; CSList #ifdef_DEBUG _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF|_CRTDBG_LEAK_CHECK_DF); #endif slist.InsertAfter(slist.InsertAfter(slist.AddHead (1),2),3); slist.InsertAfter(slist.InsertAfter(slist.GetCount(),4),5); slist.InsertAfter(slist.GetCount(),6); slist.AddTail(10); slist.InsertAfter(slist.InsertBefore(slist.GetCount(),7),8); slist.SetAt(slist.GetCo
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 分析 读书笔记
![提示](https://static.bingdoc.com/images/bang_tan.gif)