大连海事大学2016-2017-1学期
《数据结构》实验报告
选课序号：班 级：学 号：姓 名：指导教师：
成 绩：
42 计科（二）班 ****** *** *** 2016年 11月 28日
目 录
1. 实验目的 .............................................. 2 2. 实验内容 .............................................. 2
2.1 实验一 客房管理（链表） ............................................................................................. 2
2.2 实验二 串模式匹配算法（串） ..................................................................................... 3 2.3 实验三 求二叉树上结点的路径（二叉树） ................................................................. 3
3.实验步骤 ............................................... 3
3.1 实验一 客房管理（链表） ............................................................................................. 4
3.1.1程序流程图 ............................................................................................................ 4 3.1.1源程序（客房管理程序脚本必须手写） ............................................................ 5 3.1.1运行结果截图 ...................................................................................................... 12 3.2 实验二 串模式匹配算法（串） ................................................................................... 16
3.2.1程序流程图 .......................................................................................................... 16 3.2.1源程序 .................................................................................................................. 17 3.2.1运行结果截图 ...................................................................................................... 23 3.3 实验三 求二叉树上结点的路径（二叉树） ............................................................... 27
3.3.1程序流程图 .......................................................................................................... 27 3.3.1源程序 .................................................................................................................. 28 3.3.1运行结果截图 ...................................................................................................... 32
4.总结与体会 ............................................ 34
1
1. 实验目的
（1） 熟练掌握单循环链表操作的基本算法实现。 （2） 熟练掌握串模式匹配算法。
（3） 熟练掌握二叉树应用的基本算法实现。
2. 实验内容
2.1 实验一 客房管理（链表）
实现功能：以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。 实验机时：8 设计要求：
(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\->roomN,&p->Price,&p->Beds); 输出客房数据：printf(\"%s%8.1f%8.1f%6d%8s\\n\->roomN,p->Price,p->PriceL,p->Beds,p->State); 字符串赋值函数：char* strcpy(char *, const char *); 字符串比较函数：int strcmp(const char *, const char *)
#include typedef struct HNode //定义客房链表结点结构 { char roomN[7]; //客房名称 float Price; //标准价格 float PriceL; //入住价格(默认值=标准价格*80%) int Beds; //床位数Beds 2 char State[5]; //入住状态(值域：\"空闲\"、\"入住\"、\"预订\"，默认值为\"空闲\" struct HNode *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 设计思路： 数据结构： typedef struct node{ char data; //数据域 struct node *lchild , *rchild; //左右孩子指针 }BinTNode; //树中结点类型 typedef BinTNode *BinTree; 主要实现函数： 二叉树的建立 求指定结点路径 二叉树的前、中、后序遍历算法 查找函数 主控函数及运行环境设置 3.实验步骤 按以上实验内容的要求，给出实验步骤，包括程序流程图、源程序和运行结果截图等。 3 3.1 实验一 客房管理（链表） 3.1.1程序流程图 id==3 ？ N 结束 4 开始 HLink L,h; int id,k,Beds; int beds_num; char beds_state[5]; 输入id值 Y N id==0 ？ Y id==1 ？ N Y id==2 ？ N Y 创建输出链表 Build(L);Exp(L); 输入床号,状态,更改客房入住状态 updateH(L,beds_num,beds_state); break; break; 更改未入住客房价格（加价20%） Add(L); Exp(L); 输入床号Beds,更改床号排列顺序 upBed(L,Beds); Exp(L); 输出最高价格客房信息h并删除 h=FirstH(L); Exp(L); 将倒数第k个客房排至首位 MoveK1(L,k); Exp(L); 将正中间节点后的节点全部倒置ReverseN2(L); Exp(L); 输入有误！请返回重新输入 break; Y id==4 ？ N Y id==5 ？ N Y id==6 ？ N id==7 ？ N default Y break; break; break; break; break; 3.1.1源程序 #include //定义客房链表结点结构 typedef struct HNode { char roomN[7]; //客房名称 float Price; //标准价格 float PriceL; //入住价格(默认值=标准价格*80%) int Beds; //床位数Beds char State[5]; //入住状态(值域：\"空闲\"、\"入住\"、\"预订\"，默认值为\"空闲\") 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_state[5]; while(1){ printf(\"\\n ****************欢迎进入客房信息管理系统******************\"); printf(\"\\n\\n 请查看相关功能，并【 按顺序 】 输入相关功能编号，谢谢！\\n\"); printf(\" *******************************************************************\\n\"); printf(\" | 1--查看所有客房信息 |\\n\"); printf(\" | 2--更改客房入住状态 |\\n\"); printf(\" | 3--所有未入住客房加价20%% |\\n\"); printf(\" | 4--更改床号排列顺序 |\\n\"); 5 printf(\" | 5--查找入住价格最高的客房并清空该信息，然后输出更新后信息 |\\n\"); printf(\" | 6--将倒数第K个客房排在首行 |\\n\"); printf(\" | 7--正中间位置结点之后的全部结点倒置后的客房信息 |\\n\"); printf(\" | |\\n\"); printf(\" | !其他---退出 |\\n\"); printf(\" *******************************************************************\\n\\n\"); printf(\" ! 请选择：\"); scanf(\"%d\ if((id<1)||(id>7)) break; switch(id){ case 1: Build(L); Exp(L); break; case 2: printf(\"\\n 更改客房入住状态:\\n\\n\"); printf(\"输入要更改的床位数：\"); scanf(\"%d\ printf(\"\\n输入要更改的客房状态(空闲、入住、预订)：\"); scanf(\"%s\ 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\ upBed(L,Beds); Exp(L); break; case 5: h=FirstH(L); printf(\"\\n ! 输出入住客房价格最高的客房信息，并删除该节点\\n\\n\"); printf(\"-------------------------------------------------\\n\"); printf(\"客房名称 标准价格 入住价格 床位数 入住状态\\n\"); printf(\"-------------------------------------------------\\n\"); 6 } printf(\"%s %8.1f %8.1f %6d %8s\\n\->roomN,h->Price,h->PriceL,h->Beds,h->State); printf(\"-------------------------------------------------\\n\\n\"); printf(\"\\n\\n输出删除后的客房信息\\n\"); Exp(L); break; case 6: } printf(\"输入K值(1 //正序创建链表：从键盘输入结点数据 void Build(HLink &H) { HLink rear; HLink p; char *indata=\".\\\\studata.txt\"; //数据输入文件路径及名称 FILE *infile; //文件指针 infile=fopen(indata, \"r\"); //打开文本文件 if (!infile) { printf(\"数据输入文件没找到!\\n\"); exit(1); } H=(HLink)malloc(sizeof(HNode)); rear=H; while(!feof(infile)) //判断是否读取到文件结尾 { p=(HLink)malloc(sizeof(HNode)); 7 fscanf(infile,\"%s%f%d\->roomN,&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客房入住状态改为state void 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 %8s\\n\->roomN,p->Price,p->PriceL,p->Beds,p->State); p=p->next; 8 } 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->Beds>beds) { p=p->next; } while(p->next) { if(p->next->Beds>beds) { t=p->next; p->next=p->next->next; q=H->next; H->next=t; H->next->next=q; } else p=p->next; } } 9 //求出入住价格最高的客房函数，返回入住价格最高的客房结点指针，返回前将该结点在链表中删除； 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;i 10 } } 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; else { p=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; } } 11 3.1.1运行结果截图 12 13 14 15 3.2 实验二 串模式匹配算法（串） 3.2.1程序流程图 SString S; SString T; static int tem=1,tem1=1; 开始 Y int i,j,id; Int next[10], nextval[10]; int start_pos; 输入id值 id==0 ? N Y id==1 ? N Y id==2 ? N Y id==3 ? N Y id==4 ? N default 求T的nextval值,调用KMP匹配 get_next(T,nextval); Index_KMP_next(S,T,start_pos,next); break 求T的next值,调用KMP匹配 get_next(T,next); Index_KMP_next(S,T,start_pos,next); break 输入字符串并输出 getString(S);getString(T); 输入匹配起点 调用朴素匹配法Index(S,T,start_pos); break break 结束 16 3.2.1源程序 #include typedef unsigned char SString[MAXSTRLEN+1]; static int tem,tem1; //输入字符串 void getString(SString S) { SString s; printf(\"请输入字符串【测试串：ebababababcaababababcabadaaaac scanf(\"%s\ int i=0; while(s[i]!=0){ i++;S[0]=i;} for(int j=0;j void Output(SString S,SString T) { for(int i=0;i //朴素的模式匹配法 void Index(SString S,SString T,int pos) { 17 babababcabad】: \"); int i=pos,j=1; while(i<=S[0]&&j<=T[0]) { if(S[i]==T[j]) { ++i; ++j; } else { i=i-j+2; j=1; } } if(i<=S[0]-T[0]) { printf(\"【匹配点为：%d】\\n\- T[0]); Index(S,T,i); } else { if(j>T[0]) printf(\"【匹配点为：%d】\- T[0]); else printf(\"【匹配点为：%d】\ } } //利用模式串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趟: \ for(int num=0;num ++i; ++j; } else { printf(\"%-4c\ ++i; ++j; } } else { printf(\"%-4c\ printf(\"\\n\\n第%-2d趟: \ j = next[j]; for(int num2=0;num2 //利用模式串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趟: \ for(int num2=0;num2 if (j==0 || S[i]==T[j]) { if(j==0) { ++i; ++j; } else { printf(\"%-4c\ ++i; ++j; } } else { printf(\"%-4c\ printf(\"\\n\\n第%-2d趟: \ j = nextval[j]; for(int num2=0;num2 //求模式串T的next函数值并存入数组next void get_next(SString T,int next[]) { int i = 1,j = 0; next[1] = 0; 20 while (i < T[0]) { if (j==0 || T[i]==T[j]) { ++i; ++j; next[i] = j; } else j = next[j]; } } //求模式串T的next函数修正值并存入数组nextval void get_nextval(SString T,int nextval[]) { int i = 1,j = 0; nextval[1] = 0; while (i < T[0]) { if (j==0 || T[i]==T[j]) { ++i; ++j; if (T[i] != T[j]) nextval[i] = j; else nextval[i] = nextval[j]; } else j = nextval[j]; } } //主函数 void main() { SString S; SString T; int i,j,id; int next[10], nextval[10]; int start_pos; 21 while(1) { tem=1; tem1=1; system(\"cls\"); printf(\"\\n\\n*****************串模式匹配算法操作***********\\n\"); printf(\"\\n\\n 请查看相关功能，并输入相关功能编号，谢谢！\\n\"); printf(\"\\n*************************************************\\n\"); printf(\"\\n 1--输入字符串\\n\"); printf(\"\\n 2--朴素的模式匹配法\\n\"); printf(\"\\n 3--KMP的模式匹配法\\n\"); printf(\"\\n 4--高效的KMP模式匹配法\\n\"); printf(\"\\n\\n 0--退出!\\n\"); printf(\"\\n*************************************************\\n\"); printf(\"\\n请选择：\"); scanf(\"%d\ system(\"cls\"); if(id==0) { printf(\"\\n 你已经退出系统!\\n\\n\"); break; } switch(id){ case 1: printf(\"\\n请按照【先主串后字串】输入字符串：\\n\"); getString(S); getString(T); if(S[0] for(int i=0;i 22 } } get_next(T,next); printf(\"\\n输出模式串T的next函数值\\n\"); for(i=1;i<=T[0];i++) printf(\" %d \ printf(\"\\n\\n请输入匹配的起始点: \"); scanf(\"%d\ Output(S,T); Index_KMP_next(S,T,start_pos,next); printf(\"\\n\"); for(i=0;i printf(\"\\n\\n请输入匹配的起始点: \"); scanf(\"%d\ Output(S,T); Index_KMP_nextval(S,T,start_pos,nextval); printf(\"\\n\"); for(i=0;i 23 24 25 26 3.3 实验三 求二叉树上结点的路径（二叉树） 3.3.1程序流程图 输入id值 id==4 ? N id==0 ? N id==5 ? 结束 27 开始 int id,tem,num; int queue[100];char val; Bintree T,P; Y id==0 ? N Y id==1 ? N Y id==2 ? N Y id==3 ? N Y 中序遍历输出二叉树 LDR(T); break 先序遍历输出二叉树 DLR(T); break 先序输入并创建二叉树 T=createBTpre(); break 层序输入二叉树并打印树状二叉树 PrintTree(T,tem,queue); break Y 后序遍历输出二叉树 LRD (T); break Y N 查询节点并输出路径 P=Locate(T,val); break default 3.3.1源程序 #include typedef struct TNode { char data; struct TNode *lchild,*rchild; }BinTNode; typedef BinTNode *Bintree; //建立二叉树 Bintree createBTpre() { Bintree T; char ch; if((ch=getchar())=='#') T=NULL; else { T=(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; } 28 else { printf(\"%c-\->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 \->data); //访问D DLR(root->lchild); //递归遍历左子树 DLR(root->rchild); //递归遍历右子树 } } //中序遍历算法 void LDR(Bintree root) { if(root!=NULL) { LDR(root->lchild); printf(\" %c \->data); LDR(root->rchild); } } //后序遍历算法 void LRD (Bintree root) { if(root !=NULL) { LRD(root->lchild); LRD(root->rchild); printf(\"%c\->data); } } 29 //树状打印 void PrintTree(Bintree T,int tem,int queue[]) { int pos=0; for(int i=0;i 30 printf(\"\\n请选择：\"); scanf(\"%d\ getchar(); system(\"cls\"); if(id==0){ printf(\"\\n 你已经退出系统!\\n\\n\"); system(\"pause\"); break; } switch(id){ case 1: printf(\"输入你想创建二叉树的深度: \"); scanf(\"%d\ getchar(); printf(\"\\n按层序遍历顺序输入并树状输出二叉树: for(num=0;num 31 \"); } system(\"pause\"); break; case 5: PrintTree(T,tem,queue); printf(\"\\n\"); printf(\"\\n后序遍历树并输出结果：\"); LRD (T); printf(\"\\n\\n\"); system(\"pause\"); break; case 6: PrintTree(T,tem,queue); printf(\"\\n\\n输入你要查询的数值：\"); scanf(\"%c\ printf(\"\\n按照先序顺序输出当前节点路径为: \"); P=Locate(T,val); printf(\"%c\->data); printf(\"\\n\\n\"); system(\"pause\"); break; default: printf(\"\\n输入错误! 不存在该选项\\n\"); printf(\"\\n\\n请返回，重新输入!\\n\\n\"); system(\"pause\"); break; } } printf(\"\\n\"); 3.3.1运行结果截图 32 33 4.总结与体会 数据结构，是学好并应用程序的基础。只是简单的编程，而不注重代码的的质量，编出来的程序毫无意义。数据结构是程序和算法的结合，无论是在面向过程，还是面向对象的程序中，学好数据结构尤为重要。 通过几周的上机实训，在上机的过程中，我也遇到了很多困难，对很多问题也做了多方面的思考，经过自己的努力和想老师请教，解决了其中一些问题，还有一些尚待解决。而这一段时间，给我印象较深的，是在寻求解决问题的过程中，我的思考及思维和一些想法。下面我从各个实验部分写出我的感悟。 一 客房管理系统 （1）查看客房信息 拿到这个题目，我当时首先想到要用一个while加上创造节点个数num来创建输入，但在后来的编译运行中，发现每次都要输入大量的信息，非常麻烦，于是想到大一学过的文件读取与写入的知识，运用这一知识，我提前编写好了的文件，让程序去读取输出，节约了好多时间，而在程序的结尾，在解决“偶数个节点无法找到最中间节点”的问题，可以（写入）插入节点使之正常进行。 34 （2）更改Beds排序问题 在解决这个问题时，首先想到要用排序。有三种思路：一是将原来链表分成3条新链表，比beds小的，等于beds的，大于beds的，然后重新连接。二是先将原链表排序，然后在找到beds，断开连接。三是从链表头开始找，找到一个就把它放在合适的位置，一直到表尾。考虑到不能新建节点，不能改变其他节点的相对位置，我选择了第三种。 （3）找出倒数K个客房 先定义两个同样的节点等于头节点，使其中一个先循环到k个位置，然后一起循环，第一个的下一个为空是，第二个恰好为倒数第K个。 二 模式匹配 （1）c语言中数组s[0]不是串长 第一次输入字符串，输出的时候，出现了乱码，现在想想，自己的C语言基础经验还有待提高，数组，出现乱码，就应该想到是不是有的位置没有初始化？输出打印的类型是不是有问题？等等。二自己还花费了很多时间都没想明白，后来问了老师才明白这个问题，利用先求串长，再挨个后移，求出标准串，问题得以解决。 （2）模式匹配的格式问题及多位置匹配 因为老师要求输出要与课后习题格式一致，于是其中出现了序号，当序号大于9是，一个数字就多占了一个空格，最后格式就不好控制，最后想到了上学期C语言的格式调整，有 %-数字d 的格式，于是问题也解决了。还有一个就是多项匹配位置的输出及判断结束条件问题，经过计算，也解决了。 35 三 二叉树 （1）树状打印及层序输入 我一开始看到这个问题，想到这个问题的关键是格式与节点值。 格式可以通过for循环来解决，节点值无论是先序，中序，还是后序都无法找到一个合适的，后来去网上找，也没有现成的代码可以改，只有思路。就是层序遍历加队列输出。于是我想通过层序遍历创建一个节点数组，然后用for输出这个数组，问题也解决了。 （2）查询节点及返回路径 这个问题，起初我想的是设计一个求节点深度的函数，用数组保存深度，最后利用深度来求出路径，也想过用图的思想去求最短路径 去求，但后来发生了一点事情，请假回家，时间仓促，只是用了代码输出了节点的先序路径，这也是这次报告的一个遗憾。 不过，总的来说，还是收获不错，学到了知识，认识到自己基础还是很差，要学的还很多，希望自己再接再厉！ 36 因篇幅问题不能全部显示，请点此查看更多更全内容