大数据结构线性表地实现与应用完整版

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

2、步骤:第一部分顺序表的实现与应用(1) 基于顺序表实现线性表的以下基本操作:public in terface LList<T> /线性表接口，泛型参数T表示数据元素的数据类型boolea n isEmpty();判断线性表是否空int size();/返回线性表长度T get(int i);/返回第i (i >0)个元素void set(i nt i, T x);设置第i个元素值为xvoid insert（int i, T x）;插入x作为第i个元素void insert（T x）;在线性表最后插入x元素T remove（int i）;删除第i个元素并返回被删除对象int

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

4、利用顺序表解决约瑟夫环问题：已知 n个人（以编号1, 2, 3n分别表示） 围坐在一圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一 个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周 围的人全部出列。要求：输出出列次序。第二部分单链表的实现与应用（4）基于单链表实现线性表的以下基本操作（不需要建立接口，直接建立带头结点的单链表类）：ADT List<T>boolea n isEmpty();判断线性表是否空int size();/返回线性表长度T get(i nt i);/返回第i （i >0）个元素void set(i nt i, T x

5、);设置第i个元素值为xNode<T> in sert(i nt i, T x);/插入x作为第i个元素Node<T> in sert(T x);在线性表最后插入x元素T remove(i nt i);删除第i个元素并返回被删除对象void removeAII();删除线性表所有元素Node<T> search(T key);/查找，返回首次出现的关键字为key儿糸public Stri ng toStri ng();/返回顺序表所有兀素的描述子符串，形式为要求：实现后应编写代码段对每个基本操作做测试。（5）实现单链表的子类排序单链表，覆盖单链表如下方法：v

6、oid set(i nt i, T x);/设置第i个元素值为xNode<T> in sert(i nt i, T x);/插入x作为第i个元素Node<T> in sert(T x);/在线性表最后插入x元素Node<T> 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 exl; public in terface LList<T>II线性表接口，泛型参数T表示数据元素的数据类型boolea n isEmpty();intlen gt

8、h();T get( int i); void set( int i, T x); intin sert(int i, T x);intappe nd(T x);T remove( int i); void removeAll(); int search(T key);的位序II判断线性表是否空II返回线性表长度II返回第i (i >0)个元素II设置第i个元素值为xII插入x作为第i个元素II在线性表最后插入x兀素II删除第i个元素并返回被删除对象II删除线性表所有元素II查找，返回首次出现的关键字为key的元素类名:publicclass SeqList<T>implem

9、e ntsLList<T> protected Object eleme ntprotectedint n;II构造容量为II申请数组的存public SeqList( intlen gth)len gth的空表this . element = new Objectlength;储空间，元素为null。II若length<0, Java抛出负数组长度异常java .Ian g.NegativeArraySizeExcepti onthis . n = 0;II创建默认容量的II调用本类已声明的public SeqList()空表，构造方法重载this (64);指定参数列表的

10、构造方法II构造顺序表,public SeqList(T values)由values数组提供元素，忽略其中空对象this (values. len gth *2);values 数组容量的空表/若values=null，用空对象调用方法,/创建2倍Java抛出空对象异常/复制非空的数for ( int i=0; i<values.len gth ; i+)组兀素。O(n)if (valuesi!=n ull)this . elementthis . n + = values"/对象引用赋值NullPoi nterExceptio npublicboolea nisEmpty(

11、)returnthis.n=0;publicintlen gth()returnthis . n;/判断线性表是否空/返回线性表长度publicT get( inti)if(i>=0 && i<this . n)return (T)this . element i;兀素引用的对象，传递对象引用返回第i (i >0)个元素/返回数组编译错,/设置第i个元素值为x/ return this.eleme nti;/Object对象不能返回T对象return n ull ;public void set( int i, T x)if (x= n ull )throw

12、new NullPointerException("x=null");/ 抛出空对象异常if (i>=0 && i< this . n)this . element i = x;else throw newjava.lang.lndexOutOfBoundsException(i+"" ); / 抛出序号越界异常public int insert( int i, T x)/ 插入 x 作为第 i 个元素if (x= n ull )throw new NullPoi nterExceptio n("x=null&quo

13、t;);/ 抛出空对象异常if (i<0)i=0;/插入位置i容错，插入在最前if (i> this . n) i= this . n;Object source =this引用赋值，source 也引用element数组.elementif ( this . n= = element . length )则扩充顺序表的数组容量/插入在最后/数组变量/若数组满,this . element = new Objectsource. 请一个容量更大的数组for ( int j=0; j<i; j+)组前i-1个元素this . element j = sourcej;for (

14、int j= this . n-1; j>=i; j-)至表尾的元素向后移动，次序从后向前this . element j+1 = sourcej;len gth*2;/重新申/复制当前数II从i开始this . element i = x; this . n +;II返回x序号return i;publicintappe nd(T x)II在线性表最后插入x兀素return this.insert(this . n, x);public T remove( int i)II删除第i个元素并返回被删除对象if ( this .n>0 && i>=0 &

15、& i< this . n)T old = (T)this . element i;IIold 中存储被删除元素for ( int j=i; j< this . n-1; j+)this . element j= this . elementj+1;II 元素前移一个位置this . element this .n -1= null ;II 设置数组元素对象为空，释放原引用实例this . n-;return old;II 返回 old 局部变量引用的对象，传递对象引用return n ull ;publicvoid removeAII()II删除线性表所有元素+key+

16、")，");/执行T类/返回类名II执行T类的/执行T类的this . n=0;/查找，返回首次出现的关键public int search(T key)字为key的元素的位System. out .print(this .getClass().getName()+".indexOf(”for ( int i=0; i< this . n; i+)if (key.equals( this . elementi)的equals(Object) 方法，运行时多态return i;return -1;publicStri ng toStri ng()Stri ng

17、 str= this .getClass().getName()+"("if ( this . n>0)str +=this . element 0.toString();toStri ng()方法，运行时多态for ( int i=1; i< this . n; i+)str +=", " +this . element i.toString();toStri ng()方法，运行时多态return str+ ")"public static void main (Stri ng args) SeqList< In

18、teger> list=new SeqList< In teger>(20);In teger values=10,1,2,3,4,5,6,7,8,9;SeqList< In teger> list1=new SeqList< In teger>(values);System.out.pri nt("输出顺序表：”)；System.out.pri ntln (listl.toStri ng();System.out.pri ntl n("顺序表List是否为空"+list.isEmpty()+",List1是否为

19、空"+list1.isEmpty();System.out.pri ntl n("list 的长度 ” +list.length()+",list1"+list1.le ngth();System.out.pri ntl n("返回listl的第7个兀素是:"+list1.get(6);System.out.pri ntl n("重新设置第5个元素为19:");list1.set(4, 19);的长度listl.i nsert(2, 100);listl.appe nd(20);System. out .print

20、ln(” 删除 8:" +Iist1.remove(8);System. out .print("修改后的顺序表:");System. out .println(list1.toString(); list1.removeAll();System.out .println(” 删除后的顺序表："+list1.toString();/为空System.out .println(” 寻找元素 50:" +list1.search(50);输出晒序表 :exl -SeqList. (10 1# J 3” 呛# 5, 6, 7f 3, 3)*曲序為Li

21、mt是:否衣空txumrlAmtl是否为空false 丄iwt的长度长度M返回“丸丄的第7个元素是;日重新设置第5个元素为归：删除8 ：7修改后的顺序表 :» SeqLit (i0f 1 f 100 f 2 f 3 f 19 f 5 f 8卢 20) 刪除后的顺序表；axl. SeqList _exl ,SeqLlst, indlexOf (50) ? 寻找兀素50 : -1(2)a)package ex1;public class Del public Del( int i, int k)String values="A" , "b" , &

22、quot;C" , "d" , "e"，”f" , "g" , "h" ;int n =values. len gth ;for ( int j=0;j<n;j+)System.out .print(valuesj+" ");System.out .println();for ( int j=i+k;j<n;j+) valuesj-k=valuesj; n=n _k;for ( int j=0;j<n;j+)II II);System.out .print(

23、valuesj+System.out .println();publicstatic voidmain( Stri ng args)new Del(2,3);Abe1g *hA b fb)package ex1;public class Del2 public Del2( int i,String values=SeqList<Stri ng> list=int k)"A" , "x" , "y" , "y" , "b"IIc" , "h" ;new S

24、eqList<Stri ng>(values);new SeqList< In teger>(values1);System.out .println(list.toString();for ( int j=1;j<=k;j+) list.remove(i);System.out .println(list.toString();public static void main( Stri ng args)new Del2(2,3);.習记Li目匸(Ar x, g匚h)exl.SeqLlstx, c, hjc)package ex1;public class Mer

25、ge public Merge()In teger values1=1,3,5,11; SeqList< In teger> list仁In teger values2=2,4,5,22,23;SeqList< In teger> list2=SeqList< In teger> list3=new SeqList< In teger>(values2);new SeqList< In teger>();int i=O,j=O;while (i<list1.le ngth()&&j<list2.le ngt

26、h()if (list1.get(i)<list2.get(j)list3.appe nd(list1.get(i); i+; else list3.appe nd(list2.get(j); j+;while (i<list1.le ngth() list3.appe nd(list1.get(i); i+;while (j<list2.le ngth()list3.append(list2.get(j);j+;System.out.println( list1.toStri ng();System.out.pri ntln( list2.toStri ng();Syste

27、m.out.pri ntln( list3.toStri ng();public static voidmain( Stri ng args)new Merge();口 I "i b bejcl.SeqList (1, 3, 5r 11)eKl 注亡国11工3匚(2/4,5j. 22z S3)ezl,5eciLlst (1, J 3f % 5f 5r 11# 22f 23d)package test;import exl.SeqList;public class In tersect ion publicIn tersect ion()In tegervalues1SeqList&l

28、t; In teger>In tegervalues2SeqList< In teger>=1,3,5,11,12,13,22,23,50;list1 =new SeqList< In teger>(=2,4,5,12,19,20,22,23,;list2 =new SeqList< In teger>(values1 );values2 );SeqList< In teger>list3 =new SeqList< In teger>();int i =0, j =0;while (i <list1ength()&

29、;&j <list2.length()if (list1 .get( i )< list2 .get( j )i +;else if ( list1 .get( i )> list2 .get( j ) j +;else list3.append(list1 .get( i );i +;j +;System.out.pri ntl n(list1.toStri ng();System.out.pri ntl n(list2.toStri ng();System.out.pri ntl n(list3.toStri ng();public static voidmain

30、(Stringargs )new In tersecti on();<terminated* Intersection |Jdvd Applkdtionl C:Fiogram KilcsJdjajdk1.8.0 121binjdvdw.exe exl.SeqList(1,戈 5f 11, 12, 13, 22, 23, 50)&xl-SGqList(2r5 12, 19f 20, 22f 23)exl,SeqList(5f 12f 22, 23顺序表尾3.插入，O(1)/顺序表的描述字符串,System.out.pri ntln (list.toStri ng();O(n)/输出

31、int i = k; while ( list元素时循环，计数O(1).len gth()>1)/计数起始位置/多于一个i =(序表进行遍历，圆桌循环System.");/删除i位置对象,+ m-1) % list .le ngth();out .print("出列"+ listO(n).remove(/按循环方式对顺i ).toString()+IIpackageex1;publicclassJosephus publicJosephus(int n,int k, int m)1System.out.println("Josephus(”+n +

32、 "," +k + ","+m+"),"SeqList<Stri ng>list=new SeqList<Stri ng>(n)；/创建顺序表实例，兀素类型是数字字符，只能排到则达不到效果for(int i=0; i <n;i +)(1)n=9,否/);list.append(char )( '1' +i )+"");/ System.out.pri ntln( list.toStri ng();System.out .println( "出列"+l

33、ist .get(0).toStri ng();get(O)获得元素，0(1)public static voidmain(Stringargs )new Josephus(9,1,3);Josephus(9,1f 3)出列4出列7.出列1,出列5出列9出列&出列3,出列出列2public JosephusA( int n, int k, System.outSeqList< In teger>int m)+n +"," +k+","n=9,否则达不到效果for/.println( "Josephus(”list = new

34、 SeqList<I nteger>(创建顺序表实例，元素类型是数字字符,/+ m+"),");n)；只能排到i <n; i +)i );(int i list.appe nd(System.out.pri ntln (list.toStri ng();=0;/顺序表尾插入，O(1)输出顺序表的描述字符串，O(n)int i = k;while ( list ength()>1)一个元素时循环，计数O(1)i = ( i +m-1) % list.len gth();对顺序表进行遍历，圆桌循环System.out .print( "出列&q

35、uot;+list .remove( i ).toString()+"， " );/ 删除 i 位置对象,/计数起始位置/多于/按循环方式0(n)(2)packagetest;importexl.SeqList;publicclass JosephusA / System.out.pri ntln( list.toStri ng();System.out .println(” 出列"+list .get(0).toStri ng();get(0)获得元素，0(1)public static void main(Stringargs )new JosephusA(1

36、5,2,9);Josephus (IS*2 r 9)也6,出如心r出舛9,出呵鼠出列工出列2,出列出:削乱出列丄3,出列匕，出列丄上列7二也，出列丄第二部分：(4) 、package ex2;public class Node<T> public T data ;/ 数据域public Node<T> next ;/地址域，后继结点/构造结点public Node(T data,Node<T> n ext)this . data =data;this . next =next;/构造空结点public Node()this (null , null );/描

37、述字符串publicStri ng toStri ng()return this . data .toString();package ex2;public class Sin glyList<T> public Node<T> head ;/构造空单链表public Sin glyList()head =new Node<T>();/构造单链表，由values数组数组提供元素public Sin glyList(T values)this ();Node<T>rear= this . head ;for (int i=O;i<values

38、. length;i+)rear. next =new Node<T>(valuesi, null ); rear=rear.next ;publicboolean isEmpty()/判断线性表是否空returnthis . head . next = null ;public T get( int i)/ 返回第 i (i >0 个元素Node<T>p= head . next ;for (int j=O;p!= null &&j<i;j+)p=p. next ;return (p!= null &&i>=0) ?

39、p. data : null ;public void set( int i, T x)/ 设置第 i 个元素值为 xif (x= null )throw new NullPointerException("x=null");/抛出空对象异Node<T>p= this . head . next ;0/遍历寻找第i个结点（pfor (int j=O;p!= null &&j<i;j+)指向)p=p. next ;if (i>0&&p!= null )p. data =x;public int size()/返回线性表长

40、度int i=0;for (Node<T>p= this . head . next ;p!= null ;p=p. next )i+;return i;/插入x作为第i个元素publicNode<T> in sert(int i, T x)if (x= null )throw new NullPointerException(Node<T>front= this . head ;"x=n ull");/指定头结点for (int j=0;front.next != null &&j<i;j+)fron t=fr o

41、nt.n ext以此循环找i-1front, next =new Node<T>(x,front.next );returnfront. next ;public Node<T> in sert(T x) if (x= null )throw new NullPoi nterExceptio n(Node<T> front=this . head ;for (;fron t.next != null ;)front =fron t.n ext ;fron t.n ext=new Node<T>(x, front包括头插入、中间/尾插入"

42、x=null"）;/抛出空对象异常/front 指向头结点/寻找第i-1个或最后一个结点（front指向）next ）;/在front之后插入值为x结点,return front.n extpublic T remove( int i)/删除第i个元素并返回被删除对象Node<T>p= this . head ;for (int j=O;j<i&&p.next != null ;j+)p=p. next ;if (p. next != null )T old=p. next .data ;p. next =p. next.next ;return o

43、ld;returnnull ;/让p指向头结点public void removeAII() /删除线性表所有元素this . head . next =null/让头结点直接为空public Node<T> search(T key)/查找，返回首次出现的关键字为key元素for (Node<T> p =this . head ;p. next != null;p=p. next )if ( key.equals(p. data )return p;return null ;public StringtoString()/返回顺序表所有元素的描述字符串，形式为(，)”

44、String str= this .getClass().getName()+ "(" ;/ 返回类名for (Node<T> p= this . head . next ; p!= null ; p=p. next ) /p 遍历单链表 str += p.data .toString();if (p. next != null )str+=","；/不是最后一个结点时，加分隔符return str+ ")"数组対空：fa He亟回云臺，D设置元素：ex2.SinglyList (A,BjSjDj E>F)纯性克怅度

45、：6插 ASSex2. SinglyListfAj Bj &jXzD f E, F)删躁第二乍元臺：5査找关S?； A删除師育元重：ex2.SinglyList()查栈关键宇；null(5) 、package ex2;public class SortedSinglyList<Textends Comparable <? super T>> extendsSi nglyList<T>/构造空排序单链表public SortedSi nglyList()super ();默认调用父类构造方法 SinglyList()public SortedSingl

46、yList(SinglyList<T> list)super ();/构造空单链表for (Node<T> p=list. head . next ; p!= null ; p=p. next ) / 直接插入排序， 每趟插入1个元素this .insert(p.data );/排序单链表按值插入/构造，将values数组中的所有对象按值插入public SortedSi nglyList(T values)super ();for (int i=0;i<values. length ;i+)this .insert(valuesi);public void se

47、t( int i, T x)/ 设置第 i 个元素值为 xthrow new UnsupportedOperationException("set(int i, T x)"); / 不支持父类方法，覆盖并抛出异常public Node<T> insert( int i, T x)/ 插入 x作为第 i 个元素throw new UnsupportedOperationException("set(int i, T x)");/ 不支持父类方法，覆盖并抛出异常publicNode<T> insert(T x)/在线性表最后插入x元素

48、Node<T>p= this . head ;for (;p. next != null && p. next . data .compareTo(x)>0;)p=p. next ;p. next = new Node<T>(x, p. next );return p. next ;public Node<T> search(T key)/查找，返回首次出现的关键字为key元素for (Node<T>p=this . head ;p. next != null &&pareTo(p.data )<=0;

49、p=p.next )if (pareTo(p.next . data )=0)return p;returnnull ;(6) 、e、package ex2;public class Del1 public Del1( int i, int k)In teger values=1,5,6,10,13;Si nglyListV nteger> list=new Si nglyListV nteger>(values);System. out .println( list.toString();for (int j=O;j<k ;j+)list.remove(i);System.

50、 out .println("删除后："+list.toString();public static void main(Stringl args)new Del1(2,2); x2.SinglyList(lJ5,6?10J15> 删瞧后；ex2.SinglyList(l,5j13)package ex2;public class Del2 public Del2( int mi nk, int maxk)In teger values=1,3,9,17,34;SortedSi nglyListV nteger> list =newSortedSin glyLi

51、st< In teger>(values);System. out .println(list.toString();Node< In teger> p=list. int j=0;while (p. next != null p=p. next ;j+；while (p. next != null list.remove(j);System. out .println(head ;&& p. next . data <=mink)&&p. next . data <maxk)"list=" +list.t

52、oStri ng();public static void main(String args) new Del2(2,18); 0 p iii >0 veg 讨 a *oi“円 v ! y m严带#囂 2 - Sorted Singly List (lj 3?17 34)list=ex2.SartedSinglyList(134)g、package ex2;public class Megerpublic Meger() In teger values仁1,2,5,7,9;val1= new SortedSinglyList<Integer>(values1);val2= n

53、ew SortedSinglyList<Integer>(values2);SortedS in glyList< In teger>In teger values2= 1,0,5,8,9;SortedS in glyList< In teger>new SortedS in glyList< In teger>();SortedS in glyList< In teger> val=int i=0; int j = 0;while (i<val1.size()&&j<val2.size() if (val1.get(i)<=val2.get(j)val.i nsert(val1.get(i);if (val1.get(i)=val2.get(j)j+;i+;elseval.i nsert(val2.get(j); j+;while (i<val1.size()val.i nsert(val2.get(i);i+;while (j<val2.size()val.i nsert(val2.get(j);j+;System. out .println(val1.toString();System. out .println(val