搜索
北京邮电大学信息与通信工程学院第1页数据结构实验报告实验名称：学生姓名：班级：班内序号：学号：日期：1．实验要求掌握如下内容：1、进一步掌握指针、模板类、异常处理的使用2、掌握栈的操作的实现方法3、掌握队列的操作的实现方法4、学习使用栈解决实际问题的能力5、学习使用队列解决实际问题的能力利用队列结构实现车厢重排问题。车厢重排问题如下：一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。给定任意次序的车厢，通过转轨站将车厢编号按顺序重新排成1~n。转轨站共有k个缓冲轨，缓冲轨位于入轨和出轨之间。开始时，车厢从入轨进入缓冲轨，经过缓冲轨的重排后，按1~n的顺序进入出轨。缓冲轨按照先进先出方式，编写一个算法，将任意次序的车厢进行重排，输出每个缓冲轨中的车厢编号。2.程序分析2.1存储结构为了实现对火车车厢的存储，方便以后的排序，在储存初始化的主轨道和副轨道的火车车厢时，采用了链队列的思想，将每个车厢视为一个结构体，该结构体中的两个元素分别为整形与指向这种结构体的一个指针。整形数代表主车厢的每个车厢的编号，而指针则指向下一个车厢。对于整个主轨道和缓冲轨,分别采用一个数组来存储它们的排序方式，即该轨道中列车的排序方式。但是每个轨道中列车的数量是不确定的，因此不能采用静态数组，必须采用动态数组，因此储存列车编号的数组是动态数组，通过对内存空间的申请使用来申请动态数组储存列车编号。以下是主轨道和缓冲轨的存储结构示意图：缓冲轨1：北京邮电大学信息与通信工程学院第2页缓冲轨2：缓冲轨3：、、、、、、缓冲轨n：另外，专门定义了一个结构体LinkQueue，对对象的操作进行统一的定义。比如出队入队操作，析构操作等。2.2关键算法分析一：关键算法分析：1：链队列的构造函数：1：建立一个新的结点，2：节点的next域指向空3：将front结点和rear结点都指向该节点2：链队列的析构函数：1：建立一个指向头结点的指针2:如果该节点不为空，再建立一个指针，指向该节点的next结点3:释放该节点指向的内存空间4：重复以上两步操作3：链队列的入队操作函数1：建立一个新结点2：对该新结点的数据域和next域进行赋值，next赋为空3：将rear指针的next域指向该新结点4：该新结点赋给rear指针4：链队列的出队操作函数1：判断是否发生下溢2：新建一个指针指向front的next域3：将front的next域改为p的next域4：如果p的next不为空，就释放p指针，否则将rear赋值为front北京邮电大学信息与通信工程学院第3页5：返回被析构的结点的数据域的值5：遍历打印元素1：建立一个指针，指向front的next域2：输出该指针指向的结点的next域3：如果该指针不是空的话，那么该指针继续指向下一个结点6：将主轨道内的火车车厢开进缓冲轨的函数1：将主轨道的最前面的元素入队2：如果进入的该缓冲轨是空的话，那么是可以入队的3：如果进入的缓冲轨不是空的，那么判断最近进入缓冲轨的车厢编号是否大于马上就要进入的车厢编号，如果大于，就不能进入，否则，可以进入4：如果所有的缓冲轨都不满足以上条件，该函数结束，并且提示无法对车厢进行排序。7、依次按1~n的顺序出轨。cout车厢出轨次序为：endl;for(intp=1;p=n;p++)//遍历依次输出{for(intq=0;qk;q++){if(a[q].GetFront()==p)couta[q].DeQueue();}}二：代码详细分析1：链队列的构造函数O(n)1：建立一个指向Node的指针：NodeT*s=newNodeT;2：将该指针的next域赋值为空：s-next=NULL;3：将头指针和尾指针指向该节点front=rear=s;FrontRearS2：链队列的析构函数O(n)1：建立一个新指针指向头结点：NodeT*p=front;2：如果该指针不为空：while(p!=NULL){3：再建立一个指针指向p：NodeT*q=p;4：将p指向p的下一个元素：p=p-next;5：释放p指向的空间：deleteq;}p北京邮电大学信息与通信工程学院第4页3：链队列的入队操作函数O（1）1:建立一个指针：NodeT*s=newNodeT;2：将该指针的data域赋值为x：s-data=x;3：将该指针的next域赋值为空s-next=NULL;4：将尾指针的next域指向s：rear-next=s;5：将尾指针赋值为s：rear=s;SRear4：链队列的出队操作函数O（1）1：判断头结点和尾节点是否相等，如果相等，抛出发生下溢的报错信息：if(rear==front)throw发¤¡é生¦¨²下?溢°?;2：建立一个新指针指向front的next域，即队首元素：NodeT*p=front-next;3：建立一个整形变量保存p的data域：intx=p-data;4：将front的next域赋值为p的next域：front-next=p-next;5：如果p的next域为空：if(p-next==NULL)6：首尾节点相等：rear=front;7：释放p节点指向的内存：deletep;8：返回一个x值：returnx;P5：遍历打印元素O（n）1：建立新结点指向front的next域：NodeT*p=front-next;2：如果p不为空：while(p){3：如果p为空：if(p==NULL)4：终止：break;else{5：否则输出p的data域：coutp-data'';6：将p赋值为p的next域名：p=p-next;}};P北京邮电大学信息与通信工程学院第5页2.3其它对轨道排序的操作，其实可以采用更优化的算法，比如说一个较大的车厢号，可以优先进入级别更高的缓冲轨，这样有利于合理的空间利用。使得每个缓冲轨尽可能的多放几个车厢。3.程序运行结果1：主函数流程图是2：程序执行的结果如图所示：当可以正常排序时：北京邮电大学信息与通信工程学院第6页当无法正常排序时：3．总结1：对车厢排序的算法还可以进一步优化，使得排序更加合理，对于较大的车厢号，可以北京邮电大学信息与通信工程学院第7页优先进入级别高的缓冲轨，为小的车厢留出低级的缓冲轨。2：在对队列的使用过程中，体会到了对先进先出的思想的使用极其优点，对栈的使用有了更进一步的认识。3：下一步，可以将排序算法优化，使得程序的实现性更好，而且占用较小的计算机资源开支。源代码：//车厢重排.cpp:定义控制台应用程序的入口点。//#includestdafx.h#includeiostream#includectimeusingnamespacestd;constintMaxSize=1000;templateclassTstructNode{Tdata;NodeT*next;};templateclassTclassLinkQueue//链队列模板类{public:LinkQueue();//构造函数~LinkQueue();//析构函数voidtempTrans();//遍历输出缓冲轨中的内容voidEnterQueue(Tx);//入队TDeQueue();//出队TGetFront()//查找队头元素,返回队头元素的数据域{if(front!=rear)returnfront-next-data;elsereturn0;}TGetRear()//查找队尾元素，返回队尾元素的数据域{if(front!=rear)returnrear-data;else北京邮电大学信息与通信工程学院第8页return0;}boolEmpty(){if(front==NULL)return1;elsereturn0;}//判断队列是否为空，如果是空，返回，否则返回friendvoidDrive(intarr[],LinkQueueTa[],intn,intk);//一个友元函数drive，实现从主到缓冲的变换private:NodeT*front,*rear;};templateclassTLinkQueueT::LinkQueue(){NodeT*s=newNodeT;s-next=NULL;front=rear=s;}templateclassTLinkQueueT::~LinkQueue(){NodeT*p=front;while(p!=NULL){NodeT*q=p;p=p-next;deleteq;}}templateclassTvoidLinkQueueT::EnterQueue(Tx){NodeT*s=newNodeT;s-data=x;s-next=NULL;rear-next=s;rear=s;}templateclassTTLinkQueueT::DeQueue()北京邮电大学信息与通信工程学院第9页{if(rear==front)throw发生下溢;NodeT*p=front-next;intx=p-data;front-next=p-next;if(p-next==NULL)rear=front;deletep;returnx;}templateclassTvoidLinkQueueT::tempTrans()//遍历输出缓冲轨中的元素的值{NodeT*p=front-next;while(p){if(p==NULL)break;else{coutp-data'';p=p-next;}};}voidmain(){intn,k,t;cout请输入火车的车厢数n:;cinn;if(nMaxSize)throw输入错误!车厢数太大了!;if(n=0)throw车厢数不能为负数;cout请输入缓冲轨数k:;cink;if(k=0)throw必须存在缓冲轨道!;cout这一列火车有n节车厢，;srand((unsigned)time(NULL));//产生随机数，生成火车初始车厢号排列intcount=0;int*main;main=newint[n];int*mark;mark=newint[n];while(count!=n)北京邮电大学信息与通信工程学院第10页{t=rand()%n;if(mark[t]!=1){main[t]=count+1;mark[t]=1;count++;}}//完成对array数组的赋值，生成了初始的车厢排列cout火车车厢初始的排序为:endl;for(inti=0;in;i++)coutmain[i];//逐个原始排序下的火车车厢的编码coutendl;LinkQueueint*huan;huan=newLinkQueueint[k];Drive(main,huan,n,k);coutendl;}voidDrive(intarr[],LinkQueueinta[],intn,intk)//arr为原来的车厢数组，a为缓冲轨道的数组{inti=0;boolp=1;//做判断变量while((in)&&(p))//当还有车厢没进入缓冲轨时{p=0;for(intm=0;mk;m++){if(a[m].front-next==NULL)//某条缓冲轨空置的时候，是可以进入的{a[m].EnterQueue(arr[i]);//入队p=1;i++;break;}if(a[m].GetRear()arr[i])//如果某条缓冲轨道的第一个车厢的编号小于即将进来的车厢的编号，那么它就可以进入缓冲轨道{a[m].EnterQueue(arr[i]);//入队i++;//i加一实现了对下一个车厢的操作p=1;//重新置为北京邮电大学信息与通信工程学院第11页break;}}}if(p==0)//当无法将入