软考软件设计师数据结构学习C++合集.docx

软考软件设计师数据结构学习C++合集.docx

《软考软件设计师数据结构学习C++合集.docx》由会员分享，可在线阅读，更多相关《软考软件设计师数据结构学习C++合集.docx（69页珍藏版）》请在冰点文库上搜索。

软考软件设计师数据结构学习C++合集

数据结构学习（C++）（合集）

题外话：

先前有一篇文章叫《用C++模板描述的链表、栈、队列（声明与实现）》，当时是第一次发表文章（我才注册没几天），很不成熟，改了又改不说，还弄的老长，不利于阅读。

于是我重写了一下，并且想做成一个系列，这从我的标题可以看出来。

好，言归正传。

本篇为后面一系列文章的序言，旨在说明写作的目的，以及写作的风格；或者说是为自己可能的错误，预先给个托词。

如果您不想听我在这废话，请跳过本篇，直接阅读后面的文章。

但是这样，我不能保证，您在阅读的同时，不会骂我白痴。

为什么写这些文章

这些文章可以说是《数据结构（用面向对象方法与C++描述）》这本书的读书笔记，但也不完全是。

数据结构是计算机专业必修课——几乎每个计算机专业的学生都会推崇他的重要；同时，也是其他专业转修计算机专业的一个难点。

从学习的角度来说，严蔚敏的《数据结构（C语言版）》是本不错的书。

但是，C语言不是描述的理想工具。

《数据结构（C语言版）》的前言里是这样说的：

“虽然C语言不是抽象数据类型的理想描述工具，但鉴于目前和近一、二年内，……并增添了C++语言的引用调用参数传递方式等，构成了一个类C描述语言。

”

从抽象数据类型的定义——一个数学模型以及定义在该模型上的一组操作——可以看出，面向对象语言中类的概念和这个定义很接近，加之C语言的普及，用C++来描述于是就成了顺理成章的事情。

于是，清华在2002年的考研参考书目中对《数据结构》的参考书做了改变，使用《数据结构（用面向对象方法与C++描述）》（殷人昆等编著，ISBN7-302-03405-2/TP1845）作为参考书，而实际上考的也是（废话，不是那叫误导）。

坦白的讲，原书把教学目的和提供实例的目的搞混了，结果是个四不象：

作为教科书，条理不清晰；提供各个方法的实现，也不是很实用，相反，重复建设太多。

至于错误，可能有些是笔误，比如少个友元声明了，不是继承而使用别的类的成员函数没有指明了；还有一些，就是考虑不够周全。

不管怎么说，现在不是挑书的时候，你想考清华的计算机专业研究生吗，这本书是你不二的选择。

我发现读懂此书的最好方法，就是自己按照书上的思路，以及实际应用的分析，自己重新实现各种抽象数据类型。

这样做还有一个好处，为自己将来积累一点财富。

我的写作风格

编译器我选用的是VC6，因此，我不保证我提供的代码在别的编译器也能通过——从头到尾只使用了iostream.h，没有任何别的库，当然更没有MFC，标准的C++代码应该没什么问题。

全部是手工完成的代码，没有使用ClassWizard，主要是不喜欢那些乱七八糟的预处理和注释。

这样完成之后，发现C++的声明和实现分开xx.h+xx..ccp这种文档结构并不招人喜欢——很乱。

于是我采用了单工程单cpp的结构，就是一个工程只有一个cpp文件，放main（），其他的部分都是头文件，声明和实现放在一起——其实这是违反C++规范的，C++要求函数必须声明原型，实际上，我觉得这很罗嗦（我这是典型的C后遗症，以前用TC时为了不声明原型，把函数都放到main（）前面），声明一下原型，我认为这和设定密码需要确认一个道理。

由于使用的IDE环境，把声明单独集中起来作为一个文件已经没有必要——ClassView窗口很好用，就因为如此，我几乎从来不去看类的声明文件。

除非你提供的是一个库，在你的工程中单独的声明文件已经不是必须的了。

当然，这里的前提是从一个空的工程建立你的项目。

如果你使用了AppWizard，我很难想象不使用ClassWizard的。

因为这时文档的结构已经确定了，你所做的实际上是在修修补补。

什么人适合读这些文章

●        刚开始从C过渡到C++的人，看完这些后，会体会到C++的新特性。

●        和我一样研读那本黄皮书的人，希望看完之后能更好的理解和学习。

●        从未编写过超过1000行代码程序的人，这样我们才能达到共鸣。

因为我们从来不使用工具和库文件，做的事都是在编程老手看来很蠢的事。

一些约定

假定你使用的是VC6，先建立一个Win32ConsoleApplication的emptyproject。

后面将陆续往这个工程中添加文件（就是将后面介绍的每一个文件都添加进去，不然到时候找不到xx.h不要埋怨），每一个#ifndefxx_H～#endif和其中的部分为一个头文件，文件名为xx.h。

例如：

#ifndefList_H

#defineList_H

……

#endif

这一大块为一个文件，文件名为List.h

数据结构学习（C++）—队列应用（事件驱动模拟）

我看的两本教科书（《数据结构（C语言版）》还有这本黄皮书）都是以这个讲解队列应用的，而且都是银行营业模拟（太没新意了）。

细比较，这两本书模拟的银行营业的方式还是不同的。

1997版的《数据结构（C语言版）》的银行还是老式的营业模式（毕竟是1997年的事了），现在的很多地方还是这种营业模式——几个窗口同时排队。

这种方式其实不太合理，经常会出现先来的还没有后来的先办理业务（常常前面一个人磨磨蹭蹭，别的队越来越短，让你恨不得把前面那人干掉）。

1999版的这本黄皮书的银行改成了一种挂牌的营业方式，每个来到的顾客发一个号码，如果哪个柜台空闲了，就叫号码最靠前的顾客来办理业务；如果同时几个柜台空闲，就按照一种法则来决定这几个柜台叫号的顺序（最简单的是按柜台号码顺序）。

这样，就能保证顾客按照先来后到的顺序接受服务——因为大家排在一个队里。

这样的营业模式我在北京的西直门工商银行见过，应该说这是比较合理的一种营业模式。

不过，在本文中最重要的是，这样的营业模式比较好模拟（一个队列总比N个队列好操作）。

原书的这部分太难看了，我看的晕晕的，我也不知道按照原书的方法能不能做出来，因为我没看懂（旁白：

靠，你小子这样还来现眼）。

我按照实际情况模拟，实现如下：

#ifndefSimulation_H

#defineSimulation_H

#include

#include

#include

classTeller

{

public:

inttotalCustomerCount;

inttotalServiceTime;

intfinishServiceTime;

Teller（）:

totalCustomerCount（0）,totalServiceTime（0）,

finishServiceTime（0）{}

};

//#definePRINTPROCESS

classSimulation

{

public:

Simulation（）

{

cout<

cout<<"柜台数量：

";cin>>tellerNum;

cout<<"营业时间：

";cin>>simuTime;

cout<<"两个顾客来到的最小间隔时间：

";cin>>arrivalLow;

cout<<"两个顾客来到的最大间隔时间：

";cin>>arrivalHigh;

cout<<"柜台服务最短时间：

";cin>>serviceLow;

cout<<"柜台服务最长时间：

";cin>>serviceHigh;

arrivalRange=arrivalHigh-arrivalLow+1;

serviceRange=serviceHigh-serviceLow+1;

srand（（unsigned）time（NULL））;

}

Simulation（inttellerNum,intsimuTime,intarrivalLow,intarrivalHigh,intserviceLow,intserviceHigh）

:

tellerNum（tellerNum）,simuTime（simuTime）,arrivalLow（arrivalLow）,arrivalHigh（arrivalHigh）,

serviceLow（serviceLow）,serviceHigh（serviceHigh）,

arrivalRange（arrivalHigh-arrivalLow+1）,serviceRange（serviceHigh-serviceLow+1）

{srand（（unsigned）time（NULL））;}

voidInitialize（）

{

curTime=nextTime=0;

customerNum=customerTime=0;

for（inti=1;i<=tellerNum;i++）

{

tellers[i].totalCustomerCount=0;

tellers[i].totalServiceTime=0;

tellers[i].finishServiceTime=0;

}

customer.MakeEmpty（）;

}

voidRun（）

{

Initialize（）;

NextArrived（）;

#ifdefPRINTPROCESS

cout<

cout<<"tellerID";

for（intk=1;k<=tellerNum;k++）cout<<"TELLER"<

cout<

#endif

for（curTime=0;curTime<=simuTime;curTime++）

{

if（curTime>=nextTime）

{

CustomerArrived（）;

NextArrived（）;

}

#ifdefPRINTPROCESS

cout<<"Time:

"<

#endif

for（inti=1;i<=tellerNum;i++）

{

if（tellers[i].finishServiceTime

if（tellers[i].finishServiceTime==curTime&&!

customer.IsEmpty（））

{

intt=NextService（）;

#ifdefPRINTPROCESS

cout<<''<

#endif

CustomerDeparture（）;

tellers[i].totalCustomerCount++;

tellers[i].totalServiceTime+=t;

tellers[i].finishServiceTime+=t;

}

#ifdefPRINTPROCESS

elsecout<<"";

#endif

}

#ifdefPRINTPROCESS

cout<

#endif

}

PrintResult（）;

}

voidPtintSimuPara（）

{

cout<

cout<<"柜台数量：

"<

"<

cout<<"两个顾客来到的最小间隔时间：

"<

cout<<"两个顾客来到的最大间隔时间：

"<

cout<<"柜台服务最短时间：

"<

cout<<"柜台服务最长时间：

"<

}

voidPrintResult（）

{

inttSN=0;

longtST=0;

cout<

cout<<"－－－－－－－－－－－－－模拟结果－－－－－－－－－－－－－－－－－－－";

cout<

for（inti=1;i<=tellerNum;i++）

{

cout<<"TELLER"<

cout<<''<

cout<<''<

cout<<'';

if（tellers[i].totalCustomerCount）

cout<<（float）tellers[i].totalServiceTime/（float）tellers[i].totalCustomerCount;

elsecout<<0;

cout<<""<

}

cout<<"TOTAL"<

if（tSN）cout<<（float）tST/（float）tSN;elsecout<<0;

cout<<""<

cout<<"CustomerNumber:

"<

"<

cout<<"CustomerWaitTime:

"<

";

if（tSN）cout<<（float）customerTime/（float）tSN;elsecout<<0;

cout<

}

private:

inttellerNum;

intsimuTime;

intcurTime,nextTime;

intcustomerNum;

longcustomerTime;

intarrivalLow,arrivalHigh,arrivalRange;

intserviceLow,serviceHigh,serviceRange;

Tellertellers[21];

Queuecustomer;

voidNextArrived（）

{

nextTime+=arrivalLow+rand（）%arrivalRange;

}

intNextService（）

{

returnserviceLow+rand（）%serviceRange;

}

voidCustomerArrived（）

{

customerNum++;

customer.EnQueue（nextTime）;

}

voidCustomerDeparture（）

{

customerTime+=（long）curTime-（long）customer.DeQueue（）;

}

};

#endif

几点说明

●        Run（）的过程是这样的：

curTime是时钟，从开始营业计时，自然流逝到停止营业。

当顾客到的事件发生时（顾客到时间等于当前时间，小于判定是因为个别时候顾客同时到达——输入arrivalLow＝0的情况，而在同一时间，只给一个顾客发号码），给这个顾客发号码（用顾客到时间标示这个顾客，入队，来到顾客数增1）。

当柜台服务完毕时（柜台服务完时间等于当前时间），该柜台服务人数增1，服务时间累加，顾客离开事件发生，下一个顾客到该柜台。

因为柜台开始都是空闲的，所以实际代码和这个有点出入。

最后，停止营业的时候，停止发号码，还在接受服务的顾客继续到服务完，其他还在排队的就散伙了。

●        模拟结果分别是：

各个柜台的服务人数、服务时间、平均服务时间，总的服务人数、服务时间、平均服务时间，来的顾客总数、没被服务的数目（来的太晚了）、接受服务顾客总等待时间、平均等待时间。

●        这个算法效率是比较低的，实际上可以不用队列完成这个模拟（用顾客到时间推动当前时钟，柜台直接公告服务完成时间），但这样就和实际情况有很大差别了——出纳员没等看见人就知道什么时候完？

虽然结果是一样的，但是理解起来很莫名其妙，尤其是作为教学目的讲解的时候。

当然了，实际中为了提高模拟效率，本文的这个算法是不值得提倡的。

●        注释掉的#definePRINTPROCESS，去掉注释符后，在运行模拟的时候，能打印出每个时刻柜台的服务情况（第几个顾客，顾客到达时间，接受服务时间），但只限4个柜台以下，多了的话屏幕就满了（格式就乱了）。

【后记】本来我没打算写这篇，后来，当我开始实现模拟的时候，竟欲罢不能了。

这是数据结构这本书中第一个实际应用的例子，而且也有现实意义。

你可以看出各个柜台在不同的业务密度下的工作强度（要么给哪个柜台出纳员发奖金，要么轮换柜台），各种情况下顾客的等待时间（人都是轮到自己就不着急了），还有各种情况下设立几个柜台合理（很少的空闲时间，很短的等待时间，几乎为零的未服务人数）。

例如这样：

for（inti=1;i<16;i++）

{

Simulationa（i,240,1,4,8,15）;

a.Run（）;

}

你模拟一下就会得出，在不太繁忙的银行，4～5个柜台是合适的——现在的银行大部分都是这样的。

数据结构学习（C++）—单链表（定义与实现）

节点类

#ifndefNode_H

#defineNode_H

templateclassNode//单链节点类

{

public:

Typedata;

Node*link;

Node（）:

data（Type（））,link（NULL）{}

Node（constType&item）:

data（item）,link（NULL）{}

Node（constType&item,Node*p）:

data（item）,link（p）{}

};

#endif

【说明】因为数据结构里用到这个结构的地方太多了，如果用原书那种声明友元的做法，那声明不知道要比这个类的本身长多少。

不如开放成员，事实上，这种结构只是C中的struct，除了为了方便初始化一下，不需要任何的方法，原书那是画蛇添足。

下面可以看到，链表的public部分没有返回Node或者Node*的函数，所以，别的类不可能用这个开放的接口对链表中的节点操作。

【重要修改】原书的缺省构造函数是这样的Node（）:

data（NULL）,link（NULL）{}  。

我原来也是照着写的，结果当我做扩充时发现这样是不对的。

当Type为结构而不是简单类型（int、……），不能简单赋NULL值。

这样做使得定义的模板只能用于很少的简单类型。

显然，这里应该调用Type的缺省构造函数。

 这也要求，用在这里的类一定要有缺省构造函数。

在下面可以看到构造链表时，使用了这个缺省构造函数。

当然，这里是约定带表头节点的链表，不带头节点的情况请大家自己思考。

【闲话】请不要对int*p=newint

（1）;这种语法有什么怀疑，实际上int也可以看成一种class。

单链表类

#ifndefList_H

#defineList_H

#ifndefTURE

#defineTURE1

#endif

#ifndefFALSE

#defineFALSE0

#endif

typedefintBOOL;

#include"Node.h"

templateclassList//单链表定义

{

//基本上无参数的成员函数操作的都是当前节点，即current指的节点

//认为表中“第1个节点”是第0个节点，请注意，即表长为1时，最后一个节点是第0个节点

public:

List（）{first=current=last=newNode;prior=NULL;}

~List（）{MakeEmpty（）;deletefirst;}

voidMakeEmpty（）//置空表

{

Node*q;

while（first->link!

=NULL）

{

q=first->link;

first->link=q->link;

deleteq;

}

Initialize（）;

}

BOOLIsEmpty（）

{

if（first->link==NULL）

{

Initialize（）;

returnTURE;

}

elsereturnFALSE;

}

intLength（）const//计算带表头节点的单链表长度

{

Node*p=first->link;

intcount=0;

while（p!

=NULL）

{

p=p->link;

count++;

}

returncount;

}

Type*Get（）//返回当前节点的数据域的地址

{

if（current!

=NULL）return¤t->data;

elsereturnNULL;

}

BOOLPut（Typeconst&value）//改变当前节点的data，使其为value

{

if（current!

=NULL）

{

current->data=value;

returnTURE;

}

elsereturnFALSE;

}