第一篇：C++ 数据结构 课程设计报告 计算表达式
题目：计算表达式的值
1、问题描述
对于给定的一个表达式，表达式中可以包括常数、算术运行符（“+”、“-”、“*”、“/”）和括号，编写程序计算表达式的值。
基本要求：从键盘输入一个正确的中缀表达式，将中缀表达式转换为对应的后缀表达式，计算后缀表达式的值。
提高要求：（1）对于表达式中的简单错误，能够给出提示；
（2）不仅提示错误，也能给出错误信息（3）表达式中可以包括单个字母表示的变量（4）能够处理多种操作符（5）实现包含简单运算的计算器
（6）实现一个包含简单运算和函数运算的计算器。
2．需求分析
软件的基本功能：由键盘输入中缀表达式，程序可以将输入的中缀表达式转换成对应的后缀表达式，并计算后缀表达式的值。对于在输入时发生的简单错误，程序可以给出提示。本程序支持整数、小数、多种操作数的处理，可以计算含加、减、乘、除、运算符的表达式，并能判断表达式括号是否匹配。输入/输出形式：用户可以通过控制台，根据输入提示。输入形式：
①正确的不含字母变量的中缀表达式； ②含有简单错误的中缀表达式。
输出形式：
①对于正确的中缀表达式，可以输出其转化后的后缀表达式及表达式的计算结果；
②对于含有简单错误的中缀表达式，程序将自动输出错误提示，并给出错误信息。
测试数据要求：用户可以输入一个符合要求的中缀表达式，也可以输入一个包含简单错误的表达式。表达式中可以包括各种类型的常数以及小数等，操作符包括（+、-、*、/），同时表达式还可以包括各种括号。
3．概要设计
（1）抽象数据类型：
根据题目的要求，考虑用栈类型比较适合。ADT SeqStack Data 栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系 Operation SeqStack 前置条件：栈不存在
输入：无
功能：栈的初始化
输出：无
后置条件：构造一个空栈 ~ SeqStack 前置条件：栈已存在输入：无
功能：销毁栈 输出：无
后置条件：释放栈所占用的存储空间
Push 前置条件：栈已存在
输入：元素值x 功能：在栈顶插入一个元素x 输出：如果插入不成功，抛出异常
后置条件：如果插入成功，栈顶增加了一个元素 Pop 前置条件：栈已存在输入：无
功能：删除栈顶元素
输出：如果删除成功，返回被删元素值，否则，抛出异常
后置条件：如果删除成功，栈顶减少了一个元素 GetTop 前置条件：栈已存在
输入：无
功能：读取当前的栈顶元素
输出：若栈不空，返回当前的栈顶元素值 后置条件：栈不变
Empty 前置条件：栈已存在输入：无
功能：判断栈是否为空
输出：如果栈为空，返回1；否则，返回0 后置条件：栈不变
End ADT 4．详细设计
（1）实现概要设计的数据类型：
采用顺序栈
const int StackSize = 50;template
~SeqStack();//析构函数
void Push(T x);//将元素x入栈
DataType Pop();
//将栈顶元素弹出
DataType GetTop();//取栈顶元素（并不删除）
int Empty();//判断栈是否为空
private:
DataType data[StackSize];//存放栈元素的数组
int top;//栈顶元素 };（2）主程序以及其它模块的算法描述：
这个函数主要调用了实现功能的各个函数。其步骤为：在用户没有选择退出时，先调用输入函数，输入中缀表达式；然后调用判断表达式，如果中缀表达式错误，则根据返回的值来输出错误提示，不再往下运算；如果中缀表达式正确，则将中缀表达式转换为后缀表达式，然后输出中缀表达式和转换后的后缀表达式；接着，再调用计算函数，计算后缀表达式的结果输出。最后是清屏函数。直至用户选择退出。
5、编码与调试分析
编码与调试过程中遇到的问题及解决办法：
【问题1】程序在判断表达式输入形式有误时，考虑情况不周全。解决办法：尽可能多的将表达式有误的情况考虑在内。以下为现已考虑到并解决的问题：①表达式中出现非数字或非运算符的其他字符； ②表达式中括号不匹配。
【问题2】给变量赋值时出现重定义问题。
解决办法：在定义暂存栈顶元素的变量t时，应该在函数外面定义，在函数里面给变量赋值时不能定义。【问题3】无法处理多位数和小数。
解决办法：在连续的操作数结束之后插入空格到后缀表达式中，以分隔操作数。
解决此问题的核心代码： int i,t=0;float sum=0;for(i=0;i if(a[i]=='.'){ } } t=i;break;if(t!=0){ } else { } return sum; 2.待解决问题： for(i=0;i } i++;for(;i } sum=(a[i]-'0')*pow(0.1,i-t)+sum;if(a[i]=='.')break;sum=(a[i]-'0')*pow(10,n-(n-t)-1-i)+sum;for(i=0;i 6、使用说明 进入菜单，根据提示进行选择。 7、测试结果 （1）含小数、多位数及括号的表达式显示结果： 8、自学知识 在课程设计过程中，特别是在代码编写和调试的过程中，自学了很多新的知识。例如atof()函数，包含于表头文件 #include 自学MFC。还有一个知识点是清屏函数，它也是包含于 9、课程设计心得体会 通过这次课程设计，增强了我的自信心。因为在这次课程设计中，我遇到了一些问题，但是都逐个得解决了，虽然有些问题请教了同学，但是从中学了很多东西，也学到了一些处理问题的方法。在能力上得到了一些提升。同时也养成了独立思考问题，以及和同学一起探索问题的良好习惯。当然，在课程设计过程中，有些细节的处理还是不够完美，需要完善的地方还有很多，还需要继续努力，尽量将程序完善。 在编写程序过程中，得到了部分同学的帮助，如：数据间的分隔问题，得到了***同学的帮助，将中缀表达式转换为后缀表达式的算法思想参考了《数据结构课程设计》（机械工业出版社），然后根据自己的理解，完成基本算法和细节处理，最后完成了转换函数的代码编写。 在将字符串转换为浮点型数字进行运算的思想主要参考了《程序设计引导及在线实践》这本书里面的一道程序，然后加以灵活运用，转换为自己的代码。当然，为此也掌握了一些新的知识。 清屏函数是在百度百科上获取的知识，也属于自学的新知识。 参考书 [1]《c++面向对象程序设计》 清华大学出版社 谭浩强著 [2]《数据结构（C++版）》清华大学出版社 王红梅、胡明、王涛著 C++/数据结构 大作业/课程设计——【校园导游咨询】【停车场管理】娃娃们可以收着以后用 绝对纯手工打造 内含类模块/一维指针数组（谨以此程序供大家参考。运行结果后面有贴图） 目录 【1】校园导游咨询 程序设计源代码 及 截图 【2】停车场管理——方案一 程序设计源代码 及 截图 【3】停车场管理——方案二 程序设计源代码 及 截图 【1】【【校园导游咨询】】 ###### (ps:该校园导游咨询系统没有输入值，所有信息是都在class MGraph的构造函数中传输的，且校园景点信息皆为【【上海电力学院】】景点信息。请大家注意，直接从文章copy到visual stutio中会出现中文字符，注意删除，推荐大家在一行语句的分号后面，点出光标，按一下delete键，然后按一下enter键，完成visual stutio的自动对齐，这样程序看起来一目了然，更易于操作和更改)【问题描述】 设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】 (1)设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。(2)为来访客人提供图中任意景点相关信息的查询。 (3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一个最短的简单路径。【选作内容】 (6)扩充每个景点的邻接景点的方向等信息，使得路径查询结果能提供详尽的导向信息。**************************【以下为类的定义】******************************** #include class direction;template { friend class MGraph direction dir;//存放顶点方位信息的direction类的dir。}; class direction { public: int ln;//存放在方向图中的横坐标，表示东西 int col;//存放在方向图中的纵坐标，表示南北 };template { public: MGraph(); //构造函数，初始化具有n个顶点的图 void printvexname();//显示所有景点及景点代号 void printvexinf(int i);//显示代号为i景点的名称及信息 void printroad(int i,int j);//显示景点i~j的最短路径方案信息 void printdir(int i,int j);//显示景点i到j的方向信息，如“向东100m，向南200m” VertexNode void Root(int p,int q);//递归寻找pq间的最短路径 int Path[MaxSize][MaxSize],Dist[MaxSize][MaxSize];//创建Path和Dist分别存放两点间最短路径的前驱节点，两点间最短路径长度 int Line[MaxSize];//Line存放路径 int kkk;//Line[]数组的标记 private: T vertex[MaxSize];//存放图中顶点的数组 int arc[MaxSize][MaxSize];//存放图中边的数组 };*************************【以下为类的实现 即类函数的定义】*********************************** template //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 for(j=0;j template cout<<“向东”< cout<<“向南”< if(Path[p][q]>0){ Root(p,Path[p][q]);Root(Path[p][q],q);} else { Line[kkk]=q;kkk++;} } template for(q=0;q Dist[p][q]=Dist[p][k]+Dist[k][q];Path[p][q]=k;} cout<<“n=======n”;cout<<“从”< { int choice;cout<<“================”< 【2】【停车场管理系统【方案一 程序】】 ###### （ps：该程序有漏洞，若将要离开的车辆是停于便道上的，则对该车进行驶离操作时程序内部有错误数据，虽然做了函数完成这一功能，但因时间有限，没能及时查找更正，现在懒得改了。。大家将就看吧。不过运行是可以的）【问题描述】 设停车场是一个可停放n辆汽车的 长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。【测试数据】 设n=2，输入数据为：(A，1，5)，（A，2，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到达（Arrival）；D表示离去（Departure）；E表示输入结束（End）。**************************【以下为类的定义】************************************* #include 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 car[Max];//创建car类型栈元素的数组 if(s==NULL){ cout<<“栈空间分配不成功！”< cs.top++;(cs.s[cs.top]).number=cnum;//将cnum赋给栈顶位置的车的车牌号，s是car类型栈元素的数组(cs.s[cs.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.s[i]).number==cnum)break;//当要出栈的车的车牌号=栈内的车牌号元素时，跳出循环 p=cs.s[i];//将要出栈的元素赋给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即车在过道上的位置，【从1开始计！！】 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.s[i].number==cnum)//如果到达的车的车牌号=栈内已有车辆的车牌号 { fl=1;//fl记1 break;} } if(fl==1)//如果到达的车的车牌号!=栈内已有车辆的车牌号 cout<<“输入错误！请重新输入！”< cout<<“该停车场还有空位，请到”< { pos=pushqueue(cq,cnum,ctime);//入队，返回车位信息 cout<<“该停车场已满，请将车停到便道”< { popstack(cs,cnum);//出栈操作 hour=ctime-popstacktime;//时间计算 outcarnum=popqueue(cq);//将便道上的第一辆车出队，入栈。并将其车牌号赋给outcarnum pstack=pushstack(cs,outcarnum,ctime);//将便道上的第一辆车，入栈 cout<<“该车在本停车场内停留时间为”< { p=cq.front;while(p!=NULL){ count++;//如果在过道中找到该车，则该车的位置为过道中的第count位置（count从1开始）p=p->next;if(p->number==cnum)//在过道中找到要出去的车，则在队列中删除该car。//后面的车辆依然顺序排列，补足空位 { deletequeue(cq,count);if(count>Max){ cout<<“您的车在便道上的位置为”< car *p,*q;int j(0);p=cq.front;while(p && j ######【3】【停车场管理系统【方案二 程序】】 （ps：本方案与方案一有同样的问题，就是在对 便道上的车 进行驶离操作时，数据错误，同样的理由，没有改正。如果有细心娃娃帮忙指点改正，在此感激啦~） *************************【以下为类定义】************************************ #include struct Node//过道停车的队列所需链式结点 { T carnum;//定义车牌号类型 Node friend class carStack;public: T carnum;//车号 int cartime;//停车时间 }; template int EnQueue(T cnum);//将元素x入队,并返回其在队内的位置（从1开始）T DeQueue();//将队头链式结点出队,并返回汽车车牌号 void deletequeue(int i);//将队内低i个元素删除，即便道上i位置的汽车驶离 bool Empty();//判断链队列是否为空 Node int Popcar(T outcnum,int outctime);//将第cnum辆车出栈，并返回其停车时间（hour）bool full();//判断栈是否为满？满则返回1 carinfo s=new Node front=rear=s;} else { rear->next=s;//将结点s插入到队尾 rear=s;} p=front;while(p!=NULL){ i++;p=p->next;}//i即车在过道上的位置，【从1开始计！！】 return i;} template front=front->next;//将队头元素所在结点摘链 } return p->carnum;delete p;//将出队进栈的车从队列里删除 } template template :top(-1){//建立一个最大尺寸为size的空栈 S=new carinfo { cerr<<“动态存储失败！”< template template void outputpark()//系统功能选择页面，输入泊车信息 { cout<<“========================”< { cs.Pushcar(carnum,cartime);cout<<“请驶入停车场的”< Node C++课程设计报告 一、题目名称：矩阵乘法计算 二、难易等级： A级 三、对题目的分析和注释： 分析： 依次建立两个矩阵空间并按照矩阵乘法规则进行运算。（矩阵的乘法规则： 1、矩阵的乘法运算必须符合m*n的矩阵与n*s的矩阵相乘。 2、第一个矩阵的第i行的元素依次乘以第二个矩阵的第j列元素后结果相加组成生成矩阵第i行第j列元素。） 注释： （1）设计一个矩阵类，将相应的函数和数据封装在类中，简化程序。 （2）修改程序结构，使程序可以反复执行，直至按键选择退出为止。 （3）本程序用数组表示5*5矩阵，将其改为根据输入矩阵的大小动态分配空间[m][n]来放置数据，其中m，n为用户可输入的任意整数。 （4）增加类的构造函数和成员函数，使得矩阵数据既可以用在对象初始化时赋值，也可以通过键盘赋值，还可以通过读取数据文件输入。 （5）用模板的形式改写矩阵数据类型，使得矩阵中的数据既可以是整型数据，也可以是浮点型数据，执行程序时，分别定义两个整型矩阵和两个浮点型矩阵进行乘法验证。 （6）完成矩阵的乘法运算，在运算之前判断这两个矩阵能否满足乘法运算的条件，若不满足，则给出提示信息。 四、所增加功能模块的设计 如果要说增加功能的话，自己编的程序里面不多，我只是按照题目要求，设计了一个矩阵类，同时用模板的形式改写矩阵数据类型和运算符的重载。 1、模板的使用 我使用了大量的模板，以T为模板参数，通过对T的不同类型的选择实现相应的运算处理。其中choose1（）函数本是无参函数，为了方便模板化，给其赋以伪参数T，在执行时通过T的取值生成相应的函数模板。 template switch(sjlx){ case 1: { choose1(1); }break; case 2: { choose1(0.0); }break; case 3: { choose1(1e-10); }break; default:cout<<“输入选择错误！!”< 2、矩阵类的构造 按照课本要求采用二级指针动态开辟内存空间，节省内存使用； 其中数据结构如下： Mat-->Mat[0]----->Mat[0][0] Mat[0][1] ……Mat[0][j] Mat[1]----->Mat[1][0] Mat[1][1] ……Mat[1][j] : : Mat[i]----->Mat[i][0] Mat[i][1] ……Mat[i][j] 实现构造的代码为： template Mat[i]=new T[nCol];} cout<<“请输入数据:n”;for(i=0;i for(j=0;j { cout<<“第[”< cin>>Mat[i][j]; } } 3、运算符的重载 要实现矩阵间的乘法运算，有必要对其运算符进行重载。而乘法运算符又要针对不同数据类型进行运算，所以我对运算符重载函数模板化。template mat3.Mat[i][j]=0; for(int k=0;k mat3.Mat[i][j]+=mat1.Mat[i][k]*mat2.Mat[k][j];} return mat3;} 五、设计中遇到的主要问题及解决办法 1、无法实现文件输入 主要原因是输入之前调用的是默认构造函数，只是简单赋值，并未开辟内存空间，后来调用带参构造函数就可以正常输入数据； 2、重载乘法运算的函数无法重载 经检查发现，由于重载的是友元函数，函数不存在this指针，因此必须显式地调用两个相乘的矩阵类。 六、设计中尚存的不足 1、功能还不够强大，只能做简单的矩阵乘法，我所期望的是能够做各种混合运算，具有强大处理功能的实用程序，希望在以后的深入学习中可以改进。 2、关于异常处理这方面，我觉得处理功能也不是很行，觉得还是应该建立全面的异常检测与异常处理机制。 七、对设计的感想和心得体会 经过这几周的上机编程，我体会颇多，学到了很多东西。我加强了对C++程序设计这门课程的认识，并且复习了自己上学期学习到的知识。这些都使我对计算机语言的学习有了更深入的认识。总之，通过这这几周的上机编程，我收获颇丰，相信会为自己以后的学习和工作带来很大的好处。像矩阵乘法计算问题这样的程序设计，经历了平时在课堂和考试中不会出现的问题和考验。而这些问题，这并不是我们平时只靠课本，就可以轻易解决的。所以，锻炼了我们挑战难题，学会用已掌握的知识去解决具体问题的能力，进一步培养了独立思考问题和解决问题的能力。当然，老师的指导和同学的帮助也是不可忽视的，他们给了我许多提示和帮助，教会了我编译复杂程序的方法。 实践出真知，做课程设计前，我的C++知识只是停留在理论水平，而且就算理论水平，也存在很多漏洞。有时，在做课题的时候，理论的漏洞冒了出来，我就只能在看着课本慢慢的再学习一遍，但有些东西还是没有搞懂，所以现在就又翻出课本，看着课本编程，也算是将旧的东西复习了一遍。同时，有的概念在编程过程中印象更加深刻。 成功=勤奋+合作。在课程设计这方面自己也花了好多时间，交流与合作在编程过程中给我很大的帮助，我得到了很多，每次看到解问题后大家的愉悦，我想大家应该与我一样收获很大吧。说真的，我挺喜欢这种讨论的氛围，它也让编程过程变得趣味横生，不再只是呆滞的盯着屏幕写程序。 对凡事都应当有毅力，不要中途放弃。在编程过程中，好几次遇到困难我都想再换一个别的程序或找同学拷一个程序，但我最终还是坚持下来了。永不言弃，你就一定会成功的。 磨刀不误砍柴工。在刚拿到任务时，书上的关键代码我也是看的一头雾水，后来我将上学期的课本认真研读一遍之后，感觉收获真的不少，接着编起程来就顺手好多了。 此次程序设计使我透彻地领悟到面向对象的程序设计的优点和强大生命力，特别是类和模板的使用，使程序的兼容性和扩展能力都大大加强，比如我们想要再做一个处理其他类型数据的矩阵的乘法计算，只需要添加一个相应的类型声明就可以利用模板迅速构造出来。 通过课程设计的训练，我进一步学习和掌握了对程序的设计和编写，从中体会到了面向对象程序设计的方便和巧妙。懂得了在进行编写一个程序之前，要有明确的目标和整体的设计思想。另外某些具体的细节内容也是相当的重要。这些宝贵的编程思想和从中摸索到的经验都是在编程的过程中获得的宝贵财富。这些经验对我以后的编程会有很大的帮助的，我要好好利用。 这次矩阵乘法计算问题课程设计让我充分认识到了自己的不足，认识到了动手能力的重要性。我会在以后的学习中更加努力锻炼自己，提高自己，让自己写出更好更完善的程序，为以后的编程打好基础！ 数据结构课程设计 散列表的应用:插队买票 专业 计算机科学与技术（网络技术） 金玲 计算机131 1310704114 张静林 2015年1月23日 学生姓名 班学级 号 指导教师 完成日期 目录概述……………………………………………………………………………………1 1.1 课程设计目的……………………………………………………………………….1 1.2 课程设计内容……………………………………………………………………….1 2 系统需求分析……………………………………………………………………….1 2.1 主体功能…………………………………………………………………………....2 3系统概要设计…………………………………………………………………………2 3.1 系统流程图………………………………………………………………………….2 4 系统详细设计…………………………………………………………………………3 5 测试……………………………………………………………………………………5 5.1 测试方案…………………………………………………………………………….5 5.2 测试结果…………………………………………………………………………….5 6 小结……………………………………………………………………………………5 参考文献…………………………………………………………………………………5 附录………………………………………………………………………………………7 附录1 源程序清单……………………………………………………………………...7 概述 1.1 课程设计目的 数据结构课程设计是为数据结构课程独立开设的实践性教学环节。数据结构课程设计对于巩固数据结构知识，加强学生的实际动手能力和提高学生综合素质是十分必要的。课程设计的目的： 1．要求学生达到熟练掌握C语言的基本知识和技能。 2．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。3．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 4．培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。 5．初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。 1.2课程设计内容 本课程设计的任务是写一个程序模拟这种情况。每个队伍都允许插队。如果你在排队，有一个以上的朋友要求插队，则你可以安排他们的次序。每次一个人入队，并且如果这个入队的人发现队伍中有自己的朋友，则可以插入到这个朋友的后面；当队伍中的朋友不止一个的时候，这个人会排在最后一个朋友的后面；如果队伍中没有朋友，则他只能够排在这个队伍的最后面。每一个入队的人都先进行上述的判断。当队伍前面的人买到车票之后，依次出队。系统需求分析 2.1 主体功能 程序从“input.txt”文件读入测试用例，一个文件可包含多个测试用例。每个用例的第一行是朋友组的数目n（1<=n<=1000)。对于一个朋友组以朋友的数目j（1<=j<=1000）开始，由朋友的个数以及他们的名字组成，一个空格后接该组朋友的名字，以空格分开，并且每个人的名字都不同。每个名字不超过四个字母，由{A，B，...，Z，a，b，...，z}组成。一个朋友组最多有1000个人，每个人只属于一个朋友组。n=0时，测试数据结束。 下面是一些具体命令：.ENQUEUE——X入队;.DEQUEUE——排队头的人买票，离开队伍，即出队；.STOP——一个测试用例结束。 测试结果输出到“output.txt”文件中。每个测试用例第一行输出“Scenario#k”，k是测试用例的序号（从1开始）。对每一个出队命令，输出刚买票离开队伍的人名。两个测试试用例 之间隔一空行，最后一个用例结束不输出空行。系统概要设计 3.1 系统流程图 系统详细设计 本题目主要解决两个问题：一是怎么存放和查找大量数据（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。 用散列表来存放和查找数据。由于最多有1000个朋友组，每组最多有1000人，使用平方探测法解决冲突，则表的大小是2*（1000*1000），所以选择TableSize=2000003（2000003是大于2000000的最小素数）。同一个组内的都是朋友，所以每个人除了记录他的名字name，还要记录他属于哪个组group，另外用info来表示该单元是否被占用，数据结构如图4.1所示。散列函数是根据Honer法则计算一个以64为阶的多项式，如图4.2所示。冲突解决方法采用平方探测法，如图4.3所示。 #define TabSize 2000003 typedef struct hashtab *PtrToHash;struct hashtab /*散列表数据结构*/ { char name[5]; /*名字*/ int group; /*属于哪个朋友组*/ char info; /*标志位，该单元是否被占用*/ };图4.1数据结构：散列表 Int Hash(char *key,int TableSize){ Int HashVal=0; While(key!=NULL) HashVal=(HashVal<<6)+*key; Return HashVal%TableSize;} 图4.2散列函数 Long int Find(PtrToHash hash,char *c){ key=c; CurrentPos=Hash(key,TableSize); CollisionNum=0; While((单元被占用)and(单元内的名字与查找的名字不同)) { CurrentPos+=2*(++CollisionNum)-1; If(CurrentPos>=TabSize) CurrentPos=TabSize; } Return CurrentPos;} 图4.3用平方探测法解决冲突 第二个问题是关于怎么操作“ENQUEUE”和“DEQUEUE”命令。这可以用队列来模拟。由于有插队现象的存在，不能单纯的用一个数组来表示队列，因为这样的话，插入一个朋友，则他后面的人都要往后移一个单位，删除一个人，则他后面的人都要前移一个，会降低效率。所以，采用一个Index标记来表示当前元素的后继元素，最后一个单元的后继元素是第0个，形成环，数据结构如图4.4所示。不用链表是因为链表存放指针也需要空间，并且链表插入、删除的效率没有数组高。 typedef struct Que *PtrToQue;struct Que /*队列数据结构*/ { long int HashVal; /*散列值*/ long int Index; /*在中的队列序号*/ };图4.4数据结构：队列 输入ENQUEUE命令，如果队伍里有朋友，则排在朋友后面；如果没有朋友，则排在队尾。入队时，用一个数组记录每个朋友组的最后一位，以便下一个朋友到来时排到他后面，这个数组被称为“插队数组”。 输入DEQUEUE命令，则根据“先进先出”，按照各个元素和它后继元素的先后顺序，每次删除队列重的第一个。程序结构如图4.5所示。 While(读测试文件){ if(输入”ENQUEUE”) { 读入名字； 插入散列表； 插入队列； } else if(输入”DEQUEUE”) { 删除队列第一个名字； 将该名字输出到文件； } else stop;} 图4.5入队、出队操作 测试 5.1 测试方案 按输入要求输入正常测试数据，测试程序是否能正确解决问题，得到正确答案。应注意边界测试。例如，将n，j分别取为1的用例和n为1000的用例。n，j比较大时需写程序生成测试用例。 不按输入要求输入数据，测试程序能否对输入内容进行数据合法性检测并进行相应的异常处理。例如，将n或j取为小于1或大于1000的数，名字超过4个字母等情况下的测试用例。5.2 测试结果 小结 在前面的学习过程中我们学到了很多知识而这次课程设计又是对我们所学的 一次总结，刚开始，可以说是没有头绪，于是就去图书馆找资料，找到了一些关于程序方面的，可这远远不够，这只是小小的开始。我们必须掌握很多已学的知识才能很好的完成本次的课程设计。在这次课程设计中，总的感觉是我遇到了很多困难这主要是由于我编写代码的经验不足，有时虽然是一个很小的问题但解决起来却花费了我不少的时间，值得欣慰的是，当自己苦思冥想或者和其它同学一起探讨把问题解决的时候我还是觉得获益非浅，这就是在摸索中寻求到的知识。在设计时也免不了存在着些不足，所以在今后的学习中我会努力取得更大的进步。虽然对着电脑做程序，有些累，可当看到劳动成果时，却有另一番滋味。 参考文献 [1]范策，周世平，胡晓琨.《算法与数据结构（C语言版）》[M].北京：机械工业出版社，2004 [2]严蔚敏.《数据结构（C语言版）》.北京：清华大学出版社，2004 [3]许卓群，杨冬青，唐世渭，张铭.《数据结构与算法》.北京：高等教育出版社，2004 [4]徐孝凯.《数据结构实用教程（第二版）》.北京：清华大学出版社，2006 附录 附录1 源程序清单 #include /*散列表大小TabSize 是大于表最大空间的素数*/ #define Max 1000001 /*队列空间最大值*/ struct hashtab;typedef struct hashtab *PtrToHash;struct hashtab /*散列表数据结构*/ { char name[5]; /*名字*/ int group; /*属于哪个朋友组*/ char info; /*标志位，该单元是否被占用*/ };struct Que;typedef struct Que *PtrToQue;struct Que /*队列数据结构*/ { long int HashVal; /*散列值*/ long int Index; /*在中的队列序号*/ }; int hashedx=0; /*标记元素是否已经在散列表里*/ long int Find(PtrToHash hash,char *c)/*查找在散列表中的位置*/ { char *key;long int CurrentPos,CollisionNum; key=c;for(CurrentPos=0;*key;++key) /*散列函数，计算散列值*/ CurrentPos=(CurrentPos<<6)+*key;CurrentPos%=TabSize; /*散列值*/ CollisionNum=0;/*如果当前单元被占用：单元内的元素与当前操作的名字不同，使用平方探测法解决冲突；与当前操作的名字相同，则直接返回在散列中的位置*/ while((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c))) { /*平方探测法*/ CurrentPos+=2*(++CollisionNum)-1; if(CurrentPos>=TabSize) CurrentPos-=TabSize;} if((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)==0)) /*元素已经在散列表里*/ hashedx=1;else /*元素不在散列表里*/ hashedx=0;return CurrentPos;/*返回在散列表中的位置*/ } int main(){ long int Find(PtrToHash hash,char *c); /*查找在散列表中的位置*/ PtrToHash hash; /*散列表*/ PtrToQue queue; /*队列*/ int *grouppos; /*记录每个朋友组的最后一位，即插队数组*/ int n; /*测试用例数目*/ int num; /*当前测试用例序号*/ long int i,ii,j,key,temp;long int head,last; /*队列的头和尾*/ char c[8],tempc[8]; /*名字*/ FILE *fpin,*fpout; /*输入、输出文件指针*/ if(!(fpin=fopen(“input.txt”,“r”))) /*打开测试文件*/ { printf(“fopen error!”); /*文件打开错误*/ return-1;} if(!(fpout=fopen(“output.txt”,“w”))) /*打开输出文件*/ { printf(“fopen error!”); return-1;} hash=(PtrToHash)malloc(sizeof(struct hashtab)*TabSize);/*为散列表申请空间*/ queue=(PtrToQue)malloc(sizeof(struct Que)*Max);/*为队列申请空间*/ grouppos=(int *)malloc(sizeof(int)*1000);/*申请空间记录每个朋友组的最后一位*/ for(i=0,j=1;i queue[i].Index=j;queue[i-1].Index=0;/*最后一个单元的后继单元是第0个，形成环*/ num=0;for(fscanf(fpin,“%d”,&n);n;fscanf(fpin,“%d”,&n))/*输入当前测试用例的朋友组数*/ { if(n<1||n>1000) /*处理异常输入n*/ { fprintf(fpout,“n is out of rangen”); return-1; } num++; if(num!=1) /*两个测试用例间输入一空行*/ fprintf(fpout,“n”); for(i=0;i hash[i++].info=0; /*初始化散列表，标记位置0*/ for(i=0;i /*对每一组朋友*/ { fscanf(fpin,“%d”,&j); /*当前组里的人数*/ if(j<1||j>1000) /*处理异常输入j*/ { fprintf(fpout,“j is out of rangen”); return-1; } for(;j;--j) { fscanf(fpin,“%s”,c); /*输入名字*/ for(ii=0;ii tempc[ii]=' '; strcpy(tempc,c); ii=0; while(tempc[ii]!=' ') /* 是否由四个以内字母组成*/ { if(tempc[ii]<'A'||('Z' { fprintf(fpout,“Group %d: Nonstandard namen ”,i); return-1; } ii++; } key=Find(hash,c); /*找到在散列表中的位置*/ if(hashedx==1)/*重名*/ { fprintf(fpout,“repeated name %sn”,c); return-1; } strcpy(hash[key].name,c);/*插入散列表*/ hash[key].info=1; /*标记置1，该单元被占用*/ hash[key].group=i; /*记录他属于哪个组*/ } } for(i=0;i<1000;) grouppos[i++]=0;/*初始化插队数组*/ head=0; /*初始化队列头、尾标记*/ last=0;fprintf(fpout,“Scenario #%dn”,num);/*输出当前用例序号到文件*/ for(fscanf(fpin,“%s”,c);;fscanf(fpin,“%s”,c))/*输入命令*/ { if(*c=='E') /*入队命令*/ { fscanf(fpin,“%s”,c); /*输入名字*/ key=Find(hash,c); /*查找在散列表中的位置*/ if(hashedx==0)/*散列表里没这个人*/ { fprintf(fpout,“no %sn”,c); return-1;} temp=queue[0].Index; /*队列第0个位置记录队尾的后继单元*/ queue[0].Index=queue[temp].Index; /*在队列中申请一个新单元，队尾标记后移一个位置 */ queue[temp].HashVal=key;/*入队*/ if(!head)/*如果是队列里的第一个元素 */ last=head=temp;/*队头、队尾标记指向第一个元素*/ if(!grouppos[hash[key].group])/*如果队列里没朋友*/ { queue[temp].Index=0;/*队尾指向对头，形成环*/ queue[last].Index=temp;/*前一次队尾的后继元素是当前元素*/ last=temp; /*队尾标记指向当前元素*/ grouppos[hash[key].group]=temp;/*插队数组记录该朋友组里已入队的最后一位*/ } else/*如果队列中已经有他的朋友*/ { queue[temp].Index=queue[grouppos[hash[key].group]].Index; /*插队到朋友的后面*/ queue[grouppos[hash[key].group]].Index=temp; /*插队到朋友后面一位的前面*/ grouppos[hash[key].group]=temp; /*替换插队数组里该组的元素为当前元素*/ if(hash[queue[last].HashVal].group==hash[key].group) /*如果当前元素和前一元素是朋友，队尾标志指向当前元素*/ last=temp; } } else if(*c=='D')/*出队命令*/ { if(last==0) /*不能对空队列执行出队命令*/ { fprintf(fpout,“Empty queue!nCan't execute DEQUEUE!n”); return-1; } fprintf(fpout,“%sn”,hash[queue[head].HashVal].name); /*输出队头元素到文件*/ temp=head; head=queue[temp].Index; /*队列第一位出队，队头标记后移一位*/ queue[temp].Index=queue[0].Index; /*队列第0个元素后移一位*/ queue[0].Index=temp; /*释放空间*/ if(grouppos[hash[queue[temp].HashVal].group]==temp) /*当前删除的元素是该朋友组在队列里的最后一位*/ grouppos[hash[queue[temp].HashVal].group]=0; if(last==temp) /*出队后，队列为空*/ last=0; } else /*输入 “STOP”*/ break; /*测试结束*/ } } fprintf(fpout,“b”);fclose(fpin);fclose(fpout);return 1;} 正文要求：对每一个题目，正文必须包括以下几个方面 知识点回顾： 实验要求： 实验过程：包括设计思路，算法描述，程序清单，调试等等； 实验小结： 注意：（1）正文中字体用小四号宋体，行间距1.25倍行距； （2）页码居中； （3）A4纸双面打印，在纸的左侧装订。 （4）上交的课程设计报告控制在10页以内。 齐鲁工业大学 理学院 信计11-1 郑桥 一、提示：对于单窗口的服务系统知识点回顾如下： 1、什么是负指数分布？ 又称指数分布。泊松事件流的等待时间（相继两次出现之间的间隔）服从指数分布。用于描述非老化性元件的寿命（元件不老化，仅由于突然故障而毁坏）。常假定排队系统中服务器的服务时间和Petri网中变迁的实施速率符合指数分布。 2、用C语言如何产生随机序列？ double rd_MN1(double m,double n){ double r;if(m>n){r=n;n=m;m=r;};r =((double)rand()/((double)(RAND_MAX)+(double)(1)));r = m+ r*(n-m);return r;} 3、用C语言如何产生负指数分布的时间序列？ double expntl(double x){ double z;do { z =((double)rand()/ RAND_MAX);} while((z == 0)||(z == 1));return(-x * log(z));//z相当于1-x,而x相当于1/lamda。} 其中的x相当于1/λ 4、排队论简单叙述； 排队系统主要有：X/Y/Z，其中X表示到达时间间隔的分布，Y表示服务时间的分布，Z表示并列的服务设备的数目。表示相继到达的时间间隔或服务时间的分布的符号是： M——负指数分布，D——确定性，Ek——k阶Erlang，GI——相互独立的一般随机分布，G——一般的随机分布。 例如：M/M/1表示达到时间间隔为负指数分布，服务时间为负指数分布，单服务设备的排队系统。 这里我们用静态仿真的思想来实现M/M/1仿真。在排队系统中的每一个动态实体的状态可以有三个量来反映：与前一个实体到达的时间间隔，在排到自己服务前的等待时间以及服务时间。其中服务时间和到达时间间隔服从指数分布，不受别的因素的影响。开始服务前的等待时间则受到排在前面的动态实体的状态的影响。其更新算法如下： 即：如果某个实体到达以后，发现处在它前面的动态实体已经结束服务，所以这个实体就不用等待，直接接受服务；反之，处在它前面的动态实体如果没有结束服务（包括没有开始服务），则这个实体的等待时间就是它前一实体结束服务的时刻减去它到达的时刻。 5、如何得到每个顾客的到达时刻，服务时间，等待时间和离开时刻； 到达时间=前面各个到达时间之和； 服务时间就是负指数随机生成的时间； 等待时刻：如果前一个人的离开时间小于这个人的到达时间，等待时间=0； 如果不是，则等待时间=该人的离开时间-他的到达时间-服务时间 6、如何排队，排队的主要算法思想？ 排队就是来到的人数多于离开的人数； 如果下一个人到达时前一个人依旧在接受服务，则此人就要排队。 7、如何求队长？以及最大的队长？ 假设以5分钟为一个时间段，则在第5分钟时用这5分钟内来到的人数减去这5分钟内离开的人数即是排队人数 8、如何求平均等待时间？ 求平均等待时间首先要求出总的等待时间与接受服务的人数； 总的等待时间=每个人的等待时间之和；接受服务的人数由时间540分钟来控制，如果在540分钟之后才到达的人则不再算入接受服务的人数之内。 9、用C语言如何将得到的数据输出到文件？ 在C语言中用fopen函数打开文件，然后把数据输出比如用fprintf函数，最后fclose。 利用ofstream fcout(“d:arr_time.txt”);语句来实现C++中的输出文件 10、如何用已学的数学语言程序（如：Mathematica, Matlab）把C语言得到的数据文件画出其相应的图像？ 11、如果是两个窗口的服务系统，则该怎么修改程序？ 12、如果到达时间间隔，服务时间服从泊松分布或者其他分布，该程序该如何改进？ 二、数据结构课程设计题目 单窗口的排队模型的数值仿真（参考课本上第四章的离散事件模拟）要求如下：（1）要求相邻两个顾客的到达时间间隔服从负指数分布；且每个顾客接受服务的时间也服从负指数分布； （2）求出各个时刻的队长（以五分钟为一时间单位，即求零时刻的队长，五分钟时的队长，十分钟时的队长，依次类推）； （3）一个工作日内的顾客总数，约定8：30上班，17：30下班，中午不休息；（4）求平均等待时间（顾客总等待时间除以总人数）； （5）画出顾客的到达，离开图像（横坐标是顾客图，纵坐标是到达时刻，和离开时刻）； （6）画出队长变换图像（横坐标是时刻图，纵坐标是队长个数）；（7）求出一个工作日内的最大队长； 三、设计思路： 1）把8：:30记做第0分钟，17:30记做第540分钟。 2）首先利用C++随机生成200个服从负指数分布的到达时间与200个服务时间 然后根据随机生成的数计算到达的时刻，即到达时间的逐步加和，然后计算离开的时刻； 3）根据到达时刻与离开时刻来计算等待时刻，于是便可得到平均等待时间； 同时根据这两个时刻求出每5分钟到达人数与离开的人数，于是便得出每5分钟的队长，同时也可求出最大队长。4）再利用MATLAB画出相应的图像。 四、算法描述： 1）首先将8:30这个时刻化为0时刻，17:30化为第540分钟这个时刻，全体单位为分钟。 2）定义到达时间间隔arr_time[200]，服务时间ser_time[200]，到达时刻arr_time1[200],离开时间lea_time[200],等待时间sta_time[200],离开人数lea_num[200],到达人数arr_num[200]等变量。3）根据负指数函数 来利用C++程序生成随机到达时间间隔与服务时间。 4）利用到达时刻与离开时刻之间的关系来求出等待时间。同时将这540分钟划分为5分钟间隔的108个时间段来求出在每个时间段到达人数与离开人数，再求出队长。 5）利用已知的服务人数，平均到达时间与平均离开时间来做出图像。（借助MATLAB软件。） 五、总结 （1）求出各个时刻的队长（以五分钟为一时间单位，即求零时刻的队长，五分钟时的队长，十分钟时的队长，依次类推）；见程序清单中数据部分对长。（2）求平均等待时间（顾客总等待时间除以总人数）；根据程序可得，平均等待时间为21.6分钟。 （3）画出顾客的到达，离开图像（横坐标是顾客图，纵坐标是到达时刻，和离开时刻）； ***0100806040200 0Arrive curveleave curve***600 （6）画出队长变换图像（横坐标是时刻图，纵坐标是队长个数）； 25Queue Length Curve 20151050 ***0600 （7）求出一个工作日内的最大队长： 最大对长为16个人在排队。 六、程序清单： 求随机产生负指数 #include #include void main(){ long int i,k;double m,n;//m,n控制时间间隔 double r;double a,s,sum;//arr为到达时间，ser为服务时间 double LAM=1.2; //f(x)=LAM*exp(-LAM*x);double arr_time[200];double ser_time[200];ofstream fcout(“d:arr_time.txt”);ofstream fscout(“d:ser_time.txt”);m=2.0;n=5.0;srand((unsigned)time(NULL)); k=0;loop: r=((double)rand()/((double)(RAND_MAX)+(double)(1))); a =-log(r)/LAM;if(a >= m && a <= n){ arr_time[k]=a; k++;};if(k < 200)goto loop; // 产生200个指数分布随机数 for(i=0;i<200;i++){ fcout< //cout< if(i!=0 && i%5==0) //cout< fcout< s =-log(r)/LAM;if(s >= m && s <= n){ ser_time[k]=s;k++;};if(k < 100)goto loop1; // 产生200个指数分布随机数 m=3.0;n=5.5; srand((unsigned)time(NULL));k=100;loop2: r=((double)rand()/((double)(RAND_MAX)+(double)(1))); s =-log(r)/LAM;if(s >= m && s <= n){ ser_time[k]=s;k++;};if(k < 200)goto loop2; // 产生200个指数分布随机数 for(i=0;i<200;i++){ fscout< //cout< if(i!=0 && i%5==0) //cout< fscout< #include double sta_time[200];//等待时间 double arr_time[200];//随机生成到达时间 double ser_time[200];//随机生成服务时间 double arr_time1[200];//到达时间 ifstream fcin(“d:arr_time.txt”);ifstream fscin(“d:ser_time.txt”);ofstream fcout(“d:arr_time1.txt”);ofstream flcout(“d:lea_time.txt”);ofstream fscout(“d:sta_time.txt”); //求到达的时间 for(i=0;i<200;i++){ fcin>>arr_time[i]; arr_time1[i]=arr_time[i];} double sum=0.0;for(i=0;i<200;i++){ sum+=arr_time1[i]; arr_time1[i]=sum;} for(i=0;i<200;i++){ fcout< if(i!=0 && i%5==0) fcout< //求离开时间 fscin>>ser_time[0];lea_time[0]=arr_time1[0]+ser_time[0];for(i=1;i<200;i++){ fscin>>ser_time[i]; if(lea_time[i-1]>arr_time1[i]) {lea_time[i]=lea_time[i-1]+ser_time[i];} else {lea_time[i]=arr_time1[i]+ser_time[i];} } for(i=0;i<200;i++){ flcout< if(i!=0 && i%5==0) flcout< sta_time[i]=lea_time[i]-arr_time1[i]-ser_time[i];// if(sta_time[i]<0) { sta_time[i]=0; } } for(i=0;i<200;i++){ fscout< if(i!=0 && i%5==0) fscout< sta_sum+=sta_time[i];} //求平均等待时间 double ave;int peo_sum;for(i=0;i<200;i++){ if(lea_time[i]<540) peo_sum=i;} cout<<“总的服务人数为：”< 求离开人数和到达人数 #include #include int i,j; int arr_num[200];//到达人数arr int lea_num[200];//lea离开人数 int arr_jian=0;//时间间隔 double arr_time1[200];double lea_time[200];int peo_sum;int count=0;int count1=0;ifstream fcin(“d:arr_time1.txt”);ifstream flcin(“d:lea_time.txt”);ofstream fcout(“d:arr_num.txt”);ofstream flcout(“d:lea_num.txt”);for(i=0;i<200;i++){ fcin>>arr_time1[i]; flcin>>lea_time[i];} for(i=0;i<200;i++){ if(lea_time[i]<540) peo_sum=i;} while(arr_jian<540){ for(i=0;i { if(arr_time1[i]>arr_jian) { arr_num[count]=i; count++; //cout< break; } } for(j=0;j { if(lea_time[j]>arr_jian) { lea_num[count1]=j; count1++; break; } } arr_jian=arr_jian+5;} for(i=0;i<108;i++){ fcout< //cout< if(i!=0 && i%5==0) //cout< fcout< for(i=0;i<108;i++){ flcout< //cout< if(i!=0 && i%5==0) //cout< flcout< 求对长 #include int i;int max;int que[200];int arr_num[200];int lea_num[200];ifstream fcin(“d:arr_num.txt”);ifstream flcin(“d:lea_num.txt”);ofstream fcout(“d:que.txt”); for(i=0;i<200;i++){ fcin>>arr_num[i]; //cout< flcin>>lea_num[i]; //cout< for(i=0;i<200;i++){ que[i]=arr_num[i]-lea_num[i]; //cout< } for(i=0;i<200;i++){ fcout< if(i!=0 && i%5==0) { fcout< } } max=que[0];for(i=1;i<200;i++) { if(que[i]>max) { max=que[i]; //cout< } } cout<<“最大对长是”< 画图: function[maxque,mwait_t,mstay_t,queue_l,use_rate]=MM1queue(mean_arr,mean_lea,peo_num)status=zeros(3,peo_num); %用一个3行矩阵表示每个顾客的状态; %到达时间间隔，服务时间，等待时间;status(1,:)=exprnd(mean_arr,1,peo_num); %按照指数分布随机生成各顾客的到达间隔;status(2,:)=exprnd(mean_lea,1,peo_num); %按照指数分布随机生成各顾客的服务时间;for i=2:peo_num if status(1,i)<=status(2,i-1)+status(3,i-1) status(3,i)=status(2,i-1)+status(3,i-1)-status(1,i); else status(3,i)=0; end; %对状态进行更新； end;arr_time=cumsum(status(1,:));status(1,:)=arr_time;lea_time=sum(status);stairs([0 arr_time],0:peo_num); %绘出各顾客的到达时间图; hold on;stairs([0 lea_time],0:peo_num,'r'); %绘出各顾客的离去时间图;legend('Arrive curve','leave curve',0)hold off figure;plot(1:peo_num,status(3,:),'r:',1:peo_num,status(2,:)+status(3,:),'k-'); %绘出每个顾客的等待时间和停留时间;legend('Wait Time','Stay Time',0);n1=1;n2=1;mstay_t=(sum(status(2,:))+sum(status(3,:)))/peo_num;mwait_t=mean(status(3,:)); %求平均停留时间和等待时间;queue_num=zeros(1,2*peo_num+1);queue_time=zeros(1,2*peo_num+1);n3=1; %while循环求每个时间队列的长度;while n1<=peo_num n3=n3+1; if arr_time(n1) queue_num(1,n3)=n1-n2+1; queue_time(1,n3)=arr_time(n1); n1=n1+1; else queue_num(1,n3)=n1-n2-1; queue_time(1,n3)=lea_time(n2); n2=n2+1; end;end;while n2<=peo_num n3=n3+1; queue_num(1,n3)=peo_num-n2; queue_time(1,n3)=lea_time(n2); n2=n2+1;end;figure;stairs(queue_time,queue_num,'k'); %绘出队列长度的时间变化曲线, stairs 是Matlab的函数 legend('Queue Length Curve',0);hold off;temp=diff(queue_time);overtime=max(queue_time);queue_l=sum(temp.*queue_num(2:(2*peo_num+1)))/overtime;use_rate=sum(temp(find(queue_num)))/overtime;maxque=max(queue_num);% 最大队长 在MATLAB中命令窗口中输入MM1queue(2.86,3.22,175)数据结果： 随机到达时间arr_time 2.2218 2.91038 2.70151 3.20392 2.20729 2.23954 2.27037 2.12161 2.97105 2.59537 2.05195 2.33276 2.40885 2.54536 3.18395 4.34619 2.9621 4.03687 2.56005 4.3556 2.59767 2.6854 2.2156 2.35007 2.01546 3.16558 2.51725 2.4227 3.00499 2.68796 2.57445 2.29238 2.04275 3.56593 4.12181 3.14539 4.60806 2.85305 2.18215 4.15836 2.75386 2.45691 3.15095 3.84449 3.29556 2.35349 2.88082 2.96656 2.60517 3.09175 3.77562 2.12649 2.17347 2.28761 2.91709 2.59767 2.20084 3.64077 2.09167 2.30401 2.89137 2.78563 2.35564 2.60401 3.47721 2.31212 2.2892 2.26189 2.71001 3.23541 3.15543 4.04989 2.33905 2.60575 2.93069 2.63466 2.33025 2.67211 2.13304 2.46765 2.01119 2.66026 2.17867 4.26591 2.56115 2.84451 3.37485 2.22326 2.3109 3.08451 2.75872 3.02393 2.32155 2.37607 2.43489 3.70764 3.07631 2.56943 2.81941 2.81567 2.18215 3.78511 2.72393 2.02062 2.28013 2.03219 2.9324 4.02088 2.83606 2.01804 2.82241 2.23062 2.38448 2.15369 4.07996 2.02407 2.77847 2.93584 4.92381 4.07996 2.52143 2.10523 3.29291 2.34922 2.60807 2.83989 3.77091 2.4652 2.12096 2.36601 4.23257 2.29039 2.03278 3.42756 3.04233 2.80972 4.46149 2.04867 3.6673 2.04363 3.56409 4.8267 4.40435 3.60347 2.01375 4.41955 2.28406 2.49971 2.85853 2.11547 2.29079 2.2037 3.0078 2.43726 2.43963 3.82172 2.26189 3.14207 3.02297 2.39612 2.26381 3.59773 2.454 4.98197 3.60539 3.04233 3.21228 2.48553 2.16591 2.17244 2.25882 2.11773 3.77326 2.1113 3.15319 2.4011 2.66648 3.58261 3.36182 2.74012 2.16046 2.53464 2.21742 2.48754 2.86484 2.45837 2.4213 2.81047 4.02405 2.08667 2.24179 2.17971 3.1465 2.96925 2.07709 2.6139 3.48217 4.50565 3.25667 2.71528 随机服务时间ser_time 1.36266 1.25234 1.19953 1.81288 1.7025 1.49777 1.18475 1.2005 2.2218 2.91038 1.69353 1.06181 1.95277 1.86629 1.35603 1.36501 1.98628 1.05845 1.48635 2.70151 1.56285 1.7392 1.00964 1.69024 1.23548 1.68311 3.20392 2.20729 2.23954 1.0431 1.986 1.09644 2.27037 1.53367 2.12161 2.97105 1.68177 2.59537 2.05195 1.54594 1.24156 1.42946 2.33276 1.06994 2.40885 1.9069 2.54536 3.18395 4.34619 2.9621 1.09313 4.03687 2.56005 1.01332 1.97996 1.76143 1.26501 1.34689 1.66416 4.3556 1.6471 1.46631 2.59767 2.6854 1.92952 1.51985 1.85138 1.04044 2.2156 1.30726 1.1663 1.16661 5.21173 2.35007 1.3357 1.00973 2.01546 3.16558 2.51725 1.27905 2.4227 1.04284 1.69508 1.63761 1.13783 1.05052 1.94433 1.53127 3.00499 2.68796 2.57445 2.29238 1.40015 1.2112 1.64527 2.04275 1.29598 1.29286 3.56593 1.07538 3.20392 3.18395 4.34619 4.03687 4.3556 5.21173 3.16558 3.00499 3.56593 4.12181 3.14539 4.60806 4.15836 3.15095 3.84449 3.29556 5.29513 3.09175 3.77562 3.64077 3.47721 3.23541 3.15543 4.04989 4.26591 3.37485 3.08451 3.02393 3.70764 3.07631 3.78511 4.02088 4.07996 4.92381 4.07996 3.29291 3.77091 4.23257 3.42756 3.04233 4.46149 3.6673 3.56409 4.8267 4.40435 3.60347 4.41955 3.0078 3.82172 3.14207 3.02297 3.59773 4.98197 3.60539 3.04233 3.21228 3.77326 3.15319 3.58261 3.36182 5.0445 4.02405 3.1465 3.48217 4.50565 3.25667 4.85208 4.16211 4.13261 3.21952 3.46087 3.74548 4.5463 3.72969 3.29423 3.0804 3.08657 3.47556 4.09022 3.17586 5.29513 3.75694 3.74548 3.30222 3.01725 3.18627 3.40305 4.12539 3.49556 3.02777 3.87053 3.39703 3.51433 3.67983 3.27072 4.11115 4.22444 4.08337 3.37339 5.03375 到达时刻：arr_time1 2.2218 5.13218 7.83369 11.0376 13.2449 15.4844 17.7548 19.8764 22.8475 25.4428 27.4948 29.8276 32.2364 34.7818 37.9657 42.3119 45.274 49.3109 51.8709 56.2265 58.8242 61.5096 63.7252 66.0753 68.0907 71.2563 73.7736 76.1963 79.2012 81.8892 84.4637 86.756 88.7988 92.3647 96.4865 99.6319 104.24 107.093 109.275 113.434 116.187 118.644 121.795 125.64 128.935 131.289 134.17 137.136 139.741 142.833 146.609 148.735 150.909 153.196 156.113 158.711 160.912 164.553 166.644 168.948 171.84 174.625 176.981 179.585 183.062 185.374 187.664 189.925 192.635 195.871 199.026 203.076 205.415 208.021 210.952 213.586 215.917 218.589 220.722 223.189 225.201 227.861 230.039 234.305 236.867 239.711 243.086 245.309 247.62 250.705 253.463 256.487 258.809 261.185 263.62 267.327 270.404 272.973 275.793 278.608 280.79 284.575 287.299 289.32 291.6 293.632 296.565 300.586 303.422 305.44 308.262 310.493 312.877 315.031 319.111 321.135 323.913 326.849 331.773 335.853 338.374 340.48 343.773 346.122 348.73 351.57 355.341 357.806 359.927 362.293 366.525 368.816 370.849 374.276 377.318 380.128 384.59 386.638 390.306 392.349 395.913 400.74 405.144 408.748 410.762 415.181 417.465 419.965 422.823 424.939 427.23 429.433 432.441 434.878 437.318 441.14 443.402 446.544 449.567 451.963 454.227 457.824 460.278 465.26 468.866 471.908 475.12 477.606 479.772 481.944 484.203 486.321 490.094 492.205 495.359 497.76 500.426 504.009 507.371 510.111 512.271 514.806 517.023 519.511 522.376 524.834 527.255 530.066 534.09 536.176 538.418 540.598 543.744 546.714 548.791 551.405 554.887 559.393 562.649 565.364 离开时刻：lea_time 3.58446 6.38452 9.03322 12.8505 14.9474 16.9822 18.9396 21.0769 25.0693 28.3532 30.0467 31.1086 34.1892 36.6481 39.3217 43.6769 47.2603 50.3693 53.3573 58.928 60.4909 63.2488 64.7348 67.7655 69.3262 72.9394 76.9775 79.1848 81.4408 82.9323 86.4497 87.8525 91.0692 93.8984 98.6081 102.603 105.922 109.688 111.74 114.979 117.429 120.074 124.128 126.71 131.344 133.251 136.715 140.32 144.666 147.628 148.722 152.772 155.332 156.345 158.325 160.472 162.177 165.9 168.308 173.304 174.951 176.417 179.579 182.27 184.992 186.894 189.515 190.966 194.851 197.178 200.193 204.243 210.627 212.977 214.313 215.322 217.932 221.754 224.271 225.551 227.973 229.016 231.735 235.943 238.004 240.762 245.03 246.84 250.625 253.393 256.038 258.78 260.209 262.396 265.265 269.37 271.7 274.266 279.358 280.434 283.994 287.759 292.106 296.142 300.498 305.71 308.875 311.88 315.446 319.568 322.713 327.322 331.48 334.631 338.475 341.771 347.066 350.158 353.933 357.574 361.051 364.287 367.442 371.492 375.758 379.133 382.217 385.241 388.949 392.025 395.81 399.831 403.911 408.835 412.915 416.208 419.979 424.211 427.639 430.681 435.143 438.81 442.374 447.201 451.605 455.209 459.628 462.636 466.458 469.6 472.623 476.22 481.202 484.808 487.85 491.062 494.836 497.989 501.572 504.933 509.978 514.002 517.148 520.631 525.136 528.393 533.245 537.407 541.54 544.759 548.22 551.966 556.512 560.242 563.536 566.616 569.703 573.178 577.269 580.444 585.74 589.496 593.242 596.544 599.561 602.748 606.151 610.276 613.772 616.799 620.67 624.067 627.581 631.261 634.532 638.643 642.867 646.951 650.324 655.358 到达人数：peo_num 0 1 3 5 8 9 12 14 15 16 18 19 21 23 25 27 29 31 33 34 36 39 40 42 43 45 47 49 50 52 54 56 58 60 62 64 65 68 69 71 74 76 78 80 82 84 86 87 89 91 93 95 96 98 100 102 104 106 107 109 111 113 115 117 118 119 121 123 125 126 129 130 132 134 135 137 138 140 141 142 144 145 148 150 152 154 155 157 159 161 162 163 165 166 167 169 170 171 173174 175 177 离开人数：lea_num 0 1 3 5 7 8 10 13 15 16 17 19 20 23 25 26 28 30 32 34 35 38 40 41 43 44 46 47 49 51 52 55 57 59 61 63 65 67 69 70 72 75 77 79 82 83 85 86 88 90 92 94 96 98 99 101 102 103 104 105 107 108 110 111 112 114 115 116 117 119 120 122 123 124 127 129 130 132 133 134 135 137 138 139 140 142 143 144 147 148 150 151 152 154 155 157 158 160 161 162 队长que 0 0 0 0 1 1 2 1 0 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 0 1 2 1 1 2 1 1 1 1 1 0 1 0 1 0 2 1 1 1 0 1 1 1 1 1 1 0 0 1 1 2 3 3 4 4 5 5 6 6 5 6 7 8 7 9 8 9 10 0 10 9 10 9 9 10 10 11 12 13 14 13 14 15 16 15 15 15 15 0 0 0 0 0 0 0 0 605040302010Wait TimeStay Time***401601800 0第二篇：C++数据结构 大作业课程设计
第三篇：C++课程设计报告--矩阵乘法计算
第四篇：数据结构课程设计报告
第五篇：数据结构课程设计报告
点击咨询 