数据结构总结

数据结构应用山东师大附中赵宗昌数据结构总结全文共96页，当前为第1页。◆高精度运算◆排序的应用◆栈的应用◆队列的应用◆图的应用数据结构总结全文共96页，当前为第2页。一、高精度运算主要解决的问题：1、高精度数的输入和保存。2、运算时的进位与借位。3、运算结果的保存。4、运算结果的输出。数据结构总结全文共96页，当前为第3页。1、实数减法dec.pas/dec.in/dec.out【问题描述：】输入两个正的实数a,b，输出a-b的值。【输入：】两行，第一行a，第二行b，a和b的长度均小于1000位。【输出：】一行，a-b的值。【样例输入：】4.52.3【样例输出：】2.2数据结构总结全文共96页，当前为第4页。1、数据的输入2、比较实数a和b的大小。从而确定结果的正负号

ifa>bthen+ifa<bthen-ifa=bthen03、借位问题。4、结果的输出实数减法数据结构总结全文共96页，当前为第5页。◆数据的输入：

a和b的长度均小于1000位1、string:最大长度255位。2、单个数字字符读入；3、ansistring：最大长度:256*256-1=65535数据结构总结全文共96页，当前为第6页。正整数大小的比较：◆

实数数据大小的比较：S1;s2(s1<>s2)la:=length(s1);lb:=length(s2);if(la<lb)or((la=lb)and(s1<s2))thens1<s2Elses1>s2数据结构总结全文共96页，当前为第7页。实数大小的比较：

a=‘1234.343’b=‘4.5545545’

补齐：容易比较大小

a=‘1234.3430000’b=‘0004.5545545’

记录小数点的位置p．去掉小数点．

a=‘12343430000’b=‘’根据整数大小的比较。运算按照整数减法。数据结构总结全文共96页，当前为第8页。◆

结果的输出小数点的处理.345453454000003444.4355454000000000.000000.000000输出合法要求：不能有多余的0数据结构总结全文共96页，当前为第9页。

k1:最后一位小数位置；

p：小数点位置。

k2:整数最高位。

k1:=1;while(a[k1]=0)and(k1<=p)doinc(k1);k2:=len;while(a[k2]=0)and(k2>p+1)dodec(k2);fori:=k2downtop+1dowrite(a[i]);ifk1<=pthenbeginwrite('.');fori:=p-1downtok1dowrite(a[i]);end;……342444.84584938……..k2k1p数据结构总结全文共96页，当前为第10页。1、选择排序2、冒泡排序3、插入排序4、快速排序5、堆排序二、排序的应用时间：O(n2)N<1000时间：O(n*log(n))N<10000数据结构总结全文共96页，当前为第11页。1、区间合并【问题描述：】从键盘上任意输入n个区间，然后按从小到大的顺序依次输出n个区间的并集。【输入：】第一行，区间个数n（<=1000）以下n行，每行两个整数a、b（-1000000000<a<b<1000000000）,相应区间的坐标，中间一个空格。【输出：】n个区间的并集，n行，每行一个区间，坐标轴的左边的区间先输出。【样例输入：】3251478【样例输出：】1578数据结构总结全文共96页，当前为第12页。区间的合并注意：1、区间个数n的范围（<=1000）2、区间的数据类型和范围：整数类型、-109--109数据结构总结全文共96页，当前为第13页。算法一：离散化思路：◆设f[i]:0..1,初始值全部为0。◆每读入一个区间abFori:=1tonForj:=atobdof[j]=1◆最后输出f[j]=1的区间。时间复杂度：1012，只能过部分数据。数据结构总结全文共96页，当前为第14页。算法二：直接合并1、按每个区间的左端的的值升序排列。由于N<=1000,任意排序算法。注意数据结构的设置:

◆记录类型

◆二维数组：

a:array[1..1000,1..2]oflongint;a:array[1..1000]ofarray[1..2]oflongint数据结构总结全文共96页，当前为第15页。2、合并过程◆输出第一个区间的左端点坐标（最小的）◆依次处理后面的n-1的区间。Ifa[I,2]<=tailTail不变If(a[I,1]<=tail)and(tail<=a[I,2])Tail=a[I,2]Iftail<a[I,1]Writeln(tail);Write(a[I,1]);Tail:=a[I,2];数据结构总结全文共96页，当前为第16页。write(a[1,1],'');tail:=a[1,2];fori:=2tondobeginif(a[i,1]<=tail)and(tail<=a[i,2])//2thentail:=a[i,2];iftail<a[i,1]then//3beginwriteln(tail);write(a[i,1],'');tail:=a[i,2];end;end;writeln(tail);数据结构总结全文共96页，当前为第17页。2、潜水比赛

在马其顿王国举行了一次潜水比赛。其中一个项目是从高山上跳下水，再潜水达到终点。这是一个团体项目，一支队伍由n人组成。在潜水时必须使用氧气瓶，但是每只队伍只有一个氧气瓶。最多两人同时使用一个氧气瓶，但此时两人必须同步游泳，因此两人达到终点的时间等于较慢的一个人单独游到终点所需要的时间。好在大家都很友好，因此任何两个人后都愿意一起游水。安排一种潜水的策略，使得最后一名选手尽量的达到终点。输入：第一行：队伍的人数n（<=1000）。第二行：n个数，分别是n个人潜水所用的时间ti(<=1000)。样例：输入：3134输出：8数据结构总结全文共96页，当前为第18页。分析:先从简单入手:1)n=2,时间t:110所需的时间为:102)n=3,时间t:134所需的时间为:3+1+4=83)n=4,时间t:1101112所需的时间为:10+1+11+1+12=35贪心策略方法一:N个人:每个人所需的时间:t1，t2，……tn。假设t1最小。每次由t1接送人和氧气瓶，则总时间：s=t2+t3+。。。。tn+（n-2）*t1数据结构总结全文共96页，当前为第19页。4）n=4，每个人所用时间：1258采用贪心策略方法一：计算所用的总时间为：2+5+8+1*2=17事实上：采用下面策略：第一步：12一起先过，用时：2第二步：1送回氧气瓶，用时：1第三步：58一起过，用时：8第四步：2送回氧气瓶，用时：2第五步：1和2一起过去，用时：2完成。共用时：2+1+8+2+2=15<17数据结构总结全文共96页，当前为第20页。贪心策略方法二:将n个人的时间从小到达排序，假设从小到大为：t1，t2，……tn1：t1和t2过：t22：t1带瓶返回：t13：最大的两个人：tntn-1过：tn4：t2带瓶返回：t2把以上看作一趟：把用事最长的两个人tn，tn-1送过去：用时：2*t2+t1+tn重复上述过程：用t1和t2在把tn-2

，tn-3

送过去，用时：2*t2+t1+tn-2每趟都用t1和t2，每趟运送2人。最后如果剩2人：t1，t2：时间：t2最后如果剩3人：t1，t2，t3时间：t1+t2+t3数据结构总结全文共96页，当前为第21页。5）n=6，时间：1101112100101按照贪心策略方法二:计算总时间：165另外的方法：10101110010110110101121211111111111010157！数据结构总结全文共96页，当前为第22页。贪心策略方法三：每一趟送用时间最长的两个人时：根据情况选择：用t1和t2两个人还是只用t1一个人。用t1和t2送一趟用时：x=2*t2+t1+tn用t1一个人送一趟（2人）：y=2*t1+tn+tn-1每送一趟都要比较x和y的大小：Ifx>ythen用t1送else用t1和t2送数据结构总结全文共96页，当前为第23页。贪心三算法：数组a存时间：把时间从小到大排序。sum:=0;ifodd(n)thenbeginsum:=sum+a[2]+a[1]+a[3]endelsesum:=sum+a[2];i:=n;whilei>3dobeginx:=2*a[2]+a[1]+a[i];{用a1和a2送一趟}y:=2*a[1]+a[i]+a[i-1];{用a1送一趟}ifx<ythensum:=sum+xelsesum:=sum+y;dec(i,2);{i=i-2:每趟送两人}end;writeln(sum);数据结构总结全文共96页，当前为第24页。三、栈的应用典型应用：表达式类问题的求解中缀表达式转化为后缀表达式中缀表达式求值数据结构总结全文共96页，当前为第25页。【问题描述：】判断包含有括号{，[，<，（，），>，]，}的字符串是否是合法匹配。例如以下是合法的括号匹配：(),[],(()),([]),()[],()[()]以下是不合法括号匹配的：(,[,],)(,([)],([()【输入：】一行，字符串（长度范围：[1，500]）。【输出：】如果字符串中括号匹配是合法的输出“yes”，不合法的输出“no”。【样例1输入：】abc{a[bb]m}aa<ss>【样例1输出：】yes【样例2输入：】abc{a[bb]maa<ss>【样例2输出：】no1、括号匹配数据结构总结全文共96页，当前为第26页。s:ansistring;ch:array[1..8]ofchar=('{','[','<','(',')','>',']','}');利用栈操作主程序：

beginreadlnI(s);ifcheckthenwriteln('yes')elsewriteln('no');end;数据结构总结全文共96页，当前为第27页。functioncheck:boolean;//检测函数：合法返回true；非法返回false；

beginlen:=length(s);t:=0;//栈顶指针；

i:=1;whilei<=lendobegink1:=find(s[i]);//返回序号

if(k1>0)and(k1<=4)thenpush(k1);//左括号进栈

ifk1>4then//右括号，出栈判断是否配对。

beginift=0thenexit(false);//空栈：非法的，预防栈溢出；

k2:=pop;ifk1+k2<>9thenexit(false);//不匹配退出检测

end;inc(i);end;ift=0thenexit(true)elseexit(false);//栈空：合法；非空：非法；

end;数据结构总结全文共96页，当前为第28页。functionfind(x:char):integer;//返回括号的序号函数,用序号代替括号;0：不是括号

vari:integer;beginfori:=1to8doifx=ch[i]thenexit(i);exit(0);end;Find(x:char)函数数据结构总结全文共96页，当前为第29页。2、中缀表达式求值【问题描述：】输入表达式，输出值。1）、表达式中除了数字外0----9外，仅含有运算符合：+、-、*、/、（、）六种符号。2）、输入的数全部为正整数，不含有如下类似的表达式：+3，-45等。3）、表达式长度不超过100，中间运算值以及最后的运算结果都在[-109，109]内。4）、/运算只取整数部分。采用div即可。【输入：】合法的中缀表达式。【输出：】表达式的值【样例输入：】3*（7-2）【样例输出：】15数据结构总结全文共96页，当前为第30页。表达式类问题的两种求解算法：◆算符优先算法：栈操作。

符号栈，操作数栈

1、先化中缀，再求值。

2、直接求值。考虑情况复杂，代码复杂，乱。◆递归处理算法数据结构总结全文共96页，当前为第31页。分析:

采用递归算法:

设表达式：s=s1ops2;op是最低优先运算符。

1）、找s中的最低优先级运算符:op2）、先计算s1和s2；

3）、然后s1和s2再作op运算。

s1和s2采取同样的方法。如：34*10+30+10*5数据结构总结全文共96页，当前为第32页。主程序：BEGINreadln（S）；

n:=length(S);ans=work(1,n)writeln(ans);END;数据结构总结全文共96页，当前为第33页。functionwork(L,r:longint):longint;//求表达式SL……Sr的值

vark,a,b:longint;beginifst[l]='('theninc(l);ifst[r]=')'thendec(r);k:=find1(l,r);//最低优先级算符的位置

ifk=0thenexit(data(l,r));//返回数值

a:=work(l,k-1);//左边求值

b:=work(k+1,r);//右边求值

work:=opt(a,k,b);//按k位置的算符计算

end;递归算法数据结构总结全文共96页，当前为第34页。标号法求运算符的优先级：

◆+-的标号为1，*/的标号为2。

◆遇到括号标号加2。标号大的运算优先级高。34+2*(23+3)-(2+(3+5)*3))+10+5数据结构总结全文共96页，当前为第35页。

预处理：求出表示式中S运算符号的优先级

fori:=1tondoh[i]:=maxint;//运算数优先级最大

base:=0;fori:=1tondocasest[i]of'(‘:inc(base,2);')‘:dec(base,2);'+‘,'-‘:h[i]:=base+1;'*‘,'/‘:h[i]:=base+2;end;数据结构总结全文共96页，当前为第36页。functionfind(l,r:longint):longint;vari,min:longint;beginmin:=maxint;find:=0;fori:=rdowntoldo//从右向左找？

ifh[i]<minthenbeginmin:=h[i];find:=i;end;end;find1(l,r);//最低优先级算符的位置数据结构总结全文共96页，当前为第37页。functiondata(l,r:longint):longint;vari:longint;begindata:=0;fori:=ltordodata:=data*10+ord(st[i])-48;end;data(l,r)：返回数值数据结构总结全文共96页，当前为第38页。functionopt(a,k,b:longint):longint;begincasest[k]of'+':opt:=a+b;'-':opt:=a-b;'*':opt:=a*b;'/':opt:=adivb;end;end;opt(a,k,b);按k位置的算符计算数据结构总结全文共96页，当前为第39页。3、中缀表达式转换为后缀表达式【问题描述：】输入中缀表达式，输出后缀表达式的形式，运算符号：+、-、*、/。每个操作数后面用“.”作为该操作数的结束标志。表达式除中的括号只有“（”和“）”。【输入：】合法的中缀表达式（长度不超过100）【输出：】后缀表达式。【样例输入：】3*(5–2)+7【样例输出：】3．5．2．-*7．+数据结构总结全文共96页，当前为第40页。分析：假设表达式：s=s1ops2，op为最低优先级运送符。1、首先把整个表达式中优先级最低的符号op放在最后边。变成：s1s2op2、再依次处理s1和s2：

s1=s11op1s12s2=s21op2s22

变成：s11s12op1s21s22op2

op3、再处理s11s12s21s2递归思想数据结构总结全文共96页，当前为第41页。//Main;beginreadln(s);Ans:=work(1,len);writeln(Ans);end;数据结构总结全文共96页，当前为第42页。functionwork(l,r:integer):string;//把表达式SL……Sr转化为后缀表达式。

varpos,i:integer;beginif(s[l]='(')theninc(l);if(s[r]=')')thendec(r);pos:=findlow(l,r);if(pos=0)thenexit(copy(s,l,r-l+1)+'.');work:=work(l,pos-1)+work(pos+1,r)+s[pos];end;数据结构总结全文共96页，当前为第43页。四、队列的应用典型应用：广度优先搜索数据结构总结全文共96页，当前为第44页。概念

在一端进行插入（进队列），在另一端进行删除（出队列）的线性表。插入的一端称为队尾：closed;（指向队尾，最后一个元素）删除的一端称为队首：open(习惯指向队首的前一位置，空的位置)3265419openclosed队列数组a下标：1234567……队列空：open>=closed;非空：open<closed数据结构总结全文共96页，当前为第45页。1、合并石子【问题描述：】

小Ray在河边玩耍，无意中发现一些很漂亮的石子堆，于是他决定把这些石子搬回家。河滩上共有n堆石子，小Ray在把石子搬回家之前首先要把这n堆石子合并为一堆石子。已知小Ray每次可以选择其中的两堆石子合并为一堆，合并一次石子他要消耗的体力是两堆石子的数量和。请计算小Ray把n堆石子合并成一堆最少消耗的体力值是多少。【输入：】第一行：n（<=30000）.第二行：那个用空格隔开的数，分别表示n堆石子的数量。（每堆<10000）【输出：】n堆石子合并成一堆所消耗的最小体力值。说明:分别用队列和堆两种算法实现。【样例输入：】3124【样例输出：】10数据结构总结全文共96页，当前为第46页。

在最优二叉树中非叶结点的度均为2，因此采用顺序存储结构为宜。如果带权叶结点数为n个，则最优二叉树的结点数为2n-1个。由此得出最优二叉树的数据类型定义Maxn=30000;n=叶结点数的上限；

m=2*n-1；{最优二叉树的结点数}Typenode=record{结点类型}data：integer；{权值}prt，lch，rch：longint；{父指针、左、右指针和路径长度}end；Vara：array[1..maxn]oflongint；{其中a[1‥n]为叶结点，a[n+1‥2n-1]为中间结点，根为a[2n-1]}算法一(hafuman.pas)数据结构总结全文共96页，当前为第47页。procedurecreat;//创建哈夫曼树

vari,j,k:longint;beginsum:=0;//费用

m:=2*n-1;fork:=n+1tomdobegini:=findmin(k-1);a[k].lch:=i;a[i].prt:=k;j:=findmin(k-1);a[k].rch:=j;a[j].prt:=k;a[k].data:=a[i].data+a[j].data;sum:=sum+a[k].data;end;end;数据结构总结全文共96页，当前为第48页。functionfindmin(k:longint):longint;//在前k个街道中找最小的结点，父结点为0varmin,i:longint;beginmin:=maxlongint;fori:=1tokdoif(a[i].data<min)and(a[i].prt=0)thenbeginmin:=a[i].data;findmin:=i;end;end;Sum是所求的费用时间复杂度：O(n2)，无法完成n=30000数据结构总结全文共96页，当前为第49页。算法二（stone.pas）设置两个队列：a，b队列a：保存初始的n个叶结点，从小到大排序。队列b:依次放生成的新结点，递增的。生成结点过程：Mindata=min{a[opena]+a[opena+1];b[openb]+b[openb+1];a[open]+b[open]}Inc(closedb);B[closedb]=mindata;采用快速排序；时间复杂度：O（n*long(n)）合并的时间复杂度：O（n）总的时间复杂度：O（n*long(n)）数据结构总结全文共96页，当前为第50页。opena:=1;openb:=1;closedb:=0;ans:=0;fori:=1ton-1dobeginsum:=a[opena]+a[opena+1];f:=1;ifa[opena]+b[openb]<sumthenbeginsum:=a[opena]+b[openb];f:=2;end;ifb[openb]+b[openb+1]<sumthenbeginsum:=b[openb]+b[openb+1];f:=3;end;inc(closedb);b[closedb]:=sum;inc(ans,sum);casefof1:inc(opena,2);2:begininc(opena);inc(openb);end;3:inc(openb,2);end;end;将石子从小到大排序放入数组a；数组b，一次存放合并后的石子，同样是递增的的？数据结构总结全文共96页，当前为第51页。将石子从小到大排序放入数组a；N=300001、快速排序算法。2、桶排序算法。readln(n);fori:=1tondobeginread(k);inc(t[k]);end;k:=0;fori:=1to10000doforj:=1tot[i]dobegininc(k);a[k]:=i;end;

a[n+1]:=maxlongintdiv2;a[n+2]:=maxlongintdiv2;fori:=1ton+2dot[i]:=maxlongintdiv2;数据结构总结全文共96页，当前为第52页。【问题描述：】在n*n的棋盘上有一匹马在第x行第y列的格子上。棋盘上有些格子上有障碍物，马不能达到有障碍物的格子。已知马在棋盘中的走法按“日“字8个方向可走，如下图所示：问：哪些格子能到达，到达这些格子的最小步数是多少。【输入：】第一行:n（n<=100）,x,y

(马的开始位置)。接下来n行为棋盘的描述：“-“为空格子，”+“表示该格子有障碍物。【输出：】n行，每行n个用空格隔开的数，表示马到达该格子的最少步数，如果无法到达则用-1表示。2、马的遍历数据结构总结全文共96页，当前为第53页。422----------+-----【样例输入：】4321303223-111214【样例输出：】０数据结构总结全文共96页，当前为第54页。dx:array[1..8]ofinteger=(-1,-2,-2,-1,1,2,2,1);dy:array[1..8]ofinteger=(2,1,-1,-2,-2,-1,1,2);varcan:array[-1..maxn+2,-1..maxn+2]ofboolean;//加边界，方便判断是否出界

dist:array[1..maxn,1..maxn]ofinteger;//记录最少步数

n,i,j,x0,y0:integer;procedureinit;vars:string;beginreadln(n,x0,y0);fillchar(can,sizeof(can),false);fori:=1tondobeginreadln(s);forj:=1tondocan[i,j]:=s[j]='-';end;end;数据结构总结全文共96页，当前为第55页。procedurebfs;//广度优先搜索

varq:array[1..maxn*maxn,1..2]ofinteger;open,closed,k,x,y,xx,yy:integer;beginfori:=1tondoforj:=1tondodist[i,j]:=-1;open:=0;closed:=1;dist[x0,y0]:=0;q[1,1]:=x0;q[1,2]:=y0;whileopen<closeddobegininc(open);x:=q[open,1];y:=q[open,2];fork:=1to8dobeginxx:=x+dx[k];yy:=y+dy[k];ifcan[xx,yy]and(dist[xx,yy]=-1)thenbegindist[xx,yy]:=dist[x,y]+1;inc(closed);q[closed,1]:=xx;q[closed,2]:=yy;end;end;end;end;数据结构总结全文共96页，当前为第56页。广度优先搜索算法（bfs）:1、适合的题目类型：

1）、求从给定初始状态到目标状态最少需要的步数。

2）、给定初始状态，经过k步后能够到达哪些状态。2、利用的数据结构：队列。3、状态的最大值：决定队列的大小（非常重要）4、队列里需要记住哪些状态：一般使用记录数据类型。5、状态的转移：不能遗漏。6、状态的判重：避免重复进入队列。（结合跳马题目分析）数据结构总结全文共96页，当前为第57页。4、Bfs的基本框架：初始化；建立数据库（队列）；初始状态进入队列；Open=0：队列的首指针；Closed=1：队列的尾指针（开始时指向初始状态）；Quene[1]:初始结点;While（open<closed{还有未扩展的结点，队列不空}）doBeginInc（open）；{移动队列的首指针：出队列}

记录open状态；

Fori=1tomethoddo{按规则扩展下一层新的子结点}Begin

生成新的结点;If新结点是目标结点then输出目标，搜索结束；

If新结点是以前没出现过then保存新结点（入队列）；

EndEnd；数据结构总结全文共96页，当前为第58页。3、中国盒子问题给定10个盒子排成一行，其中有两个相邻的盒子是空的，其余的盒子中有4个A和4个B，例如：移动规则：任意两相邻字母可移到空盒子中去，但这两个字母的原来顺序保持改变。目标：全部的A在左边，全部的B在右边，空格在中间。如下图：对于任意给定的一个排列顺序，最少经过多少次移动，能达到目标序列。输入：一行：初始序列，空格用0代替。输出：初始序列达到目标的最少移动次数。样例：输入：ABBA00ABAB输出：5AAAABBBBABBAABAB数据结构总结全文共96页，当前为第59页。中国盒子问题（box）1、问题：初始序列达到目标的最少移动次数。适合使用bfs算法。2、队列需要保存的状态：转化后的字符串s;转换需要的步数depth。适合用记录数据类型：

typenode=recordstr:string[10];depth:integer;end;3、状态的多少（队列的大小）：630数据结构总结全文共96页，当前为第60页。4、状态的转移：任意两相邻字母可移到空盒子中去，但这两个字母的原来顺序保持改变ABBAABAB1）、确定空格的位置：sp:=pos('0',s);spS=i（1---9）2）、i，i+1与sp，sp+1位置的字符交换：条件：(sp–i>=2)or(i–sp>=2)3）、交换：Tem=stem[sp]:=s[i];tem[sp+1]:=s[i+1];tem[i]:='0';tem[i+1]:='0';？数据结构总结全文共96页，当前为第61页。5、判重：

fori=1tocloseddoifa[1].str=tem最简单、最直接的判重方法。缺点：效率低，时间慢。st='AAAA00BBBB';数据结构总结全文共96页，当前为第62页。open:=0;closed:=1;q[1].str:=s1;q[1].depth:=0;whileopen<closeddobegininc(open);s:=q[open].str;step:=q[open].depth+1;sp:=pos('0',s);fori:=1to9dobegintem:=s;if(i+2<=sp)or(i-2>=sp)thenbegintem[sp]:=s[i];tem[sp+1]:=s[i+1];tem[i]:='0';tem[i+1]:='0';iftem=stthenprint(step);ifnotfind(tem)thenbegininc(closed);q[closed].str:=tem;q[closed].depth:=step;end;end;end;end;数据结构总结全文共96页，当前为第63页。functionfind(tem:string):boolean;varj:integer;beginforj:=1tocloseddoiftem=q[j].strthenexit(true);exit(false);end;数据结构总结全文共96页，当前为第64页。4、翻硬币问题描述有N个硬币正面朝上排成一排（N>=6），每次将5个硬币翻过来放在原位置，直到最后全部硬币翻成反面朝上为止。编程找出最少步数输入只有一个整数N（<1000）输出翻币的最少次数coin.in8Coin.out4数据结构总结全文共96页，当前为第65页。关键：反的最少次数仅仅与正面朝上和反面朝上的硬币各数有关，而与硬币的顺序无关。1、需要记录的状态有哪些？2、怎样判重复状态？3、状态转移及条件？4、队列的大小？数据结构总结全文共96页，当前为第66页。typenode=recordnum:integer;{正面朝上个数}depth:integer;{翻的次数}end;vara:array[1..1000]ofnode;n,open,closed,step:integer;b:array[0..1000]ofboolean;{(b[i]：i个正面朝上的情况是否出现过)}数据结构总结全文共96页，当前为第67页。procedurebfs;vari,m:integer;beginopen:=0;closed:=1;a[1].num:=n;a[1].depth:=0;b[n]:=true;whileopen<closeddobegininc(open);m:=a[open].num;{(m表示当前正面朝上的硬币个数)}step:=a[open].depth+1;

fori:=1to5do{(翻i个正面朝上的硬币)}if(m>=i)and(n-m>=5-i)then{(m-i+5-i:正面朝上的个数)}beginifm-i+5-i=0thenprint(step);{正面朝上的个数为0时结束}ifnot(b[m-i+5-i])thenbegininc(closed);{进队列}b[m-i+5-i]:=true;a[closed].num:=m-i+5-i;{正面朝上的个数}a[closed].depth:=step;{翻的次数}end;end;end;end;数据结构总结全文共96页，当前为第68页。数据结构总结全文共96页，当前为第69页。可以看出：除了6和8是特例外，其他满足：1）if(nmod5=0)thens=ndiv52)if(nmod5=1)or(nmod5=3)thens=ndiv5+13)if(nmod5=2)or(nmod5=4)thens=ndiv5+2或者：Ifnmod5=0thens=ndiv5Elses=ndiv5+(nmod5-1)mod2+1数据结构总结全文共96页，当前为第70页。1、图的存储结构：邻接矩阵、邻接表2、图的遍历：dfs、bfs、连通分量3、无向图的传递闭包4、最短路径算法：floyed,dijkstra5、最小生成树算法：prim,kruskal五、图数据结构总结全文共96页，当前为第71页。1253412534678图一图二定义：连通：如果从顶点u到v有路径，则称u和v是连通的。连通图：图中任意的两个顶点u和v都是连通的。图一是连通图，图二是非连通图连通分量：无向图中的极大连通子图。图二中有3个连通分量：{1245}{36}{78}求连通分量数，最大连通分量等。有向图：强连通、强连通图、强连通分量◆图的连通分量数据结构总结全文共96页，当前为第72页。//连通分量的算法

sum:=0;fori:=1tondoifnotf[i]thenbegin

inc(sum);dfs(i);end;数据结构总结全文共96页，当前为第73页。【犯罪团伙】

警察抓到了n个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从1至n。输入：第一行：n（<=10000,罪犯数量），第二行：m（<=100000，关系数量）以下若干行：每行两个数：I和j，中间一个空格隔开，表示罪犯i和罪犯j相互认识。输出：一个整数，犯罪团伙的数量。输入：118124534135671051089输出：3测试数据说明：1s共10个测试数据：（1）5个数据：

n<=1000,m<=5000;（2）5个数据：

10000>=n>=9000,

100000>=m>=90000;数据结构总结全文共96页，当前为第74页。建立无向图的模型。最容易想到的算法1：把n个人看成图的n个顶点；相互认识的连一条边。相互认识的所有人构成一个极大连通子图。问题转化为：求无向图的连通分量（有多少个极大连通子图）数据结构总结全文共96页，当前为第75页。//建图

readln(n);readln(m);fori:=1tomdobeginreadln(x,y);a[x,y]:=1;a[y,x]:=1;end;//dfsproceduredfs(i:longint);varj:longint;beginvisited[i]:=1;forj:=1tondoif(a[i,j]=1)and(visited[j]=0)thendfs(j);end;数据结构总结全文共96页，当前为第76页。proceduremain;vari:integer;begin

sum:=0;fillchar(f,sizeof(f),false);fori:=1tondoifnotf[i]thenbegin

inc(sum);dfs(i);end;writeln(sum);end;数据结构总结全文共96页，当前为第77页。☻时间和空间！邻接矩阵：空间太大，超时。邻接表：空间满足，时间>1s

无法通过后5个数据数据结构总结全文共96页，当前为第78页。输入：118124534135671051089高效的树型结构算法2：建立森森结构，统计树的数量数据结构总结全文共96页，当前为第79页。constmax=10000;vara:array[1..max]oflongint;i,j,m,n,ans,x,y,p,q:longint;functionfind(i:longint):longint;{非递归算法找i的根}varj,k,t:longint;beginj:=i;whilea[j]<>0doj:=a[j];find:=j;end;程序算法：数据结构总结全文共96页，当前为第80页。readln(n);readln(m);fillchar(a,sizeof(a),0);{默认根标志是0，开始全是树根}fori:=1tomdobeginreadln(x,y);p:=find(x);{查找x的根}q:=find(y);{查找y的根}ifp<>qthena[q]:=p;{合并p和q子树}end;ans:=0;{树根记数}fori:=1tondoifa[i]=0theninc(ans);{记录树根结点}writeln(ans);end.数据结构总结全文共96页，当前为第81页。◆无向图的传递闭包判断无向图的连通性1234657输入图的边的信息，输出各点的连通行。输入：7122313345667输出：11110001111000111100011110000000111000011100001110110000101000011010000010000000001000001010000010邻接矩阵数据结构总结全文共96页，当前为第82页。判断结点i和j的连通性：ijk1、结点i和j如果原来有边则连通。2、如果i和j之间没有边：如果存在另外的一个结点k，满足：i与k连通，k与j连通，则i与j连通。否则i和j不连通。Can[i,j]:true，i与j之间有边；false：无边。则：Can[i,j]=can[i,j]or(can[i,k]andcan[k,j])数据结构总结全文共96页，当前为第83页。fork:=1tondofori:=1tondoforj:=1tondocan[i,j]:=can[i,j]or(can[i,k]andcan[k,j]);过程：数据结构总结全文共96页，当前为第84页。产生数【问题描述:】给出一个正整数n（n<10^50)和k个变换规则（k<=15）。每个变换规则是指：一位数可变换成另一个一位数：规则的右部不能为零。例如：n=234。有规则（k＝2）：

2－>53－>6上面的整数234经过变换后可能产生出的整数为（包括原数）:

234534264564共4种不同的产生数。【任务：】给出一个整数n和k个变换规则。求经过任意次的变换（0次或多次），能产生出多少个不同整数。仅要求输出个数。【输入：】第一行：n。第二行：k。以下k行：每行两个一位数：xy，中间一个空格，表示一个变换规则：x可以变为y。【输出：】一个整数（满足条件的个数）：【输入样例：】23422536【样例输出：】4应用举例数据结构总结全文共96页，当前为第85页。►本题搜索显然是不行的。►对于只需计数而不需求具体方案的题目，一般都不会用搜索解决。分析：►乘法原理直接进行计数。用F[i]表示数字i包括本身可以变成的数字总个数这里的变成可以是直接变成也可以是间接变成：比如3->5,5->7,那么3->7那么对于一个数a（用数组存,长度为n），根据乘法原理它能产生出不同整数数量：F[a[1]]*F[a[2]]*F[a[3]]*…F[a[n]]数据结构总结全文共96页，当前为第86页。init；

//建图

makef;//生成每个数字的转化数量

n:=length(s);fillchar(ans,sizeof(ans),0);//结果

ans[1]:=1;ans[0]:=1;fori:=1tondobegink:=f[ord(s[i])-48];ifk<>0thenmul(k);end;pr