棧、隊(duì)列及其應(yīng)用.ppt

《棧、隊(duì)列及其應(yīng)用.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、線性表的應(yīng)用1、【問題描述】線性表a和b分別表示兩個(gè)線性表，它們的數(shù)據(jù)元素類型相同，現(xiàn)要將b中存在而a中不存在的數(shù)據(jù)元素插入到線性表a中。設(shè)線性表a的長度與線性表b的長度之和不超過線性表a允許的最大長度。【參考程序】proceduIreunion(vara：list；b：list)；beginn：=length(a)；fori：=1tolength(b)dobegingetlist(b，i，x)；{取線性表b中第i位上的數(shù)給T}k：=loclist(a，x)；{返回z在線性表a中的位置}ifk=0thenbegininslist(a，n

2、+1，x)；{將z插入線性表a的末尾}n：=n+1；end；end；end；線性表的應(yīng)用2、【問題描述】已知線性表。和b中的數(shù)據(jù)元素按遞增的順序排列，現(xiàn)要求將a和b歸并為一個(gè)新的線性表c，c中的數(shù)據(jù)元素仍按遞增排列。①用數(shù)組實(shí)現(xiàn)②用鏈表實(shí)現(xiàn)線性表的應(yīng)用3、Joseph(約瑟夫)問題【問題描述】m只猴子要選大王，選舉辦法如下：所有猴子按1…m編號圍坐一圈，從第1號開始按順序1，2，…，n報(bào)數(shù)，凡報(bào)到竹的猴子退出到圈外，如此循環(huán)，直到圈內(nèi)只剩下一只猴子時(shí)，這只猴子就是大王。m和咒由鍵盤輸入，打印出最后剩下的那只猴子的編號。運(yùn)行示例：Inpu

3、tm，n：83Themonkeykingisno．7①用數(shù)組實(shí)現(xiàn)【算法分析】在確定程序設(shè)計(jì)方法之前首先來考慮如何組織數(shù)據(jù)，由于要記錄m只猴子的狀態(tài)，可利用含m個(gè)元素的數(shù)組monkey來實(shí)現(xiàn)。利用元素下標(biāo)代表猴子的編號，元素的值表示猴子的狀態(tài)，用monkeyEk]=l表示第k只猴子仍在圈中，monkeyEk-]=0則表示第k只猴子已經(jīng)出圈。程序采用模擬選舉過程的方法，開始時(shí)將報(bào)數(shù)變量count置為1；用變量current表示當(dāng)前報(bào)數(shù)的猴子的編號，初始時(shí)也置為1；變量。out記錄出圈猴子數(shù)。當(dāng)count=n時(shí)，對當(dāng)前報(bào)數(shù)的猴子做出圈處理，即

4、monkey[current]：=O，count：=0,out：=out+1。然后繼續(xù)往下報(bào)數(shù)，直到圈中只剩一只猴子為止(即out=m-1)。②用數(shù)組實(shí)現(xiàn)【算法分析】在組織數(shù)據(jù)時(shí)，也可以考慮只記錄仍在圈中的猴子的情況。用一個(gè)線性表按編號由小到大依次記錄圈中所有猴子的編號，每當(dāng)有猴子出圈時(shí)，即從線性表中刪除對應(yīng)元素，表中元素減少一個(gè)。程序中用變量rest表示圈中剩余的猴子數(shù)，即線性表中元素的總數(shù)。③用單向循環(huán)鏈表實(shí)現(xiàn)【算法分析】結(jié)點(diǎn)的數(shù)據(jù)域?yàn)楹镒拥木幪?，指針域指向下一個(gè)猴子。報(bào)數(shù)實(shí)際上是計(jì)數(shù)，只要設(shè)一個(gè)計(jì)數(shù)器就可以了。當(dāng)計(jì)數(shù)器由0變化到n

5、時(shí)，刪除該結(jié)點(diǎn)，計(jì)數(shù)器回0繼續(xù)計(jì)數(shù)(或者用求余運(yùn)算)。直到鏈表中剩下一個(gè)結(jié)點(diǎn)。線性表的應(yīng)用4、一元多項(xiàng)式加減運(yùn)算【問題描述】給定一個(gè)一元n次多項(xiàng)式p和一個(gè)一元m次多項(xiàng)式Q，求它們的和與差?！舅惴ǚ治觥窟x方法②。遍歷兩個(gè)單鏈表．根據(jù)指數(shù)和系數(shù)進(jìn)行相應(yīng)的加減，生成一個(gè)新鏈表系數(shù)為0的結(jié)點(diǎn)刪除掉(或不生成這種結(jié)點(diǎn))，輸出該鏈表。特殊線性結(jié)構(gòu)——棧棧(stack)是一種特殊的線性表，這種線性表限定其只能在表尾進(jìn)行插入或刪除數(shù)據(jù)元素。棧頂棧底a1a2an…進(jìn)棧出棧棧的存儲方式順序存儲：通常?？梢杂庙樞虻姆绞酱鎯Γ褪怯靡唤M連續(xù)的存儲單元依次存放自

6、棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)設(shè)立指針top（稱為棧頂指針）以指示棧頂元素的當(dāng)前位置。1.用記錄方式實(shí)現(xiàn)：Typestack=recorddata:array[1..smaxsize]ofselement;top:0..smaxsize;end;2.用數(shù)組方式實(shí)現(xiàn)Typeatype=array[1..smaxsize]ofselement;Varstack:arraytype;top:integer;棧的存儲方式鏈接存儲：即鏈棧，目的是提高空間利用率，但編程復(fù)雜度提高了。typelink=^node;node=recorddata:elem

7、ent;next:link;end;Vartop:link;?；静僮鞯膶?shí)現(xiàn)順序存儲棧的操作?棧的初始化Procedureinistack(vars:stack);begins.top=0end;?判斷棧空functionsempty(s:stack):boolean;beginsempty:=(s.top=0)end;?入棧Procedurepush(vars:stack;x:selement);beginifs.top=smaxsizethenwriteln(‘overflow’)elsebegins.top:=s.top+1;s.

8、data[s.top]end;棧基本操作的實(shí)現(xiàn)順序存儲棧的操作?出棧Procedurepop(vars:stack);beginifsempty(s)thenwriteln(‘underflow’)else