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

1、软考软件设计师数据结构学习C+合集数据结构学习（C+）（合集）题外话：先前有一篇文章叫用C+模板描述的链表、栈、队列（声明与实现），当时是第一次发表文章（我才注册没几天），很不成熟，改了又改不说，还弄的老长，不利于阅读。于是我重写了一下，并且想做成一个系列，这从我的标题可以看出来。好，言归正传。本篇为后面一系列文章的序言，旨在说明写作的目的，以及写作的风格；或者说是为自己可能的错误，预先给个托词。如果您不想听我在这废话，请跳过本篇，直接阅读后面的文章。但是这样，我不能保证，您在阅读的同时，不会骂我白痴。为什么写这些文章这些文章可以说是数据结构（用面向对象方法与C+描述）这本书的读书笔记，但也不

2、完全是。数据结构是计算机专业必修课几乎每个计算机专业的学生都会推崇他的重要；同时，也是其他专业转修计算机专业的一个难点。从学习的角度来说，严蔚敏的数据结构（C语言版）是本不错的书。但是，C语言不是描述的理想工具。数据结构（C语言版）的前言里是这样说的：“虽然C语言不是抽象数据类型的理想描述工具，但鉴于目前和近一、二年内，并增添了C+语言的引用调用参数传递方式等，构成了一个类C描述语言。”从抽象数据类型的定义一个数学模型以及定义在该模型上的一组操作可以看出，面向对象语言中类的概念和这个定义很接近，加之C语言的普及，用C+来描述于是就成了顺理成章的事情。于是，清华在2002年的考研参考书目中对数据

3、结构的参考书做了改变，使用数据结构（用面向对象方法与C+描述）（殷人昆等编著，ISBN 7-302-03405-2/TP1845）作为参考书，而实际上考的也是（废话，不是那叫误导）。坦白的讲，原书把教学目的和提供实例的目的搞混了，结果是个四不象：作为教科书，条理不清晰；提供各个方法的实现，也不是很实用，相反，重复建设太多。至于错误，可能有些是笔误，比如少个友元声明了，不是继承而使用别的类的成员函数没有指明了；还有一些，就是考虑不够周全。不管怎么说，现在不是挑书的时候，你想考清华的计算机专业研究生吗，这本书是你不二的选择。我发现读懂此书的最好方法，就是自己按照书上的思路，以及实际应用的分析，自己

4、重新实现各种抽象数据类型。这样做还有一个好处，为自己将来积累一点财富。我的写作风格编译器我选用的是VC6，因此，我不保证我提供的代码在别的编译器也能通过从头到尾只使用了iostream.h，没有任何别的库，当然更没有MFC，标准的C+代码应该没什么问题。全部是手工完成的代码，没有使用ClassWizard，主要是不喜欢那些乱七八糟的预处理和注释。这样完成之后，发现C+的声明和实现分开xx.h+xx.ccp这种文档结构并不招人喜欢很乱。于是我采用了单工程单cpp的结构，就是一个工程只有一个cpp文件，放main()，其他的部分都是头文件，声明和实现放在一起其实这是违反C+规范的，C+要求函数必须

5、声明原型，实际上，我觉得这很罗嗦（我这是典型的C后遗症，以前用TC时为了不声明原型，把函数都放到main()前面），声明一下原型，我认为这和设定密码需要确认一个道理。由于使用的IDE环境，把声明单独集中起来作为一个文件已经没有必要ClassView窗口很好用，就因为如此，我几乎从来不去看类的声明文件。除非你提供的是一个库，在你的工程中单独的声明文件已经不是必须的了。当然，这里的前提是从一个空的工程建立你的项目。如果你使用了AppWizard，我很难想象不使用ClassWizard的。因为这时文档的结构已经确定了，你所做的实际上是在修修补补。什么人适合读这些文章 刚开始从C过渡到C+的人，看完这

6、些后，会体会到C+的新特性。 和我一样研读那本黄皮书的人，希望看完之后能更好的理解和学习。 从未编写过超过1000行代码程序的人，这样我们才能达到共鸣。因为我们从来不使用工具和库文件，做的事都是在编程老手看来很蠢的事。一些约定假定你使用的是VC6，先建立一个Win32 Console Application的empty project。后面将陆续往这个工程中添加文件（就是将后面介绍的每一个文件都添加进去，不然到时候找不到xx.h不要埋怨），每一个#ifndef xx_H#endif和其中的部分为一个头文件，文件名为xx.h。例如：#ifndef List_H#define List_H#end

7、if这一大块为一个文件，文件名为List.h数据结构学习（C+）队列应用（事件驱动模拟）我看的两本教科书（数据结构（C语言版）还有这本黄皮书）都是以这个讲解队列应用的，而且都是银行营业模拟（太没新意了）。细比较，这两本书模拟的银行营业的方式还是不同的。1997版的数据结构（C语言版）的银行还是老式的营业模式（毕竟是1997年的事了），现在的很多地方还是这种营业模式几个窗口同时排队。这种方式其实不太合理，经常会出现先来的还没有后来的先办理业务（常常前面一个人磨磨蹭蹭，别的队越来越短，让你恨不得把前面那人干掉）。1999版的这本黄皮书的银行改成了一种挂牌的营业方式，每个来到的顾客发一个号码，如果哪

8、个柜台空闲了，就叫号码最靠前的顾客来办理业务；如果同时几个柜台空闲，就按照一种法则来决定这几个柜台叫号的顺序（最简单的是按柜台号码顺序）。这样，就能保证顾客按照先来后到的顺序接受服务因为大家排在一个队里。这样的营业模式我在北京的西直门工商银行见过，应该说这是比较合理的一种营业模式。不过，在本文中最重要的是，这样的营业模式比较好模拟（一个队列总比N个队列好操作）。原书的这部分太难看了，我看的晕晕的，我也不知道按照原书的方法能不能做出来，因为我没看懂（旁白：靠，你小子这样还来现眼）。我按照实际情况模拟，实现如下：#ifndef Simulation_H#define Simulation_H #i

9、nclude #include #include class Tellerpublic: int totalCustomerCount; int totalServiceTime; int finishServiceTime; Teller() :totalCustomerCount(0), totalServiceTime(0), finishServiceTime(0) ;/#define PRINTPROCESSclass Simulationpublic: Simulation() cout endl 输入模拟参数 endl; cout tellerNum; cout simuTime

10、; cout arrivalLow; cout arrivalHigh; cout serviceLow; cout serviceHigh; arrivalRange = arrivalHigh - arrivalLow + 1; serviceRange = serviceHigh - serviceLow + 1; srand(unsigned)time(NULL); Simulation(int tellerNum, int simuTime, int arrivalLow, int arrivalHigh, int serviceLow, int serviceHigh) : tel

11、lerNum(tellerNum), simuTime(simuTime), arrivalLow(arrivalLow), arrivalHigh(arrivalHigh), serviceLow(serviceLow), serviceHigh(serviceHigh), arrivalRange(arrivalHigh - arrivalLow + 1), serviceRange(serviceHigh - serviceLow + 1) srand(unsigned)time(NULL); void Initialize() curTime = nextTime = 0; custo

12、merNum = customerTime = 0; for (int i = 1; i = tellerNum; i+) tellersi.totalCustomerCount = 0; tellersi.totalServiceTime = 0; tellersi.finishServiceTime = 0; customer.MakeEmpty(); void Run() Initialize(); NextArrived();#ifdef PRINTPROCESS cout endl; cout tellerID; for (int k = 1; k = tellerNum; k+)

13、cout TELLER k; cout endl;#endif for (curTime = 0; curTime = nextTime) CustomerArrived(); NextArrived(); #ifdef PRINTPROCESS cout Time: curTime ;#endif for (int i = 1; i = tellerNum; i+) if (tellersi.finishServiceTime curTime) tellersi.finishServiceTime = curTime; if (tellersi.finishServiceTime = cur

14、Time & !customer.IsEmpty() int t = NextService();#ifdef PRINTPROCESS cout customerNum + 1 ( customer.GetFront() , t );#endif CustomerDeparture(); tellersi.totalCustomerCount+; tellersi.totalServiceTime += t; tellersi.finishServiceTime += t; #ifdef PRINTPROCESS else cout ;#endif #ifdef PRINTPROCESS c

15、out endl;#endif PrintResult(); void PtintSimuPara() cout endl 模拟参数 endl; cout 柜台数量： tellerNum 营业时间： simuTime endl; cout 两个顾客来到的最小间隔时间： arrivalLow endl; cout 两个顾客来到的最大间隔时间： arrivalHigh endl; cout 柜台服务最短时间： serviceLow endl; cout 柜台服务最长时间： serviceHigh endl; void PrintResult() int tSN = 0; long tST = 0;

16、 cout endl; cout 模拟结果; cout endl tellerID ServiceNum ServiceTime AverageTime endl; for (int i = 1; i = tellerNum; i+) cout TELLER i; cout tellersi.totalCustomerCount ; tSN += tellersi.totalCustomerCount; cout tellersi.totalServiceTime ; tST += (long)tellersi.totalServiceTime; cout ; if (tellersi.tot

17、alCustomerCount) cout (float)tellersi.totalServiceTime/(float)tellersi.totalCustomerCount; else cout 0; cout endl; cout TOTAL tSN tST ; if (tSN) cout (float)tST/(float)tSN; else cout 0; cout endl; cout Customer Number: customerNum no Service: customerNum - tSN endl; cout Customer WaitTime: customerT

18、ime AvgWaitTime: ; if (tSN) cout (float)customerTime/(float)tSN; else cout 0; cout endl; private: int tellerNum; int simuTime; int curTime, nextTime; int customerNum; long customerTime; int arrivalLow, arrivalHigh, arrivalRange; int serviceLow, serviceHigh, serviceRange; Teller tellers21; Queue cust

19、omer; void NextArrived() nextTime += arrivalLow + rand() % arrivalRange; int NextService() return serviceLow + rand() % serviceRange; void CustomerArrived() customerNum+; customer.EnQueue(nextTime); void CustomerDeparture() customerTime += (long)curTime - (long)customer.DeQueue(); ; #endif几点说明 Run()

20、的过程是这样的：curTime是时钟，从开始营业计时，自然流逝到停止营业。当顾客到的事件发生时（顾客到时间等于当前时间，小于判定是因为个别时候顾客同时到达输入arrivalLow0的情况，而在同一时间，只给一个顾客发号码），给这个顾客发号码（用顾客到时间标示这个顾客，入队，来到顾客数增1）。当柜台服务完毕时（柜台服务完时间等于当前时间），该柜台服务人数增1，服务时间累加，顾客离开事件发生，下一个顾客到该柜台。因为柜台开始都是空闲的，所以实际代码和这个有点出入。最后，停止营业的时候，停止发号码，还在接受服务的顾客继续到服务完，其他还在排队的就散伙了。 模拟结果分别是：各个柜台的服务人数、服务时间

21、、平均服务时间，总的服务人数、服务时间、平均服务时间，来的顾客总数、没被服务的数目（来的太晚了）、接受服务顾客总等待时间、平均等待时间。 这个算法效率是比较低的，实际上可以不用队列完成这个模拟（用顾客到时间推动当前时钟，柜台直接公告服务完成时间），但这样就和实际情况有很大差别了出纳员没等看见人就知道什么时候完？虽然结果是一样的，但是理解起来很莫名其妙，尤其是作为教学目的讲解的时候。当然了，实际中为了提高模拟效率，本文的这个算法是不值得提倡的。 注释掉的#define PRINTPROCESS，去掉注释符后，在运行模拟的时候，能打印出每个时刻柜台的服务情况（第几个顾客，顾客到达时间，接受服务时间

22、），但只限4个柜台以下，多了的话屏幕就满了（格式就乱了）。【后记】本来我没打算写这篇，后来，当我开始实现模拟的时候，竟欲罢不能了。这是数据结构这本书中第一个实际应用的例子，而且也有现实意义。你可以看出各个柜台在不同的业务密度下的工作强度（要么给哪个柜台出纳员发奖金，要么轮换柜台），各种情况下顾客的等待时间（人都是轮到自己就不着急了），还有各种情况下设立几个柜台合理（很少的空闲时间，很短的等待时间，几乎为零的未服务人数）。例如这样：for (int i = 1; i 16; i+) Simulation a(i,240,1,4,8,15); a.Run();你模拟一下就会得出，在不太繁忙的银行，

23、45个柜台是合适的现在的银行大部分都是这样的。数据结构学习（C+）单链表（定义与实现）节点类#ifndef Node_H#define Node_Htemplate class Node /单链节点类public: Type data; Node *link; Node() : data(Type(), link(NULL) Node(const Type &item) : data(item), link(NULL) Node(const Type &item, Node *p) : data(item), link(p) ;#endif【说明】因为数据结构里用到这个结构的地方太多了，如果用

24、原书那种声明友元的做法，那声明不知道要比这个类的本身长多少。不如开放成员，事实上，这种结构只是C中的struct，除了为了方便初始化一下，不需要任何的方法，原书那是画蛇添足。下面可以看到，链表的public部分没有返回Node或者Node*的函数，所以，别的类不可能用这个开放的接口对链表中的节点操作。【重要修改】原书的缺省构造函数是这样的Node() : data(NULL), link(NULL) 。我原来也是照着写的，结果当我做扩充时发现这样是不对的。当Type为结构而不是简单类型（int、），不能简单赋NULL值。这样做使得定义的模板只能用于很少的简单类型。显然，这里应该调用Type的缺

25、省构造函数。这也要求，用在这里的类一定要有缺省构造函数。在下面可以看到构造链表时，使用了这个缺省构造函数。当然，这里是约定带表头节点的链表，不带头节点的情况请大家自己思考。【闲话】请不要对int *p = new int(1);这种语法有什么怀疑，实际上int也可以看成一种class。单链表类#ifndef List_H#define List_H#ifndef TURE#define TURE 1#endif#ifndef FALSE#define FALSE 0#endiftypedef int BOOL;#include Node.htemplate class List /单链表定义/

26、基本上无参数的成员函数操作的都是当前节点，即current指的节点/认为表中“第1个节点”是第0个节点，请注意，即表长为1时，最后一个节点是第0个节点public: List() first = current = last = new Node; prior = NULL; List() MakeEmpty(); delete first; void MakeEmpty() /置空表 Node *q; while (first-link != NULL) q = first-link; first-link = q-link; delete q; Initialize(); BOOL IsE

27、mpty() if (first-link = NULL) Initialize(); return TURE; else return FALSE; int Length() const /计算带表头节点的单链表长度 Node *p = first-link; int count = 0; while (p != NULL) p = p-link; count+; return count; Type *Get()/返回当前节点的数据域的地址 if (current != NULL) return ¤t-data; else return NULL; BOOL Put(Type const &value)/改变当前节点的data，使其为value if (current != NULL) current-data = value; return TURE; else return FALSE;