《[计算机软件及应用]数据结构与算法程序设计.docx》由会员分享，可在线阅读，更多相关《[计算机软件及应用]数据结构与算法程序设计.docx（34页珍藏版）》请在三一办公上搜索。
1、数据结构与算法 课程设计姓名：班号：学号：2012年2月前言（先写点感想吧，但为什么要放在第一页呢？因为这都是我的肺腑之言，纯手打，希望老师能看到 +_+ ）不积跬步，无以至千里；不积小流，无以成江海。是的，没有打下扎实的基础无法进一步发展，没有坚持的努力无法能人所不能。这是我这次课程设计最大的感想。一个月前，我的困惑.“为什么这么难？这是什么错误？为什么不能实现？我不想做了！”这是一个月前这数据结构课程给我的感觉。为什么会有这样的感觉呢？不是因为数据结构这个课程很难，其实就是C+基础不过关，由于这一限制，让我无法在数据结构这门课程有更大的发展。大一下学期C+课程和考试都结束得比较匆忙，自己也
2、没有认真复习，所以C+学得不好，程序根本不能轻松做出来，更别说改进算法和提升性能了。渐渐地，我发觉了差距本次课程设计有一点令我很不满。就是上机实习时间，期间刚好有两场考试，英语四级和物理，面对考试和实习这个二叉路口，选其一意味着多多少少要放弃另一，这种无形的压力让我带着抱怨去上机实习。于是，为了复习考试，我马马虎虎地应对实习，以便有更多精力去复习考试。我仿造了网上的题目做了一两个题目交给老师检查，不是不想完成，是因为确实代码不会写，也因为当时觉得考试更重要。可是，我发现一些做得好的同学，他们能在规定时间内做完，为什么他们想到的东西我也能想到，他们能写出代码我就不能呢？是因为他们C+基础好，写代
3、码没语法错误，懂得怎样调试，也能运用书上的代码。而我就困于各种语法错误，自己的想法不能用代码实现，浪费了不少时间。顿时，我深深地感觉到C+基础这一道屏障，彻底把我围住了冲破困惑，做出改变正所谓“偷得半日闲”，趁着寒假的清静和放松，厌倦了游戏的虚无，没有各种烦扰嘈杂，在静静的书房内，我重拾学习C+的激情。经过一个星期，我把整本C+重新看了一遍，而且我有一种豁然开朗的感觉。渐渐地明白到以前C+的问题都是由于自己没有认真对待，得过且过，以致于日积月累形成一道屏障，连书上一些简单的程序都看不懂，编写的程序也语法错漏百出，影响的自己对C+的心情和耐性。经过一步一步的重新学习，我对C+的基础知识基本掌握，
4、自然而然编程能力得到提升，课本上二叉树，排序等那些代码也看得懂了。课程设计的题目变得不再难，心中也收获了难得的喜悦。Now.由于C+语法的掌握，我现在不再有一些无谓的时间浪费，始于编程，终于程序实现的成就感。回顾了我的学习经历以及一些同学的例子，我发觉有好多同学为什么编程能力这么差，一方面是由于游戏诱惑实在太大了（在一些同学的眼中，游戏中的级数排名的成就感比你编写一个成功的程序大得多）和在人生道路上没有远大的目标（正所谓人各有志，一些同学觉得一个游戏高手比一个编程高手更值得称赞），另一方面是由于学习方法不当，好多基础都没掌握，限制了发展。有一句话，成功的道路注定是孤独的。要想获得成功，少不了寂
5、寞和痛楚。有时梦想看似飘拂，有时现实又那么残酷，那么，在没有直行的丁字路口，你会如何选择呢？坚持自己的信念。End。 转入正题 skipping 目录一、停车场管理系统 .3 1.1 问题描述 .3 1.2 设计思想 .31.3 设计表示 .3 1.4 详细设计 .41.5 程序测试 .101.6 分析小结 .11二、个人电话号码查询系. 11 2.1 问题描述 .11 2.2 设计思想 .112.3 设计表示 .12 2.4 详细设计 .132.5 程序测试 .192.6 分析小结 .21三、排序应用 .22 3.1 问题描述 .22 3.2 设计思想 .223.3 详细设计 .223.4
6、程序测试 .263.5 分析小结 .27四、“火烧连营”问题 .27 4.1 问题描述 .27 4.2 设计思想 .274.2 设计表示 .274.4 详细设计 .274.5 程序测试 .304.6 分析小结 .331、停车场管理【问题描述】设停车场是一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n 辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路
7、，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。【设计思想】基本要求：每一组输入数据包括三个数据项：汽车“到达”或“离去”信息，汽车牌照号以及到达或离去的时刻。对每一组输入的数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。实现思路：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。栈以顺序结构实现，队列以链表结构实现。需另设一个栈，
8、临时停放为给要离去的汽车让路而从停车场推出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。【设计表示】Arrival便道（队列） 栈满Departure停车场（栈） 栈不满 栈不满，对头元素进入 倒车场（另一栈） 若栈顶车 若非栈顶车【详细设计】（1）建立汽车信息类struct car int number;int time;（2）建立栈类模板，模拟停车场和倒车场/栈以顺序结构实现templateclass Stackpublic:Stack(int sz=50);Stack()deleteelemen
9、ts;void Push(const T &x);bool Pop(T &x);bool getTop(T &x);bool IsEmpty()const return (top=-1)?true:false;bool IsFull()const return (top=maxSize-1)?true:false;int getSize()const return top+1;void MakeEmpty() top=-1;private:T *elements;int top;int maxSize;templateStack:Stack(int sz):top(-1),maxSize(sz
10、)elements=new TmaxSize;templatevoid Stack:Push(const T &x)elements+top=x;templatebool Stack:Pop(T &x)if(IsEmpty()=true) return false;x=elementstop-;return true;templatebool Stack:getTop (T &x)if(IsEmpty()=true) return false;x=elementstop;return true;（3）建立队列类模板，模拟便道/队列以链表结构实现templatestruct LinkNode/结
11、点类T data;LinkNode *link;LinkNode(LinkNode *ptr=NULL)link=ptr;LinkNode(const T &item,LinkNode *ptr=NULL)data=item;link=ptr;templateclass LinkedQueuepublic:LinkedQueue():rear(NULL),front(NULL);LinkedQueue()makeEmpty();bool EnQueue(const T &X);bool DeQueue( T &X);bool getFront(T &x)const;void makeEmpty
12、();bool IsEmpty()const return (front=NULL)?true:false;int getSize()const;protected:LinkNode *front,*rear;templatevoid LinkedQueue:makeEmpty()LinkNode *p;while(front!=NULL)p=front;front=front-link;delete p;templatebool LinkedQueue:EnQueue (const T &x)if(front=NULL)front=rear=new LinkNode(x);if(front=
13、NULL) return false;elserear-link=new LinkNode(x);if(rear-link=NULL)return false;rear=rear-link;return true;templatebool LinkedQueue:DeQueue (T &x)if(IsEmpty()=true)return false;LinkNode *p=front;x=front-data;front=front-link;delete p;return true;templatebool LinkedQueue:getFront (T &x)constif(IsEmpt
14、y()=true)return false;x=front-data;return true;templateint LinkedQueue:getSize ()constLinkNode *p=front;int k=0;while(p!=NULL)p=p-link;k+;return k;（4）Arrival函数，处理到达车辆void Arrival(Stack &Park,LinkedQueue &line)int number,time;coutnumber;car arrive;arrive.number =number;if(Park.IsFull()cout停车场已满，请等候en
15、dl;line.EnQueue(arrive);cout车牌为number的汽车转入便道endl;cout=endl; elsecouttime;arrive.time =time;Park.Push(arrive);cout车牌为number的汽车进入停车场endl;cout=endl;（5）Departure函数，处理离开车辆void Departure(Stack &Park,Stack &Back,LinkedQueue &line)int number,time;int flag1=1;int flag2=1;coutnumber;couttime;car temp;while(fl
16、ag1)Park.Pop(temp);if(temp.number =number)flag1=0;elseBack.Push(temp);cout停留时间:time-temp.time分钟 收费:(time-temp.time)*2元（按2元/分钟收费） endl;cout=endl;while(flag2)if(Back.IsEmpty ()=true)flag2=0;elsecar temp;Back.Pop(temp);Park.Push(temp);if(line.IsEmpty()=false)car temp;line.DeQueue(temp);cout车牌为temp.numb
17、er 的汽车从便道进入停车场endl;cout=endl;temp.time=time;Park.Push(temp);（6）主函数，建立停车场、倒车场、便道，调用Arrival函数和Departure函数实现停车场管理int main(int argc, char* argv) int n;char flag;coutn;Stack Park(n);Stack Back(n);LinkedQueue Line;cout* 欢迎进入停车场管理系统 *endl;cout=endl;cout* A - 进入停车场 D - 离开停车场 E - 退出程序 *endl;cout=flag;switch(
18、flag)case A: Arrival(Park,Line);break; /汽车进车场case D: Departure(Park,Back,Line);break; /汽车出车场case E: exit(0);break;default:cout选择有误，重新选择！endl;break; while(flag!=E);return 0;【程序测试】测试数据：设 n=2，输入数据为：(A，1，5)， (A，2，10)， (D，1，15)， (A，3，20)， (A，4，25)，(A，5，30)， (D，2，35)， (D，4，40)，(E，0，0)。其中：A表示到达（Arrival）； D
19、表示离去（Departure）；E表示输入结束（END）。【分析小结】总体上能达到题目要求。此程序的算法需要熟练掌握栈和队列，压栈和出栈，入队列和出队列是重点，选对存储结构也很重要，有利于提升性能和简化程序，而其余的较为简单。程序或许不完善，异常处理没仔细做（例如：同车牌号车进了没离开又再进入），不过这改善也比较容易。只要按照正常操作不会有问题。2、个人电话号码查询系统【问题描述】人们在日常生活中经常需要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号码查询系统，根据用户输入的信息（例如姓名等）进行快速查询。【设计思想】基本要求：（1） 在外存上，用文件保存电话号码信息；（2）
20、 在内存中，设计数据结构存储电话号码信息；（3） 提供查询功能：根据姓名实现快速查询；（4） 提供其他维护功能：例如插入、删除、修改等。实现方式：由于需要管理的电话号码信息较多，而且要在程序运行结束后仍然保存电话号码信息，所以电话号码信息采用文件的形式存放到外存中。在系统运行时，需要将电话号码信息从文件调入内存来进行查找等操作，为了接收文件中的内容，要有一个数据结构与之对应，可以设计如下结构类型的数组来接收数据：const int max=10;struct TeleNumberstring name; /姓名string phoneNumber; /固定电话号码string mobileNu
21、mber; /移动电话号码string email; /电子邮箱 Telemax;为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但是，在数组中实现插入和删除操作的代价较高。如果记录需频繁进行插入或删除操作，可以考虑采用二叉搜索树组织电话号码信息，则查找和维护都能获得较高的时间性能。更复杂地，需要考虑该二叉搜索树是否平衡，如何使之达到平衡。【设计表示】外存（文件） 结构体数组内存（操作）修改删除添加查询 提取 存储 保存操作【详细设计】（1）建立电话信息类结构体，用于存储从文件提取的电话信息数据struct telstring name; /姓名string phone
22、Number; /固定电话号码string mobileNumber; /移动电话号码string email; /电子邮箱bool operator ( tel& x) /重载：判小于 return (name ( tel &x) /重载：判大于 return name x.name; bool operator = ( tel & x) /重载：判等于 return (name = x.name)?true:false; ;（2）采用了二叉搜索树组织电话号码信息，建立二叉树类/树结点类struct BSTNodetel data;BSTNode *left,*right;BSTNode()
23、:left(NULL),right(NULL)BSTNode(const tel d,BSTNode *L=NULL,BSTNode *R=NULL):data(d),left(NULL),right(NULL);/二叉搜索树类class BSTpublic:BST():root(NULL);BSTNode * Search( tel x)return Search(x,root);bool Insert(tel& e1)return Insert(e1,root);bool Remove(tel x)return Remove(x,root);void PrintTree()PrintTre
24、e(root);void PrintTree(ofstream &out)PrintTree(root,out);private:BSTNode *root;BSTNode *Search( tel x,BSTNode * ptr);bool Insert( tel& e1,BSTNode *& ptr);bool Remove(tel x,BSTNode *& ptr);void PrintTree(BSTNode *ptrt);void PrintTree(BSTNode *ptr,ofstream &out);/各类成员函数实现BSTNode *BST:Search( tel x,BST
25、Node * ptr)if(ptr=NULL) return NULL;else if(xdata ) return Search(x,ptr-left ); else if(xptr-data ) return Search(x,ptr-right ); else return ptr;bool BST:Insert( tel& e1,BSTNode *& ptr)if(ptr=NULL)ptr=new BSTNode(e1);if(ptr=NULL)coutOut of spaceendl;exit(1);return true;else if(e1data ) Insert(e1,ptr
26、-left ); else if(e1ptr-data ) Insert(e1,ptr-right ); else return false;bool BST:Remove(tel x,BSTNode *& ptr)BSTNode *temp;if(ptr!=NULL)if(xdata ) Remove(x,ptr-left );else if(xptr-data ) Remove(x,ptr-right );else if(ptr-left !=NULL&ptr-right !=NULL) temp=ptr-right ; while(temp-left !=NULL) temp=temp-
27、left; ptr-data =temp-data ; Remove(ptr-data ,ptr-right );else temp=ptr; if(ptr-left =NULL) ptr=ptr-right ; else ptr=ptr-left ; delete temp;return true; else return false;void BST:PrintTree(BSTNode *ptr,ofstream &out)if(ptr!=NULL) outsetw(10)data.name setw(15)data.phoneNumber setw(15)data.mobileNumbersetw(20)data.emailleft,out );PrintTree(ptr-right,out );void BST:PrintTree(BSTNode *ptr)if(ptr!=NULL)coutsetw(10)data.name
