数据结构实习报告.doc

数据结构课程设计报告学生姓名： 孔令周 指导老师： 陈占龙 班 级： 116102 学生学号： 20101002021 实习题目一1.需求规格说明书 设停车场是一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停 车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆 车停放在车场的最北端），若车场内已停满 n 辆汽车，则后来的汽车只能在门外的便道上等 候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它 之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入 车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车 场编制按上述要求进行管理的模拟程序。2.总体分析与设计 【设计思想】 在内存中实现，无需外存的流处理过程。主要的算法思想是栈和队列的使用。以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟 管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息，汽车牌照号以及到达或 离去的时刻。对每一组输入的数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳 的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。【设计表示】其他输入situationSituation=ESituation=DSituation=AA 添加函数删除函数结束【详细设计表示】 主函数开始时要求用户输入停车场的初始大小，然后对进入的车辆进行管理，如果是进入，调用添加函数，此函数中定义的规则是如果停车场如果没有满就加到停车场栈中，如果停车场已经满了，就添加到走道队列中。处理完添加函数后while循环调用次过程。同理，如果是车辆要出去，就调用删除函数，如果删除后走道上有车在等待车位就将走道上的车辆根据先进先出的规则压到栈中。处理完删除函数之后也while循环调用次过程。只有当用户输入结束的时候此循环才会结束。3.编码 1.输入A表示的是添加，输入D表示删除，输入E表示结束，那么要是用户不小心输入了其他的一个字母怎么办呢？ 在while循环中最开始进行判断的并不是输入的是否为ADE而是输入的是不是不是ADE中间的任何一个，这时候令输入无效，用户需重新输入。此时的输入作废。2.添加的时候如果是栈没有满，这时应该添加到栈中去，储存进入时间和车号，但是如果只是停在走道上需不需要这些数据呢？这里要不要抖没有关系，因为在这里如果要了的话在后面闪出部分走道上的车子重新进入的时候就重新记录一遍车子的进入时间，避免在走道上的时间也要被收费。3.删除的时候将此时的时间减去车子这个数据对象的进入时间就是时间差，根据规定的单价计算停车费用。但是如果走道上有车子的时候他的进入时间呢？处理时一定的，一定要更新，否则车子在走道上的时间也总算在停车场的时间这是不对的。4.如果在停车场中要出去的车是先进来的车子，则表示比他后来的车要先出去那此时的算法呢？答案是也将前面的车先存在一个栈中，等向后面的车子先出去后在出栈重新压栈。4.程序算分分析【运行结果】5.小结【改进设想】用类的思想，本题我还是沿用的过程思想，对各个过程处理好就出了结果，尽管结果没有错，但是和面向对象的思想不是太符合，所以希望可以用个停车场这一个类来处理问题。【体会】有时候在调试的时候的很小的一个结果和预想的不符就是很大的思想问题，比如我调试的时候最后一步有时候钱算的不对，就是添加删除时的时间没有处理正确，所以，错误不在小。要知道为什么会出这个错。编程的时候重要的是提前把思路理好。6.附录class Car public: int carno; /车牌号 int intime; /时间;int n; /停车场容量int no; /车牌号char situa; /状态int tim; /进出站时间int index=1; /车的序列 int preindex=index; /跟踪indexcout<<"输入停车场容量："cin>>n;cout<<endl;Stake<int> carpark(n); /停车场栈Stake<int> tempstake(8); /临时车站LinkedQueue<int> passage; /走道队列Car car7; /车对象 6个/*for (int i=1;i<=6;i+)cari.carno=i; */while (true)cout<<"进站还是出站："cin>>situa;if (situa!=A && situa!=D && situa!=E)cout<<"错误状态！请输入 A ，D 或者 E！"<<endl;cout<<"进站还是出站："cin>>situa;if (situa=A)cout<<"车牌号："cin>>no;cout<<"进/出 站时间："cin>>tim;if (index<=2)cout<<"位置："<<index<<endl; elsecout<<"车道上"<<endl;carno.intime=tim;carno.carno=no;index+;/如果栈满就加到队列中if (carpark.IsFull()passage.Add(no); /! /如果栈没有满就压栈if (!carpark.IsFull()carpark.Add(no); /出车站if (situa=D)cout<<"车牌号："cin>>no;cout<<"进/出 站时间："cin>>tim;cout<<"停留时间："<<tim-(carno.intime)<<endl;cout<<"应缴费用："<<(tim-(carno.intime)*2<<" 元"<<endl;index-;preindex-;/把no以前的car都放到tempstake里面，再删除no，在放回int cp_delete;int tcp_delete;int pas_delete;int waste; while(carpark.Top()!=no)carpark.Delete(cp_delete);tempstake.Add(cp_delete);carpark.Delete(waste);while (!tempstake.IsEmpty()tempstake.Delete(tcp_delete);carpark.Add(tcp_delete);/如果走道有车就加到栈顶if (!passage.IsEmpty() && !carpark.IsFull()passage.Delete(pas_delete); /!1carpark.Add(pas_delete);cp_delete=0;tcp_delete=0;pas_delete=0;waste=0;if (situa=E)break;cout<<endl<<endl;cout<<"感谢使用本程序，祝您新年快乐！"<<endl;实习题目二1.需求规格说明书 人们在日常生活中经常需要查找某个人或某个单位的电话号码，本实验将实现一个简单 的个人电话号码查询系统，根据用户输入的信息（例如姓名等）进行快速查询。2.总体分析与设计 【设计思想】本题要求的是做一个通讯录，由于所需要的数据量比较大，所以考虑在外存中进行处理，这里用的是txt文件。当然本来想用数据库的，但是水平不到家。所以放弃了。新建一个数据类型，包括姓名，固定电话，移动电话，电子邮箱。为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但是， 在数组中实现插入和删除操作的代价较高。如果记录需频繁进行插入或删除操作，可以考虑采用二叉搜索树组织电话号码信息，则查找和维护都能获得较高的时间性能。【设计表示】开始退出插入删除添加【详细设计表示】 设置四个选项，0、1、2、3分别代表退出、查询、插入、删除。根据所需要的功能做出操作。初始数据储存在txt文本中。如果选择退出则退出系统，如果选择插入则需填写姓名，电话，手机，邮箱信息。根据名字按照二叉搜索树的形式组织插入，如果选择删除，根据名字的次序在搜索树中删除。如果是查询也根据二叉搜索树的形式删除。3.编码1.名字的判断大小，因为组织二叉搜索树的时候需要对插入和删除做优化，所以需要对名字的大小问题作出比较。解决的时候是通过操作符重载完成的。开始的时候不知道汉字怎么比较大小。后来通过请教了解到汉字可以直接比较大小。大于号的重载就是这个人的名字大于另外一个人的名字。2二叉树的插入，我拷的是以前的代码其实自己重写一遍话的时间还少一些，因为pp和p搞反了。后来问了张唯老师才在讲的时候发现这个问题。3.删除的时候在内存中的二叉搜索树中删除很容易但是文本中的内容并没有变，所以在内存中处理完了之后需要重写文本。开始的时候是先删除所有的文本内容，在重新全部重写。但是后来发信啊这样内存的开销特别大，而且不容易实现，后来是删除之后直接就在文本中输出。发现重新输出的时候文本会重新更新。. 4.程序算分分析【运行结果】5.小结【改进设想】Txt中的信息没有对齐。如果可以的话用数据库或者excel做可能会清晰一些。还有就是如果文本中的信息没有8条的话是会出错的。界面不好。用mfc会好一些【体会】直接烤以前的代码如果有不适合的话会很麻烦，如果代码不很长的话还是抄一遍吧。那样会思路清晰一些。6.附录ifstream in("Tele.txt");/建立流对象 BSTree bstree;int num;int total=8;for (int i=0;i<total;i+)/把txt里面的信息带出来in>>Telei.name>>Telei.mobilnumber>>Telei.phonenumber>>Telei.email;for (int j=0;j<total;j+)/做二叉树bstree.Insert(Telej);while(true)cout<<"*"<<endl;cout<<"*如果要退出请按0*"<<endl;cout<<"*如果要查询请按1*"<<endl;cout<<"*如果要插入请按2*"<<endl;cout<<"*如果要删除请按3*"<<endl;cout<<"*"<<endl;cin>>num;if (num=0)/退出break;if (num=1)/查找string temp_name;TelNumber menber,find_member;cout<<"您要查找的名字："cin>>temp_name;bstree.Search(temp_name,find_member);/根据名字找cout<<temp_name<<"的电话为："<<find_member.phonenumber<<endl;cout<<temp_name<<"的手机为："<<find_member.mobilnumber<<endl;cout<<temp_name<<"的邮箱为："<<find_member.email<<endl;if (num=2)/插入完成ofstream out("Tele.txt");TelNumber mem2,insertmen,delmen; int num2=0;cout<<"您插入的人的姓名："cin>>mem2.name;cout<<"您插入的人的电话："cin>>mem2.phonenumber;cout<<"您插入的人的手机："cin>>mem2.mobilnumber;cout<<"您插入的人的邮箱："cin>>mem2.email;bstree.Insert(mem2);Teletotal=mem2;total+;while (num2<total)/重新写txtif (Telenum2!=mem2)bstree.Delete(Telenum2,delmen);out<<setw(5)<<left<<delmen.name<<setw(20)<<right<<delmen.mobilnumber<<right<<setw(20)<<delmen.phonenumber<<setw(30)<<right<<delmen.email<<endl;if (Telenum2=mem2)bstree.Delete(Telenum2,delmen);out<<setw(5)<<left<<delmen.name<<setw(20)<<right<<delmen.mobilnumber<<right<<setw(20)<<delmen.phonenumber<<setw(30)<<right<<delmen.email<<endl;num2+;for (int j=0;j<total;j+)bstree.Insert(Telej); if (num=3)/删除string temp_name0;char yorn;ofstream out("Tele.txt");TelNumber menber0,delete_member;cout<<"您要删除的名字："cin>>temp_name0;for (int t=0;t<total;t+)if (Telet.name=temp_name0)menber0=Telet;cout<<"您真的要删除吗？"<<endl;while (yorn!=y && yorn!=n)cout<<"输入y或者n表示yes或者no: "cin>>yorn;if (yorn=y)int tempnum=0;int nmo=0; TelNumber here100;while (tempnum<total)if (Teletempnum!=menber0)bstree.Delete(Teletempnum,delete_member);herenmo=delete_member;out<<setw(5)<<left<<delete_member.name<<setw(20)<<right<<delete_member.mobilnumber<<right<<setw(20)<<delete_member.phonenumber<<setw(30)<<right<<delete_member.email<<endl;nmo+;if (Teletempnum=menber0)bstree.Delete(Teletempnum,delete_member);tempnum+;/重新插入for (int e=0;e<=nmo;e+)bstree.Insert(heree);total-;cout<<"已删除成功！"<<endl;实习题目三1.需求规格说明书假定文本文件 A1.txt 中是我校所有参加南望山庄二期挑房职工的信息，请编写程序，读 出文件中的内容，再按挑房的先后次序排队后将排序号和姓名以文本方式存放到文件A2.txt 中。 排队原则： 先按职称排，同职称按分房工龄排，同工龄按年龄排。2.总体分析与设计【设计思想】 由于测试数据是在文本中的数据，所以处理起来需要用到输入输出流。将已经给好的a1.txt.中的数据在内存中处理完毕之后就重新输出到另外一个a2.txt中。【设计表示】内存处理读文本aaaaaaa1.txta1.txt输出到文本【详细设计】 建立流对象两个，第一个是输入流，一个是输出流。将给输数据流读到内存中，调用排序函数，这里不能用选择排序，因为选择排序的话要写三个不同的找到最大值函数。根据三个不同的因素来排。所以选择冒泡排序。拍完之后在输出就行了。3.编码1.开始的时候建立流对象忘记了。看以前的数的时候也不知道，因为以前这里也没有学通。现在做到时候是叫同学叫我怎么做流的技巧的。2.排序算法。开始的时候嫌冒泡太麻烦。要写好多。想找个简单的但是后来发现就这个用的方便。其他的都需要重载函数。太麻烦。3.调整间距，在用了一个left或right之后只能管一下，在下一个<<操作符之后的地方前面的限定就不起作用了。需要重新声明左对齐与右对齐。4.程序算分分析【运行结果】5.小结 【体会】这次实习最大的收获就是学会了初级的输入输出流处理，程序大多数是对输入输出的处理，应付不同的数据组织形式。需要掌握多种技术。 6.附录class Workerpublic:int number; /职称编号int workage; /工龄int age; /年龄char name20; /姓名;void bubsort(Worker temp,int n)int a,b;Worker tempwork;/根据number排序for(a=1;a<n;a+)for (b=1;b<n-a+1;b+)if (tempb.number>tempb-1.number)tempwork=tempb;tempb=tempb-1;tempb-1=tempwork;/根据工龄排for (a=1;a<n;a+)for (b=1;b<n-a+1;b+)if (tempb.number=tempb-1.number) && (tempb.workage>tempb-1.workage)tempwork=tempb;tempb=tempb-1;tempb-1=tempwork;/根据年龄排for (a=1;a<n;a+)for (b=1;b<n-a+1;b+)if (tempb.number=tempb-1.number && tempb.workage=tempb-1.workage && tempb.age>tempb-1.age)tempwork=tempb;tempb=tempb-1;tempb-1=tempwork;int main(int argc, char* argv)ifstream in("123.txt"); /定义输入流，源txt ofstream out("ok.txt"); /定义输出流，目标txtint width=40;char information40;in.getline(information,width); /把宽度为width的字符放在info中out<<information<<endl; /在out中输出infoWorker worker505; for (int i=0;i<505;i+) in>>workeri.name>>workeri.number>>workeri.workage>>workeri.age; bubsort(worker,505);for (int index=0;index<505;index+)out<<left<<setw(7)<<workerindex.name<<setw(8)<<right<<workerindex.number<<setw(8)<<workerindex.workage<<setw(9)<<workerindex.age<<endl; cout<<"OK!"<<endl; return 0;实习题目四1.需求规格说明书“火烧连营”是三国演义中的著名典故之一广为流传，假定文本文件c1.txt 是火烧连营中的 军营分布图，每个字符 A 代表一个营帐，营帐是可燃物，其他字符代表不可燃的空白地段， 文件共有 40 行 70 列，请你编写程序，读入该文件的内容，再从键盘输入任意点的 x 和 y 值（x<70,y<40 ）作为着火点，“火烧连营”后，被燃烧的营帐标上字符X，并把整个结果 输出到文件 c2.txt 中。2.总体分析与设计【设计思想】 基本思想：从着火点位置开始，按四连通思想上下左右寻找其邻居点。 开辟一个堆栈，先将着火点压栈，然后重复一下操作：栈顶点出栈并标记X ，同 时将符合被燃烧条件的邻居点入栈。，直到栈空为止。【设计表示】 输入坐标是否有效 有效 无效火烧连营结束【详细设计】 首先将c1中的数据独到内存中，在内存中处理是否火烧连营，然后根据输入的坐标，如果坐标显示的是A的话就将连在一起的A全部变成X。具体做法是做一个栈。将A压倒栈里面去，出栈顶。压入的后边是A 的坐标，在重复以上做法。如果是就不处理。等栈空了之后就结束。3.编码 1.二维数组的赋值。因为数据是从c1里面获取的，需要一个空的二维空间来存储他一遍再内存中可以使用。所以需要开辟一个动态的二维数组，静态的不行就是因为需要初始化。这里声明的时候。二维数组的分两步，第一步是声明以为的指针数组，在声明以为数组。 2.行列出错，说的是40行70列，但是我开始声明的时候总是反了，结果内存总出问题。后来改正了。4.程序算分分析【运行结果】5.小结【体会】这题最大的收获就是二维数组的声明。以前总是声明的以为数组，很熟练，但是到了二维数组的时候就不是一样的声明方法了。所以积累了知识。6.附录void getfire(char *temp_A,LinkedStack<char> temp_stake,int temp_x,int temp_y)char temp=X;int xx; /得到的xint yy; /得到的yif (temp_Atemp_xtemp_y=A)temp_stake.Add(temp,temp_x,temp_y);while(!temp_stake.IsEmpty()temp_stake.Delete(temp,xx,yy);temp_Axxyy=temp;if (temp_Axxyy-1=A)/左temp_stake.Add(temp,xx,yy-1); if (temp_Axxyy+1=A)/右temp_stake.Add(temp,xx,yy+1);if (temp_Axx-1yy=A)/上temp_stake.Add(temp,xx-1,yy);if (temp_Axx+1yy=A)/下temp_stake.Add(temp,xx+1,yy);ifstream in("c1.txt");ofstream out("c2.txt"); /建立流对象 char *A=new char*40;/声明二维数组for(int i=0;i<40;i+)Ai=new char70; LinkedStack<char> stake;int x,y;cout<<"请输入着火地点横坐标：" cin>>x;cout<<"请输入着火地点纵坐标："cin>>y;for (int d=0;d<40;d+)for(int e=0;e<70;e+)in>>Ade;getfire(A,stake,x,y);cout<<"get fire no wrong"<<endl;for (int a=0;a<40;a+)for(int b=0;b<70;b+)out<<Aab;out<<endl;cout<<"end !1"<<endl;实习题目五1.需求规格说明书 需要在某个城市的 n 个居民区之间铺设煤气管道，则在这 n 个居民区之间只要铺设 n-1 条管道即可。假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费 不同。选择最有的施工方案能使总投资尽可能少，这个问题即为求网的“最小生成树”。2.总体分析与设计【设计思想】用Kruskal算法，找到所有的最短边，构成通路。从最开始输入的时候的起点找到起点的最短通路，再将通道一一输出。【设计表示】储存在边权数组中输入边和权深度优先搜索排序比安全数组输出结果【详细设计】 从main函数入口。得到丁点个数，建立这么多个顶点的有向图，再调用输入函数得到各个点和边的权值。得到之后将权值储存在边的数组中，排序。然后经过深度优先，得到串联的有向图解，根据需求输出方案并且得到耗费。3.编码 1.最难的是深度优先搜索函数，上次实习的时候是将深度优先和宽度优先在一个函数中实现的，但是这次是讲深度优先拆成几个函数的符合而成。需要深刻知道reach数组和result数组的作用。 2.判断环路是一个难点。这里的判断方法是终点的reach不等于一。开始的时候始终不知道怎么做。上网查询了不少。但是有意义的没多少。后来半猜半试的做的。如果存在一个终点同时他又是这条线路中的另一个终点说明有环路了，这一点是需要判断的。 3.路径查找算法。因为有n个点，所以最短路径必然只有n-1个边所以路径查找算法表示根据点的个数定量的找到边的个数。所以需要对边排序。事先知道最短的那几条边可不可以满足。4.程序算分分析【测试数据】 413 7 8 6 42 10 4 5 5 5.小结这题和数据结构实习的最后一题类似，需要用到深度优先搜索和图的知识。带有智能的味道。做起来比较麻烦。任何一个小地方出现问题都会带来意想不到的错误，调试时很关键的一步，不仅要知道函数是什么意思，来呢每一个变量都要知道是什么意思。很复杂。6.附录void Bubsort(Edge x,int& n)Edge edge;for (int i=n-1;i>0;i-)for (int j=0;j<i;j+)if (xj.weight > xj+1.weight)edge=xj;xj=xj+1;xj+1=edge;template<class T>class DGraph T *a; /存储的二维数组int Number_of_Vertice; /点的数量T Noedge; /没有边界int Number_of_Edge; /边的数量T *Note; /标记public:DGraph<T> (int numofvetc,T noeg); /构造函数DGraph<T> (); /析构函数DGraph<T>& Delete (int i,int j); /删除边int