《数据结构实习报告.doc》由会员分享，可在线阅读，更多相关《数据结构实习报告.doc（30页珍藏版）》请在三一文库上搜索。
1、数据结构课程设计报告学生姓名： 孔令周 指导老师： 陈占龙 班 级： 116102 学生学号： 20101002021 实习题目一1.需求规格说明书 设停车场是一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停 车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆 车停放在车场的最北端），若车场内已停满 n 辆汽车，则后来的汽车只能在门外的便道上等 候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它 之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入 车场，每辆停放在车场的车在它离开停车
2、场时必须按它停留的时间长短交纳费用。试为停车 场编制按上述要求进行管理的模拟程序。2.总体分析与设计 【设计思想】 在内存中实现，无需外存的流处理过程。主要的算法思想是栈和队列的使用。以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟 管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息，汽车牌照号以及到达或 离去的时刻。对每一组输入的数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳 的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。【设计表示】其他
3、输入situationSituation=ESituation=DSituation=AA 添加函数删除函数结束【详细设计表示】 主函数开始时要求用户输入停车场的初始大小，然后对进入的车辆进行管理，如果是进入，调用添加函数，此函数中定义的规则是如果停车场如果没有满就加到停车场栈中，如果停车场已经满了，就添加到走道队列中。处理完添加函数后while循环调用次过程。同理，如果是车辆要出去，就调用删除函数，如果删除后走道上有车在等待车位就将走道上的车辆根据先进先出的规则压到栈中。处理完删除函数之后也while循环调用次过程。只有当用户输入结束的时候此循环才会结束。3.编码 1.输入A表示的是添加，输
4、入D表示删除，输入E表示结束，那么要是用户不小心输入了其他的一个字母怎么办呢？ 在while循环中最开始进行判断的并不是输入的是否为ADE而是输入的是不是不是ADE中间的任何一个，这时候令输入无效，用户需重新输入。此时的输入作废。2.添加的时候如果是栈没有满，这时应该添加到栈中去，储存进入时间和车号，但是如果只是停在走道上需不需要这些数据呢？这里要不要抖没有关系，因为在这里如果要了的话在后面闪出部分走道上的车子重新进入的时候就重新记录一遍车子的进入时间，避免在走道上的时间也要被收费。3.删除的时候将此时的时间减去车子这个数据对象的进入时间就是时间差，根据规定的单价计算停车费用。但是如果走道上有
5、车子的时候他的进入时间呢？处理时一定的，一定要更新，否则车子在走道上的时间也总算在停车场的时间这是不对的。4.如果在停车场中要出去的车是先进来的车子，则表示比他后来的车要先出去那此时的算法呢？答案是也将前面的车先存在一个栈中，等向后面的车子先出去后在出栈重新压栈。4.程序算分分析【运行结果】5.小结【改进设想】用类的思想，本题我还是沿用的过程思想，对各个过程处理好就出了结果，尽管结果没有错，但是和面向对象的思想不是太符合，所以希望可以用个停车场这一个类来处理问题。【体会】有时候在调试的时候的很小的一个结果和预想的不符就是很大的思想问题，比如我调试的时候最后一步有时候钱算的不对，就是添加删除时的
6、时间没有处理正确，所以，错误不在小。要知道为什么会出这个错。编程的时候重要的是提前把思路理好。6.附录class Car public: int carno; /车牌号 int intime; /时间;int n; /停车场容量int no; /车牌号char situa; /状态int tim; /进出站时间int index=1; /车的序列 int preindex=index; /跟踪indexcoutn;coutendl;Stake carpark(n); /停车场栈Stake tempstake(8); /临时车站LinkedQueue passage; /走道队列Car car7
7、; /车对象 6个/*for (int i=1;i=6;i+)cari.carno=i; */while (true)coutsitua;if (situa!=A & situa!=D & situa!=E)cout错误状态！请输入 A ，D 或者 E！endl;coutsitua;if (situa=A)coutno;couttim;if (index=2)cout位置：indexendl; elsecout车道上endl;carno.intime=tim;carno.carno=no;index+;/如果栈满就加到队列中if (carpark.IsFull()passage.Add(no)
8、; /! /如果栈没有满就压栈if (!carpark.IsFull()carpark.Add(no); /出车站if (situa=D)coutno;couttim;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
9、_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
10、=E)break;coutendlendl;cout感谢使用本程序，祝您新年快乐！endl;实习题目二1.需求规格说明书 人们在日常生活中经常需要查找某个人或某个单位的电话号码，本实验将实现一个简单 的个人电话号码查询系统，根据用户输入的信息（例如姓名等）进行快速查询。2.总体分析与设计 【设计思想】本题要求的是做一个通讯录，由于所需要的数据量比较大，所以考虑在外存中进行处理，这里用的是txt文件。当然本来想用数据库的，但是水平不到家。所以放弃了。新建一个数据类型，包括姓名，固定电话，移动电话，电子邮箱。为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但是， 在数组中实
11、现插入和删除操作的代价较高。如果记录需频繁进行插入或删除操作，可以考虑采用二叉搜索树组织电话号码信息，则查找和维护都能获得较高的时间性能。【设计表示】开始退出插入删除添加【详细设计表示】 设置四个选项，0、1、2、3分别代表退出、查询、插入、删除。根据所需要的功能做出操作。初始数据储存在txt文本中。如果选择退出则退出系统，如果选择插入则需填写姓名，电话，手机，邮箱信息。根据名字按照二叉搜索树的形式组织插入，如果选择删除，根据名字的次序在搜索树中删除。如果是查询也根据二叉搜索树的形式删除。3.编码1.名字的判断大小，因为组织二叉搜索树的时候需要对插入和删除做优化，所以需要对名字的大小问题作出比
12、较。解决的时候是通过操作符重载完成的。开始的时候不知道汉字怎么比较大小。后来通过请教了解到汉字可以直接比较大小。大于号的重载就是这个人的名字大于另外一个人的名字。2二叉树的插入，我拷的是以前的代码其实自己重写一遍话的时间还少一些，因为pp和p搞反了。后来问了张唯老师才在讲的时候发现这个问题。3.删除的时候在内存中的二叉搜索树中删除很容易但是文本中的内容并没有变，所以在内存中处理完了之后需要重写文本。开始的时候是先删除所有的文本内容，在重新全部重写。但是后来发信啊这样内存的开销特别大，而且不容易实现，后来是删除之后直接就在文本中输出。发现重新输出的时候文本会重新更新。. 4.程序算分分析【运行结
13、果】5.小结【改进设想】Txt中的信息没有对齐。如果可以的话用数据库或者excel做可能会清晰一些。还有就是如果文本中的信息没有8条的话是会出错的。界面不好。用mfc会好一些【体会】直接烤以前的代码如果有不适合的话会很麻烦，如果代码不很长的话还是抄一遍吧。那样会思路清晰一些。6.附录ifstream in(Tele.txt);/建立流对象 BSTree bstree;int num;int total=8;for (int i=0;iTelei.nameTelei.mobilnumberTelei.phonenumberTelei.email;for (int j=0;jtotal;j+)/做
14、二叉树bstree.Insert(Telej);while(true)cout*endl;cout*如果要退出请按0*endl;cout*如果要查询请按1*endl;cout*如果要插入请按2*endl;cout*如果要删除请按3*endl;cout*num;if (num=0)/退出break;if (num=1)/查找string temp_name;TelNumber menber,find_member;couttemp_name;bstree.Search(temp_name,find_member);/根据名字找couttemp_name的电话为：find_member.phone
15、numberendl;couttemp_name的手机为：find_member.mobilnumberendl;couttemp_name的邮箱为：find_member.emailendl;if (num=2)/插入完成ofstream out(Tele.txt);TelNumber mem2,insertmen,delmen; int num2=0;coutmem2.name;coutmem2.phonenumber;coutmem2.mobilnumber;coutmem2.email;bstree.Insert(mem2);Teletotal=mem2;total+;while (n
16、um2total)/重新写txtif (Telenum2!=mem2)bstree.Delete(Telenum2,delmen);outsetw(5)leftdelmen.namesetw(20)rightdelmen.mobilnumberrightsetw(20)delmen.phonenumbersetw(30)rightdelmen.emailendl;if (Telenum2=mem2)bstree.Delete(Telenum2,delmen);outsetw(5)leftdelmen.namesetw(20)rightdelmen.mobilnumberrightsetw(20
17、)delmen.phonenumbersetw(30)rightdelmen.emailendl;num2+;for (int j=0;jtotal;j+)bstree.Insert(Telej); if (num=3)/删除string temp_name0;char yorn;ofstream out(Tele.txt);TelNumber menber0,delete_member;couttemp_name0;for (int t=0;ttotal;t+)if (Telet.name=temp_name0)menber0=Telet;cout您真的要删除吗？endl;while (yo
18、rn!=y & yorn!=n)coutyorn;if (yorn=y)int tempnum=0;int nmo=0; TelNumber here100;while (tempnumtotal)if (Teletempnum!=menber0)bstree.Delete(Teletempnum,delete_member);herenmo=delete_member;outsetw(5)leftdelete_member.namesetw(20)rightdelete_member.mobilnumberrightsetw(20)delete_member.phonenumbersetw(
19、30)rightdelete_member.emailendl;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 中。 排队原则： 先按职称排，同职
20、称按分房工龄排，同工龄按年龄排。2.总体分析与设计【设计思想】 由于测试数据是在文本中的数据，所以处理起来需要用到输入输出流。将已经给好的a1.txt.中的数据在内存中处理完毕之后就重新输出到另外一个a2.txt中。【设计表示】内存处理读文本aaaaaaa1.txta1.txt输出到文本【详细设计】 建立流对象两个，第一个是输入流，一个是输出流。将给输数据流读到内存中，调用排序函数，这里不能用选择排序，因为选择排序的话要写三个不同的找到最大值函数。根据三个不同的因素来排。所以选择冒泡排序。拍完之后在输出就行了。3.编码1.开始的时候建立流对象忘记了。看以前的数的时候也不知道，因为以前这里也没有
21、学通。现在做到时候是叫同学叫我怎么做流的技巧的。2.排序算法。开始的时候嫌冒泡太麻烦。要写好多。想找个简单的但是后来发现就这个用的方便。其他的都需要重载函数。太麻烦。3.调整间距，在用了一个left或right之后只能管一下，在下一个操作符之后的地方前面的限定就不起作用了。需要重新声明左对齐与右对齐。4.程序算分分析【运行结果】5.小结 【体会】这次实习最大的收获就是学会了初级的输入输出流处理，程序大多数是对输入输出的处理，应付不同的数据组织形式。需要掌握多种技术。 6.附录class Workerpublic:int number; /职称编号int workage; /工龄int age;
22、 /年龄char name20; /姓名;void bubsort(Worker temp,int n)int a,b;Worker tempwork;/根据number排序for(a=1;an;a+)for (b=1;btempb-1.number)tempwork=tempb;tempb=tempb-1;tempb-1=tempwork;/根据工龄排for (a=1;an;a+)for (b=1;btempb-1.workage)tempwork=tempb;tempb=tempb-1;tempb-1=tempwork;/根据年龄排for (a=1;an;a+)for (b=1;btemp
23、b-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中outinformationendl; /在out中输出infoWorker worker505; for (int i=0;iw
24、orkeri.nameworkeri.numberworkeri.workageworkeri.age; bubsort(worker,505);for (int index=0;index505;index+)outleftsetw(7)workerindex.namesetw(8)rightworkerindex.numbersetw(8)workerindex.workagesetw(9)workerindex.ageendl; coutOK!endl; return 0;实习题目四1.需求规格说明书“火烧连营”是三国演义中的著名典故之一广为流传，假定文本文件c1.txt 是火烧连营中的
25、 军营分布图，每个字符 A 代表一个营帐，营帐是可燃物，其他字符代表不可燃的空白地段， 文件共有 40 行 70 列，请你编写程序，读入该文件的内容，再从键盘输入任意点的 x 和 y 值（x70,y40 ）作为着火点，“火烧连营”后，被燃烧的营帐标上字符X，并把整个结果 输出到文件 c2.txt 中。2.总体分析与设计【设计思想】 基本思想：从着火点位置开始，按四连通思想上下左右寻找其邻居点。 开辟一个堆栈，先将着火点压栈，然后重复一下操作：栈顶点出栈并标记X ，同 时将符合被燃烧条件的邻居点入栈。，直到栈空为止。【设计表示】 输入坐标是否有效 有效 无效火烧连营结束【详细设计】 首先将c1中
26、的数据独到内存中，在内存中处理是否火烧连营，然后根据输入的坐标，如果坐标显示的是A的话就将连在一起的A全部变成X。具体做法是做一个栈。将A压倒栈里面去，出栈顶。压入的后边是A 的坐标，在重复以上做法。如果是就不处理。等栈空了之后就结束。3.编码 1.二维数组的赋值。因为数据是从c1里面获取的，需要一个空的二维空间来存储他一遍再内存中可以使用。所以需要开辟一个动态的二维数组，静态的不行就是因为需要初始化。这里声明的时候。二维数组的分两步，第一步是声明以为的指针数组，在声明以为数组。 2.行列出错，说的是40行70列，但是我开始声明的时候总是反了，结果内存总出问题。后来改正了。4.程序算分分析【运
27、行结果】5.小结【体会】这题最大的收获就是二维数组的声明。以前总是声明的以为数组，很熟练，但是到了二维数组的时候就不是一样的声明方法了。所以积累了知识。6.附录void getfire(char *temp_A,LinkedStack 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,x
28、x,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;/声明二维数组f
29、or(int i=0;i40;i+)Ai=new char70; LinkedStack stake;int x,y;coutx;couty;for (int d=0;d40;d+)for(int e=0;eAde;getfire(A,stake,x,y);coutget fire no wrongendl;for (int a=0;a40;a+)for(int b=0;b70;b+)outAab;outendl;coutend !10;i-)for (int j=0;j xj+1.weight)edge=xj;xj=xj+1;xj+1=edge;templateclass DGraph T *a; /存储的二维数组int Number_of_Vertice; /点的数量T Noedge; /没有边界int Number_of_Edge; /边的数量T *Note; /标记public:DGraph (int numofvetc,T noeg); /构造函数DGraph (); /析构函数DGraph& Delete (int i,int j); /删除边int