2025年數(shù)據(jù)結(jié)構(gòu)與算法實踐指南創(chuàng)新實驗解析

大連海事大學(xué)-1學(xué)期

《數(shù)據(jù)構(gòu)造》試驗匯報

選課序號：42_________________________________

班級：計科（二）班________________________

號.******

姓名：*"________________________________

指導(dǎo)教師：***______________________________

成績：_________________________________________

11月28H

目錄

1.試驗?zāi)康?................................錯誤!未定義書簽。

2.試驗內(nèi)容.................................錯誤!未定義書簽。

2.1試驗一客房管理：鏈表）.......................................錯誤!未定義書簽。

2.2試驗二串模式匹配算法（串）..................................錯誤!未定義書簽。

2.3試驗三求二叉樹上結(jié)點的途徑（二叉樹）.......................錯誤I未定義書簽。

3.試驗環(huán)節(jié)..................................錯誤!未定義書簽。

3.1試瞼一客房管理：鏈表）.......................................錯誤!未定義書簽。

3.1.L程序流程圖.............................................錯誤!未定義書簽。

3.1.1源程序（客房管理程序腳本必須手寫）....................錯誤!未定義書簽。

3.1.1運行成果截當(dāng)...........................................錯誤!未定義書簽。

3.2試驗二串模式匹配算法（串）..................................錯誤!未定義書簽。

3.2.1程序流程圖..............................................錯誤!未定義書簽。

3.2.1源程序..................................................錯誤!未定義書簽。

3.2.1運行成果截名............................................錯誤!未定義書簽。

3.3試臉三求二叉樹上結(jié)點的途徑（二叉樹）........................錯誤!未定義書簽。

3.3.1程序流程圖..............................................錯誤!未定義書簽。

3.3.L源程序..................................................錯誤!未定義書簽。

3.3.1運行成果截犯............................................錯誤!未定義書簽。

4.總結(jié)與體會.................................錯誤!未定義書簽。

1.試驗?zāi)康?/p>

(1)純熟掌握單循環(huán)鏈表操作的基本算法實現(xiàn)。

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

(3)純熟掌握二叉樹應(yīng)用的基本算法實現(xiàn)。

2.試驗內(nèi)容

2.1試驗一客房管理(鏈表)

?實現(xiàn)功能：以帶表頭結(jié)點的單鏈表為存儲構(gòu)造，實現(xiàn)如下客房管理的設(shè)計規(guī)定。

?試驗機時：8

?設(shè)計規(guī)定：

⑴定義客房鏈表結(jié)點構(gòu)造類型，以Hotel和*HLink命名，數(shù)據(jù)域：客房名稱roomN.原則價格Price、入住價格PriceL(默

認(rèn)值=原則價格*80%)、床位數(shù)Beds、入住狀態(tài)State(空閑、入住、預(yù)訂，默認(rèn)值為空閑)，指針域：*next；

⑵實現(xiàn)創(chuàng)立客房基本狀況鏈表函數(shù)voidBuild(HLink&H),輸入客房名稱、原則價格、床位數(shù),將入住價格、入住狀態(tài)

修改為默認(rèn)值，提議用文獻操作來輸入數(shù)據(jù)：

(3)實現(xiàn)函數(shù)voidupdateH(HLink&H,intbeds,char*state),將床位數(shù)為beds的客房入住狀態(tài)改為state；

⑷實現(xiàn)輸出客房基本狀況函數(shù)voidExp(HLinkH),輸出所有客房的客房名稱、原則價格、入住價格、床位數(shù)、入住狀

態(tài)；

⑸函數(shù)voidAdd(HLink&H),將該鏈表中未入住的客房入住價格均加價20%；

⑹函數(shù)voidupBed(HLinkbeds),將該鏈表床位數(shù)不超過beds的結(jié)點都放在床位數(shù)超過beds的結(jié)點背面；

⑺求出入住價格最高的客房函數(shù)HLinkFirstH(HLink&H),該函數(shù)內(nèi)return語句返回入住價格最高的客房結(jié)點指針，返

回前將該結(jié)點在鏈表中刪除；

(8)函數(shù)voidMoveKl(HLink&H,intk),將單鏈表中倒數(shù)第k個結(jié)點移到第一種結(jié)點位置，注意：嚴(yán)禁采用先計算鏈表

長度n再減k(即n-k)的措施：

(9)函數(shù)voidReverseN2(HLink&H),將單鏈表的正中間位置結(jié)點之后的所有結(jié)點倒置的功能，注意：嚴(yán)禁采用先計算

鏈表長度n再除以2(即n/2)的措施：

(10)主控函數(shù)main。調(diào)用以上函數(shù)，輸出(3)、(5)、(6)、(7)、(8)、(9)處理后的鏈表內(nèi)容、輸出入住價格最高的

客房基本狀況。

也許用到的函數(shù)：

從文獻中讀取客房數(shù)據(jù)：fscanf(文獻指針,"％s%f,%d",p->roomN,&p->Price,&p->Beds);

輸出客房數(shù)據(jù):

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

字符串賦值函數(shù)：char*strcpy(char*,constchar*);

字符串比較函數(shù)：intstrcmp(constchar*,constchar*)

#include<stdio.h>

#indude<stdlib.h>

#include<string.h>

typedefstructHNode〃定義客房鏈表結(jié)點構(gòu)造

{

charroomN[7];〃客房名稱

floatPrice;〃原則價格

floatPriceL;〃入住價格(默認(rèn)值=原則價格*80%)

intBeds;〃床位數(shù)Beds

charState(5);〃入住狀態(tài)(值域："空閑"、"入住"、"預(yù)訂“，默認(rèn)值為"空閑"

structHNode*next;〃指針域

}Hotel,*HLink;

2.2試驗二串模式匹配算法(串)

?實現(xiàn)功能：從主串中笫K個字符起，求出子串在主串中初次出現(xiàn)的位置，即模式匹配或串匹配。

?規(guī)定用三種模式匹配算法分別實現(xiàn)：

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

■KMP改善算法(Next")

■KMP改善算法(NextVwl[])

?試驗機時：6

?設(shè)計規(guī)定：

首先設(shè)計一種具有多種菜單項的主控菜單程序，然后再為這些菜單項配上對應(yīng)的功能。

程序運行后，給出5個菜單項的內(nèi)容和輸入提醒：

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

2.樸素的模式匹配算法

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

4.KMP改善算法(NextVal")

0.退出管理系統(tǒng)

請選擇0—4：

?菜單設(shè)計規(guī)定：使用數(shù)字0—4來選擇菜單項，其他輸入則不起作用。

?輸出成果規(guī)定：輸出各趟匹配詳細過程(其中3、4,首先輸出Next[]或者NextVal[]的各元素的數(shù)值)，最

終輸出單個字符比較次數(shù)、匹配成功時的位置序號或者匹配失敗提醒信息。

2.3試驗三求二叉樹上結(jié)點的途徑(二叉樹)

?實現(xiàn)功能：在采用鏈?zhǔn)酱鎯?gòu)造存儲的一義樹上，以bt指向根結(jié)點，p指向任一給定的結(jié)點，編程實現(xiàn)求

出從根結(jié)點bt到給定結(jié)點p之間的途徑。

?試驗機時：6

?設(shè)計思緒：

數(shù)據(jù)構(gòu)造：

typedefstructnode{

chardata;〃數(shù)據(jù)域

structnode*lchild,*rchild;〃左右孩子指針

}BinTNode;〃樹中結(jié)點類型

typedefBinTNode*BinTree;

重要實現(xiàn)函數(shù)：

■二叉樹的建立

■求指定結(jié)點途徑

■二叉樹的前、中、后序遍歷算法

■查找函數(shù)

主控函數(shù)及運行環(huán)境設(shè)置

3.試驗環(huán)節(jié)

按以上試驗內(nèi)容的規(guī)定，給出試驗環(huán)節(jié)，包括程序流程圖、源程序和運行成果截圖等。

3.1試驗一客房管理（鏈表）

3.1.1程序流程圖

一

7I；

3.1.］源程序

#indude<stdio.h>

#include<stdlib.h>

#inrhidp<<;tringh>

#include<windows.h>

〃定義客房鏈表結(jié)點構(gòu)造

typedefstructHNode

{

charroomN[7];〃客房名稱

floatPrice;〃原則價格

floatPriceL;〃入住價格（默認(rèn)值=原則價格"80%）

intBeds;〃床位數(shù)Beds

diarSLdle（51;〃入住狀態(tài)（值域："空閑"、"入住"、"預(yù)訂"，默認(rèn)值為"空闈"）

structHNode*next;〃指針域

}Hotel,*HLink;

〃函數(shù)申明

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);

〃主函數(shù)

voidmain()

{

HLinkL,h;

intid,k,Beds;

intbeds_num;

charbeds_state(5];

while(l){

printf("\n****************歡迎進入客房彳言官管理系統(tǒng)******************

printf（"\n\n請查看有關(guān)功能,并【！!!按次序!!?。葺斎胗嘘P(guān)功能編號,謝謝!\n"）;

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

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

printf（"|2-更改客房入住狀態(tài)|\n"）；

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

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

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

printf("|6--將倒數(shù)第K個客房排在首行l(wèi)\n")；

printf("|7--正中間位置結(jié)點之后的所有結(jié)點倒置后的客房信息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更改客房入住狀態(tài):\n\n");

printf("輸入要更改的床位數(shù)：")；

scanf("%d",&beds_num);

printf(、】輸入要更改的客房狀態(tài)(空閑、入住、預(yù)訂)：");

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數(shù)：");

scanf("%d”,&Beds);

upBed(L,Beds);

Fxp(l);

break;

case5:

h=FirstH(L);

printf("\n!輸出入住客房價格最高的客房信息，并刪除該節(jié)點\n\n");

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

printf("客房名稱原則價格入住價格床位數(shù)入住狀態(tài)\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輸出止中間位置結(jié)點之后的所仃結(jié)點倒置后的客房信息\n”);

ReverseN2(L);

Exp(L);

break；

default:

print-!你輸入有誤!\n\n");

hrpak;

)

)

)

〃正序創(chuàng)立鏈表：從鍵盤輸入結(jié)點數(shù)據(jù)

voidBuild(HLink&H)

{

HLinkrear;

HLinkp;

clidr*iriddLd=".\\blucldld.txt";〃數(shù)據(jù)輸入文獻途徑及名稱

FILE?infile;〃文獻指針

in(indata,"r");〃打開文本文獻

if(linfile){

pnntf（“數(shù)據(jù)輸入義獻沒找到!\n"）;

exit(l);

)

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

rear=H;

while(!feof(infile))〃判斷與否讀取到文獻結(jié)尾

{

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);

)

〃將床位數(shù)為beds客房入住狀態(tài)改為state

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

(

HLinkp;

p=H->next;

while(p)

if(p->Beds==beds)

strcpy(p->State,state);

p=p->next;

}

)

〃輸出所有客房的客房名稱、原則價格、入住價格、床位數(shù)、入住狀態(tài)：

voidExp(HLinkH)

{

HLinkp;

p=H->next;

if(!p)

(

printf("數(shù)據(jù)為空!\n")；

return;

}

printf("\n*************客房信息輸出如下***************\n)

printf("---------------------------------------------------\n");

printf(“客房名稱原則價格入住價格床位數(shù)入住狀態(tài)\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;

)

)

〃將該鏈表床位數(shù)不超過beds的結(jié)點都放在床位數(shù)超過beds的結(jié)點背而

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;

)

〃求出入住價格最高的客房函數(shù)，返回入住價格最高的客房結(jié)點指針，返回前將該站點在鏈表中刪除:

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;

)

〃將單鏈表中倒數(shù)第k個結(jié)點移到第一種結(jié)點位置

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;

)

〃將單鏈表的正中間位置結(jié)點之后的所有結(jié)點倒置的功能

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一自、管理本冬齊******************

潔,石相關(guān)功能，并工?。?！按順療?。?！1領(lǐng)入相關(guān)功能組號，謝謝！

召

霍信

查

1S萼

二

2蠢狀

入

二

霹

未

嘉

3二

格房

轉(zhuǎn)

4二5

二

失

蕾

一僵

0價

二潔至彥信息，然后輸出更新后信息

一

6將

中

番

7正

3結(jié)點倒冒后的君房信息

?請選擇二1

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

客厲名稱標(biāo)7住價格入住價格床位數(shù)入住狀W

0空閑

m1S1

0Q1OO.O80.OQ空

i--需

03S200.O160.O3空

協(xié)

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協(xié)

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

更改客房入住狀態(tài)：

輸入要更改的床位數(shù)：2

輸入要更改的客房狀態(tài)（空閑、入住、預(yù)訂）：入住

輸出更新后的客房信息

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

五燕瓦一贏初森一入住林格床位數(shù)入住泉態(tài)

---一

空

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一將倒數(shù)第K個客房排在首行—4.o

7--正中間位置結(jié)點之后的全部結(jié)點倒置后的客房信息

!其他一-退出

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

!請選擇：3

!將該鏈表中未入住的客房入住價格均加價20%

輸出加價后的客房信息

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

客房名稱標(biāo)準(zhǔn)價格入住價格床位數(shù)入住狀態(tài)

空

閑

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

****************歡迎進入客責(zé)信息管理系統(tǒng)******************

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

7--正中間位置結(jié)點之后的全部結(jié)點倒置后的客房信息

!其他---退出

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

!請選擇：2

更改客房入住狀態(tài)：

輸入要更改的床位數(shù)：2

輸入要更改的客厲狀態(tài)：入住

輸出更新后的客房借息

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

客房名稱標(biāo)準(zhǔn)價格入住價格床位數(shù)入住狀態(tài)

空閑

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告手王里累當(dāng);24=今**************

話音石相關(guān)功能，并【?。。“错樂剑。?！1領(lǐng)入相關(guān)功蚱組號，謝謝！

3二拿翥罷嘉支翟裳晨

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

4.-----號抄劉

O——杳找入仕價的春潔空該信息，然后鎖出更新啟信總

___:fcfc倒數(shù)

結(jié)，點、但Im后的客歸信息

!其他——退出

!請選擇二4

播入Bedm數(shù):2

容聲名稱標(biāo)準(zhǔn)價格入住價格床位數(shù)入住狀態(tài)

耋

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

!輸出入住客房價格最高的客房信息，并刪除該節(jié)點

客房名稱標(biāo)準(zhǔn)價格入住價格床位數(shù)入住狀態(tài)

206室440.0422.43空閑

輸出刪除后的客房信