数据结构课程设计报告.docx

1、数据结构课程设计报告2013年1月 控制台1.停车场管理32.个人电话号码查询系统63.排序运用124.“火烧连营”问题165.管道铺设施工的最佳方案选择19MFC1.停车场管理272.个人电话号码查询系统293.排序运用34总结自我总结38实习题目一 停车场管理【问题描述】设停车场是一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n 辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之

2、后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。【设计思想】以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息，汽车牌照号以及到达或离去的时刻。对每一组输入的数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。

3、需另设一个栈，临时停放为给要离去的汽车让路而从停车场推出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。【设计表示】【代码实现】/主函数的实现#include stdafx.h#include iostream.h#include queue.h#include stack.hint main(int argc, char* argv) coutn; char a; cout请输入停车场车辆的情况:anumtime; SeqStack s1; SeqStack s2; LinkedQueue q; s1

4、.Push(a,num,time); cout车牌为 num 在停车场的位置为:s1.getSize()anumtime; int time1=time; if (a=A) if (s1.Find(num)=true) cout车牌为num车停在s1.getnum(num)+1位置 请重新输入!endl; continue; else if (s1.getSize()n) s1.Push(a,num,time); cout车牌为 num 在停车场的位置为:s1.getSize()endl; else q.EnQueue(a,num,time); cout车牌为 num 在便道上的位置为:q.g

5、etSize()endl; if (a=D) if (s1.Find(num)=true) /先找到此车 int b=s1.gettime(num); cout车牌为 num 在停车场停留的时间是:time-bendl; for (int i=s1.getnum(num)+1;is1.getSize();i+) s1.Pop(a,num,time); /将车辆放在零时栈 s2.Push(a,num,time); s1.Pop(a,num,time); /退出此车 for (i=0;i0) /如果便道中有车，则将便道的车进入停车场 q.DeQueue(a,num,time); s1.Push(a

6、,num,time1); else cout车牌为 num 车在便道上，不在停车场！endl; return 0;【运行结果】实习题目二 个人电话号码查询系统【问题描述】人们在日常生活中经常需要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号码查询系统，根据用户输入的信息（例如姓名等）进行快速查询。基本要求：（1） 在外存上，用文件保存电话号码信息；（2） 在内存中，设计数据结构存储电话号码信息；（3） 提供查询功能：根据姓名实现快速查询；（4） 提供其他维护功能：例如插入、删除、修改等。【设计思想】由于需要管理的电话号码信息较多，而且要在程序运行结束后仍然保存电话号码信息，所

7、以电话号码信息采用文件的形式存放到外存中。在系统运行时，需要将电话号码信息从文件调入内存来进行查找等操作，为了接收文件中的内容，要有一个数据结构与之对应，可以设计如下结构类型的数组来接收数据：const int max=10;struct TeleNumberstring name; /姓名string phoneNumber; /固定电话号码string mobileNumber; /移动电话号码string email; /电子邮箱 Telemax;为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但是，在数组中实现插入和删除操作的代价较高。如果记录需频繁进行插入或删

8、除操作，可以考虑采用二叉搜索树组织电话号码信息，则查找和维护都能获得较高的时间性能。更复杂地，需要考虑该二叉搜索树是否平衡，如何使之达到平衡。【设计表示】【代码实现】/结构体的实现#include #include stdlib.h#include using namespace std;struct TeleNumber;istream &operator(istream &is,TeleNumber &c); /使编译器识别重载的运算符ostream &operator(istream &is,TeleNumber &c); /重载 friend ostream &operator(ost

9、ream &os,TeleNumber &c); /重载(istream &is,TeleNumber &c) isc.namec.phoneNumberc.mobileNumberc.email; /输入结构体 return is; ostream &operator(ostream &os,TeleNumber &c) /输出结构体 osc.namesetw(10)setw(15)c.phoneNumbersetw(20)c.mobileNumbersetw(20)c.email; return os; /二叉搜索树的实现#include stdlib.hstruct BSTNode /T

10、eleNumber(E) TeleNumber data; BSTNode *left,*right; BSTNode():left(NULL),right(NULL) BSTNode(const TeleNumber 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 BST public: BST():root(NULL) BST() bool Insert(

11、const TeleNumber& e1) return Insert(e1,root); bool Remove(const string x) return Remove(x,root); bool Modify(const string 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 Remov

12、e(const string x,BSTNode *&ptr); ;/插入到二叉搜索树bool BST:Insert(const TeleNumber& e1,BSTNode *&ptr) int i=0; if (ptr=NULL) ptr=new BSTNode(e1); if (ptr=NULL) cerrOut of spaceendl;exit(1); return true; else if (int(e1.name.substr(i,i+1)0)data.name.substr(i,i+1)0) Insert(e1,ptr-left); else if (int(e1.name.

13、substr(i,i+1)0)int(ptr-data.name.substr(i,i+1)0) Insert(e1,ptr-right); else return false;/删除二叉搜索树中的某结点bool BST:Remove(const string x,BSTNode *&ptr) BSTNode *temp; if (ptr!=NULL) if (int(x.substr(0,1)0)data.name.substr(0,1)0) Remove(x,ptr-left); else if (int(x.substr(0,1)0)int(ptr-data.name.substr(0,

14、1)0) Remove(x,ptr-right); else if (ptr-left!=NULL&ptr-right!=NULL) temp=ptr-right; while (temp-left!=NULL) temp=temp-left; ptr-data=temp-data; Remove(ptr-data.name,ptr-right); else temp=ptr; if (ptr-left=NULL) ptr=ptr-right; else ptr=ptr-left; delete temp; return true; return false;/在二叉搜索树的某个值BSTNod

15、e *BST:Search(const string x,BSTNode *ptr) if (ptr=NULL) return NULL; else if (int(x.substr(0,1)0)data.name.substr(0,1)0) return Search(x,ptr-left); else if (int(x.substr(0,1)0)int(ptr-data.name.substr(0,1)0) return Search(x,ptr-right); else return ptr; ;bool BST:Modify(const string x,BSTNode *&ptr)

16、 ptr=Search(x,root); cinptr-data; return true;/主函数的实现#include #include #include #include using namespace std;#include tele.h#include BST.Hint main(int argc, char* argv) int a; string str; BST bst; BSTNode *b; cout*欢迎使用个人电话号码查询系统*endl; cout*| 1.查找联系人 |*endl; cout*| 2.添加联系人 |*endl; cout*| 3.删除联系人 |*en

17、dl; cout*| 4.修改联系人 |*endl; cout*| 5.退出本系统 |*Telei; bst.Insert(Telei); i+; fin.close(); while (a!=5) couta; switch(a) case 1: coutstr; if(bst.Search(str,bst.getroot()=NULL) cout没有此联系人!endl; else coutdataendl; break; case 2: coutTelei; bst.Insert(Telei); break; case 3: coutstr; bst.Remove(str); break;

18、 case 4: coutstr; bst.Modify(str,b); break; case 5: cout谢谢使用个人电话号码查询系统!endl; break; return 0;【运行结果】实习题目三 排序应用【问题描述】假定文本文件 A1.txt 中是我校所有参加南望山庄二期挑房职工的信息，请编写程序，读出文件中的内容，再按挑房的先后次序排队后将排序号和姓名以文本方式存放到文件A2.txt中。排队原则： 先按职称排，同职称按分房工龄排，同工龄按年龄排。职称编号： 校级干部 0教授、正处级 1副教授、副处级 2讲师、科级 3其他 4【设计思想】 先将文本文档的内容读到数组中，重载输入输

19、出号，使得文本文档中的每一行为一个元素，然后按照要用冒泡排序法。排序后，并将有序的结果输入到文本文档中【设计表示】【代码实现】#include #include using namespace std;struct staff;istream &operator(istream &is,staff &c);ostream &operator(istream &is,staff &c); /重载 friend ostream &operator(istream &is,staff &c) isc.namec.titleIDc.workingagec.age; return is; ostream

20、 &operator(ostream &os,staff &c) ossetiosflags(ios_base:left)setw(12)c.namesetiosflags(ios_base:left)setw(10)c.titleIDsetiosflags(ios_base:left)setw(10)c.workingagesetiosflags(ios_base:left)setw(10)c.ageendl; return os; /冒泡排序法进行排序void BubbleSort(staff v,int n) for (int i=2;i=i;j-) if (atof(vj-1.titl

21、eID.c_str()atoi(vj.titleID.c_str() staff temp=vj-1;vj-1=vj;vj=temp; 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 stdafx.h#include staff.h#include sort.h#include #include #include using namespace std;int main(int argc, char* argv) int i=0; ifstream fin(a1.txt); /将a1.txt的内容读到结构体数组中 while(!fin.eof() finstai; i+; fin.close(); BubbleSort(sta,i)