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