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

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

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

3、线性表最后插入 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 isEmp

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

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

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

8、验内容，设计相关算法5. 实验过程：第一部分：（ 1）packagepublicex1;interfaceLList<T>/线性表接口，泛型参数T 表示数据元素的数据类型booleanisEmpty();/判断线性表是否空intlength();/返回线性表长度T get(inti);/ 返回第 i （ i 0）个元素voidset(inti, T x);/ 设置第 i 个元素值为 xintinsert(inti, T x);/插入 x 作为第 i 个元素intappend(T x);/在线性表最后插入x 元素T remove(inti);/删除第 i 个元素并返回被删除对象voi

9、dremoveAll();/删除线性表所有元素intsearch(T key);/查找，返回首次出现的关键字为key的元素的位序类名：publicclassSeqList<T>implementsLList<T> protectedObjectelement;protectedintn ;publicSeqList(intlength)/构造容量为length的空表this. element=new Objectlength;/申请数组的存储空间，元素为null。/若length<0java.lang.NegativeArraySizeExceptionthis.

10、 n = 0;， Java抛出负数组长度异常publicSeqList()/创建默认容量的空表，构造方法重载this(64);/调用本类已声明的指定参数列表的构造方法publicSeqList(T values)/构造顺序表，由 values 数组提供元素，忽略其中空对象this(values.length*2);/创建 2倍values数组容量的空表/若values=null，用空对象调用方法，Java抛出空对象异常NullPointerExceptionfor( int组元素。 O(n)i=0; i<values.length; i+)/复制非空的数if(valuesi!=null)

11、this. element this. n += valuesi;/对象引用赋值publicbooleanisEmpty()/ 判断线性表是否空returnthis. n=0;publicreturnintlength()this. n ;/返回线性表长度publicT get(inti)/返回第i （ i 0）个元素if(i>=0 && i<this. n )return(T)this. elementi;/ 返回数组元素引用的对象，传递对象引用/return this.elementi;/编译错，Object对象不能返回T对象returnnull;publicv

12、oidset(inti, T x)/设置第i个元素值为xif(x= thrownull)new NullPointerException("x=null");/抛出空对象异常if(i>=0 && i<this. n )this. elementi = x;elsethrownewjava.lang.IndexOutOfBoundsException(i+"" ); /抛出序号越界异常publicintinsert(inti, T x)/插入 x 作为第 i个元素if(x=nullthrow)new NullPointerExc

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

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

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

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

17、nt0.toString();toString()方法，运行时多态"("/返回类名/执行 T类的forstr +=( inti=1; i< ", "this +this. n; i+) . elementi.toString();/执行 T类的toString()方法，运行时多态returnstr+") "publicstaticvoidmain (String args)SeqList<Integer> list=new SeqList<Integer>(20);Integer values=10,1,

18、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的长度 " +li

19、st.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)packageex1;publicclassDel publicDel(inti,intk)String values="A" , "b" , "C&quo

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

22、();" ");publicstaticvoidmain(String args)new Del(2,3);b)packageex1;publicclassDel2 publicDel2(inti,intk)String values="A" , "x", "y", "y", "b", "c", "h" ;SeqList<String> list=new SeqList<String>(values);Syste

23、m.out .println(list.toString();for( intj=1;j<=k;j+) list.remove(i);System.out .println(list.toString();publicstaticvoidmain(String args)new Del2(2,3);c)packageex1;publicclass publicMerge Merge()Integer values1=1,3,5,11;SeqList<Integer> list1=new SeqList<Integer>(values1);Integer value

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

25、le(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();publicstaticvoidmain(String args)new Merge();d)packageimportpublictest;ex1.SeqList;

26、classIntersection publicIntersection()Integervalues1=1,3,5,11,12,13,22,23,50;SeqList<Integer>list1= new SeqList<Integer>(values1);Integervalues2=2,4,5,12,19,20,22,23,;SeqList<Integer>list2= new SeqList<Integer>(values2);SeqList<Integer>list3= new SeqList<Integer>(

27、);inti =0, j =0;while( i <list1.length()&&j <list2.length()if( list1.get(i )< list2.get(j )i +;elseif( list1.get(i )> list2.get(j )j +;elselist3.append(list1.get(i );i +;j +;System.out.println(list1.toString();System.out.println(list2.toString();System.out.println(list3.toString(

28、);publicstaticvoidmain(Stringargs)new Intersection();3.（ 1）packageex1;publicclassJosephus publicJosephus(intn ,intk ,intm)System.outSeqList<String>.println(list"Josephus("+ n+ ","+k + ","+m+") ， " );=new SeqList<String>(n );/创建顺序表实例，元素类型是数字字符，只能排到n

29、=9,否则达不到效果for( inti =0;i <n;i +)list.append(char)('1'+ i )+ "");/顺序表尾插入， O(1)/System.out.println(list.toString();/输出顺序表的描述字符串，O(n)inti =while(元素时循环，计数O(1)k ; list.length()>1)/计数起始位置/ 多于一个i= (i + m-1) %list.length();/按循环方式对顺序表进行遍历, 圆桌循环" );System./删除 i 位置对象，out O(n).print

30、(" 出列" + list.remove(i ).toString()+" ，/ System.out.println(list.toString();System.out .println(" 出列" +list.get(0).toString();/get(0)获得元素，O(1)publicstaticvoidmain(Stringargs)new Josephus(9,1,3);（ 2）packagetest;importex1.SeqList;publicclassJosephusA publicJosephusA(intn ,intk

31、 ,intm)System.out .println("Josephus("+n +","+k+ ","+ m+ ") ， " );SeqList<Integer>list=new SeqList<Integer>(n);/创建顺序表实例，元素类型是数字字符，只能排到n=9,否则达不到效果for(inti =0;i < n;i +)list.append(i );/顺序表尾插入，O(1)/System.out.println(list.toString();/输出顺序表的描述字符串，O

32、(n)inti=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.println(list.toString();" +listSystem.get(0).toString();out .println(/get(0)&q

33、uot; 出列获得元素， O(1)publicstaticvoidmain(Stringargs)new JosephusA(15,2,9);第二部分：（ 4）、packageex2;publicclassNode<T> publicpublicT data ; Node<T>next ;/ 数据域/ 地址域，后继结点/ 构造结点publicNode(T data,Node<T> next)this. data=data;this. next =next;/ 构造空结点publicNode()this( null, null);/ 描述字符串publicSt

34、ring toString()returnthis. data .toString();packageex2;publicclassSinglyList<T> publicNode<T> head ;/ 构造空单链表publicSinglyList()head =new Node<T>();/ 构造单链表，由 values 数组数组提供元素publicSinglyList(T values)this();Node<T>rear=this. head ;for ( inti=0;i<values.length;i+)rear.nextrear

35、=rear.=new Node<T>(valuesi,next ;null);publicbooleanisEmpty()/ 判断线性表是否空returnthis. head . next= null;publicT get(inti)/ 返回第i （ i0）个元素Node<T>p= head . next;for ( intj=0;p!=null&&j<i;j+)p=p. next ;return(p!=null&&i>=0) ? p.data : null;publicvoidset(inti, T x)/ 设置第i 个元

36、素值为xif(x= null)thrownew NullPointerException("x=null");/ 抛出空对象异常Node<T>p= this. head . next ;/0for ( intj=0;p!=null&&j<i;j+)/ 遍历寻找第i 个结点（p指向）p=p. next ;if(i>0&&p!=null)p. data =x;publicintsize()/ 返回线性表长度inti=0;for (Node<T>p= this. head . next ;p!= null;p=p

37、.next )i+;returni;publicNode<T> insert(inti, T x)/ 插入 x 作为第 i 个元素if(x= null)thrownew NullPointerException("x=null");Node<T>front=this. head ;/ 指定头结点for ( intj=0;front.next != null&&j<i;j+)front=front.next ;/ 以此循环找front.next =new Node<T>(x,front.next);returnfron

38、t.next ;i-1publicNode<T> insert(T x)if(x=null)thrownew NullPointerException(Node<T> front=this. head ;for(; front.next != null;)front = front.next ;front.next= new Node<T>(x,front.包括头插入、中间/ 尾插入"x=null"/ 寻找第 i-1next ););/ 抛出空对象异常/front指向头结点个或最后一个结点（front指向）/ 在 front之后插入值为x

39、 结点，returnfront.next ;publicT remove(inti)/删除第 i个元素并返回被删除对象Node<T>p= this. head ;/ 让 p指向头结点for ( intj=0;j<i&&p.next != null;j+)p=p. next ;if(p. next != null)T old=p.next . data;p. next =p. next . next ;returnold;returnnull;publicvoidremoveAll()/ 删除线性表所有元素this. head . next =null;/ 让头结点直接为空publicNode<T> search(T key)/ 查找，返回首次出现的关键字为key 元素