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

1、实验二 线性表的链式存储结构一目的要求： 1掌握链式存储结构的特点。 2掌握链式存储结构的常见算法。二实验内容1使用原有的顺序表的接口；2用类实现该接口的基本方法：u 插入数据元素（按指定位置插入和在表尾插入），建立链表；u 按指定位置查找在该链表中的某一元素；u 按指定位置删除该链表中的某一元素；u 实现该链表的遍历；3定义客户类来调用接口中的方法三程序设计分析因为链表的基本操作方法也是插入删除等，所以链表同样使用了ListInterface接口。实现声明ADT操作的单一借口的类，应该将声明的方法只定义为公有方法，这个类还可以定义私有方法和受保护方法。四，源代码1链表类.import lis

2、t.ListInterface;public class LList implements ListInterface private Node firstNode; / 指向第一个结点的引用private int length; / 线性表的元素数目public LList() / TODO Auto-generated constructor stubclear();public boolean add(T newEntry) Node newNode = new Node(newEntry);if (isEmpty() firstNode = newNode; else Node las

3、tNode = 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) Node newNod

4、e = new Node(newEntry);if (isEmpty() | (newPosition = 1) newNode.setNext(firstNode);firstNode = newNode; else Node nodeBefore = getNodeAt(newPosition - 1);Node nodeAfter = nodeBefore.getNext();newNode.setNext(nodeAfter);nodeBefore.setNext(newNode);/ end iflength+; elseisSuccessful = false;return isS

5、uccessful;/ end addprivate Node getNodeAt(int givenPosition) / Task:返回对指定位置结点的引用assert !isEmpty() & (givenPosition = 1) & (givenPosition = length);Node currentNode = firstNode;for (int counter = 1; counter givenPosition; counter+)currentNode = currentNode.getNext();assert currentNode != null;return

6、currentNode;public void clear() / TODO Auto-generated method stubfirstNode = null;length = 0;public boolean contains(T anEntry) boolean found = false;Node currentNode = firstNode;while (!found & (currentNode != null) if (anEntry.equals(currentNode.getData()found = true;elsecurrentNode = currentNode.

7、getNext();return found;public void display() Node currentNode = firstNode;while (currentNode != null) System.out.println(currentNode.getData();currentNode = currentNode.getNext();public T getEntry(int givenPosition) T result = null;if (!isEmpty() & (givenPosition = 1) & (givenPosition = 1) & (givenP

8、osition = length) if (givenPosition = 1) removedEntry = firstNode.getData();firstNode = firstNode.getNext(); else Node nodeBefore = getNodeAt(givenPosition - 1);Node nodeToRemove = nodeBefore.getNext();removedEntry = nodeToRemove.getData();Node nodeAfter = nodeToRemove.getNext();nodeBefore.setNext(n

9、odeAfter);length-;return removedEntry;public boolean replace(int givenPosition, T newEntry) boolean isSuccessful = true;if (!isEmpty() & (givenPosition = 1) & (givenPosition = length) Node desiredNode = getNodeAt(givenPosition);desiredNode.setData(newEntry); elseisSuccessful = false;return isSuccess

10、ful;/* * public int getLoc(T anEntry) int result=-1; Node * currentNode=firstNode; int i=1; * * while(result1 &(currentNode!=null) * if(anEntry.equals(currentNode.getData() result=i; else * currentNode=currentNode.getNext(); i+; return result; * public boolean union(ListInterface willBeUnion) int lb

11、_len = willBeUnion.getLength(); / 求线性表的长度for (int i = 1; i = 1 & head tail & tail = length) while (head = 1 & n = 1 & m + n = listLen) int firsEntryLoc = 1;for (int i = listLen - n + 1; i = listLen; i+) T temp = remove(i);add(firsEntryLoc, temp);firsEntryLoc+;for (int j = m + n + 1; j = listLen; j+)

12、 T temp = remove(j);add(firsEntryLoc, temp);firsEntryLoc+;public void swap2(ListInterface list, int m, int n) if (m = 1 & n = 1 & m + n = length) invert(1, length);System.out.println(第一次调换：);display();invert(1, n);System.out.println(第二次调换：);display();invert( n + 1, length - m);System.out.println(第三次

13、调换：);display();this.invert(length + 1 - m, length);System.out.println(第四次调换：);/ list.display();public void purge() 2. 结点类public class Node private T data; /entry in listprivate Node next; /link to next nodepublic Node(T dataPortion)data=dataPortion;setNext(null); /end constructorpublic Node(T dataPo

14、rtion, Node nextNode)data=dataPortion;setNext(nextNode);/end constructorpublic T getData()return data;public void setData(T newEntry)this.data=newEntry;public void setNext(Node next) this.next = next;public Node getNext() return next;public class TestLList private ListInterface llist;TestLList() lli

15、st = new LList();public ListInterface getAList() return llist;public void setAList(ListInterface alist) this.llist = alist;public void testInvert()llist.add(1);llist.add(2);llist.add(3);llist.add(4);System.out.println(逆置之前：);llist.display();llist.invert(1, 3);System.out.println(逆置之后：);llist.display(

16、);public void testSwap()llist.add(1);llist.add(2);llist.add(3);llist.add(4);System.out.println(置换之前：);llist.display();llist.exchage(1, 2);System.out.println(置换之后：);llist.display();public void testSwap2()llist.add(1);llist.add(2);llist.add(3);llist.add(4);System.out.println(置换之前：);llist.display();/ll

17、ist.swap2(1, 2);System.out.println(置换之后：);llist.display();public void testPurge()llist.add(1);llist.add(2);dd(1);llist.add(1);llist.add(2);llist.add(2);llist.add(1);System.out.println(删除重复元素之前：);llist.display();llist.purge();System.out.println(删除重复元素之后：);llist.display();public void testPurge2()AList

18、 llist2=new AList(15);llist2.add(1);llist2.add(2);llist2.add(2);llist2.add(2);llist2.add(1);/bb.add(2);/bb.add(1);System.out.println(删除重复元素之前：);llist2.display(); llist2.purge2();System.out.println(删除重复元素之后：);llist2.display();public static void main(String args) TestLList testLList=new TestLList();/测试线性表逆置/testAList.testInvert();/测试置换实现一/testAList.testSwap();/测试置换实现二/testAList.testSwap2();