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

实 验 报 告课程名称 数据结构 实验项目 线性表的实现及应用 实验仪器 PC机一台 学 院_ 专 业 班级/学号 姓名 实验日期 成 绩 指导教师 北京信息科技大学信息管理学院（数据结构课程上机）实验报告专业: 班级: 学号: 姓名: 成绩: 实验名称线性表的实现及应用实验地点实验时间1. 实验目的：（1） 理解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会利用顺序表解决实际应用问题。（2） 熟练掌握单链表的使用；理解用链表实现线性表的特点；了解链表的多种形式；学会利用单链表解决实际应用问题。2. 实验要求：（1） 学时为8学时；（2） 能在机器上正确、调试运行程序；（3） 本实验需提交实验报告；（4） 实验报告文件命名方法：数据结构实验_信管16xx_学号_姓名.doc。3. 实验内容和步骤：第一部分 顺序表的实现与应用（1）基于顺序表实现线性表的以下基本操作：public interface LList /线性表接口，泛型参数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个元素 void 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) 若两个元素按值递增有序排列的顺序表A和B，且同一表中的元素值各不相同。试构造一个顺序表C，其元素为A和B中元素的交集，且表C中的元素也按值递增有序排列；（3）利用顺序表解决约瑟夫环问题：已知n个人（以编号1，2，3.n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。要求：输出出列次序。第二部分 单链表的实现与应用（4）基于单链表实现线性表的以下基本操作（不需要建立接口，直接建立带头结点的单链表类）：ADT Listboolean isEmpty(); /判断线性表是否空 int size(); /返回线性表长度 T get(int i); /返回第i（i0）个元素 void set(int i, T x); /设置第i个元素值为x Node insert(int i, T x); /插入x作为第i个元素 Node insert(T x); /在线性表最后插入x元素 T remove(int i); /删除第i个元素并返回被删除对象 void removeAll(); /删除线性表所有元素 Node search(T key); /查找，返回首次出现的关键字为key元素public String toString(); /返回顺序表所有元素的描述字符串，形式为“（，）”要求：实现后应编写代码段对每个基本操作做测试。（5）实现单链表的子类排序单链表，覆盖单链表如下方法：void set(int i, T x); /设置第i个元素值为xNode insert(int i, T x); /插入x作为第i个元素Node insert(T x); /在线性表最后插入x元素Node search(T key); /查找，返回首次出现的关键字为key元素（6）基于排序单链表实现线性表的以下综合应用：e) 删除第i个开始的k个元素。f) 删除递增有序单链表中所有值大于mink且小于maxk的元素。g) 将两个单链表合并为一个单链表，保持有序。h) 若两个元素按值递增有序排列的单链表A和B，且同一表中的元素值各不相同。试构造一个单链表C，其元素为A和B中元素的交集，且表C中的元素也按值递增有序排列。要求利用原有链表中的元素。（7）一元多项式的基本运算用排序单链表表示一元多项式，并实现以下基本运算：l 一元多项式的建立l 一元多项式的减法运算（要求：在运算过程中不能创建新结点 即A=A-B）（8）备份自己程序4. 实验准备：复习教材第2章线性表的知识点熟悉Java编程环境提前熟悉实验内容，设计相关算法5. 实验过程：第一部分：（1）package ex1;public interface LList /线性表接口，泛型参数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(); /删除线性表所有元素 int search(T key); /查找，返回首次出现的关键字为key的元素的位序类名：public class SeqList implements LList protected Object element;protected int n; public SeqList(int length) /构造容量为length的空表 this.element = new Objectlength; /申请数组的存储空间，元素为null。 /若length0，Java抛出负数组长度异常 java.lang.NegativeArraySizeException this.n = 0; public SeqList() /创建默认容量的空表，构造方法重载 this(64); /调用本类已声明的指定参数列表的构造方法 public SeqList(T values) /构造顺序表，由values数组提供元素，忽略其中空对象 this(values.length*2); /创建2倍values数组容量的空表 /若values=null，用空对象调用方法，Java抛出空对象异常NullPointerException for (int i=0; i=0 & i=0 & ithis.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); /抛出空对象异常 if (ithis.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开始至表尾的元素向后移动，次序从后向前 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.n0 & i=0 & ithis.n) T old = (T)this.elementi; /old中存储被删除元素 for (int j=i; jthis.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) /查找，返回首次出现的关键字为key的元素的位 System.out.print(this.getClass().getName()+.indexOf(+key+)，); for (int i=0; i0) str += this.element0.toString(); /执行T类的toString()方法，运行时多态 for (int i=1; ithis.n; i+) str += , +this.elementi.toString(); /执行T类的toString()方法，运行时多态 return str+) ; public static void main (String args) SeqList list=new SeqList(20); Integer values=10,1,2,3,4,5,6,7,8,9; SeqList list1=new SeqList(values); System.out.print(输出顺序表:); System.out.println(list1.toString(); System.out.println(顺序表List是否为空+list.isEmpty()+,List1是否为空+list1.isEmpty(); System.out.println(list的长度+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(修改后的顺序表:); 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,d,e,f,g,h; int n =values.length; for(int j=0;jn;j+) System.out.print(valuesj+ ); System.out.println(); for(int j=i+k;jn;j+) valuesj-k=valuesj; n=n-k; for(int j=0;jn;j+) System.out.print(valuesj+ ); 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 list=new SeqList(values); 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 list1=new SeqList(values1); Integer values2=2,4,5,22,23; SeqList list2=new SeqList(values2); SeqList list3=new SeqList(); int i=0,j=0; while(ilist1.length()&jlist2.length() if(list1.get(i)list2.get(j) list3.append(list1.get(i); i+; else list3.append(list2.get(j); j+; while(ilist1.length() list3.append(list1.get(i); i+; while(jlist2.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 Merge(); d) package test;import ex1.SeqList;public class Intersection public Intersection() Integer values1=1,3,5,11,12,13,22,23,50; SeqList list1=new SeqList(values1); Integer values2=2,4,5,12,19,20,22,23,; SeqList list2=new SeqList(values2); SeqList list3=new SeqList(); int i=0,j=0; while(ilist1.length()&jlist2.length() if(list1.get(i)list2.get(j) j+; else list3.append(list1.get(i); i+; j+; System.out.println(list1.toString(); System.out.println(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 list = new SeqList(n); /创建顺序表实例，元素类型是数字字符，只能排到n=9,否则达不到效果 for (int i=0; i1) /多于一个元素时循环，计数O(1) i = (i+m-1) % list.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）package test;import ex1.SeqList;public class JosephusA public JosephusA(int n, int k, int m) System.out.println(Josephus(+n+,+k+,+m+)，); SeqList list = new SeqList(n); /创建顺序表实例，元素类型是数字字符，只能排到n=9,否则达不到效果 for (int i=0; i1) /多于一个元素时循环，计数O(1) i = (i+m-1) % list.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 JosephusA(15,2,9); 第二部分：（4）、package ex2;public class Node public T data;/数据域public Node next;/地址域，后继结点/构造结点public Node(T data,Node next)this.data =data;this.next=next;/构造空结点public Node()this(null,null);/描述字符串public String toString()return this.data.toString();package ex2;public class SinglyList public Nodehead;/构造空单链表public SinglyList()head=new Node();/构造单链表，由values数组数组提供元素public SinglyList(T values)this();Noderear=this.head;for(int i=0;ivalues.length ;i+)rear.next=new Node(valuesi,null);rear=rear.next;public boolean isEmpty() /判断线性表是否空return this.head.next =null; public T get(int i) /返回第i（i0）个元素 Nodep=head.next ; for(int j=0;p!=null&j=0) ? p.data:null; public void set(int i, T x) /设置第i个元素值为x if(x=null) throw new NullPointerException(x=null); /抛出空对象异常 Nodep=this.head.next;/0 for(int j=0;p!=null&j0&p!=null) p.data=x; public int size() /返回线性表长度 int i=0;for(Nodep=this.head.next;p!=null;p=p.next)i+; return i; public Node insert(int i, T x) /插入x作为第i个元素 if(x=null) throw new NullPointerException(x=null); Nodefront=this.head ;/指定头结点 for(int j=0;front.next!=null&ji;j+) front=front.next;/以此循环找i-1 front.next=new Node(x,front.next ); return front.next; public Node insert(T x) if (x=null) throw new NullPointerException(x=null); /抛出空对象异常 Node front=this.head; /front指向头结点 for (; front.next!=null;) /寻找第i-1个或最后一个结点（front指向） front = front.next; front.next = new Node(x, front.next); /在front之后插入值为x结点，包括头插入、中间/尾插入 return front.next; public T remove(int i) /删除第i个元素并返回被删除对象 Nodep=this.head;/让p指向头结点 for(int j=0;ji&p.next!=null;j+) p=p.next; if(p.next!=null) T old=p.next.data ; p.next=p.next.next; return old; return null; public void removeAll() /删除线性表所有元素 this.head.next=null;/让头结点直接为空 public Node search(T key) /查找，返回首次出现的关键字为key元素 for(Node p =this.head;p.next!=null;p=p.next) if( key.equals(p.data) return p; return null; public String toString() /返回顺序表所有元素的描述字符串，形式为“（，）” String str=this.getClass().getName()+(; /返回类名 for (Node 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 SortedSinglyListT extends Comparable extends SinglyList/构造空排序单链表public SortedSinglyList()super();/默认调用父类构造方法SinglyList()public SortedSinglyList(SinglyList list) super(); /构造空单链表 for (Node p=list.head.next; p!=null; p=p.next)/直接插入排序，每趟插入1个元素 this.insert(p.data); /排序单链表按值插入 /构造 ，将values数组中的所有对象按值插入public SortedSinglyList(T values)super();for(int i=0;ivalues.length;i+)this.insert(valuesi);public void set(int i, T x) /设置第i个元素值为x throw new UnsupportedOperationException(set(int i, T x); /不支持父类方法，覆盖并抛出异常 public Node insert(int i, T x) /插入x作为第i个元素throw new UnsupportedOperationException(set(int i, T x); /不支持父类方法，覆盖并抛出异常 public Node insert(T x) /在线性表最后插入x元素Nodep=this.head;for(;p.next!=null& p.next.data.compareTo(x)0;)p=p.next;p.next = new Node(x, p.next);return p.next;public Node search(T key) /查找，返回首次出现的关键字为key元素for (Node p=this.head;p.next!=null&key.compareTo(p.data)=0;p=p.next)if(key.compareTo(p.next.data)=0)return p;return null;（6）、e、package ex2;public class Del1 public Del1(int i,int k)Integer values=1,5,6,10,13;SinglyList list= new SinglyList(values);System.out.println( list.toString();for(int j=0;jk ;j+)list.remove(i);System.out.println(删除后：+list.toString();public static void main(String args)new Del1(2,2);f、package ex2;public class Del2 public Del2(int mink,int maxk)Integer values=1,3,9,17,34;SortedSinglyList list = new SortedSinglyList(values);System.out.println(list.toString();Node p=list.head;int j=0;while(p.next!=null & p.next.data=mink)p=p.next;j+;while(p.next!=null &p.next.datamaxk)list.remove(j);System.out.println(list=+list.toString();public static void main(String args)new Del2(2,18);g、package ex2;public class Megerpublic Meger()Integer values1=1,2,5,7,9;SortedSinglyList val1=new SortedSinglyList(values1);Integer v