返回 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 国际文凭组织
第一组	英语
第二组	法语 • 西班牙语
第三组	商业管理 • 文化人类学 • 经济学 • 历史 • 地理 • 心理学 • 环境系统与社会
第四组	计算机科学 • 生物学 • 化学 • 物理 • 设计技术
第五组	数学 (进阶 • 高级 • 标准 • 研究)
第六组	音乐 • 视觉艺术 • 电影 • 剧院
核心	知识论 • 扩展论文 • 创意行动服务