【資料結構】堆疊

2016-12-07 陳富國Leave a Comment

堆疊(Stack)是一種後進先出(Last In First Out, LIFO)的有序串列，亦即資料處理的方式都是在同一邊進行，也就是由相同的一端來進行插入與刪除動作。而我們日常生活中，也有一些是堆疊的例子，例如堆盤子、書本裝箱…等，都是一層一層的堆上去，如果想要取出箱子中某一本書，也只能從最上面開始取出。

【定義】

1.一群相同性質元素的組合，即有序串列(ordered List) 。

2.具有後進先出 (Last In First Out, LIFO) 的特性。

3.將一個項目放入堆疊的頂端，這個動作稱為Push(加入)。

4.從堆疊頂端拿走一個項目，這個動作稱為Pop(取出)。

5.Push/Pop的動作皆發生在同一端，則稱此端為Top(頂端)。

6.要取出資料時，則只能從Top(頂端)取出，不能從中間取出資料。

【堆疊的操作示範】

【堆疊常用的操作】

Push ：加入新項目到堆疊的頂端。
Pop ：取出堆疊頂端一個項目。
TopItem ：查看堆疊頂端的項目內容。
IsEmpty ：判斷堆疊是否為空，若為空則傳回真(True)，否則傳回假(False)。
IsFull ：判斷堆疊是否為滿，若為滿則傳回真(True)，否則傳回假(False)。

【C#-Stack類別】

Stack.Push 方法 (Object)

using System;
using System.Collections; //C#的Stack所在的命名空間
public class SamplesStack
{

    public static void Main()
    {

        // Creates and initializes a new Stack. 建立並初始化一個新的堆疊
        Stack myStack = new Stack();
        myStack.Push("The");
        myStack.Push("quick");
        myStack.Push("brown");
        myStack.Push("fox");

        // Displays the Stack. //印出堆疊內容
        Console.Write("堆疊元素：:");
        PrintValues(myStack, '\t'); //呼叫下方PrintValues方法

        // Removes an element from the Stack. 從堆疊裏移除一個元素
        Console.WriteLine("(Pop)\t\t{0}", myStack.Pop());

        // Displays the Stack. 印出堆疊內容
        Console.Write("堆疊元素：:");
        PrintValues(myStack, '\t');

        // Removes another element from the Stack. 從堆疊裏移除另一個元素
        Console.WriteLine("(Pop)\t\t{0}", myStack.Pop());

        // Displays the Stack. 印出堆疊內容
        Console.Write("堆疊元素：:");
        PrintValues(myStack, '\t');

        // Views the first element in the Stack but does not remove it.
        //檢視堆疊裏的第一個元素，但不移除該元素，注意動作與pop不同
        Console.WriteLine("(Peek)\t\t{0}", myStack.Peek());

        // Displays the Stack.
        Console.Write("堆疊元素：:");
        PrintValues(myStack, '\t');
    }


    public static void PrintValues(IEnumerable myCollection, char mySeparator)
    {
        foreach (Object obj in myCollection) //對每一個在myCollection集合裏的物件obj
            Console.Write("{0}{1}", mySeparator, obj);
        Console.WriteLine();
    }

}


/* 
程式輸出：
堆疊元素：:     fox     brown   quick   The
(Pop)           fox
堆疊元素：:     brown   quick   The
(Pop)           brown
堆疊元素：:     quick   The
(Peek)          quick
堆疊元素：:     quick   The
請按任意鍵繼續 . . .
*/

【堆疊在運算式上的應用】

在日常生活中，我們所使用的四則運算都屬於中序(infix order)運算式，亦即運算子位於兩個運算元之間的表示法。但是，此種表示法電腦並無法直接的處理，因為中序式可能會含有括號，並且運算子可能有不同的優先順序權。因此，若要使用電腦來處理運算式時，則必須要先將「中序式」轉換成「後序式」(postfix order)。

算術式表示的方式有三種：

中序(Infix)表示法： A+B
前序(prefix)表示法： +AB
後序(postfix)表示法： AB-

【中序(Infix)表示法】

【定義】數學上的表示方式，就是屬於中序式，它是把運算子放在兩個運算元的中間。

【表示式】<運算元1 > <運算子> <運算元2 >

【例如】A+B。

【缺點】電腦無法一次依序讀取運算式，因運算式可能含有括號，且未定義運算子優先順序。

【前序 (prefix)表示法】

【定義】指將中序表示法中的運算子和運算元重新調整順序，只是運算子的順序是在運算元前面。

【表示式】<運算子> <運算元1 > <運算元2 >

【例如】+AB。

【後序 (postfix)表示法】

【定義】後序表示法和前序表示法相類似，使得運算子放於運算元後面的表示法。

【表示式】<運算元1 > <運算元2 > <運算子>

【例如】AB+。

【優點】不必使用括號，方便電腦使用。

【運算式的轉換】

大部份的運算式(expression)都是由運算元(operand)與運算子(operator)所組成。

【例如】A*B+(C/D)-E 其中： A,B,C,D,E為運算元(operand)， +,-,*,/為運算子(operator)

【運算原則】

括號內先處理
優先權較高的運算子先執行
同優先權者，則由結合性，來決定是由左而右，還是由右而左執行。

【中序式→前序式】

假設有一個中序式為：A×B+C×D，欲轉換成前序式，其步驟如下：

1.先用括號將優先順序分出來

((A×B)＋(C×D))

2.將運算子移到左括號右邊

((×AB)＋(×CD))

(＋(×AB)(×CD))

3.把括弧全部拿掉，即為所得。

＋×AB×CD

【中序式→後序式】

假設有一個中序式為：A×B+C×D，欲轉換成後序式，其步驟如下：

1.先用括號將優先順序分出來

((A×B)＋(C×D))

2.將運算子移到右括號左邊

((AB×)＋(CD×))

((AB×)(CD×)＋)

3.把括弧全部拿掉，即為所得。

AB×CD×＋

練習：

1. A+B*C-D/E

Ans: 依優先順序括上括弧

(A+(B*C))-(D/E))

後序式係將運算子移到右括號左邊

(A(BC*)+)(DE/)-)

去掉括弧：

**ABC*+DE/-**

2. (A+B)*C/(D-E/F)

Ans: 依優先順序括上括弧

(((A+B)*C)/(D-(E/F)))

後序式係將運算子移到右括號左邊

(((AB+)C*)(D(EF/)-)/)

去掉括弧：

AB+C*DEF/-/

後序式求解：

設A=1, B=2, C=3, D=4, E=5, F=2，求下面後序式的值為何？

1．AB*C-DE**

=(((AB*)C-)(DE*)*)

=(((A*B)-C)*(D*E))

=(((1*2)-3)*(4*5))

=-20

2．ABC*+DE/-

=((A(BC*)+)(DE/)-)

=((A+(B*C))-(D/E))

=((1+(2*3))-(4/5))

=1+6-0.8

=6.2

3．AB+C*DEF/-/

=(((AB+)C*)(D(EF/)-)/)

=(((A+B)*C)/(D-(E/F)))

=(((1+2)*3)/(4-(5/2)))

=3*3/(4-2.5)

=9/1.5

以上方法是我們人員用來進行的中序轉後序/前序的快速方法，應付考試相當快捷，但是，若要用程式來實現轉換方法，需要特定的資料結構來協助，一般來說有二種作法：堆疊與二元樹。

考試時，一般不會考程式，所以不用特別注意堆疊的演算法，大家要記得的是去括弧法與二元樹法。(考試必考！)

【C# – 中序到後序的轉換程式】

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace Infix
{
   class Program
   {
 
      static bool InfixToPostfixConvert(ref string infixBuffer, out string postfixBuffer)
      {
         int priority = 0;
         postfixBuffer = "";
 
         Stack<Char> s1 = new Stack<char>();
 
         for (int i = 0; i < infixBuffer.Length; i++)
         {
            char ch = infixBuffer[i];
            if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
            {
               // check the precedence
               if (s1.Count <= 0)
                  s1.Push(ch);
               else
               {
                  if (s1.Peek() == '*' || s1.Peek() == '/')
                     priority = 1;
                  else
                     priority = 0;
                  if (priority == 1)
                  {
                     if (ch == '+' || ch == '-')
                     {
                        postfixBuffer += s1.Pop();
                        i--;
                     }
                     else
                     { // Same
                        postfixBuffer += s1.Pop();
                        i--;
                     }
                  }
                  else
                  {
                     if (ch == '+' || ch == '-')
                     {
                        postfixBuffer += s1.Pop();
                        s1.Push(ch);
                     }
                     else
                        s1.Push(ch);
                  }
               }
            }
            else
            {
               postfixBuffer += ch;
            }
         }
         int len = s1.Count;
         for (int j = 0; j < len; j++)
            postfixBuffer += s1.Pop();
         return true;
      }
 
      static void Main(string[] args)
      {
         string infixBuffer = "";
         string postfixBuffer = "";
 
         if (args.Length == 1)
         {
            infixBuffer = args[0];
           
            InfixToPostfixConvert(ref infixBuffer, out postfixBuffer);
            System.Console.WriteLine("InFix  :\t" + infixBuffer);
            System.Console.WriteLine("PostFix:\t" + postfixBuffer);
         }
         else
         {
            infixBuffer = "a+b*c";
 
            InfixToPostfixConvert(ref infixBuffer, out postfixBuffer);
            System.Console.WriteLine("InFix  :\t" + infixBuffer);
            System.Console.WriteLine("PostFix:\t" + postfixBuffer);
            System.Console.WriteLine();
           
            infixBuffer = "a+b*c/d-e";
            InfixToPostfixConvert(ref infixBuffer, out postfixBuffer);
            System.Console.WriteLine("InFix  :\t" + infixBuffer);
            System.Console.WriteLine("PostFix:\t" + postfixBuffer);
            System.Console.WriteLine();
           
            infixBuffer = "a+b*c/d-e+f*h/i+j-k";
            InfixToPostfixConvert(ref infixBuffer, out postfixBuffer);
            System.Console.WriteLine("InFix  :\t" + infixBuffer);
            System.Console.WriteLine("PostFix:\t" + postfixBuffer);
            System.Console.WriteLine();
         }        
      }
   }
}

/* 程式輸出
中序  : a+b*c
後序:   abc*+

中序  : a+b*c/d-e
後序:   abc*d/+e-

中序  : a+b*c/d-e+f*h/i+j-k
後序:   abc*d/+e-fh*i/+j+k-

請按任意鍵繼續 . . .

*/

陣列的排序

Array.Sort() 方法
可用來對指定的一維陣列物件由小而大做遞增排序。
語法1：將一維陣列物件中的元素做由小到大排序：將一維陣列物件中的元素做由小到大排序
Array.Sort(陣列物件);
語法2：
用來將陣列物件1 中的元素做由小到大排序，
且陣列物件2 的元素會隨著陣列物件1 的
索引位置跟著做排序的動作。
Array.Sort(陣列物件1, 陣列物件2);

陣列的反轉

Array.Reverse() 方法
用來反轉整個一維陣列的順序。
上例用Array.Sort() 方法對指定陣列由小而大遞增排序。
若希望改由大而小作遞減排序，需再將已做完遞增排序
的陣列再用 Array.Reverse() 方法即可將陣列由大而小
作遞減排序。
Array.Reverse() 語法：
Array.Reverse(陣列物件);

[例] 欲對陣列名稱avg做由大而小遞減排序，寫法：
Array.Sort(avg);
Array.Reverse(avg);
若同時有兩個相關陣列 name 和 avg，若以 avg 陣列
為基準由大而小做遞減排序，相關陣列需要同時，相關陣列需要同時反轉，
寫法：
Array.Sort(avg,name);
Array.Reverse(avg);
Array.Reverse(name);

陣列的搜尋

.NET Framework 類別程式庫的 Array 類別提供
1. Array.IndexOf()方法
2. Array. BinarySearch() 方法
用來搜尋某個資料是否在陣列物件中。
1. Array.IndexOf()方法
使用 Array.IndexOf 可用來搜尋陣列中是否有相符
資料。
若有找到，則會傳回該陣列元素的註標值。
若沒有找到，會傳回-1。
語法：
Array.IndexOf(陣列名稱 ,查詢資料 [ ,起始註標] [ ,查詢距離] );

[例] 假設字串陣列 name 中有
{“Jack”,”Tom”,”Fred”,”Mary”,”Lucy”, “Jane” }
共六個陣列元素，觀察下列各陳述式輸出結果：
Array.IndexOf(name,”Tom”);
[結果] 由註標0開始找起，傳回值為1。
Array.IndexOf(name, ”Tom”, 3) ;
[結果] 由註標3開始找起，傳回值為-1。
若str1=”Lucy” , start=1, offset=2
Array.IndexOf(name, str1, start, offset);
[結果] 由註標1開始往下找2個陣列元素的內容是否
有 ”Lucy” 字串。傳回值為-1。

2. Array.BinarySearch()方法
– 用來搜尋陣列中的資料，陣列未經排序，陣列未經排序，每次
搜尋資料都由最前面開始，資料量大時，愈後
面的資料查詢所花費的時間愈多，資料平均搜
尋時間不平均。
– 為不管資料前後次序，使得資料平均搜尋時間都
差不多，在 .NET Framework 類別程式庫另提供
此二分化搜尋方法來搜尋資料是否在陣列中。
– 此方法使用前陣列才可使用
適用於資料量大的陣列。
語法：Array.BinarySearch(陣列名稱, 查詢資料);

陣列的拷貝

將某個陣列複製給另一個陣列時，可用 Array.Copy()
方法進行拷貝陣列。
語法：
Array.Copy (srcAry , srcIndex , dstAry , dstIndex , length );
srcAry ：來源陣列即被拷貝的陣列。
srcIndex：代表 srcAry 來源陣列的註標，由指定的註標開始複製。
dstAry ：接收資料的目的陣列。
dstIndex：代表 dstAry 目的陣列的註標，由指定的註標開始儲存。
length ：表示要複製的陣列元素個數。

陣列的清除

當需要將某個陣列中指定範圍內的陣列元素的內容
清除，可透過 Array.Clear() 方法。語法：
Array.Clear(aryname, startindex, length);
【例1】將 myary 陣列中，註標為 3~4 陣列元素的內容
清除，寫法：
Array.Clear(myary, 3, 2);
【例2】將 myary 陣列中所有陣列元素的內容清除，
假設該陣列共有六個陣列元素。寫法：
Array.Clear(myary, 0, 6);

【資料結構】陣列

2016-11-17 陳富國Leave a Comment

陣列的觀念

【定義】陣列是指一群具有相同名稱及資料型態的變數之集合。

【特性】

佔用連續記憶體空間。
用來表示有序串列之一種方式。
各元素的資料型態皆相同。
支援隨機存取(Random Access)與循序存取(Sequential Access)。
插入或刪除元素時較為麻煩。因為須挪移其他元素。

【優點】

(1)利用註標（Index）可以快速的輸入資料。

輸入：for(i=0;i<5;i++) //利用「迴圈結構」

A[i]=i*2+1; //快速「輸入資料」到「陣列」中

(2) 利用註標（Index）一次可以輸出大批的資料。

輸出：for(i=0;i<5;i++) //利用「迴圈結構」

WriteLine(A[i]); //從「陣列」一次「輸出大批」的資料

【定義】宣告陣列時，其括弧內的「註標」個數，只有一個時稱為「一維陣列」。在一維陣列中，常使用的運算指令有五種。

讀取(Read)
寫入(Write)
插入(Insert)
刪除(Delete)
複製(Copy)

讀取(Read)

【定義】利用註標（Index）來「讀取」資料。

【例如】將A陣列的第二個元素放到X目的變數中。

【寫法】X= A[1]; //陣列的註標是從0開始

【圖解】

%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b-%e9%99%a3%e5%88%97-1

寫入(Write)

【定義】利用註標（Index）來「寫入」資料。

【例如】將數值50寫入到陣列的第二個索引位置中。

【寫法】A[1]=50; //陣列的註標是從0開始

【圖解】
%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b-%e9%99%a3%e5%88%97-2

插入(Insert)

【定義】在指定的註標 i 的位置插入一項新元素，原來註標 i 和之後的元素都必須要再往後挪移一個位置。

【例如】將在註標1的位置插入一項新元素(15)。

【演算法】

Procedure ArrayInsert(int A[],int Max,int i ,int value)  
Begin
  If(i>0 && i<=Max)  //判斷欲插入位置i是否存在，如果有，則
{
  for(count=Max-1;count>i;count--)   //i位置及後面的元素逐一往後挪
    A[count]=A[count-1];
  A[i]=value;                        //最後再將新元素插入到第i位置
}
   Else                              //如果欲插入位置i不存在，則
     Return 0;                      //傳回0
End
End Procedure

【圖解】

【說明】

首先將30往後挪移一個位置，再將A[1]的元素20，往後挪移放到A[2]位置中，最後再插入15到A[1]中。

刪除(Delete)

【定義】指刪除指定的註標 i 位置的元素，原來註標 i的元素被刪除，為了避免浪費記憶體空間，因此，之後的元素都必須要再往前挪一個位置。

【例如】將在註標1的位置刪除一項舊元素(20)。

【演算法】

Procedure ArrayDelete(int A[],int Max,int i)  
Begin
  If(i>0 && i<=Max)                                       //判斷欲刪除元素位置i是否存在，如果有，則
  {
    for(count=i;count<Max-1;count++)     //i位置後面的元素逐一往前挪
    A[count]=A[count+1];
    A[Max-1]=0;                                           //最後再將0放到最後一個位置
  }
   Else                                                             //如果欲插入位置i不存在，則
     Return 0;                                                   //傳回0
End
End Procedure

【圖解】

%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b-%e9%99%a3%e5%88%97-4

【說明】首先將A[1]的元素20刪除，再將A[2]的元素30往前挪移一個位置，最後再寫入0到A[2]中。

複製(Copy)

【定義】指將「來源陣列」的元素內含值全部逐一copy到「目的陣列」。

【例如】將A陣列的元素內含值全部逐一copy到B陣列中。

【演算法】

Procedure ArrayCopy(int A[],int B[], int Max)  
Begin
  If(Max>0)                                                    //判斷陣列是否有元素內含值，如果有，則
{
  for(count=0;count<Max-1;count++)    //A陣列全部逐一copy到B陣列
    B[count]=A[count];
}
   Else                                                             //如果陣列沒有元素，則
     Return 0;                                                   //傳回0
End
End Procedure

【圖解】

%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b-%e9%99%a3%e5%88%97-5

【說明】

A陣列的元素內含值全部逐一copy到B陣列中，例如A[0]元素會被copy到B[0]中，A[1]元素放到B[1]中，以此類推。

陣列的宣告

(1) 變數宣告

int A, B, C; //宣告三個變數(A,B,C)為整數型態

以上三個變數與變數之間都是個別獨立的記憶體空間。

(2) 陣列宣告

int A[3]; //宣告一維陣列A，共有A[0]、A[1]、A[2]三個元素

以上三個記憶體空間，可以讓我們連續儲存多項資料，並且資料與資料之間都是按照順序排列的記憶體空間。

【堆疊的操作示範】

【堆疊常用的操作】

【C#-Stack類別】

【堆疊在運算式上的應用】

算術式表示的方式有三種：

【中序(Infix)表示法】

【前序 (prefix)表示法】

【後序 (postfix)表示法】

【運算式的轉換】

【運算原則】

【中序式→前序式】

【中序式→後序式】

練習：

ABC*+DE/-

AB+C*DEF/-/

後序式求解：

1．AB*C-DE**

2．ABC*+DE/-

3．AB+C*DEF/-/

以上方法是我們人員用來進行的中序轉後序/前序的快速方法，應付考試相當快捷，但是，若要用程式來實現轉換方法，需要特定的資料結構來協助，一般來說有二種作法：堆疊與二元樹。

【C# – 中序到後序的轉換程式】

陣列的排序

陣列的反轉

陣列的搜尋

陣列的拷貝

陣列的清除

陣列的觀念

【定義】陣列是指一群具有相同名稱及資料型態的變數之集合。

【特性】

【優點】

【定義】宣告陣列時，其括弧內的「註標」個數，只有一個時稱為「一維陣列」。在一維陣列中，常使用的運算指令有五種。

讀取(Read)

寫入(Write)

插入(Insert)

【圖解】 【說明】

刪除(Delete)

複製(Copy)

陣列的宣告

(1) 變數宣告

(2) 陣列宣告

陣列的儲存方式

二維陣列的觀念

多維陣列的觀念

陣列在記憶體中的表示法

Ⅰ. 一維陣列

二維陣列

Row-major(以列為主)

Column-major(以行為主)

矩陣(Matrices)

矩陣轉置(Matrix Transposition)

矩陣相加(Matrix Addition)

矩陣相乘(Matrix Multiplication)

稀疏矩陣(Sparse Matrix)

【2-3 二維陣列的觀念，以下不在期中考的範圍內】

台電 – 電價表

**ABC*+DE/-**

【圖解】

【說明】