簡介:棧和隊列,棧的定義和基本運算/順序棧/鏈棧/隊列的定義和基本運算/順序隊列/鏈式隊列/實訓,唐懿芳,數(shù)據(jù)結(jié)構與算法,,目錄,CONTENTS,,,棧的定義和基本運算,1、棧的定義2、棧的基本運算,01,數(shù)據(jù)結(jié)構與算法,第一節(jié)棧的定義和基本運算,數(shù)據(jù)結(jié)構與運算,生活中的棧與隊列棧和隊列是特殊的線性表棧與隊列的特征LIFOLASTINFIRSTOUTFIFOFIRSTINFIRSTOUT,棧的定義,堆棧簡稱為棧,是限定只能在表的一端進行插入和刪除操作的線性表。在表中,允許插入和刪除的一端稱作“棧頂”,另一端稱作“棧底”。通常將元素插入棧頂?shù)牟俜Q作為“入?!保ㄟM?;驂簵#?,稱刪除棧頂元素的操作為“出棧”,棧底,棧頂,入棧,出棧,圖31堆棧,,,,,A1,A2,AN,,,,第一節(jié)棧的定義和基本運算,棧的基本運算,堆棧的基本運算如下。1STACKINIT初始化堆棧。2STACKEMPTYS判定棧S是否為空。3STACKLENGTHS求堆棧S的長度。4GETTOPS獲取棧頂元素的值。5PUSHS,E將元素E進棧。6POPS,出棧(刪除棧頂元素)。,數(shù)據(jù)結(jié)構與運算,第一節(jié)棧的定義和基本運算,棧的存儲結(jié)構,兩種存儲結(jié)構1順序棧采用順序結(jié)構存儲2鏈棧采用鏈式結(jié)構存儲,數(shù)據(jù)結(jié)構與運算,,,順序棧,1、順序棧的存儲結(jié)構3、順序棧的案例2、順序棧的基本運算,02,數(shù)據(jù)結(jié)構與算法,第二節(jié)順序棧,順序棧的存儲結(jié)構,,MAXSIZE1,DEFINEMAXSIZE堆棧可能達到的最大長度TYPEDEFSTRUCT{ELEMENTTYPEELEMMAXSIZEINTTOP/棧頂位置/}SEQSTACK,棧底,棧頂,,,,,A0,A1,AN1,,,備用空間,棧滿和棧空的條件是什么,棧滿TOPMAXSIZE1??誘OP1,數(shù)據(jù)結(jié)構與運算,,SEQSTACKSTACKINIT{SEQSTACKSSTOP1RETURNS},,順序棧的基本運算,,初始化堆棧STACKINIT,,,INTSTACKEMPTYSEQSTACKS{RETURNSTOP1},,判定棧S是否為空STACKEMPTYS,,,INTSTACKLENGTHSEQSTACKS{RETURNSTOP1},,求堆棧S的長度STACKLENGTHS,,,ELEMENTTYPEGETTOPSEQSTACKS{IFSTACKEMPTYS/空棧/RETURNNILRETURNSELEMSTOP},,獲取棧頂元素的值GETTOPS,,,VOIDPUSHSEQSTACKS,ELEMENTTYPEE{IFSTOPMAXSIZE1/棧滿/PRINTF“FULL”ELSE{STOPSELEMSTOPE}},,進棧PUSHS,E,,,ELEMENTTYPEPOPSEQSTACKS{IFSTOP1/棧空/RETURNNIL/返回空值/ELSE{ESELEMSTOPSTOPRETURNE}},,出棧POPS,,第二節(jié)順序棧,數(shù)據(jù)結(jié)構與運算,順序棧案例1,【例1】假設有兩個棧共享一個一維數(shù)組空間0,MAXSIZE-1,其中一個棧用數(shù)組的第0單元(元素)作為棧底,另一棧用數(shù)組的第MAXSIZE-1號單元(元素)作為棧底(即兩個堆棧從兩端向中間延伸),其對應的類型描述如下DEFINEMAXSIZE堆??赡苓_到的最大長度TYPEDEFSTRUCT{ELEMENTTYPEELEMMAXSIZEINTTOP1,TOP2/棧頂位置/}SHARESTACK,第二節(jié)順序棧,數(shù)據(jù)結(jié)構與運算,順序棧案例2,,則棧1的棧頂表示為STOP1,棧2的棧頂表示為STOP2棧1的進棧操作使得棧頂1右(后)移,即STOP1,棧2進棧操作使得棧頂2左(前)移,即STOP1棧滿時兩個棧頂相鄰,即STOP11==STOP2。,圖32共享堆棧,,,,,,,,棧1,,,棧頂2,,A1,AN,B1,BM,棧2,棧底1,,棧底2,0,,MAXSIZE1,,棧頂1,第二節(jié)順序棧,數(shù)據(jù)結(jié)構與運算,順序棧案例3進棧,,VOIDPUSHSHARESTACKS,ELEMENTTYPEE,INTI/將元素E壓入棧II1,2/{IFSTOP11STOP2/棧滿/PRINTF“FULL”ELSE{IFI1{STOP1SELEMSTOP1E}ELSE{STOP2SELEMSTOP2E}}},第二節(jié)順序棧,數(shù)據(jù)結(jié)構與運算,順序棧案例4出棧,,ELEMENTTYPEPOPSHARESTACKS,INTI/棧II1,2出棧/{IFI1IFSTOP11/棧1空/RETURNNILELSE{ESELEMSTOP1STOP1RETURNE}IFI2IFSTOP2MAXSIZE/棧2空/RETURNNILELSE{ESELEMSTOP2STOP2RETURNE}},第二節(jié)順序棧,數(shù)據(jù)結(jié)構與運算,,,鏈棧,1、棧的鏈式存儲結(jié)構2、鏈棧的基本運算,03,數(shù)據(jù)結(jié)構與算法,第三節(jié)鏈棧,鏈棧的存儲結(jié)構,,DEFINEMAX_SIZE100//設置最大元素個數(shù)TYPEDEFINTELEMTYPETYPEDEFSTRUCTSNODE{ELEMENTTYPEDATASTRUCTSNODENEXT}STACKNODETYPEDEFSTACKNODELINKSTACK/LINKSTACK為指向STACKNODE的指針類型/,,圖36鏈棧,棧頂,,,,,,,,,,,A1,AN,AN1,棧底,DATA,NEXT,Λ,S,,,,數(shù)據(jù)結(jié)構與運算,第三節(jié)鏈棧,鏈棧的基本操作,,1.棧初始化棧的初始化實現(xiàn)比較簡單,算法如下LINKSTACKSTACKINIT{LINKSTACKSLINKSTACKMALLOCSIZEOFSTACKNODESNEXT0RETURNS}/STACKINIT/2.判斷棧是否為空在判斷棧是否為空時,只需將棧頂指針SNEXT值與NULL相比即可,算法實現(xiàn)如下INTSTACKEMPTYLINKSTACKS{RETURNSNEXTNULL}/STACKEMPTY/,數(shù)據(jù)結(jié)構與運算,第三節(jié)鏈棧,鏈棧的基本操作,,3.求棧的長度INTSTACKLENGTHLINKSTACKS{LINKSTACKPSNEXTINTLENGTH0WHILEP{LENGTHPPNEXT}RETURNLENGTH}/STACKLENGTH/4.進棧操作//插入元素E為新的棧頂元素VOIDPUSHLINKSTACKS,INTE{LINKSTACKPSTACKNODEMALLOCSIZEOFSTACKNODEPDATAEPNEXTSNEXT//如圖②把當前的棧頂元素賦值給新結(jié)點的直接后繼SNEXTP//如圖③將新的結(jié)點P賦值給棧頂指針}/PUSH/,數(shù)據(jù)結(jié)構與運算,第三節(jié)鏈棧,鏈棧的基本操作,,5.出棧操作//若棧不空,則刪除棧頂元素,用E返回值INTPOPLINKSTACKS{IFSTACKEMPTYS/???RETURNNIL/返回空值/ELSE{LINKSTACKPSNEXT/如圖①將棧頂結(jié)點賦值給P/INTE0SNEXTPNEXT/如圖②使得棧頂指針下移1位,指向后一結(jié)點/EPDATAFREEP/釋放結(jié)點P/RETURNE}}/POP/,數(shù)據(jù)結(jié)構與運算,第三節(jié)鏈棧,鏈棧的基本操作,,6.獲取棧頂元素根據(jù)棧頂指針S,可以直接獲取最后入棧的元素。應該注意的是,在進行讀取之前,也要進行??諜z查。相關的算法實現(xiàn)如下INTGETTOPLINKSTACKS{IFSTACKEMPTYSRETURNNILRETURNSNEXTDATA}/GETTOP/,數(shù)據(jù)結(jié)構與運算,,,隊列,1、隊列的定義3、隊列的存儲結(jié)構2、隊列的基本運算,04,數(shù)據(jù)結(jié)構與算法,第4節(jié)隊列,隊列的定義,,隊列簡稱為隊,是限定只能在表的一端作插入運算、在另一端作刪除運算的線性表;在表中,允許插入的一端稱作“隊尾”,允許刪除的另一端稱作“隊首”(或“隊頭”);通常將元素插入隊尾的操作稱作為入隊列(或入隊),稱刪除隊首元素的操作為出隊列(或出隊)。,數(shù)據(jù)結(jié)構與運算,第4節(jié)隊列,隊列的基本運算,,,數(shù)據(jù)結(jié)構與運算,隊列的基本運算如下。1INITQUEUE初始化隊列。2QUEUEEMPTYQ判定隊列Q是否為空。3QUEUELENGTHQ求隊列Q的長度。GETHEADQ獲取隊列Q隊首元素的值。5ADDQUEUEQ,E將元素E入隊。6DELETEQUEUEQ刪除隊首元素。,第4節(jié)隊列,隊列的存儲結(jié)構,,兩種結(jié)構1順序隊列采用順序結(jié)構存儲2鏈式隊列采用鏈式結(jié)構存儲,數(shù)據(jù)結(jié)構與運算,,,順序隊列,1、隊列的順序存儲結(jié)構2、順序隊列的基本運算,05,數(shù)據(jù)結(jié)構與算法,第5節(jié)順序隊列,隊列的順序存儲結(jié)構1,,DEFINEMAXSIZEN隊列可能達到的最大長度NTYPEDEFSTRUCT{ELEMENTTYPEELEMMAXSIZEINTFRONT,REAR/隊首、隊尾指示器/}QUEUE,數(shù)據(jù)結(jié)構與運算,第5節(jié)順序隊列,隊列的順序存儲結(jié)構2,,,數(shù)據(jù)結(jié)構與運算,,,,,圖312隊列操作,,,,,,,,,,,,,A,B,C,E,REAR4,,,,,,,D,FRONT1,,,,,B,C,E,REAR4,,,,,,,D,FRONT0,,,,,FRONTREAR4,,,,,,FRONTREAR1,,A空隊,BA,B,C,D,E入隊,C出隊1次,D出隊4次,隊滿和隊空的條件是什么,隊空FRONTREAR隊滿REARMAXSIZE1,,第5節(jié)順序隊列,隊列的順序存儲結(jié)構3,,數(shù)據(jù)結(jié)構與運算,當REARMAXSIZE1時,隊列為滿,如果再加入新元素,就會產(chǎn)生“溢出“。但是這種“溢出“并不是真正的溢出,在數(shù)組的前端還可能有空位置,所以這是一種假溢出。,,,,,,,B,C,E,REAR4,,,,,,,D,FRONT0,,,,,FRONTREAR4,,,,,,,解決方法循環(huán)隊列,第5節(jié)順序隊列,隊列的順序存儲結(jié)構4,,數(shù)據(jù)結(jié)構與運算,為了能夠充分的使用數(shù)組中的存儲空間,把數(shù)組的前端和后端連接起來,形成一個環(huán)形的表,即把存儲隊列元素的表從邏輯上看成一個環(huán),成為循環(huán)隊列(CIRCULARQUEUE)。,FRONT,,,,,FRONT,REAR,FRONT,REAR,A,,,FRONT,REAR,B,C,D,,,FRONT,REAR,A,B,C,D,,,FRONT,REAR,A,B,C,,,REAR,A空隊列,BA入隊列,CB,C入隊列,DD入隊列(隊滿),E出隊1次,F出隊3次(隊空),隊頭指針進1FRONTFRONT1MAXSIZE;隊尾指針進1REARREAR1MAXSIZE;,第5節(jié)順序隊列,隊列的順序存儲結(jié)構4,數(shù)據(jù)結(jié)構與運算,以下是隊空的幾種情況,初始化時FRONTREAR0循環(huán)隊列為空的條件是FRONTREAR,,,FRONT,REAR,A空隊列,FRONT,,,REAR,F出隊3次(隊空),FRONT0REAR0,FRONT4REAR4,第5節(jié)順序隊列,隊列的順序存儲結(jié)構4,數(shù)據(jù)結(jié)構與運算,循環(huán)隊列為滿的條件是FRONTREAR1MAXSIZE,,,FRONT,REAR,A,B,C,D,以下是隊滿的幾種情況,FRONT0REAR4,,,FRONT,REAR,A,B,C,D,FRONT3REAR2,,,FRONT,REAR,B,C,D,A,FRONT1REAR0,第5節(jié)順序隊列,順序隊列的基本運算1,1)、初始化隊列INITQUEUECIRQUEUEINITQUEUE{CIRQUEUEQQFRONTQREAR0RETURNQ}2)、判定隊列Q是否為空QUEUEEMPTYQINTQUEUEEMPTYCIRQUEUEQ{RETURNQFRONTQREAR},數(shù)據(jù)結(jié)構與運算,第5節(jié)順序隊列,順序隊列的基本運算2,3、求隊列Q的長度QUEUELENGTHQINTQUEUELENGTHCIRQUEUEQ{RETURNQREARMAXSIZEQFRONTMAXSIZE},數(shù)據(jù)結(jié)構與運算,,,FRONT,REAR,A,B,C,FRONT0REAR3,,,FRONT,REAR,A,B,C,D,FRONT3REAR2,第5節(jié)順序隊列,順序隊列的基本運算3,4、獲取隊列Q隊首元素的值GETHEADQELEMENTTYPEGETHEADCIRQUEUEQ{IFQUEUEEMPTYQRETURN1RETURNQELEMQFRONT1MAXSIZE},數(shù)據(jù)結(jié)構與運算,,,FRONT,REAR,,,FRONT,REAR,A,B,C,FRONT0REAR3,,,FRONT,REAR,A,B,D,FRONT4REAR2,第5節(jié)順序隊列,順序隊列的基本運算4,5、ADDQUEUEQ,E將元素E入隊VOIDADDQUEUECIRQUEUEQ,ELEMENTTYPEE{IFQFRONTQREAR1MAXSIZEPRINTF“\NFULL“ELSE{QREARQREAR1MAXSIZEQELEMQREARE}},數(shù)據(jù)結(jié)構與運算,6、DELETEQUEUEQ刪除隊首元素ELEMENTTYPEDELETEQUEUECIRQUEUEQ{ELEMENTTYPEEIFQFRONTQREARRETURN1ELSE{EQELEMQFRONT1MAXSIZEQFRONTQFRONT1MAXSIZERETURNE}},,,鏈式隊列,1、鏈式隊列的存儲結(jié)構2、鏈式隊列的基本運算,06,數(shù)據(jù)結(jié)構與算法,第6節(jié)鏈式隊列,鏈式隊列的存儲結(jié)構,數(shù)據(jù)結(jié)構與運算,361隊列的鏈式存儲結(jié)構,隊首指針FRONT,圖316鏈隊列,,,隊尾指針REAR,,,,Λ,,,,,A2,A1,AN,ΛΛ,頭結(jié)點,,,隊首指針FRONT,隊尾指針REAR,B非空鏈隊列,A空鏈隊列,第6節(jié)鏈式隊列,鏈式隊列的存儲結(jié)構,數(shù)據(jù)結(jié)構與運算,TYPEDEFSTRUCTQNODE{ELEMENTTYPEDATA//結(jié)點數(shù)據(jù)域STRUCTQNODENEXT//結(jié)點指針域}QUEUENODETYPEDEFSTRUCT{QUEUENODEFRONT,REAR//隊首和隊尾指針}LINKQUEUE,第6節(jié)鏈式隊列,鏈式隊列的基本操作,數(shù)據(jù)結(jié)構與運算,1.隊列初始化。隊列的初始化實現(xiàn)比較簡單,算法如下LINKQUEUEINITQUEUE{QUEUENODEPLINKQUEUEQPQUEUENODEMALLOCSIZEOFQUEUENODEPNEXTNULLQFRONTQREARPRETURNQ},2判斷隊列是否為空INTQUEUEEMPTYLINKQUEUEQ{RETURNQFRONTQREAR},第6節(jié)鏈式隊列,鏈式隊列的基本操作,數(shù)據(jù)結(jié)構與運算,3.獲取隊首元素ELEMENTTYPEGETHEADLINKQUEUEQ{IFQUEUEEMPTYQRETURNNILRETURNQFRONTNEXTDATA},第6節(jié)鏈式隊列,鏈式隊列的基本操作,數(shù)據(jù)結(jié)構與運算,4入隊操作//插入元素E為Q的新的隊尾元素VOIDADDQUEUELINKQUEUEQ,ELEMENTTYPEE{QUEUENODEPPQUEUENODEMALLOCSIZEOFQUEUENODEIFP{PRINTF“存儲分配失敗\N”RETURN}PDATAEPNEXTNULLQREARNEXTP//把擁有元素E新結(jié)點P賦值給原隊尾結(jié)點的后繼QREARP//把當前的P設置為隊尾結(jié)點,REAR指向P},第6節(jié)鏈式隊列,鏈式隊列的基本操作,數(shù)據(jù)結(jié)構與運算,5.出隊操作//若隊列不空,刪除Q的隊頭元素,用E返回其值ELEMENTTYPEDELETEQUEUELINKQUEUEQ{IFQUEUEEMPTYQRETURN1ELSE{ELEMENTTYPEEQUEUENODEPPQFRONTNEXT//將欲刪除的隊頭結(jié)點暫存給PQFRONTNEXTPNEXT//將原隊頭結(jié)點后繼賦值給頭結(jié)點后繼EPDATA//將欲刪除的隊頭結(jié)點的值賦值給EIFPQREARQREARQFRONTFREEPRETURNE}},,,本章實訓,07,數(shù)據(jù)結(jié)構與算法,,,約瑟夫環(huán)的實現(xiàn)(P58),,鏈式隊列分隊簡單實現(xiàn),順序共享棧的簡單實現(xiàn),,棧和隊列,,,,,實訓1,實訓3,實訓2,,,第七節(jié)實訓,數(shù)據(jù)結(jié)構與運算,,,THANKS,,完,數(shù)據(jù)結(jié)構與算法,
下載積分: 4 賞幣
上傳時間:2024-01-07
頁數(shù): 44
大?。?1.62(MB)
子文件數(shù):