java 数据结构实验报告实验二线性表的链式存储结构.doc

实验二 线性表的链式存储结构 一．目的要求： 1．掌握链式存储结构的特点。 2．掌握链式存储结构的常见算法。 二．实验内容 1．使用原有的顺序表的接口； 2．用类实现该接口的基本方法： 插入数据元素（按指定位置插入和在表尾插入），建立链表； 按指定位置查找在该链表中的某一元素； 按指定位置删除该链表中的某一元素； 实现该链表的遍历； 3．定义客户类来调用接口中的方法 三．程序设计分析 因为链表的基本操作方法也是插入删除等，所以链表同样使用了ListInterface接口。实现声明ADT操作的单一借口的类，应该将声明的方法只定义为公有方法，这个类还可以定义私有方法和受保护方法。 四，源代码 1链表类. import list.ListInterface; public class LListT implements ListInterfaceT { private NodeT firstNode; // 指向第一个结点的引用　 private int length; // 线性表的元素数目　 public LList() { // TODO Auto-generated constructor stub clear(); } public boolean add(T newEntry) { NodeT newNode = new NodeT(newEntry); if (isEmpty()) { firstNode = newNode; } else { NodeT lastNode = getNodeAt(length); lastNode.setNext(newNode); // 使最后一个结点指向新结点 } length++; return true; } /** * 任务：往线性表的末尾插入新元素 * 输入：newEntry作为新元素插入的对象 * 返回：如果插入成功则返回true,否则返回false */ public boolean add(int newPosition, T newEntry) { boolean isSuccessful = true; if ((newPosition = 1) (newPosition = length + 1)) { NodeT newNode = new NodeT(newEntry); if (isEmpty() || (newPosition == 1)) { newNode.setNext(firstNode); firstNode = newNode; } else { NodeT nodeBefore = getNodeAt(newPosition - 1); NodeT nodeAfter = nodeBefore.getNext(); newNode.setNext(nodeAfter); nodeBefore.setNext(newNode); }// end if length++; } else isSuccessful = false; return isSuccessful; }// end add private NodeT getNodeAt(int givenPosition) { // Task:返回对指定位置结点的引用 assert !isEmpty() (givenPosition = 1) (givenPosition = length); NodeT currentNode = firstNode; for (int counter = 1; counter givenPosition; counter++) currentNode = currentNode.getNext(); assert currentNode != null; return currentNode; } public void clear() { // TODO Auto-generated method stub firstNode = null; length = 0; } public boolean contains(T anEntry) { boolean found = false; NodeT currentNode = firstNode; while (!found (currentNode != null)) { if (anEntry.equals(curr