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

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

2、验需提交实验报告；（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

3、(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）基于单链表实现线性表的以下基本操作（不需要建立接口，直接建立带头结点的单链表类）：ADTListboolean isEmpty()。 /判断线性表是否空 int size()。 /返回线性表

5、长度T get(int i)。 /返回第i（i0）个元素 void set(int i, T x)。 /设置第i个元素值为xNode 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()。 /返回顺序表所有元素的描述字符串，形式为“（，）”要求：实现后应编写代码段对每个基本操

6、作做测试。（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，且同一表中的元素值各

7、不相同。试构造一个单链表C，其元素为A和B中元素的交集，且表C中的元素也按值递增有序排列。要求利用原有链表中的元素。（7）一元多项式的基本运算用排序单链表表示一元多项式，并实现以下基本运算：l 一元多项式的建立l 一元多项式的减法运算（要求：在运算过程中不能创建新结点 即A=A-B）（8）备份自己程序4. 实验准备：复习教材第2章线性表的知识点熟悉Java编程环境提前熟悉实验内容，设计相关算法5. 实验过程：第一部分：（1）package ex1。publicinterface LList /线性表接口，泛型参数T表示数据元素的数据类型boolean isEmpty()。 /判断线性表是否空i

8、nt length()。 /返回线性表长度 T get(int i)。 /返回第i（i0）个元素void set(int i, T x)。 /设置第i个元素值为xint insert(int i, T x)。 /插入x作为第i个元素int append(T x)。 /在线性表最后插入x元素 T remove(int i)。 /删除第i个元素并返回被删除对象void removeAll()。 /删除线性表所有元素int search(T key)。 /查找，返回首次出现的关键字为key的元素的位序类名：publicclass SeqList implements LList protected

9、Object element。protectedintn。public SeqList(int length) /构造容量为length的空表 this.element = new Objectlength。 /申请数组的存储空间，元素为null。/若length0，Java抛出负数组长度异常 java.lang.NegativeArraySizeExceptionthis.n = 0。 public SeqList() /创建默认容量的空表，构造方法重载 this(64)。 /调用本类已声明的指定参数列表的构造方法 public SeqList(T values) /构造顺序表，由value

10、s数组提供元素，忽略其中空对象 this(values.length*2)。 /创建2倍values数组容量的空表/若values=null，用空对象调用方法，Java抛出空对象异常NullPointerExceptionfor (int i=0。 i=0 & i=0 & ithis.n)this.elementi = x。elsethrownew java.lang.IndexOutOfBoundsException(i+)。/抛出序号越界异常 publicint insert(int i, T x) /插入x作为第i个元素if (x=null)thrownew NullPointerExc

11、eption(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 =

12、x。this.n+。return i。 /返回x序号 publicint append(T x) /在线性表最后插入x元素returnthis.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。 /设置数组元素

13、对象为空，释放原引用实例this.n-。return old。 /返回old局部变量引用的对象，传递对象引用 returnnull。 publicvoid removeAll()/删除线性表所有元素this.n=0。 publicint search(T key) /查找，返回首次出现的关键字为key的元素的位 System.out.print(this.getClass().getName()+.indexOf(+key+)，)。for (int i=0。 i0) str += this.element0.toString()。 /执行T类的toString()方法，运行时多态for (in

14、t i=1。 ithis.n。 i+) str += , +this.elementi.toString()。 /执行T类的toString()方法，运行时多态return str+) 。 publicstaticvoid 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()。 Syst

15、em.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(删除

16、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。publicclass Del public Del(int i,int k) String values=A,b,C,d,e,f,g,h。int n =values.

17、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()。 publicstaticvoid main(String args)new Del(2,3)。 b)package ex1。publicclassDel2 public Del2(int i,int k) Strin

18、g 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()。 publicstaticvoid main(String args) newDel2(2,3)。 c)package ex1。publicclass Merge public Merge() Integer values1=1,3,5,11。 SeqList list1

19、=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(list

20、1.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()。 publicstaticvoid main(String args)new Merge()。 d) package test。import ex1.SeqList。publicclass Intersection public Interse

21、ction() 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()。inti=0,j=0。while(ilist1.length()&jlist2.length() if(list1.get(i)list2.get(j)j+。 else list3.append(list1.get(i)。i

22、+。j+。 System.out.println(list1.toString()。 System.out.println(list2.toString()。 System.out.println(list3.toString()。 publicstaticvoid main(String args) new Intersection()。 3.（1）package ex1。publicclass Josephus public Josephus(intn, intk, intm) System.out.println(Josephus(+n+,+k+,+m+)，)。 SeqList list

23、 = new SeqList(n)。/创建顺序表实例，元素类型是数字字符，只能排到n=9,否则达不到效果for (inti=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) p

24、ublicstaticvoid main(String args) new Josephus(9,1,3)。 （2）package test。import ex1.SeqList。publicclass JosephusA public JosephusA(intn, intk, intm) System.out.println(Josephus(+n+,+k+,+m+)，)。 SeqList list = new SeqList(n)。/创建顺序表实例，元素类型是数字字符，只能排到n=9,否则达不到效果for (inti=0。 i1) /多于一个元素时循环，计数O(1) i = (i+m-1

25、) % 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) publicstaticvoid main(String args) new JosephusA(15,2,9)。 第二部分：（4）、package ex2。publicclass Node pu

26、blic 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()returnthis.data.toString()。package ex2。publicclass SinglyList public Nodehead。/构造空单链表public SinglyList()head=new Node()。/构造单链表，由

27、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。publicboolean isEmpty() /判断线性表是否空returnthis.head.next =null。 public T get(int i) /返回第i（i0）个元素 Nodep=head.next 。for(int j=0。p!=null&j=0) ? p.data:null。 pub

28、licvoid set(int i, T x) /设置第i个元素值为x if(x=null)thrownew NullPointerException(x=null)。 /抛出空对象异常 Nodep=this.head.next。/0for(int j=0。p!=null&j0&p!=null) p.data=x。 publicint 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

29、)thrownew 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)thrownew NullPointerException(x=null)。 /抛出空对象异常 Node front=this.head。 /front指向头结点

30、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

31、.next=p.next.next。return old。 returnnull。 publicvoid 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。returnnull。 public String toString() /返回顺序表所有元素的描述字符串，形式为“（，）” String st

32、r=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。publicclass SortedSinglyListT extends Comparable extends SinglyList/构造空排序单链表public SortedSinglyList()super()。/默

33、认调用父类构造方法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)。publicvoid s

34、et(int i, T x) /设置第i个元素值为xthrownew UnsupportedOperationException(set(int i, T x)。 /不支持父类方法，覆盖并抛出异常 public Node insert(int i, T x) /插入x作为第i个元素thrownew UnsupportedOperationException(set(int i, T x)。 /不支持父类方法，覆盖并抛出异常 public Node insert(T x) /在线性表最后插入x元素Nodep=this.head。for(。p.next!=null& pareTo(x)0。)p=p

35、.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&pareTo(p.data)=0。p=p.next)if(pareTo(p.next.data)=0)return p。returnnull。（6）、e、package ex2。publicclass Del1 public Del1(int i,int k)Integer values=1,5,6,10,13。SinglyList li

36、st= new SinglyList(values)。System.out.println( list.toString()。for(int j=0。jk 。j+)list.remove(i)。System.out.println(删除后：+list.toString()。publicstaticvoid main(String args)new Del1(2,2)。f、package ex2。publicclass Del2 public Del2(int mink,int maxk)Integer values=1,3,9,17,34。SortedSinglyList list = new

37、 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()。publicstaticvoid main(String args)new Del2(2,18)。g、package ex2。publicclass Megerpublic Meger()Integer values1=1,2,5,7,9。SortedSinglyList val1=new SortedSinglyList(values1)。Integer values2= 1,0,5,8,9。SortedSinglyList val2=new SortedSinglyList(values2)。SortedSinglyList val=new SortedSinglyList()。int i=0。int j = 0。while(