Download presentation
Presentation is loading. Please wait.
1
書名 Java於資料結構與演算法之實習應用
書號 PG20098 原著 河西朝雄著 譯者 周明憲/徐堯譯 台北總公司／台北縣汐止市新台五路一段112號10樓A棟 Building A, 10F, 112, Shin-Tai-Wu Road Sec. 1, Shijr, Taipei, Taiwan. 電話／ 傳真／ 台中辦事處／台中市文心路一段540號4樓-1 4-1F, 540, Wen Shing Road, Sec. 1, Taichung, Taiwan. 電話／ 傳真／ 博碩網址：
2
第五章 學習重點 電腦常會處理到大量的資料，這時的資料結構(data structure)如果不同，解決問題的演算法就會不同。N.Wirth的曾寫過一本名著「Algorithms + Data Structures = Programs（演算法＋資料結構＝程式）」，誠如此書書名，資料結構與演算法具有緊密的關係，選擇好的資料結構才會製作出好的程式。資料結構的串列、樹、圖形非常重要。樹與圖形將會在第6章與第7章中說明。 本章將會說明堆疊(stack)、佇列 (queue) 與串列(list)等資料結構。 由於串列為使資料的插入與刪除作業容易進行的資料結構，因此本章會說明串列，並說明雙向串列、循環串列等特殊串列。 堆疊的應用方面，本章舉逆向波蘭標記法(reverse polish notation)與語法分析(parsing)為例加以說明，串列的應用方面，則舉自我重整搜尋(self re-organizing search)與hash的鏈節法為例來加以說明。
3
5-0 何謂資料結構 Java的資料型態可大致分類如下： 典型的資料結構有下列數種： 1. 資料表格(table) 2. 堆疊(stack)
5-0 何謂資料結構 Java的資料型態可大致分類如下： 典型的資料結構有下列數種： 1. 資料表格(table) 2. 堆疊(stack) 3. 佇列(queue) 4. 串列(list) 5. 樹(tree) 6. 圖形(graph) 這些資料結構是由使用者將其與程式語言的資料型態加以組合而製作出來的。 資料表格、堆疊與佇列可用陣列表現出來，串列、樹與圖形則可用結構（記錄）與指標型態表現出來。 由於Java沒有C語言、C++所具有的指標及結構，因此以類別(class)來取代結構，以陣列元素來取代指標。 基本型態 字元型態、整數型態、實數型態 資料型態 陣列 類別
4
5-1 堆疊 將資料依序從堆疊(stack)下面儲存起來，並視需要從堆疊的上面將資料取出的方式（last in first out：後進先出）之資料結構稱為堆疊(stack)。 堆疊通常1維陣列表現出來。 將資料儲存在堆疊的動作稱為push、由堆疊取出資料的動作則稱為pop。至於堆疊上的資料儲存在哪個位置，則由堆疊指標來管理。
5
private final int MaxSize=1000; // 堆疊大小
private int[] stack=new int[MaxSize]; // 堆疊 private int sp=0; // 堆疊指標 int push(int n) { // 將資料儲存在堆疊內 if (sp<MaxSize) { stack[sp]=n; sp++; return 0; } else return -1; // 堆疊已滿的時候 int pop(int[] n) { // 從堆疊取出資料 if (sp>0) { sp--; n[0]=stack[sp]; return -1; // 堆疊已空的時候 ………
6
河內塔的模擬 將棒a、b、c圓盤狀態分別儲存至pie[][0],pie[][1],pie[][2]，以堆疊指標sp[0],sp[1],sp[2]來管理圓盤的最前面的位置。圓盤由最小的圓盤開始按1、2、3...的順序編號。 將棒s的最前面的圓盤移至棒d的動作是以 pie[sp[d]][d] = pie[sp[s]-1][s] 來表示。
![河內塔的模擬 將棒a、b、c圓盤狀態分別儲存至pie[][0],pie[][1],pie[][2]，以堆疊指標sp[0],sp[1],sp[2]來管理圓盤的最前面的位置。圓盤由最小的圓盤開始按1、2、3...的順序編號。](http://slidesplayer.com/slide/11742958/65/images/6/%E6%B2%B3%E5%85%A7%E5%A1%94%E7%9A%84%E6%A8%A1%E6%93%AC+%E5%B0%87%E6%A3%92a%E3%80%81b%E3%80%81c%E5%9C%93%E7%9B%A4%E7%8B%80%E6%85%8B%E5%88%86%E5%88%A5%E5%84%B2%E5%AD%98%E8%87%B3pie%5B%5D%5B0%5D%2Cpie%5B%5D%5B1%5D%2Cpie%5B%5D%5B2%5D%EF%BC%8C%E4%BB%A5%E5%A0%86%E7%96%8A%E6%8C%87%E6%A8%99sp%5B0%5D%2Csp%5B1%5D%2Csp%5B2%5D%E4%BE%86%E7%AE%A1%E7%90%86%E5%9C%93%E7%9B%A4%E7%9A%84%E6%9C%80%E5%89%8D%E9%9D%A2%E7%9A%84%E4%BD%8D%E7%BD%AE%E3%80%82%E5%9C%93%E7%9B%A4%E7%94%B1%E6%9C%80%E5%B0%8F%E7%9A%84%E5%9C%93%E7%9B%A4%E9%96%8B%E5%A7%8B%E6%8C%891%E3%80%812%E3%80%813...%E7%9A%84%E9%A0%86%E5%BA%8F%E7%B7%A8%E8%99%9F%E3%80%82.jpg "將棒s的最前面的圓盤移至棒d的動作是以. pie[sp[d]][d] = pie[sp[s]-1][s] 來表示。")
7
5-2 佇列 例題33 佇列 製作將資料存入佇列的方法queuein與將資料從佇列取出的方法queueout
5-2 佇列 例題33 佇列 製作將資料存入佇列的方法queuein與將資料從佇列取出的方法queueout 從堆疊取出資料的順序為LIFO（last in first out：後進先出）方式，正好與資料的儲存順序相反，以此方法處理待處理的資料時，會先從後到的資料開始處理，而導致不公平。這時FIFO（first in first out：先進先出）方式的資料結構就有存在的必要了。這種資料結構就是佇列(queue)。 empty
8
class Rei33Frame extends Frame {
private TextField tf1,tf2; private final int MaxSize=1000; // 佇列大小 private int[] queue=new int[MaxSize]; // 佇列 private int head=0, // 指向開頭資料的指標 tail=0; // 指向尾端資料的指標 int queuein(int n) { // 將資料存入佇列 if ((tail+1)%MaxSize !=head) { queue[tail]=n; tail++; tail=tail%MaxSize; return 0; } else return -1; // 佇列已滿時 int queueout(int[] n) { // 從佇列取出資料 if (tail!=head) { n[0]=queue[head]; head++; head=head%MaxSize; return -1; // 佇列空的時候
9
5-3 製作串列 何謂串列 將由資料部分與指標部分組成的資料以鎖狀連結的資料結構稱為串列（list，或稱線性串列：linear list）。
5-3 製作串列 何謂串列 將由資料部分與指標部分組成的資料以鎖狀連結的資料結構稱為串列（list，或稱線性串列：linear list）。 head為指向第1筆記錄的指標，串列的最後1筆紀錄的指標部分NIL則為未指向任何位置（即串列的尾端）的值之意。
10
將串列以陣列的形式表現出來 定義下列的Girl類別(class)，並設name,tel為資料部分，ptr為指標部分。
class Girl { private String name; ←資料部分 private String tel; ←資料部分 private int ptr; ←指標部分 } 若將資料存入Girl類別的物件陣列a[]內，則第k個的資料則是以a[k].name、a[k].tel、a[k].ptr來表示。a[k].ptr中含有指向第k+1個節點的指標（陣列的元素編號）。 ptr為0的節點代表還沒有資料之意。NIL的值則設為-1。由於Java沒有指標，因此以陣列元素來代替。
11
例題34 製作與輸入順序相反的串列 製作與鍵盤輸入資料逆向相連的串列 如要將鍵盤輸入資料製作成串列，最簡單的方法為，將第1筆資料設為串列的尾端，將最後1筆資料設為串列的開頭。 假設新取得的節點為k，如將其加入串列的開頭，則其操作步驟如下： 換句話說，只要移動 a[k].ptr=head 存入指向目前開頭資料的指標 head=k 使head指向第k個節點 上述指標，就可輕易達到這個目的了。
12
練習問題34 製作與輸入順序相同的串列 製作與鍵盤輸入資料順向相連的串列 製作與鍵盤輸入資料順向相連的串列時，若目前的節點為k，如要將其連結至串列的尾端，就必須要有指向前1個位置的指標。我們將這個指標設為old。此外將目前的節點k的指標設為NIL。 以 a[old].ptr=k 將k連結至串列的尾端，再以 old=k 將k位置設為新的old位置。 此外，程式將a[0]設為虛擬節點，讓a[0].ptr指向開頭的節點。
13
5-4 將資料插入串列 串列適合執行資料的插入與刪除作業。如要在陣列之類的資料結構中插入新的資料或刪除現有的資料，就必須移動一部分的陣列元素。而同樣的作業若在串列中執行，則只要替換指標即可，無須移動其他的資料。
14
bt1.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) { int k; for (k=1;k<=Max;k++) { // 製作串列 if (a[k].ptr==0) { a[k]=new Girl(tf1.getText(),tf2.getText(),head); head=k; return; } tf1.setText("空間已滿"); }); bt2.addActionListener(new ActionListener() { int k,p; for (k=1;k<=Max;k++) { // 新增資料 p=head; while (p!=NIL) { if (a[p].name.equals(tf3.getText())) { a[k]=new Girl(tf1.getText(),tf2.getText(),a[p].ptr); a[p].ptr=k; p=a[p].ptr; tf3.setText("找不到鍵值");
15
5-5 刪除串列的資料 鍵值資料若位於串列的開頭，就必須修改head的內容，若位於其他位置，就必須前1個節點的指標部分，因此進行刪除作業時，須將各種情況分開處理。
16
……………… bt2.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { int p=head,old=head; while (p!=NIL){ // 刪除資料 if (a[p].name.equals(tf3.getText()) && p==head) { head=a[p].ptr; return; } if (a[p].name.equals(tf3.getText()) && p!=head) { a[old].ptr=a[p].ptr; old=p; p=a[p].ptr; ta.setText(ta.getText()+"找不到鍵值資料\n"); }); ……………
17
刪除串列的資料（虛擬節點版） 加入虛擬節點後，就不用將開頭節點與其他節點分開處理了。
若串列指標為p時，則下1個節點的名稱欄位能以a[p].name來參考，指標欄位能以a[p].ptr來參考。因此無須另外準備例題36中的old指標。 程式將a[1]設為虛擬節點
18
for (int i=1;i<=Max;i++) // 初始設定
a[i]=new Girl("","",0); head=1;a[1].ptr=NIL; // 虛擬節點 bt1.addActionListener(new ActionListener() { // 製作串列 public void actionPerformed(ActionEvent e) { int k; for (k=2;k<=Max;k++) { if (a[k].ptr==0) { a[k]=new Girl(tf1.getText(),tf2.getText(),a[1].ptr); a[1].ptr=k; return; } tf1.setText("空間已滿"); }); bt2.addActionListener(new ActionListener() { // 刪除串列 int p=head; while (a[p].ptr!=NIL) { if (a[a[p].ptr].name.equals(tf3.getText())) { a[p].ptr=a[a[p].ptr].ptr; p=a[p].ptr; ta.setText(ta.getText()+"找不到鍵值資料\n");
19
5-6 雙向串列 由head開始依序向後搜尋元素，到NIL處便結束搜尋作業的串列稱為線性串列(linear list)。除了線性以外，串列還有環狀串列(circular list)與雙向串列（雙向鏈結串列：doubly-linked list）。 環狀串列是指串列的最後的指標不是指向NIL，而是指向開頭節點的結構。 因此這種串列的資料沒有尾端。 線性串列雖可將串列資料由前向後推進，但卻無法反過來將串列資料由後向前推進。有1種串列具有向前的指標（逆向指標）與向後的指標（順向指標），這種指標稱為雙向指標。
20
例題37 雙向串列 首先以tail為基點製作下列與輸入順序相反的串列：
例題37 雙向串列 首先以tail為基點製作下列與輸入順序相反的串列： 由tail開始搜尋這個串列，並將指向右側節點的指標放至順向指標（向右的指標）內。 若由head開始搜尋這個串列，就可按資料的輸入順序搜尋節點。這個方法也是製作與鍵盤輸入資料順向的串列的方式之一。
21
for (int i=1;i<=Max;i++) // 初始設定
a[i]=new Girl(0,"","",0); tail=NIL; bt1.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { int k; for (k=1;k<=Max;k++) { // 製作逆向串列 if (a[k].L==0) { a[k]=new Girl(tail,tf1.getText(),tf2.getText(),NIL); tail=k; return; } tf1.setText("空間已滿"); }); bt2.addActionListener(new ActionListener() { int p;p=tail;head=NIL; while (p!=NIL) { // 製作順向串列 a[p].R=head; head=p; p=a[p].L; ………
22
……………… ta.setText(""); p=head; // 順向顯示串列 while (p!=NIL) { ta.setText(ta.getText()+a[p].name+","+a[p].tel+"\n"); p=a[p].R; } }); bt3.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { int p=tail; // 逆向顯示串列 p=a[p].L;
![……………… ta.setText( ); p=head; // 順向顯示串列. while (p!=NIL) { ta.setText(ta.getText()+a[p].name+ , +a[p].tel+ \n );](http://slidesplayer.com/slide/11742958/65/images/22/%E2%80%A6%E2%80%A6%E2%80%A6%E2%80%A6%E2%80%A6%E2%80%A6+ta.setText%28+%29%3B+p%3Dhead%3B+%2F%2F+%E9%A0%86%E5%90%91%E9%A1%AF%E7%A4%BA%E4%B8%B2%E5%88%97.+while+%28p%21%3DNIL%29+%7B+ta.setText%28ta.getText%28%29%2Ba%5Bp%5D.name%2B+%2C+%2Ba%5Bp%5D.tel%2B+%5Cn+%29%3B.jpg "p=a[p].R; } }); bt3.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { int p=tail; // 逆向顯示串列. p=a[p].L;")
23
練習問題37 環狀雙向串列 環狀雙向串列是指將環狀串列與雙向串列結合起來的串列，其結構如下：
練習問題37 環狀雙向串列 環狀雙向串列是指將環狀串列與雙向串列結合起來的串列，其結構如下： 在這種串列中，虛擬節點具有重要的地位。換句話說，虛擬節點具有排除對開頭節點的處理與做為資料尋中的衛兵等2項功用。 製作這種節點時，先要製作下列的空串列，然後將新的節點加至後面。
24
環狀雙向串列 程式將新節點設為k，將必須更改的指標部分設為(A)、(B)、(C)、(D)後，以下列的順序進行更改作業。若不照順序則更改作業將無法順利進行。 (D) ← 指向head的指標 (A) ← 指向左側節點的指標 (B) ← 指向k的指標 (A) ← 指向k的指標 a[a[head].L].R代表新增k之前的(B)的指標部分，a[head].L則代表指向左側節點的指標。 程式將a[1]而不是將a[0]設為虛擬節點，其原因在於程式將a[k].L==0設為判斷陣列是否為空的依據。
25
for (int i=1;i<=Max;i++) // 初始設定
a[i]=new Girl(0,"","",0); head=1; a[head].L=head;a[head].R=head; // 虛擬節點 tail=NIL; bt1.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { int k; for (k=2;k<=Max;k++) { // 製作雙向串列 if (a[k].L==0) { a[k]=new Girl(a[head].L,tf1.getText(),tf2.getText(),head); a[a[head].L].R=k; a[head].L=k; return; } tf1.setText("空間已滿"); });
26
bt2.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) { ta.setText(""); int p=a[head].R; // 順向顯示 while (p!=head) { ta.setText(ta.getText()+a[p].name+","+a[p].tel+"\n"); p=a[p].R; } }); bt3.addActionListener(new ActionListener() { int p=a[head].L; // 逆向顯示 p=a[p].L;
27
5-7 逆向波蘭標記法 如下所示 a+b-c*d/e
5-7 逆向波蘭標記法 如下所示 a+b-c*d/e 這種將運算子置於運算元（運算的對象）中間的計算式書寫方式稱為插入標記法（中置標記法：infix notation），為數學常用的計算式書寫方式。若將其改寫成 ab+cd*e/- 也就是將運算子置於運算元的後面的書寫方式則稱為後置標記法(postfix notation)，或稱為逆向波蘭標記法(reverse polish notation)。這種式子由於可如「a加b，c乘d，再減去被e除的結果」一般由式子的開頭讀起，再加上不需使用括弧即能簡單的製作出演算程序，因而廣泛的被運用在電腦上。
28
5-7 逆向波蘭標記法 要執行計算式時，以stack[]（存有取出的因子的作業用堆疊）及polish[]（製作逆向波蘭標記法的堆疊）進行下列步驟： (1)計算式結束之前反覆操作下列步驟 (2)由計算式取出1個因子 (3)在（取出的因子的優先順位）<=（堆疊最上層的因子的優先順位） 之間，將stack[]的最 上層的因子取出存入polish[]內。 (4)將(2)取出的因子存至stack[]內 (5)將stack的剩餘因子取出後存至polish[]內
![5-7 逆向波蘭標記法 要執行計算式時，以stack[]（存有取出的因子的作業用堆疊）及polish[]（製作逆向波蘭標記法的堆疊）進行下列步驟： (1)計算式結束之前反覆操作下列步驟. (2)由計算式取出1個因子.](http://slidesplayer.com/slide/11742958/65/images/28/5-7+%E9%80%86%E5%90%91%E6%B3%A2%E8%98%AD%E6%A8%99%E8%A8%98%E6%B3%95+%E8%A6%81%E5%9F%B7%E8%A1%8C%E8%A8%88%E7%AE%97%E5%BC%8F%E6%99%82%EF%BC%8C%E4%BB%A5stack%5B%5D%EF%BC%88%E5%AD%98%E6%9C%89%E5%8F%96%E5%87%BA%E7%9A%84%E5%9B%A0%E5%AD%90%E7%9A%84%E4%BD%9C%E6%A5%AD%E7%94%A8%E5%A0%86%E7%96%8A%EF%BC%89%E5%8F%8Apolish%5B%5D%EF%BC%88%E8%A3%BD%E4%BD%9C%E9%80%86%E5%90%91%E6%B3%A2%E8%98%AD%E6%A8%99%E8%A8%98%E6%B3%95%E7%9A%84%E5%A0%86%E7%96%8A%EF%BC%89%E9%80%B2%E8%A1%8C%E4%B8%8B%E5%88%97%E6%AD%A5%E9%A9%9F%EF%BC%9A+%281%29%E8%A8%88%E7%AE%97%E5%BC%8F%E7%B5%90%E6%9D%9F%E4%B9%8B%E5%89%8D%E5%8F%8D%E8%A6%86%E6%93%8D%E4%BD%9C%E4%B8%8B%E5%88%97%E6%AD%A5%E9%A9%9F.+%282%29%E7%94%B1%E8%A8%88%E7%AE%97%E5%BC%8F%E5%8F%96%E5%87%BA1%E5%80%8B%E5%9B%A0%E5%AD%90..jpg "(3)在（取出的因子的優先順位）<=（堆疊最上層的因子的優先順位） 之間，將stack[]的最 上層的因子取出存入polish[]內。 (4)將(2)取出的因子存至stack[]內. (5)將stack的剩餘因子取出後存至polish[]內.")
29
public void paint(Graphics g) {
char[] stack=new char[50], polish=new char[50]; int[] pri=new int[256]; // 優先順位表 int sp1,sp2; // 堆疊指標 int i; char[] p="a+b-c*d/e".toCharArray(); // 計算式 for (i=0;i<=255;i++) // 製作優先順位表 pri[i]=3; pri['+']=pri['-']=1;pri['*']=pri['/']=2; stack[0]=0;pri[0]=-1; // 衛兵 sp1=sp2=0; for (i=0;i<p.length;i++) { while (pri[p[i]]<=pri[stack[sp1]]) polish[++sp2]=stack[sp1--]; stack[++sp1]=p[i]; } for (i=sp1;i>0;i--) // 取出剩餘的堆疊 polish[++sp2]=stack[i]; for (i=1;i<=sp2;i++) g.drawString(""+polish[i],i*16,20);
30
練習問題38-1 括弧處理 括弧處理的原則如下： 直接將"("存至stack[]內
練習問題38-1 括弧處理 括弧處理的原則如下： 直接將"("存至stack[]內 在stack[]的最上層到達"(" 之前，")" 取出存在stack[]內的因子，然後將其存在polish[]內。堆疊上層的"("則予以捨棄。")並不儲存在stack[]內。
![練習問題38-1 括弧處理 括弧處理的原則如下： 直接將 ( 存至stack[]內](http://slidesplayer.com/slide/11742958/65/images/30/%E7%B7%B4%E7%BF%92%E5%95%8F%E9%A1%8C38-1+%E6%8B%AC%E5%BC%A7%E8%99%95%E7%90%86+%E6%8B%AC%E5%BC%A7%E8%99%95%E7%90%86%E7%9A%84%E5%8E%9F%E5%89%87%E5%A6%82%E4%B8%8B%EF%BC%9A+%E7%9B%B4%E6%8E%A5%E5%B0%87+%28+%E5%AD%98%E8%87%B3stack%5B%5D%E5%85%A7.jpg "練習問題38-1 括弧處理. 括弧處理的原則如下： 直接將 ( 存至stack[]內. 在stack[]的最上層到達 ( 之前， ) 取出存在stack[]內的因子，然後將其存在polish[]內。堆疊上層的 ( 則予以捨棄。 )並不儲存在stack[]內。")
31
………… char[] p="(a+b)*(c+d)".toCharArray(); // 計算式 for (i=0;i<=255;i++) // 運算元的優先順位 pri[i]=3; pri['+']=pri['-']=1;pri['*']=pri['/']=2; pri['(']=0; stack[0]=0;pri[0]=-1; // 衛兵 sp1=sp2=0; for (i=0;i<p.length;i++) { if (p[i]=='(') // (的處理 stack[++sp1]=p[i]; else if(p[i]==')') { // )的處理 while (stack[sp1]!='(') polish[++sp2]=stack[sp1--]; sp1--; } else { // 運算元與運算子的處理 while (pri[p[i]]<=pri[stack[sp1]]) for (i=sp1;i>0;i--) // 取出剩餘的堆疊 polish[++sp2]=stack[i]; for (i=1;i<=sp2;i++) // 逆向波蘭標記法的寫法 g.drawString(""+polish[i],i*16,20);
![………… char[] p= (a+b)*(c+d) .toCharArray(); // 計算式. for (i=0;i<=255;i++) // 運算元的優先順位. pri[i]=3;](http://slidesplayer.com/slide/11742958/65/images/31/%E2%80%A6%E2%80%A6%E2%80%A6%E2%80%A6+char%5B%5D+p%3D+%28a%2Bb%29%2A%28c%2Bd%29+.toCharArray%28%29%3B+%2F%2F+%E8%A8%88%E7%AE%97%E5%BC%8F.+for+%28i%3D0%3Bi%3C%3D255%3Bi%2B%2B%29+%2F%2F+%E9%81%8B%E7%AE%97%E5%85%83%E7%9A%84%E5%84%AA%E5%85%88%E9%A0%86%E4%BD%8D.+pri%5Bi%5D%3D3%3B.jpg "pri[ + ]=pri[ - ]=1;pri[ * ]=pri[ / ]=2; pri[ ( ]=0; stack[0]=0;pri[0]=-1; // 衛兵. sp1=sp2=0; for (i=0;i<p.length;i++) { if (p[i]== ( ) // (的處理. stack[++sp1]=p[i]; else if(p[i]== ) ) { // )的處理. while (stack[sp1]!= ( ) polish[++sp2]=stack[sp1--]; sp1--; } else { // 運算元與運算子的處理. while (pri[p[i]]<=pri[stack[sp1]]) for (i=sp1;i>0;i--) // 取出剩餘的堆疊. polish[++sp2]=stack[i]; for (i=1;i<=sp2;i++) // 逆向波蘭標記法的寫法. g.drawString( +polish[i],i*16,20);")
32
以更好的方法執行括弧處理 練習問題38-1將括弧的處理作業與其他因子分開處理，練習問題38-2則將括弧處理作業與其他因子一起處理，並使程式更精簡。 設"("的優先順位時會有下列問題： (1)若將"("的優先順位設為最低，則將其儲存在堆疊時，會從stack[]中取出因子。 (2)若將"("的優先順位設為最高，則從stack[]中取出因子的作業不會停在"("位置。 在練習問題38-1的從stack[]中取出因子的作業中，"("由於是與其他因子一起處理，因此其優先順位設為最低。正因為如此，就必須另外進行將"("儲存在stack[]內的處理作業。
![以更好的方法執行括弧處理 練習問題38-1將括弧的處理作業與其他因子分開處理，練習問題38-2則將括弧處理作業與其他因子一起處理，並使程式更精簡。 設 ( 的優先順位時會有下列問題： (1)若將 ( 的優先順位設為最低，則將其儲存在堆疊時，會從stack[]中取出因子。](http://slidesplayer.com/slide/11742958/65/images/32/%E4%BB%A5%E6%9B%B4%E5%A5%BD%E7%9A%84%E6%96%B9%E6%B3%95%E5%9F%B7%E8%A1%8C%E6%8B%AC%E5%BC%A7%E8%99%95%E7%90%86+%E7%B7%B4%E7%BF%92%E5%95%8F%E9%A1%8C38-1%E5%B0%87%E6%8B%AC%E5%BC%A7%E7%9A%84%E8%99%95%E7%90%86%E4%BD%9C%E6%A5%AD%E8%88%87%E5%85%B6%E4%BB%96%E5%9B%A0%E5%AD%90%E5%88%86%E9%96%8B%E8%99%95%E7%90%86%EF%BC%8C%E7%B7%B4%E7%BF%92%E5%95%8F%E9%A1%8C38-2%E5%89%87%E5%B0%87%E6%8B%AC%E5%BC%A7%E8%99%95%E7%90%86%E4%BD%9C%E6%A5%AD%E8%88%87%E5%85%B6%E4%BB%96%E5%9B%A0%E5%AD%90%E4%B8%80%E8%B5%B7%E8%99%95%E7%90%86%EF%BC%8C%E4%B8%A6%E4%BD%BF%E7%A8%8B%E5%BC%8F%E6%9B%B4%E7%B2%BE%E7%B0%A1%E3%80%82+%E8%A8%AD+%28+%E7%9A%84%E5%84%AA%E5%85%88%E9%A0%86%E4%BD%8D%E6%99%82%E6%9C%83%E6%9C%89%E4%B8%8B%E5%88%97%E5%95%8F%E9%A1%8C%EF%BC%9A+%281%29%E8%8B%A5%E5%B0%87+%28+%E7%9A%84%E5%84%AA%E5%85%88%E9%A0%86%E4%BD%8D%E8%A8%AD%E7%82%BA%E6%9C%80%E4%BD%8E%EF%BC%8C%E5%89%87%E5%B0%87%E5%85%B6%E5%84%B2%E5%AD%98%E5%9C%A8%E5%A0%86%E7%96%8A%E6%99%82%EF%BC%8C%E6%9C%83%E5%BE%9Estack%5B%5D%E4%B8%AD%E5%8F%96%E5%87%BA%E5%9B%A0%E5%AD%90%E3%80%82.jpg "(2)若將 ( 的優先順位設為最高，則從stack[]中取出因子的作業不會停在 ( 位置。 在練習問題38-1的從stack[]中取出因子的作業中， ( 由於是與其他因子一起處理，因此其優先順位設為最低。正因為如此，就必須另外進行將 ( 儲存在stack[]內的處理作業。")
33
練習問題38-2則使用下列的方法： ‧將“(”的優先順位設為最高，並不另外執行將其儲存在堆疊的處理作業。不過，當在進行取出因子作業時由於會穿越"("，因此須設下不執行取出作業的條件 ‧“)”也須設下優先順位，將“)”的優先順位設為最高後，在到達“)”以前，stack[]的內容將會全被取出。這項處理作業結束之後，到達堆疊開頭的")"就會被取出。 這時的優先順位表便成為： 因子 優先順位 ( ４ 運算元 ３ *、/ ２ +、- １ ) ０
34
………… char[] p="(a+b)*(c+d)".toCharArray(); // 計算式 for (i=0;i<=255;i++) // 運算元的優先順位 pri[i]=3; pri['+']=pri['-']=1;pri['*']=pri['/']=2; // 運算子的優先順位 pri['(']=4;pri[')']=0; stack[0]=0;pri[0]=-1; // 衛兵 sp1=sp2=0; for (i=0;i<p.length;i++) { while (pri[p[i]]<=pri[stack[sp1]] && stack[sp1]!='(') polish[++sp2]=stack[sp1--]; if (p[i]!=')') stack[++sp1]=p[i]; else sp1--; } for (i=sp1;i>0;i--) // 取出剩餘的堆疊 polish[++sp2]=stack[i]; for (i=1;i<=sp2;i++) // 逆向波蘭標記法表示 g.drawString(""+polish[i],i*16,20);
![………… char[] p= (a+b)*(c+d) .toCharArray(); // 計算式. for (i=0;i<=255;i++) // 運算元的優先順位. pri[i]=3;](http://slidesplayer.com/slide/11742958/65/images/34/%E2%80%A6%E2%80%A6%E2%80%A6%E2%80%A6+char%5B%5D+p%3D+%28a%2Bb%29%2A%28c%2Bd%29+.toCharArray%28%29%3B+%2F%2F+%E8%A8%88%E7%AE%97%E5%BC%8F.+for+%28i%3D0%3Bi%3C%3D255%3Bi%2B%2B%29+%2F%2F+%E9%81%8B%E7%AE%97%E5%85%83%E7%9A%84%E5%84%AA%E5%85%88%E9%A0%86%E4%BD%8D.+pri%5Bi%5D%3D3%3B.jpg "pri[ + ]=pri[ - ]=1;pri[ * ]=pri[ / ]=2; // 運算子的優先順位. pri[ ( ]=4;pri[ ) ]=0; stack[0]=0;pri[0]=-1; // 衛兵. sp1=sp2=0; for (i=0;i<p.length;i++) { while (pri[p[i]]<=pri[stack[sp1]] && stack[sp1]!= ( ) polish[++sp2]=stack[sp1--]; if (p[i]!= ) ) stack[++sp1]=p[i]; else. sp1--; } for (i=sp1;i>0;i--) // 取出剩餘的堆疊. polish[++sp2]=stack[i]; for (i=1;i<=sp2;i++) // 逆向波蘭標記法表示. g.drawString( +polish[i],i*16,20);")
35
5-8 語法解析 例題39 逆向波蘭標記法計算式的語法解析 將(6+2)/(6-2)+4計算式施以語法解析(parse)後，再求其值
5-8 語法解析 例題39 逆向波蘭標記法計算式的語法解析 將(6+2)/(6-2)+4計算式施以語法解析(parse)後，再求其值 計算式的運算元設為'0'～'9'之間的1個常數字元。 以例題38、練習問題38的方法將計算式改以逆向波蘭標記法書寫，然後將其儲存在polish[]內。 接下來以下列的原則進行計算，運算元與計算結果儲存在堆疊v[]內，最後剩下的v[1]的值即為此計算式的答案。 (1)在polish[]為空以前反覆執行以下步驟 (2)從polish[]取出1個因子 (3)因子若為運算元（'0'～'9'），則將其儲存在v[]內。 (4)因子若為運算子（+、-、*、/），則將堆疊的頂端（v[sp1]）與其下面（v[sp1-1]）按運算子(ope)加以以下列方 式計算，然後將結果儲存在v[sp1-1]。 v[sp1-1]=v[sp1-1] ope v[sp1]
36
具體範例如下：
37
public void paint(Graphics g) {
char[] stack=new char[50], polish=new char[50]; int[] pri=new int[256]; // 優先順位表 double[] v=new double[50]; int sp1,sp2; // 堆疊指標 int i; String exp="(6+3)/(6-2)+3*2^3-1"; // 計算式 char[] p=exp.toCharArray(); for (i=0;i<=255;i++) pri[i]=4; pri['+']=pri['-']=1;pri['*']=pri['/']=2;pri['^']=3; pri['(']=5;pri[')']=0; stack[0]=0;pri[0]=-1; // 衛兵 sp1=sp2=0; for (i=0;i<p.length;i++) { while (pri[p[i]]<=pri[stack[sp1]] && stack[sp1]!='(') polish[++sp2]=stack[sp1--]; if (p[i]!=')') stack[++sp1]=p[i]; else sp1--; }
38
……………… for (i=sp1;i>0;i--) // 取出剩餘的堆疊 polish[++sp2]=stack[i]; sp1=0; // 計算 for (i=1;i<=sp2;i++) { if ('0'<=polish[i] && polish[i]<='9') v[++sp1]=polish[i]-'0'; else { switch (polish[i]) { case '+':v[sp1-1]=v[sp1-1]+v[sp1];break; case '-':v[sp1-1]=v[sp1-1]-v[sp1];break; case '*':v[sp1-1]=v[sp1-1]*v[sp1];break; case '/':v[sp1-1]=v[sp1-1]/v[sp1];break; case '^':v[sp1-1]=Math.pow(v[sp1-1],v[sp1]);break; } sp1--; g.drawString(exp+"="+v[1],10,20);
![……………… for (i=sp1;i>0;i--) // 取出剩餘的堆疊. polish[++sp2]=stack[i]; sp1=0; // 計算.](http://slidesplayer.com/slide/11742958/65/images/38/%E2%80%A6%E2%80%A6%E2%80%A6%E2%80%A6%E2%80%A6%E2%80%A6+for+%28i%3Dsp1%3Bi%3E0%3Bi--%29+%2F%2F+%E5%8F%96%E5%87%BA%E5%89%A9%E9%A4%98%E7%9A%84%E5%A0%86%E7%96%8A.+polish%5B%2B%2Bsp2%5D%3Dstack%5Bi%5D%3B+sp1%3D0%3B+%2F%2F+%E8%A8%88%E7%AE%97..jpg "for (i=1;i<=sp2;i++) { if ( 0 <=polish[i] && polish[i]<= 9 ) v[++sp1]=polish[i]- 0 ; else { switch (polish[i]) { case + :v[sp1-1]=v[sp1-1]+v[sp1];break; case - :v[sp1-1]=v[sp1-1]-v[sp1];break; case * :v[sp1-1]=v[sp1-1]*v[sp1];break; case / :v[sp1-1]=v[sp1-1]/v[sp1];break; case ^ :v[sp1-1]=Math.pow(v[sp1-1],v[sp1]);break; } sp1--; g.drawString(exp+ = +v[1],10,20);")
39
練習問題39 直接法 使用計算用的堆疊v[]與運算子用的堆疊ope[]按下列步驟評估計算式。 (1)由計算式取出1個因子，進行以下步驟：
練習問題39 直接法 使用計算用的堆疊v[]與運算子用的堆疊ope[]按下列步驟評估計算式。 (1)由計算式取出1個因子，進行以下步驟： (2)若因子為運算元（常數：'0'～'9'），則將其儲存在v[]內。 (3)若不是運算元（而是運算子），則適用例題39的規則。不過例題39是在是執行stack[]→polish[]的資料移動，本練習問題則以執行名為calc的「運算處理」來代替。 (4)取出ope[]中的剩餘的運算子並進行「運算處理」。
![練習問題39 直接法 使用計算用的堆疊v[]與運算子用的堆疊ope[]按下列步驟評估計算式。 (1)由計算式取出1個因子，進行以下步驟：](http://slidesplayer.com/slide/11742958/65/images/39/%E7%B7%B4%E7%BF%92%E5%95%8F%E9%A1%8C39+%E7%9B%B4%E6%8E%A5%E6%B3%95+%E4%BD%BF%E7%94%A8%E8%A8%88%E7%AE%97%E7%94%A8%E7%9A%84%E5%A0%86%E7%96%8Av%5B%5D%E8%88%87%E9%81%8B%E7%AE%97%E5%AD%90%E7%94%A8%E7%9A%84%E5%A0%86%E7%96%8Aope%5B%5D%E6%8C%89%E4%B8%8B%E5%88%97%E6%AD%A5%E9%A9%9F%E8%A9%95%E4%BC%B0%E8%A8%88%E7%AE%97%E5%BC%8F%E3%80%82+%281%29%E7%94%B1%E8%A8%88%E7%AE%97%E5%BC%8F%E5%8F%96%E5%87%BA1%E5%80%8B%E5%9B%A0%E5%AD%90%EF%BC%8C%E9%80%B2%E8%A1%8C%E4%BB%A5%E4%B8%8B%E6%AD%A5%E9%A9%9F%EF%BC%9A.jpg "練習問題39 直接法. 使用計算用的堆疊v[]與運算子用的堆疊ope[]按下列步驟評估計算式。 (1)由計算式取出1個因子，進行以下步驟： (2)若因子為運算元（常數： 0 ～ 9 ），則將其儲存在v[]內。 (3)若不是運算元（而是運算子），則適用例題39的規則。不過例題39是在是執行stack[]→polish[]的資料移動，本練習問題則以執行名為calc的「運算處理」來代替。 (4)取出ope[]中的剩餘的運算子並進行「運算處理」。")
40
void calc() { // 運算處理 switch (ope[sp1]) { case '|' : v[sp2-1]=(v[sp2-1]+v[sp2])/2;break; case '>' : v[sp2-1]=Math.max(v[sp2-1],v[sp2]);break; case '<' : v[sp2-1]=Math.min(v[sp2-1],v[sp2]);break; } sp2--;sp1--; public void paint(Graphics g) { int i; String exp="(1>2|2<8|3<4)|(9<2)"; // 計算式 char[] p=exp.toCharArray(); for (i=0;i<=255;i++) pri[i]=4; pri['|']=1;pri['<']=pri['>']=2; pri['(']=3;pri[')']=0; ope[0]=0;pri[0]=-1; // 衛兵 sp1=sp2=0; for (i=0;i<exp.length();i++) { if ('0'<=p[i] && p[i]<='9') v[++sp2]=p[i]-'0'; else { while (pri[p[i]]<=pri[ope[sp1]] && ope[sp1]!='(') calc(); if (p[i]!=')') ope[++sp1]=p[i]; else sp1--; // 將(去除 while (sp1>0) // 直到運算子堆疊成為空的 g.drawString(exp+"="+v[1],0,20);
![void calc() { // 運算處理 switch (ope[sp1]) { case | : v[sp2-1]=(v[sp2-1]+v[sp2])/2;break; case > : v[sp2-1]=Math.max(v[sp2-1],v[sp2]);break;](http://slidesplayer.com/slide/11742958/65/images/40/void+calc%28%29+%7B+%2F%2F+%E9%81%8B%E7%AE%97%E8%99%95%E7%90%86+switch+%28ope%5Bsp1%5D%29+%7B+case+%7C+%3A+v%5Bsp2-1%5D%3D%28v%5Bsp2-1%5D%2Bv%5Bsp2%5D%29%2F2%3Bbreak%3B+case+%3E+%3A+v%5Bsp2-1%5D%3DMath.max%28v%5Bsp2-1%5D%2Cv%5Bsp2%5D%29%3Bbreak%3B.jpg "case < : v[sp2-1]=Math.min(v[sp2-1],v[sp2]);break; } sp2--;sp1--; public void paint(Graphics g) { int i; String exp= (1>2|2<8|3<4)|(9<2) ; // 計算式. char[] p=exp.toCharArray(); for (i=0;i<=255;i++) pri[i]=4; pri[ | ]=1;pri[ < ]=pri[ > ]=2; pri[ ( ]=3;pri[ ) ]=0; ope[0]=0;pri[0]=-1; // 衛兵. sp1=sp2=0; for (i=0;i<exp.length();i++) { if ( 0 <=p[i] && p[i]<= 9 ) v[++sp2]=p[i]- 0 ; else { while (pri[p[i]]<=pri[ope[sp1]] && ope[sp1]!= ( ) calc(); if (p[i]!= ) ) ope[++sp1]=p[i]; else. sp1--; // 將(去除. while (sp1>0) // 直到運算子堆疊成為空的. g.drawString(exp+ = +v[1],0,20);")
41
5-9 自我重組搜尋 逐筆搜尋由於是由開頭開始搜尋1筆筆的資料，因此搜尋到排列在尾端的資料時，會花費一段時間。
5-9 自我重組搜尋 逐筆搜尋由於是由開頭開始搜尋1筆筆的資料，因此搜尋到排列在尾端的資料時，會花費一段時間。 一般而言，一度被使用過的資料很有可能再度被使用，，因此在搜尋資料的過程中，如將已搜尋過的資料移到開頭，則使用頻率較高的資料自然就移到前方，這種方法稱為自我重組搜尋(self re-organizing search)。 由於自我重組搜尋(self re-organizing search)是在搜尋資料以便插入‧刪除資料時進行的，因此可以以串列形式表現出來。 資料的重整方法如下： ‧欲搜尋的資料移至開頭 ‧將欲搜尋的資料向前移一位
42
將欲搜尋的資料移至開頭的方法如下：
43
bt2.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) { int p; p=head;old=head; while (p!=NIL) { // 搜尋 if (a[p].name.equals(tf3.getText())) { if (p!=head) { // 移至開頭 a[old].ptr=a[p].ptr;a[p].ptr=head;head=p; } ta.setText(""); p=head; while (p!=NIL) { // 顯示串列 ta.setText(ta.getText()+a[p].name+","+a[p].tel+"\n"); p=a[p].ptr; break; old=p; });
44
自我重組搜尋（移至前1位） 將搜尋過的資料移至前1位
為了修改前2個節點的指標部分，程式使用了old1、old2等2個指標。為此，程式將虛擬節點置於串列開頭，將a[1]設為虛擬節點。
45
bt2.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) { int p,q; p=a[head].ptr;old1=old2=head; while (p!=NIL) { // 搜尋 if (a[p].name.equals(tf3.getText())) { if (p!=a[head].ptr) { // 若不在開頭時則與前1筆資料交換 q=a[old1].ptr;a[old1].ptr=p; a[old2].ptr=a[p].ptr;a[p].ptr=q; } ta.setText(""); p=a[head].ptr; while (p!=NIL) { // 顯示串列 ta.setText(ta.getText()+a[p].name+","+a[p].tel+"\n"); p=a[p].ptr; break; old1=old2;old2=p; });
46
5-10 串列Hash法 例題41 鏈結法 將由hash法所管理的資料以串列組織起來
第3章3-8是將資料直接存入至hash表內，這種方法稱為開放位址(open addressing)法。相對的，以串列將具有相同hash值的資料（互相衝突的資料）連結起來，並將指向串列開頭的指標儲存至hash表的方法則稱為鏈結(chaining)法。使用這項方法，可輕易且無限制的將衝突所產生時的資料新增起來。 以下為將衝突所產生的資料新增至串列開頭的範例：
47
int hash(String s) { // hash函數
int n,ModSize=1000; n=s.length(); return (s.charAt(0)-'A'+(s.charAt(n/2-1)-'A')*26 +(s.charAt(n-2)-'A')*26*26)%ModSize; } ………………… bt1.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { int n=hash(tf1.getText()); // hashing if (0<=n && n<TableSize) { // 新增至開頭 a[pt]=new Girl(tf1.getText(),tf2.getText(),Table[n]); Table[n]=pt++; if (pt>Max) { tf1.setText("空間已滿"); return; ………… bt2.addActionListener(new ActionListener() { int p,n=hash(tf3.getText()); if (0<=n && n<TableSize) { p=Table[n]; while (p!=NIL) { if (a[p].name.equals(tf3.getText())) ta.setText(ta.getText()+a[p].name+","+a[p].tel+"\n"); p=a[p].ptr; ………
48
鏈結法（新增至尾端） 搜尋至資料的結尾處，然後將資料新增至此位置。 必須將資料為空及不空的情形分開處理。
49
………………… bt1.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { int q,n=hash(tf1.getText()); // hashing if (0<=n && n<TableSize) { a[pt]=new Girl(tf1.getText(),tf2.getText(),NIL); if (Table[n]==NIL) Table[n]=pt; else { // 衝突時新增至尾端 q=Table[n]; while (a[q].ptr!=NIL) q=a[q].ptr; a[q].ptr=pt; } pt++; if (pt>Max) { tf1.setText("空間已滿"); return; }); ………………………………
Similar presentations
