大連海事大學-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空閑

輸出刪除后的客房信