數(shù)據(jù)結(jié)構(gòu)第三章

第三章第三章棧和隊(duì)列從數(shù)據(jù)結(jié)構(gòu)的角度看:從數(shù)據(jù)類型的角度看:它們和線性表相同它們和線性表不同線性表Insert(L,i,x)(1<i<n+1)Delete(L,i)(1<i<n)棧Insert(S,n+1,x)隊(duì)列Insert(Q,n+1,x)Delete(S,n)Delete(Q,1)3.1棧的類型定義ADTStack{數(shù)據(jù)對(duì)象：D={a.Ia.EElemSet,i=1,2,...,n,n弟}數(shù)據(jù)關(guān)系：R1={<a],ai>|曲,乎。i=2,...,n}約定a端為棧頂，a1端為棧底。基本操作：nInitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。DestroyStack(&S)初始條件：棧S已存在。操作結(jié)果：棧S被銷毀。ClearStack(&S)初始條件：棧S已存在。操作結(jié)果：將S清為空棧。StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALE。StackLength(S)初始條件：棧S已存在。操作結(jié)果：返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度。GetTop(S,&e)初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。Push(&S,e)初始條件：棧S已存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop(&S,&e)初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e返回其值。}ADTStack3.2棧的應(yīng)用舉例例一、數(shù)制轉(zhuǎn)換十進(jìn)制數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題，其解決方法很多，其中一個(gè)簡(jiǎn)單算法基于下列原理：N=(Ndivd)xd+Nmodd(其中：div為整除運(yùn)算，mod為求余運(yùn)算)例如：(1348)10=(2504)8，其運(yùn)算過程如下:NNdiv8Nmod8TOC\o"1-5"\h\z134816841682102125202假設(shè)現(xiàn)要編制一個(gè)滿足下列要求的程序：對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)。由于上述計(jì)算過程是從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個(gè)數(shù)位，而打印輸出，一般來說應(yīng)從高位到低位進(jìn)行，恰好和計(jì)算過程相反。因此，若將計(jì)算過程中得到的八進(jìn)制數(shù)的各位順序進(jìn)棧，則按出棧序列打印輸出的即為與輸入對(duì)應(yīng)的八進(jìn)制數(shù)。voidconversion(){//對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出//與其等值的八進(jìn)制數(shù)InitStack(S);//構(gòu)造空棧scanf("%d",N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf("%d",e);}}//conversion這是利用棧的后進(jìn)先出特性的最簡(jiǎn)單的例子。在這個(gè)例子中，棧操作的序列是直線式的，即先一味地入棧，然后一味地出棧。也許，有的讀者會(huì)提出疑問：用數(shù)組直接實(shí)現(xiàn)不也很簡(jiǎn)單嗎？仔細(xì)分析上述算法不難看出，棧的引入簡(jiǎn)化了程序設(shè)計(jì)的問題，劃分了不同的關(guān)注層次，使思考范圍縮小了。而用數(shù)組不僅掩蓋了問題的本質(zhì)，還要分散精力去考慮數(shù)組下標(biāo)增減等細(xì)節(jié)問題。例二、括號(hào)匹配的檢驗(yàn)假設(shè)表達(dá)式中允許包含兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，即([]())或[([][])]等為正確的格式，[(])或([())或(()])均為不正確的格式。檢驗(yàn)括號(hào)是否匹配的方法可用"期待的急迫程度"這個(gè)概念來描述。例如考慮下列括號(hào)序列：[([][])]12345678分析可能出現(xiàn)的不匹配的情況：1)到來的右括弧非是所期待的；2)到來的是不速之客;3)直到結(jié)束，也沒有到來所期待的。statusmatching(string&exp){//檢驗(yàn)表達(dá)式中所含括弧是否正確嵌套，若是，則返回//OK，否則返回ERRORintstate=1;while(i<=length(exp)&&state){swithofexp[i]{case左括弧:{Push(S,exp[i]);i++;break;}case")":{if(NOTStackEmpty(S)&&GetTop(S)="("){Pop(S,e);i++;}else{state=0}break;}……}if(state&&StackEmpty(S))returnOKelsereturnERROR;例三、行編輯程序問題一個(gè)簡(jiǎn)單的行編輯程序的功能是：接受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。每接受一個(gè)字符即存入用戶數(shù)據(jù)區(qū)”不恰當(dāng)。較好的做法是，設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。例如，可用一個(gè)退格符#表示前一個(gè)字符無效；可用一個(gè)退行符@，表示當(dāng)前行中的字符均無效。例如，假設(shè)從終端接受了這樣兩行字符：whli##ilr#e(s#*s)outcha@putchar(*s=#++);則實(shí)際有效的是下列兩行：while(*s)putchar(*s++);voidLineEdit()(//利用字符棧S，從終端接收一行并傳送至調(diào)用過程//的數(shù)據(jù)區(qū)。InitStack(S);〃構(gòu)造空棧Sch=getchar();〃從終端接收第一個(gè)字符while(ch!=EOF){//EOF為全文結(jié)束符while(ch!=EOF&&ch!='\n'){switch(ch){case'#':Pop(S,c);break;//僅當(dāng)棧非空時(shí)退棧case'@':ClearStack(S);break;//重置S為空棧default:Push(S,ch);break;//有效字符進(jìn)棧，未考慮棧滿情形}ch=getchar();//從終端接收下一個(gè)字符}將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；ClearStack(S);//重置S為空棧if(ch!=EOF)ch=getchar();}DestroyStack(S);例四、迷宮求解求迷宮中從入口到出口的所有路徑是一個(gè)經(jīng)典的程序設(shè)計(jì)問題。由于計(jì)算機(jī)解迷宮時(shí)，通常用的是“窮舉求解”的方法，即從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，在求迷宮通路的算法中應(yīng)用棧也就是自然而然的事了。假設(shè)迷宮如下圖所示:###########T]#$$$###J#$$$###J—$$####J######TTJ#####TT、L#######、L####TTT0###########假設(shè)“當(dāng)前位置”指的是在搜索過程中某一時(shí)刻所在圖中某個(gè)方塊位置，則求迷宮中一條路徑的算法的基本思想是：若當(dāng)前位置"可通",則納入"當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當(dāng)前位置”，如此重復(fù)直至到達(dá)出口；若當(dāng)前位置“不可通”，則應(yīng)順著“來向”退回到“前一通道塊，，，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周四個(gè)方塊均“不可通，，，則應(yīng)從“當(dāng)前路徑，，上刪除該通道塊。所謂“下一位置，，指的是“當(dāng)前位置，，四周四個(gè)方向（東、南、西、北）上相鄰的方塊。假設(shè)以棧S記錄“當(dāng)前路徑，則棧頂中存放的是“當(dāng)前路徑上最后一個(gè)通道塊，，。由此，“納入路徑，，的操作即為“當(dāng)前位置入棧，七“從當(dāng)前路徑上刪除前一通道塊，，的操作即為“出棧，求迷宮中一條從入口到出口的路徑的算法可簡(jiǎn)單描述如下：設(shè)定當(dāng)前位置的初值為入口位置；do{若當(dāng)前位置可通，則{將當(dāng)前位置插入棧頂；//納入路徑若該位置是出口位置，則結(jié)束；//求得路徑存放在棧中否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；}否則{若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為：沿順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則{刪去棧頂位置；//從路徑中刪去該通道塊若棧不空，則重新測(cè)試新的棧頂位置，直至找到一個(gè)可通的相鄰塊或出棧至?？眨粆}while（棧不空）；在此，尚需說明一點(diǎn)的是，所謂當(dāng)前位置可通，指的是未曾走到過的通道塊，即要求該方塊位置不僅是通道塊，而且既不在當(dāng)前路徑上(否則所求路徑就不是簡(jiǎn)單路徑)，也不是曾經(jīng)納入過路徑后又從路徑上刪除的通道塊(否則只能在死胡同內(nèi)轉(zhuǎn)圈)。typedefstruct{intord;//通道塊在路徑上的序號(hào)PosTypeseat;//通道塊在迷宮中的坐標(biāo)位置intdi;//從此通道塊走向下一通道塊的方向}SElemType;//棧的元素類型StatusMazePath(MazeTypemaze,PosTypestart,PosTypeend){//若迷宮maze中從入口start到出口end的通道，//則求得一條存放在棧中(從棧底到棧頂)，并返回//TRUE;否則返回FALSEInitStack(S);curpos=start;//設(shè)定當(dāng)前位置為入口位置curstep=1;//探索第一步do{if(Pass(curpos)){//當(dāng)前位置可以通過，即是未曾走到過的通道塊FootPrint(curpos);//留下足跡e=(curstep,curpos,1);Push(S,e);//加入路徑if(curpos==end)return(TRUE);//到達(dá)終點(diǎn)(出口)curpos=NextPos(curpos,1);/下一位置是當(dāng)前位置的東鄰curstep++;//探索下一步}else{//當(dāng)前位置不能通過if(!StackEmpty(S)){Pop(S,e);while(e.di==4&&!StackEmpty(S)){MarkPrint(e.seat);Pop(S,e);//留下不能通過的標(biāo)記，并退回一步}//whileif(e.di<4){e.di++;Push(S,e);〃換下一個(gè)方向探索curpos=NextPos(curpos,e.di);//設(shè)定當(dāng)前位置是該新方向上的相鄰塊}//if}//if}//else}while(!StackEmpty(S));return(FALSE);}//MazePath例五、表達(dá)式求值限于二元運(yùn)算符的表達(dá)式定義：表達(dá)式：:=（操作數(shù)）+（運(yùn)算符）+（操作數(shù)）操作數(shù)：:=簡(jiǎn)單變量I表達(dá)式簡(jiǎn)單變量::=標(biāo)識(shí)符|無符號(hào)整數(shù)在計(jì)算機(jī)中，表達(dá)式可以有三種不同的標(biāo)識(shí)方法設(shè)Exp=S1+OP+S2則稱OP+S1+S2為表達(dá)式的前綴表示法稱S1+OP+S2為表達(dá)式的中綴表示法稱S1+S2+OP為表達(dá)式的后綴表示法可見，它以運(yùn)算符所在不同位置命名的。例如:Exp=axb+（c一d/e）xf前綴式：+xabx-c/def中綴式：axb+c一d/exf后綴式：abxcde/-fx+結(jié)論：1）1）操作數(shù)之間的相對(duì)次序不變；2）2）運(yùn)算符的相對(duì)次序不同；3）3）中綴式丟失了括弧信息，致使運(yùn)算的次序不確定；4）4）前綴式的運(yùn)算規(guī)則為:連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式；5）5）后綴式的運(yùn)算規(guī)則為：?運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序；?每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式；?如何從后綴式求值？先找運(yùn)算符，后找操作數(shù)?如何從原表達(dá)式求得后綴式？分析原表達(dá)式和后綴式中的運(yùn)算符：原表達(dá)式：a+bxc-d/exf后綴式：abcx+de/fx-運(yùn)算符#（+-x/?*優(yōu)先數(shù)-1011223每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來定，若當(dāng)前運(yùn)算符的優(yōu)先數(shù)小，則暫不進(jìn)行；否則立即進(jìn)行。表達(dá)式求值的規(guī)則：1)設(shè)立運(yùn)算符棧和操作數(shù)棧；2)設(shè)表達(dá)式的結(jié)束符為#，予設(shè)運(yùn)算符棧的棧底為#3)若當(dāng)前字符是操作數(shù)，則進(jìn)操作數(shù)棧；4)若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧；5)否則，退出棧頂運(yùn)算符作相應(yīng)運(yùn)算；6)(對(duì)它之前后的運(yùn)算符起隔離作用，)可視為自相應(yīng)左括弧開始的表達(dá)式的結(jié)束符。算法描述如下：OperandTypeEvaluateExpression(){//算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)OPTR和OPND//分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OP為運(yùn)算符集合。InitStack(OPTR);Push(OPTR,'#');initStack(OPND);c=getchar();while(c!='#'IIGetTop(OPTR)!='#'){if(!In(c,OP)){Push((OPND,c);c=getchar();}//不是運(yùn)算符則進(jìn)棧elseswitch(precede(GetTop(OPTR),c){case'<'://棧頂元素優(yōu)先權(quán)低Push(OPTR,c);c=getchar();break;case'='://脫括號(hào)并接收下一字符Pop(OPTR,x);c=getchar();break;case'>'#//退棧并將運(yùn)算結(jié)果入棧Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression例六、實(shí)現(xiàn)遞歸在高級(jí)語(yǔ)言編制的程序中，調(diào)用函數(shù)與被調(diào)用函數(shù)之間的鏈接和信息交換必須通過棧例進(jìn)行。當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，需先完成三件事：1)將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存；2)為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)；3)將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成：1)保存被調(diào)函數(shù)的計(jì)算結(jié)果；2)釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)；3)依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是:后調(diào)用先返回此時(shí)的內(nèi)存管理實(shí)行“棧式管理”遞歸過程指向過程中占用的數(shù)據(jù)區(qū)，稱之為遞歸工作棧每一層的遞歸參數(shù)合成一個(gè)記錄，稱之為遞歸工作記錄棧頂記錄指示當(dāng)前層的執(zhí)行情況，稱之為當(dāng)前活動(dòng)記錄棧頂指針，稱之為當(dāng)前環(huán)境指針例如：voidhanoi(intn,charx,chary,charz)//將塔座x上按直徑由小到大且全上而下編號(hào)為1至n//的n個(gè)圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。{if(n==1)move(x,1,z);//將編號(hào)為1的圓盤從x移到zelse{hanoi(n-1,x,z,y);//將x上編號(hào)為1至n-1的圓//盤移到y(tǒng),z作輔助塔move(x,n,z);//將編號(hào)為n的圓盤從x移到zhanoi(n-1,y,x,z);//將y上編號(hào)為1至n-1的圓盤//移到z,x作輔助塔}}3.33.3棧類型的實(shí)現(xiàn)順序棧類似于線性表的順序映象實(shí)現(xiàn)，指向表尾的指針可以作為棧頂指針。鏈棧利用鏈表實(shí)現(xiàn)棧，注意鏈表中指針的方向是從棧頂?shù)綏５住?includeLinkList.htemplate<classElemType>classstack{private:List<ElemType>stackList;public://constructorstack(void);//accessmethodBOOLstackEmpty(void);intstackLength(void);ElemType*getTop(void);//modificationmethodvoidPush(ElemType*item);ElemType*Pop(void);voidclearStack(void);}；template<classElemType>voidstack<ElemType>::Push(ElemType*item){stackLisLinsFirst(item);}template<classElemType>ElemType*stack<ElemType>::Pop(void){ifstackList.listEmpty()returnNULL;elsereturnstackList.delFirst()}3.4隊(duì)列的類型定義ADTQueue{數(shù)據(jù)對(duì)象：D=伉|ai^ElemSet,i=1,2,...,n,n弟}數(shù)據(jù)關(guān)系：R1={<ai1,ai>|ai1,aiED,i=2,...,n}約定其中端為隊(duì)列頭，a端為隊(duì)列尾?；静僮鳎簄InitQueue(&Q)操作結(jié)果構(gòu)造一個(gè)空隊(duì)列Q。DestroyQueue(&Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：隊(duì)列Q被銷毀，不再存在。ClearQueue(&Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：將Q清為空隊(duì)列。QueueEmpty(Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：若Q為空隊(duì)列，則返回TRUE,否則返回FALSE。QueueLength(Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度。GetHead(Q,&e)初始條件：Q為非空隊(duì)列。操作結(jié)果：用e返回Q的隊(duì)頭元素。EnQueue(&Q,e)初始條件：隊(duì)列Q已存在。操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。DeQueue(&Q,&e)初始條件：Q為非空隊(duì)列。操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。}ADTQueue3.5隊(duì)列類型的實(shí)現(xiàn)鏈隊(duì)列——鏈?zhǔn)接诚?includeLinkList.htemplate<classElemType>classQueue{private:List<ElemType>queueList;public://constructorQueue(void):queueList();~Queue(void)//accessmethodBOOLqueueEmpty(void){returnqueueList.listEmpty()}intqueueLength(void){returnqueueList.listSize()}ElemType*getHead(void);//modificationmethodvoidenQueue(ElemType*pitem);ElemType*deQueue(void);voidclearQueue(void);};template<classElemType>voidQueue<ElemType>::enQueue(ElemType*pitem){queueList.addTail(pitem);}template<classElemType>ElemType*QueuevElemType*deQueue(void){ifqueueList.listEmpty()returnNULL;elsereturnqueueList.delFirst()}循環(huán)隊(duì)列——順序映象constintMaxQSize=100;template<classElemType>classQueue{private:intfront,rear,curSize,maxSize;ElemType*qList;public://constructorQueue(void);~Queue(void)//accessmethodBOOLqueueEmpty(void);BOOLqueueFULL(void);intqueueLength(void);ElemType*getHead(void);//modificationmethodvoidenQueue(ElemType*item);ElemType*deQueue(void);voidclearQueue(void);}；3.6隊(duì)列應(yīng)用舉例一一排隊(duì)問題的系統(tǒng)仿真一、需求分析和規(guī)格說明編制一個(gè)事件驅(qū)動(dòng)仿真程序以模擬理發(fā)館內(nèi)一天的活動(dòng)，要求輸出在一天的營(yíng)業(yè)時(shí)間內(nèi)，到達(dá)的顧客人數(shù)、顧客在館內(nèi)的平均逗留時(shí)間和排隊(duì)等候理發(fā)的平均人數(shù)以及在營(yíng)業(yè)時(shí)間內(nèi)空椅子的平均數(shù)。假設(shè)理發(fā)館內(nèi)設(shè)有N把理發(fā)椅，一天內(nèi)連續(xù)營(yíng)業(yè)T小時(shí)。在T小時(shí)內(nèi)顧客到達(dá)的時(shí)間及顧客理發(fā)所需時(shí)間均隨機(jī)生成，過了營(yíng)業(yè)時(shí)間，不再有顧客進(jìn)門，但仍需繼續(xù)為已進(jìn)入店內(nèi)的顧客理發(fā)，直至最后一名顧客離開為止。二、概要設(shè)計(jì)主程序?yàn)椋簐oidBarberShop_Simulation(intchairNum,intCloseTime){//理發(fā)店業(yè)務(wù)模擬，統(tǒng)計(jì)一天內(nèi)顧客在店內(nèi)逗留的平均時(shí)間//和顧客在等待理發(fā)時(shí)排隊(duì)的平均長(zhǎng)度以及空椅子的平均數(shù)OpenForDay;//初始化whileMoreEventdo{EventDrived(OccurTime,EventType);//事件驅(qū)動(dòng)switch(EventType){case'A':CustomerArrived;break;//處理到達(dá)事件case'D':CustomerDeparture;break;//處理離開事件default:Invalid;}//switch}//whileCloseForDay;//計(jì)算平均逗留時(shí)間和排隊(duì)的平均長(zhǎng)度}//BarberShop_Simulation數(shù)據(jù)類型為：ADTEvent(事件){數(shù)據(jù)對(duì)象:D={事件的發(fā)生時(shí)刻，事件類型}數(shù)據(jù)關(guān)系：R={}基本操作：Initiate(&E,oT,eT);操作結(jié)果：產(chǎn)生一個(gè)發(fā)生時(shí)間為oT,事件類型為eT的事件E;GetOccurTime(ev);初始條件：事件ev已存在，操作結(jié)果：返回該事件的發(fā)生時(shí)間；GetEventType(ev);初始條件：事件ev已存在；操作結(jié)果：返回該事件的類型；ADTcustomer(顧客){數(shù)據(jù)對(duì)象:D={進(jìn)門時(shí)刻，理發(fā)所需時(shí)間};數(shù)據(jù)關(guān)系：R={}基本操作：Initiate(&P,aT,cT);操作結(jié)果：產(chǎn)生一個(gè)進(jìn)門時(shí)刻為aT,理發(fā)時(shí)間為cT的顧客P;GetArrivalTime(Ps);初始條件：顧客Ps已存在，操作結(jié)果：返回該顧客的進(jìn)門時(shí)刻；GetCutTime(Ps);初始條件：顧客Ps已存在；操作結(jié)果：返回該顧客的理發(fā)時(shí)間；ADTOrderedList(有序表){數(shù)據(jù)對(duì)象：是上述定義的事件的集合數(shù)據(jù)關(guān)系：按事件的發(fā)生時(shí)刻自小至大有序基本操作：在線性表的操作的基礎(chǔ)上添加一個(gè)有序表的插入Insert(&OL,x)初始條件：有序表OL已存在；操作結(jié)果：在有序表中插入x,并保持表的有序性；ADT(數(shù)據(jù)元素為上述定義的顧客的)隊(duì)列三、詳細(xì)設(shè)計(jì)classEvent{private：intoccurTime;chareventType;public:Event(intoT,chartp):occurTime(oT),eventType(tp){}intevTime(void){returnoccurTime}charevType(void){returneventType}classCustomer{private:intarrivalTime;intcutTime;public:Customer(intaT,charcT):arrivalTime(oT),cutTime(ct){}intavTime(void){returnarrivalTime}intcuTime(void){returncutTime}}template<classElemType>classorderedList:publicList{public:orderedList(void);//構(gòu)造函數(shù)，初始化一個(gè)空表intlocate(ElemType*pitem);//在有序表中查詢數(shù)據(jù)元素pitem,若存在，則移//動(dòng)當(dāng)前指針指向該結(jié)點(diǎn)并返回1，否則移動(dòng)當(dāng)前//指針指向第一個(gè)大于它的結(jié)點(diǎn)并返回0voidinsert(ElemType*item);//插入數(shù)據(jù)元素item,并保持表的有序性}template<classElemType>voido