《数据结构》实验报告

大连海事大学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 实验三 求二叉树上结点的路径（二叉树）33.3.1程序流程图43.3.1源程序43.3.1运行结果截图44.总结与体会4371. 实验目的（1） 熟练掌握单循环链表操作的基本算法实现。（2） 熟练掌握串模式匹配算法。（3） 熟练掌握二叉树应用的基本算法实现。2. 实验内容2.1 实验一 客房管理（链表）l 实现功能：以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。l 实验机时：8l 设计要求：(1)定义客房链表结点结构类型，以Hotel和*HLink命名，数据域：客房名称roomN、标准价格Price、入住价格PriceL(默认值=标准价格*80%)、床位数Beds、入住状态State(空闲、入住、预订，默认值为空闲)，指针域：*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)函数void 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再除以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 *, 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 要求用三种模式匹配算法分别实现：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 的各元素的数值），最后输出单个字符比较次数、匹配成功时的位置序号或者匹配失败提示信息。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 查找函数主控函数及运行环境设置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,更改床号排列顺序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;/客房名称float 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);void 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( | 6-将倒数第K个客房排在首行 |n);printf( | 7-正中间位置结点之后的全部结点倒置后的客房信息 |n);printf( | |n);printf( | !其他-退出 |n);printf( *nn);printf( ! 请选择：);scanf(%d,&id);if(id7) break;switch(id)case 1:Build(L);Exp(L);break;case 2:printf(n 更改客房入住状态:nn);printf(输入要更改的床位数：);scanf(%d,&beds_num);printf(n输入要更改的客房状态(空闲、入住、预订)：);scanf(%s,beds_state);updateH(L,beds_num,beds_state);printf(输出更新后的客房信息n);Exp(L);break;case 3:printf(n ! 将该链表中未入住的客房入住价格均加价20%n);Add(L);printf(输出加价后的客房信息n);Exp(L);break;case 4:printf(输入Beds数：);scanf(%d,&Beds);upBed(L,Beds);Exp(L);break;case 5:h=FirstH(L);printf(n ! 输出入住客房价格最高的客房信息，并删除该节点nn);printf(-n);printf(客房名称 标准价格 入住价格 床位数 入住状态n);printf(-n);printf(%s %8.1f %8.1f %6d %8sn,h-roomN,h-Price,h-PriceL,h-Beds,h-State);printf(-nn);printf(nn输出删除后的客房信息n);Exp(L);break;case 6:printf(输入K值(1kroomN,&p-Price,&p-Beds);p-PriceL=(float)0.8 * p-Price;strcpy(p-State,空闲);rear-next=p;rear=p; rear-next=NULL;fclose(infile);/将床位数为beds客房入住状态改为statevoid updateH(HLink &H, int beds, char state)HLink p;p=H-next;while(p)if(p-Beds=beds)strcpy(p-State,state);p=p-next;/输出所有客房的客房名称、标准价格、入住价格、床位数、入住状态；void Exp(HLink H) HLink p; p=H-next; if (!p) printf(数据为空！n); return; printf(n*客房信息输出如下*n); printf(-n); printf(客房名称 标准价格 入住价格 床位数 入住状态n); printf(-n);while(p)printf(%s %8.1f %8.1f %6d %8sn,p-roomN,p-Price,p-PriceL,p-Beds,p-State); p=p-next; printf(n);/将该链表中未入住的客房入住价格均加价20%void Add(HLink &H)HLink p;p=H-next;while(p)if(!strcmp(p-State,空闲)p-PriceL=(float)1.2*p-PriceL;p=p-next;/将该链表床位数不超过beds的结点都放在床位数超过beds的结点后面void upBed(HLink &H,int beds) HLink p=H,q,t; if(p-next-Bedsbeds) p=p-next; while(p-next)if(p-next-Bedsbeds) t=p-next; p-next=p-next-next; q=H-next; H-next=t; H-next-next=q;else p=p-next;/求出入住价格最高的客房函数，返回入住价格最高的客房结点指针，返回前将该结点在链表中删除；HLink FirstH(HLink &H)HLink p,q,r=H;p=H-next;q=H-next; float priceMax=0.0;while(p)if( p-PriceL priceMax)priceMax=p-PriceL;/q=q-next;/r=r-next;p=p-next;while(q-PriceL!=priceMax)q=q-next;r=r-next;r-next=q-next;return q;/将单链表中倒数第k个结点移到第一个结点位置void MoveK1(HLink &H, int k)HLink p,q,r,f;p=H-next;q=H-next;r=H;f=r-next;for(int i=0;inext;while(p)p=p-next;q=q-next;r=r-next;r-next=q-next;H-next=q;q-next=f;/将单链表的正中间位置结点之后的全部结点倒置的功能void ReverseN2(HLink &H)HLink p=H,q=H,h;while(q)if(p-next)p=p-next-next;elsep=p-next;break;q=q-next;p=q-next;q-next=NULL;while(p)h=p-next;p-next=q-next;q-next=p;p=h;3.1.1运行结果截图3.2 实验二 串模式匹配算法（串）3.2.1程序流程图开始SString S; SString T;static int tem=1,tem1=1;int i,j,id;Int next10, nextval10;int start_pos;输入id值Yid=0 ?NYbreak输入字符串并输出getString(S);getString(T);id=1 ?NYbreak输入匹配起点调用朴素匹配法Index(S,T,start_pos);id=2 ?NYbreak求T的next值,调用KMP匹配get_next(T,next);Index_KMP_next(S,T,start_pos,next);id=3 ?N求T的nextval值,调用KMP匹配get_next(T,nextval);Index_KMP_next(S,T,start_pos,next);Ybreakid=4 ?Ndefault结束3.2.1源程序#include#include#include#include#define MAXSTRLEN 255typedef unsigned char SStringMAXSTRLEN+1;static int tem,tem1;/输入字符串void getString(SString S)SString s;printf(请输入字符串【测试串：ebababababcaababababcabadaaaac babababcabad】: );scanf(%s,s);int i=0;while(si!=0) i+;S0=i;for(int j=0;ji+1;j+)Sj+1=sj;/输出字符串void Output(SString S,SString T)for(int i=0;iS0+2;i+)printf(-);printf(n 序号 : );for(int num=1;num=S0;num+)printf(%-4d,num);printf(n);printf(n 主串 : );for(int num1=1;num1=S0;num1+)printf(%-4c,Snum1);printf(n);printf(n 副串 : );for(int num2=1;num2=T0;num2+)printf(%-4c,Tnum2);printf(nn);/朴素的模式匹配法void Index(SString S,SString T,int pos)int i=pos,j=1;while(i=S0&j=T0)if(Si=Tj) +i;+j;else i=i-j+2;j=1;if(iT0)printf(【匹配点为：%d】,i - T0);elseprintf(【匹配点为：%d】,0);/利用模式串T的next函数求T在主串S中第pos字符之后的位置的KMP算法void Index_KMP_next(SString S,SString T,int pos,int next)int i = pos,j = 1;printf(n第%-2d趟: ,tem);for(int num=0;numi-1;num+)printf(%-4c, );while (i=S0 & j=T0)if (j=0 | Si=Tj)if(j=0)+i;+j;else printf(%-4c,Tj);+i;+j;elseprintf(%-4c,Tj);printf(nn第%-2d趟: ,+tem);j = nextj;for(int num2=0;num2i-j;num2+)printf(%-4c, );for(int num=1;numj;num+)printf(%c ,Tnum);if(iT0)printf(【此处匹配点为：%d】,i - T0);elseprintf(【此处匹配点为：%d】,0);/利用模式串T的next函数修正值求T在主串S中第pos字符之后的位置的高效KMP算法void Index_KMP_nextval(SString S,SString T,int pos,int nextval)int i = pos,j = 1;printf(n第%-2d趟: ,tem1);for(int num2=0;num2i-1;num2+)printf(%-4c, );while (i=S0 & j=T0)if (j=0 | Si=Tj)if(j=0) +i;+j;else printf(%-4c,Tj);+i;+j;elseprintf(%-4c,Tj);printf(nn第%-2d趟: ,+tem1);j = nextvalj;for(int num2=0;num2i-j;num2+)printf(%-4c, );for(int num=1;numj;num+)printf(%c ,Tnum); if(iT0)printf(【此处匹配点为：%d】,i - T0);elseprintf(【此处匹配点为：%d】,0);/求模式串T的next函数值并存入数组nextvoid get_next(SString T,int next)int i = 1,j = 0;next1 = 0;while (i T0)if (j=0 | Ti=Tj)+i;+j;nexti = j;elsej = nextj;/求模式串T的next函数修正值并存入数组nextvalvoid get_nextval(SString T,int nextval)int i = 1,j = 0;nextval1 = 0;while (i T0)if (j=0 | Ti=Tj)+i;+j;if (Ti != Tj)nextvali = j;elsenextvali = nextvalj;elsej = nextvalj;/主函数void main()SString S;SString T;int i,j,id;int next10, nextval10;int start_pos;while(1)tem=1;tem1=1;system(cls);printf(nn*串模式匹配算法操作*n);printf(nn 请查看相关功能，并输入相关功能编号，谢谢！n);printf(n*n);printf(n 1-输入字符串n);printf(n 2-朴素的模式匹配法n);printf(n 3-KMP的模式匹配法n);printf(n 4-高效的KMP模式匹配法n);printf(nn 0-退出!n);printf(n*n);printf(n请选择：);scanf(%d,&id);system(cls);if(id=0) printf(n 你已经退出系统!nn);break; switch(id)case 1:printf(n请按照【先主串后字串】输入字符串：n);getString(S);getString(T);if(S0T0)printf(n请注意匹配字串常识，按任意键返回重新输入nn);elseprintf(n输出字符串：n);Output(S,T);for(int i=0;iS0+2;i+)printf(-);printf(n);system(pause);break;case 2:Output(S,T);printf(请输入匹配的起始点: );scanf(%d,&start_pos);Index(S,T,start_pos);printf(nn);system(pause);break;case 3:get_next(T,next);printf(n输出模式串T的next函数值n);for(i=1;i=T0;i+)printf( %d ,nexti);printf(nn请输入匹配的起始点: );scanf(%d,&start_pos);Output(S,T);Index_KMP_next(S,T,start_pos,next);printf(n);for(i=0;iS0+2;i+)printf(-);printf(n);system(pause);break;case 4: get_nextval(T,nextval);printf(n输出模式串T的nextval函数值n);for(j=1;j=T0;j+)printf( %d ,nextvalj);printf(nn请输入匹配的起始点: );scanf(%d,&start_pos);Output(S,T);Index_KMP_nextval(S,T,start_pos,nextval);printf(n);for(i=0;iS0+2;i+)printf(-);printf(n);system(pause);break;default:printf(n输入错误! 不存在该选项n); printf(nn请返回，重新输入!nn);system(pause);break;3.2.1运行结果截图3.3 实验三 求二叉树上结点的路径（二叉树）开始3.3.1程序流程图int id,tem,num;int queue100;char val;Bintree T,P;输入id值Yid=0 ?NY层序输入二叉树并打印树状二叉树PrintTree(T,tem,queue);id=1 ?breakNY先序输入并创建二叉树T=createBTpre();id=2 ?breakNY先序遍历输出二叉树DLR(T);id=3 ?breakNid=4 ?break中序遍历输出二叉树LDR(T);NYYid=0 ?break后序遍历输出二叉树LRD (T);NYbreak查询节点并输出路径P=Locate(T,val);id=5 ?Ndefault 结束3.3.1源程序#include#include#include#include#includetypedef struct TNodechar data; struct TNode *lchild,*rchild;BinTNode;typedef BinTNode *Bintree; /建立二叉树Bintree createBTpre()Bintree T;char ch;if(ch=getchar()=#)T=NULL; elseT=(Bintree)malloc(sizeof(TNode);T-data=ch;T-lchild=createBTpre();T-rchild=createBTpre(); return T;/查找二叉树节点Bintree Locate(Bintree T,char x)Bintree p;if(T=NULL|x=T-data)return T;else printf(%c-,T-data);p=Locate(T-lchild,x);if(p)return p;else return Locate(T-rchild,x);/先序遍历算法void DLR(Bintree root)if (root!=NULL) /非空二叉树 printf( %c ,root-data); /访问DDLR(root-lchild); /递归遍历左子树DLR(root-rchild); /递归遍历右子树 /中序遍历算法void LDR(Bintree root)if(root!=NULL)LDR(root-lchild); printf( %c ,root-data);LDR(root-rchild); /后序遍历算法void LRD (Bintree root)if(root !=NULL) LRD(root-lchild);LRD(root-rchild);printf(%c,root-data); /树状打印void PrintTree(Bintree T,int tem,int queue) int pos=0;for(int i=0;item;i+)for(int j=1;j=(tem-1)*(tem-1)-i);j+)printf( );for(int k=0;kpow(2,i);k+)printf(%c,queuepos);pos+;for(int j=0;j=1&k%2=1)printf( );elsefor(int m=0;mtem-1;m+)printf( );for(int p=0;ptem;p+) printf(n);/主函数void main()int id,tem,num;int queue100;char val;Bintree T,P;while(1)system(cls);printf(nn*二叉树操作*n);printf(nn 请查看相关功能，并输入相关功能编号，谢谢！n);printf(n*n);printf(n 1-按层序遍历顺序输入并树状输出二叉树n);printf(n 2-输入字符串,先序创建树n);printf(n 3-先序遍历树并输出结果n);printf(n 4-中序遍历树并输出结果n);printf(n 5-后序遍历树并输出结果n);printf(n 6-查询二叉树n);printf(nn 0-退出!n);printf(n*n);printf(n请选择：);scanf(%d,&id);getchar();system(cls);if(id=0) printf(n 你已经退出系统!nn);system(pause);break;switch(id)case 1:printf(输入你想创建二叉树的深度: );scanf(%d,&tem);getchar();printf(n按层序遍历顺序输入并树状输出二叉树: );for(num=0;numdata);printf(nn);system(pause);break;default:printf(n输入错误! 不存在该选项n); printf(nn请返回，重新输入!nn);system(pause);break;printf(n); 3.3.1运行结果截图4.总结与体会 数据结构，是学好并应用程序的基础。只是简单的编程，而不注重代码的的质量，编出来的程序毫无意义。数据结构是程序和算法的结合，无论是在面向过程，还是面向对象的程序中，学好数据结构尤为重要。通过几周的上机实训，在上机的过程中，我也遇到了很多困难，对很多问题也做了多方面的思考，经过自己的努力和想老师请教，解决了其中一些问题，还有一些尚待解决。而这一段时间，给我印象较深的，是在寻求解决问题的过程中，我的思考