華北電力大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、華北電力大學(xué)實(shí) 驗(yàn) 報(bào) 告| 實(shí)驗(yàn)名稱 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn) 課程名稱 數(shù)據(jù)結(jié)構(gòu) | 專業(yè)班級(jí)：網(wǎng)絡(luò) 學(xué)生姓名： 學(xué) 號(hào)： 成 績(jī)：指導(dǎo)教師：牛為華 實(shí)驗(yàn)日期：2011.6.17 華 北 電 力 大 學(xué) 實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)一：停車場(chǎng)管理一，實(shí)驗(yàn)?zāi)康?.熟悉棧和隊(duì)的定義和有關(guān)操作。二，實(shí)驗(yàn)要求1.認(rèn)真閱讀和掌握實(shí)驗(yàn)內(nèi)容。2.用棧和隊(duì)解決停車場(chǎng)問(wèn)題。3.輸入和運(yùn)行編出的相關(guān)操作的程序。4.保存程序運(yùn)行結(jié)果 , 并結(jié)合輸入數(shù)據(jù)進(jìn)行分析。三，所用儀器設(shè)備1. PC機(jī)。2. Microsoft Visual Studio運(yùn)行環(huán)境。四，實(shí)驗(yàn)方法與步驟#include"iostream"usin

2、g namespace std;/棧在這里用順序結(jié)構(gòu)實(shí)現(xiàn)int N; int cnum; /定義作為車牌號(hào)的變量 struct stack/定義棧 int cstack9999;/這里隨便定義一個(gè)數(shù)字表示數(shù)組的長(zhǎng)度,因?yàn)楹竺鏁?huì)根據(jù)用戶輸入的N值作為停車場(chǎng)能夠停車的數(shù)量. int top; int size; ; struct node/定義隊(duì)列節(jié)點(diǎn)的類型 int nnum; node *next; ; struct queue/定義隊(duì)列 node *front,*rear; ; void initstack(stack *s)/初始化棧 s->top=-1; int instack(st

3、ack *s,int x)/元素進(jìn)棧 返回值類型為int 這個(gè)作為flag使用 /int 元素進(jìn)棧n; if(s->top=N-1) cout<<"停車場(chǎng)已滿!車將會(huì)停在便道上。"<<endl; return 0; else s->cstack+(s->top)=x; return 1; int outstack(stack *s)/元素出棧 if(s->top<0) cout<<"目前停車場(chǎng)內(nèi)一輛車也沒(méi)有"<<endl; return 0; else s->top-;

4、return s->cstacks->top+1; /幫剛才出棧的那臺(tái)車的號(hào)碼返回 void initqueue(queue *q)/初始化隊(duì)列 這里也想寫(xiě)成(*front,*rear) q->front=new node; q->rear=q->front; q->front->nnum=0; q->front->next=NULL; /隊(duì)列初始化要涉及到front和rear指針void inqueue(queue *q,int num1)/元素進(jìn)隊(duì)列 node *p=new node; p->nnum=num1; p->ne

5、xt=NULL; q->rear->next=p; q->rear=p; q->front->nnum+; /頭結(jié)點(diǎn)的數(shù)據(jù)域放上便道上所停車的輛數(shù) int outqueue(queue *q)/元素出隊(duì)列 node* p; int n; if(q->front=q->rear) return 0; else p=q->front->next; q->front->next=p->next; if(p->next=NULL) q->rear=q->front; n=p->nnum; delete p;

6、 q->front->nnum-; return n; void carrival(stack *s,queue *q,int x)/處理車輛到達(dá)的情況 int flag; flag=instack(s,x); /退出及返回值都正常 if(flag=0) /停車場(chǎng)滿 inqueue(q,x); / 在主程序部分的確是這個(gè)位置*cout<<"車牌號(hào)為"<<x<<"的車停在便道上第"<<q->front->nnum<<"號(hào)位置."<<endl;

7、 else cout<<"車牌號(hào)為"<<x<<"的車停在停車場(chǎng)第"<<s->top+1<<"號(hào)位置."<<endl; /細(xì)節(jié)：數(shù)組是從0記位的 void carleave(stack* s1,stack* s2,queue *q,int x)/處理車輛離開(kāi) int y; int a,n=0; while(s1->top>-1)&&(n=0) y=outstack(s1); if(y!=x) a=instack(s2,y); els

8、e n=1; if(y=x) cout<<"車牌號(hào)為"<<x<<"的車離開(kāi)停車場(chǎng)"<<endl; while(s2->top>-1) y=outstack(s2); n=instack(s1,y); a=outqueue(q); if(a!=0) y=a; n=instack(s1,y); cout<<"車牌號(hào)為"<<y<<"的車開(kāi)進(jìn)停車場(chǎng)并停在"<<s1->top+1<<"號(hào)位置

9、"<<endl; void main()/主程序 cout<<">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>&g

10、t;>>>>>>>>>>>>>>>>"<<endl<<endl; cout<<">>>> 歡迎使用停車場(chǎng)程序 >>>>"<<endl<<endl;cout<<">>>>>>>>>>>>>>>>>>>>>>>

11、>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>"<<endl<<endl; cout<<"請(qǐng)輸入一個(gè)數(shù)作為作為停車場(chǎng)的最大容車量:"<

12、<endl; cin>>N;/這里N將作為棧能存放元素的數(shù)量 while(N<=0) cout<<"輸入錯(cuò)誤，請(qǐng)?jiān)佥斎?"<<endl; cin>>N; char ch1; stack *s1,*s2; queue *q; int x; int flag; s1=new stack; s2=new stack; q=new queue; initstack(s1); initstack(s2); initqueue(q); flag=1; for(;) cout<<"車輛是到達(dá)(A)還是離開(kāi)(

13、D)?請(qǐng)輸入車輛的牌號(hào)："<<endl; cin>>ch1>>x; switch(ch1) case'A': case'a':carrival(s1,q,x); break; case'D': case'd':carleave(s1,s2,q,x); break; case'E': case'e':flag=0;cout<<"停車場(chǎng)系統(tǒng)即將關(guān)閉"<<endl; break; default:cout<&l

14、t;"輸入錯(cuò)誤!"<<endl; cout<<endl;if(flag=0) break; /對(duì)應(yīng)的系統(tǒng)關(guān)閉程序 system("pause");六，數(shù)據(jù)與結(jié)果輸入N為3實(shí)驗(yàn)二：約瑟夫環(huán)一，實(shí)驗(yàn)?zāi)康?.熟悉循環(huán)鏈表的定義和有關(guān)操作。二，實(shí)驗(yàn)要求1.認(rèn)真閱讀和掌握實(shí)驗(yàn)內(nèi)容。2用循環(huán)鏈表解決約瑟夫問(wèn)題。3.輸入和運(yùn)行編出的相關(guān)操作的程序。4.保存程序運(yùn)行結(jié)果 , 并結(jié)合輸入數(shù)據(jù)進(jìn)行分析。三，所用儀器設(shè)備3. PC機(jī)。4. Microsoft Visual Studio運(yùn)行環(huán)境。四，實(shí)驗(yàn)原理1.約瑟夫問(wèn)題解決方案： 用兩個(gè)指針?lè)謩e指向鏈

15、表開(kāi)頭和下一個(gè)，兩指針依次挪動(dòng)，符合題意就輸出結(jié)點(diǎn)數(shù)據(jù)，在調(diào)整指針，刪掉該結(jié)點(diǎn)。五，實(shí)驗(yàn)方法與步驟#include"iostream"using namespace std; struct Nodeint data;Node* next;/定義一個(gè)類型void main()int m,n,j=1;cout<<"請(qǐng)輸入m的值："cin>>m;cout<<"請(qǐng)輸入n的值："cin>>n;Node* head=NULL;Node* s=new Node;/新建節(jié)點(diǎn)for(int i=1;i&l

16、t;=n;i+)Node* p=new Node;/新建指針p->data=n+1-i;/p的數(shù)據(jù)域賦值p->next=head;head=p;if(i=1) s=head;Node* p=new Node;p=head;s->next=head;while(p!=s)while(j!=m)p=p->next;s=s->next;j+;cout<<p->data;s->next=p->next;delete p;p=s->next;j=1;cout<<p->data<<endl;delete p;s

17、ystem(“pause”);六，數(shù)據(jù)與結(jié)果1.輸入：總?cè)藬?shù)8；數(shù)到 4出列；從第 1人開(kāi)始；按照理論應(yīng)有出隊(duì)序列：4 8 5 2 1 3 7 6. 2.實(shí)驗(yàn)輸入輸出：七，討論總結(jié)1，循環(huán)鏈表（不帶頭結(jié)點(diǎn)）的建立：（1）建立一個(gè)新結(jié)點(diǎn)A，給其data域賦值，將其自身的next指向自己。（2）繼續(xù)申請(qǐng)新結(jié)點(diǎn)B，同樣賦值，把B->next=A->next，A->next=B。（3）要不斷插入結(jié)點(diǎn)，重復(fù)（2）即可，這樣就可創(chuàng)立一個(gè)不帶頭結(jié)點(diǎn)的循環(huán)鏈表?！?】約瑟夫環(huán)的順序存儲(chǔ)方法一，實(shí)驗(yàn)?zāi)康?. 熟悉順序存儲(chǔ)。2. 熟悉對(duì)約瑟夫的順序存儲(chǔ)解決算法。 二，實(shí)驗(yàn)要求1. 認(rèn)真閱讀和掌握

18、實(shí)驗(yàn)內(nèi)容。2. 輸入和運(yùn)行編出的圖與相關(guān)操作的程序。3. 保存程序運(yùn)行結(jié)果 , 并結(jié)合輸入數(shù)據(jù)進(jìn)行分析。三，所用儀器設(shè)備1. PC機(jī)。2. Microsoft Visual Studio運(yùn)行環(huán)境。四，實(shí)驗(yàn)原理#include"iostream"using namespace std;void main()int m,n,s=0,j=1;cout<<"請(qǐng)輸入m的值："cin>>m;cout<<"請(qǐng)輸入n的值："cin>>n;int *a=new intn;for(int i=0;i<

19、n;i+)ai=i+1;while(n!=0)if(j=m)cout<<as;j=0;if(s!=n-1)for(int i=s;i<n-1;i+)ai=ai+1;n-;j+;if(s>n-1) s=0;elsej+;s+;if(s>n-1)s=0;delete a;cout<<endl;system("pause");五，實(shí)驗(yàn)結(jié)果六，討論就順序存儲(chǔ)來(lái)看，實(shí)現(xiàn)要比鏈?zhǔn)酱鎯?chǔ)麻煩一些，如果元素個(gè)數(shù)較多的話，移動(dòng)的次數(shù)也會(huì)迅速的增加。實(shí)驗(yàn)三：二叉樹(shù)的遍歷一，實(shí)驗(yàn)?zāi)康?.熟悉二叉樹(shù)的定義和有關(guān)操作。2.加深理解和認(rèn)識(shí)對(duì)二叉樹(shù)進(jìn)行遍歷的遞歸算

20、法。二，實(shí)驗(yàn)要求1.認(rèn)真閱讀和掌握實(shí)驗(yàn)內(nèi)容。2.對(duì)二叉樹(shù)進(jìn)行三種遍歷。3.輸入和運(yùn)行給出的二叉樹(shù)與相關(guān)操作的程序。4.保存程序運(yùn)行結(jié)果 , 并結(jié)合輸入數(shù)據(jù)進(jìn)行分析。三，所用儀器設(shè)備3. PC機(jī)。4. Microsoft Visual Studio運(yùn)行環(huán)境。四，實(shí)驗(yàn)原理1. 先序遍歷：（1）訪問(wèn)根結(jié)點(diǎn)。 （2）按先序遍歷原則遍歷左子樹(shù)。 （3）按先序遍歷原則遍歷右子樹(shù)。2.中序遍歷：（1）按中序遍歷原則遍歷左子樹(shù) （2）訪問(wèn)根結(jié)點(diǎn)。 （3）按中序遍歷原則遍歷右子樹(shù)3.后序遍歷：（1）按后序遍歷原則遍歷左子樹(shù) （2）按后序遍歷原則遍歷右子樹(shù) （3）訪問(wèn)根結(jié)點(diǎn)。五，實(shí)驗(yàn)方法與步驟#include&q

21、uot;iostream"using namespace std;struct nodeint data;node *Lchild;node *Rchild;void creatshu(node *nod)/建立二叉樹(shù)int x,y;cin>>x;/左子樹(shù)if(x=0) nod->Lchild=NULL;elsenode *p=new node;p->data=x;nod->Lchild=p;creatshu(nod->Lchild);cin>>y;/右子樹(shù)if(y=0) nod->Rchild=NULL;elsenode *p=

22、new node;p->data=y;nod->Rchild=p;creatshu(nod->Rchild);void preorder(node *nod)/前序遍歷if(nod!=NULL)cout<<nod->data<<" "preorder(nod->Lchild);preorder(nod->Rchild);void inorder(node *nod)/中序遍歷if(nod!=NULL)inorder(nod->Lchild);cout<<nod->data<<&q

23、uot; "inorder(nod->Rchild);void postorder(node *nod)/后續(xù)遍歷if(nod!=NULL)postorder(nod->Lchild);postorder(nod->Rchild);cout<<nod->data<<" "void main()node *head=new node;/頭指針,樹(shù)根cout<<"輸入樹(shù)根："<<endl;cin>>head->data;cout<<"請(qǐng)輸

24、入結(jié)點(diǎn)(結(jié)點(diǎn)為空是輸入0，結(jié)束也輸入0),先建左子樹(shù)，后建右子樹(shù):"<<endl;creatshu(head);cout<<endl<<endl;cout<<"先序?yàn)椋?quot;<<endl;preorder(head);cout<<endl<<endl;cout<<"中序?yàn)椋?quot;<<endl;inorder(head);cout<<endl<<endl;cout<<"后序?yàn)椋?quot;<<

25、;endl;postorder(head);cout<<endl<<endl;system("pause");六，實(shí)驗(yàn)結(jié)果與數(shù)據(jù) 1.輸入1,2,3,0,0,4,5,0,0,6,7,0,0,0,8,9,0,0,10,11,12,0,0,13,0,0,14,0,0, 按照原理先序遍歷應(yīng)輸出：1,2,3,4,5,6,7,8,9,10,11,12,13,14 中序遍歷應(yīng)輸出：3,2,5,4,7,6,1,9,8,12,11,13,10,14 后序遍歷應(yīng)輸出：3,5,7,6,4,2,9,12,13,11,14,10,8,1七，討論與總結(jié)本實(shí)驗(yàn)較好的體現(xiàn)了二叉樹(shù)

26、遍歷的遞歸思想。用遞歸算法編起來(lái)算法語(yǔ)句較為簡(jiǎn)單，但調(diào)用過(guò)程太多，非遞歸語(yǔ)句調(diào)用的次數(shù)上會(huì)有優(yōu)勢(shì)，但代碼量會(huì)增加。實(shí)驗(yàn)四：圖的遍歷一，實(shí)驗(yàn)?zāi)康?. 熟悉圖的鄰接表表示。2. 熟悉對(duì)圖的鄰接表表示分別進(jìn)行深度和廣度優(yōu)先遍歷的算法。 二，實(shí)驗(yàn)要求1. 認(rèn)真閱讀和掌握實(shí)驗(yàn)內(nèi)容。2. 對(duì)圖的鄰接表表示分別進(jìn)行深度和廣度優(yōu)先遍歷的算法。3. 輸入和運(yùn)行編出的圖與相關(guān)操作的程序。4. 保存程序運(yùn)行結(jié)果 , 并結(jié)合輸入數(shù)據(jù)進(jìn)行分析。三，所用儀器設(shè)備5. PC機(jī)。6. Microsoft Visual Studio運(yùn)行環(huán)境。四，實(shí)驗(yàn)原理 1.圖的深度優(yōu)先遍歷（DFS）：從圖的某一點(diǎn)出發(fā)，先訪問(wèn)該點(diǎn)的頂點(diǎn)，后選

27、取一個(gè)與該點(diǎn)鄰接且未被訪問(wèn)過(guò)的頂點(diǎn)A，在訪問(wèn)A后，再?gòu)腁出發(fā)進(jìn)行如上訪問(wèn)，重復(fù)此過(guò)程，直到某個(gè)頂點(diǎn)的所有鄰接點(diǎn)都被訪問(wèn)過(guò)時(shí)，回退到尚有鄰接點(diǎn)未被訪問(wèn)過(guò)的頂點(diǎn)，再?gòu)脑擁旤c(diǎn)出發(fā)，重復(fù)上述過(guò)程，直到所有的被訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)過(guò)，這時(shí)遍歷結(jié)束。2.圖的廣度優(yōu)先遍歷（BFS）：訪問(wèn)圖的某一頂點(diǎn)A，從A出發(fā)，先訪問(wèn)A的鄰接點(diǎn)B1,B2,B3,B4，然后再順序訪問(wèn)B1,B2,B3,B4的所有鄰接的尚未訪問(wèn)過(guò)的全部頂點(diǎn)，再?gòu)倪@些被訪問(wèn)過(guò)的頂點(diǎn)出發(fā)，逐次訪問(wèn)與它們連接且未被訪問(wèn)過(guò)的頂點(diǎn)。以此類推，直到所有頂點(diǎn)都被訪問(wèn)完為止。五，實(shí)驗(yàn)方法與步驟#include"iostream"us

28、ing namespace std;struct Vertex /因?yàn)檫吂?jié)點(diǎn)沒(méi)有權(quán)值，所以想用一種同構(gòu)的結(jié)構(gòu)來(lái)簡(jiǎn)化結(jié)構(gòu)，讓程序可讀性更高int adjvex;/頂點(diǎn)域Vertex *next;int visit;/是否訪問(wèn)過(guò);/初始化鄰接表void creat(Vertex v,int n)int k,i,j;for(i=0;i<n;i+)vi.adjvex=i; /給頂點(diǎn)標(biāo)上序號(hào)Vertex *s=NULL;s=v; /s作為滾動(dòng)指針，不用分配實(shí)際空間for(i=0;i<n;i+)cout<<"請(qǐng)輸入Vertex"<<i<<

29、"有幾條鄰接的邊："cin>>k;if(k!=0)for(j=0;j<k;j+)Vertex *p=new Vertex;cout<<"請(qǐng)輸入和Vertex"<<i<<"鄰接的點(diǎn)的序號(hào)："cin>>p->adjvex;s->next=p;s=p;p->next=NULL; /連接過(guò)程else vi.next=NULL;s=v+i+1; /每給一個(gè)頂點(diǎn)初始化完后，要將s指針指向下一個(gè)頂點(diǎn)cout<<endl;/深度優(yōu)先搜索void depth

30、(Vertex v,int x)cout<<vx.adjvex<<" "vx.visit=1;Vertex *p=new Vertex;p=vx.next;while(p!=NULL)x=p->adjvex;if(vx.visit=0)depth(v,x);p=p->next;/廣度優(yōu)先搜索void breadth(Vertex v,int x)cout<<vx.adjvex<<" "vx.visit=1;int f=0; /隊(duì)列指針int r=0;int q20;Vertex *p=new V

31、ertex;p=vx.next;dowhile(p!=NULL)x=p->adjvex;if(vx.visit=0)qr=x; /入隊(duì)r+;cout<<vx.adjvex<<" "vx.visit=1;p=p->next;if(f!=r)/v出隊(duì)x=qf;f+;p=vx.next;while(f!=r) | (p!=NULL); /書(shū)上的算法有問(wèn)題void main()int n,x;cout<<"請(qǐng)輸入定點(diǎn)個(gè)數(shù)："cin>>n;Vertex *v=new Vertexn;cout<<

32、;endl;creat(v,n);for(int i=0;i<n;i+) vi.visit=0;cout<<"請(qǐng)輸入深度搜索的開(kāi)始頂點(diǎn)號(hào)："cin>>x;cout<<endl;cout<<"深度優(yōu)先搜索順序?yàn)椋?quot;depth(v,x);cout<<endl<<endl;for(int i=0;i<n;i+) vi.visit=0;cout<<"請(qǐng)輸入廣度搜索的開(kāi)始頂點(diǎn)號(hào)："cin>>x;cout<<endl;cout&

33、lt;<"廣度優(yōu)先搜索順序?yàn)椋?quot;breadth(v,x);cout<<endl;system("pause");六，結(jié)果與數(shù)據(jù) 輸入以下圖的信息并進(jìn)行遍歷： 0213七，討論與結(jié)論重點(diǎn)在于廣度優(yōu)先搜索與深度優(yōu)先搜索的算法，以及一開(kāi)始圖的初始化問(wèn)題。實(shí)驗(yàn)五：哈希表一，實(shí)驗(yàn)?zāi)康?. 熟悉建立哈希表的方法。二，實(shí)驗(yàn)要求1. 認(rèn)真閱讀和掌握實(shí)驗(yàn)內(nèi)容。2. 輸入和運(yùn)行編出的相關(guān)操作的程序。3. 保存程序運(yùn)行結(jié)果 , 并結(jié)合輸入數(shù)據(jù)進(jìn)行分析。三，所用儀器設(shè)備1. PC機(jī)。2. Microsoft Visual Studio運(yùn)行環(huán)境。四，實(shí)驗(yàn)方法與步

34、驟#include"iostream"#include"string" #include"fstream"using namespace std;#define NULL 0 unsigned int key; unsigned int key2; int *p; struct node /建節(jié)點(diǎn) char name8,address20; char num11; node * next; ; typedef node* pnode; typedef node* mingzi; node *phone; node *nam; node

35、 *a; /void hash1(char num11) /以電話號(hào)碼為關(guān)鍵字建立的哈希函數(shù)int i=0;int s=0;for(i=0;i<11;i+)s=(int)numi-48)+s; key=s%7; /void hash2(char name8) /哈希函數(shù) int i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%20; node* input() /輸入節(jié)點(diǎn) node *temp; temp = new node; temp->next=NULL; cout<&

36、lt;"輸入姓名："<<endl; cin>>temp->name; cout<<"輸入地址："<<endl; cin>>temp->address; cout<<"輸入電話："<<endl; cin>>temp->num; return temp; int apend() /添加節(jié)點(diǎn) node *newphone; node *newname; newphone=input(); newname=newphone; ne

37、wphone->next=NULL; newname->next=NULL; hash1(newphone->num); hash2(newname->name); newphone->next = phonekey->next; phonekey->next=newphone; newname->next = namkey2->next; namkey2->next=newname; return 0; void create() /新建節(jié)點(diǎn) int i; phone=new pnode20; for(i=0;i<20;i+)

38、 phonei=new node; phonei->next=NULL; void create2() /新建節(jié)點(diǎn) int i; nam=new mingzi20; for(i=0;i<20;i+) nami=new node; nami->next=NULL; void list() /顯示列表 int i; node *p; for(i=0;i<20;i+) p=phonei->next; while(p) cout<<p->name<<'_'<<p->address<<'_&

39、#39;<<p->num<<endl; p=p->next; void list2() /顯示列表 int i; node *p; for(i=0;i<20;i+) p=nami->next; while(p) cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl; p=p->next; void find(char num11) /查找用戶信息 hash1(num); no

40、de *q=phonekey->next; while(q!= NULL) if(strcmp(num,q->num)=0) break; q=q->next; if(q) cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl; else cout<<"無(wú)此記錄"<<endl; void find2(char name8) /查找用戶信息 hash2(nam

41、e); node *q=namkey2->next; while(q!= NULL) if(strcmp(name,q->name)=0) break; q=q->next; if(q) cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl; else cout<<"無(wú)此記錄"<<endl; void save() /保存用戶信息 int i; node *p; for(i=0;i<20;i+) p=phonei->next; while(p) fst