数据结构实验报告.doc

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

按以上实验容的要求，给出实验步骤，包括程序流程图、源程序和运行结果截图等。
实验一客房管理〔链表〕
程序流程图
开场
-
. z
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);E*p(L);
N
Y
输入床号,状态,更改客房入住状态
updateH(L,beds_num,beds_state);
break;
id==2 ？
N
Y
break;
更改未入住客房价格〔加价20%〕
Add(L); E*p(L);
id==3 ？
N
Y
输入床号Beds,更改床号排列顺序
upBed(L,Beds); E*p(L);
id==4 ？
break;
N
Y
输出最高价格客房信息h并删除
h=FirstH(L); E*p(L);
id==5 ？
N
break;
Y
break;
将倒数第k个客房排至首位
MoveK1(L,k); E*p(L);
id==6 ？
N
Y
break;
将正中间节点后的节点全部倒置ReverseN2(L); E*p(L);
id==7 ？
N
输入有误！请返回重新输入
break;
default
完毕
源程序
#include<>
#include<>
#include<>
#include<>
//定义客房链表结点构造
typedef struct HNode
{