返回 IB 計算機科學

抽象資料結構和演算法

基礎

靜態資料結構

您應該能夠在任何 Java 編輯器中編譯這些示例，例如 BlueJ 或 JCreator。所有示例都假設 IBIO 方法存在於檔案中。

可以使用這些方法的示例類在這裡找到。如果您想實現這些頁面中給出的任何示例，請確保您能夠編譯並執行此原始碼。

您要嘗試的任何程式碼都應放在建構函式中

/**

Adams 類物件的建構函式
/

public Adams() {

    // valid Java or JETS statements may be placed here...
    output("The answer is: " + d);

}

您可能想要更改類名，在這種情況下，請記住

   the file name must be the same as the class name with the extension .java
   the constructor name must be the same as the class name.
   you ought to change the comments to reflect what your program does.

陣列中的堆疊

將使用陣列來儲存一系列字元

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11] stack

最初，指標 size 設定為 0，因此 stack[size] 是下一個可用元素。要將專案推入堆疊，我們可以透過兩種方式之一進行操作

   Allocate the item to stack[size] then move size up one in the array
   Allocate the item to stack[0] and increment size by 1

很明顯，第二個選項涉及向上移動元素，而第一個選項只需要移動堆疊指標。

鑑於

  private static final int SIZE = 12;      // a constant for the stack size
  private char[] stack = new char[SIZE];  // the array to hold the stack
  private int size = 0;                   // the number of items in the stack

可能的 push 操作是

 // method to push an item onto the stack
  public void push(char item)
  {      
    stack[size] = item;
    size = size + 1;
  }

它可以執行到一定程度。需要進行任何檢查嗎？新增它。

到目前為止，程式碼可能如下所示

/**

堆疊類
實現字元堆疊
使用陣列 - 是靜態資料結構
/

public class Stack {

  private static final int SIZE = 12;      // a constant for the stack size
  private char[] stack = new char[SIZE];   // the array to hold the stack
  private int size = 0;                    // the number of items in the stack

  // Constructor
  public Stack()
  {
    size = 0;
    char c;
    do
    {
      c = inputChar("Input a character ('/' to end)");
      push(c);
      display();
    } while (c != '/');
  }
  // method to push an item onto the stack
  public void push(char item)
  {
    if (size < SIZE)
    {
      stack[size] = item;
      size = size + 1;
    }
    else
    {
      output("Stack full");
    }
  }
  public void display()
  {
    output("stack");
    output("=====");
    for(int p = (size - 1); p >= 0; p--)
    {
      output(p + ":> " + stack[p]);
    }
    output("=====");
  }
  // Main method for class stack
  public static void main(String[] args)
  {
    new Stack();
  }
  //============================================================
  // Below are the IBIO simple input and output methods
  // to be included in the Class.

練習

編寫 pop 方法，以從堆疊中刪除專案 - 務必注意下溢（當堆疊中沒有任何專案時）。

編寫演算法，它會就地反轉字元字串（上一頁上對此進行了討論）。要獲取輸入字串並將其拆分為字元，您可能需要類似的東西

 String s = input("Please input a String");
  for (int p = 0; p < s.length(); p++)
  {
    char c = s.getChar(p);
   // process c

要將字元連線到字串，請嘗試以下操作

 String s;
  char c;
  s = s + c; // string s with char c added at the end (concatenated)

一個有用的方法 top，如果存在，則返回堆疊中的頂部元素，而不會將其彈出。實現這一點。

陣列中的佇列

我們已經看到了使用連結串列實現佇列的一種可能方式，但本節涉及靜態資料結構。因此，讓我們看看如何使用與上面相同的陣列，但我們將需要兩個指向陣列的指標，front 和 rear。

回想一下，專案是在 rear 新增的（入隊）並從 front 刪除的（出隊）。

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11] queue

最初將 front 和 rear 都指向元素 0 似乎是合理的。要入隊專案，請將其放置在 rear，然後將 rear 加 1 以指向下一個空閒位置。

檢查是否已到達陣列的末尾

佇列類
實現字元堆疊
使用陣列 - 是靜態資料結構
/

public class Queue {

  private static final int SIZE = 12;     // a constant for the queue size
  private char[] queue = new char[SIZE];  // the array to hold the queue
  private int front = 0;                  // the first item in the queue
  private int rear = 0;                   // the last item in the queue

  // Constructor
  public Queue()
  {
    front = 0;
    rear = 0;
    char c;
    do
    {
      c = inputChar("Input a character ('/' to end)");
      enqueue(c);
      display();
    } while (c != '/');
  }
  public void enqueue(char item)
  {
    if (rear < SIZE)
    {
      queue[rear] = item;
      rear = rear + 1;
    }
    else
    {
      output("Queue full - cannot add item");
    }
  }
  public void display()
  {
    output("front");
    output("=====");
    for(int p = front; p < rear; p++)
    {
      output(p + ":> " + queue[p]);
    }
    output("=====");
  }
  // Main method for class queue
  public static void main(String[] args)
  {
    new Queue();
  }

//============================================================ // 下面是 IBIO 的簡單輸入和輸出方法

練習

實現出隊方法，務必測試佇列中是否有任何要刪除的專案。

您可能想要更改建構函式以允許調用出隊

    c = inputChar("Input a character ('/' to end, '#' to dequeue)");

您可以從出隊方法返回一個字元，或者在方法主體中將其輸出。

一旦您成功執行，這裡就會出現一些問題 - 嘗試新增和刪除足夠的專案，我們就會到達 rear 指標碰到陣列末尾的位置，但陣列的前端仍然有空間

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11] queue

f

a

d 未使用/浪費的空間 front

rear

因此，我們需要做的是將 front 指標重新繞回開頭。

但是，我們必須能夠檢測到佇列何時已滿，即 rear 指標追上 front 指標時。

有幾種方法可以解決此問題，最簡單的方法可能是維護一個特殊標誌 qFull，當 front 達到 rear 時將其設定為 true，並在每次出隊專案時將其取消設定。

也可以以類似的方式使用 qEmpty 標誌。

/**

佇列類
實現字元堆疊
使用陣列 - 是靜態資料結構
/

public class Queue {

  private static final int SIZE = 12;    // a constant for the queue size
  private char[] queue = new char[SIZE]; // the array to hold the queue
  private int front = 0;                  // the first item in the queue
  private int rear = 0;                   // the last item in the queue
  private boolean qFull = false;          // flag
  private boolean qEmpty = true;          // nothing in the queue initially
  // Constructor
  public Queue()
  {
    front = 0;
    rear = 0;
    qFull = false;
    qEmpty = true;

    char c;
    do
    {
      c = inputChar("Input a character ('/' to end, '#' to dequeue)");
      if ( (c != '/') && (c !='#'))
      {
        enqueue(c);
      }
      else if (c == '#')
      {
        dequeue();
      }
      display();

    } while (c != '/');
  }
  public void enqueue(char item)
  {
    if (qFull)
    {
      output("Queue full - cannot add item");
    }
    else
    {
      queue[rear] = item;
      rear = (rear + 1) % SIZE;
      qFull = (rear == front);
      qEmpty = false;
    }
  }
  public void dequeue()
  {
    if (qEmpty)
    {
      output("Empty queue");
    }
    else
    {
      char c = queue[front];
      front = (front + 1) % SIZE;
      output("dequeued: " + c);
      qFull = false;
      qEmpty = (front == rear);
    }
  }
  public void display()
  {
    output("front");
    output("=====");
    for(int p = front; p != rear; p = (p + 1) % SIZE)
    {
      output(p + ":> " + queue[p]);
    }
    output("=====");
  }
  // Main method for class queue
  public static void main(String[] args)
  {
    new Queue();
  }

//============================================================ // 下面是 IBIO 的簡單輸入和輸出方法

練習

編寫一個自包含的佇列類，該類可以入隊和出隊字串或您自己選擇的其他物件。

該類應實現異常處理，以便可以丟擲 EmptyQueue、FullQueue 和其他自定義異常。

其他方法可能是 getFront、getRear，用於檢查但不要刪除這些專案。返回隊列當前大小的方法也很有用。

動態資料結構

問題解決方案中的物件

遞迴

示例（Java）

public static int factorial(int num) {
    int ans;
    if(num !== 1) {
        ans = factorial(num-1) * num;
    }
    return ans;
}

這是一段簡單的程式碼來表示階乘的值。

演算法評估

演算法效率

要最佳化演算法，首先必須瞭解某個演算法比另一個演算法好還是差。在這種情況下，更好可以意味著演算法處理資料的速度更快或使用的 RAM 更少。要測量資料處理速度，可以使用大 O 符號。

大O表示法總是以O(表示式)的形式出現。括號內的表示式對於不同的效率是不同的。它幾乎總是包含 $n$ ，要處理的資料項的數量。在一個數組（大小為n）上的線性搜尋的大O表示法是O( $n$ )。這意味著將陣列大小加倍，平均而言，線性搜尋完成的時間也會加倍。

然而，大O表示法並不表示演算法的效率到底有多高。它只表示當 $n$ 非常大並增加時，花費的時間會增加多少。例如，如果某個演算法對每項資料花費 $0.5n+2$ 毫秒，它仍然將具有O( $n$ )的大O表示法。這是因為當n達到，比如，一萬億時，增加的2幾乎沒有影響，所以它被丟棄了。以同樣的方式，n的所有係數都被丟棄。

其他大O表示法的例子包括用於氣泡排序和選擇排序的O( $n^{2}$ )，以及用於二分查詢的O( $\log n$ )。請注意，二分查詢的大O表示法是 $\log n$ ，而不是 $\log _{2}n$ ，因為當 $n$ 很大時，不同底數的對數以近似相同的方式增長。

v t e 國際文憑組織
第一組	英語
第二組	法語 • 西班牙語
第三組	商業管理 • 文化人類學 • 經濟學 • 歷史 • 地理 • 心理學 • 環境系統與社會
第四組	計算機科學 • 生物學 • 化學 • 物理 • 設計技術
第五組	數學 (進階 • 高階 • 標準 • 研究)
第六組	音樂 • 視覺藝術 • 電影 • 劇院
核心	知識論 • 擴充套件論文 • 創意行動服務