数据结构实验

实验报告||实验名称约瑟夫环、停车场管理、二叉树的遍历、图的广度优先遍历和深度优先遍历、哈希表的设计课程名称算法与数据结构|专业班级：学生姓名：学号：成绩：指导教师：袁和金实验日期：20160621一、约瑟夫环1、实验目的及要求：利用单向循环链表存储结构模拟此过程，利用顺序结构模拟此过程。2、问题描述：约瑟夫(Joseph)问题:已知n个人(以编号1，2，3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。3、实验内容:顺序表：#includeiostreamusingnamespacestd;classVector{private:intm,n;int*p;public:Vector(intinput_m,intinput_n){m=input_m;n=input_n;p=newint[n];//建立动态数组}~Vector(){delete[]p;}voidinput(){//建立约瑟夫环for(inti=0;in;i++)p[i]=i+1;}voiddeletenum(intloc){for(inti=loc;in-1;i++){if(loc+1==n)break;p[i]=p[i+1];}n=n-1;}voidprint(){//输出约瑟夫环if(n%m==0){//n为m的倍数时输出对应环中的数for(inti=0,t=0;i=n/m;i++){t=t+m-1;coutp[t];deletenum(t);//删除该数}}intc=0;while(n!=1){c=c+m-1;if(c=n)c=c%n;coutp[c];deletenum(c);if(n==1)coutp[0];}}};intmain(){inta,b;cout请输入人数和间隔:;cinab;Vectorv(a,b);v.input();v.print();return0;}单链表：#includeiostreamusingnamespacestd;classNode{//定义链表结点public:intdata;//数据域Node*next;//next指针域Node(int_data){data=_data;next=NULL;}};classLinkList{private:Node*head;//定义头指针public:LinkList(){head=NULL;}voidinsert(Node*node,intindex){//插入结点if(head==NULL){//当头指针为空head=node;node-next=head;return;}if(index==2){//当插入位置为第二个时head-next=node;node-next=head;return;}Node*current_node=head;intcount=1;while(countindex-1){current_node=current_node-next;count++;}if(count==index-1){//将最后一个结点连到头指针上构成循环链表node-next=head;current_node-next=node;}}voidoutput(intm){//循环输出约瑟夫环数intcount=1;Node*current_node=head;while(current_node!=current_node-next){while(countm-1){//找到相隔m的数的前一个数current_node=current_node-next;count++;}count=1;//输出相隔m的数cout(current_node-next)-data;Node*p=current_node-next;current_node-next=(current_node-next)-next;deletep;current_node=current_node-next;}coutcurrent_node-data;deletecurrent_node;}};intmain(){LinkListlinklist;intn,m;cout请输入人数和间隔:endl;cinnm;for(inti=1;i=n;i++){Node*node=newNode(i);linklist.insert(node,i);}linklist.output(m);return0;}4、实验结果：二、停车场管理1、实验目的及要求：熟练栈和队列的结构特性，掌握在实际背景下的应用。2、问题描述：设停车场是一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出.汽车在停车场内按车辆到达时间的先后顺序,依次从停车厂最里面向大门口停放(最先到达的第一辆车停放在车场的最里面),若车场内一停满n辆汽车,则后来的汽车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入车场,每辆停放在车场内的车在它离开时必须按它停留时间长短交纳费用.如果停留在便道上的车未进车场就要离去,允许其离去,不收停车费,并且其他在便道上等待的车辆的次序不变.编制一程序模拟停车场管理。3、实验内容：#includeiostreamusingnamespacestd;classcar{//定义停车场的汽车类public:intnum;charcommand;inttime;car(){}car(intn,charc,intt){num=n;command=c;time=t;}};classStack{//定义栈public:carG[3];inttop;Stack(){top=0;}voidpush(carc){//压栈G[top++]=c;}voidpop(car&c){//弹栈if(top==0){cout*停车场为空endl;return;}top--;}};classtemway{//定义便道上的车信息public:intnum;//汽车车号temway*next;temway(){}temway(intn){num=n;next=NULL;}};classQueue{//定义便道队列public:temway*front;//队头指针temway*rear;//队尾指针intlength;//队的长度Queue(){front=rear=newtemway();front-next=NULL;length=0;}~Queue(){if(rear==front){deleterear;front=NULL;rear=NULL;}else{deleterear;rear=NULL;deletefront;front=NULL;}}voidenqueue(intcnum){//进队temway*p=newtemway(cnum);if(front==rear){//插入到便道0号位front-next=p;rear=p;length++;}else{rear-next=p;rear=p;length++;}}voidpopqueue(temway*w){//出队,删除第一个元素temway*p;if(front==rear){cout*便道为空endl;return;}p=front-next;if(p==w&&p==rear){rear=front;length--;deletep;}elseif(p==w){front-next=p-next;deletep;length--;}}};voidarrive(Queue&q,Stack&s,cara){//当停车场的车的数量小于3时的处理方法if(s.top3){s.push(a);cout*车号为:a.numendl;cout*进入时间为：a.timeendl;cout*请把车停在s.top号位上endl;}//当停车场的车的数量等于3后车进入便道的处理方法else{q.enqueue(a.num);cout*车号为:a.numendl;cout*进入时间为：a.timeendl;cout*停车场已满，请将车停在便道的q.length号位上endl;}}//s1为停车场栈，s2为临时栈voidleave(Queue&q,Stack&s,Stack&s1,carl){intx,y,i;temway*p;for(i=0;is.top;i++){if(s.G[i].num!=l.num)continue;elsebreak;}if(i==s.top){cout*error！停车场中无此车！endl;return;}x=l.time-s.G[i].time;//从进入到离开的时间差y=10*x;//计算费用cout*车牌号为l.num的停车时间为：x小时endl;cout*停车费用为y元endl;if(is.top-1){for(intj=i+1;js.top;j++)s1.push(s.G[j]);for(intm=i,n=0;ms.top&&ns1.top;n++,m++)s.G[m]=s1.G[n];}if(q.length==0)//便道为空s.top--;else{//便道不为空p=q.front-next;s.G[s.top-1].num=p-num;//便道上的车进入停车场的时间为当前要离开车的时间s.G[s.top-1].time=l.time;q.popqueue(p);}}//对输入命令的处理方法voidjudgeResult(Stack&s,Stack&s1,Queue&q,carc){if(c.command=='E'||c.command=='e')cout*退出系统！endl;elseif((c.command=='W'||c.command=='w')&&c.num==0&&c.time==0)cout*便道中的汽车数为：q.lengthendl;elseif((c.command=='P'||c.command=='p')&&c.num==0&&c.time==0)cout*停车场中的汽车数为：s.topendl;elseif(c.command=='A'||c.command=='a')arrive(q,s,c);elseif(c.command=='D'||c.command=='d')leave(q,s,s1,c);elsecout*ERROR!endl;}intmain(){Stacks,s1;//定义停车场栈和临时栈Queueq;//定义便道队列carc;cout********************************************************************************\n;cout*********************************停车场管理系统*********************************\n;cout********************************************************************************\n;cout**A(a)车辆到达;D(d)车辆离开;P(p)停车场车辆总数;W(w)便道车辆总数;E(e)退出系统**\n;while(c.command!='E'||c.command!='e'){cout