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

数据结构（Java版）-线性表的实 现与应用完整版实验报告课程名称 数据结构 实验项目 线性表的实现及应用实验仪器 PC机一台 学 院 专 业 班级/学号 姓名 实验日期 成 绩 指导教师 北京信息科技大学信息管理学院(数据结构课程上机)实验报告专业:_班级:_学号:_姓名: 成绩： 实验名称 线性表的实现及应用 实验地点 实验时间1.实验目的：(1) 理解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会利 用顺序表解决实际应用冋题2) 熟练掌握单链表的使用；理解用链表实现线性表的特点；了解链表的多 种形式；学会利用单链表解决实际应用问题2.实验要求：(1) 学时为8学时；(2) 能在机器上正确、调试运行程序；(3) 本实验需提交实验报告；(4) 实验报告文件命名方法：数据结构实验 ―信管16xx_学号J生名.doc3.实验内容和步骤：第一部分顺序表的实现与应用(1)基于顺序表实现线性表的以下基本操作：public in terface LList{ //线性表接口，泛型参数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); 〃性表最后插入x兀素T remove(int i); //删除第i个兀素并返回被删除对象int 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) 禾U用顺序表解决约瑟夫环问题：已知 n个人(以编号1, 2, 3…n分别表示) 旨坐在一张圆桌周围从编号为 k的人开始报数，数到 m的那个人出列；他的一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到要求：输出出列次序单链表的实现与应用(4) 基于单链表实现线性表的以下基本操作(不需要建立接口，直接建立带头吉点的单链表类)：ADT List{ boolea n isEmpty(); int size(); T get(i nt i); void set(i nt i, T x);Node in sert(i nt i, T x); Node in sert(T x);T remove(i nt i);象void removeAll(); Node search(T key);key元素public String toString();形式为“(，)”//判断线性表是否空//返回线性表长度〃返回第i (i > 0)个元素//设置第i个元素值为x〃插入x作为第i个元素//性表最后插入x元素〃删除第i个元素并返回被删除对〃删除线性表所有元素〃查找，返回首次出现的关键字为〃返回顺序表所有元素的描述字符串，(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，且同一表中的元素值各 不相同试构造一个单链表 C,其元素为A和B中元素的交集，且表C 中的元素也按值递增有序排列要求利用原有链表中的元素7） —元多项式的基本运算用排序单链表表示一元多项式，并实现以下基本运算：一元多项式的建立一元多项式的减法运算（要求：在运算过程中不能创建新结点 即A=A-B）（8） 备份自己程序4.实验准备：复习教材第2章线性表的知识点熟悉Java编程环境提前熟悉实验内容，设计相关算法5.实验过程：第一部分：(1)package exl;public in terface LList{ //线性表接口，泛型参数T表示数据元素的数据类型boolean isEmpty(); // 判断线性表是否空int length();//返回线性表长度T get( int i);//返回第i (i >0)个元素void set( int i, T x); //设置第i个元素值为xint in sert( int i, T x); //插入x作为第i个元素int append(T x); // 性表最后插入x元素T remove( int i); //删除第i个元素并返回被删除对象void removeAII(); // 删除线性表所有元素int search(T key); //查找，返回首次出现的关键字为key的元素的位 序}类名：public class SeqList impleme nts LList {protected Object]] element ;protected int n;public SeqList( int len gth)//构造容量为length的空表{this . element = newObject[length]; // 申请数组的存储空间，元素为null 。

// 若 length<0 ，Java抛出负数组长度异常java.la ng.NegativeArraySizeExceptionthis . n = 0;}public SeqList()//创建默认容量的空表，构造方法重载{this (64);//调用本类已声明的指定参数列表的构造方法}public SeqList(T [] values)//构造顺序表，由values数组提供元素，忽略 其中空对象{this (values. len gth *2);//创建2倍values数组容量的空表// 若values==null ，用 空对象调用方法，Java抛出空对象异常NullPoi nterExceptio nfor ( int i=0;i0)个元素i f (i>=0 && i< this . n) return(T) this 二element //返回数组元素引用的对象，传递对象引用// return this.eleme nt[i];//编译错，Object对象不能返回T对象return n ull ;}public void set( int i, Tx){ //设置第i个元素值为xi f (x== null )throw newNullPoi nterExceptio n( "x==nu II" );//抛出空对象异常if (i>=0 && i< this . n) this . element [i] = x;else throw newjava.la ng.ln dexOutOfBo un dsException(i+ "" ); //抛出序号越界异常}public int in sert( int i, Tx){ II插入x作为第i个元素if (x== n ull )throw newNullPoi nterExceptio n( "x==nu II" );//抛出空对象异常if (i<0) i=0;//插入位置i容错，插入在最前if (i> this . n) i= this . n;//插入在最后Object]] source =this . element ; // 数组变量引用赋值，source也引用element数组 if (this . n= =element . length )//若数组满，则扩充顺序表的数组容量{this . element = newObject[source. length *2]; // 重新申请一个容量更大的数组for ( int j=0; j

];}for ( int j= this . n-1; j>=i;j--) //从i开始至表尾的元素向后移动，次序从后向前this . element [j+1]= source];this . element [i] = x;this . n ++;return i;//返回x序号}public int appe nd(Tx){ //性表最后插入x元素return this .insert( this . n,x);}public T remove( int i){//删除第i个元素并返回被删除对象if ( this . n>0 && i>=0 &&i< this . n){T old =(T) this element //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局部变量引用的对象，传递对象引用}return n ull ;}public void removeAII(){//删除线性表所有元素this . n=0;} public int search(Tkey){ //查找，返回首次出现的关键字为key的元素的位System. out .print( this .getClass().g etName()+ ".indexOf(" +key+ ")，");for (int i=0; i< this . n; i++) {if(key.equals( this . element [i]))//执行T类的equals(Object) 方法，运行时多 态return i;}return -1;}public String toString(){Stri ng"(";str= this .getClass().getName()+//返回类名if ( this . n >0)str +=this . element [0].toString();//执行T类的toString() 方法，运行时多态"+this// 执行T类的 toString()for ( int i=1; i< this . n; i++) str += ",.element [i].toString();return st叶方法，运行时多态")";public staticvoid main (Stringargs[]){newSeqListvl nteger> list=SeqListvl nteger>(20);In tegervalues[]={10,1,2,3,4,5,6,7,8,9};SeqListvl nteger> list1 =SeqListvl nteger>(values);newSystem. out .print( "输出顺序表:");System. out .println(list1.toString());System. out .println("顺序表List 是否为空"+list.isEmpty()+",List1是否为空"+list1.isEmpty());System. out .println("list 的长度"+list.le ngth()+ ",list1的长度"+list1.le ngth());System. out .println("返回list1 的第 7个元素是:"+list1.get(6));System. out .println(-重新设置第5个元素为19:");list1.set(4, 19);list1.i nsert(2, 100);list1.appe nd(20);System. out .println( "删除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.5eqLisr (10^ J 厂 化 5, 6, 7,孔 9)*曲序為Limt•是:否衣空t.rue^List.1是否为空false丄i处的长长度M返回的第T个元素是;日重新设置第5个元素为19：刪除8 ：7修改后的顺序表 :» SeqLi^t (101 100 f 2 f 3 f 19 f 5 f 6^ 8卢 9f 20) 刪除后的顺序表；sxl. SeqLisc _exl ,SeqL13t, index Of (50)) 寻找兀素 5d : -1(2)a)package exl;public class Del {public Del( int i, int k){Stri ngvalues[]={ "A" , "b" , "C" , "d" , "e" , "f" nun i .g , h };int n =values. len gth ;for (int j=O;j list= newSeqListvStri ng>(values);System. out .println(list.toString());for (int j=1;j<=k;j++){ list.remove(i);}System. out .println(list.toString());}public static void mai n(Stri ng args[]){new Del2(2,3);}}|exl.自曾好Li目匸(Ar 耳』 yr h)exl.SeqList(kr x, c, h)c) package exl;public class Merge { public Merge(){In teger values1[]={1,3,5,11};SeqListvlnteger> Iist1 =SeqListv In teger>(values1);In tegervalues2[]={2,4,5,22,23};SeqList list2=SeqList(values2);SeqList list3=SeqList();newnewnewint i=0,j=0;while (ivlistl.length()&&j list1 =newSeqList< In teger>( values1 );In tegervalues2 []={2,4,5,12,19,20,22,23,};SeqList list2 =newSeqList< In teger>( values2 );list3 =newSeqListvl nteger>SeqListvl nteger>();int i =0, j =0;while ( i list2 .get( j )){j ++;}else{ list3 .append( list1 .get( i ));i ++；j ++；}}System.))；out .println(list1.toStri ng(System.))；out .println(list2.toStri ng(System.))；out .println(list3.toStri ng(}public staticmain(String args []){voidnew Intersection();}} kitCfSiKtion |Jdvd Applkdtionl C:\PfOgrdinhilesVdkT.8.0 121 \bin\jdvdw.exc exl.SeqList (1, 3, 5, 11, 12f 13., 22t 23, 50)&xl-SGqList(2f 4, 5r 12, 19. 20, 22f 23)&xl.S&qlist(Sf 12f 22, 23}3.(1)package ex1;public class Josephus {public Josephus( int n, int k,int m){System. out .println( "Josephus(" +n+","+k+"," +m+"),");SeqListvStri ng> list = newSeqListvStri ng>( n);//创建顺序表实例，元素类型是数字字符，只能排到n=9,否则达不到效果for ( int i =0; i 1)//多于一个元素时循环，计数O(1){i = ( i +m-1) %list .length(); // 按循环方式对顺序表进行遍历，圆桌循环System. out .print( "出列"+list .remove( i ).toString()+ "，");//删除i位置对象，0(n)//System.out.pri ntl n(list.toStri ng());}System. out .println( "出列"+list .get(0).toStri ng()); 〃get(0)获得元素，0(1)}public static void main (Stri ng args []){new Josephus(9,1,3);}}Josephus(9,1f 3)出列4』出列7,出列1,出列5“出列9』出列®出列*出列8,出列2 I(2)package test;import exl.SeqLis t;public class JosephusA {public JosephusA( int n, int k, int m){System. out .println( "Josephus(" +n+","+k+"," +m+"),");SeqListvl nteger> list =new SeqList< In teger>( n);//创建顺序表实 例，元素类型是数字字符，只能排到n=9,否则 达不到效果for ( int i =0; i 1)//多于一个元素时循环，计数0(1){i = ( i +m-1) %list .length(); // 按循环方式对顺序表进行遍历，圆桌循环System. out .print( "出列"+list .remove( i ).toString()+ "，");//删除i位置对象，O(n)//System.out.pri ntl n(list.toStri ng());}System. out .println( "出歹卩-+=sf ■gexorosfringox vgef(o) 绍笳耳W7 Ou)pub=c sErfic void main(sfring args =)宀new JosephusA(」529=Josephus (Isu^gr 恳一」p Ji±4“ §=14 r丘着、总二『圧.MW 圧竺5、圧這IL圧HL2『』辿7」」NCI“対一厂(4:package exz pub=c c-ass NodeATV 宀 pub-ic T daIEr- -_ 臂命溥}public Node next ; II 地址域，后继 结点II构造结点public Node(T data,Node n ext){this . data =data;this . next =next;}II构造空结点public Node(){this (null , null );}II描述字符串public String toString(){return this . data .toString();}package ex2;public class SinglyList {public Node head;//构造空单链表public Si nglyList(){head =new Node();}//构造单链表，由values数组数组提供元素public Si nglyList(T[] values){this ();Noderear= this . head;for (int i=O;i(values[i], null ); rear=rear. next ;public boolea n isEmpty() 判断线性表是否空return this . head. next == nullpublic T get( int i)//返回第i (i >0个元素{Nodep= head. next ;f or (int j=O;p!= null &&j=0) ?.data : null ;public void set( int i, T x)//设置第i个元素值为x{i f (x== null )throw newNullPoi nterExceptio n( "x==null" ); //抛出空对象异常Nodep=this . head. next ; //0f or (int j=O;p!= null &&j0&&p!= null )p. data =x;}public int size()//返回线性表长度{int i=0;for (Nodep= this . head .next ;p!= nullp=p. next )i++；r eturn i;}public Node insert( int i, T x)//插入x作为第i个元素{i f (x== null )throw newNullPoi nterExceptio n( "x=null");//以此循Nodefront= this . head ;指定头结点f or (intj=O;front. next != null &&j(x,front. next );r eturn front. next ;}public Node in sert(T x){ if (x== null )throw newNullPoi nterExceptio n( "x==null");//抛出空对象异常Node front= this . head;//front 指向头结点for (; front. next != null ;) //寻找第i-1个或最后一个结点(front指向)front = front. next ;front. n ext = new Node(x,front. next ); //在front之后插入值为x结点，包括头插入、中间/尾插入return front. next ;}public T remove( int i)//删除第i个元素并返回被删除对象{Nodep=this . head; // 让p指向头结点f or (int j=O;j search(T key)查找，返回首次出现的关键字为key元素{f or (Node p=this . head ;p. next != null ;p=p. next )if(key.equals(p. data ))r eturnreturn p; null ;public//返回aStri ng toStri ng()顺序表所有元素的描述字符串，形式为{Stri ngstr= this .getClass().getName()+ "(";//返回类名for (Node p= this . head. next ; p!= null ; p=p. next ) //p 遍历单链表{ str += p. data .toString();str +=if (p. next != null )II II ■//不是最后一个结点时，加分隔符}return str+ ")"}}教组为空：f^l&e亟回兀圭：D设蛊元秦：ex2*SinglyLi5t (AjBjSjD, E>F) 绕性克怅度：6插A5HK ex2. SinglyListCAa Bj f E ； IF)刪馀第二个兀臺:5査栈关躍学；A删障前有元臺：ex2,SinglyList()查栈关键宇；null(5)、package ex2;public class SortedSinglyListvTextends Comparable > extendsSin glyList{//构造空排序单链表public SortedSi nglyList(){super (); 〃默认调用父类构造方法SinglyList()}publicSortedSi nglyList(Si nglyList list){super ();//构造空单链表for (Node p=list. head.next;p!= null ; p=p. next ) //直接插入排序，每趟 插入1个元素this .insert(p. data );//排序单链表按值插入}//构造，将values数组中的所有对象按值插 入public SortedS in glyList(T values[]){super ();for (int i=O;i insert( int i, T x)//插入x作为第i个元素{throw newUn supportedOperati on Excepti on( "set(i nti, T x)" ); //不支持父类方法，覆盖并抛出异常}public Node in sert(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 (Nodedata )v=O;p=p. next )ifp=this . head ;p. next != null &&pareT o(p.(pareTo(p. next . data )==0) return p;return null ;}(6)、e、package ex2;public class Dell {public Del1( int i, intk){In teger[] values={1,5,6,10,13};SinglyListvlnteger> list=newSi nglyListvl nteger>(values);System. out .println( list.toString())for (int j=O;j list =new SortedSi nglyListvl nteger>(values);System. out .println(list.toString());Nodev In teger> p=list. head;int j=0;while (p. next != null &&p. next . data <=mink){ p=p. next ;j++;}while (p. next != null&&p. next . data 查看更多