[其他資格考試]pascal數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用(編輯修改稿)
2024-09-17 13:53 本頁面
【文章內(nèi)容簡介】 0。 (C)a[ha]b[hb]將比較的小者取出送入X，取出數(shù)的隊列的頭指針相應(yīng)加1。 (4)重復(fù)(2)，(3)直至取出第N項為止。注意：數(shù)組的上標(biāo)定到1000，當(dāng)N較大時會出現(xiàn)隊滿溢出的情況，可以將上標(biāo)定大些，或改用循環(huán)鏈表進行改進。練習(xí)二高精度加法：設(shè)計一個程序?qū)崿F(xiàn)兩個正整數(shù)(長度不超過200位)的求和運算。解：Pascal程序：Program lx7_2_1；uses crt；var a，b：string； c，i，x，y，lm，ha，hb：integer； m：array[1..300] of integer；begin clrscr； write(39。A=39。)；readln(a)； write(39。B=39。)；readln(b)； ha：=length(a)；hb：=length(b)； c：=0；lm：=1； while (ha0) or (hb0) do begin if ha0 then x：=ord(a[ha])48 else x：=0； if hb0 then y：=ord(b[hb])48 else y：=0； m[lm]：=x+y+c； c：=m[lm] div 10； m[lm]：=m[lm] mod 10； inc(lm)；dec(ha)；dec(hb)； end； if c0 then m[lm]：=c else dec(lm)； write(a，39。+39。，b，39。=39。)； for i：=lm downto 1 do write(m[i])；end.基數(shù)排序：將278，109，063，930，589，184，505，269，008，083利用基數(shù)排序法按從小到大的順序排列。分析：基數(shù)排序法是一種基于對關(guān)鍵字進行分配和收集的排序法，常用最低位優(yōu)先法(Least Significant Digit first)，簡稱LSD法。它先從最低位的關(guān)鍵字開始進行排序，然后對次低位關(guān)鍵字進行排序，依此類推，直到對最高位進行排序為止。例如本題，關(guān)鍵字是各位上的數(shù)碼，從0到9共10個。首先，將需要排序的數(shù)放在隊列A中，如圖：有1至2N的自然數(shù)，按從小到大的順序排成一列，對這2N個數(shù)進行如下操作：（1）將這2N個數(shù)等分成A，B兩組，即： A組：1，2，...，N；B組：N+1，N+2，...，2N（2）輪流從A，B兩組中按順序取數(shù)： 1，N+1，2，N+1，...，N，2N（3）再將取過的數(shù)等分為兩組，并重復(fù)上述操作，直到這2N個數(shù)又按從小到大的順序排好為止。例如：當(dāng)N=3時，操作如下：初始序列為：1，2，3，4，5，6 (1) 1，4，2，5，3，6 (2) 1，5，4，3，2，6 (3) 1，3，5，2，4，6 (4) 1，2，3，4，5，6分析：將1至2N的自然數(shù)分成兩組，用兩個隊列來模擬上述過程即可。有一個數(shù)，它的末位數(shù)字是N，將N移到這個數(shù)的首位，得到的新數(shù)恰好是原數(shù)的N倍，現(xiàn)輸入N的值，求滿足條件的最小的數(shù)。第三節(jié) 棧“?！笔且环N先進后出(First In Last Out)或后進先出(Last In First Out)的數(shù)據(jù)結(jié)構(gòu)。日常生活中也常能見到它的實例，如壓入彈夾的子彈，最先壓進去的子彈最后射出，而最后壓入的子彈則最先發(fā)射出來?！皸！笔且环N只能在一端進行插入和刪除的特殊的線性表，進行插入和刪除的一端稱為“棧頂”，而不動的一端稱為棧底(如下圖)。插入的操作也稱為進棧(PUSH)，刪除的操作也稱為出棧(POP)。出棧←─┐┌──進棧││↓│├───┤棧頂→│ an│ ├───┤│...│├───┤│ a2│├───┤棧底→│ a1│└───┘例算術(shù)表達式的處理：由鍵盤輸入一個算術(shù)表達式(含有+，，*，/，(，)運算)，且運算結(jié)果為整數(shù))，編一程序求該算術(shù)表達式的值。分析：表達式的運算是程序設(shè)計中一個基本的問題，利用棧求解是一種簡單易行的方法，下面介紹的是算符優(yōu)先法。比如：4+2*310/5我們都知道，四則運算的法則是：(1)先乘除后加減，同級運算從左到右；(2)有括號先算括號。因此上例的結(jié)果是8。算符優(yōu)先法需要兩個棧：一個是操作數(shù)棧，用來存放操作數(shù)，記為SN；另一個是操作符棧用來存放運算符，記為SP。具體處理方法如下： (1)將SN，SP置為空棧； (2)從左開始掃描表達式，若是操作數(shù)壓入SN中；若是操作符則與SP的棧頂操作符比較優(yōu)先級有兩種可能：（a）優(yōu)先級小于棧頂算符，此時從SN中彈出兩個操作數(shù)，從SP彈出一個操作符，實施運算，結(jié)果壓入SN的棧頂。（b）優(yōu)先級大于棧頂算符，此時將操作符壓入SP中。 (3)重復(fù)操作(2)直至表達式掃描完畢，這時SP應(yīng)為空棧，而SN只有一個操作數(shù)，即為最后的結(jié)果。為了方便起見，可以將作為表達式的結(jié)束標(biāo)志，初始化時在SP的棧底壓入，并將其優(yōu)先級規(guī)定為最低。下面給出的是計算4+2*310/5的示意圖步驟 SN SP讀入字符│說明─────────────────┼──────────1空 4│將4壓入SN2 4160
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1