数据结构实习报告

孔令周陈占龙孔令周陈占龙116102021数据结构课程设计报告学生姓名：指导老师：班级:学生学号：实习题目一.需求规格说明书设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序， 依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入； 当停车场内某辆车要离开时， 在它之后进入的车辆必须先退出车场为它让路， 待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。 试为停车场编制按上述要求进行管理的模拟程序。.总体分析与设计【设计思想】在内存中实现，无需外存的流处理过程。主要的算法思想是栈和队列的使用。以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟 管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息，汽车牌照号以及到达或 离去的时刻。对每一组输入的数据进行操作后的输出信息为： 若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳 的费用（在便道上停留的时间不收费） 。栈以顺序结构实现，队列以链表结构实现。【设计表示】【详细设计表示】主函数开始时要求用户输入停车场的初始大小，然后对进入的车辆进行管理，如果是进入，调用添加函数，此函数中定义的规则是如果停车场如果没有满就加到停车场栈中,果停车场已经满了，就添加到走道队列中。处理完添加函数后while循环调用次过程。同理,如果是车辆要出去，就调用删除函数，如果删除后走道上有车在等待车位就将走道上的车辆根据先进先出的规则压到栈中。处理完删除函数之后也 while循环调用次过程。只有当用户输入结束的时候此循环才会结束。.编码.输入A表示的是添加，输入D表示删除，输入E表示结束，那么要是用户不小心输入了其他的一个字母怎么办呢 在while循环中最开始进行判断的并不是输入的是否为 ADE而是输入的是不是不是ADE中间的任何一个，这时候令输入无效，用户需重新输入。此时的输入作废。.添加的时候如果是栈没有满，这时应该添加到栈中去，储存进入时间和车号，但是如果只是停在走道上需不需要这些数据呢这里要不要抖没有关系， 因为在这里如果要了的话在后面闪出部分走道上的车子重新进入的时候就重新记录一遍车子的进入时间， 避免在走道上的时间也要被收费。.删除的时候将此时的时间减去车子这个数据对象的进入时间就是时间差， 根据规定的单价计算停车费用。但是如果走道上有车子的时候他的进入时间呢处理时一定的， 一定要更新，否则车子在走道上的时间也总算在停车场的时间这是不对的。.如果在停车场中要出去的车是先进来的车子， 则表示比他后来的车要先出去那此时的算法呢答案是也将前面的车先存在一个栈中，等向后面的车子先出去后在出栈重新压栈。4.程序算分分析【运行结果】输入停车场容量；幺进站还是出站1王牌号工，步出站时间:位置：1进站还是出站।A车牌号52进/出站时间：10・位置，2

进站还是出站：门整售赭间:位置：220进站还是出站;王牌号；4进出站肝间;车道上堂站若是出站:车牌号：进站还是出站：门整售赭间:位置：220进站还是出站;王牌号；4进出站肝间;车道上堂站若是出站:车牌号：5出/出站时间!车道上A30祝您新年快乐!检站还是出站；。手牌号；4也出站时间；4a髀*曾站:B步出站时间t35.小结【改进设想】用类的思想，本题我还是沿用的过程思想，对各个过程处理好就出了结果， 尽管结果没有错，但是和面向对象的思想不是太符合，所以希望可以用个停车场这一个类来处理问题。【体会】有时候在调试的时候的很小的一个结果和预想的不符就是很大的思想问题， 比如我调试的时候最后一步有时候钱算的不对，就是添加删除时的时间没有处理正确，所以，错误不在小。要知道为什么会出这个错。编程的时候重要的是提前把思路理好。.附录classCar{public:intcarno;arno=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;)else(cout<<"车道上"«endl;}car[no].intime=tim;car[no].carno=no;index++;ntime)«endl;cout<<"应缴费用："«(tim-(car[no].intime))*2«"%"«endl;index-;preindex-;求规格说明书人们在日常生活中经常需要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号码查询系统，根据用户输入的信息（例如姓名等）进行快速查询。.总体分析与设计【设计思想】本题要求的是做一个通讯录，由于所需要的数据量比较大，所以考虑在外存中进行处理,这里用的是txt文件。当然本来想用数据库的，但是水平不到家。所以放弃了。新建一个数据类型，包括姓名，固定电话，移动电话，电子邮箱。为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但是， 在数组中实现插入和删除操作的代价较高。如果记录需频繁进行插入或删除操作，可以考虑采用二叉搜索树组织电话号码信息，则查找和维护都能获得较高的时间性能。【设计表示】【详细设计表示】设置四个选项，0、1、2、3分别代表退出、查询、插入、删除。根据所需要的功能做出操作。初始数据储存在txt文本中。如果选择退出则退出系统，如果选择插入则需填写姓名，电话，手机，邮箱信息。根据名字按照二叉搜索树的形式组织插入，如果选择删除，根据名字的次序在搜索树中删除。如果是查询也根据二叉搜索树的形式删除。.编码.名字的判断大小，因为组织二叉搜索树的时候需要对插入和删除做优化，所以需要对名字的大小问题作出比较。解决的时候是通过操作符重载完成的。 开始的时候不知道汉字怎么比较大小。后来通过请教了解到汉字可以直接比较大小。 大于号的重载就是这个人的名字大于另外一个人的名字。2二叉树的插入，我拷的是以前的代码……其实自己重写一遍话的时间还少一些，因为pp和p搞反了。后来问了张唯老师才在讲的时候发现这个问题。3.删除的时候在内存中的二叉搜索树中删除很容易但是文本中的内容并没有变， 所以在内存中处理完了之后需要重写文本。 开始的时候是先删除所有的文本内容， 在重新全部重写。但是后来发信啊这样内存的开销特别大， 而且不容易实现，后来是删除之后直接就在文本中输出。发现重新输出的时候文本会重新更新。.4.程序算分分析【运行结果】口叵®石源132皿8567g01877625388918872932507131D2334S4915B3727554615^2283998711111111111222222222220271111111182722222222D27U444444402/55555555027666666660277777777711111111112222222222口叵®石源132皿8567g01877625388918872932507131D2334S4915B3727554615^2283998711111111111222222222220271111111182722222222D27U444444402/5555555502766666666027777777771111111111222222222213244856790@124.con187762538S9@136.comiaS729325D7«lqq.con1310S334049@163.con15B37275545@15522639歹目Rqq.con11111111111111111222皆2222222222222「如果要退出.「….丁「道柳也廊要查询请嗤1文评要插入请次2******如里要删除清按3******卷“赵一冗 名的为为为的查话器我要电露查您的的的要冬冬您祝赵赵赵名话北姓电手邮的的町的人人人人AAAA■-3i--3J--"i---3您您您您悔要删鹿的名字：石冰较真哗删窿吗？输入y或者n表小yes并寻已删除成功I助帮看查⑪式格广帅克金杰n^l^8均刚光1MM85679。mfl72932&D7131醛334鼬915B3727554fi155228399971111111111102711111111U272222222ZU271UiHlUU11tti027555555550276666666602777777777111111111113244fl56790@124.com胆13b.sm1SR7?9n2^O7G15a37275546@1&522S39907Q11111111111111111Tele.txt—记聿本文件旧编辑（！）格式⑪查看也）帮助®5.小结【改进设想】Txt中的信息没有对齐。如果可以的话用数据库或者 excel做可能会清晰一些。还有就是如果文本中的信息没有 8条的话是会出错的。界面不好。用 mfc会好一些……【体会】直接烤以前的代码如果有不适合的话会很麻烦，如果代码不很长的话还是抄一遍吧。那样会思路清晰一些。6.附录ifstreamin("");ame>>Tele[i].mobilnumber>>Tele[i].phonenumber>>Tele[i].email;};for(intj=0;j<total;j++){ame==temp_name0){menber0=Tele[t];}}cout<<"您真的要删除吗"<<endl;while(yorn!='y'&&yorn!='n'){cout<<"输入y或者n表示yes或者no:";cin>>yorn;}if(yorn=='y'){inttempnum=0;intnmo=0;TelNumberhere[100];while(tempnum<total){if(Tele[tempnum]!=menber0){(Tele[tempnum],delete_member);here[nmo]=delete_member;out<<setw(5)<<left<<<<setw(20)<<right<<<<right<<setw(20)<<<<setw(30)<<right<<<<endl;nmo++;}if(Tele[tempnum]==menber0){(Tele[tempnum],delete_member);tempnum++;}求规格说明书假定文本文件 中是我校所有参加南望山庄二期挑房职工的信息， 请编写程序，读出文件中的内容，再按挑房的先后次序排队后将排序号和姓名以文本方式存放到文件 中。排队原则： 先按职称排，同职称按分房工龄排，同工龄按年龄排。.总体分析与设计【设计思想】由于测试数据是在文本中的数据，所以处理起来需要用到输入输出流。将已经给好的 .中的数据在内存中处理完毕之后就重新输出到另外一个中。【设计表示】【详细设计】建立流对象两个，第一个是输入流，一个是输出流。将给输数据流读到内存中，调用排序函数，这里不能用选择排序，因为选择排序的话要写三个不同的找到最大值函数。 根据三个不同的因素来排。所以选择冒泡排序。拍完之后在输出就行了。.编码.开始的时候建立流对象忘记了。看以前的数的时候也不知道，因为以前这里也没有学通。现在做到时候是叫同学叫我怎么做流的技巧的。.排序算法。开始的时候嫌冒泡太麻烦。要写好多。想找个简单的但是后来发现就这个用的方便。其他的都需要重载函数。太麻烦。.调整间距，在用了一个left或right之后只能管一下，在下一个<<操作符之后的地方前面的限定就不起作用了。需要重新声明左对齐与右对齐。.程序算分分析【运行结果】BB123.txt-记事本文件®编辑⑥格式@）查看9帮助®止u9

£6职称编号工龄19488021321201h-431112114■■nk.txt-记事本 □0S职称编号工龄年龄U33554335443Z5剌“325曰316Sq3064等3052由3051u3049也30U8.2959429574294«4294742857U2654U276242761427534274G耳26664265。426564265542644西2555屿25532447可2444il24U23594234742345a23“Sh2343u2252u224fiii22h5U2243U21垢女荣辉省立伟辰智旭蜀莹达斌珍平宇亮嵯比目iw?科里生名小新阳鼎力小昱培芳凯哓宇超莹小建武僵巍乘竟玉腰亚工薪王轮杰俭露春华钢感浦姓里出.毁标周冯周赵吴王口胤售口味王吴r天漆詈罗朴由.小结【体会】程序大多数是对输入输出的处这次实习最大的收获就是学会了初级的输入输出流处理,理，应付不同的数据组织形式。需要掌握多种技术。程序大多数是对输入输出的处.附录classWorker{public:intnumber;umber>temp[b-1].number){tempwork=temp[b];temp[b]=temp[b-1];temp[b-1]=tempwork;}}}umber==temp[b-1].number)&&(temp[b].workage>temp[b-1].workage)){tempwork=temp[b];temp[b]=temp[b-1];temp[b-1]=tempwork;}}}umber==temp[b-1].number&&temp[b].workage==temp[b-1].workage&&temp[b].age>temp[b-1].age){tempwork=temp[b];temp[b]=temp[b-1];temp[b-1]=tempwork;}}}}intmain(intargc,char*argv[]){ifstreamin("");ame>>worker[i].number>>worker[i].workage>>worker[i].age;}bubsort(worker,505);for(intindex=0;index<505;index++){out<<left<<setw(7)<<worker[index].name<<setw(8)<<right<<worker[index].number<<setw(8)<<worker[index].workage<<setw(9)<<worker[index].age<<endl;}cout<<"OK!"<<endl;return0;实习题目四.需求规格说明书“火烧连营”是三国演义中的著名典故之一广为流传，假定文本文件 是火烧连营中的军营分布图，每个字符A代表一个营帐，营帐是可燃物，其他字符代表不可燃的空白地段，文件共有40行70歹U,请你编写程序，读入该文件的内容，再从键盘输入任意点的 x和y值(x<70,y<40)作为着火点，“火烧连营”后，被燃烧的营帐标上字符' X',并把整个结果输出到文件中。.总体分析与设计【设计思想】基本思想：从着火点位置开始，按四连通思想上下左右寻找其邻居点。 OOOO开辟一个堆栈，先将着火点压栈，然后重复一下操作：栈顶点出栈并标记 X,同时将符合被燃烧条件的邻居点入栈。。。。，直到栈空为止。【设计表示】【详细设计】首先将cl中的数据独到内存中，在内存中处理是否火烧连营，然后根据输入的坐标，如果坐标显示的是A的话就将连在一起的A全部变成X。具体做法是做一个栈。将A压倒栈里面去，出栈顶。压入的后边是 A的坐标，在重复以上做法。如果是一就不处理。等栈空了之后就结束。.编码.二维数组的赋值。因为数据是从 cl里面获取的，需要一个空的二维空间来存储他一遍再内存中可以使用。所以需要开辟一个动态的二维数组，静态的不行就是因为需要初始化。这里声明的时候。二维数组的分两步，第一步是声明以为的指针数组，在声明以为数组。2.行列出错，说的是40行70歹U,但是我开始声明的时候总是反了，结果内存总出问题。后来改正了。.程序算分分析【运行结果】*七叱-记聿本 匚反编辑如格式。交看超』都助⑥ 同口白 ^AAnnAnAnAflAnAAAAAflAflAflAAAAnA 白口口皿皿门口门口白口白口口nanna口由口口口口 AAAAAAAAAAAAftAAAAAAft nAAAflAAAAnAAAAAAAA AAAAAAAnAAAAAA AAnAAHAAAA AAAAAA AAAAAAAAAA AAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAnAA HnAnAnAnAAAAAflAHAHAANHRAnAHAn .AAAFlAARAAAAAflAAiAAAAAAAAnAAAAAAAft .AAAA...AAAAAaAaAAAAAAAAAAAAAAAAAAAAAAAAfl.. fAAAAAA..AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAflAAAAAAAAAAAftAAAftAflAAA ARAAAAAAAAAAAAA AAAAAAAAAAAAAftAAAAAA AAAAAAftAAflAA^AAA. AAAAAAAAAAAAAAAAAA. AAAAAAAAAftflftAAAAA, ^AAftAflAAAAAAAAAAA H内科HHHRHH白血M.. .AAAAAAAAAAAAAARA ,....AAAAAAAAAAAfiftAAA... 0%醺山口口口口血白血 白白白白AQ口口RR口口的口白口…. AAAAAAAAAAAAAAA AAAAAAAAAAAAAftAA.... AAAAAAAAAAAAAAAAAAAAAA AHAAAAAAAAAAAAAAAA AAPAAAAAAflAAAA….AAAAAAftAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAA..AAAAAAAftAAAAAAAAAAAAAAAA AnAAHnARAHA-.nnAnARFinRRAnARAAAAAAAAR AARA力科，科-..由AAAA自由由由由白科由自力 .AriAAAflAAAAAAAriA. ,.， AAAAAAAAAAAnAAAAAARAAARA AAAAAAAAAAAAAAAAAAAnAAAAAAA AARAAAAAAAAAAAAAAAAAAAAAAAR ftAAAAAAAAAAAAAAAAAAAnAAAAAAA nnnHnRnnnHARRARAnnRAnnHnnRRR ,^AAAAF^AAAAAA. ARHHHWRHRHHH由 nnna口口口口 aaaaaaan EEP2,txt-记事本 [Tj(n文件⑥编辑3）槁式电）查看但）锦助如 芥芥芥芥 JiJtXMKKMXX；(薜XXH怎XXXXXXX邓XXJtXXX xxxxxxxxxxxxmxxxxxxxxxjcxx XKXXKXXXMXXX*KXXXXKX KXXXXXXWXXXXXXXJIX XXXXXKXXXXXXIiX xxxwxxxxx MNXXXN AAAAAAAAAA 触由帕帕帕白由白府时 flAAAAHAAAHnARAAHAflRnRA AAftAAAARAnAAAAAAAAAriAAAAAAAAA AnAAAflAAnAAAnAnAnnnAAflflAflAfln(innn aara.- AAAAAAAAnAAAAAAAAf>AAAnAAAAAAAAARA AAARAA. AAAAAAAAAAAAAAAAAAAAAfiAAAAAAflAAAAA AAfiAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAfiAAAAARAAARAA AAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAA4A AAAAAAAAAAAAAAflA. .RHAHAARARRHARAHRHR.. HRARRRHRflRRRRARRH. AAAftAAAAAAAAAAAAA AAAAAHAAA^AAAAAAA.. MAAAAAAAAAAQftAftA N口由门口府口口口口口门口口内口，.. .AAAAAAAAAAftAftAft ..AftAAAAAAAAfiAAftAAA... AAAAAAftAAAAAftAA AAAAAAAAAAAAAAAA.. AAAAAAAAAAAAftAAftftAAAflft AAnAAAAAAAAAAAAAAA AAAAftAAAAnAA4A..AAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAA4A..fiAAAAAAAAAAAAAAAAAAAAHAA AAAAAAAA^AA.,AAAAAAAAflAAA^AAA^A^A^AA AAAAAAAA...AAAAAaAAAAAAAAA AAAAAAAAAAAAAAA.. AAAAAAAAAAAAAAAAAAAAAAftA AriAAAAAAAAAAAAAAAnAAAftAAAAA 由肺加配AD皿AA由口白"由蒯的皿AA nAHAARAAAnAAAAAAAAAAAAAAAAAA rmnfinnnfkR自力arra/自由由nRfmnnnRn AAAAAAAAAAnA. AftAAflAAAAAflfiA _ AflAAAAAA AAAAAAAA .小结【体会】这题最大的收获就是二维数组的声明。 以前总是声明的以为数组， 很熟练，但是到了二维数组的时候就不是一样的声明方法了。所以积累了知识。.附录voidgetfire（char**temp_A,LinkedStack<char>temp_stake,inttemp_x,inttemp_y）{char temp='X';int xx; 求规格说明书需要在某个城市的n个居民区之间铺设煤气管道，则在这n个居民区之间只要铺设n-1条管道即可。假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同。选择最有的施工方案能使总投资尽可能少， 这个问题即为求网的“最小生成树”.总体分析与设计【设计思想】用Kruskal算法，找到所有的最短边，构成通路。从最开始输入的时候的起点找到起点的最短通路，再将通道一一输出。【设计表示】【详细设计】从main函数入口。得到丁点个数，建立这么多个顶点的有向图，再调用输入函数得到各个点和边的权值。得到之后将权值储存在边的数组中， 排序。然后经过深度优先，得到串联的有向图解，根据需求输出方案并且得到耗费。.编码.最难的是深度优先搜索函数，上次实习的时候是将深度优先和宽度优先在一个函数中实现的，但是这次是讲深度优先拆成几个函数的符合而成。 需要深刻知道reach数组和result数组的作用。.判断环路是一个难点。这里的判断方法是终点的 reach不等于一。开始的时候始终不知道怎么做。上网查询了不少。 但是有意义的没多少。后来半猜半试的做的