華北電力大學數(shù)據(jù)結(jié)構(gòu)實驗報告-2023修改整理

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦華北電力大學數(shù)據(jù)結(jié)構(gòu)實驗報告華北電力高校

試驗報告

|

|

試驗名稱算法與數(shù)據(jù)結(jié)構(gòu)綜合試驗

課程名稱算法與數(shù)據(jù)結(jié)構(gòu)

|

|

專業(yè)班級：同學姓名：

學號：成果：

指導(dǎo)老師：試驗日期：

（試驗報告如打印，紙張用A4，左裝訂；頁邊距：上下2.5cm,左2.9cm,

右2.1cm；字體：宋體小四號，1.25倍行距。）

（試驗一停車場管理）

（試驗二約瑟夫環(huán)）

（試驗三二叉樹的存儲及遍歷）

（試驗四圖的存儲及遍歷）

（試驗五哈希表的設(shè)計）

一、試驗?zāi)康募耙?/p>

二、所用儀器、設(shè)備

三、試驗原理

四、試驗辦法與步驟

五、試驗結(jié)果與數(shù)據(jù)處理

六、研究與結(jié)論（對試驗現(xiàn)象、試驗故障及處理辦法、試驗中存在的問題等舉行分析和研究，對試驗的進一步主意或改進意見）

七、所附試驗輸出的結(jié)果或數(shù)據(jù)

試驗一停車場管理

一、試驗內(nèi)容

設(shè)停車場是一個可以停放n輛汽車的狹長通道，且惟獨一個大門可以供車輛進出。車輛按到達停車場時光的早晚依次從停車場最里向大門口處停放（最先到達的第一輛車放在停車場的最里面）。假如停車場已放滿n輛車，則后來的車只能在停車場大門外的便道上等待，一旦停車場內(nèi)有車開走，則排在便道上的第一輛車就進入停車場。停車場內(nèi)如有某輛車要開走，在它之后進入停車場的車都必需先退出停車場為它讓路，待其開出停車場后，這些車輛再依本來的次序進場。每輛車在離開停車場時，都應(yīng)按照它在停車場內(nèi)停歇的時光長短交費。假如停歇在便道上的車未進停車場就要離去，允許其離去，不收停車費，并且仍然保持在便道上等待的車輛次序。編制一程序模擬該停車場的管理。

二、試驗?zāi)康?/p>

把握棧和隊列的定義和實現(xiàn)，學習利用棧和隊列解決實際問題。

三、所用儀器、設(shè)備

計算機，VC++2022。

四、試驗辦法與步驟

停車場采納棧式結(jié)構(gòu)，停車場外的便道采納隊列結(jié)構(gòu)（即便道就是迎候隊列）。停車場的管理流程如下：

①當車輛要進入停車場時，檢查停車場是否已滿，假如未滿則車輛進棧（車輛進入停車場）；假如停車場已滿，則車輛進入迎候隊列（車輛進入便道迎候）。

②當車輛要求出棧時，該車到棧頂?shù)哪切┸囕v先彈出棧（在它之后進入的車輛必需先退出車場為它讓路），再讓該車出棧，其他車輛再按原次序進棧（進入車場）。當車輛出棧完畢后，檢查迎候隊列（便道）中是否有車，有車則從隊列頭取出一輛車壓入棧中。

1、用棧模擬停車場，用隊列模擬車場外的便道，根據(jù)從終端讀入的輸入數(shù)據(jù)序列舉行模擬管理。

2、每次輸入完舉行輸出操作：若是車輛到達，輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，輸出離開的車牌號。

3、其中棧以挨次結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。

具體步驟：

1、定義棧：

typedefstruct

{

chardata[stacksize];

inttop;

}stack;

初始化棧：voidStackinit(stack*x)

voidStackinit(stack*x)

{

inti;

x->top=0;

for(i=0;idata[x->top]=NULL;

}

2、定義隊列：

typedefstructNode

{

chardata;

structNode*next;

}Node;

typedefstruct

{

structNode*head;

structNode*rear;

}squeue;

初始化隊列：intQueueinit(squeue*Q)

intQueueinit(squeue*Q)

{

Q->head=(Node*)malloc(sizeof(Node));

if(Q->head!=NULL)

{

Q->head->next=NULL;

Q->rear=Q->head;

returnOK;

}

else

returnERROR;

}

3、處理車輛到達的狀況intArrival(stack*s,squeue*Q)

intArrival(stack*s,squeue*Q)

{

charp;

Node*t;

cout>p;

if(s->toptop++;

coutdata[s->top]=p;

returnOK;

}

else

{

coutdata=p;

t->next=NULL;

Q->rear->next=t;

Q->rear=t;

returnOK;

}

}

處理車輛離開voidLeave(stack*s,stack*t,squeue*Q)

voidLeave(stack*s,stack*t,squeue*Q)

{

introom;

charp,q;

Node*n;

n=newNode;

if(s->top>0)

{

while(1)

{

couttop>room;

if(room>=1

}

while(s->top>room)

{

t->top++;

t->data[t->top]=s->data[s->top];

s->data[s->top]=NULL;

s->top--;

}

p=s->data[s->top];

s->data[s->top]=NULL;

s->top--;

while(t->top>=1)

{

s->top++;

s->data[s->top]=t->data[t->top];

t->data[t->top]=NULL;

t->top--;

}

couthead!=Q->rear)

q=n->data;

s->top++;

couttophead->next=n->next;

if(n==Q->rear)

Q->rear=Q->head;

s->data[s->top]=q;

delete(n);

}

else

cout>ch;

if(ch>=1

else

coutdata=i;

p->next=NULL;

if(*head==NULL)

{

*head=q=p;

q->next=*head;

}

else

{

p->next=q->next;

q->next=p;

q=p;

}

}

}

3、舉行約瑟夫嬉戲：voidJoseph(circularList*head,intt)

voidJoseph(circularList*head,intt)

{

Node*p,*q,*b;

b=newNode;

intr=1;

p=q=*head;

while(r)

{

for(inti=1;inext;

}

if(p==q)

r=0;

b=q;

p->next=q->next;

q=q->next;

coutdata>n;

while(n>n;

}

cout>m;

while(m>m;

}

CreatList(

cout>x;

if(x=='#')

*t=NULL;

else

{

*t=(btnode*)malloc(sizeof(btnode));

(*t)->data=x;

CreateTree(

CreateTree(

}

}

3、先序遍歷：voidPrecorder(Treet)

voidPrecorder(Treet)

{

if(t)

{

coutdata;

Precorder(t->Lchild);

Precorder(t->Rchild);

}

}

4、中序遍歷：voidInorder(Treet)

voidInorder(Treet)

{

if(t)

{

Inorder(t->Lchild);

coutdata;

Inorder(t->Rchild);

}

}

5、后序遍歷：voidPostorder(Treet)

voidPostorder(Treet)

{

if(t)

{

Postorder(t->Lchild);

Postorder(t->Rchild);

coutdata;

}

}

6、主程序：voidmain()

voidmain()

{

Treet;

CreateTree(

cout>n;

while(n>n;

}

for(intm=1;mlink=NULL;

ga[m]->vertex=m;

}

cout>e;

for(intk=0;k>i;

cin>>j;

p=newEdgeNode;

p->adjvex=j;

p->next=ga[i]->link;

ga[i]->link=p;

q=newEdgeNode;

q->adjvex=i;

q->next=ga[j]->link;

ga[j]->link=q;

}

}

3、深度優(yōu)先遍歷：voiddfs(Adjlist*g,intv0,intvisited[])

voiddfs(Adjlist*g,intv0,intvisited[])

{

coutlink;

while(p!=NULL)

{

if(visited[p->adjvex]==0)

{

dfs(g,p->adjvex,visited);

}

else

p=p->next;

}

}

4、廣度優(yōu)先遍歷：voidbfs(Adjlist*g,intv0,intvisited[])

voidbfs(Adjlist*g,intv0,intvisited[])

{

intv;

visited[v0]=1;

coutlink;

squeue*q;

q=newsqueue;

q->f=q->r=0;

do

{

while(p!=NULL)

{

v=p->adjvex;

if(visited[v]==0)

{

coutdata[q->r]=v;

q->r=q->r+1;

visited[v]=1;

}

p=p->next;

}

if(q->f!=q->r)

{

v=q->data[q->f];

q->f=q->f+1;

p=g[v]->link;

}

}while((p!=NULL)

}

5、主程序：voidmain()

voidmain()

{

Adjlistga;

build_adjlist(

intvisited[MAX];

for(inti=1;idata=i;

h[i]->link=NULL;

}

}

3、獵取關(guān)鍵字key：intkeygain(doublenum)

intkeygain(doublenum)

{

inta,sum=0;

a=num/1000000;

while(a>1)

{

sum+=a%10;

a=a/10;

}

a=num-floor(num/1000000)*1000000;

while(a>1)

{

sum+=a%10;

a=a/10;

}

returnsum%7;

}

4、輸入信息函數(shù)：voidinput(hashlist*h)

voidinput(hashlist*h)

{

Edgenode*p;

p=newEdgenode;

charname[8],address[8];

doublenumber;

intkey;

cout>name;

cout>number;

cout>address;

key=keygain(number);

p=h[key]->link;

if(p!=NULL)

{

while(p->num!=number

if(p->num==number)

coutname,name);

strcpy(q->ads,address);

q->num=number;

q->next=NULL;

p->next=q;

}

}

else

{

Edgenode*q=newEdgenode;

strcpy(q->name,name);

strcpy(q->ads,address);

q->num=number;

q->next=NULL;

h[key]->link=q;

}

}

5、查找函數(shù)：voidfindhash(hashlist*h)

voidfindhash(hashlist*h)

{

Edgenode*p,*q;

intx;

intkey;

doublenum2;

cout>num2;

key=keygain(num2);

p=newEdgenode;

p=h[key]->link;

if(p==NULL)

{

coutnum!=num2

if(p->num==num2)

{

cout>x;

if(x==1)

{

if(h[key]->link==p)

h[key]->link=p->next;

else

{

q=newEdgenode;

q=h[key]->link;

while(q->next==p)

q=q->next;

q->next=p->next;

delete(p);

}

coutlink;

while(p!=NULL)

{

c