數(shù)據(jù)結(jié)構(gòu)應(yīng)用山東師大附中趙宗昌數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第1頁(yè)?！舾呔冗\(yùn)算◆排序的應(yīng)用◆棧的應(yīng)用◆隊(duì)列的應(yīng)用◆圖的應(yīng)用數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第2頁(yè)。一、高精度運(yùn)算主要解決的問(wèn)題：1、高精度數(shù)的輸入和保存。2、運(yùn)算時(shí)的進(jìn)位與借位。3、運(yùn)算結(jié)果的保存。4、運(yùn)算結(jié)果的輸出。數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第3頁(yè)。1、實(shí)數(shù)減法dec.pas/dec.in/dec.out【問(wèn)題描述：】輸入兩個(gè)正的實(shí)數(shù)a,b，輸出a-b的值?！据斎耄骸?jī)尚校谝恍衋，第二行b，a和b的長(zhǎng)度均小于1000位?！据敵觯骸恳恍校琣-b的值?！緲永斎耄骸?.52.3【樣例輸出：】2.2數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第4頁(yè)。1、數(shù)據(jù)的輸入2、比較實(shí)數(shù)a和b的大小。從而確定結(jié)果的正負(fù)號(hào)

ifa>bthen+ifa<bthen-ifa=bthen03、借位問(wèn)題。4、結(jié)果的輸出實(shí)數(shù)減法數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第5頁(yè)。◆數(shù)據(jù)的輸入：

a和b的長(zhǎng)度均小于1000位1、string:最大長(zhǎng)度255位。2、單個(gè)數(shù)字字符讀入；3、ansistring：最大長(zhǎng)度:256*256-1=65535數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第6頁(yè)。正整數(shù)大小的比較：◆

實(shí)數(shù)數(shù)據(jù)大小的比較：S1;s2(s1<>s2)la:=length(s1);lb:=length(s2);if(la<lb)or((la=lb)and(s1<s2))thens1<s2Elses1>s2數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第7頁(yè)。實(shí)數(shù)大小的比較：

a=‘1234.343’b=‘4.5545545’

補(bǔ)齊：容易比較大小

a=‘1234.3430000’b=‘0004.5545545’

記錄小數(shù)點(diǎn)的位置p．去掉小數(shù)點(diǎn)．

a=‘12343430000’b=‘’根據(jù)整數(shù)大小的比較。運(yùn)算按照整數(shù)減法。數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第8頁(yè)?！?/p>

結(jié)果的輸出小數(shù)點(diǎn)的處理.345453454000003444.4355454000000000.000000.000000輸出合法要求：不能有多余的0數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第9頁(yè)。

k1:最后一位小數(shù)位置；

p：小數(shù)點(diǎn)位置。

k2:整數(shù)最高位。

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數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第10頁(yè)。1、選擇排序2、冒泡排序3、插入排序4、快速排序5、堆排序二、排序的應(yīng)用時(shí)間：O(n2)N<1000時(shí)間：O(n*log(n))N<10000數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第11頁(yè)。1、區(qū)間合并【問(wèn)題描述：】從鍵盤(pán)上任意輸入n個(gè)區(qū)間，然后按從小到大的順序依次輸出n個(gè)區(qū)間的并集?！据斎耄骸康谝恍?，區(qū)間個(gè)數(shù)n（<=1000）以下n行，每行兩個(gè)整數(shù)a、b（-1000000000<a<b<1000000000）,相應(yīng)區(qū)間的坐標(biāo)，中間一個(gè)空格?！据敵觯骸縩個(gè)區(qū)間的并集，n行，每行一個(gè)區(qū)間，坐標(biāo)軸的左邊的區(qū)間先輸出?！緲永斎耄骸?251478【樣例輸出：】1578數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第12頁(yè)。區(qū)間的合并注意：1、區(qū)間個(gè)數(shù)n的范圍（<=1000）2、區(qū)間的數(shù)據(jù)類(lèi)型和范圍：整數(shù)類(lèi)型、-109--109數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第13頁(yè)。算法一：離散化思路：◆設(shè)f[i]:0..1,初始值全部為0?！裘孔x入一個(gè)區(qū)間abFori:=1tonForj:=atobdof[j]=1◆最后輸出f[j]=1的區(qū)間。時(shí)間復(fù)雜度：1012，只能過(guò)部分?jǐn)?shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第14頁(yè)。算法二：直接合并1、按每個(gè)區(qū)間的左端的的值升序排列。由于N<=1000,任意排序算法。注意數(shù)據(jù)結(jié)構(gòu)的設(shè)置:

◆記錄類(lèi)型

◆二維數(shù)組：

a:array[1..1000,1..2]oflongint;a:array[1..1000]ofarray[1..2]oflongint數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第15頁(yè)。2、合并過(guò)程◆輸出第一個(gè)區(qū)間的左端點(diǎn)坐標(biāo)（最小的）◆依次處理后面的n-1的區(qū)間。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];數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第16頁(yè)。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);數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第17頁(yè)。2、潛水比賽

在馬其頓王國(guó)舉行了一次潛水比賽。其中一個(gè)項(xiàng)目是從高山上跳下水，再潛水達(dá)到終點(diǎn)。這是一個(gè)團(tuán)體項(xiàng)目，一支隊(duì)伍由n人組成。在潛水時(shí)必須使用氧氣瓶，但是每只隊(duì)伍只有一個(gè)氧氣瓶。最多兩人同時(shí)使用一個(gè)氧氣瓶，但此時(shí)兩人必須同步游泳，因此兩人達(dá)到終點(diǎn)的時(shí)間等于較慢的一個(gè)人單獨(dú)游到終點(diǎn)所需要的時(shí)間。好在大家都很友好，因此任何兩個(gè)人后都愿意一起游水。安排一種潛水的策略，使得最后一名選手盡量的達(dá)到終點(diǎn)。輸入：第一行：隊(duì)伍的人數(shù)n（<=1000）。第二行：n個(gè)數(shù)，分別是n個(gè)人潛水所用的時(shí)間ti(<=1000)。樣例：輸入：3134輸出：8數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第18頁(yè)。分析:先從簡(jiǎn)單入手:1)n=2,時(shí)間t:110所需的時(shí)間為:102)n=3,時(shí)間t:134所需的時(shí)間為:3+1+4=83)n=4,時(shí)間t:1101112所需的時(shí)間為:10+1+11+1+12=35貪心策略方法一:N個(gè)人:每個(gè)人所需的時(shí)間:t1，t2，……tn。假設(shè)t1最小。每次由t1接送人和氧氣瓶，則總時(shí)間：s=t2+t3+。。。。tn+（n-2）*t1數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第19頁(yè)。4）n=4，每個(gè)人所用時(shí)間：1258采用貪心策略方法一：計(jì)算所用的總時(shí)間為：2+5+8+1*2=17事實(shí)上：采用下面策略：第一步：12一起先過(guò)，用時(shí)：2第二步：1送回氧氣瓶，用時(shí)：1第三步：58一起過(guò)，用時(shí)：8第四步：2送回氧氣瓶，用時(shí)：2第五步：1和2一起過(guò)去，用時(shí)：2完成。共用時(shí)：2+1+8+2+2=15<17數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第20頁(yè)。貪心策略方法二:將n個(gè)人的時(shí)間從小到達(dá)排序，假設(shè)從小到大為：t1，t2，……tn1：t1和t2過(guò)：t22：t1帶瓶返回：t13：最大的兩個(gè)人：tntn-1過(guò)：tn4：t2帶瓶返回：t2把以上看作一趟：把用事最長(zhǎng)的兩個(gè)人tn，tn-1送過(guò)去：用時(shí)：2*t2+t1+tn重復(fù)上述過(guò)程：用t1和t2在把tn-2

，tn-3

送過(guò)去，用時(shí)：2*t2+t1+tn-2每趟都用t1和t2，每趟運(yùn)送2人。最后如果剩2人：t1，t2：時(shí)間：t2最后如果剩3人：t1，t2，t3時(shí)間：t1+t2+t3數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第21頁(yè)。5）n=6，時(shí)間：1101112100101按照貪心策略方法二:計(jì)算總時(shí)間：165另外的方法：10101110010110110101121211111111111010157！數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第22頁(yè)。貪心策略方法三：每一趟送用時(shí)間最長(zhǎng)的兩個(gè)人時(shí)：根據(jù)情況選擇：用t1和t2兩個(gè)人還是只用t1一個(gè)人。用t1和t2送一趟用時(shí)：x=2*t2+t1+tn用t1一個(gè)人送一趟（2人）：y=2*t1+tn+tn-1每送一趟都要比較x和y的大?。篒fx>ythen用t1送else用t1和t2送數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第23頁(yè)。貪心三算法：數(shù)組a存時(shí)間：把時(shí)間從小到大排序。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);數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第24頁(yè)。三、棧的應(yīng)用典型應(yīng)用：表達(dá)式類(lèi)問(wèn)題的求解中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式中綴表達(dá)式求值數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第25頁(yè)?！締?wèn)題描述：】判斷包含有括號(hào){，[，<，（，），>，]，}的字符串是否是合法匹配。例如以下是合法的括號(hào)匹配：(),[],(()),([]),()[],()[()]以下是不合法括號(hào)匹配的：(,[,],)(,([)],([()【輸入：】一行，字符串（長(zhǎng)度范圍：[1，500]）?！据敵觯骸咳绻址欣ㄌ?hào)匹配是合法的輸出“yes”，不合法的輸出“no”?！緲永?輸入：】abc{a[bb]m}aa<ss>【樣例1輸出：】yes【樣例2輸入：】abc{a[bb]maa<ss>【樣例2輸出：】no1、括號(hào)匹配數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第26頁(yè)。s:ansistring;ch:array[1..8]ofchar=('{','[','<','(',')','>',']','}');利用棧操作主程序：

beginreadlnI(s);ifcheckthenwriteln('yes')elsewriteln('no');end;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第27頁(yè)。functioncheck:boolean;//檢測(cè)函數(shù)：合法返回true；非法返回false；

beginlen:=length(s);t:=0;//棧頂指針；

i:=1;whilei<=lendobegink1:=find(s[i]);//返回序號(hào)

if(k1>0)and(k1<=4)thenpush(k1);//左括號(hào)進(jìn)棧

ifk1>4then//右括號(hào)，出棧判斷是否配對(duì)。

beginift=0thenexit(false);//空棧：非法的，預(yù)防棧溢出；

k2:=pop;ifk1+k2<>9thenexit(false);//不匹配退出檢測(cè)

end;inc(i);end;ift=0thenexit(true)elseexit(false);//?？眨汉戏ǎ环强眨悍欠?；

end;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第28頁(yè)。functionfind(x:char):integer;//返回括號(hào)的序號(hào)函數(shù),用序號(hào)代替括號(hào);0：不是括號(hào)

vari:integer;beginfori:=1to8doifx=ch[i]thenexit(i);exit(0);end;Find(x:char)函數(shù)數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第29頁(yè)。2、中綴表達(dá)式求值【問(wèn)題描述：】輸入表達(dá)式，輸出值。1）、表達(dá)式中除了數(shù)字外0----9外，僅含有運(yùn)算符合：+、-、*、/、（、）六種符號(hào)。2）、輸入的數(shù)全部為正整數(shù)，不含有如下類(lèi)似的表達(dá)式：+3，-45等。3）、表達(dá)式長(zhǎng)度不超過(guò)100，中間運(yùn)算值以及最后的運(yùn)算結(jié)果都在[-109，109]內(nèi)。4）、/運(yùn)算只取整數(shù)部分。采用div即可?！据斎耄骸亢戏ǖ闹芯Y表達(dá)式?！据敵觯骸勘磉_(dá)式的值【樣例輸入：】3*（7-2）【樣例輸出：】15數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第30頁(yè)。表達(dá)式類(lèi)問(wèn)題的兩種求解算法：◆算符優(yōu)先算法：棧操作。

符號(hào)棧，操作數(shù)棧

1、先化中綴，再求值。

2、直接求值?？紤]情況復(fù)雜，代碼復(fù)雜，亂?！暨f歸處理算法數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第31頁(yè)。分析:

采用遞歸算法:

設(shè)表達(dá)式：s=s1ops2;op是最低優(yōu)先運(yùn)算符。

1）、找s中的最低優(yōu)先級(jí)運(yùn)算符:op2）、先計(jì)算s1和s2；

3）、然后s1和s2再作op運(yùn)算。

s1和s2采取同樣的方法。如：34*10+30+10*5數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第32頁(yè)。主程序：BEGINreadln（S）；

n:=length(S);ans=work(1,n)writeln(ans);END;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第33頁(yè)。functionwork(L,r:longint):longint;//求表達(dá)式SL……Sr的值

vark,a,b:longint;beginifst[l]='('theninc(l);ifst[r]=')'thendec(r);k:=find1(l,r);//最低優(yōu)先級(jí)算符的位置

ifk=0thenexit(data(l,r));//返回?cái)?shù)值

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

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

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

end;遞歸算法數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第34頁(yè)。標(biāo)號(hào)法求運(yùn)算符的優(yōu)先級(jí)：

◆+-的標(biāo)號(hào)為1，*/的標(biāo)號(hào)為2。

◆遇到括號(hào)標(biāo)號(hào)加2。標(biāo)號(hào)大的運(yùn)算優(yōu)先級(jí)高。34+2*(23+3)-(2+(3+5)*3))+10+5數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第35頁(yè)。

預(yù)處理：求出表示式中S運(yùn)算符號(hào)的優(yōu)先級(jí)

fori:=1tondoh[i]:=maxint;//運(yùn)算數(shù)優(yōu)先級(jí)最大

base:=0;fori:=1tondocasest[i]of'(‘:inc(base,2);')‘:dec(base,2);'+‘,'-‘:h[i]:=base+1;'*‘,'/‘:h[i]:=base+2;end;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第36頁(yè)。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);//最低優(yōu)先級(jí)算符的位置數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第37頁(yè)。functiondata(l,r:longint):longint;vari:longint;begindata:=0;fori:=ltordodata:=data*10+ord(st[i])-48;end;data(l,r)：返回?cái)?shù)值數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第38頁(yè)。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位置的算符計(jì)算數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第39頁(yè)。3、中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式【問(wèn)題描述：】輸入中綴表達(dá)式，輸出后綴表達(dá)式的形式，運(yùn)算符號(hào)：+、-、*、/。每個(gè)操作數(shù)后面用“.”作為該操作數(shù)的結(jié)束標(biāo)志。表達(dá)式除中的括號(hào)只有“（”和“）”?！据斎耄骸亢戏ǖ闹芯Y表達(dá)式（長(zhǎng)度不超過(guò)100）【輸出：】后綴表達(dá)式?！緲永斎耄骸?*(5–2)+7【樣例輸出：】3．5．2．-*7．+數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第40頁(yè)。分析：假設(shè)表達(dá)式：s=s1ops2，op為最低優(yōu)先級(jí)運(yùn)送符。1、首先把整個(gè)表達(dá)式中優(yōu)先級(jí)最低的符號(hào)op放在最后邊。變成：s1s2op2、再依次處理s1和s2：

s1=s11op1s12s2=s21op2s22

變成：s11s12op1s21s22op2

op3、再處理s11s12s21s2遞歸思想數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第41頁(yè)。//Main;beginreadln(s);Ans:=work(1,len);writeln(Ans);end;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第42頁(yè)。functionwork(l,r:integer):string;//把表達(dá)式SL……Sr轉(zhuǎn)化為后綴表達(dá)式。

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;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第43頁(yè)。四、隊(duì)列的應(yīng)用典型應(yīng)用：廣度優(yōu)先搜索數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第44頁(yè)。概念

在一端進(jìn)行插入（進(jìn)隊(duì)列），在另一端進(jìn)行刪除（出隊(duì)列）的線(xiàn)性表。插入的一端稱(chēng)為隊(duì)尾：closed;（指向隊(duì)尾，最后一個(gè)元素）刪除的一端稱(chēng)為隊(duì)首：open(習(xí)慣指向隊(duì)首的前一位置，空的位置)3265419openclosed隊(duì)列數(shù)組a下標(biāo)：1234567……隊(duì)列空：open>=closed;非空：open<closed數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第45頁(yè)。1、合并石子【問(wèn)題描述：】

小Ray在河邊玩耍，無(wú)意中發(fā)現(xiàn)一些很漂亮的石子堆，于是他決定把這些石子搬回家。河灘上共有n堆石子，小Ray在把石子搬回家之前首先要把這n堆石子合并為一堆石子。已知小Ray每次可以選擇其中的兩堆石子合并為一堆，合并一次石子他要消耗的體力是兩堆石子的數(shù)量和。請(qǐng)計(jì)算小Ray把n堆石子合并成一堆最少消耗的體力值是多少?！据斎耄骸康谝恍校簄（<=30000）.第二行：那個(gè)用空格隔開(kāi)的數(shù)，分別表示n堆石子的數(shù)量。（每堆<10000）【輸出：】n堆石子合并成一堆所消耗的最小體力值。說(shuō)明:分別用隊(duì)列和堆兩種算法實(shí)現(xiàn)。【樣例輸入：】3124【樣例輸出：】10數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第46頁(yè)。

在最優(yōu)二叉樹(shù)中非葉結(jié)點(diǎn)的度均為2，因此采用順序存儲(chǔ)結(jié)構(gòu)為宜。如果帶權(quán)葉結(jié)點(diǎn)數(shù)為n個(gè)，則最優(yōu)二叉樹(shù)的結(jié)點(diǎn)數(shù)為2n-1個(gè)。由此得出最優(yōu)二叉樹(shù)的數(shù)據(jù)類(lèi)型定義Maxn=30000;n=葉結(jié)點(diǎn)數(shù)的上限；

m=2*n-1；{最優(yōu)二叉樹(shù)的結(jié)點(diǎn)數(shù)}Typenode=record{結(jié)點(diǎn)類(lèi)型}data：integer；{權(quán)值}prt，lch，rch：longint；{父指針、左、右指針和路徑長(zhǎng)度}end；Vara：array[1..maxn]oflongint；{其中a[1‥n]為葉結(jié)點(diǎn)，a[n+1‥2n-1]為中間結(jié)點(diǎn)，根為a[2n-1]}算法一(hafuman.pas)數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第47頁(yè)。procedurecreat;//創(chuàng)建哈夫曼樹(shù)

vari,j,k:longint;beginsum:=0;//費(fèi)用

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;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第48頁(yè)。functionfindmin(k:longint):longint;//在前k個(gè)街道中找最小的結(jié)點(diǎn)，父結(jié)點(diǎn)為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是所求的費(fèi)用時(shí)間復(fù)雜度：O(n2)，無(wú)法完成n=30000數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第49頁(yè)。算法二（stone.pas）設(shè)置兩個(gè)隊(duì)列：a，b隊(duì)列a：保存初始的n個(gè)葉結(jié)點(diǎn)，從小到大排序。隊(duì)列b:依次放生成的新結(jié)點(diǎn)，遞增的。生成結(jié)點(diǎn)過(guò)程：Mindata=min{a[opena]+a[opena+1];b[openb]+b[openb+1];a[open]+b[open]}Inc(closedb);B[closedb]=mindata;采用快速排序；時(shí)間復(fù)雜度：O（n*long(n)）合并的時(shí)間復(fù)雜度：O（n）總的時(shí)間復(fù)雜度：O（n*long(n)）數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第50頁(yè)。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;將石子從小到大排序放入數(shù)組a；數(shù)組b，一次存放合并后的石子，同樣是遞增的的？數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第51頁(yè)。將石子從小到大排序放入數(shù)組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;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第52頁(yè)?！締?wèn)題描述：】在n*n的棋盤(pán)上有一匹馬在第x行第y列的格子上。棋盤(pán)上有些格子上有障礙物，馬不能達(dá)到有障礙物的格子。已知馬在棋盤(pán)中的走法按“日“字8個(gè)方向可走，如下圖所示：?jiǎn)枺耗男└褡幽艿竭_(dá)，到達(dá)這些格子的最小步數(shù)是多少?！据斎耄骸康谝恍?n（n<=100）,x,y

(馬的開(kāi)始位置)。接下來(lái)n行為棋盤(pán)的描述：“-“為空格子，”+“表示該格子有障礙物?！据敵觯骸縩行，每行n個(gè)用空格隔開(kāi)的數(shù)，表示馬到達(dá)該格子的最少步數(shù)，如果無(wú)法到達(dá)則用-1表示。2、馬的遍歷數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第53頁(yè)。422----------+-----【樣例輸入：】4321303223-111214【樣例輸出：】０數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第54頁(yè)。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;//記錄最少步數(shù)

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;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第55頁(yè)。procedurebfs;//廣度優(yōu)先搜索

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;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第56頁(yè)。廣度優(yōu)先搜索算法（bfs）:1、適合的題目類(lèi)型：

1）、求從給定初始狀態(tài)到目標(biāo)狀態(tài)最少需要的步數(shù)。

2）、給定初始狀態(tài)，經(jīng)過(guò)k步后能夠到達(dá)哪些狀態(tài)。2、利用的數(shù)據(jù)結(jié)構(gòu)：隊(duì)列。3、狀態(tài)的最大值：決定隊(duì)列的大?。ǚ浅Ｖ匾?、隊(duì)列里需要記住哪些狀態(tài)：一般使用記錄數(shù)據(jù)類(lèi)型。5、狀態(tài)的轉(zhuǎn)移：不能遺漏。6、狀態(tài)的判重：避免重復(fù)進(jìn)入隊(duì)列。（結(jié)合跳馬題目分析）數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第57頁(yè)。4、Bfs的基本框架：初始化；建立數(shù)據(jù)庫(kù)（隊(duì)列）；初始狀態(tài)進(jìn)入隊(duì)列；Open=0：隊(duì)列的首指針；Closed=1：隊(duì)列的尾指針（開(kāi)始時(shí)指向初始狀態(tài)）；Quene[1]:初始結(jié)點(diǎn);While（open<closed{還有未擴(kuò)展的結(jié)點(diǎn)，隊(duì)列不空}）doBeginInc（open）；{移動(dòng)隊(duì)列的首指針：出隊(duì)列}

記錄open狀態(tài)；

Fori=1tomethoddo{按規(guī)則擴(kuò)展下一層新的子結(jié)點(diǎn)}Begin

生成新的結(jié)點(diǎn);If新結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)then輸出目標(biāo)，搜索結(jié)束；

If新結(jié)點(diǎn)是以前沒(méi)出現(xiàn)過(guò)then保存新結(jié)點(diǎn)（入隊(duì)列）；

EndEnd；數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第58頁(yè)。3、中國(guó)盒子問(wèn)題給定10個(gè)盒子排成一行，其中有兩個(gè)相鄰的盒子是空的，其余的盒子中有4個(gè)A和4個(gè)B，例如：移動(dòng)規(guī)則：任意兩相鄰字母可移到空盒子中去，但這兩個(gè)字母的原來(lái)順序保持改變。目標(biāo)：全部的A在左邊，全部的B在右邊，空格在中間。如下圖：對(duì)于任意給定的一個(gè)排列順序，最少經(jīng)過(guò)多少次移動(dòng)，能達(dá)到目標(biāo)序列。輸入：一行：初始序列，空格用0代替。輸出：初始序列達(dá)到目標(biāo)的最少移動(dòng)次數(shù)。樣例：輸入：ABBA00ABAB輸出：5AAAABBBBABBAABAB數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第59頁(yè)。中國(guó)盒子問(wèn)題（box）1、問(wèn)題：初始序列達(dá)到目標(biāo)的最少移動(dòng)次數(shù)。適合使用bfs算法。2、隊(duì)列需要保存的狀態(tài)：轉(zhuǎn)化后的字符串s;轉(zhuǎn)換需要的步數(shù)depth。適合用記錄數(shù)據(jù)類(lèi)型：

typenode=recordstr:string[10];depth:integer;end;3、狀態(tài)的多少（隊(duì)列的大小）：630數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第60頁(yè)。4、狀態(tài)的轉(zhuǎn)移：任意兩相鄰字母可移到空盒子中去，但這兩個(gè)字母的原來(lái)順序保持改變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';？數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第61頁(yè)。5、判重：

fori=1tocloseddoifa[1].str=tem最簡(jiǎn)單、最直接的判重方法。缺點(diǎn)：效率低，時(shí)間慢。st='AAAA00BBBB';數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第62頁(yè)。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;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第63頁(yè)。functionfind(tem:string):boolean;varj:integer;beginforj:=1tocloseddoiftem=q[j].strthenexit(true);exit(false);end;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第64頁(yè)。4、翻硬幣問(wèn)題描述有N個(gè)硬幣正面朝上排成一排（N>=6），每次將5個(gè)硬幣翻過(guò)來(lái)放在原位置，直到最后全部硬幣翻成反面朝上為止。編程找出最少步數(shù)輸入只有一個(gè)整數(shù)N（<1000）輸出翻幣的最少次數(shù)coin.in8Coin.out4數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第65頁(yè)。關(guān)鍵：反的最少次數(shù)僅僅與正面朝上和反面朝上的硬幣各數(shù)有關(guān)，而與硬幣的順序無(wú)關(guān)。1、需要記錄的狀態(tài)有哪些？2、怎樣判重復(fù)狀態(tài)？3、狀態(tài)轉(zhuǎn)移及條件？4、隊(duì)列的大小？數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第66頁(yè)。typenode=recordnum:integer;{正面朝上個(gè)數(shù)}depth:integer;{翻的次數(shù)}end;vara:array[1..1000]ofnode;n,open,closed,step:integer;b:array[0..1000]ofboolean;{(b[i]：i個(gè)正面朝上的情況是否出現(xiàn)過(guò))}數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第67頁(yè)。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表示當(dāng)前正面朝上的硬幣個(gè)數(shù))}step:=a[open].depth+1;

fori:=1to5do{(翻i個(gè)正面朝上的硬幣)}if(m>=i)and(n-m>=5-i)then{(m-i+5-i:正面朝上的個(gè)數(shù))}beginifm-i+5-i=0thenprint(step);{正面朝上的個(gè)數(shù)為0時(shí)結(jié)束}ifnot(b[m-i+5-i])thenbegininc(closed);{進(jìn)隊(duì)列}b[m-i+5-i]:=true;a[closed].num:=m-i+5-i;{正面朝上的個(gè)數(shù)}a[closed].depth:=step;{翻的次數(shù)}end;end;end;end;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第68頁(yè)。數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第69頁(yè)。可以看出：除了6和8是特例外，其他滿(mǎn)足：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數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第70頁(yè)。1、圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣、鄰接表2、圖的遍歷：dfs、bfs、連通分量3、無(wú)向圖的傳遞閉包4、最短路徑算法：floyed,dijkstra5、最小生成樹(shù)算法：prim,kruskal五、圖數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第71頁(yè)。1253412534678圖一圖二定義：連通：如果從頂點(diǎn)u到v有路徑，則稱(chēng)u和v是連通的。連通圖：圖中任意的兩個(gè)頂點(diǎn)u和v都是連通的。圖一是連通圖，圖二是非連通圖連通分量：無(wú)向圖中的極大連通子圖。圖二中有3個(gè)連通分量：{1245}{36}{78}求連通分量數(shù)，最大連通分量等。有向圖：強(qiáng)連通、強(qiáng)連通圖、強(qiáng)連通分量◆圖的連通分量數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第72頁(yè)。//連通分量的算法

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

inc(sum);dfs(i);end;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第73頁(yè)?！痉缸飯F(tuán)伙】

警察抓到了n個(gè)罪犯，警察根據(jù)經(jīng)驗(yàn)知道他們屬于不同的犯罪團(tuán)伙，卻不能判斷有多少個(gè)團(tuán)伙，但通過(guò)警察的審訊，知道其中的一些罪犯之間相互認(rèn)識(shí)，已知同一犯罪團(tuán)伙的成員之間直接或間接認(rèn)識(shí)。有可能一個(gè)犯罪團(tuán)伙只有一個(gè)人。請(qǐng)你根據(jù)已知罪犯之間的關(guān)系，確定犯罪團(tuán)伙的數(shù)量。已知罪犯的編號(hào)從1至n。輸入：第一行：n（<=10000,罪犯數(shù)量），第二行：m（<=100000，關(guān)系數(shù)量）以下若干行：每行兩個(gè)數(shù)：I和j，中間一個(gè)空格隔開(kāi)，表示罪犯i和罪犯j相互認(rèn)識(shí)。輸出：一個(gè)整數(shù)，犯罪團(tuán)伙的數(shù)量。輸入：118124534135671051089輸出：3測(cè)試數(shù)據(jù)說(shuō)明：1s共10個(gè)測(cè)試數(shù)據(jù)：（1）5個(gè)數(shù)據(jù)：

n<=1000,m<=5000;（2）5個(gè)數(shù)據(jù)：

10000>=n>=9000,

100000>=m>=90000;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第74頁(yè)。建立無(wú)向圖的模型。最容易想到的算法1：把n個(gè)人看成圖的n個(gè)頂點(diǎn)；相互認(rèn)識(shí)的連一條邊。相互認(rèn)識(shí)的所有人構(gòu)成一個(gè)極大連通子圖。問(wèn)題轉(zhuǎn)化為：求無(wú)向圖的連通分量（有多少個(gè)極大連通子圖）數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第75頁(yè)。//建圖

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;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第76頁(yè)。proceduremain;vari:integer;begin

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

inc(sum);dfs(i);end;writeln(sum);end;數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第77頁(yè)。?時(shí)間和空間！鄰接矩陣：空間太大，超時(shí)。鄰接表：空間滿(mǎn)足，時(shí)間>1s

無(wú)法通過(guò)后5個(gè)數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第78頁(yè)。輸入：118124534135671051089高效的樹(shù)型結(jié)構(gòu)算法2：建立森森結(jié)構(gòu)，統(tǒng)計(jì)樹(shù)的數(shù)量數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第79頁(yè)。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;程序算法：數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第80頁(yè)。readln(n);readln(m);fillchar(a,sizeof(a),0);{默認(rèn)根標(biāo)志是0，開(kāi)始全是樹(shù)根}fori:=1tomdobeginreadln(x,y);p:=find(x);{查找x的根}q:=find(y);{查找y的根}ifp<>qthena[q]:=p;{合并p和q子樹(shù)}end;ans:=0;{樹(shù)根記數(shù)}fori:=1tondoifa[i]=0theninc(ans);{記錄樹(shù)根結(jié)點(diǎn)}writeln(ans);end.數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第81頁(yè)。◆無(wú)向圖的傳遞閉包判斷無(wú)向圖的連通性1234657輸入圖的邊的信息，輸出各點(diǎn)的連通行。輸入：7122313345667輸出：11110001111000111100011110000000111000011100001110110000101000011010000010000000001000001010000010鄰接矩陣數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第82頁(yè)。判斷結(jié)點(diǎn)i和j的連通性：ijk1、結(jié)點(diǎn)i和j如果原來(lái)有邊則連通。2、如果i和j之間沒(méi)有邊：如果存在另外的一個(gè)結(jié)點(diǎn)k，滿(mǎn)足：i與k連通，k與j連通，則i與j連通。否則i和j不連通。Can[i,j]:true，i與j之間有邊；false：無(wú)邊。則：Can[i,j]=can[i,j]or(can[i,k]andcan[k,j])數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第83頁(yè)。fork:=1tondofori:=1tondoforj:=1tondocan[i,j]:=can[i,j]or(can[i,k]andcan[k,j]);過(guò)程：數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第84頁(yè)。產(chǎn)生數(shù)【問(wèn)題描述:】給出一個(gè)正整數(shù)n（n<10^50)和k個(gè)變換規(guī)則（k<=15）。每個(gè)變換規(guī)則是指：一位數(shù)可變換成另一個(gè)一位數(shù)：規(guī)則的右部不能為零。例如：n=234。有規(guī)則（k＝2）：

2－>53－>6上面的整數(shù)234經(jīng)過(guò)變換后可能產(chǎn)生出的整數(shù)為（包括原數(shù)）:

234534264564共4種不同的產(chǎn)生數(shù)?！救蝿?wù)：】給出一個(gè)整數(shù)n和k個(gè)變換規(guī)則。求經(jīng)過(guò)任意次的變換（0次或多次），能產(chǎn)生出多少個(gè)不同整數(shù)。僅要求輸出個(gè)數(shù)?！据斎耄骸康谝恍校簄。第二行：k。以下k行：每行兩個(gè)一位數(shù)：xy，中間一個(gè)空格，表示一個(gè)變換規(guī)則：x可以變?yōu)閥?！据敵觯骸恳粋€(gè)整數(shù)（滿(mǎn)足條件的個(gè)數(shù)）：【輸入樣例：】23422536【樣例輸出：】4應(yīng)用舉例數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第85頁(yè)。?本題搜索顯然是不行的。?對(duì)于只需計(jì)數(shù)而不需求具體方案的題目，一般都不會(huì)用搜索解決。分析：?乘法原理直接進(jìn)行計(jì)數(shù)。用F[i]表示數(shù)字i包括本身可以變成的數(shù)字總個(gè)數(shù)這里的變成可以是直接變成也可以是間接變成：比如3->5,5->7,那么3->7那么對(duì)于一個(gè)數(shù)a（用數(shù)組存,長(zhǎng)度為n），根據(jù)乘法原理它能產(chǎn)生出不同整數(shù)數(shù)量：F[a[1]]*F[a[2]]*F[a[3]]*…F[a[n]]數(shù)據(jù)結(jié)構(gòu)總結(jié)全文共96頁(yè)，當(dāng)前為第86頁(yè)。init；

//建圖

makef;//生成每個(gè)數(shù)字的轉(zhuǎn)化數(shù)量

n:=length(s);fillchar(ans,sizeof(ans),0);//結(jié)果

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