C++数据结构 大作业课程设计.docx

C+数据结构 大作业课程设计C+/数据结构 大作业/课程设计娃娃们可以收着以后用 绝对纯手工打造 内含类模块/一维指针数组 目录 校园导游咨询 程序设计源代码 及 截图 停车场管理方案一 程序设计源代码 及 截图 停车场管理方案二 程序设计源代码 及 截图 #】# (ps:该校园导游咨询系统没有输入值，所有信息是都在class MGraph的构造函数中传输的，且校园景点信息皆为】景点信息。请大家注意，直接从文章copy到visual stutio中会出现中文字符，注意删除，推荐大家在一行语句的分号后面，点出光标，按一下delete键，然后按一下enter键，完成visual stutio的自动对齐，这样程序看起来一目了然，更易于操作和更改) 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 (1)设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 (2)为来访客人提供图中任意景点相关信息的查询。 (3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一个最短的简单路径。 (6)扩充每个景点的邻接景点的方向等信息，使得路径查询结果能提供详尽的导向信息。 * #include<iostream> #include<iomanip> using namespace std; const int MaxSize=18; const int INFINITY=65535;/最大值无穷 class direction; template <class T> class MGraph; template <class T> class VertexNode/定义头结点 friend class MGraph<T> public: int vex;/顶点名称 T vexname;/顶点名称 T vexinf;/顶点信息 direction dir;/存放顶点方位信息的direction类的dir。 ; class direction public: int ln;/存放在方向图中的横坐标，表示东西 int col;/存放在方向图中的纵坐标，表示南北 ; template <class T> class MGraph/定义无向图的邻接矩阵 public: MGraph; /构造函数，初始化具有n个顶点的图 void printvexname;/显示所有景点及景点代号 void printvexinf(int i);/显示代号为i景点的名称及信息 void printroad(int i,int j);/显示景点ij的最短路径方案信息 void printdir(int i,int j);/显示景点i到j的方向信息，如“向东100m，向南200m” VertexNode<T> adjlistMaxSize; /存放景点全部信息的 景点类数组 int vertexNum,arcNum; /图的顶点数和边数 void Root(int p,int q);/递归寻找pq间的最短路径 int PathMaxSizeMaxSize,DistMaxSizeMaxSize;/创建Path和Dist分别存放两点间最短路径的前驱节点，两点间最短路径长度 int LineMaxSize;/Line存放路径 int kkk;/Line数组的标记 private: T vertexMaxSize; /存放图中顶点的数组 int arcMaxSizeMaxSize;/存放图中边的数组 ; * template <class T> MGraph<T>:MGraph/a为景点代号，b为景点名称，c为景点信息，d为景点方位信息的横坐标，e为景点方位信息的纵坐标 /s为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arc int s=0, 1,0, 0,2,0, 0,0,2,0, 0,0,2,3,0, 0,0,0,4,2,0, 0,0,0,0,2,3,0, 0,0,0,0,2,3,1,0, 0,0,2,0,2,0,0,2,0, 4,0,2,0,0,0,0,0,1,0, 0,0,0,0,0,0,0,0,0,2,0, 1,0,0,0,0,0,0,0,0,0,2,0, 0,0,0,0,0,0,0,0,0,3,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,2,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0, 0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0, 0,0,0,0,0,0,0,0,0,0,0,0,4,4,0,0,2,0; int a=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17; char* b="南门","实验楼","南图","大活","睿思楼","大礼堂", "南4教","知行楼","国交楼","南3教","南2教","南1教", "北图","北3教","北4教","北2教","北1教","北门" char* c="南校区正门","物理实验楼","南校区图书馆","大学生活动中心", "教师办公楼、医务室及留学生公寓","大礼堂，用于举办各种文艺演出","南校区第4教学楼","实习基地，计算机房等", "国际交流中心，教职工餐厅","南校区第3教学楼","南校区第2教学楼","南校区第1教学楼", "北校区图书馆","北校区第3教学楼","北校区第4教学楼","北校区第2教学楼", "北校区第1教学楼","北校区正门" int d=8,6,4,4,1,0,0,1,3,4,6,8,4,3,2,3,5,8; int e=8,8,8,10,8,10,7,6,6,6,6,6,3,1,0,0,0,2; int i,j; vertexNum=18; arcNum=30; for(i=0;i<vertexNum;i+) adjlisti.vex=ai; adjlisti.vexname=bi; adjlisti.vexinf=ci; adjlisti.dir.ln=di; adjlisti.dir.col=ei; for (i=0; i<vertexNum; i+)/初始化邻接矩阵 for (j=0; j<vertexNum; j+) arcij=arcji=s(i*(i+1)/2+j; /根据s的对称性，将一维数组中的数据赋给二维数组arc template<class T> void MGraph<T>:printvexname int i; for(i=0;i<vertexNum;i+) cout<<adjlisti.vex<<" "<<adjlisti.vexname<<endl; template<class T> void MGraph<T>:printvexinf(int i) cout<<i<<" "<<adjlisti.vexname<<":"<<adjlisti.vexinf<<endl; template<class T> void MGraph<T>:printdir(int i,int j) int dx,nb;/临时存放i与j之间的南北东西关系 j在i的哪边？ dx=adjlistj.dir.col-adjlisti.dir.col; nb=adjlistj.dir.ln-adjlisti.dir.ln; if(dx>0)/即j在i的东边 cout<<"向东"<<dx*100<<"m，" else cout<<"向西"<<dx*(0-100)<<"m，" if(nb>0)/即j在i的南边 cout<<"向南"<<nb*100<<"m" else cout<<"向北"<<nb*(0-100)<<"m" template<class T> void MGraph<T>:Root(int p,int q) if (Pathpq>0) Root(p,Pathpq); Root(Pathpq,q); else Linekkk=q; kkk+; template<class T> void MGraph<T>:printroad(int i,int j) int p,q,m,k,item1,item2; for(p=0;p<vertexNum;p+) for(q=0;q<vertexNum;q+) Distpq=arcpq;/邻接矩阵赋值 for(k=0;k<vertexNum;k+) for(p=0;p<vertexNum;p+) if (Distpk>0) for(q=0;q<vertexNum;q+) if (Distkq>0) if (Distpq>Distpk+Distkq)|(Distpq=0)&&(p!=q) Distpq=Distpk+Distkq; Pathpq=k; cout<<"n=n" cout<<"从"<<adjlisti.vexname<<"到"<<adjlistj.vexname<<"的最短路径为："<<endl; cout<<adjlisti.vexname; kkk=2; Root(i,j); item2=Line2; cout<<"->" printdir(i,item2); cout<<"->"<<adjlistitem2.vexname; for(m=3;m<=kkk-1;m+) item1=Linem; cout<<"->" printdir(item1-1,item1); cout<<"->"<<adjlistitem1.vexname; cout<<endl; cout<<"n=n" * int funcchoice/系统功能选择页面 int choice; cout<<"="<<endl; cout<<" 欢迎进入校园导游咨询平台"<<endl; cout<<" 1-显示校园所有景点信息"<<endl; cout<<" 2-查询校园景点信息"<<endl; cout<<" 3-问路查询系统"<<endl; cout<<" 4-退出导游资讯平台"<<endl; cout<<"="<<endl; cout<<"请输入要选择的功能号：" cin>>choice; return choice; void main MGraph<char*> mg; int funcchoice; int fc; while(1) fc=funcchoice; if(fc=1) int i; for(i=0;i<mg.vertexNum;i+) mg.printvexinf(i); else if(fc=2) int i; mg.printvexname; cout<<endl<<"请输入所要查询景点代号：" cin>>i; mg.printvexinf(i); else if(fc=3) int i,j; mg.printvexname; cout<<"请输入两景点代号：" cin>>i>>j; mg.printroad(i,j); else if(fc=4) break; else cout<<"输入有误，请重新输入！"<<endl; 运行测试图 #】# 设停车场是一个可停放n辆汽车的 长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列，若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用。栈以顺序结构实现，队列以链表结构实现。 设n=2，输入数据为：(A，1，5)，。其中：A表示到达；D表示离去；E表示输入结束。 * #include<iostream> using namespace std; const int Max=2;/车库最大容量 const double price=30;/每小时的费用 /思想： /我的系统界面，输入信息为：；车牌号；时刻 /因此，我的停车场类分成车辆到达和车辆离开两个主要的函数实现。 /车辆到达，有入栈和入队。车辆离开有出栈，出队和入栈操作。 /因此我又编写入栈的类，队的类。与parkingmanagement进行友元。 /*类定义* class car/车的信息类 public: double time;/计费时间 int number;/车牌号 car *next;/存放car类型元素的数组初始地址 ; class carstack/栈的类 friend class parkingmanagement;/parkingmanagement能访问carstack类中所有成员 public: carstack;/构造函数，栈的初始化 int empty;/判断栈是否为空 int full;/判断栈是否为满 car *s;/存放car类型栈元素的数组初始地址 int top;/栈顶指针 ; class carqueue/队列的类 friend class parkingmanagement;/parkingmanagement能访问carstack类中所有成员 public: carqueue;/构造函数，队列的初始化 int full;/判断队列是否为满 car *front,*rear;/存放car类型队列元素的数组初始地址 ; class parkingmanagement public: int pushstack(carstack &cs,int cnum,double ctime);/入栈,cs栈内进行调整，返回栈内位置 void popstack(carstack &cs,int cnum);/出栈，cs栈内进行调整， /根据车牌号把车弹出栈,将出栈car的number赋值给int popstacknumber /将出栈car的time赋值给double popstacktime，无返回值！ int pushqueue(carqueue &cq,int cnum,double ctime);/入队,队内进行调整，返回队内位置 int popqueue(carqueue &cq);/出队,队内进行调整，返回汽车车牌号 void arrival(carstack &cs,carqueue &cq,int cnum,double ctime);/车辆到达， /根据输入的车牌号、到达时间，变更函数参数；并cout车位信息 void leave(carstack &cs,carqueue &cq,int cnum,double ctime);/车辆离开， /根据输入的车牌号找到汽车，并进行出栈操作、出队操作和入栈操作； /并cout停留时间和收费情况 void deletequeue(carqueue &cq,int i);/删除cq过道中第i辆车 int popstacknumber;/专门存放出栈的时候返回的车牌号 double popstacktime;/专门存放出栈的时候返回的时刻 ; * carstack:carstack/构造函数，栈的初始化 top=-1; s=new carMax;/创建car类型栈元素的数组 if(s=NULL) cout<<"栈空间分配不成功！"<<endl; exit(1); int carstack:full/判断栈是否为满 return top=Max-1; carqueue:carqueue/构造函数，队列的初始化 rear=front=NULL; int parkingmanagement:pushstack(carstack &cs,int cnum,double ctime)/入栈,cs栈内进行调整，返回栈内位置 if(cs.top=Max-1)/Max从1开始，top从0开始 cout<<"停车场已满！"<<endl; return Max; else cs.top+; (cs.scs.top).number=cnum;/将cnum赋给栈顶位置的车的车牌号，s是car类型栈元素的数组 (cs.scs.top).time=ctime;/将ctime赋给栈顶位置的车的入栈时间，s是car类型栈元素的数组 return (cs.top+1);/返回栈内位置加1，即停车场内车位从1号开始 void parkingmanagement:popstack(carstack &cs,int cnum)/出栈，cs栈内进行调整， /根据车牌号把车弹出栈,将出栈car的number赋值给int popstacknumber /将出栈car的time赋值给double popstacktime，无返回值！ int i; car p; carstack stemp;/定义一个carstack类型的临时存放出栈元素的栈 for(i=0; i<=cs.top; i+) if(cs.si).number=cnum) break;/当要出栈的车的车牌号=栈内的车牌号元素时，跳出循环 p=cs.si;/将要出栈的元素赋给car类型的p存放 while(cs.top>i) stemp.s+(stemp.top)=cs.s(cs.top)-;/出栈的元素数组逐个赋给临时栈 popstacknumber=p.number;/将这个车牌号信息传给int popstacknumber popstacktime=p.time;/将该车的时间信息传给double popstacktime cs.top-;/栈顶指针回到原来位置 while(stemp.top>=0) cs.s+(cs.top)=stemp.s(stemp.top)-;/临时栈出栈的元素逐个赋给原栈，完成先退再进的工作 int parkingmanagement:pushqueue(carqueue &cq,int cnum,double ctime)/入队,队内进行调整，返回队内位置 car *p,*countp; int count(1);/count用于记录车在过道上的位置信息，因队列为链式的，所以进行循环累加 p=new car;/创建一个car类型的指针 p->number=cnum; p->time=ctime; p->next=NULL;/首先将指向存放car类型元素的数组初始地址置空 if (cq.front=NULL)/第一次入队要判断头结点是否为空 cq.front=cq.rear=p; else /尾插法插入元素 p->next=(cq.rear)->next; (cq.rear)->next=p; cq.rear=(cq.rear)->next; countp=(cq.front)->next; while(countp!=NULL) count+; countp=countp->next; /count即车在过道上的位置， return count; int parkingmanagement:popqueue(carqueue &cq)/出队,队内进行调整，返回汽车车牌号 car p; p.number=(cq.front)->next)->number;/cq队里，从cq.front开始指向下一个元素的车牌号赋给car类型的车信息 p.time=(cq.front)->next)->time;/cq队里，从cq.front开始指向下一个元素的时刻 /赋给car类型的车信息 p.next=(cq.front)->next)->next;/cq队里，从cq.front开始指向下一个元素的指针 /赋给car类型的车信息的下一个元素的指针 return p.number; cq.front=(cq.front)->next; void parkingmanagement:arrival(carstack &cs,carqueue &cq,int cnum,double ctime) /车辆到达，根据输入的车牌号、到达时间，变更函数参数；并cout车位信息 int pos; if(!(cs.full)/如果栈未满，车辆停入停车场 int fl(0),i;/定义一个从0开始的标记fl for(i=0;i<=cs.top;i+) if(cs.si.number=cnum)/如果到达的车的车牌号=栈内已有车辆的车牌号 fl=1;/fl记1 break; if(fl=1)/如果到达的车的车牌号!=栈内已有车辆的车牌号 cout<<"输入错误！请重新输入！"<<endl; else pos=pushstack(cs,cnum,ctime);/入栈，返回车位信息 cout<<"该停车场还有空位，请到"<<pos<<"号车位进行泊车"<<endl; cout<<endl; else/如果栈满，车辆暂停便道 pos=pushqueue(cq,cnum,ctime);/入队，返回车位信息 cout<<"该停车场已满，请将车停到便道"<<pos<<"号车位上"<<endl; cout<<endl; void parkingmanagement:leave(carstack &cs,carqueue &cq,int cnum,double ctime) /车辆离开，根据输入的车牌号找到汽车，并进行出栈操作、出队操作和入栈操作；并cout停留时间和收费情况 int i,flag(0),pstack,count(1),outcarnum; double hour; car *p; for(i=0;i<=cs.top;i+) if(cs.si).number=cnum) flag=1; break; if(flag)/如果输入的车牌号与栈内已有车辆的车牌号一致 popstack(cs,cnum);/出栈操作 hour=ctime-popstacktime;/时间计算 outcarnum=popqueue(cq);/将便道上的第一辆车出队，入栈。并将其车牌号赋给outcarnum pstack=pushstack(cs,outcarnum,ctime);/将便道上的第一辆车，入栈 cout<<"该车在本停车场内停留时间为"<<hour<<"分钟，应付金额"<<hour*(price/60)<<"元！"<<endl; else/如果输入的车牌号与队列里已有车辆的车牌号一致 p=cq.front; while(p!=NULL) count+;/如果在过道中找到该车，则该车的位置为过道中的第count位置 p=p->next; if(p->number=cnum)/在过道中找到要出去的车，则在队列中删除该car。 /后面的车辆依然顺序排列，补足空位 deletequeue(cq,count); if(count>Max) cout<<"您的车在便道上的位置为"<<count<<"号车位，请自行驶离，无需付费！"<<endl; break; if(p=NULL) cout<<"您的车不在本停车场内，或输入有误，请重新输入！"<<endl; void parkingmanagement:deletequeue(carqueue &cq,int i) car *p,*q; int j(0); p=cq.front; while(p && j<i-1) p=p->next; j+; /找到第i个节点(i从1开始) if(!p | !p->next) cout<<"i不合法" else q=p->next; p->next=q->next; delete q; * void print cout<<"= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ="<<endl; cout<<"= 欢迎光临！ ="<<endl; cout<<"= ="<<endl; cout<<"= 本停车场收费标准为：30元/小时；车库容量为：2 ="<<endl; cout<<"= ="<<endl; cout<<"= 请输入您的泊车信息：格式为：；车牌号；现在时刻 ="<<endl; cout<<"= 其中，A：到达；D：离去；E：退出系统 ="<<endl; cout<<"= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ="<<endl; /*调试程序*设n=2，输入数据为：(A，1，5)，* /*，* /*，。* /*其中：A表示到达；D表示离去；E表示输入结束。* void main char acc; int carnum; double cartime; parkingmanagement park; carstack cars; carqueue carq; while(1) print; cin>>acc>>carnum>>cartime; if(acc='A') park.arrival(cars,carq,carnum,cartime); else if(acc='D') park.leave(cars,carq,carnum,cartime); else if(acc='E') break; else cout<<"您的输入有误，请重新输入！"<<endl; #】# * #include <iostream> using namespace std; const int MaxSize=2;/停车场内最多能停2辆车 template<class T> class carStack;/ template <class T> /定义模板类 struct Node/过道停车的队列所需链式结点 T carnum;/定义车牌号类型 Node<T> *next; /此处<T>也可以省略 ; template<class T> class carinfo friend class carStack; public: T carnum; /车号 int cartime;/停车时间 ; template <class T> class carQueue friend class carStack; public: carQueue; /构造函数，初始化一个空的链队列 int EnQueue(T cnum); /将元素x入队,并返回其在队内的位置 T DeQueue; /将队头链式结点出队,并返回汽车车牌号 void deletequeue(int i);/将队内低i个元素删除，即便道上i位置的汽车驶离 bool Empty; /判断链队列是否为空 Node<T> *front, *rear; ; template<class T> class carStack friend class carinfo; public: carStack ; /构造函数，栈的初始化,停车场容量为 void Pushcar(T cnum,int ctime); /有车停入停车场 int Popcar(T outcnum,int outctime); /将第cnum辆车出栈，并返回其停车时间 bool full;/判断栈是否为满？满则返回1 carinfo<T> *S;/? int top; ; * template <class T>/初始化队列 carQueue<T>:carQueue front=rear=NULL; template <class T> int carQueue<T>:EnQueue(T cnum)/车子进入便道 int i(0); Node<T> *s,*p;/？ s=new Node<T> s->carnum=cnum; s->next=NULL; if(front=NULL)/空队列，】关键是！front指向第一个结点 front=rear=s; else rear->next=s;/将结点s插入到队尾 rear=s; p=front; while(p!=NULL) i+; p=p->next; /i即车在过道上的位置， return i; template<class T> T carQueue<T>:DeQueue Node <T> *p; if (front=NULL) cout<<"便道上没车" else p=front; front=front->next;/将队头元素所在结点摘链 return p->carnum; delete p;/将出队进栈的车从队列里删除 template<class T> bool carQueue<T>:Empty/判断是否为空，为空则返回1，不为空则返回0 return front=NULL; template <class T> carStack<T>:carStack/构造栈算法 :top(-1) /建立一个最大尺寸为size的空栈 S=new carinfo<T>MaxSize;/创建存储栈的数组 if(S=NULL) /分配不成功 cerr<<"动态存储失败！"<<endl; exit(1); /stdlib.h template<class T> void carStack<T>:Pushcar(T cnum,int ctime) if (top=MaxSize-1) cout<<"车场内已停满汽车" els