2013软件工程数据结构实验教案

2013软件工程数据结构实验教案1实验教案实验一栈和队列重点：1.掌握如何使用STL中的栈2.掌握如何自己编写栈的代码难点：用数组实现栈的原理，并能用c++描述具体实验讲解如下：本实验是要通过几段代码的编写，熟悉栈和队列的编写和应用在实验指导书中有4个题目，其中题目1、2、3是关于栈的，题目4是关于队列的。其中题目1难度小，题目2和题目3是有联系的，经过努力可以做出，但是题目4难度大些，属于选作内容1.题目一（STL中的栈）读懂实验指导书中的Task1中的程序（使用栈进行序列的顺序反转），并编译运行，通过此了解如果要实现一个栈类，里面需要的基本的成员函数。这个程序在书上也有。（1）由于程序是用了STL（标准模板库，可以简单的看成是一个函数库，在其中有各种有用的类、函数和算法），栈在其中有实现。栈在STL中的实现用到了类模板，也就是说其栈是独立于类型的，模板提供参数化类型，也就是能将类型名作为参数传递给接收方来建立类或函数。比如stackdoublenumbers;中就是声明了一个栈，这个栈中存放的数据类型为double。（2）注意要使用c++的输入输出需要加上几行语句如下，因为cout和cin是在命名空间std中的：#includeiostreamusingnamespacestd;2.题目二、题目三（自己编写栈）这里可以把题目二和题目三合成一个题目，在一个程序中完成就可以了。合并后的题目如下：自己编程程序实现一个简单的栈，并用于替换题目1中对标准模板库中的栈的使用，同时对自己实现的栈的功能进行扩充，添加实现如下几个函数(a)clear(b)full(c)size。使用新添加的栈函数，显示在进行数字序列反转时输入的十进制数的个数。注意：(1)实验题目文档中已经把大部分的代码都给出来了。栈可以用链表或者数组实现，这里是用数组实现。(2)实验题目中给出的仅仅是部分的代码，自己还需要在看懂的前提下，进行修改补充，才可以达到具体的要求，不明白的地方也可以参考书上这一部分。一些补充代码如下：2013软件工程数据结构实验教案2enumError_code{success,underflow,overflow};3.题目四（选作）这个题目的主要目的是熟悉队列这个数据结构，而为了说明问题又用了一个模拟飞机场的程序，因此这个实验项目在程序的找错误调试编译，读源代码上对大家也是一个锻炼。仔细阅读教科书中关于模拟飞机场这一部分，阅读源代码。实验题目中的源代码并不完整并且有些语法等等的错误，其缺少生成随机数这一个类，附录一会把这个类给大家，有兴趣的话，可以看教科书中的附录，有些介绍。另外，也可以使用随机数生成函数（当然主函数要做相应修改去使用现有的随机数生成函数），使用示例见附录二。另外大家把代码读懂后就可以复制粘贴到编译环境中了，主要是读懂代码。但是，一定要知道，这样直接粘贴的代码并不能直接运行，需要修改其中的一些bug。这个题目的要求是能读懂代码，明白实现，而且要把代码放到VC中编译调试，使其能正常运行。并通过此，能对程序的编译调试查找错误较为熟悉。注意，一定要使警告也为0个。一些补充代码如下：(1)enumPlane_status{null,arriving,departing};(2)enumError_code{success,underflow,overflow};(3)typedefPlaneQueue_entry;一个模拟时间点可以有飞机想起飞，或者有飞机想降落。但是该模拟时间点只能有一架飞机能起飞或者一架飞机能降落（假设飞机场只有一条跑道）具有的类如下：(1)Extended_queue：队列，实际上是作为飞机场的等待起飞和降落的排队队列，该队列里面放的是飞机类(2)Plane：飞机类(3)Rumway：飞机场类，该类中有两个队列作为类成员，分别是等待起飞和降落的队列。由于假设飞机场只有一条跑道，所以，同一时间点只能有一架飞机起飞或者降落。(4)Random附录一下面是Random类，用于生成随机数，核心代码来自教科书的附录//Random.h#ifndefRANDOM_H_#defineRANDOM_H_classRandom{public:Random(boolpseudo=true);//declarerandom-numbergenerationmethodshere2013软件工程数据结构实验教案3doublerandom_real();intpoisson(doublemean);private:intreseed();//re-randomizetheseedintseed;intmultiplier,add_on;//constantsforuseinarithmeticoperations};#endif//Random.cpp#includeRandom.h#includelimits.h#includetime.h#includemath.hintRandom::reseed()//Post:Theseedisreplacedbyapsuedorandomsuccessor{seed=seed*multiplier+add_on;returnseed;}Random::Random(boolpseudo){/*Post:Thevaluesofseed,add-on,andmultiplierareinitialized.Theseedisinitializedrandomlyonlyifpseudo==false*/if(pseudo){seed=1;}else{seed=static_castint(time(NULL)%INT_MAX);multiplier=2743;add_on=5923;}}doubleRandom::random_real(){/*Post:Arandomrealnumberbetween0and1isreturned*/doublemax=INT_MAX+1.0;doubletemp=reseed();if(temp0)2013软件工程数据结构实验教案4{temp=temp+max;}returntemp/max;}intRandom::poisson(doublemean){/*Post:Arandominteger,reflectingaPoissondistributionwithparametermean,isreturn.*/doublelimit=exp(-mean);doubleproduct=random_real();intcount=0;while(productlimit){count++;product*=random_real();}returncount;}附录二//crt_rand.c//Thisprogramseedstherandom-numbergenerator//withthetime,thenexercisestherandfunction.//#includestdlib.h#includestdio.h#includetime.hvoidSimpleRandDemo(intn){//Printnrandomnumbers.inti;for(i=0;in;i++)printf(%6d\n,rand());}voidRangedRandDemo(intrange_min,intrange_max,intn){//Generaterandomnumbersinthehalf-closedinterval//[range_min,range_max).Inotherwords,2013软件工程数据结构实验教案5//range_min=randomnumberrange_maxinti;for(i=0;in;i++){intu=(double)rand()/(RAND_MAX+1)*(range_max-range_min)+range_min;printf(%6d\n,u);}}intmain(void){//Seedtherandom-numbergeneratorwiththecurrenttimesothat//thenumberswillbedifferenteverytimewerun.srand((unsigned)time(NULL));SimpleRandDemo(10);printf(\n);RangedRandDemo(-100,100,10);}结果：2203618330116512746418093328411785146861144711285744827659664-5-42-55662013软件工程数据结构实验教案6实验教案实验二多项式加减法重点：用队列实现多项式加减法难点：1.如何用队列表示多项式2.在用队列表示多项式时，如果涉及多项式类，则队列类和多项式类之间的关系如何，即理清多项式类与队列类的关系3.正确用代码实现具体讲解如下：本实验通过编写一个程序实现两个多项式的加法和减法运算，进一步掌握常用的数据结构：栈和队列。多个多项式连续的加减法，可以用栈为辅助结构实现，该部分作为选作内容。存放多项式的数据结构实现多项式的加减法，首先考虑是用什么样的数据结构保存多项式。(1)链表：一个节点node是多项式的一项，本次实验不涉及(2)队列：队列中的一项是多项式的一项，本实验是用队列作为保存多项式的数据结构。教科书中详细描述了一种实现多项式运算的算法。a)用户从键盘输入要参与运算的多项式每一项的系数和指数，输入多个多项式后就可以对多个多项式进行运算（加法、减法等）。b)为了使多项式的加法算法相对简单些，有一个约定，就是用户在输入多项式的系数和指数的时候，约定用户输入的指数是降幂排列的（如果有时间可以想想如果用户输入每个多项式的时候并不是把指数降幂排列，你该如何编写代码）。课本中使用队列来存储每个多项式正是利用了用户输入的指数是降幂排列的这个特点（直接对队列的首尾进行操作）。这样简化后并巧妙的利用队列，使得多项式运算的算法相对简单。多项式的加法和减法运算简单的说就是比较多项式的指数，然后把指数相同的项对应的系数相加减。课本中实现的多项式算法使用的数据结构（1）栈：第一个实验已经实现了一个简单的栈，在这个实验中可以直接使用，或者使用标准模板库中的stack。为了保存多个多项式，使用了栈（用栈是为了进行多个多项式的加减）。在进行多项式运算的时候，是让弹出栈顶的两个元素（多项式）进行运算（加、减等），再把结果压回栈中。实现多个多项式连续的加减法，这部分内容是选做。本实验仅需要实现两个多项式的加减法就可以。（2）队列：用一个队列保存用户输入的一个多项式。课本中已经基本实现了一个队列，2013软件工程数据结构实验教案7简单的添加一些成员就可以使用了，或者使用标准模板库中的queue实验题目文档中给出了用户输入输出的几个函数，直接就可以使用了。但是需要自己编写实现一个多项式类。注意本次实验看上去简单，比如书上已经有绝大部分代码，而且没有的一些代码在英文的实验题目文档中也是给出了，自己要做的看上去只是要将书上的代码组织起来，并且添加一个多项式的减法函数就可以了。但是，需要注意，书上有关队列，栈的代码比较分散，而且，如果要使用书上代码的结构会涉及多个类（栈，队列，多项式类），还涉及到继承，如果对于c++并不熟悉，完全照书上的代码实现起来会有难度。为了顺利完成实验，可以使用标准模板库中的栈和队列来进行算法实现，可以看看附录1，2，3建议大家自己参考书上的算法，然后自己写代码，而不是仅仅简单的将书上的代码简单的照搬敲打到电脑中（前面介绍了，直接使用书上的代码并没有看上的那样简单）。自己写代码的时候可以使用标准模板库中的栈和队列，不需要自己从头再编写栈和队列的代码了。附录1：stack//stack_pop.cpp#includestack#includeiostream