数据结构实习报告

数据构造课程实习汇报姓名：王倩倩学号：1002193班号：116102-12指导老师:陈亮、陈占龙中国地质大学信息工程学院/2/13实习汇报内容停车场管理系统（1）需求规格阐明【问题描述】：设停车场是一种可停放n辆汽车的狭长通道，且只有一种大门可供汽车进出。汽车在停车场内按车辆抵达时间的先后次序，依次由北向南排列（大门在最南端，最先抵达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等待，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述规定进行管理的模拟程序。【基本规定】：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“抵达”或“拜别”信息，汽车牌照号以及抵达或拜别的时刻。对每一组输入的数据进行操作后的输出信息为：若是车辆抵达，则输出汽车在停车场内或便道上的停车位置；若是车辆拜别，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以次序构造实现，队列以链表构造实现。（2）总体分析与设计【算法设计】设计思想：用栈来模拟停车场，队列用来模拟便道，根据主界面输入的数据来对停车场进行管理，创立一种构造体Car用它来存储有关汽车的所有信息（车牌号、停入的时间信息等），当一种车进入停车场时把车子的信息存入构造体中，然后对构造体Car进行压栈，或压入队列，并输出车子的停车信息；当车子离开时，把构造体从栈中弹出，并根据离开时间计算出停车所需的停车费用。主界面二、设计表达：主界面退出系统停车费用查询便道车辆查询车辆离开车辆抵达退出系统停车费用查询便道车辆查询车辆离开车辆抵达Add()Arrival()Add()Add()Arrival()Add()QueueStackIsFull()QueueStackIsFull()Delete()IsEmpty（）Delete()IsEmpty（）Leave()leaveDelete()()Leave()leaveDelete()()（3）程序构造分析：由于停车场中，每辆车子都是按次序停入的，要有先后次序，且只有一种进出口，后进先出，因此要用栈模拟的停车场，创立一种构造体存入车辆信息，车子进入停车场时用Stack的Add（）函数把已存入车辆信息的构造体对象进行压栈，当停车场停满即栈满时，用Queue的Add（）函数把车子停入此外一种便道，让车子在便道等待，等栈内有空位时，再将车停入停车场；当车辆离开时先用Leave（）函数判断，车子与否在停车场中，若在Leave（）函数调用Stack的Delete（）函数，若不在输出“您要查找的车不在！”。（4）编程碰到的问题计算法改善：1、有关车辆信息的保留：由于车辆信息需要保留不止一项，因此需要建立一种可以保留信息的东西，刚开始我用的是类，信息虽然存进去了可是类却不会压栈，最终放弃，创立一种构造体Car，它功能和类差不多并且应用比较简朴。2、车辆离开时的判断：当车辆离开时，首先要判断车子与否在停车站内，当栈不为空时，从栈顶开始一种个判断输入的车牌号与否在栈内，这时就用到了Top（）函数判等（park.Top().carnumber==Carnumber）若不等寻找下一种，若相等把它弹出栈。（5）编码定义构造体Car：structCar{intcarnumber; inthour; intmin;};车辆抵达时的Arrival（）函数：intArrival(){CarCa;cout<<"请输入车牌号:"; cin>>Ca.carnumber; cout<<"请输入车辆停入时间:"<<endl; cin>>Ca.hour; cin>>Ca.min; cout<<"目前时间为:"<<Ca.hour<<":"<<Ca.min<<endl;if(park.IsFull()){cout<<"目前停车位已满，请到便道等待！"<<endl; wait.Add(Ca); i++; cout<<"目前车子位置在："<<i<<endl; } Elsepark.Add(Ca); j++; cout<<"目前车子的位置在："<<j<<endl; return0;}车辆离开是的Leave（）函数：intLeave(){ // Stack<Car>park(2); // Stack<Car>tem(2); intCarnumber; intH,M; cout<<"请输入车牌号:"; cin>>Carnumber; CarC; charm; if(!park.IsEmpty()) { while(park.Top().carnumber!=Carnumber) { park.Delete(C); j--; tem.Add(C); m++; if(park.IsEmpty()) {cout<<"您要查找的车不在！"<<endl;} } if(park.Top().carnumber==Carnumber) { park.Delete(C); j--; cout<<"请输入车辆离开时间:"<<endl; cin>>H>>M; cout<<"目前时间为:"<<H<<":"<<M<<endl; intprice; price=((H-C.hour)*60+(M-C.min))*5; cout<<"应缴费用为："<<price<<endl; } } else cout<<"您要查找的车不在！"<<endl; return0;}停车费用的计算：cout<<"请输入车辆停入时间："; intinhour,inmin; cin>>inhour>>inmin; cout<<"请输入车辆离开时间："; intouhour,oumin; cin>>ouhour>>oumin; cout<<"应缴纳的费用为："<<((ouhour-inhour)*60+(oumin-inmin))*0.5<<endl;break;主界面的设计即main（）函数：intmain(){ //LinkedQueuequeue; cout<<"欢迎进入停车场管理系统,很快乐为您服务!"<<endl; cout<<"请选择您要进行的操作:"<<endl; cout<<"A:车辆停入;"<<endl; cout<<"D:车辆离开;"<<endl; cout<<"B:便道车辆查询；"<<endl; cout<<"F:停车费用查询；"<<endl; cout<<"K:退出系统;"<<endl; chara; do{ cin>>a; { switch(a) { case'A':Arrival();break; case'D':Leave();break; case'B':break; case'F':cout<<"请输入车辆停入时间："; intinhour,inmin; cin>>inhour>>inmin; cout<<"请输入车辆离开时间："; intouhour,oumin; cin>>ouhour>>oumin; cout<<"应缴纳的费用为："<<((ouhour-inhour)*60+(oumin-inmin))*0.5<<endl;break; case'K':cout<<"谢谢您的使用！"<<endl;break; default:break; } } }while(a!='k'); return0;}（6）附录：运行成果1、主界面设计：2、有关车辆停入：3、车辆离开：4、停车费用的查询：5、退出系统：二、排序应用（职工分房排序）（1）需求规格阐明【问题描述】：假定文本文献A1.txt中是我校所有参与南望山庄二期挑房职工的信息，请编写程序，读出文献中的内容，再按挑房的先后次序排队后将排序号和姓名以文本方式寄存到文献A2.txt中。排队原则：先按职称排，同职称按分房工龄排，同工龄按年龄排。职称编号：校级干部0专家、正处级1副专家、副处级2讲师、科级3其他4【基本规定】：本题由于排序所需的数据放在一种文本文献中，因此要在程序中建立程序和文本文献的联络，读入文本文献，在程序中进行排序，然后再输出并保留在此外一种文本文献中。（2）总体设计与规定【算法设计】：设计思想：Infile（）函数a1文本SInfile（）函数a1文本Swap（）函数a2文本Outfile（）函数a2文本Outfile（）函数Bubble（）函数设计表达：主函数：main（）互换位置函数：swap（）排序函数（冒泡排序）：bubble（）读入文献：infile（）读出文献：outfile（）（3）程序构造分析：在本程序中重要考虑的是怎样把程序和外存中的文本联络起来，尚有一种冒泡排序，因此程序总体构造不是太复杂，只要将文本的读入和读出尚有排序关系处理好就没问题了。（4）编程碰到的问题及改善措施：由于程序自身不是太难，因此碰到的问题也就不是诸多，一般都是小问题，尚有一种值得尤其注意的地方就是，由于本题中排序需要比较的数据有三个，因此要写三个排序用for循环来嵌套。（5）编码1、存储教师信息的构造体：structteacher{ charname[10]; intzhicheng; intworktime; intage;};2、有关排序:voidswap(int&a,int&b){ intt; t=a; a=b; b=t; }voidBubble(teacher*tea,intn=510){ for(inti=1;i<n;i++) { for(intj=0;j<n-i;j++) { if(tea[j].zhicheng>tea[j+1].zhicheng) { swap(tea[j],tea[j+1]); } else if(tea[j].zhicheng==tea[j+1].zhicheng) { if(tea[j].worktime<tea[j+1].worktime) { swap(tea[j],tea[j+1]); } elseif(tea[j].worktime==tea[j+1].worktime) { if(tea[j].age<tea[j+1].age) { swap(tea[j],tea[j+1]); } } } } }}3、文本文献的读入和读出：ifstreaminfile("a1.txt"); ofstreamoutfile("a2.txt"); charline[50]; while(!infile.) infile.getline(line,50); outfile<<line<<endl; infile.close(); for(intm=0;m<510;m++) { infile>>Name>>Zhicheng>>Worktime>>Age; strcpy(tea[m].name,Name); tea[m].zhicheng=Zhicheng; tea[m].worktime=Worktime; tea[m].age=Age; }//teachera[505];//intn; for(inti=n;i>1;i--) Bubble(tea,550); for(inti=0;i<550;i++) { oufile<<setiosflags(ios_base::left)<<setw(13)<<tea[j].name<<setw(8)<<tea[j].zhicheng<<setw(8)<<tea[j].worktime<<setw(8)<<tea[j].age<<endl; // outfile<<tea[i].name<<""<<tea[i].zhicheng<<""<<tea[i].worktime<<""<<tea[i].age<<endl; // outfile.close(); }（6）附录：运行成果运行前：运行后：三、电话号码查询：（1）需求规格阐明：【问题描述】：人们在平常生活中常常需要查找某个人或某个单位的电话号码，本试验将实现一种简朴的个人电话号码查询系统，根据顾客输入的信息（例如姓名等）进行迅速查询。【基本规定】：（1）在外存上，用文献保留电话号码信息；（2）在内存中，设计数据构造存储电话号码信息；（3）提供查询功能：根据姓名实现迅速查询；（4）提供其他维护功能：例如插入、删除、修改等。（2）总体设计与规定：【算法设计】：设计思想：由于需要管理的电话号码信息较多，并且要在程序运行结束后仍然保留电话号码信息，因此电话号码信息采用文献的形式寄存到外存中。在系统运行时，需要将电话号码信息从文献调入内存来进行查找等操作，为了接受文献中的内容，要有一种数据构造TeleNumber与之对应，里面保留着人们的电话信息（固定电话、移动电话和电子邮箱），并设计一种链表类classTele来对系统进行操作。Insert（）Insert（）插入主界面Show（）显示主界面Show（）ClassTeleDelete（）删除ClassTeleDelete（）Sort（）排序Sort（）a1.txtChange（）修改a1.txtChange（）Search（）Search（）Save（）Save（）（3）程序构造分析：本题相对于分房排序来说难度有所增长，由于分房排序中对内存没有规定，只需将外存文献读入，在内存中进行排序然后再输出就好了。而本题还需要将电话号码信息在内存中，需要建立一种存储构造与外存文献相对应。（4）编程碰到的问题及改善措施：由于本题需要在内存中建立一种对应的存储构造与外存文献相对应，刚开始时根据老师说的建立二叉搜索树进行排序，由于对我来说难度太大，因此把它改成了冒泡排序法，它要比二叉搜索树慢些。（5）编码：电话号码（构造体）：structTeleNumber{ charname[10];//姓名intphoneNumber;//固定电话号码intmobileNumber;//移动电话号码charemail[10];//电子邮箱 ints; TeleNumber*Next; voidReadFile(istream&infile); voidinput(); voiddisplay();};对系统进行操作的Tele类：classTele//功能类{ public: Tele();//构造函数 ~Tele();//析构函数 voidSave();//数据保留到文献 TeleNumber*Search(char*);//信息查找 voidSort();//排序 voidInsert();//插入 voidDelete();//删除 voidChange();//更改个人信息 voidShow();//显示个人信息 voidSwap(TeleNumber*,TeleNumber*); private: TeleNumber*End,*Head; ifstreaminfile;//定义读，写文献对象 ofstreamoutfile;};在Tele的构造函数中建立单链表存储构造体TeleNumber：Tele::Tele(){ Head=newTeleNumber;//头插法建立单链表 Head->Next=newTeleNumber; End=Head->Next; infile.open("a1.text");//打开外存文献，看与否有数据存在 while(!infile.eof())//假如有，则打开，并将数据读取到程序 { End->ReadFile(infile); if(End->name[0]=='\0')break; End->Next=newTeleNumber; End=End->Next; } // infile.close(); }文献保留：voidTele::Save()//保留文献{ outfile.open("a1.txt");//建立外存文献a1.txt for(TeleNumber*p=Head->Next;p!=End;p=p->Next) outfile<<p->name<<""<<p->phoneNumber<<""<<p->mobileNumber<<""<<p->email<<endl;//将数据存到外存文献里 outfile.close(); cout<<"保留成功！"<<endl;}主界面及其功能设计：intmain(){ boolflag=true; Teletele; charname[20]; while(flag) { //system("cls"); Cout<<“个人电话号码查询系统"<<endl; cout<<"请选择您所需要的操作："<<endl; cout<<"A.增长电话号码"<<endl; cout<<”B.显示电话号码"<<endl; cout<<"C.排序个人电话"<<endl; cout<<"D.查找个人电话"<<endl; cout<<"E.删除个人信息"<<endl; cout<<"F.修改个人信息"<<endl; cout<<"G.保留个人信息"<<endl; cout<<"K.退出系统"<<endl;charx; do{ cin>>x; { switch(x) { case'A':tele.Insert();break; case'B':tele.Show();break; case'C':tele.Sort();break; case'D':cout<<"请输入查找人姓名"<<endl; cin>>name; tele.Search(name);break; case'E':tele.Delete();break; case'F':tele.Change();break; case'G':tele.Save();break; case'K':cout<<"谢谢您的使用！"<<endl; default:break; } } }while(x!='K'); } return0;}（6）附录：运行成果查找：修改：四、火烧连营（1）需求规格阐明：【问题描述】：“火烧连营”是三国演义中的著名典故之一广为流传，假定文本文献c1.txt是火烧连营中的军营分布图，每个字符A代表一种营帐，营帐是可燃物，其他字符代表不可燃的空白地段，文献共有40行70列，从键盘输入任意点的x和y值（x<70,y<40）作为着火点，“火烧连营”后，被燃烧的营帐标上字符’X’。【基本规定】：从文本c1.txt读入内容，再从键盘输入任意点的x和y值（x<70,y<40）作为着火点，“火烧连营”后，被燃烧的营帐标上字符’X’，并把整个成果输出到文献c2.txt（2）总体设计与规定：【算法设计】：设计思想：在上课时老师给我们讲过一种迷宫的例子，就是从一种点出发，前后左右遍历跟这个点有关联的连通点，而这道题目就和迷宫题有相似之处，只要开辟一种堆栈，先将着火点压栈，然后反复一下操作：栈顶点出栈并标识X，同步将符合被燃烧条件的邻居点入栈。。。。，直到栈空为止。设计表达：读入数据Infile.c1.txt读入数据Infile.c1.txtFile.IsEmpty（）File.IsEmpty（）fire.[i][j]fire.[i][j]判断与否可燃判断与否可燃着火点压栈yazhan着火点压栈yazhanDeleteDelete（）Stack.FStack.File.Add()可燃点弹出输出成果输出成果（3）程序构造分析:本程序虽然也是波及到外存与内存但没有规定互相对应，只需将外存数据读入内存，在内存中把着火点表达出来就好了，因此相对来说还是比电话号码查询要简朴，最重要的环节就是前后左右遍历着火点，直到所有与之连通点都被遍历就好了，这需要几种if语句想嵌套就好了。(