数据结构实验指导书0930.docx
《数据结构实验指导书0930.docx》由会员分享，可在线阅读，更多相关《数据结构实验指导书0930.docx（21页珍藏版）》请在冰点文库上搜索。
数据结构实验指导书0930
实验一多项式加减法
一、实验目的
通过实现多项式的加减法，对链表有更深入的了解
二、实验内容
问题描述：
设计一个一元稀疏多项式简单的加减法计算器
实现要求：
一元稀疏多项式简单计算器的基本功能是：
（1）输入并建立多项式：
；
（2）输出多项式
（3）多项式A和B相加，建立多项式C＝A＋B，并输出相加的结果多项式C
（4）选作：
多项式A和B相减，建立多项式C＝A－B，并输出相加的结果多项式D
方法说明：
（1）多项式的输入与存储
用带表头结点的单链表存储多项式，链表中的每个节点分别存储多项式各项的系数和指数，即每从键盘输入多项式的一对数（系数，指数），可对应建立链表的一个结点。
每个节点的结构为：
建立两个链表，其中pa和pb分别为它们的头指针：
Pa
pb
结果链表
Pa（或者是Pc）
Pc
（2）多项式数据类型的定义
structtagNode
{
floatcoef;
intexp;
structtagNode*next;
};
typedefstructtagNodeNode;
typedefstructtagNode*pNode;
（3）主要算法
①创建两个链表，分别存放多项式1和多项式2，这两个链表中的节点是按指数降序或者升序排列的
②多项式相加或相减，下面给出多项式相加的部分实现
/*
下面的函数实现两个多项式的相加，要相加的链表分别由pa和pb指向（其中，pa，pb都是分配了空间的头结点）。
相加的结果直接由pa指向的链表保存，即是在pa链表中添加或删除（当系数因为相加为0的情况下）一些结点，构成结果。
这里要相加的链表中指数都是按从小到大的顺序排列好了的，是升序链表。
*/
voidadd_poly（Node*pa,Node*pb）
{
Node*p=pa->pNext;//链表1，将来的结果也放在此
Node*q=pb->pNext;//链表2
Node*pre=pa;
Node*u;//临时用
floatx;
while（p!
=NULL&&q!
=NULL）//当两个链表都不为空
{
if（p->expexp）//比较链表1跟链表2当前节点的指数大小，链表1也是存放结果的地方
{
pre=p;
p=p->pNext;//p指向要比较的下一个结点。
pre指向的是结果链表的最后一个结点。
}
elseif（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->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多余的部分加入结果链表中。
链表1比链表2长，则什么都不用做。
{
pre->pNext=q;
}
free（pb）;
}
③输出结果多项式
实验二迷宫
一、实验目的
1、了解回溯法在求解迷宫问题中的应用
2、进一步掌握栈的使用
二、实验内容
用回溯法求解迷宫问题，可以用一个栈保存探索的序列。
并且在该迷宫的行走中，站在一点可以有八个方向选择。
比如如下的迷宫
Enter->0111000000
0001000100
0101100100
0100101100
0100101100
1110101000
0010001011
0010001011
0110101000
0000101100-->EXIT
下面是可能的路径（注意：
从入口到出口可能有多条路径，优先选择的方向不同，路径可能也不一样！
）
Path:
（maze[0][0],maze[1][0],maze[1][1],maze[1][2],maze[2][2],
maze[3][2],maze[3][3],maze[4][3],maze[5][3],maze[6][3],
maze[6][4],maze[6][5],maze[5][5],maze[4][5],maze[3][5],
maze[2][5],maze[2][6],maze[1][6],maze[0][6],maze[0][7],
maze[0][8],maze[1][8],maze[2][8],maze[3][8],maze[4][8],
maze[5][8],maze[5][7],maze[6][7],maze[7][7],maze[8][7],
maze[8][8],maze[8][9],maze[9][9]）
Enter->X11100X---X---X0
X---X---X100X1X0
01X11X---X1X0
01X---X1X11X0
010X1X11X0
111X1X1X---X0
001X---X---X1X11
0010001X11
0110101X--X--X
000010110X-->EXIT
1、提示：
（1）数据结构：
✧用二维数组MAZE[m+2][n+2]表示迷宫的结构，数组中的值为1表示是墙，为0表示可以走通。
（用MAZE[m+2][n+2]而不用MAZE[m][n]的原因在于想表示和编写代码的时候简单些，而且让迷宫周围都是墙，防止错误的走出去）
✧用二维数组MARK[m+2][n+2]表示迷宫是否被走过，主要是为了回溯时已经证明走不通的路线就不要再去走了。
（用MARK[m+2][n+2]而不用MARK[m][n]的原因在于想表示和编写代码的时候简单些）
✧二维数据MOVE[8][2]是为了更方便的移动到下一步，改变坐标。
这个二维数组是为了更好的转换坐标（八个方向，从0到7），而且也能避免重复走路
✧用栈保存走过的路径
（2）输出：
✧迷宫布局，用0表示可以走通的地方，用1表示墙
✧如果能走通，则输出路径和路径的长度；若不能走通，则输出提示不能走通
✧带有路径的迷宫布局
2、伪代码
注意：
下面的仅仅是伪代码！
！
！
不能直接做代码使用的，揭示的仅仅是算法本身
Path（MAZE,MARK,m,n,MOVE,STACK）
//AbinarymatrixMAZE（0:
m+1,0:
n+1）holdsthemaze.
//STACK（mn,2）recordsthepath
{
MARK（1,1）=1;
STACK.push（（1,1,1））;
WhilenotSTACK.empty（）
{
（i,j,mov）=STACK.top（）;
STACK.pop（）;
Whilemov!
=8
{
g=i+MOVE（mov,1）;
h=j+MOVE（mov,2）;
ifg=mandh=n
{
reverseprintSTACK;
printi,j;
printm,n;
return;
}
ifMAZE（g,h）=0andMARK（g,h）=0
{
MARK（g,h）=1;
STACK.push（（i,j,mov））;
i=g;
j=h;
mov=0;
}
elsemov=mov+1;
}
}
print“Nopathhasbeenfound”
}
附录：
STL中栈的使用
#pragmawarning（disable:
4786）
#include
#include
usingnamespacestd;
typedefstackSTACK_INT;
intmain（）
{
STACK_INTstack1;
cout<<"stack1.empty（）returned"<<
（stack1.empty（）?
"true":
"false"）<cout<<"stack1.push
（2）"<stack1.push
（2）;
if（!
stack1.empty（））//Function3
cout<<"stack1.top（）returned"<<
stack1.top（）<cout<<"stack1.push（5）"<stack1.push（5）;
if（!
stack1.empty（））//Function3
cout<<"stack1.top（）returned"<<
stack1.top（）<cout<<"stack1.push（11）"<stack1.push（11）;
if（!
stack1.empty（））//Function3
cout<<"stack1.top（）returned"<<
stack1.top（）<//Modifythetopitem.Setitto6.
if（!
stack1.empty（））{//Function3
cout<<"stack1.top（）=6;"<stack1.top（）=6;//Function1
}
//Repeatuntilstackisempty
while（!
stack1.empty（））{//Function3
constint&t=stack1.top（）;//Function2
cout<<"stack1.top（）returned"<cout<<"stack1.pop（）"<stack1.pop（）;
}
}
运行结果：
stack1.empty（）returnedtrue
stack1.push
（2）
stack1.top（）returned2
stack1.push（5）
stack1.top（）returned5
stack1.push（11）
stack1.top（）returned11
stack1.top（）=6;
stack1.top（）returned6
stack1.pop（）
stack1.top（）returned5
stack1.pop（）
stack1.top（）returned2
stack1.pop（）
实验三农夫过河
一、实验目的
1、进一步掌握队列的使用
2、会使用队列进行农夫过河解的搜索
二、实验内容
经典的农夫过河问题，具体讲解请看课本
要求：
使用广度优先搜索农夫过河解，并输出结果
提示：
可以使用STL中的队列进行代码编写。
附录：
STL中队列的使用
注：
队列，这里也不要求大家再去自己实现一个有关队列的类，直接用标准模板库（STL）中的队列就可以了。
需要#include
STL中的queue，里面的一些成员函数如下（这里仅仅描述也许会用到的几个，具体不明白可以查找msdn，搜索queueclass）：
front：
Returnsareferencetothefirstelementatthefrontofthequeue.
pop：
Removesanelementfromthefrontofthequeue
push：
Addsanelementtothebackofthequeue
empty：
Testsifthequeueisempty
程序示例：
//queue:
:
push（）,queue:
:
pop（）,queue:
:
empty（）,queue:
:
back（）,
//queue:
:
front（）,queue:
:
size（）
#include
#include
usingnamespacestd;
typedefqueueINTQUEUE;
typedefqueueCHARQUEUE;
intmain（void）
{
intsize_q;
INTQUEUEq;
CHARQUEUEp;
//Insertitemsinthequeue
q.push（42）;
q.push（100）;
q.push（49）;
q.push（201）;
//Outputthesizeofqueue
size_q=q.size（）;
cout<<"sizeofqis:
"<//Outputitemsinqueueusingfront（）
//andusepop（）togettonextitemuntil
//queueisempty
while（!
q.empty（））
{
cout<q.pop（）;
}
//Insertitemsinthequeue
p.push（"cat"）;
p.push（"ape"）;
p.push（"dog"）;
p.push（"mouse"）;
p.push（"horse"）;
//Outputtheiteminsertedlastusingback（）
cout<//Outputthesizeofqueue
size_q=p.size（）;
cout<<"sizeofpis:
"<//Outputitemsinqueueusingfront（）
//andusepop（）togettonextitemuntil
//queueisempty
while（!
p.empty（））
{
cout<p.pop（）;
}
}
输出结果：
sizeofqis:
4
42
100
49
201
horse
sizeofpis:
5
cat
ape
dog
mouse
horse
实验四二叉树的建立和遍历
一、实验目的
1、掌握树的先根构造
2、了解树的遍历
二、实验内容
构造一棵二叉树，并进行遍历
要求：
1、二叉树的构造，可以输入树的先根序遍历序列，然后进行构造
2、先使用递归的中根，先根，后根序对二叉树做遍历，然后对二叉树进行中根序非递归遍历
提示：
1、在构造二叉树的时候，输入树的先根序的时候，树的先根序必须是完整的
2、在进行二叉树的中根序非递归遍历代码书写时，使用的栈，可以使用STL的栈。
实验五二叉树排序树的建立和检索
一、实验目的
1、掌握二叉排序树的建立
2、对二叉排序树进行数据检索
二、实验内容
构造一棵二叉排序树，并进行遍历，检索数据
要求：
1、输入数据构造二叉排序树
2、对构造好的二叉排序树进行中根序遍历
3、对构造好的二叉排序树进行数据检索
提示：
对二叉排序树进行中根序遍历的时候，获得的是排序序列
实验六排序
一、实验目的
至少掌握一种排序算法，能进行多种排序算法的比较
二、实验内容
随机生成10个从1－100之间的随机数，编程实现至少一种排序算法，对该数据进行排序。
要求
1、要排序的数据随机生成
2、先升序排序一次，再用同样的算法降序排序一次
附录（帮助文档中的随机数生成）：
//crt_rand.c
//Thisprogramseedstherandom-numbergenerator
//withthetime,thenexercisestherandfunction.
//
#include
#include
#include
voidSimpleRandDemo（intn）
{
//Printnrandomnumbers.
inti;
for（i=0;iprintf（"%6d\n",rand（））;
}
voidRangedRandDemo（intrange_min,intrange_max,intn）
{
//Generaterandomnumbersinthehalf-closedinterval
//[range_min,range_max）.Inotherwords,
//range_min<=randomnumberinti;
for（i=0;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）;
}
结果：
22036
18330
11651
27464
18093
3284
11785
14686
11447
11285
74
48
27
65
96
64
-5
-42
-55
66
实验七图
一、实验目的
掌握求最短路径的Dijkstra算法
二、实验内容
编写程序，用Dijkstra算法求图的最短路径
提示：
程序简单模板（只是参考，不需要照着这个来写，下面的模板用到了C＋＋的一些语法知识，如果对面向对象的一些知识有所遗忘，可以用C编写代码）
//最短路径
#ifndefMYGRAPH_H_
#defineMYGRAPH_H_
classMyGraph
{
public:
voidreadDirectedGraph（）;
MyGraph（intsize）;//构造函数中设置图的大小，分配空间
voidwriteGraph（）;
voidshortDistance（intsource）;//最短路径
protected:
private:
int**m_graph;//用二维数组保存图
intm_size;//图的大小
};
#endif
//构造函数中设置图的大小，分配空间
MyGraph:
:
MyGraph（intsize）
{
inti,j;
m_size=size;
//给图分配空间
m_graph=newint*[m_size];
for（i=0;i{
m_graph[i]=newint[m_size];
}
for（i=0;i{
for（j=0;j{
m_graph[i][j]=INT_MAX;
}
}
}
实验八综合
一、实验目的
运用数据结构的知识，编写应用程序
二、实验内容
分组完成一个题目，3-5人一组
题目
1、中国邮递员（图）
2、推箱子游戏（栈和队列）
3、飞机场管理，包括飞机调度和航空订票问题（链表、栈和队列）
4、文件目录管理和显示（二叉树）
5、机房机位预订系统（链表、检索排序）
6、其余题目跟老师商量
升级会员 