2025年数据结构与算法实践指南创新实验解析

大连海事大学-1学期

《数据构造》试验汇报

选课序号：42_________________________________

班级：计科（二）班________________________

号.******

姓名：*"________________________________

指导教师：***______________________________

成绩：_________________________________________

11月28H

目录

1.试验目的.................................错误!未定义书签。

2.试验内容.................................错误!未定义书签。

2.1试验一客房管理：链表）.......................................错误!未定义书签。

2.2试验二串模式匹配算法（串）..................................错误!未定义书签。

2.3试验三求二叉树上结点的途径（二叉树）.......................错误I未定义书签。

3.试验环节..................................错误!未定义书签。

3.1试睑一客房管理：链表）.......................................错误!未定义书签。

3.1.L程序流程图.............................................错误!未定义书签。

3.1.1源程序（客房管理程序脚本必须手写）....................错误!未定义书签。

3.1.1运行成果截当...........................................错误!未定义书签。

3.2试验二串模式匹配算法（串）..................................错误!未定义书签。

3.2.1程序流程图..............................................错误!未定义书签。

3.2.1源程序..................................................错误!未定义书签。

3.2.1运行成果截名............................................错误!未定义书签。

3.3试脸三求二叉树上结点的途径（二叉树）........................错误!未定义书签。

3.3.1程序流程图..............................................错误!未定义书签。

3.3.L源程序..................................................错误!未定义书签。

3.3.1运行成果截犯............................................错误!未定义书签。

4.总结与体会.................................错误!未定义书签。

1.试验目的

(1)纯熟掌握单循环链表操作的基本算法实现。

(2)纯熟掌握串模式匹配算法。

(3)纯熟掌握二叉树应用的基本算法实现。

2.试验内容

2.1试验一客房管理(链表)

•实现功能：以带表头结点的单链表为存储构造，实现如下客房管理的设计规定。

•试验机时：8

•设计规定：

⑴定义客房链表结点构造类型，以Hotel和*HLink命名，数据域：客房名称roomN.原则价格Price、入住价格PriceL(默

认值=原则价格*80%)、床位数Beds、入住状态State(空闲、入住、预订，默认值为空闲)，指针域：*next；

⑵实现创立客房基本状况链表函数voidBuild(HLink&H),输入客房名称、原则价格、床位数,将入住价格、入住状态

修改为默认值，提议用文献操作来输入数据：

(3)实现函数voidupdateH(HLink&H,intbeds,char*state),将床位数为beds的客房入住状态改为state；

⑷实现输出客房基本状况函数voidExp(HLinkH),输出所有客房的客房名称、原则价格、入住价格、床位数、入住状

态；

⑸函数voidAdd(HLink&H),将该链表中未入住的客房入住价格均加价20%；

⑹函数voidupBed(HLinkbeds),将该链表床位数不超过beds的结点都放在床位数超过beds的结点背面；

⑺求出入住价格最高的客房函数HLinkFirstH(HLink&H),该函数内return语句返回入住价格最高的客房结点指针，返

回前将该结点在链表中删除；

(8)函数voidMoveKl(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*)

#include<stdio.h>

#indude<stdlib.h>

#include<string.h>

typedefstructHNode〃定义客房链表结点构造

{

charroomN[7];〃客房名称

floatPrice;〃原则价格

floatPriceL;〃入住价格(默认值=原则价格*80%)

intBeds;〃床位数Beds

charState(5);〃入住状态(值域："空闲"、"入住"、"预订“，默认值为"空闲"

structHNode*next;〃指针域

}Hotel,*HLink;

2.2试验二串模式匹配算法(串)

•实现功能：从主串中笫K个字符起，求出子串在主串中初次出现的位置，即模式匹配或串匹配。

•规定用三种模式匹配算法分别实现：

■朴素的模式匹配算法＜BF算法)

■KMP改善算法(Next")

■KMP改善算法(NextVwl[])

•试验机时：6

•设计规定：

首先设计一种具有多种菜单项的主控菜单程序，然后再为这些菜单项配上对应的功能。

程序运行后，给出5个菜单项的内容和输入提醒：

1.输入主串、子串和匹配起始位置

2.朴素的模式匹配算法

3.KMP改善算法(Ne»t[])

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.试验环节

按以上试验内容的规定，给出试验环节，包括程序流程图、源程序和运行成果截图等。

3.1试验一客房管理（链表）

3.1.1程序流程图

一

7I；

3.1.］源程序

#indude<stdio.h>

#include<stdlib.h>

#inrhidp<<;tringh>

#include<windows.h>

〃定义客房链表结点构造

typedefstructHNode

{

charroomN[7];〃客房名称

floatPrice;〃原则价格

floatPriceL;〃入住价格（默认值=原则价格"80%）

intBeds;〃床位数Beds

diarSLdle（51;〃入住状态（值域："空闲"、"入住"、"预订"，默认值为"空闱"）

structHNode*next;〃指针域

}Hotel,*HLink;

〃函数申明

voidBuild(HLink&H);

voidupdateH(HLink&H,intbeds,char5tate[));

voidExp(HLinkH);

voidAdd(HLink&H);

voidupBed(HLink&H,intbeds);

HLinkFirstH(HLink&H);

voidMoveKl(HLink&H,intk);

voidReverseN2(HLink&H);

〃主函数

voidmain()

{

HLinkL,h;

intid,k,Beds;

intbeds_num;

charbeds_state(5];

while(l){

printf("\n****************欢迎进入客房彳言官管理系统******************

printf（"\n\n请查看有关功能,并【！!!按次序!!！］输入有关功能编号,谢谢!\n"）;

printf("****************x****************************W*********************

printf（"I1一查看所有客房信息l\n"）;

printf（"|2-更改客房入住状态|\n"）；

printf（"I3-所有未入住客房加价20%%|\n"）；

printf（"|4-更改床号排列次序|\n”）；

printff1|5-查找入住价格最高的客房井清空该信息，然后输出更新后信息l\n");

printf("|6--将倒数第K个客房排在首行l\n")；

printf("|7--正中间位置结点之后的所有结点倒置后的客房信息l\n")；

printf("|l\n")；

printf("|!其他一退出l\n")；

printf((>***************”*******************************************

printfC!请选择：");

scanf("%d",&id);

if((id<l)||(id>7))

break;

switch(id){

case1:

Build(L);

Exp(L);

break;

case2:

printf("\n更改客房入住状态:\n\n");

printf("输入要更改的床位数：")；

scanf("%d",&beds_num);

printf(、】输入要更改的客房状态(空闲、入住、预订)：");

scanf("%s",beds_state);

updateH(L,beds_num,beds_state);

printf("输出更新后的客房信息\n”)；

Exp(L);

break;

case3:

printf("\n!将该链表中未入住的客房入住价格均加价20%%\n");

Add(L);

printf("输出加价后的客房信息\n");

Exp(L);

break;

case4:

printf("输入Beds数：");

scanf("%d”,&Beds);

upBed(L,Beds);

Fxp(l);

break;

case5:

h=FirstH(L);

printf("\n!输出入住客房价格最高的客房信息，并删除该节点\n\n");

printf("---------------------------------------------------\n")；

printf("客房名称原则价格入住价格床位数入住状态\n");

printff'---------------------------------------------------\n")；

printf("%s%8.1f%8.1f%6d%8s\n",h->roomN,h->Price,h->PriceL,h->Beds,h->State);

printf("---------------------------------------------------\n\n")；

printf("\n\n输出删除后的客房信息

Exp(L);

break;

case6:

printf("输入K值(l<k<6)：

scanf("%d",&k);

MoveKl(L,k);

Exp(L);

break；

case7:

printf(”\n输出止中间位置结点之后的所仃结点倒置后的客房信息\n”);

ReverseN2(L);

Exp(L);

break；

default:

print-!你输入有误!\n\n");

hrpak;

)

)

)

〃正序创立链表：从键盘输入结点数据

voidBuild(HLink&H)

{

HLinkrear;

HLinkp;

clidr*iriddLd=".\\blucldld.txt";〃数据输入文献途径及名称

FILE♦infile;〃文献指针

in(indata,"r");〃打开文本文献

if(linfile){

pnntf（“数据输入义献没找到!\n"）;

exit(l);

)

H=(HLink)malloc(sizeof(HNode));

rear=H;

while(!feof(infile))〃判断与否读取到文献结尾

{

p=(HLink)malloc(sizeof(HNode));

Rcanf(infilp,"%<;%f%d",Rp->roomN,Rp->Pricp/Rip->Rpd«;);

p->PriceL=(float)0.8*p->Price;

strcpy(p->State/,空闲)

rear->next=p;

rear=p;

)

rear->next=NULL;

fclose(infile);

)

〃将床位数为beds客房入住状态改为state

voidupdateH(HLink&H,intbeds,charstate[])

(

HLinkp;

p=H->next;

while(p)

if(p->Beds==beds)

strcpy(p->State,state);

p=p->next;

}

)

〃输出所有客房的客房名称、原则价格、入住价格、床位数、入住状态：

voidExp(HLinkH)

{

HLinkp;

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",p->roomN,p->P-ice,p->PriceL,p->Beds,p->State);

p=p->next;

}

printf("\n")；

〃将该链表中未入住的客房入住价格均加价20%

vniHAdd(HIinkRH)

(

HLinkp;

p=H->next;

while(p)

(

if(lstrcmp(p->State,"空闲"))

p->PriceL=(float)1.2*p->PriceL;

p=p->next;

)

)

〃将该链表床位数不超过beds的结点都放在床位数超过beds的结点背而

voidupbed(HLink&H,intbeds)

HLinkp=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;

)

〃求出入住价格最高的客房函数，返回入住价格最高的客房结点指针，返回前将该站点在链表中删除:

HLinkFirstHfHLink&H)

HLinkp,q,r=H;

p=H->next;

q=H->next;

floatpriceMax=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;

returnq;

)

〃将单链表中倒数第k个结点移到第一种结点位置

voidMoveKl(HLink&H,intk)

(

HLinkp,q,r,f;

p=H->next;

q=H->next;

r=H;

f=r->npxt;

for(inti=0;i<k;i++)

{

p=p->next;

}

while(p)

{

p=p->next;

q=q->next;

r=r->next,

)

r->next=q->next;

H->next=q;

q->next=f;

)

〃将单链表的正中间位置结点之后的所有结点倒置的功能

voidReverseN2(HLink&H)

(

HLinkp=H,q=H,h;

while(q)

(

if(p->next)

p=p->next->next;

pkp

(

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;

)

)

3.1.1运行成果截图

****************X次i卬~i井.入宅7病1^7一自、管理本冬齐******************

洁,石相关功能，并工！！！按顺疗！！！1领入相关功能组号，谢谢！

召

霍信

查

1S萼

二

2蠢状

入

二

霹

未

嘉

3二

格房

转

4二5

二

失

蕾

一僵

0价

二洁至彦信息，然后输出更新后信息

一

6将

中

番

7正

3结点倒冒后的君房信息

»请选择二1

+*+**+*++*彳占女口卜***水****+*****水

客厉名称标7住价格入住价格床位数入住状W

0空闲

m1S1

0Q1OO.O80.OQ空

i--需

03S200.O160.O3空

协

l0300.O240.O1空

42

0156.O124.S2i

l5闲

06耋236.O1SS.S2

闲

Q01400.O320.O1空

-

0萋426.O340.82

22闲

203430.O344.O3塞

204«440.O352.O1i协

0

24426.O340.S2闲

0

仝

2,辜430.O344.O3

0用

301440.O352.O2空

500.O400.。

"C:\Users\lenovo\Desktop\cxlcode\S^SS\Debug\Test.exe'OX

!请选择：2

更改客房入住状态：

输入要更改的床位数：2

输入要更改的客房状态（空闲、入住、预订）：入住

输出更新后的客房信息

*************客房信息输出如下***************

五燕瓦一赢初森一入住林格床位数入住泉态

---一

空

1O1闲

室

住

1O2100.080.0入

室

闲

1O3200.0160.0空

室

闲

1O4300.0240.0空

室

住

1O156.0124.8入

5室

入

1O236.0188.8住

6室

空

2O400.0320.0闲

1室

入

2O426.0340.8住

2室

空

2O430.0344.0闲

3室

空

2O352.0闲

4室440.0

入

426.0340.8住

2O4室

空

闲

2O6室430.0344.0

入

住

3O1室440.0352.0

500.0400.0

"C:\Users\lenovo\Desktop\cxlcode\i^^Si5\Debug\Test.exe"□x

6一将倒数第K个客房排在首行—4.o

7--正中间位置结点之后的全部结点倒置后的客房信息

!其他一-退出

*I******************************************************************

!请选择：3

!将该链表中未入住的客房入住价格均加价20%

输出加价后的客房信息

*************客房信息输出如下***************

客房名称标准价格入住价格床位数入住状态

空

闲

1O1室10O901

住

O.6.入

1O2室20O1602

O.0.&

闲

空

O室30O2803

130.

闲

空

1O4室15O1481

6.9&.

住

2入

1O5室36.O1882

46

入

住

1O6室00.O3202

4

空

闲

2O1室26.O4001

49.

入

O.住

2O2室3O344.02

4O.

空

闲

2O3室4O422.43

46.

空

闲

2O4室42O409.01

0.4.

入

2住

2O4室430.O3402

空

闲

2O6室-40.O4243

0.

入

住

3O1室00O4002

****************欢迎进入客责信息管理系统******************

Ufa-C:\Uc^rc\l^novo\D^cktop\cxlcod^\SP^St^8\0<^bug\T^€t.«x^*

7--正中间位置结点之后的全部结点倒置后的客房信息

!其他---退出

*******************************************************************

!请选择：2

更改客房入住状态：

输入要更改的床位数：2

输入要更改的客厉状态：入住

输出更新后的客房借息

*************客房信息输出如下***************

客房名称标准价格入住价格床位数入住状态

空闲

1O1室10O1

06.

入

80.0住

1O2室20O2

3

空

160.0闲

1O室30O3

40.

空

O156.O240.01闲

1-室

6.

入

1O023O124.82住

室0.

入

1O6406.O188.82住

室

0.空

2O142O320.01闲

室0.

入

2O2436.O340.82住

室

空

2O34406.O344.03闲

室

空

2O442O352.01闲

萋0.

入

2O443O340.82住

室

空

2O644O344.03闲

室

入

3O150O352.02住

O.

"C:\Ufsors\looovo\Dofslctop\oxluodu\£FG5=T^\»ob*J0\ToGqxo

****************又欠迫言:彳吉Ft告手王里累当;24=今**************

话音石相关功能，并【！！！按顺方！！！1领入相关功蚱组号，谢谢！

3二拿翥罢嘉支翟裳晨

3——所有不入住客息力口价20%

4.-----号抄刘

O——杳找入仕价的春洁空该信息，然后锁出更新启信总

___:fcfc倒数

结，点、但Im后的客归信息

!其他——退出

!请选择二4

播入Bedm数:2

容声名称标准价格入住价格床位数入住状态

耋

2O646042243空

.

2O34042243

空I

.

1O3室0O6.02SS03

9.零

1O1S060601

1O20606.00

146至

1O4室8Y

501S9

6..入

1O53010s82

1O6耋06.0.0

3-O2全

2O120.0.0

睾401m

9

2O236.0.0全

0.3442

2O4室0.0

26.40y1入

^O43034.02

妻0.4

6.入

3O10040O02

.

C:\Users\lenovo\Desktop\cxlcode\nS^®IS\Debug\Test.exe*X

*******************************************************************

!请选择：5

!输出入住客房价格最高的客房信息，并删除该节点

客房名称标准价格入住价格床位数入住状态

206室440.0422.43空闲

输出删除后的客房信