數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列市公開課一等獎(jiǎng)省賽課獲獎(jiǎng)?wù)n件

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

DataStructure彭宏京南京工業(yè)大學(xué)計(jì)算機(jī)科學(xué)系年9月數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第1頁(yè)課時(shí)數(shù)：48（32+16）學(xué)分：2教材：嚴(yán)蔚敏等，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），清華大學(xué)出版社，1997年4月（配題集）參考書：[1]殷人昆等，數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述），清華大學(xué)出版社，1999年7月。￥26[2]殷人昆等，數(shù)據(jù)結(jié)構(gòu)習(xí)題解析，清華大學(xué)出版社，204月。￥26[3]李春保，數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析（C語(yǔ)言篇），清華大學(xué)出版社，年1月。￥28[4]丁寶康等，數(shù)據(jù)結(jié)構(gòu)自學(xué)考試指導(dǎo)，清華大學(xué)出版社，年5月。￥23數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第2頁(yè)內(nèi)容安排章內(nèi)容課時(shí)章內(nèi)容課時(shí)1緒論27圖62線性表48動(dòng)態(tài)存放管理略3棧和隊(duì)列69查找44串（自學(xué)）210內(nèi)部排序45數(shù)組和廣義表（自學(xué)）411外部排序略6樹和二叉樹612文件略試驗(yàn)：課內(nèi)上機(jī)（16要求內(nèi)容）+課外上機(jī)（24平時(shí)作業(yè)中編程題驗(yàn)證）數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第3頁(yè)數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容邏輯結(jié)構(gòu)唯一存放結(jié)構(gòu)不唯一運(yùn)算實(shí)現(xiàn)依賴于存放結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第4頁(yè)3.1棧（Stack）3.2隊(duì)列（Queue）第三章棧和隊(duì)列1.定義2.邏輯結(jié)構(gòu)3.存放結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式1.定義2.邏輯結(jié)構(gòu)3.存放結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第5頁(yè)1.定義3.1棧與線性表相同，仍為一對(duì)一(1:1)關(guān)系。用次序?；蜴湕４娣啪?，但以次序棧更常見(jiàn)只能在棧頂運(yùn)算，且訪問(wèn)結(jié)點(diǎn)時(shí)依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）標(biāo)準(zhǔn)。關(guān)鍵是編寫入棧和出棧函數(shù)，詳細(xì)實(shí)現(xiàn)依次序?；蜴湕４娣沤Y(jié)構(gòu)有別而不一樣。3.存放結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式

2.邏輯結(jié)構(gòu)限定只能在表一端進(jìn)行插入和刪除運(yùn)算線性表。即棧頂基本操作有：建棧、判斷棧滿或?？?、入棧、出棧、讀棧頂元素值，等等。數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第6頁(yè)棧是僅在表尾進(jìn)行插入、刪除操作線性表。表尾(即an端)稱為棧頂

/top;表頭(即a1端)稱為棧底/base比如：棧S=(a1,a2,a3,……….,an-1,an

)插入元素到棧頂操作，稱為入棧。從棧頂刪除最終一個(gè)元素操作，稱為出棧。an稱為棧頂元素a1稱為棧底元素想一想：要從棧中取出a1，應(yīng)該怎樣操作？強(qiáng)調(diào)：插入和刪除都只能在表一端（棧頂）進(jìn)行！數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第7頁(yè)Q1：堆棧是什么？它與普通線性表有什么不一樣？堆棧是一個(gè)特殊線性表，它只能在表一端（即棧頂）進(jìn)行插入和刪除運(yùn)算。與普通線性表區(qū)分：僅在于運(yùn)算規(guī)則不一樣。普通線性表堆棧邏輯結(jié)構(gòu)：1:1邏輯結(jié)構(gòu)：1:1存放結(jié)構(gòu)：次序表、鏈表存放結(jié)構(gòu)：次序棧、鏈棧運(yùn)算規(guī)則：隨機(jī)存取運(yùn)算規(guī)則：后進(jìn)先出(LIFO)“進(jìn)”＝插入=壓入=PUSH（an+1)“出”＝刪除=彈出=POP(an)數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第8頁(yè)a1a2……an次序棧Sai……Q2：次序表和次序棧操作有何區(qū)分？表頭表尾低地址高地址寫入：S[i]=ai讀出：e=S[i]壓入(PUSH):

S[top++]=an+1彈出(POP):e=S[--top]低地址高地址S[i]a1a2

aian……次序表S……an+1以線性表

S=(a1,a2,….,an-1,an)為例棧底base棧頂top前提：一定要預(yù)設(shè)棧頂指針top數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第9頁(yè)棧不存在條件：base=NULL;棧為空條件：base=top;棧滿條件：top-base=stacksize;a1a2……an次序棧Sai……低地址高地址an+1棧底base棧頂top數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第10頁(yè)若入棧動(dòng)作使地址向高端增加，稱為“向上生成”棧；若入棧動(dòng)作使地址向低端增加，稱為“向下生成”棧；

對(duì)于向上生成堆棧:入?？谠E：堆棧指針top“先壓后加”:S[top++]=an+1出?？谠E：堆棧指針top“先減后彈”:e=S[--top]Q3：什么叫“向上生成”棧？“向下生成”又是何意？數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第11頁(yè)Q4：為何要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？調(diào)用函數(shù)或子程序非它莫屬；遞歸運(yùn)算有力工具；用于保護(hù)現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)；簡(jiǎn)化了程序設(shè)計(jì)問(wèn)題。下面用4個(gè)例子來(lái)幫助了解堆棧：數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第12頁(yè)voidtest(int&sum){intx;scanf(x);if(x==0)sum=0;else{test(sum);sum+=x;}printf(sum);}斷點(diǎn)地址入棧例1（嚴(yán)題集3.10③）閱讀以下遞歸過(guò)程，說(shuō)明其功效。輸入x1≠0輸入x5＝0輸入x2輸入x3輸入x4輸出sum＝0輸出sum＝0+x4輸出sum＝x4+x3輸出sum＝x4+x3+x2輸出sum＝x4+x3+x2+x1注意：最先輸入數(shù)據(jù)x1

最終才被累加程序功效：對(duì)鍵盤輸入數(shù)據(jù)求和，直到輸入0結(jié)束數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第13頁(yè)例2（嚴(yán)題集3.1）一個(gè)棧輸入序列為1,2,3，若在入棧過(guò)程中允許出棧，則可能得到出棧序列是什么？答：能夠經(jīng)過(guò)窮舉全部可能性來(lái)求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入，3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；累計(jì)有5種可能性。數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第14頁(yè)例3：一個(gè)棧輸入序列是12345，若在入棧過(guò)程中允許出棧，則棧輸出序列43512可能實(shí)現(xiàn)嗎？12345輸出呢？答：43512不可能實(shí)現(xiàn)，主要是其中12次序不能實(shí)現(xiàn)；12345輸出能夠?qū)崿F(xiàn)，每壓入一數(shù)便馬上彈出即可。思索：有沒(méi)有通用判別標(biāo)準(zhǔn)？數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第15頁(yè)例4：設(shè)依次進(jìn)入一個(gè)棧元素序列為c，a，b，d，則可得到出棧元素序列是：

Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，bA）、D）能夠，B）、C）不行。討論：有沒(méi)有通用判別標(biāo)準(zhǔn)？有！若輸入序列是…,Pj…Pk…Pi…(Pj<Pk<Pi)，一定不存在這么輸出序列…,Pi…Pj…Pk…答：即對(duì)于輸入序列1，2，3，不存在輸出序列3，1，2年考研題數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第16頁(yè)棧抽象數(shù)據(jù)類型定義:(教材P44-45）ADTStack{數(shù)據(jù)對(duì)象：D=……數(shù)據(jù)關(guān)系：R=……基本操作：……}ADTStack入棧、出棧、建棧初始化、判斷棧滿或?？?、讀棧頂元素值等。本節(jié)重點(diǎn)：次序棧和鏈?；静僮鲾?shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第17頁(yè)次序棧存放表示（教材P46)：

#defineSTACK-INIT-SIZE100

//存放空間初始分配量

#defineSTACKINCREMENT10

//存放空間分配增量

typedefstruct{

SElemType*base;

//?；芳礂５字羔?/p>

SElemType*top;

//棧頂指針

intstacksize;

//當(dāng)前分配空間

}SqStack;動(dòng)態(tài)數(shù)組數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第18頁(yè)次序棧入棧操作——比如用堆棧存放（A，B，C，D）AACBABAtop關(guān)鍵語(yǔ)句：top=L;

次序棧入棧函數(shù)PUSH（）statusPush(ElemTypee){if(top>M){上溢}elses[top++]=e;}Push(B);Push(C);Push(D);toptoptoptop低地址LPush(A);高地址MBCD數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第19頁(yè)次序棧出棧操作——比如從棧中取出‘B’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD關(guān)鍵語(yǔ)句：Pop();次序棧出棧函數(shù)POP()statusPop(){if(top=L){下溢}else{e=s[--top];return(e);}}Pop();Printf(Pop());數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第20頁(yè)鏈棧入棧操作和出棧操作（教材省略）(1)鏈棧結(jié)構(gòu)方式——以頭指針為棧頂，在頭指針處插入或刪除.Node*st,*p;intm=sizeof(Node);棧頂棧底棧也能夠用鏈?zhǔn)浇Y(jié)構(gòu)來(lái)表示，用鏈?zhǔn)浇Y(jié)構(gòu)來(lái)表示棧就是鏈棧sta1a2an-1annextdata鏈棧中每個(gè)結(jié)點(diǎn)由兩個(gè)域組成：data域和next域，其定義為：typedefStructSNode{SElemTypedata;StructSNode*next;}Node;數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第21頁(yè)P(yáng)ush(SElemTypee)

{p=(Node*)malloc(m);if(!p){上溢}else{p->data=e;p->link=st;st=p;}}

StatusPop()

{if(st==NULL){下溢}else{e=st->data;p=st;st=st->link;

free(p);return(e);}}鏈棧入棧函數(shù)鏈棧出棧函數(shù)插入表頭從表頭刪除(2)操作由此能夠看出：一個(gè)鏈棧由其棧頂指針唯一指定設(shè)st指向棧頂元素，則st=NULL表示棧空數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第22頁(yè)鏈棧無(wú)須設(shè)頭結(jié)點(diǎn)，因?yàn)闂ｍ敚ū眍^）操作頻繁；鏈棧普通不會(huì)出現(xiàn)棧滿情況，除非沒(méi)有空間造成malloc分配失敗。鏈棧入棧、出棧操作就是棧頂插入與刪除操作，修改指針即可完成。采取鏈棧存放方式優(yōu)點(diǎn)是，可使多個(gè)棧共享空間；當(dāng)棧中元素個(gè)數(shù)改變較大，且存在多個(gè)棧情況下，鏈棧是棧首選存放方式。幾點(diǎn)說(shuō)明:數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第23頁(yè)例1：數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N）——見(jiàn)教材P48

設(shè)計(jì)思緒：用棧暫存低位值例2：括號(hào)匹配檢驗(yàn)————見(jiàn)教材P49

設(shè)計(jì)思緒：用棧暫存左括號(hào)例3：表示式求值—-————見(jiàn)教材P52

設(shè)計(jì)思緒：用棧暫存運(yùn)算符例4：漢諾（Hanoi）塔-———見(jiàn)教材P55

設(shè)計(jì)思緒：用棧實(shí)現(xiàn)遞歸調(diào)用棧應(yīng)用舉例數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第24頁(yè)例3

表示式求值(這是棧應(yīng)用經(jīng)典例子,見(jiàn)P52)這里，表示式求值算法是“算符優(yōu)先法”。比如：編寫算法，用棧實(shí)現(xiàn)表示式3*（7–2）求值。一個(gè)算術(shù)表示式是由操作數(shù)（x，y，z…）和

算符（*，/，+，-，（，），#）組成.教材P53中表3.1給出了算符之間優(yōu)先級(jí)專為計(jì)算機(jī)處理而設(shè)計(jì)表!表示式起止符號(hào)(1)

表示式求值必須滿足算術(shù)四則運(yùn)算規(guī)則：a.從左算到右b.先乘除，后加減c.先括號(hào)內(nèi)，后括號(hào)外數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第25頁(yè)(2)算法思想：1）首先置操作數(shù)棧OPND為空棧，表示式起始符#為運(yùn)算符棧OPTR棧底元素；2）依次讀入表示式中每個(gè)字符，若運(yùn)算符是‘#’或棧頂是‘#’，結(jié)束計(jì)算，返回OPND棧頂值。if（是操作數(shù)）→則PUSH（OPND，操作數(shù)）；if（是運(yùn)算符）→則與OPTR棧頂元素進(jìn)行比較，按優(yōu)先級(jí)(要求詳見(jiàn)P53表3.1）進(jìn)行操作；為了實(shí)現(xiàn)算符優(yōu)先算法，能夠設(shè)定兩個(gè)工作棧，OPND—存放操作數(shù)或運(yùn)算結(jié)果，OPTR—存放運(yùn)算符號(hào)。3）直到整個(gè)表示式求值完成（當(dāng)前讀入字符和OPTR棧棧頂元素均為#

）if棧頂元素<輸入算符，則算符壓入OPTR棧，并接收下一字符if棧頂元素=運(yùn)算符但≠‘#’，則脫括號(hào)(彈出左括號(hào))并收下一字；

if棧頂元素>運(yùn)算符，則退棧、按棧頂計(jì)算，將結(jié)果壓入OPND棧。且該未入棧運(yùn)算符要保留，繼續(xù)與下一個(gè)棧頂元素比較！數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第26頁(yè)問(wèn)：教材P53表3.1中，1和2哪個(gè)對(duì)應(yīng)棧頂元素，哪個(gè)對(duì)應(yīng)鍵盤輸入值？答：依據(jù)P53Precede()函數(shù)可知，1對(duì)應(yīng)棧頂元素由表3.1可看出，右括號(hào))

和井號(hào)#作為2時(shí)級(jí)別最低；由c規(guī)則得出：*，/，+，-為1時(shí)優(yōu)先權(quán)低于‘（’，高于‘）’由a規(guī)則得出：‘（’=‘）’表明括號(hào)內(nèi)運(yùn)算已完成；‘#’=‘#’表明表示式求值完成。附：數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第27頁(yè)表示式求值過(guò)程描述：OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,’3’)

#*(7-2)#3#Push(optr,’*’)#,*3(7-2)#Push(optr,’(’)#,*,(37-2)#Push(opnd,’7’)#,*,(3,7-2)#Push(optr,’-’)#,*,(,－3,72)#Push(opnd,’2’)#,*,(,－3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)3*（7–2）數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第28頁(yè)StatusEvaluateExpression(OperandType&result){InitStack(OPND);InitStack(OPTR);Push(OPTR,’#’);c=getchar();while((c!=‘#’)&&(GetTop(OPTR)!=‘#’)){if(!In(c,OP){Push(OPND,c);c=getchar();}elseswitch(precede(GetTop(OPTR),c)){case‘<’:Push(OPTR,c);c=getchar();break;case‘=’:Pop(OPTR);c=getchar();break;

case‘>’:Pop(OPTR,theta);Pop(OPND,b);a=Pop();Push(OPND,Operate(a,theta,b));break;;}//switch}//while

result=GetTop(OPND);}//EvaluateExpressionOperate=abC是操作符嗎？運(yùn)算符與棧頂比較并查3.1表數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第29頁(yè)例4漢諾（Hanoi）塔傳說(shuō)在創(chuàng)世紀(jì)時(shí)，在一個(gè)叫Brahma寺廟里，有三個(gè)柱子，其中一柱上有64個(gè)盤子從小到大依次疊放，僧侶工作是將這64個(gè)盤子從一根柱子移到另一個(gè)柱子上。分析：設(shè)三根柱子分別為x,y,z,盤子在x柱上，要移到z柱上。1、當(dāng)n=1時(shí)，盤子直接從x柱移到z柱上；2、當(dāng)n>1時(shí),則:①設(shè)法將前n–1個(gè)盤子從x移到y(tǒng)柱上（借助z），則盤子n就能從x移到z柱上；②再設(shè)法把n–1個(gè)盤子從y移到z柱上(這又是一個(gè)與原來(lái)相同問(wèn)題，只是規(guī)模少１了）。xyznn–1移動(dòng)時(shí)規(guī)則：

每次只能移動(dòng)一個(gè)盤子；只能小盤子在大盤子上面；能夠使用任一柱子。當(dāng)工作做完之后，就標(biāo)志著世界末日到來(lái)。數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第30頁(yè)VoidHanoi(intn,charx,chary,charz){//將n個(gè)編號(hào)從上到下為1…n盤子從x柱，借助y柱移到z柱if(n==1)move(x,1,z);//將編號(hào)為1盤子從x柱移到z柱

else

{

//將n-1個(gè)編號(hào)從上到下為1…n-1盤子從x柱，借助y柱移到z柱

Hanoi(n-1,x,z,y);move(x,n,z);//將編號(hào)為n盤子從x柱移到z柱

//將n-1個(gè)編號(hào)從上到下為1…n-1盤子從y柱，借助x柱移到z柱

Hanoi(n-1,y,x,z);

}}//Hanoi程序設(shè)計(jì)以下：誰(shuí)能畫出P57-58圖3.7所表示Hanoi塔遞歸函數(shù)運(yùn)行示意圖？數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第31頁(yè)3.1棧（Stack）

第三章棧和隊(duì)列3.2隊(duì)列（Queue）1.定義2.邏輯結(jié)構(gòu)3.存放結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式1.定義2.邏輯結(jié)構(gòu)3.存放結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第32頁(yè)3.2隊(duì)列與線性表相同，仍為一對(duì)一關(guān)系。次序隊(duì)或鏈隊(duì)，以循環(huán)次序隊(duì)更常見(jiàn)。只能在隊(duì)首和隊(duì)尾運(yùn)算，且訪問(wèn)結(jié)點(diǎn)時(shí)依照先進(jìn)先出（FIFO）標(biāo)準(zhǔn)。關(guān)鍵是掌握入隊(duì)和出隊(duì)操作，詳細(xì)實(shí)現(xiàn)依次序隊(duì)或鏈隊(duì)不一樣而不一樣。存放結(jié)構(gòu)運(yùn)算規(guī)則實(shí)現(xiàn)方式邏輯結(jié)構(gòu)只能在表一端進(jìn)行插入運(yùn)算，在表另一端進(jìn)行刪除運(yùn)算線性表?；静僮鳎喝腙?duì)或出隊(duì)，建空隊(duì)列，判隊(duì)空或隊(duì)滿等操作。尾部插入首部刪除隊(duì)列定義數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第33頁(yè)隊(duì)列（Queue）是僅在表尾進(jìn)行插入操作，在表頭進(jìn)行刪除操作線性表。它是一個(gè)先進(jìn)先出（ＦＩＦＯ）線性表。比如：隊(duì)列Q=(a1

,a2,a3,……….,an-1,an)在隊(duì)尾插入元素稱為入隊(duì)；在隊(duì)首刪除元素稱為出隊(duì)。隊(duì)首隊(duì)尾問(wèn)：為何要設(shè)計(jì)隊(duì)列？它有什么獨(dú)特用途？離散事件模擬（模擬事件發(fā)生先后次序,比如CPU芯片中指令譯碼隊(duì)列）；操作系統(tǒng)中作業(yè)調(diào)度（一個(gè)CPU執(zhí)行多個(gè)作業(yè)）；3.簡(jiǎn)化程序設(shè)計(jì)。答：數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第34頁(yè)隊(duì)實(shí)現(xiàn)方式是本節(jié)重點(diǎn)，關(guān)鍵是掌握入隊(duì)和出隊(duì)操作。

詳細(xì)實(shí)現(xiàn)依存放結(jié)構(gòu)（鏈隊(duì)或次序隊(duì)）不一樣而不一樣。1.鏈隊(duì)列2.次序隊(duì)隊(duì)抽象數(shù)據(jù)類型定義：ADTQueue{數(shù)據(jù)對(duì)象：D=……數(shù)據(jù)關(guān)系：R=……基本操作：……}ADTQueue建隊(duì)、入隊(duì)或出隊(duì)、判隊(duì)空或隊(duì)滿等，教材P59-60羅列了9種基本操作。重點(diǎn)是循環(huán)次序隊(duì)數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第35頁(yè)鏈隊(duì)列類型定義：typedefstruct{QueuePtrfront;//隊(duì)首指針QueuePtrrear;//隊(duì)尾指針}LinkQueue;結(jié)點(diǎn)類型定義：

typedefStructQNode{QElemTypedata;//元素StructQNode*next;//指向下一結(jié)點(diǎn)指針}Qnode,*QueuePtr;關(guān)于整個(gè)鏈隊(duì)總體描述鏈隊(duì)中任一結(jié)點(diǎn)結(jié)構(gòu)因簡(jiǎn)單而先介紹1.鏈隊(duì)列數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第36頁(yè)討論：空鏈隊(duì)特征？Q(隊(duì)尾)(隊(duì)首)fronta1a2a3^rearpfront^rear③怎樣實(shí)現(xiàn)鏈隊(duì)入隊(duì)和出隊(duì)操作？②鏈隊(duì)會(huì)滿嗎？front=rear普通不會(huì)，因?yàn)閯h除時(shí)有free動(dòng)作。除非內(nèi)存不足！入隊(duì)（尾部插入）：rear->next=S;rear=S;出隊(duì)（頭部刪除）：front->next=p->next;SD^鏈隊(duì)示意圖：完整操作函數(shù)見(jiàn)教材P62下數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第37頁(yè)采取動(dòng)態(tài)分配空間形式次序隊(duì)類型定義：建隊(duì)關(guān)鍵語(yǔ)句：q.base=(QElemType*)malloc(sizeof(QElemType）*QUEUE_MAXSIZE);//分配空間關(guān)于整個(gè)次序隊(duì)總體描述#defineQUEUE-MAXSIZE100//最大隊(duì)列長(zhǎng)度typedefstruct{QElemType*base;//隊(duì)列基址intfront;//隊(duì)首指針intrear;//隊(duì)尾指針}SqQueue次序隊(duì)中每個(gè)結(jié)點(diǎn)結(jié)構(gòu)描述在此省略，是QElemType類型。2.次序隊(duì)數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第38頁(yè)Q(隊(duì)尾)(隊(duì)首)fronta1a2a3dataa40.......99rear②隊(duì)列會(huì)滿嗎？極易裝滿！因?yàn)閿?shù)組通常有長(zhǎng)度限制，而其前端空間無(wú)法釋放。①空隊(duì)列特征？約定：front=rear隊(duì)尾后地址入隊(duì)(尾部插入)：Q[rear]=e;rear++

;

出隊(duì)(頭部刪除)：e=Q[front];front++;

討論：假溢出！有缺點(diǎn)③怎樣實(shí)現(xiàn)入隊(duì)和出隊(duì)操作？關(guān)鍵語(yǔ)句以下：用base做數(shù)組名e次序隊(duì)示意圖：數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第39頁(yè)處理假溢出路徑———采取循環(huán)隊(duì)列答：在次序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。問(wèn)：什么叫“假溢出”？怎樣處理？數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第40頁(yè)a3a2a10123N-1rearfront循環(huán)隊(duì)列（臆造）新問(wèn)題：在循環(huán)隊(duì)列中，空隊(duì)特征是front=rear；隊(duì)滿時(shí)也會(huì)有front=rear；判決條件將出現(xiàn)二義性！處理方案有三：①使用一個(gè)計(jì)數(shù)器統(tǒng)計(jì)隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）；②加設(shè)標(biāo)志位，刪除時(shí)置1,插入時(shí)置0,則可識(shí)別當(dāng)前front=rear屬于何種情況③人為浪費(fèi)一個(gè)單元，則隊(duì)滿特征可改為front=(rear+1)%N；次序隊(duì)列a3a2a1frontrear0123..N-1數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第41頁(yè)隊(duì)空條件:front=rear(初始化時(shí)：front=rear)隊(duì)滿條件：front=(rear+1)%N(N=maxsize)隊(duì)列長(zhǎng)度（即數(shù)據(jù)元素個(gè)數(shù)）：L=（N＋rear－front）%NJ2J3 J1J4

J5frontrear

實(shí)際中常選取方案3（人為浪費(fèi)一個(gè)單元）：即front和rear二者之一指向?qū)嵲?，另一個(gè)指向空閑元素。

問(wèn)3：在含有n個(gè)單元循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有多少個(gè)元素？N-1個(gè)6

問(wèn)1：左圖中隊(duì)列maxsizeN=？問(wèn)2：左圖中隊(duì)列長(zhǎng)度L=？5數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第42頁(yè)（Ａ）r－f（Ｂ）（n＋f－r）%n（Ｃ）n＋r－f（Ｄ）（n＋r－f）%n要分析4種公式哪種最合理？當(dāng)r≥f時(shí)（A）合理；當(dāng)r<f時(shí)（C）合理；答：綜合2種情況，以（D）表示最為合理例2：在一個(gè)循環(huán)隊(duì)列中，若約定隊(duì)首指針指向隊(duì)首元素前一個(gè)位置。那么，從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先移動(dòng)隊(duì)首指針取出元素√，后。例1：數(shù)組Ｑ[n]用來(lái)表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素前一位置，r為隊(duì)尾元素位置。假定隊(duì)列中元素個(gè)數(shù)小于n，計(jì)算隊(duì)列中元素公式為:數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第43頁(yè)例3：一循環(huán)隊(duì)列以下列圖所表示，若先刪除4個(gè)元素，接著再插入4個(gè)元素，請(qǐng)問(wèn)隊(duì)頭和隊(duì)尾指針?lè)謩e指向哪個(gè)位置?J2J3 J1J4

J5front=1rear=0解：由圖可知，隊(duì)頭和隊(duì)尾指針初態(tài)分別為front=1和rear=0。刪除4個(gè)元素后f=5；再插入4個(gè)元素后，r=(0+4)%6=4

front=5J6J5J7J8J9rear=4rear=0front=5數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第44頁(yè)討論：循環(huán)隊(duì)列基本操作怎樣實(shí)現(xiàn)？以建隊(duì)、入隊(duì)和出隊(duì)三種基本操作為例1）初始化一個(gè)空隊(duì)列算法要求：生成一空隊(duì)列算法操作：為隊(duì)列分配基本容量空間設(shè)置隊(duì)列為空隊(duì)列，其特征即：

front=rear=0（也可為任意單元，如1，2，…甚至-1）數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第45頁(yè)建隊(duì)完整算法：StatusInitQueue(SqQueue&q)//初始化空循環(huán)隊(duì)列q{q.base=(QElemType*)malloc(sizeof(QElemType）*QUEUE_MAXSIZE);//分配空間if(!q.base)exit(OVERFLOW);//內(nèi)存分配失敗，退出程序

q.front=q.rear=0;//置空隊(duì)列returnOK;}//InitQueue;數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第46頁(yè)算法說(shuō)明：向循環(huán)隊(duì)列隊(duì)尾插入一個(gè)元素分析：(1)插入前應(yīng)該先判斷隊(duì)列是否滿？if((q.rear+1)

%

QUEUE_MAXSIZE)==q.front)returnERROR;(2）插入動(dòng)作

q.base[q.rear]=e;q.rear=(q.rear+1)%QUEUE_MAXSIZE;2）入隊(duì)操作隊(duì)列尺寸數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第47頁(yè)StatusEnQueue(SqQueue&q,QElemTypee){//向循環(huán)隊(duì)列q隊(duì)尾加入一個(gè)元素eif((q.rear+1)%QUEUE_MAXSIZE==q.front)returnERROR;//隊(duì)滿則上溢，無(wú)法再入隊(duì)

q.base[q.rear]=e;//新元素e入隊(duì)q.rear=(q.rear+