数据结构实验报告(00002).docx

数据结构实验报告
1
大连海事大学2016-2017-1学期
《数据结构》实验报告
选课序号： 42
班 级：ct HNode //定义客房链表结点结构
{
char roomN[7]; //客房名称
5
float Price; //标准价格
float PriceL; //入住价格(默认值=标准价格*80%)
int Beds; //床位数Beds
char State[5]; //入住状态(值域："空闲"、"入住"、"预订"，默认值为"空闲"
struct HNode *next; //指针域
}Hotel, *HLink;
实验二 串模式匹配算法（串）
实现功能： 从主串中第K个字符起，求出子串在主串中首次出现的位置，即模式匹配或串匹配。
要求用三种模式匹配算法分别实现：
朴素的模式匹配算法（BF算法）
KMP改进算法(Next[ ])
KMP改进算法(NextVal[ ])
实验机时：6
设计要求：
6
首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。
程序运行后，给出5个菜单项的内容和输入提示：
1．输入主串、子串和匹配起始位置
2．朴素的模式匹配算法
3．KMP改进算法(Next[ ])
4．KMP改进算法(NextVal[ ])
0．退出管理系统
请选择0—4：
菜单设计要求：使用数字0—4来选择菜单项，其它输入则不起作用。
输出结果要求：输出各趟匹配详细过程（其中3、4，首先输出Next[ ]或者NextVal[ ]的各元素的数值），最后输出单个字符比较次数、匹配成功时的位置序号或者匹配失败提示信息。
实验三 求二叉树上结点的路径（二叉树）
实现功能：在采用链式存储结构存储的二叉树上，以bt
8
指向根结点，p指向任一给定的结点，编程实现求出从根结点bt到给定结点p之间的路径。
实验机时：6
设计思路：
数据结构：
typedef struct node{
char data; //数据域
struct node *lchild , *rchild; //左右孩子指针
}BinTNode; //树中结点类型
typedef BinTNode *BinTree;
主要实现函数：
二叉树的建立
求指定结点路径
二叉树的前、中、后序遍历算法
查找函数
8
主控函数及运行环境设置

按以上实验内容的要求，给出实验步骤，包括程序流程图、源程序和运行结果截图等。
实验一 客房管理（链表）

开始
HLink L,h;
int id,k,Beds;
int beds_num;
char beds_state[5];
输入id值
Y
id==0 ？
N
Y
id==1 ？
break;
创建输出链表
Build(L);Exp(L);
N
Y
输入床号,状态,更改客房入住状态
updateH(L,beds_num,beds_state);
break;
id==2 ？
9
N
Y
break;
更改未入住客房价格（加价20%）
Add(L); Exp(L);
id==3 ？
N
Y
输入床号Beds,更改床号排列顺序
upBed(L,Beds); Exp(L);
id==4 ？
break;
N
Y
输出最高价格客房信息h并删除
h=FirstH(L); Exp(L);
id==5 ？
N
break;
Y
break;
将倒数第k个客房排至首位
MoveK1(L,k); Exp(L);
id==6 ？
N
Y
break;
将正中间节点后的节点全部倒置ReverseN2(L); Exp(L);
id==7 ？
N
输入有误！请返回重新输入
break;
default
结束

#include<>
10
#include<>
#include<>
#include<>
//定义客房链表结点结构
typedef struct HNode
{
char roomN[7];