棧和隊(duì)列是計算機(jī)科學(xué)中兩個非常有用的概念。它們是兩種特殊的線性表，因?yàn)樗鼈兊倪壿嫿Y(jié)構(gòu)與線性表相同，只是在運(yùn)算規(guī)則方面較線性表多增加了一些限制，故可以把它們看作是運(yùn)算受限制的線性表作為線性表的推廣，本章還介紹了數(shù)組的邏輯結(jié)構(gòu).基本運(yùn)算及存儲方式棧是限制儀在表的一端進(jìn)行插入、刪除運(yùn)算的線性表允許進(jìn)行插入和刪除的這一端稱為?！肛?另一端稱為棧底處于棧頂位置的數(shù)據(jù)元素稱為棧頂元素不含任何數(shù)據(jù)元素的棧稱為空棧初始化InltstackfS)：建立一個空棧入桟pKh(S,x)4將值為x的元素壓入到棧S中⑶岀棧pop(5):刪除棧頂元素，并將它的債放到變量閃中⑷取棧頂topCS);返回棧頂元素的值(5)判斷棧是否為空empty(S)s若棧S為空，則結(jié)果為1,否則結(jié)果為0

2d進(jìn)棧的主要操作是：①找頂下標(biāo)加”②將入我元素放入到新的棧頂下標(biāo)所指的位置上。intPush(SqStaekip*DataTypek)彩若棧未滿，將元素x入棧舛中；否則提示出借信息*/【if(sq一〉top=sqstack_mdxsize-l){error滿棧")；return0;}else(sqtop++;sq->data[sq->top]-乂；return(1);}inH2OK-5-M棧的鏈接實(shí)現(xiàn)稱為鏈棧，其組織形式與單鏈表類似其中，單鏈表的第一個結(jié)點(diǎn)就是鏈棧棧頂結(jié)點(diǎn).Is2OK-5-M棧的鏈接實(shí)現(xiàn)稱為鏈棧，其組織形式與單鏈表類似其中，單鏈表的第一個結(jié)點(diǎn)就是鏈棧棧頂結(jié)點(diǎn).Is稱為棧頂指針，它相當(dāng)于單鏈表的頭指針，類似地，鏈棧由棧頂指針1S惟一確定，棧中的其它結(jié)點(diǎn)通過它們的曲對域鏈接起來。棧底結(jié)點(diǎn)的昭xt域?yàn)镹ULLi的鏈接實(shí)現(xiàn)鏈棧的類型定義typedefstructnode(DataTypedata;：structnode*next;}LStack?p;2013-3-9 Ih鏈棧的基本運(yùn)算初始化棧初始化的作用是設(shè)置一個空?！粋€空的鏈?？梢杂脳ｍ斨羔槥镹ULL來表示。voidInitStack(LStackTp*Is){Is=NULL;3D!J-5-3 17進(jìn)棧進(jìn)棧算法的基本步驟包括：申請一個新結(jié)點(diǎn)，并將X的值送入詼結(jié)點(diǎn)的血姑域；將該點(diǎn)賞入棧中使之成為新的棧頂站點(diǎn).voidPush(LStackTp*1哥，DataTypex){LSta-clcTp*p;P-(LStackTp*)niallot(s-izeof(LStackTp)):/*申謂一個新節(jié)點(diǎn)*/p->data=乂：/?元素得值添入新節(jié)點(diǎn)的Mt務(wù)域*/p->next-is;/*原棧頂鏈入新節(jié)點(diǎn)的n嚇t域*/Is=p： /*新節(jié)點(diǎn)成為新的棧頂*/}20!3-3-3 K理?xiàng)Ｖ攴ǖ幕静襟E包括；桟項(xiàng)結(jié)點(diǎn)的膈脂域的值由參數(shù)返回，并摘除成頂結(jié)晶讓它的下-個結(jié)點(diǎn)成為新的投頊；將職出的棧皿站點(diǎn)空間釋放.ihtPopfLStickTp*1我DataType**)(LStackTp?:p：if(lsi=NULL)!。件M=p->data; ■回-Is=M->隊(duì)誰丫女原権項(xiàng)的下一個節(jié)點(diǎn)成為新的棧頊free(G； 擇放原欖頂節(jié)雙間*/TetumI;}elsereturnD；}

20IVMif(Is二二NULL)return(1);elsereturn(0);intEmptyStack(LStackTp*Is)層若棧為空刖返回值“否則返回值Q*/讀棧頂元素intGetTop(LStackTp*Is：DataType*x)/*取棧頂元素*/if(ls1=NULL)(*x=ls->data;return1;elsereturn0;20!3-3-3 2\2OI5-M 設(shè)輸入序列為A,B,C,D?借助一個?？梢缘玫降妮攲缧蛄?,a.A,C,D,Bh?C,A,D,Bg.D,C5B,AtLD,A,B,C［擇題2設(shè)有一順序棧S,元素SLS2,S3.S4.SS.S6依次進(jìn)棧，如果6個元素出棧的順序是S2,S3.S4.S6.SS.SL則棧的容量至少應(yīng)該是（）TOC\o"1-5"\h\z23562CHM-4擇題3鏈棧與順序棧比較，有一個明顯的優(yōu)點(diǎn)是（）A） 通常不會出現(xiàn)棧滿的情況B） 通常不會出現(xiàn)?？盏那闆rC） 插入操作更加方便D） 刪除操作更加方便部J-5-3 Z3!題1設(shè)有一個鏈棧，其中各結(jié)點(diǎn)中有血也和next兩字段,棧頂指針為Ls（尹NULL）,則執(zhí)行退棧的基本操作是ls=ls->next—2013-5-S 36］、棧和隊(duì)列都是—,甘.順序存儲的線性表 b?鏈?zhǔn)酱鎯Φ木€性表C限制存儲點(diǎn)的線性表d.限制存儲點(diǎn)的非域性結(jié)構(gòu)2,判斷：棧只能釆用鏈?zhǔn)酱鎯Ψ绞?2CIIJ-5-M棧與函數(shù)調(diào)用tmg2CIIJ-5-M棧與函數(shù)調(diào)用tmg…）;工作棧調(diào)聊他茹 此電鮮后 園用船扃 返回起靜 理叵Fl3-.U工作棧調(diào)聊他茹 此電鮮后 園用船扃 返回起靜 理叵Fl3-.U遞歸定義的注意點(diǎn)遞歸定義不能是'循環(huán)定義對 任何遞歸定義必須同時滿足如下兩個條件*被定義項(xiàng)在定義中的應(yīng)用（即作為定義項(xiàng)的岀現(xiàn)）具有更小的“尺度":被定義項(xiàng)在最小“尺度”上的定義不I是遞歸的I（舉例P5。）2WJ-5-3 勤隊(duì)列吸列也可以看在是一種運(yùn)算受限的線性表，在這種線性表上，插入限定在表的某一端進(jìn)行，刪除限定在表的另一端進(jìn)行允許插入的一端稱為甌尾允許刪除的一端稱為隊(duì)頭30!3易 33操作規(guī)則：先進(jìn)先出操作規(guī)則：先進(jìn)先出抵H3-5-S ?6隊(duì)列的基本運(yùn)算I隊(duì)列初始化InitQucmtQ^加工型運(yùn)算，其作用是設(shè)置一個空隊(duì)列Q入隊(duì)列EnQueue(Q,X)r加工型運(yùn)算,其作用是將X插入到隊(duì)列Q的隊(duì)尾出隊(duì)誠蛆Q.X),加工型運(yùn)算，若隊(duì)列Q不空，則將隊(duì)頭元素賦給X,并刪除隊(duì)頭結(jié)點(diǎn)，而該結(jié)點(diǎn)的后繼成為新的隊(duì)頭結(jié)點(diǎn)隊(duì)列的基本運(yùn)算判隊(duì)列空EmptyQiieue(Q),引用型運(yùn)算,若隊(duì)列Q為空，則返回的值為L否則值為0讀隊(duì)頭GetHead(QA),引用型運(yùn)算，Q不空時由參數(shù)X返回隊(duì)頭結(jié)點(diǎn)的值，否則給一特殊標(biāo)志".問 川|，i——隊(duì)列的順序?qū)崿F(xiàn)稱為順序臥，它由一個一維數(shù)組(用于存儲隊(duì)列中元素)及兩個分別指示隊(duì)頭和隊(duì)尾的變量組成這兩個變量分別稱為蚌甌頭指針H和”隊(duì)尾指針”通常約定隊(duì)尾指針指示隊(duì)尾元素在一維數(shù)組中的當(dāng)前位置，隊(duì)頭指針指示隊(duì)頭元素在一維數(shù)組中的當(dāng)前位置的前一個位置(如圖)2WJ-5-q 頻

typedefstructsqqueueDataTypedata[inaxsize];tntfront,rear;}SqQueueTp;SqQueueTpsq;：typedefstructsqqueueDataTypedata[inaxsize];tntfront,rear;}SqQueueTp;SqQueueTpsq;：0lLMrem201V5_ij順序隊(duì)定義為一個結(jié)構(gòu)類型，該類型變量有三個域rem201V5_ij順序隊(duì)定義為一個結(jié)構(gòu)類型，該類型變量有三個域Idata、front、data為存儲隊(duì)中元素的一維數(shù)組。隊(duì)頭指針frcmt和隊(duì)尾指針rear定義為整列變量，實(shí)際取值范圍是。…ma而昵入隊(duì)操作sq.rear入隊(duì)操作sq.rearwq.dataEsq.rear]=出隊(duì)操作sq*front=FlJ-.M隊(duì)空條件為'nrivslire*3循環(huán)隊(duì)列的實(shí)現(xiàn)算法— ——二—隊(duì)列的初始化voidInLtCycQueue(CycqueueTp*sq〉{sq->front=0;sq->rear=0;2D!3-5-S 48入隊(duì)列intEnCycQueue(Cy^qu-eueTp*sq,Datalypek)if((sqrear+1)*gaxsise=sqfront){error(*隊(duì)滿")；return0;/車馳禰?入隊(duì)列失敗打 }elsesq一〉rear-($q->rear41)%maxsi^e;sq->data[s<i->Tear]-x:return1:}}3D!J-3-q 49出隊(duì)列■IHb,,，iMd^IVk^rM*11ralHKIIBVfeMHliiTs3it^IIbk. H^lrF:1kw馬憫trsWiJX■ if(sq->frvnt—sq->rear){ "g.g 二….二....error(*隊(duì)空。； 八隊(duì)空，出隊(duì)列失敗可tettitii0;else(*sq->frcnt-(sq.->front+1)，waxsiE-e;*x=$q->data[sq->front]：return1;}}20!3-3-3 50隊(duì)空intEmptyCycQueue(CycqueueTpsq)if(叫rear==sq.front)return1;elsereturn0;51201)-5-451 擇題1 設(shè)數(shù)組A[O,ni]作為循環(huán)隊(duì)列旳的存儲空間*front為機(jī)頭指針，rear為隊(duì)尾指針，則執(zhí)行入隊(duì)操作的語句是()sq-front=(sq,iront+l)%msq.front=(sq.front41)%(m+1)C〉sq>rear=(sqtrear+l)%mD)sq?rcar=(sqmar+l)%(m+l)20!3-3-9 S4 在具有n個單元的循環(huán)隊(duì)列中，隊(duì)滿時共有 個元素棧稱為 線性表隊(duì)稱為 線性表3D!3-5-3 55

鏈隊(duì)結(jié)構(gòu)隊(duì)列的鏈接實(shí)現(xiàn)稱為鏈隊(duì),它實(shí)際上是一個同時帶有頭指針和尾指針的單鏈表，頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向臥尾結(jié)點(diǎn)lankqu#彌lankqu#彌2CH5-5-Mi隊(duì)的類型定義typedefstructnode*front,*rear;}1inkqueue;

隊(duì)的基本運(yùn)算初始化空的鏈隊(duì)列僅有一個頭結(jié)點(diǎn)「并且頭尾指針均指向頭結(jié)點(diǎn)voidInitquene(1inkQueue*Q){Q~>front=(node*)nialloc(sizeof(node))://產(chǎn)生一個頭結(jié)點(diǎn)Q->rear=Q->front;〃尾摘有'也指向頭結(jié)點(diǎn) . .m謐畋.hnQ.front->next^NULL;//尾靖點(diǎn)后繼指針澈設(shè)置為空}20JJ-5-flhn入隊(duì)列voidEnqueue(1inkqueue*Q,datatypex){node*P=(node*)tnalloc(siz^of(node)):P^>data=x;P->neit=Nl)LL;〃新隊(duì)尾的后繼指針為空Q->rear->n?xt=P;〃插入到隊(duì)尾Q->rear=P;〃尾指針指向新的隊(duì)尾20!3-5-3 &I

隊(duì)列iBi-a隊(duì)列voidOutQueue{.linkqueue datatype*x)(if(empty)errorC隊(duì)空，不能岀隊(duì)”)：else{jc=Q->front^>next^>data;〃取隊(duì)頭元素的值node*n=Q->front->next：//保存待刪結(jié)點(diǎn)的指針Q->fr&nt->next=u->next://刪除free(u):if(Q->front->next=-NULL)2CII//岀隊(duì)最后一個結(jié)點(diǎn)時Q->rear=Q->front;}2CIIemptyQueue(linkqueueQ)(if(Q.froM=Q?rear)return1;elsereturn0;2D!J-5-3 師讀隊(duì)頭元素voidGetHead(1inkqueue*Q,d-atatype*x);{if(Q.rear==Q.front)^rror(w隊(duì)空「不能取元素與；else州=Q-》fmnt->bext-〉data;〃取隊(duì)頭元素(首結(jié)點(diǎn)〉的值20!3-5-9 64病人到達(dá)診室時，將病歷交給護(hù)士，排到等候隊(duì)列中候診護(hù)士從等待隊(duì)列取出下一位患者的病歷,該患者進(jìn)入診室就診.一箜數(shù)組=是若干個元素的有限序列若一維數(shù)組中每個元素本身又是一維數(shù)組，則I為二鎌數(shù)組以此類推，若一維數(shù)組中每個元素本身為（口?1）維數(shù)組，則為a維數(shù)組對數(shù)組的運(yùn)算，通常有兩個]L讀，紿定下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素I2.寫：給定下標(biāo)，修改相應(yīng)的元素值.要笙現(xiàn)這兩個運(yùn)尊均需計算出指定元素的實(shí)際存儲地址2013-3-9 615■由于對數(shù)組沒有定義插入和刪除運(yùn)算,

所以數(shù)組一般只采用順序存儲結(jié)構(gòu)%]auaji..aziiH的跆瑙、■?.電*0知■-=?■ti以行序?yàn)楦＃ㄐ衪t売親i!E：】e源行地抵序儲宕元基⑵I琳I]序?yàn)橹餍蚶齜t完吞晴gL遂劉池?厝萬序礙尋無疋邑1A肉齢…%], -■-扣| --- 爭■站倉h，-■、a3QJ3-5-fl 67組的,隨機(jī)存儲結(jié)構(gòu)”對給定的數(shù)組元素Mij],在以行序?yàn)橹餍虻拇鎯Ψ绞街?，核元素的序號為?i-1)*心j;而在以列序?yàn)橹餍虻拇鎯Ψ绞街?，它把序號為K=G-L)和+1若繪定存儲區(qū)的起始地址為AddrQ,每個元素占C個存儲單元,則元素A[ij]在內(nèi)存中的地址為Loc(i.j)=AddrQ+(k-L)*C數(shù)紺元素的存儲位置是F標(biāo)的線性函數(shù)『計算存儲位置所需的時間仮取決于乗法時間，因此，存取任一元素的時間相等矩陣可以用二維數(shù)組來表示在實(shí)際應(yīng)用中經(jīng)常遇鬼這種情況】矩陣中有許多元素的值相等或?yàn)?。，這種矩陣稱為樨"W;如果矩陣中元素值的分布有一定規(guī)律，則稱之為特殊矩陣.為了節(jié)省存儲空間，一般對此類矩陣進(jìn)行壓縮存儲,縮存儲：是指為多個值相同的元素只分配一個存儲空間，對零元素不分配存儲空間

2CII5-5-M A)B)2CII5-5-M A)B)C)D)在一個鏈隊(duì)列中，若f,r分別為隊(duì)首、隊(duì)尾指針，則插入$所指結(jié)點(diǎn)的操作為f^>next=s;f=s;r->next=s;r=s;s->next=r;r=s;s->next=f;f=s; 可以作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)通常數(shù)組只有 和 兩種運(yùn)算，因此常采用 來存儲數(shù)組2013-5-4數(shù)組M數(shù)組M中每個元素長度是3個字節(jié)，行下標(biāo)i從1到?列下標(biāo)j從1到1。，從首地址EA開始連續(xù)存放在存儲器中，若按行優(yōu)先方式存放.元素M[8][5]的起始地址為 :若按照列優(yōu)先方式存放，元素M.[8][5]的起始地址為 20H-M201?!-5-9陣的壓縮存儲201?!-5-9陣的壓縮存儲角矩陣以主對角線劃分，三角矩陣有上三角和下三角兩種，所謂上（下）三角短陣是指矩陣的下（上）三角（不包括對角線）中元素均為常數(shù)C或零的n吮矩陣ce num；?）上三的炬M

Iml(b)TSft}￡陣201J-5-M_— 匕三角矩陣的對應(yīng)關(guān)系旦門之前的前iT行共有上三角矩陣中，主對角批上的第t■行（L^t^n）有旦門之前的前iT行共有T+"2fi~iT+"2fi~i+2)個元素，在第I行上，冬」是詼行的第j-i+1個元素，M[k][和印j的對應(yīng)關(guān)系是：當(dāng)iWjk-l（當(dāng)iWj當(dāng)》jk當(dāng)》jmiuA

當(dāng)iA=j時，跖「M[n(n+1)/2+1]申,對稱矩陣類似口三角矩陣的對應(yīng)關(guān)系當(dāng)iA=j時，跖「M[n(n+1)/2+1]申,對稱矩陣類似口二5存放在，下三角矩陣的存儲和M[k]和％的對應(yīng)關(guān)系是;k=n(n-bl)/2+l2013-5-4稀疏矩陣一般地，設(shè)矩陣廣m”中有§個非零元素，若S遠(yuǎn)遠(yuǎn)小于矩陣元素的個數(shù)Cs?mXn)，并且非零元素的分布沒有規(guī)律，則稱A為稀琉矩陣』稀疏矩陣的氏縮存儲方法是只存儲I零匸京〃對每個非零元素第「可以用一個三元組GJ,財)惟一確定，其中旳表示該非零元素的值；LJ為該非零元素在原矩陣中的行號和列號口然后將所有非零元素的三元組按一定次序排列在一起構(gòu)成元組表2D13-5-9 S0三元組表的類型說明#(l?fLneriiaxnum10tjljedefstruct[Hiiie{1MJ； 產(chǎn)非零元眉在行號，列號呷DataTypev;件非零元的債宵}NODE;typtdcfstruclsptnatrtxIimuwE財屮〃行數(shù),列數(shù),非零元素的個數(shù)習(xí)NODEdatalmaAnum十】]港這里假定三元組的下標(biāo)的起始值為E}SpMatrixTp;Fl卜"Fl卜"在這一節(jié)中'結(jié)合棧和隊(duì)，用一個完整的程序來說明棧和隊(duì)列的應(yīng)用接受命令和車號，若是汽車要進(jìn)停車場，先判斷停車場棧是否滿，若不滿「則汽車入棧，否則汽車入便道隊(duì)列等候若是汽車要離開停車場，為給該汽車讓路將停車場棧上若干輛