四川大学计算机学院数据结构与算法分析实验报告

《数据结构与算法》课程设计指导老师：班级：姓名：学号：算术表达式求值问题描述从键盘上输入中缀算数表达式，包括括号，计算粗话表达式的值。二、根本要求程序对所输出的表达式做出简单的判断，如表达式有错，能给出适当的提示能处理单目运算符：+和—三、工具/准备工作在开始做课程设计工程前，应回忆或复习相关内容。需要一台计算机，其内安装有MicrosoftVisualStudio2023的集成开发环境软件四、分析与实现对中缀表达式，一般运算规那么如下：先乘方，再乘除，最后加减同级运算从左算到右先算括号内，再算括号外根据实践经验，可以对运算符设置统一的优先级，从而方便比拟。如下表：运算符=〔〕+-*/%^优先级12345单目运算符：+，—〔可以看成0+/—个数〕双目运算符：+，—〔在+或—的前一个字符〔当前一个不是运算符时，规定用‘0’表示〕〕为‘=’，‘〔’，那么为单目运算符。具体实现算法时，可设置两个工作栈，一个为操作符栈optr(operator),另一个为操作数栈opnd(operand),算法根本工作思路如下：将optr栈和opnd栈清空，在optr栈中参加一个‘=’从输入流获取一字符ch，循环执行〔3〕~〔5〕直到求出表达式的值为止。取出optr的栈顶optrTop，当optrTop=‘=’且ch=‘=’时，整个表达式求值完毕，这时opnd栈顶元素为表达式的值。假设ch不是操作符，那么将字符放回输入流〔cin.putback〕，读操作数operand；将operand参加opnd栈，读入下一个字符ch。假设ch是操作符，按如下方式进行处理如果ch为单目运算符，那么在ch前面加上操作数0，也就是将0入opnd栈。如果optrTop与ch不匹配，例如optrTop=’〕’且ch=‘〔’,显示错误信息。如果optrTop=‘〔’且ch=‘〕’，那么从optr栈退出栈顶的‘〔’，去括号，然后从输入流中读入字符并送入ch如果ch=‘〔’或optrTop比ch的优先级低，那么ch入optr栈，从optr栈退出theta，形成运算指令〔left〕theta(right),结果入opnd栈。源代码：//文件node.h#ifndef_NODE_H_#define_NODE_H_template<classElemType>structNode{ElemTypedata;Node<ElemType>*next;Node();Node(ElemTypeitem,Node<ElemType>*link=NULL);};template<classElemType>Node<ElemType>::Node(){next=NULL;}template<classElemType>Node<ElemType>::Node(ElemTypeitem,Node<ElemType>*link){data=item;next=link;}#endif_NODE_H_//文件lk_stack.h#ifndef_LINK_STACK_H_#define_LINK_STACK_H_#include"utility.h"#include"node.h"template<classElemType>classLinkStack{protected:Node<ElemType>*top;voidInit();public:LinkStack();intLength()const;boolEmpty()const;voidClear();voidTraverse(void(*visit)(constElemType&))const;StatusCodePush(constElemType&e);StatusCodePop(ElemType&e);StatusCodeTop(ElemType&e)const;LinkStack(constLinkStack<ElemType>©);LinkStack<ElemType>&operator=(constLinkStack<ElemType>©);};template<classElemType>voidLinkStack<ElemType>::Init(){top=NULL;}template<classElemType>LinkStack<ElemType>::LinkStack(){Init();}template<classElemType>intLinkStack<ElemType>::Length()const{intcount=0;for(Node<ElemType>*tmpPtr=top;tmpPtr!=NULL;tmpPtr=tmpPtr->next){count++;}returncount;}template<classElemType>boolLinkStack<ElemType>::Empty()const{returntop==NULL;}template<classElemType>voidLinkStack<ElemType>::Clear(){ElemTypetmpElem;while(!Empty()){Pop(tmpElem);}}template<classElemType>voidLinkStack<ElemType>::Traverse(void(*visit)(constElemType&))const{Node<ElemType>*tmpPtr;LinkStack<ElemType>tmpS;for(tmpPtr=top;tmpPtr!=NULL;tmpPtr->next){tmpS.Push(tmpPtr->data);}for(tmpPtr=tmpS.top;tmpPtr!=NULL;tmpPtr->next){(*visit)(tmpPtr->data);}}template<classElemType>StatusCodeLinkStack<ElemType>::Push(constElemType&e){Node<ElemType>*new_top=newNode<ElemType>(e,top);if(new_top==NULL){returnOVER_FLOW;}else{top=new_top;returnSUCCESS;}}template<classElemType>StatusCodeLinkStack<ElemType>::Top(ElemType&e)const{if(Empty()){returnUNDER_FLOW;}else{e=top->data;returnSUCCESS;}}template<classElemType>StatusCodeLinkStack<ElemType>::Pop(ElemType&e){if(Empty()){returnUNDER_FLOW;}else{Node<ElemType>*old_top=top;e=old_top->data;top=old_top->next;deleteold_top;returnSUCCESS;}}template<classElemType>LinkStack<ElemType>::LinkStack(constLinkStack<ElemType>©){if(copy.Empty()){Init();}else{top=newNode<ElemType>(copy.top->data);Node<ElemType>*buttomPtr=top;for(Node<ElemType>*tmp=copy.top->next;tmpPtr!=NuLL;tmpPtr!=NULL;tmpPtr=tmpPtr->next){buttomPtr->next=newNode<ElemType>(tmpPtr->data)buttomPtr=buttomptr->next;}}}template<classElemType>LinkStack<ElemType>&LinkStack<ElemType>::operator=(constLinkStack<ElemType>©){if(©!=this){if(copy.Empty()){Init();}else{Clear();top=newNode<ElemType>(copy.top->data);Node<ElemType>*buttomPtr=top;for(Node<ElemType>*tmpPtr=copy.top->next;tmpPtr!=Null;tmpPtr=tmpPtr->next){buttomPtr->next=newNode<ElemType>(tmpPtr->data);buttomPtr=buttomPtr->next;}}}return*this;}#endif_LINK_STACK_H_//文件路径名:calculator.h//文件路径名:calculator\calculator.h#ifndef__CALCULATOR_H__#define__CALCULATOR_H__#include"lk_stack.h"//链栈类//计算器类template<classElemType>classCalculator{private:LinkStack<ElemType>opnd;//操作数栈LinkStack<char>optr;//操作符栈intOperPrior(charop);//操作符优先级voidGet2Operands(ElemType&left,ElemType&right);ElemTypeOperate(ElemTypeleft,charop,ElemTyperight);boolIsOperator(charch);//判断ch是否为操作符public:Calculator(){};//无参数的构造函数virtual~Calculator(){};//析构函数voidRun();//运算表达式};template<classElemType>intCalculator<ElemType>::OperPrior(charop){intprior;//优先级if(op=='=')prior=1;//=优先级为1elseif(op=='('||op==')')prior=2;//(优先级为2elseif(op=='+'||op=='-')prior=3;//+-优先级为3elseif(op=='*'||op=='/'||op=='%')prior=4;//*/%优先级为4elseif(op=='^')prior=5;returnprior;}template<classElemType>voidCalculator<ElemType>::Get2Operands(ElemType&left,ElemType&right){if(opnd.Pop(right)==UNDER_FLOW)throwError("表达式有错!");if(opnd.Pop(left)==UNDER_FLOW)throwError("表达式有错!");};template<classElemType>ElemTypeCalculator<ElemType>::Operate(ElemTypeleft,charop,ElemTyperight){ElemTyperesult;if(op=='+')result=left+right;//加法运算elseif(op=='-')result=left-right;//减法运算elseif(op=='*')result=left*right;//乘法运算elseif(op=='/'&&right==0)throwError("除数为零!");elseif(op=='/'&&right!=0)result=left/right;elseif(op=='%'&&(long)right==0)throwError("除数为零!");elseif(op=='%'&&(long)right!=0)result=(long)left%(long)right;elseif(op=='^')result=pow(left,right);//乘方运算returnresult;//返回result}template<classElemType>boolCalculator<ElemType>::IsOperator(charch){if(ch=='='||ch=='('||ch=='^'||ch=='*'||ch=='/'||ch=='%'||ch=='+'||ch=='-'||ch==')')returntrue;elsereturnfalse;};template<classElemType>voidCalculator<ElemType>::Run(){optr.Clear();opnd.Clear();//清空optr栈与opnd栈optr.Push('=');//在optr栈中参加一个'='charch;//临时字符charpriorChar;//当前输入的前一个字符如不为操作符，那么令其值为'0'charoptrTop;//临optr栈的栈顶字符doubleoperand;//操作数charop;//操作符priorChar='=';//前一字符ch=GetChar();//读入一个字符if(optr.Top(optrTop)==UNDER_FLOW)throwError("表达式有错!");//抛出异常//取出optr栈的栈顶while(optrTop!='='||ch!='='){//当前表达式还未运算结束,继续运算if(isdigit(ch)||ch=='.'){//ch为一个操作数的第1个字符cin.putback(ch);//将字符ch放回输入流cin>>operand;//读入操作数opnd.Push(operand);//操作数入opnd栈priorChar='0';//前一字符不是操作符,规定前一字符为'0'ch=GetChar();//读入下一个字符}elseif(!IsOperator(ch)){//既不是操作符,也不属于操作数throwError("表达式有错!");//抛出异常}else{//ch为操作符if((priorChar=='='||priorChar=='(')&&(ch=='+'||ch=='-')){opnd.Push(0);priorChar='0';}if(optrTop==')'&&ch=='('||optrTop=='('&&ch=='='||optrTop=='='&&ch==')')throwError("表达式有错!");elseif(optrTop=='('&&ch==')'){//去括号if(optr.Pop(optrTop)==UNDER_FLOW)throwError("表达式有错!");ch=GetChar();//读入新字符priorChar=')';//新的前一字符为)}elseif(ch=='('||OperPrior(optrTop)<OperPrior(ch)){//optrTop为(,或optrTop比ch的优先级低optr.Push(ch);//ch入optr栈priorChar=ch;//新的前一字符为chch=GetChar();//读入新字符}else{//optrTop的大于或等于ch的优先级if(optr.Pop(op)==UNDER_FLOW)throwError("表达式有错!");ElemTypeleft,right;//操作数Get2Operands(left,right);//从opnd栈中取操作数opnd.Push(Operate(left,op,right));}}if(optr.Top(optrTop)==UNDER_FLOW)throwError("表达式有错!");//抛出异常}if(opnd.Top(operand)==UNDER_FLOW)throwError("表达式有错!");cout<<operand<<endl;//显示表达式的值};#endif//文件utility.h#ifndef__UTILITY_H__//如果没有定义__UTILITY_H__#define__UTILITY_H__//那么定义__UTILITY_H__#include<string>//标准串和操作#include<iostream>//标准流操作#include<limits>//极限#include<cmath>//数学函数#include<fstream>//文件输入输出#include<cctype>//字符处理#include<ctime>//日期和时间函数#include<cstdlib>//标准库#include<cstdio>//标准输入输出#include<iomanip>//输入输出流格式设置#include<cstdarg>//支持变长函数参数#include<cassert>//支持断言usingnamespacestd;//标准库包含在命名空间std中enumStatusCode{SUCCESS,FAIL,UNDER_FLOW,OVER_FLOW,RANGE_ERROR,DUPLICATE_ERROR,NOT_PRESENT,ENTRY_INSERTED,ENTRY_FOUND,VISITED,UNVISITED};charGetChar(istream&inStream=cin);//从输入流inStream中跳过空格及制表符获取一字符boolUserSaysYes();//当用户肯定答复(yes)时,返回true,用户否认答复(no)时,返回falsecharGetChar(istream&inStream){charch;//临时变量while((ch=(inStream).peek())!=EOF//文件结束符(peek()函数从输入流中接受1//字符,流的当前位置不变)&&((ch=(inStream).get())==''//空格(get()函数从输入流中接受1字符,流//的当前位置向后移1个位置)||ch=='\t'));//制表符returnch;//返回字符}boolUserSaysYes(){charch;//用户答复字符boolinitialResponse=true;//初始答复do{//循环直到用户输入恰当的答复为止if(initialResponse){//初始答复cout<<"(y,n)?";}else{//非初始答复cout<<"用y或n答复:";}while((ch=GetChar())=='\n');//跳过空格,制表符及换行符获取一字符initialResponse=false;}while(ch!='y'&&ch!='Y'&&ch!='n'&&ch!='N');while(GetChar()!='\n');//跳过当前行后面的字符if(ch=='y'||ch=='Y')returntrue;elsereturnfalse;}#defineMAX_ERROR_MESSAGE_LEN100classError{private:charmessage[MAX_ERROR_MESSAGE_LEN];//异常信息public:Error(charmes[]="一般性异常!");//构造函数~Error(void){};//析构函数voidShow()const;//显示异常信息};Error::Error(char*mes){strcpy(message,mes);//复制异常信息}voidError::Show()const{cout<<message<<endl;//显示异常信息}#endif//文件：mian.cpp#include"utility.h"#include"lk_stack.h"//顺序表类#include"calculator.h"//计算器类intmain(void){try//用try封装可能出现异常的代码{do{cout<<"输入一个表达式:"<<endl;Calculator::Run();//表达式求值cout<<"是否继续";}while(UserSaysYes());}catch(Errorerr)//捕捉并处理异常{err.Show();//显示异常信息}system("PAUSE");//调用库函数system()return0;//返回值0,返回操作系统}五、测试与结论输入表达式：-2*〔3+5〕+2^3/4=输入表达式：2^4/8–(+2+8)%3=从上面的屏幕显示，可知本程序满足课程设计的根本要求。六、课程设计总结尝试一下，看看自己究竟怎么样，由于以前上机的时候做过一个这样的简单程序，但是只能求整数，并且是要求个位数，我就想改编一下，把它的功能增加一些，完善一些，可以计算小数，可以计算乘方的，在吃饭的时候我就想怎么解决小数的问题，最后想通了，不就是一个字符串的处理吗，字符串的处理我还了解一些，于是就很快乐，认为成功在即，回去就开电脑，按照我的想法实现，想法是对的，但在编程中还有一些实际问题，细节问题，我都一次一次测试，改良，一点一点解决问题，最终解决了，我可能很喜欢完美吧，又把程序的一些细节改了一下，更加人性化，更加健壮，程序的风格也改良了一下，做完又是1点多钟，晚上的编程效率还可以，比拟安静，比拟集中精力。本想编一个开方程序的，但是开方符号的作用范围实在不好控制，于是作罢以后再编，本程序很多人都编了，但我的力求与别人不一样，力求比别人的功能更多，力求创新！这样的感觉真好，并且做出来了！感觉调试程序是一个很有趣的事情，对程序的结构，流程有了更加深入的了解。2.停车场管理问题描述假设停车场只有一个可停放几辆车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达的先后顺序依次排序，如果车场内已停满车，那么后进来的汽车只能在门外的便道上等候，一旦停车场内有车开走，排在便道上的第一辆车即可进入；当停车场内的某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该车辆开出大门后，为它让路的车辆再按原次序进入停车场。每辆汽车在离开时，都要依据停留时间交费〔从进入便道开始计时〕。在这里假设汽车从便道上开走时不收取任何费用，试设计这样一个停车场管理程序。根本要求汽车的输入信息格式为〔到达/离去的标识，汽车牌照号码，到达/离去的时刻〕对于不合理的输入信息应提供适当的提示信息，要求离开的汽车没在停车场或便道时可显示“此车未在停车场或便道上〞。工具/准备工作在开始做课程设计工程前，应回忆或复习相关内容。需要一台计算机，其内安装有MicrosoftVisualStudio2023的集成开发环境软件分析与实现源代码：//文件vehicle.h#ifndef_VEHICLETYPE_H_#define_VEHICLETYPE_H_structVehicleType{unsignedintnum;unsignedinttime;};#endif_VEHICLETYPE_H_//文件node.h此处node.h与第一个实验算术表达式求值的第三页node.h文件代码一样，即此处node.h也是第三页的node.h文件//文件lk_list.h#ifndef__LK_LIST_H__#define__LK_LIST_H__#include"utility.h"#include"node.h"template<classElemType>classLinkList{protected:Node<ElemType>*head;mutableintcurPosition;mutableNode<ElemType>*curPtr;intcount;Node<ElemType>*GetElemPtr(intposition)const;voidInit();public:LinkList();virtual~LinkList();intLength()const;boolEmpty()const;voidClear();voidTraverse(void(*visit)(constElemType&))const;intGetCurPosition()const;StatusCodeGetElem(intposition,ElemType&e)const;StatusCodeSetElem(intposition,constElemType&e);StatusCodeDelete(intposition,ElemType&e);StatusCodeInsert(intposition,constElemType&e);LinkList(constLinkList<ElemType>©);LinkList<ElemType>&operator=(constLinkList<ElemType>©);};template<classElemType>Node<ElemType>*LinkList<ElemType>::GetElemPtr(intposition)const{if(curPosition>position){curPosition=0;curPtr=head;}for(;curPosition<position;curPosition++)curPtr=curPtr->next;returncurPtr;}template<classElemType>voidLinkList<ElemType>::Init(){head=newNode<ElemType>;curPtr=head;curPosition=0;count=0;}template<classElemType>LinkList<ElemType>::LinkList(){Init();}template<classElemType>LinkList<ElemType>::~LinkList(){Clear();deletehead;}template<classElemType>intLinkList<ElemType>::Length()const{returncount;}template<classElemType>boolLinkList<ElemType>::Empty()const{returnhead->next==NULL;}template<classElemType>voidLinkList<ElemType>::Clear(){ElemTypetmpElem;while(Length()>0){Delete(1,tmpElem);}}template<classElemType>voidLinkList<ElemType>::Traverse(void(*visit)(constElemType&))const{for(Node<ElemType>*tmpPtr=head->next;tmpPtr!=NULL;tmpPtr=tmpPtr->next){(*visit)(tmpPtr->data);}}template<classElemType>intLinkList<ElemType>::GetCurPosition()const{returncurPosition;}template<classElemType>StatusCodeLinkList<ElemType>::GetElem(intposition,ElemType&e)const{if(position<1||position>Length()){returnNOT_PRESENT;}else{Node<ElemType>*tmpPtr;tmpPtr=GetElemPtr(position);e=tmpPtr->data;returnENTRY_FOUND;}}template<classElemType>StatusCodeLinkList<ElemType>::SetElem(intposition,constElemType&e){if(position<1||position>Length()){returnRANGE_ERROR;}else{Node<ElemType>*tmpPtr;tmpPtr=GetElemPtr(position);tmpPtr->data=e;returnSUCCESS;}}template<classElemType>StatusCodeLinkList<ElemType>::Delete(intposition,ElemType&e){if(position<1||position>Length()){returnRANGE_ERROR;}else{Node<ElemType>*tmpPtr;tmpPtr=GetElemPtr(position-1);Node<ElemType>*nextPtr=tmpPtr->next;tmpPtr->next=nextPtr->next;e=nextPtr->data;if(position==Length()){curPosition=0;curPtr=head;}else{curPosition=position;curPtr=tmpPtr->next;}count--;deletenextPtr;returnSUCCESS;}}template<classElemType>StatusCodeLinkList<ElemType>::Insert(intposition,constElemType&e){if(position<1||position>Length()+1){returnRANGE_ERROR;}else{Node<ElemType>*tmpPtr;tmpPtr=GetElemPtr(position-1);Node<ElemType>*newPtr;newPtr=newNode<ElemType>(e,tmpPtr->next);tmpPtr->next=newPtr;curPosition=position;curPtr=newPtr;count++;returnSUCCESS;}}template<classElemType>LinkList<ElemType>::LinkList(constLinkList<ElemType>©){intcopyLength=copy.Length();ElemTypee;Init();for(intcurPosition=1;curPosition<=copyLength;curPosition++){copy.GetElem(curPosition,e);Insert(Length()+1,e);}}template<classElemType>LinkList<ElemType>&LinkList<ElemType>::operator=(constLinkList<ElemType>©){if(©!=this){intcopyLength=copy.Length();ElemTypee;Clear();for(intcurPosition=1;curPosition<=copyLength;curPosition++){copy.GetElem(curPosition,e);Insert(Length()+1,e);}}return*this;}#endif//文件lk_stack.h此处lk_stack.h与第一个实验算术表达式求值的第三页lk_stack.h文件代码一样，即此处lk_stack.h也是第三页的lk_stack.h文件//文件utility.h#ifndef__UTILITY_H__#define__UTILITY_H__#include<string>#include<iostream>#include<limits>#include<cmath>#include<fstream>#include<cctype>#include<ctime>#include<cstdlib>#include<cstdio>#include<iomanip>#include<cstdarg>#include<cassert>usingnamespacestd;enumStatusCode{SUCCESS,FAIL,UNDER_FLOW,OVER_FLOW,RANGE_ERROR,DUPLICATE_ERROR,NOT_PRESENT,ENTRY_INSERTED,ENTRY_FOUND,VISITED,UNVISITED};#defineMAX_ERROR_MESSAGE_LEN100classError{private:charmessage[MAX_ERROR_MESSAGE_LEN];public:Error(charmes[]="一般性异常!"){strcpy(message,mes);}~Error(void){};voidShow()const{cout<<message<<endl;}};template<classElemType>voidWrite(constElemType&e){cout<<e.num<<e.time<<"";}#endif__UTILITY_H__//文件StoppingPlace.h#ifndef__STOPPING_PLACE_H__#define__STOPPING_PLACE_H__#include"Vehicle.h"#include"lk_list.h"//链表#include"lk_stack.h"//链栈ostream&operator<<(ostream&outStream,constVehicleType&vehicle);//停车场类classStoppingPlace{private://停车场类的数据成员:LinkStack<VehicleType>*pStopPath;//停车场的停车道LinkList<VehicleType>*pShortcutPath;//便道intmaxNumOfStopVehicle;//停车场的停车道停放车辆的最大数intrate;//停单位时间的收费值//辅助函数boolExistVehicleInStopPath(constVehicleType&vehicle)const;//停车场的停车道中是否存在车辆vehicleintLocateInpShortcutPath(constVehicleType&vehicle)const;//在便道中查找车辆vehicle的位置public://方法声明及重载编译系统默认方法声明:StoppingPlace(intn,intr);//构造函数virtual~StoppingPlace();//析构函数voidDisplayStatus()const;//显示停车道与便道中车辆状态voidArrive(constVehicleType&vehicle);//处理车辆到达的情形voidLeave(constVehicleType&vehicle);//处理车辆离开的情形};//停车场类及相关函数的实现局部ostream&operator<<(ostream&outStream,constVehicleType&vehicle){cout<<"("<<vehicle.num<<","<<vehicle.time<<")";returnoutStream;}boolStoppingPlace::ExistVehicleInStopPath(constVehicleType&vehicle)const{VehicleTypeve;//临时元素LinkStack<VehicleType>tmpS;//临时栈boolfound=false;//表示是否找到车辆while(!pStopPath->Empty()&&!found){//检查停车场的停车道的车辆pStopPath->Pop(ve);//车辆出栈tmpS.Push(ve);//车辆入临时栈if(vehicle.num==ve.num){//已找到车辆found=true;}}while(!tmpS.Empty()){//将临时栈中的车辆送回停车道pStopPathtmpS.Pop(ve);//车辆出栈pStopPath->Push(ve);//车辆入栈}returnfound;}intStoppingPlace::LocateInpShortcutPath(constVehicleType&vehicle)const{VehicleTypeve;//临时元素for(intpos=1;pos<=pShortcutPath->GetElem(pos,ve);pos++){//查找在便道中的车辆if(vehicle.num==ve.num){//已找到车辆returnpos;//返回车辆位置}}return0;//查找失败}StoppingPlace::StoppingPlace(intn,intr){pStopPath=newLinkStack<VehicleType>;//生成停车场的停车道pShortcutPath=newLinkList<VehicleType>;//生成便道maxNumOfStopVehicle=n;//停车场的停车道停放车辆的最大数rate=r;//停单位时间的收费值}StoppingPlace::~StoppingPlace(){deletepStopPath;//释放停车场的停车道deletepShortcutPath;//释放便道}voidStoppingPlace::DisplayStatus()const{cout<<"停车道中的车辆:";pStopPath->Traverse(Write);cout<<endl;cout<<"便道中的车辆:";pShortcutPath->Traverse(Write);cout<<endl<<endl;}voidStoppingPlace::Arrive(constVehicleType&vehicle){if(pStopPath->Length()<maxNumOfStopVehicle){//停车场未满pStopPath->Push(vehicle);//车辆进入停车场的停车道}else{//停车场已满pShortcutPath->Insert(pShortcutPath->Length()+1,vehicle);//车辆进入便道}}voidStoppingPlace::Leave(constVehicleType&vehicle){LinkStack<VehicleType>tmpS;//临时栈VehicleTypeve;//临时元素if(ExistVehicleInStopPath(vehicle)){//车辆在停车道中for(pStopPath->Pop(ve);vehicle.num!=ve.num;pStopPath->Pop(ve)){//在停车道中查找车辆tmpS.Push(ve);//车辆入栈}cout<<"在停车道中存在编号为"<<vehicle.num<<"的车辆"<<endl;cout<<"此车将离开,应收停车费"<<(vehicle.time-ve.time)*rate<<"元."<<endl;while(!tmpS.Empty()){//将临时栈中的车辆送回停车道pStopPathtmpS.Pop(ve);//车辆出栈pStopPath->Push(ve);//车辆入栈}if(!pShortcutPath->Empty()){//便道中有车辆pShortcutPath->Delete(1,ve);//取出便道中的第1辆车pStopPath->Push(ve);//将此车放到停车道中}}elseif(LocateInpShortcutPath(vehicle)!=0){//车辆在便道中intpos=LocateInpShortcutPath(vehicle);//车辆在便道中的位置cout<<"在便道中存在编号为"<<vehicle.num<<"的车辆"<<endl;cout<<"此车将离开,不收停车费."<<endl;pShortcutPath->Delete(pos,ve);//在便道中开走车辆}else{//在停车道与便道中无车辆vehiclecout<<"在停车道与便道中不存在编号为"<<vehicle.num<<"的车辆"<<endl;}}#endif#endif_STOPPINGPLACE_H_//文件main.cpp#include"lk_list.h"#include"lk_stack.h"#include"StoppingPlace.h"#include"utility.h"intmain(void){cout<<"输入停车道停车辆的最大数与停单位时间的收费值：";intmaxNumOfStop,cost;cin>>maxNumOfStop>>cost;StoppingPlacePtrStopping(maxNumOfStop,cost);try{while(1){cout<<"1.车辆到达"<<endl<<"2.车辆离开"<<endl<<"3.显示状态"<<endl<<"4.结束"<<endl<<"选择功能："<<endl;inti;cin>>i;switch(i){case1:cout<<"输入车辆编号与到达时间：";VehicleTypenew_ve;cin>>new_ve.num>>new_ve.time;PtrStopping.Arrive(new_ve);cout<<"1.车辆到达"<<endl<<"2.车辆离开"<<endl<<"3.显示状态"<<endl<<"4.结束"<<endl<<"选择功能："<<endl;break;case2:cout<<"输入车辆编号与离开时间：";VehicleTypenew_ve2;cin>>new_ve2.num>>new_ve2.time;PtrStopping.Leave(new_ve2);cout<<"1.车辆到达"<<endl<<"2.车辆离开"<<endl<<"3.显示状态"<<endl<<"4.结束"<<endl<<"选择功能："<<endl;break;case3:PtrStopping.DisplayStatus();cout<<"1.车辆到达"<<endl<<"2.车辆离开"<<endl<<"3.显示状态"<<endl<<"4.结束"<<endl<<"选择功能："<<endl;break;case4:exit(0);}}}catch(Errorerr){err.Show();}system("PAUSE");return0;}测试与结论测试时，应注意尽量覆盖算法的各种情况，屏幕显示如下：输入停车道停车辆的最大数与单位时间的收费值：32选择功能1，输入车辆编号与到达时间三次选择功能3，显示状态选择功能2，查看车辆编号，与应收停车费，结束。六、课程设计总结做的程序思维条理必须严密，在做程序时语言必须标准，在做完一个程序后需认真检查并补充缺乏之处。最后要仔细总结，积累经验。在课程设计的实验中，在收获知识的同时，还收获了阅历，收获了成熟，在此过程中，我们通过查找大量资料，请教老师，以及不懈的努力，不仅培养了独立思考、动手操作的能力，在各种其它能力上也都有了提高。更重要的是，在实验课上，我们学会了很多学习的方法。而这是日后最实用的，真的是受益匪浅。要面对社会的挑战，只有不断的学习、实践，再学习、再实践。压缩文件问题描述用哈夫曼编码设计一个压缩文件，能对输入的任何类型的文件进行哈夫曼编码，产生编码后的文件——压缩文件，也能对输入的压缩文件进行译码，生成压缩前的文件——解压文件。根本要求要求编码/译码效率尽可能高。工具/准备工作在开始做课程设计工程前，应回忆或复习相关内容。需要一台计算机，其内安装有MicrosoftVisualStudio2023的集成开发环境软件四、分析与实现源代码：//文件：utility.h#ifndef__UTILITY_H__//如果没有定义__UTILITY_H__#define__UTILITY_H__//那么定义__UTILITY_H__//ANSIC++标准库头文件#include<string>//标准串和操作#include<iostream>//标准流操作#include<limits>//极限#include<cmath>//数学函数#include<fstream>//文件输入输出#include<cctype>//字符处理#include<ctime>//日期和时间函数#include<cstdlib>//标准库#include<cstdio>//标准输入输出#include<iomanip>//输入输出流格式设置#include<cstdarg>//支持变长函数参数#include<cassert>//支持断言usingnamespacestd;//标准库包含在命名空间std中enumStatusCode{SUCCESS,FAIL,UNDER_FLOW,OVER_FLOW,RANGE_ERROR,DUPLICATE_ERROR,NOT_PRESENT,ENTRY_INSERTED,ENTRY_FOUND,VISITED,UNVISITED};#defineDEFAULT_SIZE1000//缺省元素个数charGetChar(istream&inStream=cin);template<classElemType>voidSwap(ElemType&e1,ElemType&e2);//交换e1,e2之值classError;//通用异常类charGetChar(istream&inStream){charch;//临时变量while((ch=(inStream).peek())!=EOF&&((ch=(inStream).get())=='’||ch=='\t'));returnch;//返回字符}#defineMAX_ERROR_MESSAGE_LEN100classError{private:charmessage[MAX_ERROR_MESSAGE_LEN];//异常信息public:Error(charmes[]="一般性异常!");//构造函数~Error(void){};//析构函数voidShow()const;//显示异常信息};Error::Error(char*mes){strcpy(message,mes);//复制异常信息}voidError::Show()const{cout<<message<<endl;//显示异常信息}template<classElemType>voidSwap(ElemType&e1,ElemType&e2){ElemTypetemp;//临时变量temp=e1;e1=e2;e2=temp;}#endif//文件：node.h此处node.h与第一个实验算术表达式求值的第三页node.h文件代码一样，即此处node.h也是第三页的node.h文件//文件：lk_list.h此处lk_list.h与第一个实验算术表达式求值的第14页lk_list.h文件代码一样，即此处lk_list.h也是第三页的lk_list.h文件//string.h#ifndef__STRING_H__#define__STRING_H__#include"lk_list.h"//线性链表classString{protected:mutablechar*strVal;intlength;public:String();virtual~String();String(constString©);String(constchar*copy);String(LinkList<char>©);intLength()const;boolEmpty()const;String&operator=(constString©);constchar*CStr()const;char&String::operator[](intpos)const;};StringRead(istream&input);StringRead(istream&input,char&terminalChar);voidWrite(constString&s);voidConcat(String&addTo,constString&addOn);voidCopy(String©,constString&original);voidCopy(String©,constString&original,intn);intIndex(constString&target,constString&pattern,intpos=0);StringSubString(constString&s,intpos,intlen);booloperator==(constString&first,constString&second);booloperator<(constString&first,constString&second);booloperator>(constString&first,constString&second);booloperator<=(constString&first,constString&second);booloperator>=(constString&first,constString&second);booloperator!=(constString&first,constString&second);String::String(){length=0;//串长度为0strVal=NULL;//空串}String::~String(){delete[]strVal;//释放串strVal}String::String(constString©){length=strlen(copy.CStr());//串长strVal=newchar[length+1];//分配存储空间strcpy(strVal,copy.CStr());//复制串值}String::String(constchar*copy){length=strlen(copy);//串长strVal=newchar[length+1];//分配存储空间strcpy(strVal,copy);//复制串值}String::String(LinkList<char>©){length=copy.Length();//串长strVal=newchar[length+1];//分配存储空间for(inti=0;i<length;i++){//复制串值copy.GetElem(i+1,strVal[i]);}strVal[length]='\0';//串值以'\0'结束}intString::Length()const{returnlength;}boolString::Empty()const{returnlength==0;}String&String::operator=(constString©){if(©!=this){delete[]strVal;//释放原串存储空间length=strlen(copy.CStr());//串长strVal=newchar[length+1];//分配存储空间strcpy(strVal,copy.CStr());//复制串值}return*this;}constchar*String::CStr()const{return(constchar*)strVal;//串值类型转换}char&String::operator[](intpos)const{returnstrVal[pos];}voidConcat(String&addTo,constString&addOn){constchar*cFirst=addTo.CStr();//指向第一个串constchar*cSecond=addOn.CStr();//指向第二个串char*copy=newchar[strlen(cFirst)+strlen(cSecond)+1];strcpy(copy,cFirst);//复制第一个串strcat(copy,cSecond);//连接第二个串addTo=copy;//串赋值delete[]copy;//释放copy}StringRead(istream&input){LinkList<char>temp;//临时线性表intsize=0;//初始线性表长度charc;//临时字符while((c=input.peek())!=EOF&&(c=input.get())!='\n'){//将输入的字符追加线性表中temp.Insert(++size,c);}Stringanswer(temp);//构造串returnanswer;//返回串}StringRead(istream&input,char&terminalChar){LinkList<char>temp;//临时线性表intsize=0;//初始线性表长度charc;//临时字符while((c=input.peek())!=EOF&&(c=input.get())!='\n'){//将输入的字符追加线性表中temp.Insert(++size,c);}terminalChar=c;//用terminalChar返回串结束字符Stringanswer(temp);//构造串returnanswer;//返回串}voidWrite(constString&s){cout<<s.CStr()<<endl;//输出串值}voidCopy(String©,constString&original){constchar*cOriginal=original.CStr();//初始串char*cCopy=newchar[strlen(cOriginal)+1];//分配存储空间strcpy(cCopy,cOriginal);//复制串copy=cCopy;//串赋值delete[]cCopy;//释放串cCopy}voidCopy(String©,constString&original,intn){constchar*cOriginal=original.CStr();//初始串intlen=(int)strlen(cOriginal)<n?(int)strlen(cOriginal):n;char*cCopy=newchar[len+1];//分配存储空间strncpy(cCopy,cOriginal,n);//复制串cCopy[len]='\0';//串值以'\0'结束copy=cCopy;//串赋值delete[]cCopy;//释放串cCopy}intIndex(constString&target,constString&pattern,intpos){constchar*cTarget=target.CStr();//目标串constchar*cPattern=pattern.CStr();//模式串constchar*ptr=strstr(cTarget+pos,cPattern);//模式匹配if(ptr==NULL){//匹配失败return-1;}else{//匹配成功returnptr-cTarget;}}StringSubString(constString&s,intpos,intlen){if(0<=pos&&pos<s.Length()&&0<=len){//返回串s的第pos个字符开始的长度为len的子串len=(len<s.Length()-pos)?len:(s.Length()-pos);char*sub=newchar[len+1];//分配存储空间constchar*str=s.CStr();//生成C风格串strncpy(sub,str+pos,len);//复制串sub[len]='\0';//串值以'\0'结束Stringtem(sub);//生成串对象returntem;}else{//返回空串Stringtem("");//生成空串对象returntem;}}booloperator==(constString&first,constString&second){returnstrcmp(first.CStr(),second.CStr())==0;}booloperator<(constString&first,constString&second){returnstrcmp(first.CStr(),second.CStr())<0;}booloperator>(constString&first,constString&second){returnstrcmp(first.CStr(),second.CStr())>0;}booloperator<=(constString&first,constString&second){returnstrcmp(first.CStr(),second.CStr())<=0;}booloperator>=(constString&first,constString&second){returnstrcmp(first.CStr(),second.CStr())>=0;}booloperator!=(constString&first,constString&second){returnstrcmp(first.CStr(),second.CStr())!=0;}#endif//文件：min_priority_heap_queue.h#ifndef__MIN_PRIORITY_HEAP_QUEUE__H__#define__MIN_PRIORITY_HEAP_QUEUE__H__template<classElemType>classMinPriorityHeapQueue{protected:ElemType*elem;//存储堆的数组intsize;//堆最大元素个数intcount;//堆元素个数voidInit(intsz);//初始化优先队列voidSiftAdjust(intlow,inthigh);voidBuildHeap();//建立堆public:MinPriorityHeapQueue(intsz=DEFAULT_SIZE);MinPriorityHeapQueue(ElemTypee[],intcnt=0,intsz=DEFAULT_SIZE);virtual~MinPriorityHeapQueue();//析构函数intLength