《大连海事大学2016-2017-1学期《数据结构》实验报告》由会员分享，可在线阅读，更多相关《大连海事大学2016-2017-1学期《数据结构》实验报告（52页珍藏版）》请在金锄头文库上搜索。
1、大连海事大学2016-2017-1学期数据结构实验报告选课序号： 42 班 级： 计科（二）班 学 号： * 姓 名： * 指导教师： * 成 绩： 2016年 11月 28日目 录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程序流程图33.2.1源程序33.2.1运行结果截图33.3 实验三 求二叉树
2、上结点的路径（二叉树）33.3.1程序流程图43.3.1源程序43.3.1运行结果截图44.总结与体会4581. 实验目的（1） 熟练掌握单循环链表操作的基本算法实现。（2） 熟练掌握串模式匹配算法。（3） 熟练掌握二叉树应用的基本算法实现。2. 实验内容2.1 实验一 客房管理（链表）l 实现功能：以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。l 实验机时：8l 设计要求：(1)定义客房链表结点结构类型，以Hotel和*HLink命名，数据域：客房名称roomN、标准价格Price、入住价格PriceL(默认值=标准价格*80%)、床位数Beds、入住状态State(空闲、入住
3、、预订，默认值为空闲)，指针域：*next；(2)实现创建客房基本情况链表函数void Build(HLink &H)，输入客房名称、标准价格、床位数，将入住价格、入住状态修改为默认值，建议用文件操作来输入数据；(3)实现函数void updateH(HLink &H, int beds, char *state)，将床位数为beds的客房入住状态改为state；(4)实现输出客房基本情况函数void Exp(HLink H)，输出所有客房的客房名称、标准价格、入住价格、床位数、入住状态；(5)函数void Add(HLink &H)，将该链表中未入住的客房入住价格均加价20%；(6)函数vo
4、id upBed(HLink &H,int beds)，将该链表床位数不超过beds的结点都放在床位数超过beds的结点后面；(7)求出入住价格最高的客房函数HLink FirstH(HLink &H)，该函数内return语句返回入住价格最高的客房结点指针，返回前将该结点在链表中删除；(8) 函数void MoveK1(HLink &H, int k)，将单链表中倒数第k个结点移到第一个结点位置，注意：严禁采用先计算链表长度n再减k（即n-k）的方法；(9) 函数void ReverseN2(HLink &H)，将单链表的正中间位置结点之后的全部结点倒置的功能，注意：严禁采用先计算链表长度n
5、再除以2（即n/2）的方法；(10)主控函数main()调用以上函数，输出（3）、（5）、（6）、（7）、（8）、（9）处理后的链表内容、输出入住价格最高的客房基本情况。可能用到的函数：从文件中读取客房数据：fscanf(文件指针,%s %f,%d,p-roomN,&p-Price,&p-Beds);输出客房数据：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 *
6、, const char *)#include#include#includetypedef struct HNode /定义客房链表结点结构charroomN7;/客房名称float Price;/标准价格float PriceL;/入住价格(默认值=标准价格*80%)int Beds;/床位数Bedschar State5;/入住状态(值域：空闲、入住、预订，默认值为空闲struct HNode *next;/指针域Hotel, *HLink;2.2 实验二 串模式匹配算法（串）l 实现功能： 从主串中第K个字符起，求出子串在主串中首次出现的位置，即模式匹配或串匹配。l 要求用三种模式匹配
7、算法分别实现：n 朴素的模式匹配算法（BF算法）n KMP改进算法(Next )n KMP改进算法(NextVal )l 实验机时：6l 设计要求：首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。程序运行后，给出5个菜单项的内容和输入提示：1输入主串、子串和匹配起始位置2朴素的模式匹配算法3KMP改进算法(Next )4KMP改进算法(NextVal )0退出管理系统请选择04：l 菜单设计要求：使用数字04来选择菜单项，其它输入则不起作用。l 输出结果要求：输出各趟匹配详细过程（其中3、4，首先输出Next 或者NextVal 的各元素的数值），最后输出单个字符比
8、较次数、匹配成功时的位置序号或者匹配失败提示信息。2.3 实验三 求二叉树上结点的路径（二叉树）l 实现功能：在采用链式存储结构存储的二叉树上，以bt指向根结点，p指向任一给定的结点，编程实现求出从根结点bt到给定结点p之间的路径。l 实验机时：6l 设计思路：数据结构：typedef struct nodechar data;/数据域struct node *lchild , *rchild; /左右孩子指针BinTNode; /树中结点类型typedef BinTNode *BinTree;主要实现函数：n 二叉树的建立n 求指定结点路径n 二叉树的前、中、后序遍历算法n 查找函数主控函数
9、及运行环境设置3.实验步骤按以上实验内容的要求，给出实验步骤，包括程序流程图、源程序和运行结果截图等。3.1 实验一 客房管理（链表）3.1.1程序流程图开始HLink L,h;int id,k,Beds;int beds_num;char beds_state5;输入id值Yid=0 ？NYid=1 ？break;创建输出链表Build(L);Exp(L);NY输入床号,状态,更改客房入住状态updateH(L,beds_num,beds_state);break;id=2 ？NYbreak;更改未入住客房价格（加价20%）Add(L); Exp(L);id=3 ？NY输入床号Beds,更改
10、床号排列顺序upBed(L,Beds); Exp(L);id=4 ？break;NY输出最高价格客房信息h并删除h=FirstH(L); Exp(L);id=5 ？Nbreak;Ybreak;将倒数第k个客房排至首位MoveK1(L,k);Exp(L);id=6 ？NYbreak;将正中间节点后的节点全部倒置ReverseN2(L); Exp(L);id=7 ？N输入有误！请返回重新输入break;default结束3.1.1源程序#include#include#include#include/定义客房链表结点结构typedef struct HNodecharroomN7;/客房名称flo
11、at Price;/标准价格float PriceL;/入住价格(默认值=标准价格*80%)int Beds;/床位数Bedschar State5;/入住状态(值域：空闲、入住、预订，默认值为空闲)struct HNode *next;/指针域Hotel, *HLink;/函数声明void Build(HLink &H);void updateH(HLink &H, int beds, char state);void Exp(HLink H);void Add(HLink &H);void upBed(HLink &H,int beds);HLink FirstH(HLink &H);vo
12、id MoveK1(HLink &H, int k);void ReverseN2(HLink &H);/主函数void main()HLink L,h;int id,k,Beds;int beds_num;char beds_state5;while(1)printf(n *欢迎进入客房信息管理系统*);printf(nn 请查看相关功能，并【 !按顺序! 】 输入相关功能编号，谢谢！n);printf( *n);printf( | 1-查看所有客房信息 |n);printf( | 2-更改客房入住状态 |n);printf( | 3-所有未入住客房加价20% |n);printf( | 4-更改床号排列顺序 |n);printf( | 5-查找入住价格最高的客房并清空该信息，然后输出更新后信息 |n);printf(
