实验一 栈和队列实验

1、实验一 栈和队列一、实验目的1、通过几个小代码的编写，熟悉栈和队列2、熟悉VC环境（VC 6或VC.net），会在其中编写调试运行c+代码，并理解多文件项目的组织，为以后的实验编程做准备3、初步掌握在VC环境中进行代码的调试二、实验内容在实验题目文档中有4个题目，其中题目1、2、3是关于栈的，题目4是关于队列的 ，要求一次实验完成所有的题目1.题目一读懂实验题目文档中的Task1中的程序（使用栈进行序列的顺序反转），并编译运行，通过此了解如果要实现一个栈类，里面需要的基本的成员函数。这个程序在书上也有。（1）由于程序是用了STL（标准模板库，可以简单的看成是一个函数库，在其中有各种有用的类、函

2、数和算法），栈在其中有实现。栈在STL中的实现用到了类模板，也就是说其栈是独立于类型的，模板提供参数化类型，也就是能将类型名作为参数传递给接收方来建立类或函数。比如stack<double> numbers;中就是声明了一个栈，这个栈中存放的数据类型为double。（2）注意，实验题目文档中的这个程序有点语法错误，要使这个程序能运行，首先要改正语法错误。另外，如果要使用c+的输入输出需要加上几行语句如下，因为cout和cin是在命名空间std中的：#include <iostream>using namespace std;2.题目二、题目三这里把题目二和题目三合成了一

3、个题目，在一个程序中完成就可以了。实现一个自己的简单的栈，并用于替换题目一中对标准模板库中的栈的使用，同时对自己实现的栈的功能进行扩充，添加实现如下几个函数(a) clear(b) full(c) size。使用新添加的栈函数，显示在进行数字序列反转时输入的十进制数的个数。注意：实验题目文档中已经把大部分的代码都给出来了。自己实现的栈不要求用类模板，如果能用，当然更好。栈可以用链表或者数组实现，这里是用数组实现。 注意：实验题目中给出的仅仅是部分的代码，自己还需要在看懂的前提下，进行修改补充，才可以达到具体的要求，不明白的地方也可以参考书上这一部分。3.题目四这个题目的主要目的是熟悉队列这个数

4、据结构，而为了说明问题又用了一个模拟飞机场的程序，因此这个实验项目在程序的找错误调试编译，读源代码上对大家也是一个锻炼。仔细阅读教科书中关于模拟飞机场这一部分，阅读源代码。实验题目中的源代码并不完整并且有些语法等等的错误，其缺少生成随机数这一个类，下面会把这个类给大家，有兴趣的话，可以看教科书中的附录，有些介绍。另外大家把代码读懂后就可以复制粘贴到编译环境中了，主要是读懂代码。但是，一定要知道，这样直接粘贴的代码并不能直接运行，需要修改其中的一些bug。这个题目的要求是能读懂代码，明白实现，而且要把代码放到VC中编译调试，使其能正常运行。并通过此，能对程序的编译调试查找错误较为熟悉。注意，一定

5、要使警告也为0个。下面是Random类，用于生成随机数，核心代码来自教科书的附录/Random.h#ifndef RANDOM_H_#define RANDOM_H_class Randompublic:Random(bool pseudo=true);/declare random-number generation methods heredouble random_real();int poisson(double mean);private:int reseed(); /re-randomize the seedint seed;int multiplier,add_on;/const

6、ants for use in arithmetic operations;#endif/Random.cpp#include "Random.h"#include <limits.h>#include <time.h>#include <math.h>int Random:reseed()/Post:The seed is replaced by a psuedorandom successorseed=seed*multiplier+add_on;return seed;Random:Random(bool pseudo)/*Post

7、:The values of seed ,add-on, and multiplier are initialized. The seed is initialized randomly only if pseudo=false*/if (pseudo)seed=1;else seed=static_cast<int>(time(NULL)%INT_MAX);multiplier=2743;add_on=5923;double Random:random_real()/*Post:A random real number between 0 and 1 is returned*/d

8、ouble max=INT_MAX+1.0;double temp=reseed();if (temp<0)temp=temp+max;return temp/max;int Random:poisson(double mean)/*Post:A random integer, reflecting a Poisson distribution with parameter mean, is return.*/double limit=exp(-mean);double product=random_real();int count=0;while (product>limit)c

9、ount+;product*=random_real();return count;三、实验附录1. VC 6环境中编写c+控制台程序步骤下面具体了解一下，如何在VC环境中用c+语言编程，开发控制台应用程序。主要的步骤分为：1.新建项目2.添加文件到新建的项目中3.编写代码4.编译链接生成可执行文件其中，代码的调试也是一个很重要的过程。(1)新建工程图1注意，在上图中一定要选择Win32 Console Application，这样才能编写控制台应用程序。在图1的中的Project name下面的文本框填写自己工程的名字，在Location中选择工程要存放在硬盘的什么地方。填好这些项后，OK按

10、钮变为可用，这时，可以点击OK，进入下一步。图2在图2中，默认选择An empty project，保持默认选项，点击Finish。这样，就建立了一个空白的控制台工程项目。以后可以往这个空白的项目中添加现有文件（已经编写好的.cpp或者.h文件），或者是添加新的空白文件（已经编写好的.cpp或者.h文件），用于在其上编写自己的代码。(2)往工程中添加文件应该注意，刚才我们选择的是新建一个空白的工程，因此，新建的工程中是没有任何.cpp或者.h文件的，现在需要往工程中添加代码文件。在工程已经建立的情况下，有两种方法往工程项目中添加代码，一种是添加空白的.cpp文件和.h文件，然后自己在这些空白的

11、文件中编写代码，另一种是添加现有的.cpp文件和.h文件。若要把添加到工程中的.cpp或者.h文件从工程中删除，只需要在workspace中选中相应的文件，按下键盘上的delete键，就可以了。不过，注意，此时文件仅仅是被从工程中移除了，还在硬盘中存在，如果要彻底将文件删除，需要在硬盘上文件保存的地方进行删除。(a)添加空白的.c文件和.h文件选择File菜单项中的New添加.cpp文件的方法如下：图3在图3的左边选择C+ Source File，右边给这个文件取名，这里取名为Demo.cpp。填写后，点击OK按钮就可以了。添加.h文件的方法如下：图4图4中，选择C/C+ Header Fil

12、e，跟上面一样，可以添加头文件。(b)添加现存的.c文件和.h文件需要在哪个文件夹下添加文件，直接在那个文件夹上点击右键，如图选择，就可以在随后弹出的对话框中选择相应的文件了。(3)VC的IDE界面的简单介绍下面简单的介绍一下，VC的IDE界面图5如图5所示，VC的IDE界面和传统的Windows程序一样，包含有菜单条、工具条和状态条。除了这些，主界面共分为三大部分，分别是Workspace窗口、工作区和输出窗口。其中，Workspace窗口在图5的左半部分，包括FileView页面和ClassView页面，若是编写c程序，只涉及到FileView页面。在FileView页面中，对加入工程中的

13、文件（包括.h和.cpp文件）进行了组织，分为3个文件夹，其中，Source Files中存放的是.cpp文件，Header Files中存放的是.h文件，Resource Files中存放的是资源文件，在数据结构a的实验中并不会涉及到，因此跟我们相关的只有两个文件夹，Source Files文件夹和Header Files文件夹，这两个文件夹对源文件做了很好的组织。如果你愿意或者说是为了满足编程的需要，也可以在其中新建新的文件夹，管理你的代码文件。工作区，在窗口的右边，在其中能打开多个代码页面，可以方便的对代码进行编辑修改。输出窗口在窗口的下部，这个窗口在对程序进行编译链接或者进行调试的时候

14、会出现，显示一些信息。(4)编译链接运行程序要对编写好的程序进行编译链接，可以使用菜单项中的Build菜单，也可以使用工具条中的工具。Build菜单是VC提供的辅助编程的主要菜单，用于对项目进行编译，连接并生成可执行文件。其中的几个子菜单的简单介绍如下：Compile：编译当前激活的源文件或头文件Build：编译并链接当前激活的项目配置Rebuild All：对当前激活的项目配置先Clean，再BuildSet Active Configuration：设置哪个项目配置被激活（其中，默认的是生成Debug版本）工具条如下：其中，第一个图标是Compile，第二个图标是Build，第三个是sto

15、p build，第四个是执行程序（如果新修改好的程序没有编译和链接的话，会有提示，先对程序重新编译链接，再执行），第五个是调试，第六个是设置或移除断点。(5)调试程序调试程序很重要，有不少的方法，比如，可以用printf语句输出中间结果进行调试。VC 6中集成了调试器，可以用VC 6的调试器设置断点，进行调试，观察中间结果信息。主要的快捷键和解释如下：F9：设置断点F5：调试运行F10：单步执行，遇到函数不进入函数内部F11：单步执行，遇到函数进入函数内部Shift+F11：跳出函数熟练运行这些快捷键，在调试的时候会感觉方便些的。在调试的时候会有各种窗口，对中间值进行观察，这样便于进行程序的调

16、试。调试的时候，会有一个调试的工具栏，如果没有出现，则可以用如下方法调出来：另外，注意一点，最好调试结果是输出窗口中显示的信息中警告也为0个，因为编译器在编译我们的程序的时候，有时候检查得不是会很准确的或者说也跟设置的警告的级别有关系，有些警告，在运行的时候就可能会产生问题。因此，最好是编写的程序在编译链接的时候显示的错误和警告都是0个。2. VC.net环境中编写c+控制台程序步骤在VC.net环境中编写c+控制台应用程序跟在VC 6中编写C+控制台应用程序差不多。主要是界面的不一致而已，下面简单的介绍一下。 首先，打开VC.net，在开始页面中点击“新建项目”按钮。在上图中选择Win32中

17、的Win32控制台项目，选择控制台项目，这样能把精力专注在算法的实现上，而不是界面的开发。注意，需要选中附加选项中的“空项目”的复选框，这样会生成一个空白的项目。点击“完成”按钮。这样一个空白的项目就建立好了。剩下的步骤，跟在VC 6中差不多了，就不详细介绍了，如果有问题，可以在实验课的时候询问。3. .h文件和.c或者.cpp文件的一些规范1.使用头文件每个c+/c程序通常分为两个文件。一个文件用于保存程序的声明（declaration），称为头文件。另一个用于保存程序的实现（implementation），称为定义（definition）文件。头文件中只存放“声明”而不存放“定义”。要学会

18、使用头文件，不要把所有的代码都编写到一个.c或者.cpp文件中，虽然在程序短小的时候，这样做也许也是一个不错的选择，但是，当程序的规模稍微大些的时候，应该学会使用头文件，并且不要把所有的代码都集中到一个.c或者.cpp文件中。使用头文件的原因，或者说是作用如下：（1）通过头文件来调用库功能。在很多场合，源代码不便或不准向用户公布，只要向用户提供头文件和二进制的库即可。用户只需要按照头文件中的接口声明来调用库功能，而不必关心接口怎么实现。编译器会从库中提取相应的代码。（2）头文件能加强类型安全检查。如果某个接口被实现或被使用时，其方式与头文件中的声明不一致，编译器就会指出错误，这一简单的规则能大大减轻程序员调试、改错的负担。在头文件中，为了防止头文件被重复引用，应当用ifndef/define/endif结构产生预处理块。用 #include <filename.h> 格式来引用标准库的头文件（编译器将从标准库目录开始搜索）。用 #include “filename.h” 格式来引用非标准库的头文件（编译器将从用户的工作目录开始搜索）。一个头文件结构的例子如下：头文件结构（ graphics.h ）#ifndefGRAPHICS_H/ 防止graphics.h被重复引用#define