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

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

2、据结构实验信管16xx_学号J生名.doc。3. 实验内容和步骤：第一部分顺序表的实现与应用（1）基于顺序表实现线性表的以下基本操作：public in terface LList /线性表接口，泛型参数T表示数据元素的数据类型专业word可编辑boolea n isEmpty();/判断线性表是否空int size();/返回线性表长度T get(int i);/返回第i （i M）个元素void set(i nt i, T x);/设置第i个元素值为xvoid in sert(i nt i, T x);/插入x作为第i个元素void in sert(T x);/在线性表最后插入x元素T r

3、emove(i nt i);/删除第i个元素并返回被删除对象int search（T key）; /查找，返回首次出现的关键字为key的元素的位序void removeAII();/删除线性表所有元素public String toString（）;返回顺序表所有元素的描述字符串，形式为要求：实现后应编写代码段对每个基本操作做测试。（2）顺序表的简单应用a）运用基本操作编写算法删除第i个开始的k个元素。b）编写高效算法删除第i个开始的k个元素。c）将两个顺序表合并为一个顺序表（表中元素有序）；d）若两个元素按值递增有序排列的顺序表 A和B,且同一表中的元素 值各不相同。试构造一个顺序表C，其元

4、素为A和B中元素的交集，且 表C中的元素也按值递增有序排列；（3） 利用顺序表解决约瑟夫环问题：已知n个人（以编号1，2, 3.n分别表 示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去， 直到圆桌周围的人全部出列。要求：输出出列次序。第二部分单链表的实现与应用(4) 基于单链表实现线性表的以下基本操作 结点的单链表类)：ADT Listboolea n isEmpty();int size();T get(i nt i);void set(i nt i, T x);Node in sert(i nt i,

5、T x); Node in sert(T x);T remove(i nt i);象void removeAll();Node search(T key);key元素public String toString();串，形式为“(，)”(不需要建立接口，直接建立带头/判断线性表是否空/返回线性表长度/返回第i (iX)个元素/设置第i个元素值为x插入x作为第i个元素/在线性表最后插入x元素/删除第i个元素并返回被删除对/删除线性表所有元素/查找，返回首次出现的关键字为/返回顺序表所有元素的描述字符要求：实现后应编写代码段对每个基本操作做测试(5)实现单链表的子类排序单链表,覆盖单链表如下方法：

6、void set(i nt i, T x);Node in sert(i nt i, T x);Node in sert(T x);Node search(T key);/设置第i个元素值为x插入x作为第i个元素/在线性表最后插入x元素/查找，返回首次出现的关键字为key(6) 基于排序单链表实现线性表的以下综合应用：e) 删除第i个开始的k个元素。f) 删除递增有序单链表中所有值大于mink且小于maxk的元素。g) 将两个单链表合并为一个单链表，保持有序。h) 若两个元素按值递增有序排列的单链表A和B,且同一表中的元素值各不相同。试构造一个单链表C，其元素为A和B中元素的交集，且表C 中的

7、元素也按值递增有序排列。要求利用原有链表中的元素。(7) 一元多项式的基本运算用排序单链表表示一元多项式，并实现以下基本运算：一元多项式的建立一元多项式的减法运算(要求：在运算过程中不能创建新结点即A=A-B)(8) 备份自己程序4. 实验准备：复习教材第2章线性表的知识点熟悉Java编程环境提前熟悉实验内容，设计相关算法5.实验过程：第一部分：(1)package exl;public in terface LList/线性表接口，泛型参数T表示数据兀素的数据类型boolea n isEmpty();/判断线性表是否空int length();/返回线性表长度T get( int i);/返

8、回第i ( i 0个元素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的元素的位序类名：public class SeqListimpleme ntsLList protected Object element ;protected int n;public S

9、eqList( int length)this .element = new Objectlength;元素为null。/若length0 , Java抛出负数组长度异常java .Ian g.NegativeArraySizeExcepti onthis .n = 0;public SeqList()构造方法重载this (64);参数列表的构造方法public SeqList(T values)/构造容量为length的空表/申请数组的存储空间/创建默认容量的空表/调用本类已声明的指定II构造顺序表，由values数组提供元素，忽略其中空对象this (values, length *2)

10、;/ 创建 2倍values 数组容量的空表/若values=null,用空对象调用方法，Java抛出空对象异常NullPoi nterExceptio nfor (int i=0; i C个元素if (i=0 & i=0 & i this .n)this .element i = x;else throw new java.lang.lndexOutOfBoundsException(i+);/ 抛出序号越界异常public int insert( int i, T x)/ 插入x作为第 个元素if (x= null )throw new NullPointerException( x=nu

11、ll );/ 抛出空对象异常if (i this .n) i=this .n;Object source = this .element ;source也引用element数组if (this .n= elementength )顺序表的数组容量大的数组this .element = new Objectsource. length *2; for (int j=0; j=i; j-)后移动，次序从后向前this .element j+1 = sourcej;this .element i = x;this .n +;return i;public int append(T x)/在线性表最后

12、插入 return this .insert( this .n, x);public T remove( int i)/删除第i个元素并返回被删除对象if (this .n0 & i=0 & i this .n)T old = (T) this .element i;/old 中存储被删除元素for (int j=i; j this .n-1; j+)this .element j = this .element j+1;/ 元素前移一个位置this .element this .n-1= null ;/ 设置数组元素对象为空，释放原引用实例this .n-;return old;/返回old

13、局部变量引用的对象，传递对象引用return null ;public void removeAII()/删除线性表所有元素this .n=0;public int search(T key)的元素的位/查找，返回首次出现的关键字为 keySystem. out .print( this .getClass().getName()+.indexOf(” +key+ ),);for (int i=0; i0)str += this .element 0.toString();运行时多态for (int i=1; i this .n; i+)str += , + this .element i.t

14、oString();行时多态/返回类名/执行T类的toString()方法,/执行T类的toString()方法，运return str+ )public static void main (String args)SeqList list=new SeqList(20);In teger values=10,1,2,3,4,5,6,7,8,9;SeqList list仁new SeqList(values);System. out .print(输出顺序表:);System. out .printin(list1.toString();System. out .println(顺序表 Lis

15、t是否为空+list.isEmpty()+ ,Listl 是否为空+list1.isEmpty();System. out .println( list 的长度+list.length()+ ,list1 的长度+list1.length();System. out .println(返回 listl 的第 7个元素是:+list1.get(6);System. out .println(重新设置第5个元素为19:);list1.set(4, 19);listl.i nsert(2, 100);listl.appe nd(20);System. out .println(删除 8:+list1

16、.remove(8);System. out .print(修改后的顺序表:);System. out .printin(listl.toString();list1.removeAII();System, out .println(删除后的顺序表：+list1.toString();/ 为空System. out .println(寻找元素 50:+list1.search(50);输出顺序(10, 1, 2t 3, 4, 5, 6, 7, 6顺序表Lint是否为空truef Listl是否为空false“眦的长度6 就i的长应W返回lim匸1的第个元素是：6 重新设置金5个元素为19 :删

17、除3: 7修改后的顺序表 :exl - SeqList (10100f 2 r 3 f 19# 5, 6Z 6 f 9 r 20 删協后盼l|5序衰：exl. SeqLi3t Qex 1.3eqL ist * indexOf (50) 寻找兀素SO: -1(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=O;jn;j+)System. out .print(valuesj+ );S

18、ystem. 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);AbCdefghA b g hb) package exl;public class Del2 public Del2( int i, int k)String values= A ,x, y ,y ,b ,c, h;

19、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);th, y,j h)SeqList (A, x, cf h)c)package exl;public class Merge public Merge()In teger values1=1,3,5,11;SeqL

20、ist list仁new SeqList(values1);In teger values2=2,4,5,22,23;SeqList list2=new SeqList(values2);SeqList list3=new SeqList();int i=O,j=O;while (ilist1.length()&jlist2.length()if (list1.get(i)list2.get(j)list3.appe nd(list1.get(i);i+；else Iist3.appe nd(list2.get(j);j+；while (ilist1.length()Iist3.appe nd

21、(list1.get(i);i+；while (jlist2.length()list3.append(list2.get(j);j+；System. out .printin(listl.toString();System. out .println(list2.toString();System. out .println(list3.toString();public static void main(String args)new Merge();k I i-x吁T 亍 | n exl,SeqLisv(1. 3S, 11)exl.SsqList(2, 4, 5, 22t 23)exl.

22、SeqList(1, 2, 35, 511, 22r 23)d)package test;import ex1.SeqList;public class In tersect ion publicIn tersect ion()Integer values1 =1,3,5,11,12,13,22,23,50;SeqListlist1 = new SeqList(values1 );Integer values2 =2,4,5,12,19,20,22,23,;SeqListlist2 = new SeqList(values2 );SeqList Iist3 = new SeqList();in

23、ti=0,j=0；while (i listl .length()& j Iist2 .length()if(list1 .get( i)list2 .get( j)j+;elselist3 .append( list1 .get(i);i+;j+;System. out .println( listl .toString();System. out .println( list2 .toString();System. out .println( list3 .toString();public static void main(Stringargs )new Intersection();

24、terminated? Intersection Java Application C:Program FilesJavajdk1KU 121binjavaw.exe exl.SeqList(1,3 f 5,11,12,13f22,23f50)exl.SeqList(会”5,12,19,20f22,23)exl.SeqList(5, 121 221 23)3.(1)package ex1;public class Josephus public Josephus( int n, int k, int m)System. out .println( Josephus( +n + ，+ k+ ，+

25、 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位置对象，0(n)/System.out.pri ntln( list.toStri ng();System, out .println(”出列

26、+list.get(0).toString(); get(0)获得元素,0(1)public static void main(Stringargs )new Josephus(9,1,3);Josephus(9,1* 3),出列4,出列7,出列匚出列5,出列9,出列&出列办出列8,出列2(2)package test;import ex1.SeqList;public class JosephusA public JosephusA( int n, int k, int m)System. out .println( Josephus( + n + ，+ k+, + m+ )，);SeqLi

27、stlist = 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.pri ntln( list.toStri ng();System, out .println(出列+list .get(0).toString();

28、get(0)获得元素,0(1)public static void main(Stringargs )new JosephusA(15,2,9);Joaephus(15,2,9)-出列10,出列心 出列14,出列出列乩 出列乳 出列2,出列乩 出列 出列13,出列11,出列12,出列片 出列0出列1第二部分：(4 )、package ex2;public class Node public T data ;/ 数据域public Node next ;/地址域，后继结点/构造结点public Node(T data,Node next) this .data =data;this .next

29、= next;/构造空结点public Node()this (null ,null );/描述字符串public String toString() return this .data .toString();package ex2;public class Sin glyList public Node head ;/构造空单链表public SinglyList()head = new Node();/构造单链表，由values数组数组提供元素public SinglyList(T values)this ();Noderear= this .head ;for (int i=O;iva

30、lues. 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 ( i C个元素Nodep= head .next ;for (int j=O;p!= null &j=0) ? p. data :null ;public void set( int i, T x)/ 设置第 i个元素值为 xif (x= null )throw new

31、NullPointerException(x=null );/ 抛出空对象异常Nodep= this .head .next;0for (int j=O;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;插入x作为第i个元素 public Node insert( int i, T x)if (x= null ) throw new Nodefr ont= for (int j=O;front

32、. fron t=fr ont.NullPoi nterExceptio n( this .head ;next != null &ji;j+) next;x=null);/指定头结点/以此循环找i-1front, next = new Node(x,front.next );return front. next;public Node insert(T x)/抛出空对象异常/front指向头结点 if (x= null )throw new NullPointerException(x=null);Node front= this .head ;for (; front. next != n

33、ull ;)/寻找第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 ;for (int j=O;ji&p.next != null ;j+)p=p. next;if (p. next != null )T old=p. next .data ;p.next =p. next

34、 .next;return old;return null ;public void removeAII()/删除线性表所有元素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= t

35、his .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+ );数组为空；false返回元義！ D设矍元寿；ex2.SinglyList(A,B5D，EF)统性喪长廈：6ffiASS ex2, Si nglyLi s t ( At BjSjXjDjEjF)删瞧第二伞元善：为查找关镖学；A删瞬斤有元畚

36、ex2,SinglyList ()查找关键宇；null(5 )、package ex2;public class SortedSinglyListTextends Comparable extendsSi nglyList/构造空排序单链表public SortedSinglyList()super ();/默认调用父类构造方法 SinglyList()public SortedSinglyList(SinglyList list)super ();/构造空单链表for (Node p=list.head . next ; p!= null; p=p. next)/ 直接插入排序，每趟插入1个

37、元素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个元素值为 xthrow new UnsupportedOperationException(set(int i, T x) );/不支持父类方法，覆盖并抛出异常public Node insert(int i, T x

38、)插入 x作为第 个元素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

39、 (Nodep= this .head ;p.next != null &pareTo(p.data ) list=new SinglyListVnteger(values);System. out .println( list.toString();for (int j=O;j 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+；whil

40、e (p.next! =null &p. next .data maxk)list.remove(j);System. out .println( list= +list.toString(); public static void main(String args)new Del2(2,18);iLEi 11 illwi pj lz. f l|ex2. SortedSinglyList (1?9 1734 P list=ex2.SortedSinglyListflj 34)g、package ex2;public class Megerpublic Meger()In teger value

41、s仁1,2,5,7,9;new SortedSinglyList(values1);SortedS in glyList val1 =In teger values2= 1,0,5,8,9;SortedS in glyList val2=new SortedSinglyList(values2);SortedS in glyList val= new SortedSinglyList();int i=0; int j = 0;while (ival1.size()&jval2.size() if (val1.get(i)=val2.get(j)val.i nsert(val1.get(i);i

42、f (val1.get(i)=val2.get(j)j+;i+;elseval.i nsert(val2.get(j);j+;while (ival1.size()val.i nsert(val2.get(i);i+;while (jval2.size()val.i nsert(val2.get(j);j+；System. out .println(vall.toString();System. out .println(val2.toString();System. out .println(val.toString();public static void main(String args

43、)new Meger(); Meger java Appii 匚日 ticinj u:iviytcii psecommonA|bx2 . SortedSinglyList (9,7,5,2 1) ex2.SortedS in glyList (9,8,5, 1?0) ex2.SortedSinglyList(955,21?10)、package Poly;public in terface Subible/可相加接口，T表示数据元素的数据类型public void sub(T t);/+=加法，约定两兀素相加规则public boolean removable。；/约定删除元素条件packag

44、e Poly;/项类，一兀多项式的一项，实现可比较接口和可相加接口public class TermX implements Comparable, Subibleprotected int coef, xexp ;/系数，X指数(可为正、0)public TermX( int coef, int xexp)/构造一项this .coef = coef;this .xexp = xexp;public TermX(TermX term)/拷贝构造方法this (term. coef, term. xexp);/以 系数xA指数”的省略形式构造一元多项式的一项。/省略形式说明：当系数为1或-1且指数0时，省略1 , -1只写负号-”，如xA2、-xT ;/当指数为0时，省略xA0，只写系数；当指数为public TermX(String termstr)if (term