四川大學計算機學院數(shù)據結構與算法分析實驗報告

《數(shù)據結構與算法》課程設計指導老師：班級：姓名：學號：算術表達式求值問題描述從鍵盤上輸入中綴算數(shù)表達式，包括括號，計算粗話表達式的值。二、根本要求程序對所輸出的表達式做出簡單的判斷，如表達式有錯，能給出適當?shù)奶崾灸芴幚韱文窟\算符：+和—三、工具/準備工作在開始做課程設計工程前，應回憶或復習相關內容。需要一臺計算機，其內安裝有MicrosoftVisualStudio2023的集成開發(fā)環(huán)境軟件四、分析與實現(xiàn)對中綴表達式，一般運算規(guī)那么如下：先乘方，再乘除，最后加減同級運算從左算到右先算括號內，再算括號外根據實踐經驗，可以對運算符設置統(tǒng)一的優(yōu)先級，從而方便比擬。如下表：運算符=〔〕+-*/%^優(yōu)先級12345單目運算符：+，—〔可以看成0+/—個數(shù)〕雙目運算符：+，—〔在+或—的前一個字符〔當前一個不是運算符時，規(guī)定用‘0’表示〕〕為‘=’，‘〔’，那么為單目運算符。具體實現(xiàn)算法時，可設置兩個工作棧，一個為操作符棧optr(operator),另一個為操作數(shù)棧opnd(operand),算法根本工作思路如下：將optr棧和opnd棧清空，在optr棧中參加一個‘=’從輸入流獲取一字符ch，循環(huán)執(zhí)行〔3〕~〔5〕直到求出表達式的值為止。取出optr的棧頂optrTop，當optrTop=‘=’且ch=‘=’時，整個表達式求值完畢，這時opnd棧頂元素為表達式的值。假設ch不是操作符，那么將字符放回輸入流〔cin.putback〕，讀操作數(shù)operand；將operand參加opnd棧，讀入下一個字符ch。假設ch是操作符，按如下方式進行處理如果ch為單目運算符，那么在ch前面加上操作數(shù)0，也就是將0入opnd棧。如果optrTop與ch不匹配，例如optrTop=’〕’且ch=‘〔’,顯示錯誤信息。如果optrTop=‘〔’且ch=‘〕’，那么從optr棧退出棧頂?shù)摹病?，去括號，然后從輸入流中讀入字符并送入ch如果ch=‘〔’或optrTop比ch的優(yōu)先級低，那么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"http://鏈棧類//計算器類template<classElemType>classCalculator{private:LinkStack<ElemType>opnd;//操作數(shù)棧LinkStack<char>optr;//操作符棧intOperPrior(charop);//操作符優(yōu)先級voidGet2Operands(ElemType&left,ElemType&right);ElemTypeOperate(ElemTypeleft,charop,ElemTyperight);boolIsOperator(charch);//判斷ch是否為操作符public:Calculator(){};//無參數(shù)的構造函數(shù)virtual~Calculator(){};//析構函數(shù)voidRun();//運算表達式};template<classElemType>intCalculator<ElemType>::OperPrior(charop){intprior;//優(yōu)先級if(op=='=')prior=1;//=優(yōu)先級為1elseif(op=='('||op==')')prior=2;//(優(yōu)先級為2elseif(op=='+'||op=='-')prior=3;//+-優(yōu)先級為3elseif(op=='*'||op=='/'||op=='%')prior=4;//*/%優(yōu)先級為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("除數(shù)為零!");elseif(op=='/'&&right!=0)result=left/right;elseif(op=='%'&&(long)right==0)throwError("除數(shù)為零!");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;//操作數(shù)charop;//操作符priorChar='=';//前一字符ch=GetChar();//讀入一個字符if(optr.Top(optrTop)==UNDER_FLOW)throwError("表達式有錯!");//拋出異常//取出optr棧的棧頂while(optrTop!='='||ch!='='){//當前表達式還未運算結束,繼續(xù)運算if(isdigit(ch)||ch=='.'){//ch為一個操作數(shù)的第1個字符cin.putback(ch);//將字符ch放回輸入流cin>>operand;//讀入操作數(shù)opnd.Push(operand);//操作數(shù)入opnd棧priorChar='0';//前一字符不是操作符,規(guī)定前一字符為'0'ch=GetChar();//讀入下一個字符}elseif(!IsOperator(ch)){//既不是操作符,也不屬于操作數(shù)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的優(yōu)先級低optr.Push(ch);//ch入optr棧priorChar=ch;//新的前一字符為chch=GetChar();//讀入新字符}else{//optrTop的大于或等于ch的優(yōu)先級if(optr.Pop(op)==UNDER_FLOW)throwError("表達式有錯!");ElemTypeleft,right;//操作數(shù)Get2Operands(left,right);//從opnd棧中取操作數(shù)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>//數(shù)學函數(shù)#include<fstream>//文件輸入輸出#include<cctype>//字符處理#include<ctime>//日期和時間函數(shù)#include<cstdlib>//標準庫#include<cstdio>//標準輸入輸出#include<iomanip>//輸入輸出流格式設置#include<cstdarg>//支持變長函數(shù)參數(shù)#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()函數(shù)從輸入流中接受1//字符,流的當前位置不變)&&((ch=(inStream).get())==''//空格(get()函數(shù)從輸入流中接受1字符,流//的當前位置向后移1個位置)||ch=='\t'));//制表符returnch;//返回字符}boolUserSaysYes(){charch;//用戶答復字符boolinitialResponse=true;//初始答復do{//循環(huán)直到用戶輸入恰當?shù)拇饛蜑橹筰f(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[]="一般性異常!");//構造函數(shù)~Error(void){};//析構函數(shù)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"http://順序表類#include"calculator.h"http://計算器類intmain(void){try//用try封裝可能出現(xiàn)異常的代碼{do{cout<<"輸入一個表達式:"<<endl;Calculator::Run();//表達式求值cout<<"是否繼續(xù)";}while(UserSaysYes());}catch(Errorerr)//捕捉并處理異常{err.Show();//顯示異常信息}system("PAUSE");//調用庫函數(shù)system()return0;//返回值0,返回操作系統(tǒng)}五、測試與結論輸入表達式：-2*〔3+5〕+2^3/4=輸入表達式：2^4/8–(+2+8)%3=從上面的屏幕顯示，可知本程序滿足課程設計的根本要求。六、課程設計總結嘗試一下，看看自己究竟怎么樣，由于以前上機的時候做過一個這樣的簡單程序，但是只能求整數(shù)，并且是要求個位數(shù)，我就想改編一下，把它的功能增加一些，完善一些，可以計算小數(shù)，可以計算乘方的，在吃飯的時候我就想怎么解決小數(shù)的問題，最后想通了，不就是一個字符串的處理嗎，字符串的處理我還了解一些，于是就很快樂，認為成功在即，回去就開電腦，按照我的想法實現(xiàn)，想法是對的，但在編程中還有一些實際問題，細節(jié)問題，我都一次一次測試，改良，一點一點解決問題，最終解決了，我可能很喜歡完美吧，又把程序的一些細節(jié)改了一下，更加人性化，更加健壯，程序的風格也改良了一下，做完又是1點多鐘，晚上的編程效率還可以，比擬安靜，比擬集中精力。本想編一個開方程序的，但是開方符號的作用范圍實在不好控制，于是作罷以后再編，本程序很多人都編了，但我的力求與別人不一樣，力求比別人的功能更多，力求創(chuàng)新！這樣的感覺真好，并且做出來了！感覺調試程序是一個很有趣的事情，對程序的結構，流程有了更加深入的了解。2.停車場管理問題描述假設停車場只有一個可停放幾輛車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內按車輛到達的先后順序依次排序，如果車場內已停滿車，那么后進來的汽車只能在門外的便道上等候，一旦停車場內有車開走，排在便道上的第一輛車即可進入；當停車場內的某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該車輛開出大門后，為它讓路的車輛再按原次序進入停車場。每輛汽車在離開時，都要依據停留時間交費〔從進入便道開始計時〕。在這里假設汽車從便道上開走時不收取任何費用，試設計這樣一個停車場管理程序。根本要求汽車的輸入信息格式為〔到達/離去的標識，汽車牌照號碼，到達/離去的時刻〕對于不合理的輸入信息應提供適當?shù)奶崾拘畔?，要求離開的汽車沒在停車場或便道時可顯示“此車未在停車場或便道上〞。工具/準備工作在開始做課程設計工程前，應回憶或復習相關內容。需要一臺計算機，其內安裝有MicrosoftVisualStudio2023的集成開發(fā)環(huán)境軟件分析與實現(xiàn)源代碼：//文件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"http://鏈表#include"lk_stack.h"http://鏈棧ostream&operator<<(ostream&outStream,constVehicleType&vehicle);//停車場類classStoppingPlace{private://停車場類的數(shù)據成員:LinkStack<VehicleType>*pStopPath;//停車場的停車道LinkList<VehicleType>*pShortcutPath;//便道intmaxNumOfStopVehicle;//停車場的停車道停放車輛的最大數(shù)intrate;//停單位時間的收費值//輔助函數(shù)boolExistVehicleInStopPath(constVehicleType&vehicle)const;//停車場的停車道中是否存在車輛vehicleintLocateInpShortcutPath(constVehicleType&vehicle)const;//在便道中查找車輛vehicle的位置public://方法聲明及重載編譯系統(tǒng)默認方法聲明:StoppingPlace(intn,intr);//構造函數(shù)virtual~StoppingPlace();//析構函數(shù)voidDisplayStatus()const;//顯示停車道與便道中車輛狀態(tài)voidArrive(constVehicleType&vehicle);//處理車輛到達的情形voidLeave(constVehicleType&vehicle);//處理車輛離開的情形};//停車場類及相關函數(shù)的實現(xiàn)局部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>;//生成便道m(xù)axNumOfStopVehicle=n;//停車場的停車道停放車輛的最大數(shù)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<<"輸入停車道停車輛的最大數(shù)與停單位時間的收費值：";intmaxNumOfStop,cost;cin>>maxNumOfStop>>cost;StoppingPlacePtrStopping(maxNumOfStop,cost);try{while(1){cout<<"1.車輛到達"<<endl<<"2.車輛離開"<<endl<<"3.顯示狀態(tài)"<<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.顯示狀態(tài)"<<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.顯示狀態(tài)"<<endl<<"4.結束"<<endl<<"選擇功能："<<endl;break;case3:PtrStopping.DisplayStatus();cout<<"1.車輛到達"<<endl<<"2.車輛離開"<<endl<<"3.顯示狀態(tài)"<<endl<<"4.結束"<<endl<<"選擇功能："<<endl;break;case4:exit(0);}}}catch(Errorerr){err.Show();}system("PAUSE");return0;}測試與結論測試時，應注意盡量覆蓋算法的各種情況，屏幕顯示如下：輸入停車道停車輛的最大數(shù)與單位時間的收費值：32選擇功能1，輸入車輛編號與到達時間三次選擇功能3，顯示狀態(tài)選擇功能2，查看車輛編號，與應收停車費，結束。六、課程設計總結做的程序思維條理必須嚴密，在做程序時語言必須標準，在做完一個程序后需認真檢查并補充缺乏之處。最后要仔細總結，積累經驗。在課程設計的實驗中，在收獲知識的同時，還收獲了閱歷，收獲了成熟，在此過程中，我們通過查找大量資料，請教老師，以及不懈的努力，不僅培養(yǎng)了獨立思考、動手操作的能力，在各種其它能力上也都有了提高。更重要的是，在實驗課上，我們學會了很多學習的方法。而這是日后最實用的，真的是受益匪淺。要面對社會的挑戰(zhàn)，只有不斷的學習、實踐，再學習、再實踐。壓縮文件問題描述用哈夫曼編碼設計一個壓縮文件，能對輸入的任何類型的文件進行哈夫曼編碼，產生編碼后的文件——壓縮文件，也能對輸入的壓縮文件進行譯碼，生成壓縮前的文件——解壓文件。根本要求要求編碼/譯碼效率盡可能高。工具/準備工作在開始做課程設計工程前，應回憶或復習相關內容。需要一臺計算機，其內安裝有MicrosoftVisualStudio2023的集成開發(fā)環(huán)境軟件四、分析與實現(xiàn)源代碼：//文件：utility.h#ifndef__UTILITY_H__//如果沒有定義__UTILITY_H__#define__UTILITY_H__//那么定義__UTILITY_H__//ANSIC++標準庫頭文件#include<string>//標準串和操作#include<iostream>//標準流操作#include<limits>//極限#include<cmath>//數(shù)學函數(shù)#include<fstream>//文件輸入輸出#include<cctype>//字符處理#include<ctime>//日期和時間函數(shù)#include<cstdlib>//標準庫#include<cstdio>//標準輸入輸出#include<iomanip>//輸入輸出流格式設置#include<cstdarg>//支持變長函數(shù)參數(shù)#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//缺省元素個數(shù)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[]="一般性異常!");//構造函數(shù)~Error(void){};//析構函數(shù)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"http://線性鏈表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;//存儲堆的數(shù)組intsize;//堆最大元素個數(shù)intcount;//堆元素個數(shù)voidInit(intsz);//初始化優(yōu)先隊列voidSiftAdjust(intlow,inthigh);voidBuildHeap();//建立堆public:MinPriorityHeapQueue(intsz=DEFAULT_SIZE);MinPriorityHeapQueue(ElemTypee[],intcnt=0,intsz=DEFAULT_SIZE);virtual~MinPriorityHeapQueue();//析構函數(shù)intLength