《数据结构》实验指导书

1、数据结构实验指导书计算机科学与工程学院目录 .3.14 .17 .18.19.20.21.22.23实验一熟悉实验环境和单向链表一、实验目的熟悉 VC 6实验环境掌握单链表的理论，并能根据需要编写相应的代码二、实验内容1、 VC 6 编写控制台c 程序指南和代码编写的一些规范使用VC开发c 语言程序，首先要熟悉VC的IDE环境。 IDE （Integrated DevelopmentEnvironment ），即集成开发环境。编译器厂家将程序编辑器、编译程序、连接程序和调试程序集成在一个开发环境中，使得这个开发环境能完成所有的开发工作，这就是当启动 VC 后，就可以看到它所提供的 IDE 环境

2、。IDE 。如何在 VC 环境中用c 语言编程，开发控制台应用程序。主要的步骤分为：1.新建项目2.添加文件到新建的项目中3.编写代码4.编译链接生成可执行文件其中，代码的调试也是一个很重要的过程。(一)、新建工程图 1注意，在图1 中一定要选择Win32 Console Application ，这样才能编写控制台应用程序。在图 1 的中的 Project name 下面的文本框填写自己工程的名字，在Location 中选择工程要存放的硬盘。填好后，点击OK ，进入下一步。图 2在图 2 中，默认选择An empty project ，保持默认选项，点击Finish 。 就建立了一个空白的控

3、制台工程项目。以后可以往这个空白的项目中添加现有文件（已经编写好的.c 或者 .h文件），或者是添加新的空白文件 （已经编写好的 .c 或者 .h 文件），用于在其上编写自己的代码。二、往工程中添加文件应注意，刚选择的是新建一个空白的工程， 因此，新建的工程中没有任何 .c 或者 .h 文件 ，现在需要往工程中添加代码文件。在工程已建立的情况下，有两种方法往工程项目中添加代码，一种是添加空白的.c 文件和.h 文件，然后自己在这些空白的文件中编写代码，另一种是添加现有的.c 文件和 .h 文件。若要把添加到工程中的.c 或者 .h 文件从工程中删除，只需要在workspace 中选中相应的文件

4、，按下键盘上的 delete 键，就可以了。 不过， 注意，此时文件仅仅是被从工程中移除了，还在硬盘中存在，如果要彻底将文件删除，需要在硬盘上文件保存的地方进行删除。1.添加空白的 .c 文件和 .h 文件选择 File 菜单项中的New（1）添加 .c 文件的方法如下：图 3在图 3 的左边选择 C+ Source File ，右边给这个文件取名， 这里取名为 Demo.c。需要注意的是后缀一定要为 .c，如果不填写，则默认为 .cpp 类型的文件。（虽然有人说 c 是 c+的子集，但是，二者还是有些区别的，当编译器把c 程序认为是c+ 程序的话，会有些问题。）填写后，点击OK 按钮。（2）

5、添加 .h 文件的方法如下：图 4图 4 中，选择 C/C+ Header File ，跟上面一样，可以添加头文件。2.添加现存的 .c 文件和 .h 文件需要在哪个文件夹下添加文件，直接在那个文件夹上点击右键，如图选择，就可以在随后弹出的对话框中选择相应的文件了。三、 VC 的 IDE 界面的简单介绍下面简单的介绍一下，VC 的 IDE 界面图 5如图 5 所示， VC 的 IDE 界面和传统的Windows 程序一样，包含有菜单条、工具条和状态条。除了这些，主界面共分为三大部分，分别是Workspace 窗口、工作区和输出窗口。其中， Workspace 窗口在图5 的左半部分，包括Fil

6、eView 页面和 ClassView 页面，若是编写 c 程序，只涉及到FileView 页面。在FileView 页面中，对加入工程中的文件（包括.h和.c 文件）进行了组织， 分为 3 个文件夹， 其中，Source Files 中存放的是 .c 文件，Header Files中存放的是 .h 文件， Resource Files 中存放的是资源文件，而这在现在简单的 c 程序编写中不会涉及到（若是使用 win32 API ，编写 windows 程序，会涉及到） ，因此跟我们相关的只有两个文件夹， Source Files 文件夹和 Header Files 文件夹， 这两个文件夹对源

7、文件做了很好的组织。 如果你愿意或者说是为了满足编程的需要，也可以在其中新建新的文件夹，管理你的代码文件。工作区， 在窗口的右边， 在其中能打开多个代码页面，可以方便的对代码进行编辑修改。输出窗口在窗口的下部，这个窗口在对程序进行编译链接或者进行调试的时候会出现，显示一些信息。四、编译链接运行程序对编写好的程序进行编译链接，可以使用菜单项中的Build菜单，也可以使用工具条中Build菜单是VC提供的辅助编程的主要菜单，用于对项目进行编译，连接并生成可执行文件。其中几个子菜单简单介绍如下：Compile ：编译当前激活的源文件或头文件Build ：编译并链接当前激活的项目配置：对当前激活的项目

8、配置先Clean，再Set Active Configuration ：设置哪个项目配置被激活（其中，默认的是生成Debug 版本）工具条如下：其中，第一个图标是Compile ，第二个图标是Build ，第三个是stop build ，第四个是执行程序 （如果新修改好的程序没有编译和链接的话，会有提示，先对程序重新编译链接，再执行），第五个是调试，第六个是设置或移除断点。五、调试程序调试程序很重要，有很多方法，比如，可以用 printf 语句输出中间结果进行调试。中集成了调试器，可以用 vc 6 的调试器设置断点，进行调试，观察中间结果信息。主要快捷键的解释如下：VC 6F9：设置断点F5：

9、调试运行F10：单步执行，遇到函数不进入函数内部F11：单步执行，遇到函数进入函数内部Shift+F11 ：跳出函数熟练运行快捷键，在调试时会感觉很方便。在调试过程中会有各种窗口，对中间值进行观察，便于进行程序的调试; 同时也会有一个调试的工具栏，如果没有出现调试工具栏，则可以用如下方法调出：另外，注意一点，最好调试结果是输出窗口中显示的信息中警告也为 0 个，因为编译器在编译程序的时候， 有时 检查得不是会很准确的或者说也跟设置的警告的级别有关系， 有些警告， 在运行的时候就可能会产生问题 。因此， 最好是编写的程序在编译链接的时候显示的错误和警告都是 0 个。附录：代码编写的一些规范1.

10、使用头文件每个 c+/c 程序通常分为两个文件。一个文件用于保存程序的声明（declaration ），称为头文件。另一个用于保存程序的实现（implementation ），称为定义（ definition ）文件。头文件中只存放“声明”而不存放“定义”。要学会使用头文件，不要把所有的代码都编写到一个.c 文件中，虽然在程序短小的时候，这样做也许也是一个不错的选择，但是， 当程序的规模稍微大些的时候，应该学会使用头文件，并且不要把所有的代码都集中到一个.c 文件中。使用头文件的原因或作用如下：（ 1）通过头文件来调用库功能。在很多场合，源代码不便或不准向用户公布，只要向用户提供头文件和二进制

11、的库即可。用户只需要按照头文件中的接口声明来调用库功能，而不必关心接口怎么实现。编译器会从库中提取相应的代码。（ 2）头文件能加强类型安全检查。如果某个接口被实现或被使用时，其方式与头文件中的声明不一致， 编译器就会指出错误， 这一简单的规则能大大减轻程序员调试、改错的负担。在头文件中， 为了防止头文件被重复引用， 应当用 ifndef/define/endif 结构产生预处理块。用 #include <filename.h> 格式来引用标准库的头文件（编译器将从标准库目录开始搜索）。用 #include “filename.h ”格式来引用非标准库的头文件（编译器将从用户的工作目

12、录开始搜索）。一个头文件结构的例子如下：头文件结构（graphics.h ）#ifndef#defineGRAPHICS_H GRAPHICS_H/ 防止 graphics.h 被重复引用/其中 GRAPHICS_H 为预编译器常量#include <math.h>/ 引用标准库的头文件#include“myheader.h”/引用非标准库的头文件void Function1();/ 全局函数声明struct Box/ 结构声明;#endif2.程序的版式（可读性）代码编写出来是给人看的，而不是给机器看的。编写具有良好的可读性的代码，写上比较好的注释，这样方便自己以后的修改调试，也

13、方便别人的阅读。有良好的可读性的代码，需要在代码中有适当空行。代码编写过程中， 成对编码原则， 也就是说， 左右括号是一一对应的， 写完左边的括号，最好马上写右边的括号， 然后再在两个括号中间填写代码。 另外，内存的分配和释放也都要注意是成对出现的（这里还没有涉及到） 。添加适当的注释，比如函数接口说明，重要的代码段，主要的算法等等。但是，注释不可以过多。在 VC 6 中，快速将混乱的代码转换成整齐的代码的方法：选中需要格式化的代码段，然后按下 Alt F8（或者选择Edit | Advanced | Format Selection ）3.统一的命名规则编写程序的时候要注意有一个统一的命名规

14、则。比如，变量和参数用小写字母开头的单词组合而成；常量全用大写的字母，用下划线分割单词；静态变量加前缀 s_（表示如果不得已需要全局变量，则使全局变量加前缀 g_（表示 global ）等等。给函数，变量命名的时候，需要起有意义的名字。static）；单向链表结点的插入和删除下面有一个单向链表的部分代码，实现的功能为： 按任意顺序输入几个整数，构造一个排序的线性表，线性表中的元素是降序排列的。主要函数有 3 个插入结点：通过插入结点的方式构造降序排列的链表打印链表：遍历链表中的元素，将其打印出来删除结点：根据用户需要删除链表中的结点其中， 插入结点函数，主函数给出， 需要补充完整删除结点和打印

15、链表函数，能实现删除链表中结点的功能。注意：（1）这里的链式存储结构的线性表中，头结点head 也是分配了空间的（2）如果全部的代码自己能编写出来，更好（自己编写代码的时候，可以给头指针不分配结点空间，仅仅是一个指针）编写链式存储结构的线性表时候需要注意下面几点：（ 1）链表的每个节点都要分配空间（ 2）编写单向链表的时候，一定有一个头结点，而因为有这个头指针，根据是否为头指针分配一个实在的结点空间，有两种方法实现后续的链表结点的插入删除遍历等操作。说，给头指针分配一个实实在在的结点空间（这样这个结点的数据区域会被浪费）于后续的结点插入和删除操作的实现。下面为部分代码，可以复制到VC 环境中读

16、懂后，编写删除链表结点的函数：相对来的做法利linckList.c/*降序链表的插入，删除，打印*/#include<stdio.h>#include<stdlib.h>structtagNodeintdata;structtagNode *pNext;typedefstructtagNode* pNode;/ 将结点插入到链表的适当位置，这是一个降序排列的链表/void insertList(pNode head,/ 链表头结点pNode pnode) / 要插入的结点pNode pPri=head;while(pPri->pNext!=NULL)if(pPri

17、->pNext->data<pnode->data)pnode->pNext=pPri->pNext;pPri->pNext=pnode;break ;pPri=pPri->pNext;if(pPri->pNext=NULL)/ 如果要插入的结点最小pPri->pNext=pnode;/ 输出链表void printLinkedList(pNode head)pNode temp=head->pNext;while (temp!=NULL)printf("%d ",temp->data);temp=te

18、mp->pNext;/ 从链表中删除结点void delformList(pNode head,int data)pNode temp=head->pNext;pNode pPri=head;while (temp!=NULL)if (temp->data=data)pPri->pNext=temp->pNext;free(temp);break;pPri=temp;temp=temp->pNext;void main()pNode head=(pNode)malloc( sizeof ( struct tagNode); / 给头指针分配空间 pNode

19、pTemp=NULL;inttemp;head->pNext=NULL; / 比较好的习惯就是分配好空间，马上赋值printf("请输入要放入链表中的数据，以-1 结尾： ");/ 读入数据，以 -1 结尾，把数据插入链表中scanf("%d",&temp);while(temp!=-1)pTemp=(pNode)malloc( sizeof ( structtagNode);pTemp->data=temp;pTemp->pNext=NULL;insertList(head,pTemp);scanf("%d"

20、;,&temp);printf("降序排列的链表为：n");printLinkedList(head);printf("n");/ 下面的代码当删除函数编写成功后，可以取消注释，让其执行, 主要是调用函数实现链表结点的删除/printf("请输入要删除数，以-1 结尾： ");/scanf("%d",&temp);/ while (temp!=-1)/ delformList(head,temp);/ scanf("%d",&temp);/printf("删除节

21、点后，链表中剩余数据为：");/printLinkedList(head);/printf("n");实验二多项式运算一、实验目的1、需要从简单的一个文件的 C 程序中转变过来， 知道一个程序的哪些部分要放到 .c 文件中，哪些部分放到 .h 文件中，能清晰的组织多个文件进行编译链接，即学会多文件项目的组织2、初步掌握在VC 环境中进行代码的调试3、掌握一元稀疏多项式的链式存储结构及其加法、减法运算的实现，进一步熟悉链表的插入、删除操作二、实验内容问题描述：设计一个一元稀疏多项式简单的加减法计算器实现要求：一元稀疏多项式简单计算器的基本功能是：（1）输入并建立多项

22、式：A( x)73x9x85x17 ；B( x)8x22x79x8（2）输出多项式（3）多项式A 和 B 相加，建立多项式C A B，并输出相加的结果多项式C（4）多项式A 和 B 相减，建立多项式C A B，并输出相加的结果多项式D方法说明：（ 1）多项式的输入与存储用带表头结点的单链表存储多项式，链表中的每个节点分别存储多项式各项的系数和指数，即每从键盘输入多项式的一对数（系数，指数） ，可对应建立链表的一个结点。每个节点的结构为：Coefexpnext建立两个链表，其中pa 和 pb 分别为它们的头指针：Pa4-170319 8 pb3-181-92结果链表Pa(或者是 Pc)Pc7 -

23、17 011 1-929 8（2）多项式数据类型的定义struct tagNodefloat coef;int exp;struct tagNode *next;typedef struct tagNode Node;typedef struct tagNode*pNode;（3）主要算法创建两个链表，分别存放多项式1 和多项式 2，这两个链表中的节点是按指数降序或者升序排列的多项式相加或相减，下面给出多项式相加的部分实现/*下面的函数实现两个多项式的相加，要相加的链表分别由pa 和 pb 指向（其中，pa， pb是分配了空间的头结点）。相加的结果直接由pa 指向的链表保存，即使在pa 链表中

24、添加或删除（当系数因为相加为都0的情况下）一些结点，构成结果。这里要相加的链表中指数都是按从小到大的顺序排列好了的，是升序链表。*/void add_poly(Node *pa,Node *pb)Node *p=pa->pNext;/ 链表 1，将来的结果也放在此Node *q=pb->pNext;/ 链表 2Node *pre=pa;Node *u;/ 临时用float x;while (p!=NULL && q!=NULL)/ 当两个链表都不为空if(p->exp<q->exp)/比较链表1 跟链表2 当前节点的指数大小，链表1 也是存放结果的

25、地方pre=p;p=p->pNext;/p 指向要比较的下一个结点。pre 指向的是结果链表的最后一个结点。else if (p->exp=q->exp)/ 假如链表1 和链表 2 的指数相等，就要系数相加x=p->coef+q->coef;if (x!=0)/ 相加后的系数不为0，有必要保留一个结点就可以了p->coef=x;pre=p;else/如果相加后，系数不是 0，不需要保留任何一个结点，在这里删除链表 1 的结点，下面删除链表 2 的结点pre->pNext=p->pNext;/ 保持链表1 的连续性free(p);p=pre->

26、;pNext;/p指向要比较的下一个结点/ 下面的代码是进行链表 2 结点的删除工作，因为指数相等，仅仅需要保留一个结点就可以了/ 而结果直接保存在链表1 中，所以，删除链表2 的结点。u=q;q=q->pNext;free(u);else/如果链表2 的当前节点指数小，那么要把链表2 的当前节点加入到结果链表中（即是链表1）/ 相当于把结点插入到链表1 中，用 u 作为临时变量， 保存链表2 的下一个当前节点的位置。u=q->pNext;q->pNext=p;pre->pNext=q;pre=q;q=u;if (q)/ 如果链表2 比链表 1 长，那么需要把链表2 多

27、余的部分加入结果链表中。链表1比链表 2 长，则什么都不用做。pre->pNext=q;free(pb);输出结果多项式实验三顺序栈的编写一、实验目的掌握顺序栈的编写和实现，并能用自己实现的栈实现相应的算法二、实验内容1. 自己实现一个顺序栈 （栈的成员函数至少必须包括压栈出栈取栈顶元素判断栈是否为空）2. 编写程序，实现功能为：输入5 个整数，然后将这些整数按与输入时相反的顺序输出。注意：（1）栈的结构为typedefstructtagMyStackintarrayMAX_NUM; / 栈intstackNum; / 栈里面的元素个数myStack;（ 2）程序编写的时候，在参数传递的

28、时候要注意，如果改变了输入参数的值，那么要用指针实验四栈的使用括号匹配一、实验目的通过一个小程序，掌握和了解栈的使用二、实验内容从键盘上输入一算术表达式检验该算术表达式中括号是否配对提示：（ 1）配对的算术表达式中左右括号的数目应相等例如：表达式（ a+b）和 a+b）中的括号不配对（ 2）对的算术表达式中每一个括号都一定有一个右括号与之匹配例如：表达式） a+b（+c 和（ b+a） +（ c+d 也属于不配对的情况算法提示： 括号配对检查的原则是： 对表达式从左向右扫描。 当遇到左括号时， 左括号入栈；而遇到右括号时， 首先将栈中的栈顶元素弹出栈， 再比较弹出元素是否与右括号匹配， 如果两

29、者匹配，则操作继续；否则，检查出错，打印“no”，并停止操作。当表达式全部扫描完后，如果栈为空，说明括号作用层次嵌套正确，打印“yes”，并停止操作。方式是先创建一个存放左括号的空栈，并将“#”作为栈底元素。顺序扫描表达式，当遇到非括号时，继续扫描，遇到“ （”时，进栈，而遇到“） ”时，与栈等元素比较，如果括号匹配，栈顶元素退栈，继续扫描表达式，否则，报错退出。这个算法实现中，栈的部分可以直接使用上次实验中自己编写好的栈。不过， 如果使用顺序栈，要明白，顺序栈中的元素个数是有限的。而且要注意，如果使用的话，需要把栈里面存放数据的类型修改为字符型实验五循环队列一、实验目的掌握循环队列的编写和实

30、现，并能用自己实现的队列实现相应的算法二、实验内容1. 自己实现一个循环队列 （队列的成员函数至少必须包括进队列出队列取队首元素值判断队列是否为空）2.编写程序，应用队列实现下述题目描述功能（下面包括题目的描述和说明）：设有两个队列A 和 B ，队列 A 中按次序存放五个大写字母，分别为A ，B ，C，D，E；队列B 中按次序存放五个小写字母，分别为a， b，c， d， e。要求每次都从A 队列队头取出一个元素，从B 队列队头取出一个元素，并列输出这取出的两个元素，直到两个队列为空为止。使得最后输出为：AaBbCcDdEe注意：（1）队列的结构为#define MAX_NUM 10typede

31、f struct tagMyQueuechar arrayMAX_NUM;/队列/这里通过浪费一个空间，来区别队列空还是满/当 front=rear 时，队列空int front;/ 约定头指针指示队列头元素的前一个位置，注意这是一个约定，如果你想做别的约定也可以int rear;/ 约定尾指针指示队尾元素在队列中的当前位置myQueue;（ 2）程序编写的时候，在参数传递的时候要注意，如果改变了输入参数的值，那么要用指针实验六二叉排序树一、实验目的通过一种二叉树构建算法的实现，对二叉树有更深的了解二、实验内容（1）构建一个二叉排序树 （中序遍历的时候会输出排序结果），树中结点数据取自数组a1

32、0 。a10=8,3,6,1,5,2,9,7,4,0（2）分别用三种遍历方法输出遍历结果。（3）键盘输入一个值 x，要求在生成好的二叉排序树中查找这个值 x，如果找到， 则输出“找到了”，没有找到，则输出“没有找到”实验七图一、实验目的熟悉图的遍历操作二、实验内容采用邻接矩阵作为存储结构，完成无向图的深度和广度优先遍历具体的实验代码包括(1) 读入图，保存为邻接矩阵的形式，为了方便，可以直接读入一个矩阵，也可以让用户输入两条相连的边，或者读入相邻的两个结点(2) 实现深度和广度优先遍历的算法(3) 输出深度和广度优先遍历的结果实验八排序一、实验目的掌握一种排序算法二、实验内容设一单向链表的头指针为head,链表的记录中包含着整数类型的key域，试设计算法，将此链表的记录按照key 递增的次序进行排序。要求：（ 1）可以使用自己熟悉的一种排序方法进行排序（ 2）要实现完整的程序，包括输入输出在排序的时候， 你