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

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

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

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

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

5、xt=NULL; q->rear->next=p; q->rear=p; q->front->nnum+; /頭結(jié)點的數(shù)據(jù)域放上便道上所停車的輛數(shù) int outqueue(queue *q)/元素出隊列 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) /停車場滿 inqueue(q,x); / 在主程序部分的確是這個位置*cout<<"車牌號為"<<x<<"的車停在便道上第"<<q->front->nnum<<"號位置."<<endl;

7、 else cout<<"車牌號為"<<x<<"的車停在停車場第"<<s->top+1<<"號位置."<<endl; /細(xì)節(jié)：數(shù)組是從0記位的 void carleave(stack* s1,stack* s2,queue *q,int x)/處理車輛離開 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<<"車牌號為"<<x<<"的車離開停車場"<<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<<"車牌號為"<<y<<"的車開進停車場并停在"<<s1->top+1<<"號位置

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

10、t;>>>>>>>>>>>>>>>>"<<endl<<endl; cout<<">>>> 歡迎使用停車場程序 >>>>"<<endl<<endl;cout<<">>>>>>>>>>>>>>>>>>>>>>>

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

12、<endl; cin>>N;/這里N將作為棧能存放元素的數(shù)量 while(N<=0) cout<<"輸入錯誤，請再輸入:"<<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)還是離開(

13、D)?請輸入車輛的牌號："<<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<<"停車場系統(tǒng)即將關(guān)閉"<<endl; break; default:cout<&l

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

15、表開頭和下一個，兩指針依次挪動，符合題意就輸出結(jié)點數(shù)據(jù)，在調(diào)整指針，刪掉該結(jié)點。五，實驗方法與步驟#include"iostream"using namespace std; struct Nodeint data;Node* next;/定義一個類型void main()int m,n,j=1;cout<<"請輸入m的值："cin>>m;cout<<"請輸入n的值："cin>>n;Node* head=NULL;Node* s=new Node;/新建節(jié)點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人開始；按照理論應(yīng)有出隊序列：4 8 5 2 1 3 7 6. 2.實驗輸入輸出：七，討論總結(jié)1，循環(huán)鏈表（不帶頭結(jié)點）的建立：（1）建立一個新結(jié)點A，給其data域賦值，將其自身的next指向自己。（2）繼續(xù)申請新結(jié)點B，同樣賦值，把B->next=A->next，A->next=B。（3）要不斷插入結(jié)點，重復(fù)（2）即可，這樣就可創(chuàng)立一個不帶頭結(jié)點的循環(huán)鏈表?！?】約瑟夫環(huán)的順序存儲方法一，實驗?zāi)康?. 熟悉順序存儲。2. 熟悉對約瑟夫的順序存儲解決算法。 二，實驗要求1. 認(rèn)真閱讀和掌握

18、實驗內(nèi)容。2. 輸入和運行編出的圖與相關(guān)操作的程序。3. 保存程序運行結(jié)果 , 并結(jié)合輸入數(shù)據(jù)進行分析。三，所用儀器設(shè)備1. PC機。2. Microsoft Visual Studio運行環(huán)境。四，實驗原理#include"iostream"using namespace std;void main()int m,n,s=0,j=1;cout<<"請輸入m的值："cin>>m;cout<<"請輸入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");五，實驗結(jié)果六，討論就順序存儲來看，實現(xiàn)要比鏈?zhǔn)酱鎯β闊┮恍?，如果元素個數(shù)較多的話，移動的次數(shù)也會迅速的增加。實驗三：二叉樹的遍歷一，實驗?zāi)康?.熟悉二叉樹的定義和有關(guān)操作。2.加深理解和認(rèn)識對二叉樹進行遍歷的遞歸算

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

21、uot;iostream"using namespace std;struct nodeint data;node *Lchild;node *Rchild;void creatshu(node *nod)/建立二叉樹int x,y;cin>>x;/左子樹if(x=0) nod->Lchild=NULL;elsenode *p=new node;p->data=x;nod->Lchild=p;creatshu(nod->Lchild);cin>>y;/右子樹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;/頭指針,樹根cout<<"輸入樹根："<<endl;cin>>head->data;cout<<"請輸

24、入結(jié)點(結(jié)點為空是輸入0，結(jié)束也輸入0),先建左子樹，后建右子樹:"<<endl;creatshu(head);cout<<endl<<endl;cout<<"先序為："<<endl;preorder(head);cout<<endl<<endl;cout<<"中序為："<<endl;inorder(head);cout<<endl<<endl;cout<<"后序為："<<

25、;endl;postorder(head);cout<<endl<<endl;system("pause");六，實驗結(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é)本實驗較好的體現(xiàn)了二叉樹

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

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

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

29、"有幾條鄰接的邊："cin>>k;if(k!=0)for(j=0;j<k;j+)Vertex *p=new Vertex;cout<<"請輸入和Vertex"<<i<<"鄰接的點的序號："cin>>p->adjvex;s->next=p;s=p;p->next=NULL; /連接過程else vi.next=NULL;s=v+i+1; /每給一個頂點初始化完后，要將s指針指向下一個頂點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; /隊列指針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; /入隊r+;cout<<vx.adjvex<<" "vx.visit=1;p=p->next;if(f!=r)/v出隊x=qf;f+;p=vx.next;while(f!=r) | (p!=NULL); /書上的算法有問題void main()int n,x;cout<<"請輸入定點個數(shù)："cin>>n;Vertex *v=new Vertexn;cout<<

32、;endl;creat(v,n);for(int i=0;i<n;i+) vi.visit=0;cout<<"請輸入深度搜索的開始頂點號："cin>>x;cout<<endl;cout<<"深度優(yōu)先搜索順序為："depth(v,x);cout<<endl<<endl;for(int i=0;i<n;i+) vi.visit=0;cout<<"請輸入廣度搜索的開始頂點號："cin>>x;cout<<endl;cout&

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

35、 *a; /void hash1(char num11) /以電話號碼為關(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é)點 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é)點 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é)點 int i; phone=new pnode20; for(i=0;i<20;i+)

38、 phonei=new node; phonei->next=NULL; void create2() /新建節(jié)點 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<<"無此記錄"<<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<<"無此記錄"<<endl; void save() /保存用戶信息 int i; node *p; for(i=0;i<20;i+) p=phonei->next; while(p) fst