1、數據結構課程設計報告學院：信息工程專業：信息工程老師：陳占龍姓名：郝寶亮學號：20111001149班號：116112-052013年1月 目錄控制臺1.停車場管理32.個人電話號碼查詢系統63.排序運用124.“火燒連營”問題165.管道鋪設施工的最佳方案選擇19MFC1.停車場管理272.個人電話號碼查詢系統293.排序運用34總結自我總結38實習題目一 停車場管理【問題描述】設停車場是一個可停放 n 輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內已停滿n 輛汽車，則后來

2、的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內某輛車要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。【設計思想】以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數據序列進行模擬管理。每一組輸入數據包括三個數據項：汽車“到達”或“離去”信息，汽車牌照號以及到達或離去的時刻。對每一組輸入的數據進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車輛離去，則輸

3、出汽車在停車場內停留的時間和應交納的費用（在便道上停留的時間不收費）。棧以順序結構實現，隊列以鏈表結構實現。需另設一個棧，臨時停放為給要離去的汽車讓路而從停車場推出來的汽車，也用順序存儲結構實現。輸入數據按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數據項：汽車的牌照號碼和進入停車場的時刻?！驹O計表示】輸入數據判斷狀態離開停車計算停車費用便道車輛進入停車場判斷停車場是否有空余否是調用棧、對列的入棧、出棧、進隊列、出隊列函數。停放在便道調用入隊列函數進入停車場調用入棧函數退出本系統【代碼實現】/主函數的實現#include "stdafx.h"#include &

4、quot;iostream.h"#include "queue.h"#include "stack.h"int main(int argc, char* argv)cout<<"請輸入停車場的容量:"int n,num,time;cin>>n;char a;cout<<"請輸入停車場車輛的情況:"<<endl;cin>>a>>num>>time;SeqStack<char,int,int> s1;SeqStac

5、k<char,int,int> s2;LinkedQueue<char,int,int> q;s1.Push(a,num,time);cout<<"車牌為 "<<num<<" 在停車場的位置為:"<<s1.getSize()<<endl;while (a!='E')cin>>a>>num>>time;int time1=time;if (a='A')if (s1.Find(num)=true)cout&l

6、t;<"車牌為"<<num<<"車停在"<<s1.getnum(num)+1<<"位置"<<" 請重新輸入!"<<endl;continue;elseif (s1.getSize()<n)s1.Push(a,num,time);cout<<"車牌為 "<<num<<" 在停車場的位置為:"<<s1.getSize()<<endl;el

7、seq.EnQueue(a,num,time);cout<<"車牌為 "<<num<<" 在便道上的位置為:"<<q.getSize()<<endl;if (a='D')if (s1.Find(num)=true) /先找到此車int b=s1.gettime(num);cout<<"車牌為 "<<num<<" 在停車場停留的時間是:"<<time-b<<endl;for (int

8、 i=s1.getnum(num)+1;i<s1.getSize();i+)s1.Pop(a,num,time); /將車輛放在零時棧s2.Push(a,num,time);s1.Pop(a,num,time); /退出此車for (i=0;i<s2.getSize();i+) /將零時棧的車輛放在停車場s2.Pop(a,num,time);s1.Push(a,num,time);if(q.getSize()>0) /如果便道中有車，則將便道的車進入停車場q.DeQueue(a,num,time);s1.Push(a,num,time1);elsecout<<&q

9、uot;車牌為 "<<num<<" 車在便道上，不在停車場！"<<endl;return 0;【運行結果】實習題目二 個人電話號碼查詢系統【問題描述】人們在日常生活中經常需要查找某個人或某個單位的電話號碼，本實驗將實現一個簡單的個人電話號碼查詢系統，根據用戶輸入的信息（例如姓名等）進行快速查詢?；疽螅海?） 在外存上，用文件保存電話號碼信息；（2） 在內存中，設計數據結構存儲電話號碼信息；（3） 提供查詢功能：根據姓名實現快速查詢；（4） 提供其他維護功能：例如插入、刪除、修改等?！驹O計思想】由于需要管理的電話號碼信息較多，

10、而且要在程序運行結束后仍然保存電話號碼信息，所以電話號碼信息采用文件的形式存放到外存中。在系統運行時，需要將電話號碼信息從文件調入內存來進行查找等操作，為了接收文件中的內容，要有一個數據結構與之對應，可以設計如下結構類型的數組來接收數據：const int max=10;struct TeleNumberstring name; /姓名string phoneNumber; /固定電話號碼string mobileNumber; /移動電話號碼string email; /電子郵箱 Telemax;為了實現對電話號碼的快速查詢，可以將上述結構數組排序，以便應用折半查找，但是，在數組中實現插入和

11、刪除操作的代價較高。如果記錄需頻繁進行插入或刪除操作，可以考慮采用二叉搜索樹組織電話號碼信息，則查找和維護都能獲得較高的時間性能。更復雜地，需要考慮該二叉搜索樹是否平衡，如何使之達到平衡?！驹O計表示】讀取內存中的文件，到數組中，并建立二叉搜索樹輸入操作選擇修改刪除添加查找【代碼實現】/結構體的實現#include <iostream>#include "stdlib.h"#include <string>using namespace std;struct TeleNumber;istream &operator>>(istrea

12、m &is,TeleNumber &c); /使編譯器識別重載的運算符ostream &operator<<(ostream &os,TeleNumber &c);struct TeleNumberstring name;string phoneNumber;string mobileNumber;string email;friend istream &operator>>(istream &is,TeleNumber &c); /重載>>friend ostream &operato

13、r<<(ostream &os,TeleNumber &c); /重載<<Tele10;istream &operator>>(istream &is,TeleNumber &c)is>>>>c.phoneNumber>>c.mobileNumber>>c.email; /輸入結構體return is;ostream &operator<<(ostream &os,TeleNumber &c) /輸出結構體os<<

14、;<<setw(10)<<setw(15)<<c.phoneNumber<<setw(20)<<c.mobileNumber<<setw(20)<<c.email;return os;/二叉搜索樹的實現#include "stdlib.h"struct BSTNode /TeleNumber(E)TeleNumber data;BSTNode *left,*right;BSTNode():left(NULL),right(NULL)BSTNode(const TeleNumber

15、 d,BSTNode *L=NULL,BSTNode *R=NULL):data(d),left(L),right(R)BSTNode()void setData(TeleNumber d)data=d;TeleNumber getData()return data;class BSTpublic:BST():root(NULL)BST()bool Insert(const TeleNumber& e1)return Insert(e1,root);bool Remove(const string x)return Remove(x,root);bool Modify(const st

16、ring x,BSTNode *&ptr);BSTNode *getroot()return root;BSTNode *Search(const string x,BSTNode *ptr);private:BSTNode *root;bool Insert(const TeleNumber& e1,BSTNode *&ptr);bool Remove(const string x,BSTNode *&ptr);/插入到二叉搜索樹bool BST:Insert(const TeleNumber& e1,BSTNode *&ptr)int i=0

17、;if (ptr=NULL)ptr=new BSTNode(e1);if (ptr=NULL)cerr<<"Out of space"<<endl;exit(1);return true;else if (in.substr(i,i+1)0)<int(ptr->.substr(i,i+1)0)Insert(e1,ptr->left);else if (in.substr(i,i+1)0)>int(ptr->.substr(i,i+1)0)Insert(e1,ptr->right);elsereturn false;

18、/刪除二叉搜索樹中的某結點bool BST:Remove(const string x,BSTNode *&ptr)BSTNode *temp;if (ptr!=NULL)if (int(x.substr(0,1)0)<int(ptr->.substr(0,1)0)Remove(x,ptr->left);else if (int(x.substr(0,1)0)>int(ptr->.substr(0,1)0)Remove(x,ptr->right);else if (ptr->left!=NULL&&ptr->right!=

19、NULL)temp=ptr->right;while (temp->left!=NULL)temp=temp->left;ptr->data=temp->data;Remove(ptr->,ptr->right);elsetemp=ptr;if (ptr->left=NULL)ptr=ptr->right;else ptr=ptr->left;delete temp;return true;return false;/在二叉搜索樹的某個值BSTNode *BST:Search(const string x,BSTNode *ptr)i

20、f (ptr=NULL)return NULL;else if (int(x.substr(0,1)0)<int(ptr->.substr(0,1)0)return Search(x,ptr->left);else if (int(x.substr(0,1)0)>int(ptr->.substr(0,1)0)return Search(x,ptr->right);elsereturn ptr; ;bool BST:Modify(const string x,BSTNode *&ptr)ptr=Search(x,root);cin>>ptr

21、->data;return true;/主函數的實現#include <iostream>#include <fstream>#include <stdlib.h>#include <iomanip>using namespace std;#include "tele.h"#include "BST.H"int main(int argc, char* argv)int a;string str;BST bst;BSTNode *b;cout<<"*歡迎使用個人電話號碼查詢系統*

22、"<<endl;cout<<"*| 1.查找聯系人 |*"<<endl;cout<<"*| 2.添加聯系人 |*"<<endl;cout<<"*| 3.刪除聯系人 |*"<<endl;cout<<"*| 4.修改聯系人 |*"<<endl;cout<<"*| 5.退出本系統 |*"<<endl;int i=0;ifstream fin("C.tx

23、t");while(!fin.eof()fin>>Telei;bst.Insert(Telei);i+;fin.close();while (a!=5)cout<<"請輸入您的選擇:"cin>>a;switch(a)case 1: cout<<"請輸入你要查找的名字:"cin>>str;if(bst.Search(str,bst.getroot()=NULL)cout<<"沒有此聯系人!"<<endl;elsecout<<bst.

24、Search(str,bst.getroot()->data<<endl;break;case 2:cout<<"請輸入要添加的聯系人:"cin>>Telei;bst.Insert(Telei);break;case 3:cout<<"請輸入要刪除的聯系人:"cin>>str;bst.Remove(str);break;case 4:cout<<"請輸入要修改的聯系人:"cin>>str;bst.Modify(str,b);break;case

25、5:cout<<"謝謝使用個人電話號碼查詢系統!"<<endl;break;return 0;【運行結果】實習題目三 排序應用【問題描述】假定文本文件 A1.txt 中是我校所有參加南望山莊二期挑房職工的信息，請編寫程序，讀出文件中的內容，再按挑房的先后次序排隊后將排序號和姓名以文本方式存放到文件A2.txt中。排隊原則： 先按職稱排，同職稱按分房工齡排，同工齡按年齡排。職稱編號： 校級干部 0教授、正處級 1副教授、副處級 2講師、科級 3其他 4【設計思想】先將文本文檔的內容讀到數組中，重載輸入輸出號，使得文本文檔中的每一行為一個元素，然后按照要

26、用冒泡排序法。排序后，并將有序的結果輸入到文本文檔中【設計表示】讀取文本文件調用排序函數排序將排序后的信息寫入文本文件【代碼實現】#include <string>#include <iomanip>using namespace std;struct staff;istream &operator>>(istream &is,staff &c);ostream &operator<<(ostream &os,staff &c);const int max=1000;struct staff /結構

27、體包括職工信息string name; /姓名string titleID; /職稱編號string workingage; /工齡string age; /年齡friend istream &operator>>(istream &is,staff &c); /重載<<,>>friend ostream &operator<<(ostream &is,staff &c);stamax;istream &operator>>(istream &is,staff &

28、c)is>>>>c.titleID>>c.workingage>>c.age;return is;ostream &operator<<(ostream &os,staff &c)os<<setiosflags(ios_base:left)<<setw(12)<<<<setiosflags(ios_base:left)<<setw(10)<<c.titleID<<setiosflags(ios_base:

29、left)<<setw(10)<<c.workingage<<setiosflags(ios_base:left)<<setw(10)<<c.age<<endl;return os;/冒泡排序法進行排序void BubbleSort(staff v,int n)for (int i=2;i<n;i+)for (int j=n-1;j>=i;j-)if (atof(vj-1.titleID.c_str()>atoi(vj.titleID.c_str()staff temp=vj-1;vj-1=vj;vj=t

30、emp;if (atof(vj-1.titleID.c_str()=atoi(vj.titleID.c_str()if (atof(vj-1.workingage.c_str()>atoi(vj.workingage.c_str()staff temp=vj-1;vj-1=vj;vj=temp;if (atof(vj-1.workingage.c_str()=atoi(vj.workingage.c_str()if (atof(vj-1.age.c_str()>atoi(vj.age.c_str()staff temp=vj-1;vj-1=vj;vj=temp;#include &

31、quot;stdafx.h"#include "staff.h"#include "sort.h"#include <iostream>#include <fstream>#include <stdlib.h>using namespace std;int main(int argc, char* argv)int i=0;ifstream fin("a1.txt"); /將a1.txt的內容讀到結構體數組中while(!fin.eof()fin>>stai;i+;fin.cl

32、ose();BubbleSort(sta,i); /調用排序函數BubbleSortfor (int j=0;j<i;j+)cout<<staj;ofstream fon("a2.txt"); /將排序后的內容寫到a2.txt中for (j=0;j<i;j+)fon<<staj;fon.close();return 0;【運行結果】實習題目四 “火燒連營”問題【問題描述】“火燒連營”是三國演義中的著名典故之一廣為流傳，假定文本文件c1.txt 是火燒連營中的軍營分布圖，每個字符A 代表一個營帳，營帳是可燃物，其他字符代表不可燃的空白地段，

33、文件共有40 行70 列，請你編寫程序，讀入該文件的內容，再從鍵盤輸入任意點的x 和y值（x<70,y<40）作為著火點，“火燒連營”后，被燃燒的營帳標上字符X，并把整個結果輸出到文件c2.txt 中?！驹O計思想】本題首先輸入某個點的位置，判斷此坐標是否為著火點。若是著火點，則從此位置開始上下左右尋找其相鄰點，判斷其是否為著火點。程序設計時可以先開辟一個堆棧，先將著火點壓棧，然后重復操作：棧頂點出棧并標記X，同時將符合被燃燒條件的鄰居點入棧，直到?？諡橹?。【設計表示】輸入點的坐標坐標的值為A時，將此A變成X，并判斷上下左右的值，若為A，將此點壓棧，并判斷棧是否為空當x>39或

34、y>69重新輸入當此坐標的值為.時，重新輸入否，則循環否，退頂端的元素 【代碼表示】/結構體表示點struct items /結構體x為某點的x坐標值，y為某點的y坐標值int x,y;temp;SeqStack<items> st(40*70);void path(char str4070,int x,int y)strxy='X' /將可燃點的值A換成Xif (strxy-1='A')temp.x=x;temp.y=y-1;st.Push(temp);if (strxy+1='A')temp.x=x;temp.y=y+1;s

35、t.Push(temp);if (strx-1y='A')temp.x=x-1;temp.y=y;st.Push(temp);if (strx+1y='A')temp.x=x+1;temp.y=y;st.Push(temp);if (st.IsEmpty()=false)st.Pop(temp);path(str,temp.x,temp.y);#include "stdafx.h"#include "stack.h"#include "iostream.h"#include <fstream>

36、;using namespace std;int main(int argc, char* argv)char str4070;ifstream infile;in("c1.txt"); for(int i=0;i<40;i+) /將c1.txt中內容讀到一個二維數組中for(int j=0;j<70;j+)infile>>strij;in();for(i=0;i<40;i+)for(int j=0;j<70;j+)cout<<strij;cout<<endl;int x,y;cout<<"請

37、輸入著火點:"cin>>x>>y;while (strxy='.')cout<<"您輸入的信息不對，請重新輸入:"cin>>x>>y;path(str,x,y);for(i=0;i<40;i+)for(int j=0;j<70;j+)cout<<strij;cout<<endl;ofstream fon("c2.txt"); /將點燃后的帳篷發布圖存到c2.txt中for(i=0;i<40;i+)for(int j=0;j<

38、;70;j+)fon<<strij;fon<<endl;fon.close();return 0;【運行結果】實習題目五 管道鋪設施工的最佳方案選擇【問題描述】需要在某個城市的n 個居民區之間鋪設煤氣管道，則在這n 個居民區之間只要鋪設n-1條管道即可。假設任意兩個居民區之間都可以架設管道，但由于地理環境的不同，所需經費不同。選擇最有的施工方案能使總投資盡可能少，這個問題即為求網的“最小生成樹”。網采用鄰接矩陣為存儲結構，以頂點對（i,j）的形式輸出最小生成樹的邊。【設計思想】可選用Kruskal 算法或Prim 算法來求網的最小生成樹，無論哪一個算法都要選好恰當的輔助

39、數據結構，以存放邊或頂點的集合。若采用Kruskal 算法，則為選取當前權值最小的邊，還要對邊按權值進行非減序的排序?！敬a實現】/鄰接矩陣的實現class Graphmtxpublic: Graphmtx(int sz=30,int max=300); Graphmtx () delete VerticesList; delete Edge;char getValue (int i) /return VerticesListi;return i>=0&&i<=numVertices?VerticesListi:NULL; int getWeight (int v1

40、, int v2) return v1 != -1 && v2 != -1 ? Edgev1v2 : 0;int NumberOfEdges()return numEdges; int NumberOfVertices()return numVertices; int getFirstNeighbor (int v);int getNextNeighbor (int v, int w);bool insertVertex (const int& vertex);bool insertEdge (int v1, int v2, int cost);bool removeV

41、ertex (int v);bool removeEdge (int v1, int v2);int getVertexPos (int vertex) for (int i=0; i<numVertices;i+)if (VerticesListi=vertex) return i;return -1;int maxVertices;int numEdges;int numVertices;int *VerticesList; int *Edge;const int maxWeight;Graphmtx:Graphmtx(int sz, int max):maxWeight(max)

42、maxVertices=sz; numVertices=0; numEdges=0;int i, j;VerticesList = new intmaxVertices; Edge = (int *) new int *maxVertices;for (i = 0; i < maxVertices; i+)Edgei = new intmaxVertices; for (i = 0; i < maxVertices; i+) for (j = 0; j < maxVertices; j+)Edgeij=(i=j)?0:maxWeight; bool Graphmtx:inse

43、rtVertex(const int& vertex)if (numVertices=maxVertices)return false;VerticesListnumVertices+=vertex;return true;bool Graphmtx:insertEdge(int v1,int v2,int cost)if (v1>-1&&v1<numVertices&&v2>-1&&v2<numVertices&&Edgev1v2=maxWeight)Edgev1v2=Edgev2v1=cost;

44、numEdges+;return true;else return false;int Graphmtx:getFirstNeighbor (int v) if (v != -1) for (int col = 0; col <numVertices;col+)if (Edgevcol && Edgevcol<maxWeight) return col; return -1;int Graphmtx:getNextNeighbor (int v, int w) if (v != -1 && w != -1) for (int col = w+1; c

45、ol < numVertices; col+) if (Edgevcol && Edgevcol < maxWeight) return col; return -1;#include <iostream>using namespace std;#include "heap.h"class MinSpanTree;ostream &operator<<(ostream &os,MinSpanTree &c);struct MSTEdgeNodeint tail,head;int key;MSTEdg

46、eNode():tail(0),head(0),key(0)bool operator<=(MSTEdgeNode& R)return key<=R.key;bool operator>(MSTEdgeNode &R)return key>R.key;class MinSpanTreepublic:MinSpanTree(int sz=100):maxSize(sz),n(0)edgevalue=new MSTEdgeNodesz;void Insert(MSTEdgeNode& item)edgevaluen=item;n+;MSTEdgeNo

47、de *edgevalue;int maxSize,n;friend ostream &operator<<(ostream &os,MinSpanTree &c);ostream &operator<<(ostream &os,MinSpanTree &c)for (int i=0;i<c.n;i+)if (c.edgevaluei.head<c.edgevaluei.tail)cout<<"("<<c.edgevaluei.head<<",&

48、quot;<<c.edgevaluei.tail<<")"<<" "elsecout<<"("<<c.edgevaluei.tail<<","<<c.edgevaluei.head<<")"<<" "return os;/Prim 算法來求網的最小生成樹void Prim(Graphmtx& G,const int u0,MinSpanTree &MST

49、)MSTEdgeNode ed;int i,v,count;int n=G.NumberOfVertices();int m=G.NumberOfEdges();int u=G.getVertexPos(u0);MinHeap<MSTEdgeNode> H(m);bool *Vmst=new booln;for (i=0;i<n;i+)Vmsti=false;Vmstu=true;count=1;do v=G.getFirstNeighbor(u);while(v!=-1)if (Vmstv=false)ed.tail=u;ed.head=v;ed.key=G.getWeig

50、ht(u,v);H.Insert(ed);v=G.getNextNeighbor(u,v);while (H.IsEmpty()=false&&count<n)H.RemoveMin(ed);if (Vmsted.head=false)MST.Insert(ed);u=ed.head;Vmstu=true;count+;break;while(count<n);/最小堆的實現#include "stdlib.h"template<class E>class MinHeappublic:MinHeap(int sz);MinHeap(E

51、 arr,int n);MinHeap()delete heap;bool Insert(const E& x);bool RemoveMin(E& x);bool IsEmpty()constreturn (currentSize=0)?true:false;private:E *heap;int currentSize;int maxHeapSize;void siftDown(int start,int m);void siftUp(int start);template<class E>MinHeap<E>:MinHeap(int sz)heap

52、=new Esz;if (heap=NULL)cerr<<"堆存儲分配錯誤!"<<endl;exit(1);currentSize=0;template<class E>MinHeap<E>:MinHeap(E arr,int n)if (heap=NULL)cerr<<"堆存儲分配錯誤!"<<endl;exit(1);for (int i=0;i<n;i+)heapi=arri;currentSize=n;int currentPos=(currentSize-2)/2;wh

53、ile (currentPos>=0)siftDown(currentPos,currentSize-1);currentPos-;template<class E>void MinHeap<E>:siftDown(int start,int m)int i=start,j=2*i+1;E temp=heapi;while (j<=m)if (j<m&&heapj>heapj+1) j+;if (temp<=heapj) break;elseheapi=heapj;i=j;j=2*j+1;heapi=temp;template<class E>void MinHeap<E>:siftUp(int start)int j=sta