大连海事大学2016-2017-1学期《数据结构》实验报告.docx

1、大连海事大学 2016-2017-1 学期数据结构实验报告选课序号： 42 班 级： 计科（二）班 学 号： * 姓 名： * 指导教师： * 成 绩： 2016 年 11 月 28 日1目 录1. 实验目的 .12. 实验内容 .12.1 实验一 客房管理（链表） .12.2 实验二 串模式匹配算法（串） .22.3 实验三 求二叉树上结点的路径（二叉树） .23.实验步骤 .33.1 实验一 客房管理（链表） .33.1.1 程序流程图 .33.1.1 源程序（客房管理程序脚本必须手写） .33.1.1 运行结果截图 .33.2 实验二 串模式匹配算法（串） .33.2.1 程序流程图 .

2、33.2.1 源程序 .33.2.1 运行结果截图 .33.3 实验三 求二叉树上结点的路径（二叉树） .33.3.1 程序流程图 .43.3.1 源程序 .43.3.1 运行结果截图 .424.总结与体会 .431. 实验目的（1） 熟练掌握单循环链表操作的基本算法实现。（2） 熟练掌握串模式匹配算法。（3） 熟练掌握二叉树应用的基本算法实现。2. 实验内容2.1 实验一 客房管理（链表） 实现功能：以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。 实验机时：8 设计要求：(1)定义客房链表结点结构类型，以 Hotel 和*HLink 命名，数据域：客房名称 roomN、标准价格

3、 Price、入住价格 PriceL(默认值= 标准价格*80%)、床位数 Beds、入住状态 State(空闲、入住、预订，默认值为空闲) ，指针域：*next；(2)实现创建客房基本情况链表函数 void Build(HLink 输出客房数据：printf(“%s%8.1f%8.1f%6d%8sn“,p-roomN,p-Price,p-PriceL,p-Beds,p-State);字符串赋值函数：char* strcpy(char *, const char *);字符串比较函数：int strcmp(const char *, const char *)#include#include#

4、includetypedef struct HNode /定义客房链表结点结构char roomN7; /客房名称float Price; /标准价格float PriceL; /入住价格(默认值=标准价格*80%)int Beds; /床位数 Bedschar State5; /入住状态(值域：“空闲“、“入住“、“ 预订“，默认值为“ 空闲“struct HNode *next; /指针域Hotel, *HLink;2.2 实验二 串模式匹配算法（串） 实现功能： 从主串中第 K 个字符起，求出子串在主串中首次出现的位置，即模式匹配或串匹配。 要求用三种模式匹配算法分别实现：5 朴素的模式

5、匹配算法（BF 算法） KMP 改进算法 (Next ) KMP 改进算法 (NextVal ) 实验机时：6 设计要求：首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。程序运行后，给出 5 个菜单项的内容和输入提示：1输入主串、子串和匹配起始位置2朴素的模式匹配算法3 KMP 改进算法(Next )4 KMP 改进算法(NextVal )0退出管理系统请选择 04： 菜单设计要求：使用数字 04 来选择菜单项，其它输入则不起作用。 输出结果要求：输出各趟匹配详细过程（其中 3、4 ，首先输出 Next 或者 NextVal 的各元素的数值） ，最后输出单个字符比较

6、次数、匹配成功时的位置序号或者匹配失败提示信息。2.3 实验三 求二叉树上结点的路径（二叉树） 实现功能：在采用链式存储结构存储的二叉树上，以 bt 指向根结点，p 指向任一给定的结点，编程实现求出从根结点 bt 到给定结点 p 之间的路径。 实验机时：6 设计思路：数据结构：typedef struct nodechar data; /数据域6YYstruct node *lchild , *rchild; /左右孩子指针BinTNode; /树中结点类型typedef BinTNode *BinTree;主要实现函数： 二叉树的建立 求指定结点路径 二叉树的前、中、后序遍历算法 查找函数主

7、控函数及运行环境设置3.实验步骤按以上实验内容的要求，给出实验步骤，包括程序流程图、源程序和运行结果截图等。3.1 实验一 客房管理（链表）3.1.1 程序流程图N开始HLink L,h;int id,k,Beds;int beds_num;char beds_state5;输入 id 值id=0 ？id=1 ？ 创建输出链表Build(L);Exp(L);break;7NNYYYYYNN3.1.1 源程序#include#include#include#include/定义客房链表结点结构NNYid=2 ？id=3 ？id=4 ？id=5 ？id=7 ？id=6 ？default结束输入床号

8、,状态 ,更改客房入住状态updateH(L,beds_num,beds_state);break;更改未入住客房价格（加价20%）Add(L); Exp(L);break;输入床号 Beds,更改床号排列顺序upBed(L,Beds); Exp(L);break;输出最高价格客房信息 h 并删除h=FirstH(L); Exp(L);break;将倒数第 k 个客房排至首位MoveK1(L,k); Exp(L);break;将正中间节点后的节点全部倒置ReverseN2(L); Exp(L); break;输入有误！请返回重新输入 break;N8typedef struct HNodech

9、ar roomN7; /客房名称float Price; /标准价格float PriceL; /入住价格(默认值=标准价格*80%)int Beds; /床位数 Bedschar State5; /入住状态(值域：“空闲“、“入住“、“ 预订“，默认值为“ 空闲“)struct HNode *next; /指针域Hotel, *HLink;/函数声明void Build(HLink void updateH(HLink void Exp(HLink H);void Add(HLink void upBed(HLink HLink FirstH(HLink void MoveK1(HLink void ReverseN2(HLink /主函数void main()