数据结构实验报告

大连海事大学2016-2017-1学期《数据结构》实验报告选课序号：42班级：计科（二）班学号：******姓名：***指导教师：***成绩：2016年11月28日1目录1.实验目的..............................................22.实验内容..............................................22.1实验一客房管理（链表）.............................................................................................22.2实验二串模式匹配算法（串）.....................................................................................32.3实验三求二叉树上结点的路径（二叉树）.................................................................33.实验步骤...............................................33.1实验一客房管理（链表）.............................................................................................43.1.1程序流程图............................................................................................................43.1.1源程序（客房管理程序脚本必须手写）............................................................53.1.1运行结果截图......................................................................................................123.2实验二串模式匹配算法（串）...................................................................................163.2.1程序流程图..........................................................................................................163.2.1源程序..................................................................................................................173.2.1运行结果截图......................................................................................................233.3实验三求二叉树上结点的路径（二叉树）...............................................................273.3.1程序流程图..........................................................................................................273.3.1源程序..................................................................................................................283.3.1运行结果截图......................................................................................................324.总结与体会............................................3421.实验目的（1）熟练掌握单循环链表操作的基本算法实现。（2）熟练掌握串模式匹配算法。（3）熟练掌握二叉树应用的基本算法实现。2.实验内容2.1实验一客房管理（链表）实现功能：以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。实验机时：8设计要求：(1)定义客房链表结点结构类型，以Hotel和*HLink命名，数据域：客房名称roomN、标准价格Price、入住价格PriceL(默认值=标准价格*80%)、床位数Beds、入住状态State(空闲、入住、预订，默认值为空闲)，指针域：*next；(2)实现创建客房基本情况链表函数voidBuild(HLink&H)，输入客房名称、标准价格、床位数，将入住价格、入住状态修改为默认值，建议用文件操作来输入数据；(3)实现函数voidupdateH(HLink&H,intbeds,char*state)，将床位数为beds的客房入住状态改为state；(4)实现输出客房基本情况函数voidExp(HLinkH)，输出所有客房的客房名称、标准价格、入住价格、床位数、入住状态；(5)函数voidAdd(HLink&H)，将该链表中未入住的客房入住价格均加价20%；(6)函数voidupBed(HLink&H,intbeds)，将该链表床位数不超过beds的结点都放在床位数超过beds的结点后面；(7)求出入住价格最高的客房函数HLinkFirstH(HLink&H)，该函数内return语句返回入住价格最高的客房结点指针，返回前将该结点在链表中删除；(8)函数voidMoveK1(HLink&H,intk)，将单链表中倒数第k个结点移到第一个结点位置，注意：严禁采用先计算链表长度n再减k（即n-k）的方法；(9)函数voidReverseN2(HLink&H)，将单链表的正中间位置结点之后的全部结点倒置的功能，注意：严禁采用先计算链表长度n再除以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%8s\n,p-roomN,p-Price,p-PriceL,p-Beds,p-State);字符串赋值函数：char*strcpy(char*,constchar*);字符串比较函数：intstrcmp(constchar*,constchar*)#includestdio.h#includestdlib.h#includestring.htypedefstructHNode//定义客房链表结点结构{charroomN[7];//客房名称floatPrice;//标准价格floatPriceL;//入住价格(默认值=标准价格*80%)intBeds;//床位数Beds3charState[5];//入住状态(值域：空闲、入住、预订，默认值为空闲structHNode*next;//指针域}Hotel,*HLink;2.2实验二串模式匹配算法（串）实现功能：从主串中第K个字符起，求出子串在主串中首次出现的位置，即模式匹配或串匹配。要求用三种模式匹配算法分别实现：朴素的模式匹配算法（BF算法）KMP改进算法(Next[])KMP改进算法(NextVal[])实验机时：6设计要求：首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。程序运行后，给出5个菜单项的内容和输入提示：1．输入主串、子串和匹配起始位置2．朴素的模式匹配算法3．KMP改进算法(Next[])4．KMP改进算法(NextVal[])0．退出管理系统请选择0—4：菜单设计要求：使用数字0—4来选择菜单项，其它输入则不起作用。输出结果要求：输出各趟匹配详细过程（其中3、4，首先输出Next[]或者NextVal[]的各元素的数值），最后输出单个字符比较次数、匹配成功时的位置序号或者匹配失败提示信息。2.3实验三求二叉树上结点的路径（二叉树）实现功能：在采用链式存储结构存储的二叉树上，以bt指向根结点，p指向任一给定的结点，编程实现求出从根结点bt到给定结点p之间的路径。实验机时：6设计思路：数据结构：typedefstructnode{chardata;//数据域structnode*lchild,*rchild;//左右孩子指针}BinTNode;//树中结点类型typedefBinTNode*BinTree;主要实现函数：二叉树的建立求指定结点路径二叉树的前、中、后序遍历算法查找函数主控函数及运行环境设置3.实验步骤按以上实验内容的要求，给出实验步骤，包括程序流程图、源程序和运行结果截图等。43.1实验一客房管理（链表）3.1.1程序流程图NNYN开始HLinkL,h;intid,k,Beds;intbeds_num;charbeds_state[5];输入id值id==0？YYid==1？id==2？id==3？id==4？id==5？id==7？id==6？default结束创建输出链表Build(L);Exp(L);break;N输入床号,状态,更改客房入住状态updateH(L,beds_num,beds_state);break;NY更改未入住客房价格（加价20%）Add(L);Exp(L);break;Y输入床号Beds,更改床号排列顺序upBed(L,Beds);Exp(L);break;NY输出最高价格客房信息h并删除h=FirstH(L);Exp(L);break;将倒数第k个客房排至首位MoveK1(L,k);Exp(L);Ybreak;N将正中间节点后的节点全部倒置ReverseN2(L);Exp(L);break;YN输入有误！请返回重新输入break;53.1.1源程序#includestdio.h#includestdlib.h#includestring.h#includewindows.h//定义客房链表结点结构typedefstructHNode{charroomN[7];//客房名称floatPrice;//标准价格floatPriceL;//入住价格(默认值=标准价格*80%)intBeds;//床位数BedscharState[5];//入住状态(值域：空闲、入住、预订，默认值为空闲)structHNode*next;//指针域}Hotel,*HLink;//函数声明voidBuild(HLink&H);voidupdateH(HLink&H,intbeds,charstate[]);voidExp(HLinkH);voidAdd(HLink&H);voidupBed(HLink&H,intbeds);HLinkFirstH(HLink&H);voidMoveK1(HLink&H,intk);voidReverseN2(HLink&H);//主函数voidmain(){HLinkL,h;intid,k,Beds;intbeds_num;charbeds_state[5];while(1){prin