2-基本数据结构1

ACM/ICPC程序设计基本数据结构及其在程序设计中的应用张淑平程序=数据结构+算法数据结构(DataStructure)是数据的计算机表示和相应的一组操作。算法(Algorithm)就是解决问题的方法或过程。基本数据结构线性结构非线性结构集合树结构图结构线性表栈队列串线性结构线性表:由n个元素组成的有限序列。每个元素有确定的前驱和后继。

元素之间的关系仅限于前趋、后继关系表、栈、队列、串

元素的存储方式数组链表线性结构由n个元素组成的有限序列。每个元素有确定的前驱和后继。

表：不限制元素的插入和删除位置。有n+1个位置可供插入，n个元素可供删除栈：插入和删除操作只允许在表尾进行队列：在表尾插入、在表头删除串：元素为字符的线性表，有求子串、子串定位、子串替换等操作(a1，a2，…，ai，…，an)表头元素表尾元素数据结构中的存储结构－－元素及元素间关系的存储数组链表数组用一组连续的存储单元依次存储数据元素.表中任一元素可以随机存取.插入或删除一个元素需要移动其他元素.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双向链表和循环链表线性表：(a1，a2，…，ai-1，ai，ai+1，…，an)head…a1∧a2an-1anai…∧(a)双向链表taila2a1anan-1…(b)循环单链表单链表的插入和删除链式存储:任意存储单元存储元素链表结点包括数据域和指针域插入或删除一个元素，只需修改结点指针域访问任一元素必须从链表头指针开始头结点带头结点的单向链表…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比最后一个元素大.在这三个乘积中找最小的添加到表尾,反复按此规则构造递增序列,直到表中有1500个元素。可以用数组预先分配1500个单元,也可以用链表动态分配.例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

处理过程(续)：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

处理过程(续)：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

处理过程(续)：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

处理过程(续)：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

处理过程(续)：01234567890123456789Anycommandinwhicha=borinwhichaandbareinthesamestackofblocksisanillegalcommand.Allillegalcommandsshouldbeignoredandshouldhavenoaffectontheconfigurationofblocks.10move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

处理过程(续)：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

处理过程(续)：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

处理过程(续)：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

处理过程(续)：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)按以上规则，用链表的操作直接模拟即可.数据结构设计设计的数据结构: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示例(续)：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示例(续)：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示例(续)：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个人，让他站在出圈者的位置上。然后从出圈者的后继位置开始数，重复上述过程直到环中只剩1个人。当N=5,k=2时，出环者的顺序为：2，5，3，1；最后留下4。输入：N，k输出：I，使得从第I个人开始数，最后能留下第1人。模拟过程N＝5，k＝2123451出圈序列：22出去接着从1开始数模拟过程(续1)N＝5，k＝214523出圈序列：2344占据2的位置模拟过程(续2)N＝5，k＝21354出圈序列：23接着从1开始数55出去模拟过程(续3)N＝5，k＝2354出圈序列：2，5接着数1144占据5的位置模拟过程(续4)N＝5，k＝213出圈序列：2，54接着数133出去模拟过程(续5)N＝5，k＝2134出圈序列：2，5，3接着数411占据3的位置模拟过程(续6)N＝5，k＝214接着数出圈序列：2，5，3411出去，环内仅剩1人，结束1模拟过程(续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。存储结构用循环链表作为存储结构进行模拟，除了考虑计数问题外，还特别需要注意指针的运算用数组作为存储结构，重点在于计数的处理#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程序实现(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程序实现(uva130)用线性表保存n个人放进环里数到第k个人继续往后数k个人前者出去，后者取代他的位置栈和队列栈：仅在表尾进行插入删除的线性表,后进先出。栈常用于模拟和深度优先搜索。队列：在表尾插入，在表头删除，先进先出。队列常用于模拟和广度优先搜索。表头元素表尾元素(a1，a2，…，ai，…，an)栈的示意栈的修改是按照后进先出的原则进行的，所以栈称为后进先出的线性表（LIFO）an

an-1

a2

a1…

栈底

入栈

出栈栈顶栈运算示例例如，有A、B、C、D、E五个元素依次进入一个栈，若得到的输出序列是CBDAE，那么栈中的运算是如何进行的？空栈栈运算示例(续)设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。A元素A入栈栈运算示例(续)A元素A入栈B元素B入栈设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。break栈运算示例(续)A元素A入栈元素B入栈BC元素C入栈设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。break栈运算示例(续)A元素A入栈元素B入栈元素C入栈CB元素C出栈C设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。break栈运算示例(续)A元素A入栈元素B入栈元素C入栈元素C出栈

C元素B出栈B,B设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。break栈运算示例(续)A元素A入栈元素B入栈元素C入栈元素C出栈元素B出栈C，BD元素D入栈设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。breakC，B栈运算示例(续)A元素A入栈元素B入栈元素C入栈元素C出栈元素B出栈元素D入栈C，B，DD元素D出栈设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。breakC，B，D栈运算示例(续)空栈元素A入栈元素B入栈元素C入栈元素C出栈元素B出栈元素D入栈元素D出栈C，B，D，A元素A出栈A设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。break栈运算示例(续)元素A入栈元素B入栈元素C入栈元素C出栈元素B出栈元素D入栈元素D出栈元素A出栈C，B，D，AE元素E入栈设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。breakC，B，D，A栈运算示例(续)空栈元素A入栈元素B入栈元素C入栈元素C出栈元素B出栈元素D入栈元素D出栈元素A出栈元素E入栈C，B，D，A，E元素E出栈E设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。break栈运算示例(续)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节车厢，顺序编号为1,2,3,...,n，从A驶入，从B驶出，车站里能停放任意多节车厢。一旦进入车站就不再回到A方向的铁轨上，一旦进入B方向铁轨，不再回车站。判断一个指定车厢顺序能否从B方向驶出。例5:AnagramsbyStack(zoj1004)问题：有一个字母序列，对它每个元素进行入栈、出栈操作。判断是否能得到指定输出序列，如果可以，则输出相应的栈操作。input：madamadammoutput：[iiiioooiooiiiiooooioiioioioiooiioioiooio]8123456781234567入口出口例6：迷宫问题寻找一条从入口到出口的通路东南迷宫问题(续)北(上)西(左)前进方向：上(北)、下(南)、左(西)、右(东)首先从下方开始，按照逆时针方向搜索下一步可能前进的位置迷宫问题(续)入口出口在迷宫周围加墙，避免判断是否出界812345678123456790908123456781234567迷宫问题(续)9090在寻找出口的过程中，每前进一步，当前位置入栈；每回退一步，栈顶元素出栈栈(1,1)i8123456781234567迷宫问题(续)9090栈(1,1)(2,1)向下方前进一步i迷宫问题(续)81234567812345679090栈(1,1)(2,1)i(3,1)向下方前进一步ii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(4,1)(3,1)i向下方前进一步breakiiii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(5,1)(3,1)(4,1)向下方前进一步breakiiiii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(6,1)(3,1)(4,1)(5,1)向下方前进一步breakiiiiii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)向下方前进一步breakiiiiii@迷宫问题(续)81234567812345679090向下方、右方、左方均不能前进，上方是来路，则后退栈(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)breakiiiii@@迷宫问题(续)81234567812345679090栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)向右方、左方均不能前进，下方路不通，上方是来路，则后退breakiiiii@@81234567迷宫问题(续)0981234567812345679090栈(1,1)(2,1)(3,1)(4,1)(5,1)(5,2)向右方前进一步breakiiiiii@@迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(5,3)(5,2)breakiiiiiii@@81234567迷宫问题(续)0981234567812345679090向下方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(5,2)(5,3)breakiiiiiii@@迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,4)(5,2)(5,3)(6,3)ibreakiiiiiii@ii@迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,5)(5,2)(5,3)(6,3)(6,4)breakiiiiiii@iii@81234567迷宫问题(续)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迷宫问题(续)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迷宫问题(续)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迷宫问题(续)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迷宫问题(续)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迷宫问题(续)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;}递归函数的执行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