数据结构Java版线性表的实现与应用完整版

1、实 验 报 告课程名称 数据结构 实验项目 线性表的实现及应用 实验仪器 PC机一台 学 院_ 专 业 班级/学号 姓名 实验日期 成 绩 指导教师 北京信息科技大学信息管理学院（数据结构课程上机）实验报告专业: 班级: 学号: 姓名: 成绩: 实验名称线性表的实现及应用实验地点实验时间1. 实验目的：（1） 理解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会利用顺序表解决实际应用问题。（2） 熟练掌握单链表的使用；理解用链表实现线性表的特点；了解链表的多种形式；学会利用单链表解决实际应用问题。2. 实验要求：（1） 学时为8学时；（2） 能在机器上正确、调试运行程序；（3） 本实验

2、需提交实验报告；（4） 实验报告文件命名方法：数据结构实验_信管16xx_学号_姓名.doc。3. 实验内容和步骤：第一部分 顺序表的实现与应用（1）基于顺序表实现线性表的以下基本操作：public interface LList<T> /线性表接口，泛型参数T表示数据元素的数据类型 boolean isEmpty(); /判断线性表是否空 int size(); /返回线性表长度 T get(int i); /返回第i（i0）个元素 void set(int i, T x); /设置第i个元素值为x void insert(int i, T x); /插入x作为第i个元素 voi

3、d insert(T x); /在线性表最后插入x元素 T remove(int i); /删除第i个元素并返回被删除对象 int search(T key); /查找，返回首次出现的关键字为key的元素的位序void removeAll(); /删除线性表所有元素 public String toString();/返回顺序表所有元素的描述字符串，形式为“（，）”要求：实现后应编写代码段对每个基本操作做测试。（2）顺序表的简单应用a) 运用基本操作编写算法删除第i个开始的k个元素。b) 编写高效算法删除第i个开始的k个元素。c) 将两个顺序表合并为一个顺序表（表中元素有序）；d) 若两个元素

4、按值递增有序排列的顺序表A和B，且同一表中的元素值各不相同。试构造一个顺序表C，其元素为A和B中元素的交集，且表C中的元素也按值递增有序排列；（3）利用顺序表解决约瑟夫环问题：已知n个人（以编号1，2，3.n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。要求：输出出列次序。第二部分 单链表的实现与应用（4）基于单链表实现线性表的以下基本操作（不需要建立接口，直接建立带头结点的单链表类）：ADT List<T>boolean isEmpty(); /判断线性表是否

5、空 int size(); /返回线性表长度 T get(int i); /返回第i（i0）个元素 void set(int i, T x); /设置第i个元素值为x Node<T> insert(int i, T x); /插入x作为第i个元素 Node<T> insert(T x); /在线性表最后插入x元素 T remove(int i); /删除第i个元素并返回被删除对象 void removeAll(); /删除线性表所有元素 Node<T> search(T key); /查找，返回首次出现的关键字为key元素public String toSt

6、ring(); /返回顺序表所有元素的描述字符串，形式为“（，）”要求：实现后应编写代码段对每个基本操作做测试。（5）实现单链表的子类排序单链表，覆盖单链表如下方法：void set(int i, T x); /设置第i个元素值为xNode<T> insert(int i, T x); /插入x作为第i个元素Node<T> insert(T x); /在线性表最后插入x元素Node<T> search(T key); /查找，返回首次出现的关键字为key元素（6）基于排序单链表实现线性表的以下综合应用：e) 删除第i个开始的k个元素。f) 删除递增有序单链表

7、中所有值大于mink且小于maxk的元素。g) 将两个单链表合并为一个单链表，保持有序。h) 若两个元素按值递增有序排列的单链表A和B，且同一表中的元素值各不相同。试构造一个单链表C，其元素为A和B中元素的交集，且表C中的元素也按值递增有序排列。要求利用原有链表中的元素。（7）一元多项式的基本运算用排序单链表表示一元多项式，并实现以下基本运算：l 一元多项式的建立l 一元多项式的减法运算（要求：在运算过程中不能创建新结点 即A=A-B）（8）备份自己程序4. 实验准备：复习教材第2章线性表的知识点熟悉Java编程环境提前熟悉实验内容，设计相关算法5. 实验过程：第一部分：（1）package

8、ex1;public interface LList<T> /线性表接口，泛型参数T表示数据元素的数据类型 boolean isEmpty(); /判断线性表是否空 int length(); /返回线性表长度 T get(int i); /返回第i（i0）个元素 void set(int i, T x); /设置第i个元素值为x int insert(int i, T x); /插入x作为第i个元素 int append(T x); /在线性表最后插入x元素 T remove(int i); /删除第i个元素并返回被删除对象 void removeAll(); /删除线性表所有元

9、素 int search(T key); /查找，返回首次出现的关键字为key的元素的位序类名：public class SeqList<T> implements LList<T> protected Object element;protected int n; public SeqList(int length) /构造容量为length的空表 this.element = new Objectlength; /申请数组的存储空间，元素为null。 this.n = 0; public SeqList() /创建默认容量的空表，构造方法重载 this(64); /

10、调用本类已声明的指定参数列表的构造方法 public SeqList(T values) /构造顺序表，由values数组提供元素，忽略其中空对象 this(values.length*2); /创建2倍values数组容量的空表 /若values=null，用空对象调用方法，Java抛出空对象异常NullPointerException for (int i=0; i<values.length; i+) /复制非空的数组元素。O(n) if (valuesi!=null) this.elementthis.n+ = valuesi; /对象引用赋值 public boolean is

11、Empty() /判断线性表是否空return this.n=0; public int length() /返回线性表长度 return this.n; public T get(int i) /返回第i（i0）个元素 if (i>=0 && i<this.n) return (T)this.elementi; /返回数组元素引用的对象，传递对象引用/ return this.elementi; /编译错，Object对象不能返回T对象 return null; public void set(int i, T x) /设置第i个元素值为x if (x=null)

12、 throw new NullPointerException("x=null"); /抛出空对象异常 if (i>=0 && i<this.n) this.elementi = x; else throw new java.lang.IndexOutOfBoundsException(i+"");/抛出序号越界异常 public int insert(int i, T x) /插入x作为第i个元素 if (x=null) throw new NullPointerException("x=null");

13、/抛出空对象异常 if (i<0) i=0; /插入位置i容错，插入在最前 if (i>this.n) i=this.n; /插入在最后 Object source = this.element; /数组变量引用赋值，source也引用element数组 if (this.n=element.length) /若数组满，则扩充顺序表的数组容量 this.element = new Objectsource.length*2; /重新申请一个容量更大的数组 for (int j=0; j<i; j+) /复制当前数组前i-1个元素 this.elementj = sourcej

14、; for (int j=this.n-1; j>=i; j-) /从i开始至表尾的元素向后移动，次序从后向前 this.elementj+1 = sourcej; this.elementi = x; this.n+; return i; /返回x序号 public int append(T x) /在线性表最后插入x元素 return this.insert(this.n, x); public T remove(int i) /删除第i个元素并返回被删除对象 if (this.n>0 && i>=0 && i<this.n) T o

15、ld = (T)this.elementi; /old中存储被删除元素 for (int j=i; j<this.n-1; j+) this.elementj = this.elementj+1; /元素前移一个位置 this.elementthis.n-1=null; /设置数组元素对象为空，释放原引用实例 this.n-; return old; /返回old局部变量引用的对象，传递对象引用 return null; public void removeAll() /删除线性表所有元素 this.n=0; public int search(T key) /查找，返回首次出现的关键字

16、为key的元素的位 System.out.print(this.getClass().getName()+".indexOf("+key+")，"); for (int i=0; i<this.n; i+) if (key.equals(this.elementi) /执行T类的equals(Object)方法，运行时多态 return i; return -1; public String toString() String str=this.getClass().getName()+"(" /返回类名 if (this.n&

17、gt;0) str += this.element0.toString(); /执行T类的toString()方法，运行时多态 for (int i=1; i<this.n; i+) str += ", "+this.elementi.toString(); /执行T类的toString()方法，运行时多态 return str+") " public static void main (String args) SeqList<Integer> list=new SeqList<Integer>(20); Integer

18、values=10,1,2,3,4,5,6,7,8,9; SeqList<Integer> list1=new SeqList<Integer>(values); System.out.print("输出顺序表:"); System.out.println(list1.toString(); System.out.println("顺序表List是否为空"+list.isEmpty()+",List1是否为空"+list1.isEmpty(); System.out.println("list的长度&

19、quot;+list.length()+",list1的长度"+list1.length(); System.out.println("返回list1的第7个元素是:"+list1.get(6); System.out.println("重新设置第5个元素为19:"); list1.set(4, 19); list1.insert(2, 100); list1.append(20); System.out.println("删除8:"+list1.remove(8); System.out.print("

20、修改后的顺序表:"); System.out.println(list1.toString(); list1.removeAll(); System.out.println("删除后的顺序表："+list1.toString(); /为空 System.out.println("寻找元素50:"+list1.search(50); （2）a) package ex1;public class Del public Del(int i,int k) String values="A","b","C

21、","d","e","f","g","h" int n =values.length; for(int j=0;j<n;j+) System.out.print(valuesj+" "); System.out.println(); for(int j=i+k;j<n;j+) valuesj-k=valuesj; n=n-k; for(int j=0;j<n;j+) System.out.print(valuesj+ " " )

22、; System.out.println(); public static void main(String args) new Del(2,3); b)package ex1;public class Del2 public Del2(int i,int k) String values="A","x","y","y","b","c","h" SeqList<String> list=new SeqList<String>(val

23、ues); System.out.println(list.toString(); for(int j=1;j<=k;j+) list.remove(i); System.out.println(list.toString(); public static void main(String args) new Del2(2,3); c) package ex1;public class Merge public Merge() Integer values1=1,3,5,11; SeqList<Integer> list1=new SeqList<Integer>

24、(values1); Integer values2=2,4,5,22,23; SeqList<Integer> list2=new SeqList<Integer>(values2); SeqList<Integer> list3=new SeqList<Integer>(); int i=0,j=0; while(i<list1.length()&&j<list2.length() if(list1.get(i)<list2.get(j) list3.append(list1.get(i); i+; else

25、 list3.append(list2.get(j); j+; while(i<list1.length() list3.append(list1.get(i); i+; while(j<list2.length() list3.append(list2.get(j) ; j+; System.out.println(list1.toString(); System.out.println(list2.toString(); System.out.println(list3.toString(); public static void main(String args) new M

26、erge(); d) package test;import ex1.SeqList;public class Intersection public Intersection() Integer values1=1,3,5,11,12,13,22,23,50; SeqList<Integer> list1=new SeqList<Integer>(values1); Integer values2=2,4,5,12,19,20,22,23,; SeqList<Integer> list2=new SeqList<Integer>(values2

27、); SeqList<Integer> list3=new SeqList<Integer>(); int i=0,j=0; while(i<list1.length()&&j<list2.length() if(list1.get(i)<list2.get(j) i+; else if(list1.get(i)>list2.get(j) j+; else list3.append(list1.get(i); i+; j+; System.out.println(list1.toString(); System.out.print

28、ln(list2.toString(); System.out.println(list3.toString(); public static void main(String args) new Intersection(); 3. （1）package ex1;public class Josephus public Josephus(int n, int k, int m) System.out.println("Josephus("+n+","+k+","+m+")，"); SeqList<Strin

29、g> list = new SeqList<String>(n); /创建顺序表实例，元素类型是数字字符，只能排到n=9,否则达不到效果 for (int i=0; i<n; i+) list.append(char)('1'+i)+""); /顺序表尾插入，O(1) / System.out.println(list.toString(); /输出顺序表的描述字符串，O(n) int i = k; /计数起始位置 while (list.length()>1) /多于一个元素时循环，计数O(1) i = (i+m-1) % l

30、ist.length(); /按循环方式对顺序表进行遍历,圆桌循环 System.out.print("出列"+list.remove(i).toString()+"，"); /删除i位置对象，O(n) / System.out.println(list.toString(); System.out.println("出列"+list.get(0).toString();/get(0)获得元素，O(1) public static void main(String args) new Josephus(9,1,3); （2）packa

31、ge test;import ex1.SeqList;public class JosephusA public JosephusA(int n, int k, int m) System.out.println("Josephus("+n+","+k+","+m+")，"); SeqList<Integer> list = new SeqList<Integer>(n); /创建顺序表实例，元素类型是数字字符，只能排到n=9,否则达不到效果 for (int i=0; i<n; i+

32、) list.append(i); /顺序表尾插入，O(1) / System.out.println(list.toString(); /输出顺序表的描述字符串，O(n) int i = k; /计数起始位置 while (list.length()>1) /多于一个元素时循环，计数O(1) i = (i+m-1) % list.length(); /按循环方式对顺序表进行遍历,圆桌循环 System.out.print("出列"+list.remove(i).toString()+"，"); /删除i位置对象，O(n) / System.out

33、.println(list.toString(); System.out.println("出列"+list.get(0).toString();/get(0)获得元素，O(1) public static void main(String args) new JosephusA(15,2,9); 第二部分：（4）、package ex2;public class Node<T> public T data;/数据域public Node<T> next;/地址域，后继结点/构造结点public Node(T data,Node<T> n

34、ext)this.data =data;this.next=next;/构造空结点public Node()this(null,null);/描述字符串public String toString()return this.data.toString();package ex2;public class SinglyList<T> public Node<T>head;/构造空单链表public SinglyList()head=new Node<T>();/构造单链表，由values数组数组提供元素public SinglyList(T values)th

35、is();Node<T>rear=this.head;for(int i=0;i<values.length ;i+)rear.next=new Node<T>(valuesi,null);rear=rear.next;public boolean isEmpty() /判断线性表是否空return this.head.next =null; public T get(int i) /返回第i（i0）个元素 Node<T>p=head.next ; for(int j=0;p!=null&&j<i;j+) p=p.next; re

36、turn (p!=null&&i>=0) ? p.data:null; public void set(int i, T x) /设置第i个元素值为x if(x=null) throw new NullPointerException("x=null"); /抛出空对象异常 Node<T>p=this.head.next;/0 for(int j=0;p!=null&&j<i;j+) /遍历寻找第i个结点（p指向） p=p.next; if(i>0&&p!=null) p.data=x; publ

37、ic int size() /返回线性表长度 int i=0;for(Node<T>p=this.head.next;p!=null;p=p.next)i+; return i; public Node<T> insert(int i, T x) /插入x作为第i个元素 if(x=null) throw new NullPointerException("x=null"); Node<T>front=this.head ;/指定头结点 for(int j=0;front.next!=null&&j<i;j+) fro

38、nt=front.next;/以此循环找i-1 front.next=new Node<T>(x,front.next ); return front.next; public Node<T> insert(T x) if (x=null) throw new NullPointerException("x=null"); /抛出空对象异常 Node<T> front=this.head; /front指向头结点 for (; front.next!=null;) /寻找第i-1个或最后一个结点（front指向） front = fron

39、t.next; front.next = new Node<T>(x, front.next); /在front之后插入值为x结点，包括头插入、中间/尾插入 return front.next; public T remove(int i) /删除第i个元素并返回被删除对象 Node<T>p=this.head;/让p指向头结点 for(int j=0;j<i&&p.next!=null;j+) p=p.next; if(p.next!=null) T old=p.next.data ; p.next=p.next.next; return old

40、; return null; public void removeAll() /删除线性表所有元素 this.head.next=null;/让头结点直接为空 public Node<T> search(T key) /查找，返回首次出现的关键字为key元素 for(Node<T> p =this.head;p.next!=null;p=p.next) if( key.equals(p.data) return p; return null; public String toString() /返回顺序表所有元素的描述字符串，形式为“（，）” String str=th

41、is.getClass().getName()+"(" /返回类名 for (Node<T> p=this.head.next; p!=null; p=p.next)/p遍历单链表 str += p.data.toString(); if (p.next!=null) str += "," /不是最后一个结点时，加分隔符 return str+")" （5）、package ex2;public class SortedSinglyList<T extends Comparable <? super T>

42、> extends SinglyList<T>/构造空排序单链表public SortedSinglyList()super();/默认调用父类构造方法SinglyList()public SortedSinglyList(SinglyList<T> list) super(); /构造空单链表 for (Node<T> p=list.head.next; p!=null; p=p.next)/直接插入排序，每趟插入1个元素 this.insert(p.data); /排序单链表按值插入 /构造 ，将values数组中的所有对象按值插入public S

43、ortedSinglyList(T values)super();for(int i=0;i<values.length;i+)this.insert(valuesi);public void set(int i, T x) /设置第i个元素值为x throw new UnsupportedOperationException("set(int i, T x)"); /不支持父类方法，覆盖并抛出异常 public Node<T> insert(int i, T x) /插入x作为第i个元素throw new UnsupportedOperationException("set