数据结构经典案例

1.停车场问题停车场管理员的任务就是帮助车主把车停放在停车场中，或者是帮助车主将车开出乘车场。然后停车场中能够停放的车辆数目很多，这就使得让莫辆车开出停车场变得复杂。比如：要开走一辆车，则管理员需要把他前面的车全部暂时清除，然后等这辆车开出后再将这些车重新放入停车场。当然了，这个时候腾出了一个空位置，此位置由后面的车占据。任务：编程模拟这样的情况，这里假设停车场最多可停放5辆车。data.txt记录了某一时间段内，该停车场车辆的到来与离开记录，刚开始，停车场是空的。其中大写字母A--P是车辆的代号，arrives--到来，departs---离开。程序需要从data.txt中读取这些信息，并且用这些数据来模拟停车场的车辆调度情况。data.txt内容如下：AarrivesAdepartsBarrivesCarrivesDarrivesCdepartsEarrivesFarrivesGarrivesBdepartsHarrivesDdepartsEdepartsIarrivesIdepartsJarrivesFdepartsKarrivesLarrivesMarrivesHdepartsNarrivesJdepartsKdepartsOarrivesParrivesPdepartsOdepartsLdeparts实现代码如下：模拟停车场问题.cpp（没有再继续分.h文件，混为一体了，主要.h文件过于简单）[cpp]viewplaincopyprint?1.#ifndefCAR_H2.#defineCAR_H3.#includeiostream4.#includestring5.usingnamespacestd;6.classcar7.{8.public:9.car(string,int);10.stringgetlicense();11.intgetmovedtimes();12.~car();13.voidmove();14.private:15.stringlicense;//车的通行证16.intmovedtimes;//被移动的次数17.};18.#endif19.car::car(stringlicense,intmovedtimes):license(license),movedtimes(0)20.{21.}22.23.stringcar::getlicense()24.{25.returnlicense;26.}27.intcar::getmovedtimes()28.{29.returnmovedtimes;30.}31.voidcar::move()32.{33.movedtimes++;34.}35.car::~car()36.{}37.38.#includefstream39.#includestack40.intmain()41.{42.stringin_filename=data.txt;//数据文件了，包含了停车场内的车辆进出记录43.ifstreaminf(in_filename.c_str());//voidopen(constchar*filename,intmode,intaccess);另外，fstream还有和open()一样的构造函数，对于上例，在定义的时侯就可以打开文件了：44.//fstreamfile1(c://config.sys);45.46.if(!inf)47.{48.cerr文件打开失败!in_filenameendl;49.returnEXIT_FAILURE;50.}51.stackcar*parking_lot,tempstack;//定义两个栈，一个模拟停车场，另外一个用来暂时存放从停车场哪里暂时清除的车，当然最后还是得返回给停车场52.car*pcar;53.stringlicense_plate,action;//分别记录从数据文件中读取的通行证跟行为（到达？离开？）54.//按行读取数据文件55.while(!inf.eof())56.{57.inflicense_plateaction;58.if(action==arrives)//到达59.{60.if(parking_lot.size()5)//栈不满的话，继续入栈61.{62.pcar=newcar(license_plate,0);//这个就不用多罗嗦63.parking_lot.push(pcar);64.65.}66.else67.68.cout抱歉license_plate,停车场已满!endl;69.70.}71.elseif(action==departs)//如果是出发72.{73.//首先得给出判断，此时栈是否为空？而且出发的这辆车的license_plate是否位于栈顶74.while((!parking_lot.empty())&&(parking_lot.top()-getlicense()!=license_plate))//while循环75.{76.tempstack.push(parking_lot.top());77.parking_lot.top()-move();//增加移动次数78.parking_lot.pop();79.//deleteparking_lot.top();此处还不能销毁结点，只是一个短暂的转移罢了80.}81.if(parking_lot.top()-getlicense()==license_plate)//如果要出发的这辆车的license_plate刚好就处在栈顶位置，则直接销毁相关结点，不需要增加移动次数82.{83.coutparking_lot.top()-getlicense()被移动了parking_lot.top()-getmovedtimes()次在这里!endl;//输出被移动的次数84.85.deleteparking_lot.top();86.parking_lot.pop();87.}88.else89.cout神马情况（异常）!endl;90.//接下来还得进行还原，既然有移动那就得还原91.while(!tempstack.empty())92.{93.parking_lot.push(tempstack.top());94.tempstack.pop();95.}96.97.98.}99.100.101.}102.cout还在车库里面的!endl;//最后把还在车库里面的车的license输出，同时关注移动次数103.while(!parking_lot.empty())//用循环依次遍历栈中的元素，也就是对应的车辆了104.{105.coutparking_lot.top()-getlicense()被移动了parking_lot.top()-getmovedtimes()次在这里endl;106.deleteparking_lot.top();//销毁栈顶107.parking_lot.pop();//出栈108.}109.inf.close();110.return0;111.112.}2.用队列解决数据结构经典问题：杨辉三角形问题。111121133114641就是下面的元素是这个元素“肩膀上”的两个元素之和。思路：首先初始化一个队列，元素为1，然后根据这个队列迭代生成任意行的二项式系数。判断用户输入的行数，然后决定循环次数。这些循环中，程序根据杨辉三角的实际构造函数模拟构造过程。每次形成一个新的二项式系数序列，并将这个序列保持在一个新的队列中。本次循环结束后，这个心构造的序列将作为下次循环来构造另一个二项式序列的参照序列。cpp]viewplaincopyprint?1.#includestdio.h2.#includeiostream3.#includeassert.h4.templateclassT5.classLinkQueueNode//结点类定义6.{7.public:8.Tdata;9.LinkQueueNodeT*link;10.LinkQueueNode(constT&value):data(value),link(NULL){}//这里传递类型const11.};12.templateclassT13.classLinkQueue14.{15.LinkQueueNodeT*front;16.LinkQueueNodeT*back;17.public:18.LinkQueue():front(NULL),back(NULL){}19.voidEnQueue(constT&element);//这里也传递const，当然也可以不修改这里，自己再去重载一个参数为const类型的入队函数跟构造函数，道理一样20.TDelQueue();21.T&GetFront();22.voidMakeEmpty();23.boolIsEmpty();24.};25.//实现如下26.templateclassT27.voidLinkQueueT::EnQueue(constT&value)28.{29.LinkQueueNodeT*add=newLinkQueueNodeT(value);30.if(back==NULL)//添加第一个结点，让front指向这个结点31.{32.front=back=add;33.}34.else//如果队列中人家已经有结点，则需要改变back指针35.{36.back-link=add;37.back=back-link;38.39.}40.}41.templateclassT42.TLinkQueueT::DelQueue()43.{44.//首先得判断是否为空队列45.assert(!IsEmpty());46.LinkQueueNodeT*old=front;47.Tdata=old-data;//保留原对头数据48.front=front-link;//移动对头指针49.if(back==old)50.back=NULL;51.deleteold;52.returndata;53.54.}55.templateclassT56.T&LinkQueueT::GetFront()57.{58.assert(!IsEmpty());//断言，这东西挺好使滴59.returnfront-data;60.}61.templateclassT62.voidLinkQueueT::MakeEmpty()63.{64.while(!IsEmpty())65.{66.this-DelQueue();67.}68.69.}70.templateclassT71.boolLinkQueueT::IsEmpty()72.{73.returnfront==NULL;74.}75.#includestring76.usingnamespacestd;77.78.templateclassT//用模板实现方式79.voidevaluate(LinkQueueT&ori,LinkQueueT&target)80.{81.ori.MakeEmpty();82.while(!target.IsEmpty())83.{84.ori.EnQueue(target.DelQueue());85.}86.}87.intmain()88.{89.cout请输入杨辉三角形阶数i(i2):;90.intnum;91.cinnum;92.LinkQueueintori;93.ori.EnQueue(1);94.ori.EnQueue(1);95.LinkQueueintnext;96.for(inti=0;inum-2;i++)97