过程程序设计中的抽象数据类型实现

Question

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

Answer 1

您可以使用它的编程风格。

首先，您需要为ADT定义一个接口。只需写下它的名字和作用。

示例：

ADT：整数堆栈

• void push(int element)-将元素添加到堆栈顶部
• int pop()-从堆栈顶部移除并返回元素
• int peek()-返回top的值。不去除价值
• boolean isEmpty()-如果堆栈为空，则返回true
• int size()-返回堆栈中元素的数目
• void print()-打印堆栈的所有值

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

示例：

ADT：整数堆栈

实现：数组整数堆栈

• 使用Java的内置数组功能实现int堆栈
• 由于数组是一个静态集合，我需要使用一个整数变量来跟踪"；顶部">

设置好所有内容后，您现在可以继续进行编码。

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);
}
}
}