过程编程中的抽象数据类型实现

Question

我有一个问题要问这里更高级的 OOP 开发人员。我目前是一名CS学生。我们在引入 ADT 的第一个学期 Java 中学习了过程编程。我理解为什么 ADT 是好的以及它有什么好处的理论和想法，但我似乎很难在代码中实现它。我感到困惑和迷失。除此之外，我们的退出测试是在纸上进行的（我们必须在纸上编写大约 200 行代码），我发现这很困难。在开始构建程序之前有什么提示吗？例如，在您开始编写代码之前，你们是否已经知道有多少方法以及什么方法将 return 并作为正式参数？

Answer 1

您可以采用编程方式处理它。

首先，您需要为 ADT 定义一个接口。只需记下它的名称和作用即可。

示例：

ADT: Integer Stack

void push(int element) - adds an element to the top of stack

int pop() - removes and returns an element from the top of stack

int peek() - returns the value of top. no removal of value

boolean isEmpty() - returns true if the stack is empty

int size() - returns the number of element in the stack.

void print() - print all values of stack

接下来您需要决定其实施。由于ADT是关于存储的，所以最好先确定存储策略。

示例：

ADT: Integer Stack

Implementation: Array Integer Stack

Implements an int stack using Java's built-in array functionality.

Since array is a static collection, i need to use an integer variable to track "top"

一切就绪后，您现在可以继续编码了。

public interface IntegerStack {
  void push(int e);
  int pop();
  int peek();
  boolean isEmpty();
  int size();
  void print();
}

public class ArrayIntegerStack implements IntegerStack {
  private static final int INITIAL_TOP_INDEX = -1;

  private int topIndex = INITIAL_TOP_INDEX;
  private int[] stackValue = new int[Integer.MAX_VALUE];

  @Override
  public void push(int element) {
    stackValue[++topIndex] = element;
  }

  @Override
  public int pop() {
    return stackValue[topIndex--];
  }

  @Override
  public int peek() {
    return stackValue[topIndex];
  }

  @Override
  public boolean isEmpty() {
    return INITIAL_TOP_INDEX == topIndex;
  }

  @Override
  public int size() {
    return topIndex + 1;
  }

  @Override
  public void print() {
    for (int i = 0; i <= topIndex; i++) {
      System.out.println(stackValue[i]);
    }
  }
}

Answer 2

加上 KaNa001 的答案，您可以使用修改后的 HashMap，其中键是索引，值是堆栈中的整数。这不会导致异常，因为 HashMap 对象可以更改其长度。

public class OrderSet<T> {

private HashMap<Integer, T> array;

public OrderSet() {

    array = new HashMap<Integer, T>();
}

public void addAt (T o, int pos) {
    // uses Array indexing

    HashMap<Integer, T> temp = new HashMap<Integer, T>();

    if (!(array.size() == 0)) {

        for (int i = 0; i < array.size(); i++) {

            temp.put(i, array.get(i));
        }

        array.put(pos, o);

        int size = array.size();

        for (int i = pos + 1; i < size + 1; i++) {

            array.put(i, temp.get(i - 1));
        }
    } else {

        array.put(0, o);
    }
}

public T getPos (int pos) {

    if (array.size() == 0) {

        return null;
    } else {

        return array.get(pos);
    }
}
}

过程编程中的抽象数据类型实现

Abstract Data Type implementation in Procedural Programming

java

abstract-data-type