搜索
1《数据结构》实验指导书计算机科学与工程学院2目录实验一、熟悉实验环境和单向链表……………………….……………………………..………3实验二、多项式运算………….………..…………………………………………………………14实验三、顺序栈的编写…...…………………………………………………………..………….17实验四、栈的使用—括号匹配…………………..………………………………………………18实验五、循环队列…………………………………………………..………………….…………19实验六、二叉排序树…………………………………………………..…………………………20实验七、图……………………………………………………..………………………………….21实验八、排序…………………………………………………………..…………………………22实验九、查找…………………………………………………………..…………………………233实验一熟悉实验环境和单向链表一、实验目的熟悉VC6实验环境掌握单链表的理论，并能根据需要编写相应的代码二、实验内容1、VC6编写控制台c程序指南和代码编写的一些规范使用VC开发c语言程序，首先要熟悉VC的IDE环境。IDE（IntegratedDevelopmentEnvironment），即集成开发环境。编译器厂家将程序编辑器、编译程序、连接程序和调试程序集成在一个开发环境中，使得这个开发环境能完成所有的开发工作，这就是IDE。当启动VC后，就可以看到它所提供的IDE环境。如何在VC环境中用c语言编程，开发控制台应用程序。主要的步骤分为：1.新建项目2.添加文件到新建的项目中3.编写代码4.编译链接生成可执行文件其中，代码的调试也是一个很重要的过程。(一)、新建工程4图1注意，在图1中一定要选择Win32ConsoleApplication，这样才能编写控制台应用程序。在图1的中的Projectname下面的文本框填写自己工程的名字，在Location中选择工程要存放的硬盘。填好后，点击OK，进入下一步。图25在图2中，默认选择Anemptyproject，保持默认选项，点击Finish。就建立了一个空白的控制台工程项目。以后可以往这个空白的项目中添加现有文件（已经编写好的.c或者.h文件），或者是添加新的空白文件（已经编写好的.c或者.h文件），用于在其上编写自己的代码。二、往工程中添加文件应注意，刚选择的是新建一个空白的工程，因此，新建的工程中没有任何.c或者.h文件，现在需要往工程中添加代码文件。在工程已建立的情况下，有两种方法往工程项目中添加代码，一种是添加空白的.c文件和.h文件，然后自己在这些空白的文件中编写代码，另一种是添加现有的.c文件和.h文件。若要把添加到工程中的.c或者.h文件从工程中删除，只需要在workspace中选中相应的文件，按下键盘上的delete键，就可以了。不过，注意，此时文件仅仅是被从工程中移除了，还在硬盘中存在，如果要彻底将文件删除，需要在硬盘上文件保存的地方进行删除。1.添加空白的.c文件和.h文件选择File菜单项中的New（1）添加.c文件的方法如下：图3在图3的左边选择C++SourceFile，右边给这个文件取名，这里取名为Demo.c。需要注意的是后缀一定要为.c，如果不填写，则默认为.cpp类型的文件。（虽然有人说c是c++的子6集，但是，二者还是有些区别的，当编译器把c程序认为是c++程序的话，会有些问题。）填写后，点击OK按钮。（2）添加.h文件的方法如下：图4图4中，选择C/C++HeaderFile，跟上面一样，可以添加头文件。2.添加现存的.c文件和.h文件需要在哪个文件夹下添加文件，直接在那个文件夹上点击右键，如图选择，就可以在随后弹出的对话框中选择相应的文件了。三、VC的IDE界面的简单介绍下面简单的介绍一下，VC的IDE界面7图5如图5所示，VC的IDE界面和传统的Windows程序一样，包含有菜单条、工具条和状态条。除了这些，主界面共分为三大部分，分别是Workspace窗口、工作区和输出窗口。其中，Workspace窗口在图5的左半部分，包括FileView页面和ClassView页面，若是编写c程序，只涉及到FileView页面。在FileView页面中，对加入工程中的文件（包括.h和.c文件）进行了组织，分为3个文件夹，其中，SourceFiles中存放的是.c文件，HeaderFiles中存放的是.h文件，ResourceFiles中存放的是资源文件，而这在现在简单的c程序编写中不会涉及到（若是使用win32API，编写windows程序，会涉及到），因此跟我们相关的只有两个文件夹，SourceFiles文件夹和HeaderFiles文件夹，这两个文件夹对源文件做了很好的组织。如果你愿意或者说是为了满足编程的需要，也可以在其中新建新的文件夹，管理你的代码文件。工作区，在窗口的右边，在其中能打开多个代码页面，可以方便的对代码进行编辑修改。输出窗口在窗口的下部，这个窗口在对程序进行编译链接或者进行调试的时候会出现，显示一些信息。四、编译链接运行程序对编写好的程序进行编译链接，可以使用菜单项中的Build菜单，也可以使用工具条中的工具。Build菜单是VC提供的辅助编程的主要菜单，用于对项目进行编译，连接并生成可执行文件。其中几个子菜单简单介绍如下：Compile：编译当前激活的源文件或头文件Build：编译并链接当前激活的项目配置RebuildAll：对当前激活的项目配置先Clean，再Build8SetActiveConfiguration：设置哪个项目配置被激活（其中，默认的是生成Debug版本）工具条如下：其中，第一个图标是Compile，第二个图标是Build，第三个是stopbuild，第四个是执行程序（如果新修改好的程序没有编译和链接的话，会有提示，先对程序重新编译链接，再执行），第五个是调试，第六个是设置或移除断点。五、调试程序调试程序很重要，有很多方法，比如，可以用printf语句输出中间结果进行调试。VC6中集成了调试器，可以用vc6的调试器设置断点，进行调试，观察中间结果信息。主要快捷键的解释如下：F9：设置断点F5：调试运行F10：单步执行，遇到函数不进入函数内部F11：单步执行，遇到函数进入函数内部Shift+F11：跳出函数熟练运行快捷键，在调试时会感觉很方便。在调试过程中会有各种窗口，对中间值进行观察，便于进行程序的调试;同时也会有一个调试的工具栏，如果没有出现调试工具栏，则可以用如下方法调出：9另外，注意一点，最好调试结果是输出窗口中显示的信息中警告也为0个，因为编译器在编译程序的时候，有时检查得不是会很准确的或者说也跟设置的警告的级别有关系，有些警告，在运行的时候就可能会产生问题。因此，最好是编写的程序在编译链接的时候显示的错误和警告都是0个。附录：代码编写的一些规范1.使用头文件每个c++/c程序通常分为两个文件。一个文件用于保存程序的声明（declaration），称为头文件。另一个用于保存程序的实现（implementation），称为定义（definition）文件。头文件中只存放“声明”而不存放“定义”。要学会使用头文件，不要把所有的代码都编写到一个.c文件中，虽然在程序短小的时候，这样做也许也是一个不错的选择，但是，当程序的规模稍微大些的时候，应该学会使用头文件，并且不要把所有的代码都集中到一个.c文件中。使用头文件的原因或作用如下：（1）通过头文件来调用库功能。在很多场合，源代码不便或不准向用户公布，只要向用户提供头文件和二进制的库即可。用户只需要按照头文件中的接口声明来调用库功能，而不必关心接口怎么实现。编译器会从库中提取相应的代码。（2）头文件能加强类型安全检查。如果某个接口被实现或被使用时，其方式与头文件中的声明不一致，编译器就会指出错误，这一简单的规则能大大减轻程序员调试、改错的负担。在头文件中，为了防止头文件被重复引用，应当用ifndef/define/endif结构产生预处理块。用#includefilename.h格式来引用标准库的头文件（编译器将从标准库目录开始搜索）。用#include“filename.h”格式来引用非标准库的头文件（编译器将从用户的工作目录开始搜索）。10一个头文件结构的例子如下：头文件结构（graphics.h）#ifndefGRAPHICS_H//防止graphics.h被重复引用#defineGRAPHICS_H//其中GRAPHICS_H为预编译器常量#includemath.h//引用标准库的头文件…#include“myheader.h”//引用非标准库的头文件…voidFunction1(…);//全局函数声明…structBox//结构声明{…};#endif2.程序的版式（可读性）代码编写出来是给人看的，而不是给机器看的。编写具有良好的可读性的代码，写上比较好的注释，这样方便自己以后的修改调试，也方便别人的阅读。有良好的可读性的代码，需要在代码中有适当空行。代码编写过程中，成对编码原则，也就是说，左右括号是一一对应的，写完左边的括号，最好马上写右边的括号，然后再在两个括号中间填写代码。另外，内存的分配和释放也都要注意是成对出现的（这里还没有涉及到）。添加适当的注释，比如函数接口说明，重要的代码段，主要的算法等等。但是，注释不可以过多。在VC6中，快速将混乱的代码转换成整齐的代码的方法：选中需要格式化的代码段，然后按下Alt＋F8（或者选择Edit|Advanced|FormatSelection）3.统一的命名规则编写程序的时候要注意有一个统一的命名规则。比如，变量和参数用小写字母开头的单词组合而成；常量全用大写的字母，用下划线分割单词；静态变量加前缀s_（表示static）；如果不得已需要全局变量，则使全局变量加前缀g_（表示global）等等。给函数，变量命名的时候，需要起有意义的名字。单向链表结点的插入和删除下面有一个单向链表的部分代码，实现的功能为：按任意顺序输入几个整数，构造一个排序的线性表，线性表中的元素是降序排列的。主要函数有3个插入结点：通过插入结点的方式构造降序排列的链表打印链表：遍历链表中的元素，将其打印出来删除结点：根据用户需要删除链表中的结点其中，插入结点函数，主函数给出，需要补充完整删除结点和打印链表函数，能实现删除链表中结点的功能。注意：（1）这里的链式存储结构的线性表中，头结点head也是分配了空间的（2）如果全部的代码自己能编写出来，更好（自己编写代码的时候，可以给头指针不分配11结点空间，仅仅是一个指针）编写链式存储结构的线性表时候需要注意下面几点：（1）链表的每个节点都要分配空间（2）编写单向链表的时候，一定有一个头结点，而因为有这个头指针，根据是否为头指针分配一个实在的结点空间，有两种方法实现后续的链表结点的插入删除遍历等操作。相对来说，给头指针分配一个实实在在的结点空间（这样这个结点的数据区域会被浪费）的做法利于后续的结点插入和删除操作的实现。下面为部分代码，可以复制到VC环境中读懂后，编写删除链表结点的函数：linckList.c/*降序链表的插入，删除，打印*/#includestdio.h#includestdlib.hstructtagNode{intdata;structtagNode*pNext;};typedefstructtagNode*pNode;//将结点插入到链表的适当位置，这是一个降序排列的链表//voidinsertList(pNodehead,//链表头结点pNodepnode)//要插入的结点{pNodepPri=head;while(pPri-pNext!=NULL){if(pPri-pNext-datapnode-data){pnode-pNext=pPri-pNext;pPri-pNext=pnode;break;}pPr