1、数据结构Java版线性表实现与应用完整版实 验 报 告课程名称数据结构实验工程 线性表的实现及应用实验仪器 PC机一台学 院_专 业班级/学号姓名 实验日期 成 绩 指导教师 北京信息科技大学信息管理学院（数据结构课程上机）实验报告专业:班级:学号:姓名:成绩:实验名称线性表的实现及应用实验地点实验时间1. 实验目的：（1） 理解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会利用顺序表解决实际应用问题。（2） 熟练掌握单链表的使用；理解用链表实现线性表的特点；了解链表的多种形式；学会利用单链表解决实际应用问题。2. 实验要求：（1） 学时为8学时；（2） 能在机器上正确、调试运行程序
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
3、 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）基于单链表实现线性表的以下基本操作（不需要建立接口，直接建立带头结点的单链表类）：ADTList boolean 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）一元多项式的基本运算用排序单链表表示一元多项式，并实现以下基本运算： 一元多项式的建立 一元多项式的减法运算（要求：在运算过程中不能创建新结点 即A=A-B）（8）备份自己程序4. 实验准备：复习教材第2章线性表的知识点熟悉Java编程环境提前熟悉实验内容，设计相关算法5. 实验过程：第一部分：（1）package ex1。publicinterface LList /线性表接口，泛型参数T表示数据元素的数据类型boolean isEmpty()。 /判断线
8、性表是否空int 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 prot
9、ected 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) /构造顺序表，
10、由values数组提供元素，忽略其中空对象 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 NullPoin
11、terException(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.eleme
12、nti = 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()方法，运行时多态f
14、or (int 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()
15、。 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.prin
16、tln(删除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 =v
17、alues.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)
18、 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()。 publicstaticvoid main(String args) newDel2(2,3)。 c)package ex1。publicclass Merge public Merge() Integer values1=1,3,5,11。 SeqList
19、 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.appen
20、d(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()。 publicstaticvoid main(String args)new Merge()。 d) package test。import ex1.SeqList。publicclass Intersection public I
21、ntersection() 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.ge
22、t(i)。i+。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+)，)。 SeqLis
23、t list = 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)获得元素，
24、O(1) publicstaticvoid 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) % list.length()。 /按循环方式对顺序表进行遍历,圆桌循环 System.out.print(出列+list.remove(i).toString()+，)。 /删除i位置对象，O(n)/ System.out.println(list.toString()。 System.out.println(出列
