2-基本數據結構1

ACM/ICPC程序設計基本數據結構及其在程序設計中的應用張淑平程序=數據結構+算法數據結構(DataStructure)是數據的計算機表示和相應的一組操作。算法(Algorithm)就是解決問題的方法或過程?；緮祿Y構線性結構非線性結構集合樹結構圖結構線性表棧隊列串線性結構線性表:由n個元素組成的有限序列。每個元素有確定的前驅和后繼。

元素之間的關系僅限于前趨、后繼關系表、棧、隊列、串

元素的存儲方式數組鏈表線性結構由n個元素組成的有限序列。每個元素有確定的前驅和后繼。

表：不限制元素的插入和刪除位置。有n+1個位置可供插入，n個元素可供刪除棧：插入和刪除操作只允許在表尾進行隊列：在表尾插入、在表頭刪除串：元素為字符的線性表，有求子串、子串定位、子串替換等操作(a1，a2，…，ai，…，an)表頭元素表尾元素數據結構中的存儲結構－－元素及元素間關系的存儲數組鏈表數組用一組連續(xù)的存儲單元依次存儲數據元素.表中任一元素可以隨機存取.插入或刪除一個元素需要移動其他元素.a1a2...aian...dai+1由下標確定數組元素a[i]：Loc(ai)=Loc(a1)+(i-1)*d(1≤i≤n)例如：由n個元素構成的一維數組a鏈表鏈式存儲:任意存儲單元存儲元素鏈表結點包括數據域和指針域插入或刪除一個元素,只需修改結點指針域訪問任一元素必須從鏈表頭指針開始a2ai...a1ai+1...an...鏈表結點鏈式存儲:任意存儲單元存儲元素鏈表結點包括數據域和指針域插入或刪除一個元素,只需修改結點指針域訪問任一元素必須從鏈表頭指針開始數據data指針next

structNode{

ElemTypedata；//數據元素

struct

Node*next；//指向后繼結點的指針};單向鏈表線性表：(a1，a2，…，ai-1，ai，ai+1，…，an)(a)單向鏈表…a2a1an∧an-1…aiai-1ai+1head頭結點(b)帶頭結點的單向鏈表…a2a1an∧an-1…aiai-1ai+1head雙向鏈表和循環(huán)鏈表線性表：(a1，a2，…，ai-1，ai，ai+1，…，an)head…a1∧a2an-1anai…∧(a)雙向鏈表taila2a1anan-1…(b)循環(huán)單鏈表單鏈表的插入和刪除鏈式存儲:任意存儲單元存儲元素鏈表結點包括數據域和指針域插入或刪除一個元素，只需修改結點指針域訪問任一元素必須從鏈表頭指針開始頭結點帶頭結點的單向鏈表…a2a1an∧an-1…aiai-1ai+1head單鏈表中插入元素將元素ai所在結點的地址賦給元素e結點的指針域：S->next=P->next;aiai-1…ai+1…PeS修改元素ai-1所在結點指針域的值：

P->next=S;②①單鏈表中刪除元素ai修改元素ai-1所在結點指針域的值：P->next=P->next->next;aiai-1…ai+1…P例1:UglyNumbersUglynumbersarenumberswhoseonlyprimefactorsare2,3or5.Thesequence1,2,3,4,5,6,8,9,10,12,15,...showsthefirst11uglynumbers.Byconvention,1isincluded.Writeaprogramtofindandprintthe1500'thuglynumber.算法思路:一個正整數m可表示如下：

m=(p1)j1*(p2)j2*…*(pn)jnUglynumber=2j1*3j2*5j3(j1,j2,j3>=0)在已知序列中,找一個最小的數,使得它乘以2比已知序列最后一個元素大;找一個最小的數,使得它乘以3比最后一個元素大;找一個最小的數,使得它乘以5比最后一個元素大.在這三個乘積中找最小的添加到表尾,反復按此規(guī)則構造遞增序列,直到表中有1500個元素?？梢杂脭到M預先分配1500個單元,也可以用鏈表動態(tài)分配.例2：TheBlocksProblem

編號為0~n-1的n個木塊，放在編號為0~n-1的n個格子里,可對它們進行四種有效的操作。01234n-1...InitialBlockWorldmoveaontob：先將a和b上的其他木塊移回到它們的初始位置，然后將木塊a摞在木塊b上.moveaoverb：先將木塊a上的其他木塊移到它們的初始位置后，然后將木塊a摞到包含了木塊b的那一堆木塊上面pileaontob：先將木塊b上的所有木塊移回到它們的初始位置，然后將木塊a及其上的木塊移到木塊b上.

pileaoverb：將包含木塊a的那一摞木塊移到包含了木塊b的那一堆木塊上面.moveaontob先將a和b上的其他木塊移回到它們的初始位置，然后將木塊a摞在木塊b上.01234567890123456789Example:move3onto6012345678901234567893moveaoverb先將木塊a上的其他木塊移到它們的初始位置后，然后將木塊a摞到包含了木塊b的那一堆木塊上面.01234567890123456789Example:move3over6012345678901234567893pileaontob

先將木塊b上的所有木塊移回到它們的初始位置，然后將木塊a及其上的木塊移到木塊b上.Example:pile3onto6012345678901234567890123456780123456789999012345678012345678pileaoverb將包含木塊a的那一摞木塊移到包含了木塊b的那一堆木塊上面.Example:pile3over6012345678901234567890123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

輸入數據樣本0:01:19242:3:34:5:58766:7:8:9:

input：output：10move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程：InitialBlockWorld01234567890123456789格子編號10move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：01234567890123456789Anycommandinwhicha=borinwhichaandbareinthesamestackofblocksisanillegalcommand.Allillegalcommandsshouldbeignoredandshouldhavenoaffectontheconfigurationofblocks.10move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：01234567890123456789output：10move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理結果012345678901234567890:01:19242:3:34:5:58766:7:8:9:

input：分析設計的操作:f(i):

把疊在木塊i上的其他木塊放回初始位置.m(i,j):

把i及其以上的木塊全疊到包含j的上方.moveaontob=>f(a),f(b),m(a,b)moveaoverb=>f(a),m(a,b)pileaontob=>f(b),m(a,b)pileaoverb=>m(a,b)按以上規(guī)則，用鏈表的操作直接模擬即可.數據結構設計設計的數據結構:structNode{

intNo；//木塊編號

structNode*next；//指向后繼結點的指針};structNode*Station[25];intBplace[25];0∧Station[0]1∧Station[1]2∧Station[2]3∧Station[3]4∧Station[4]5∧Station[5]6∧Station[6]7∧Station[7]8∧Station[8]9∧Station[9]0Bplace[0]1Bplace[1]2Bplace[2]3Bplace[3]4Bplace[4]5Bplace[5]6Bplace[6]7Bplace[7]8Bplace[8]9Bplace[9]示例：012345678901234567890Station[0]1Station[1]2Station[2]3Station[3]4Station[4]5Station[5]6Station[6]7Station[7]8Station[8]∧∧∧∧9∧∧∧∧∧∧Station[9]0Bplace[0]1Bplace[1]1Bplace[2]3Bplace[3]4Bplace[4]5Bplace[5]6Bplace[6]5Bplace[7]5Bplace[8]1Bplace[9]pile9over6p示例(續(xù))：012345678901234567890Station[0]1Station[1]2Station[2]3Station[3]4Station[4]5Station[5]6Station[6]7Station[7]8Station[8]∧∧∧∧9∧∧∧∧∧∧Station[9]0Bplace[0]1Bplace[1]1Bplace[2]3Bplace[3]4Bplace[4]5Bplace[5]6Bplace[6]5Bplace[7]5Bplace[8]1Bplace[9]pile9over6∧pqq->next=p示例(續(xù))：012345678901234567890Station[0]1Station[1]2Station[2]3Station[3]4Station[4]5Station[5]6Station[6]7Station[7]8Station[8]∧∧∧∧9∧∧∧∧∧∧Station[9]0Bplace[0]1Bplace[1]1Bplace[2]3Bplace[3]4Bplace[4]5Bplace[5]6Bplace[6]5Bplace[7]5Bplace[8]1Bplace[9]pile9over6∧pq66示例(續(xù))：01234567890123456789pile9over60Station[0]1Station[1]2Station[2]3Station[3]4Station[4]5Station[5]6Station[6]7Station[7]8Station[8]∧∧∧∧9∧∧∧∧∧∧Station[9]∧示例結束例3:RomanRouletteN個人排成一圈，按順時針從1到N編號。從1開始順時針數到第k個人，讓其出圈，接著數到第k個人，讓他站在出圈者的位置上。然后從出圈者的后繼位置開始數，重復上述過程直到環(huán)中只剩1個人。當N=5,k=2時，出環(huán)者的順序為：2，5，3，1；最后留下4。輸入：N，k輸出：I，使得從第I個人開始數，最后能留下第1人。模擬過程N＝5，k＝2123451出圈序列：22出去接著從1開始數模擬過程(續(xù)1)N＝5，k＝214523出圈序列：2344占據2的位置模擬過程(續(xù)2)N＝5，k＝21354出圈序列：23接著從1開始數55出去模擬過程(續(xù)3)N＝5，k＝2354出圈序列：2，5接著數1144占據5的位置模擬過程(續(xù)4)N＝5，k＝213出圈序列：2，54接著數133出去模擬過程(續(xù)5)N＝5，k＝2134出圈序列：2，5，3接著數411占據3的位置模擬過程(續(xù)6)N＝5，k＝214接著數出圈序列：2，5，3411出去，環(huán)內僅剩1人，結束1模擬過程(續(xù)7)N＝5，k＝214出圈序列：2，5，3，1計數時需要避免計算已出圈的元素分析當N＝5，k＝2時

從1開始數，留下4；從2開始數，留下5；從3開始數，留下1；因此，輸入5、2時，按照要求，應輸出3一般的情況：從1開始數，留下i；

從2開始數，留下i＋1；…

從n-i+1開始數，留下i+(n-i+1)-1=n；

從n-i+2開始數，留下i+(n-i+2)-1=1；

即對任意輸入，設程序均從1開始數，則最后第i人留下，若希望第1人留下，則應從第n－i＋2人開始數，因此輸出：n－i＋2。存儲結構用循環(huán)鏈表作為存儲結構進行模擬，除了考慮計數問題外，還特別需要注意指針的運算用數組作為存儲結構，重點在于計數的處理#include<fstream.h>#include<vector>int

surviver(int

n,intk);intmain(){

ifstreamfin("E.in");

ofstream

fout("E.out");

intn,k;for(;fin>>n>>k&&n;){if(n==1)

fout<<1<<endl;else

fout<<n-surviver(n,k)+2<<endl;}return0;}RomanRoulette程序實現(xiàn)(uva130)surviver(n,k)從第1人開始數，返回值為留下的人的編號i。輸出：n－i＋2，使第1人留下int

surviver(int

n,intk){std::vector<int>people;

inti,p=-1,p2;for(i=0;i<n;i++)people.push_back(i+1);while(people.size()>1){p=(p+k)%people.size();

for(i=0,p2=p;i<k;i++){p2=(p2+1)%people.size();if(p2==p)i--;}people[p]=people[p2];people.erase(people.begin()+p2);if(p>p2)p--;}returnpeople[0];}RomanRoulette程序實現(xiàn)(uva130)用線性表保存n個人放進環(huán)里數到第k個人繼續(xù)往后數k個人前者出去，后者取代他的位置棧和隊列棧：僅在表尾進行插入刪除的線性表,后進先出。棧常用于模擬和深度優(yōu)先搜索。隊列：在表尾插入，在表頭刪除，先進先出。隊列常用于模擬和廣度優(yōu)先搜索。表頭元素表尾元素(a1，a2，…，ai，…，an)棧的示意棧的修改是按照后進先出的原則進行的，所以棧稱為后進先出的線性表（LIFO）an

an-1

a2

a1…

棧底

入棧

出棧棧頂棧運算示例例如，有A、B、C、D、E五個元素依次進入一個棧，若得到的輸出序列是CBDAE，那么棧中的運算是如何進行的？空棧棧運算示例(續(xù))設有A、B、C、D、E五個元素依次進入一個棧，得到輸出序列CBDAE的過程。A元素A入棧棧運算示例(續(xù))A元素A入棧B元素B入棧設有A、B、C、D、E五個元素依次進入一個棧，得到輸出序列CBDAE的過程。break棧運算示例(續(xù))A元素A入棧元素B入棧BC元素C入棧設有A、B、C、D、E五個元素依次進入一個棧，得到輸出序列CBDAE的過程。break棧運算示例(續(xù))A元素A入棧元素B入棧元素C入棧CB元素C出棧C設有A、B、C、D、E五個元素依次進入一個棧，得到輸出序列CBDAE的過程。break棧運算示例(續(xù))A元素A入棧元素B入棧元素C入棧元素C出棧

C元素B出棧B,B設有A、B、C、D、E五個元素依次進入一個棧，得到輸出序列CBDAE的過程。break棧運算示例(續(xù))A元素A入棧元素B入棧元素C入棧元素C出棧元素B出棧C，BD元素D入棧設有A、B、C、D、E五個元素依次進入一個棧，得到輸出序列CBDAE的過程。breakC，B棧運算示例(續(xù))A元素A入棧元素B入棧元素C入棧元素C出棧元素B出棧元素D入棧C，B，DD元素D出棧設有A、B、C、D、E五個元素依次進入一個棧，得到輸出序列CBDAE的過程。breakC，B，D棧運算示例(續(xù))空棧元素A入棧元素B入棧元素C入棧元素C出棧元素B出棧元素D入棧元素D出棧C，B，D，A元素A出棧A設有A、B、C、D、E五個元素依次進入一個棧，得到輸出序列CBDAE的過程。break棧運算示例(續(xù))元素A入棧元素B入棧元素C入棧元素C出棧元素B出棧元素D入棧元素D出棧元素A出棧C，B，D，AE元素E入棧設有A、B、C、D、E五個元素依次進入一個棧，得到輸出序列CBDAE的過程。breakC，B，D，A棧運算示例(續(xù))空棧元素A入棧元素B入棧元素C入棧元素C出棧元素B出棧元素D入棧元素D出棧元素A出棧元素E入棧C，B，D，A，E元素E出棧E設有A、B、C、D、E五個元素依次進入一個棧，得到輸出序列CBDAE的過程。break棧運算示例(續(xù))Push(A)Push(B)Push(C)pop()pop()Push(D)pop()pop()Push(E)pop()C，B，D，A，EA，B，C，D，E設有A、B、C、D、E五個元素依次進入一個棧，得到輸出序列CBDAE的過程。例4：Railzoj1259火車有n節(jié)車廂，順序編號為1,2,3,...,n，從A駛入，從B駛出，車站里能停放任意多節(jié)車廂。一旦進入車站就不再回到A方向的鐵軌上，一旦進入B方向鐵軌，不再回車站。判斷一個指定車廂順序能否從B方向駛出。例5:AnagramsbyStack(zoj1004)問題：有一個字母序列，對它每個元素進行入棧、出棧操作。判斷是否能得到指定輸出序列，如果可以，則輸出相應的棧操作。input：madamadammoutput：[iiiioooiooiiiiooooioiioioioiooiioioiooio]8123456781234567入口出口例6：迷宮問題尋找一條從入口到出口的通路東南迷宮問題(續(xù))北(上)西(左)前進方向：上(北)、下(南)、左(西)、右(東)首先從下方開始，按照逆時針方向搜索下一步可能前進的位置迷宮問題(續(xù))入口出口在迷宮周圍加墻，避免判斷是否出界812345678123456790908123456781234567迷宮問題(續(xù))9090在尋找出口的過程中，每前進一步，當前位置入棧；每回退一步，棧頂元素出棧棧(1,1)i8123456781234567迷宮問題(續(xù))9090棧(1,1)(2,1)向下方前進一步i迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)i(3,1)向下方前進一步ii迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)(4,1)(3,1)i向下方前進一步breakiiii迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)(5,1)(3,1)(4,1)向下方前進一步breakiiiii迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)(6,1)(3,1)(4,1)(5,1)向下方前進一步breakiiiiii迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)向下方前進一步breakiiiiii@迷宮問題(續(xù))81234567812345679090向下方、右方、左方均不能前進，上方是來路，則后退棧(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)breakiiiii@@迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)向右方、左方均不能前進，下方路不通，上方是來路，則后退breakiiiii@@81234567迷宮問題(續(xù))0981234567812345679090棧(1,1)(2,1)(3,1)(4,1)(5,1)(5,2)向右方前進一步breakiiiiii@@迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(5,3)(5,2)breakiiiiiii@@81234567迷宮問題(續(xù))0981234567812345679090向下方前進一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(5,2)(5,3)breakiiiiiii@@迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(6,4)(5,2)(5,3)(6,3)ibreakiiiiiii@ii@迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(6,5)(5,2)(5,3)(6,3)(6,4)breakiiiiiii@iii@81234567迷宮問題(續(xù))0981234567812345679090向下方前進一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(7,5)(5,2)(5,3)(6,3)(6,4)(6,5)breakiiiiiii@iii@i迷宮問題(續(xù))81234567812345679090向下方前進一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(8,5)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)breakiiiiiii@iii@ii迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(8,6)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)breakiiiiiii@iii@iii迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(8,7)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)breakiiiiiii@iii@ii迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進一步，到達出口棧(1,1)(2,1)(3,1)(4,1)(5,1)(8,8)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)ii(8,7)breakiiiiiii@iii@iiii81234567迷宮問題(續(xù))981234567090用棧保存了路徑棧(1,1)(2,1)(3,1)(4,1)(5,1)(8,8)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)(8,7)迷宮問題(最短路徑)入口出口借助于隊列可求得入口到出口的最短路徑(若存在)8123456781234567909011迷宮問題(最短路徑)入口出口借助于隊列可求得入口到出口的最短路徑(若存在)812345678123456790901122迷宮問題(最短路徑)入口出口借助于隊列可求得入口到出口的最短路徑(若存在)81234567812345679090112233迷宮問題(最短路徑)入口出口借助于隊列可求得入口到出口的最短路徑(若存在)8123456781234567909011223434迷宮問題(最短路徑)入口出口借助于隊列可求得入口到出口的最短路徑(若存在)8123456781234567909011223453455迷宮問題(最短路徑)入口出口借助于隊列可求得入口到出口的最短路徑(若存在)8123456781234567909011262345345656迷宮問題(最短路徑)入口出口借助于隊列可求得入口到出口的最短路徑(若存在)8123456781234567909017126723453456576迷宮問題(最短路徑)入口出口借助于隊列可求得入口到出口的最短路徑(若存在)8123456781234567909017812678234534565786迷宮問題(最短路徑)入口出口借助于隊列可求得入口到出口的最短路徑(若存在)812345678123456790901789126782345345657896迷宮問題(最短路徑)入口出口借助于隊列可求得入口到出口的最短路徑(若存在)812345678123456790909178912678234510310456105789610迷宮問題(最短路徑)入口出口借助于隊列可求得入口到出口的最短路徑(若存在)8123456781234567909091789126782345101131110114561011578961011迷宮問題(最短路徑)入口出口借助于隊列可求得入口到出口的最短路徑(若存在)81234567812345679090917891267812234510113111011124561011125789610121112迷宮問題(最短路徑)入口出口借助于隊列可求得入口到出口的最短路徑(若存在)8123456781234567909091789131267812234510113111011124561011121357896101312111213迷宮問題(最短路徑)入口出口借助于隊列可求得入口到出口的最短路徑(若存在)8123456781234567909091789131267812234510113111011124561011121357896101312111213迷宮問題(最短路徑)入口出口借助于隊列可求得入口到出口的最短路徑(若存在)812345678123456790909棧與遞歸遞歸是描述或解決一類問題的簡單方法遞歸定義的函數運行時需要控制棧的支持longf(intn){if(n>1)returnn*f(n-1);elsereturn1;}遞歸函數的執(zhí)行STL中的棧#include<iostream>#include<cstdlib>#include<stack>usingnamespacestd;intmain(){stack<int>s;

s.push(1);

s.pop();

s.push(10);s.push(11);

cout<<s.top()<<endl;

cout<<s.size()<<endl;

cout<<s.empty()<<endl;return0;}TheC++Stackisacontaineradapterthatgivestheprogrammerthefunctionalityofastack--specifically,aFILO(first-in,last-out)datastructureStackconstructors:constructanewstackempty:trueifthestackhasnoelementspop:removesthetopelementofastackpush:addsanelementtothetopofthestacksize:retur