数据结构(Java版)-线性表的实现与应用完整版实验报告课程名称数据结构实验项目线性表的实现及应用实验仪器PC机一台学院_____ 专业班级/学号姓名实验日期成绩指导教师北京信息科技大学信息管理学院（数据结构课程上机）实验报告专业: 班级: 学号: 姓名: 成绩:实验名称线性表的实现及应用实验地点实验时间1.实验目的：（1）理解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会利用顺序表解决实际应用问题。

（2）熟练掌握单链表的使用；理解用链表实现线性表的特点；了解链表的多种形式；学会利用单链表解决实际应用问题。

2.实验要求：（1）学时为8学时；（2）能在机器上正确、调试运行程序；（3）本实验需提交实验报告；（4）实验报告文件命名方法：数据结构实验_信管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); //在线性表最后插入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)若两个元素按值递增有序排列的顺序表A和B，且同一表中的元素值各不相同。

试构造一个顺序表C，其元素为A和B中元素的交集，且表C中的元素也按值递增有序排列；（3）利用顺序表解决约瑟夫环问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。

从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

要求：输出出列次序。

第二部分单链表的实现与应用（4）基于单链表实现线性表的以下基本操作（不需要建立接口，直接建立带头结点的单链表类）：ADT List<T>{ boolean isEmpty(); //判断线性表是否空int size(); //返回线性表长度T get(int i); //返回第i（i≥0）个元素void set(int i, T x); //设置第i个元素值为xNode<T> insert(int i, T x); //插入x作为第i个元素Node<T> insert(T x); //在线性表最后插入x元素T remove(int i); //删除第i个元素并返回被删除对象void removeAll(); //删除线性表所有元素Node<T> search(T key); //查找，返回首次出现的关键字为key元素public String toString(); //返回顺序表所有元素的描述字符串，形式为“（，）”}要求：实现后应编写代码段对每个基本操作做测试。

（5）实现单链表的子类排序单链表，覆盖单链表如下方法：void set(int i, T x); //设置第i个元素值为xNode<T> insert(int i, T x); //插入x作为第i个元素Node<T> insert(T x); //在线性表最后插入x元素Node<T> 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 ex1;public interface LList<T>{ //线性表接口，泛型参数T表示数据元素的数据类型boolean isEmpty(); //判断线性表是否空int length(); //返回线性表长度T get(int i); //返回第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 SeqList<T>implements LList<T> {protected Object[] element;protected int n;public SeqList(int length) //构造容量为length的空表{this.element = newObject[length]; //申请数组的存储空间，元素为null。

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

O(n)if (values[i]!=null)this.element[this.n++] = values[i]; //对象引用赋值}public boolean isEmpty() //判断线性表是否空{return this.n==0;}public intlength(){ //返回线性表长度return this.n;}public T get(inti){ //返回第i（i≥0）个元素i f (i>=0 && i<this.n)return(T)this.element[i]; //返回数组元素引用的对象，传递对象引用// return this.element[i]; //编译错，Object对象不能返回T对象return null;}public void set(int i, Tx){ //设置第i个元素值为xi f (x==null)throw new NullPointerException("x==null"); //抛出空对象异常if (i>=0 && i<this.n)this.element[i] = x;else throw newng.IndexOutOfBoundsException(i+"");//抛出序号越界异常}public int insert(int i, Tx){ //插入x作为第i个元素if (x==null)throw new NullPointerException("x==null"); //抛出空对象异常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<i; j++) //复制当前数组前i-1个元素this.element[j] = source[j];}for (int j=this.n-1; j>=i;j--) //从i开始至表尾的元素向后移动，次序从后向前this.element[j+1] = source[j];this.element[i] = x;this.n++;return i; //返回x序号}public int append(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[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局部变量引用的对象，传递对象引用 }return null;}public void removeAll(){//删除线性表所有元素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(){Stringstr=this.getClass().getName()+"("; //返回类名if (this.n>0)str +=this.element[0].toString(); //执行T类的toString()方法，运行时多态for (int i=1; i<this.n; i++) str += ","+this.element[i].toString(); //执行T类的toString()方法，运行时多态return str+") ";}public static void main (String args[]){SeqList<Integer> list=new SeqList<Integer>(20);Integervalues[]={10,1,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的长度"+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.println("删除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;public class Del {public Del(int i,int k){Stringvalues[]={"A","b","C","d","e","f", "g","h"};int n =values.length;for(int j=0;j<n;j++){System.out.print(values[j]+" ");}System.out.println();for(int j=i+k;j<n;j++){values[j-k]=values[j];}n=n-k;for(int j=0;j<n;j++){System.out.print(values[j]+ " " );}System.out.println();}public static void main(String args[]){new Del(2,3);}}b)package ex1;public class Del2 {public Del2(int i,int k){S tringvalues[]={"A","x","y","y","b","c", "h"};SeqList<String> list=new SeqList<String>(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[]){n ew Del2(2,3);}}c)package ex1;public class Merge {public Merge(){Integer values1[]={1,3,5,11};SeqList<Integer> list1=new SeqList<Integer>(values1);Integervalues2[]={2,4,5,22,23};SeqList<Integer> list2=new SeqList<Integer>(values2);SeqList<Integer> list3=new SeqList<Integer>();int i=0,j=0;while(i<list1.length()&&j<list2.le ngth()){if(list1.get(i)<list2.get(j)){list3.append(list1.get(i));i++;}else{list3.append(list2.get(j));j++;}}while(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( ));}public static void main(String args[]){new Merge();}}d)package test;import ex1.SeqList;public class Intersection {public Intersection(){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>();int i=0,j=0;while(i<list1.length()&&j<list2.le ngth()){if(list1.get(i)<list2.get(j)){i++;}elseif(list1.get(i)>list2.get(j)){j++;}else{ list3.append(list1.get(i));i++;j++;}}System.out.println(list1.toString( ));System.out.println(list2.toString( ));System.out.println(list3.toString( ));}public static voidmain(String args[]){new Intersection();}}3.（1）package ex1;public class Josephus {public Josephus(int n, int k, int m){System.out.println("Josephus("+n+" ,"+k+","+m+")，");SeqList<String> list = new SeqList<String>(n);//创建顺序表实例，元素类型是数字字符，只能排到n=9,否则达不到效果for (int i=0; i<n; i++)list.append((char)('1'+i)+""); //顺序表尾插入，O(1)//System.out.println(list.toString()); //输出顺序表的描述字符串，O(n)int i = 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() );}System.out.println("出列"+list.get(0).toString());//get(0)获得元素，O(1)}public static void main(String args[]){new Josephus(9,1,3);}}（2）package test;import ex1.SeqList;public class JosephusA {public JosephusA(int n, int k, int m){System.out.println("Josephus("+n+" ,"+k+","+m+")，");SeqList<Integer> list = new SeqList<Integer>(n);//创建顺序表实例，元素类型是数字字符，只能排到n=9,否则达不到效果for (int i=0; i<n; i++)list.append(i); //顺序表尾插入，O(1)//System.out.println(list.toString()); //输出顺序表的描述字符串，O(n)int i = 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());}System.out.println("出列"+list.get(0).toString());//get(0)获得元素，O(1)}public static voidmain(String args[]){new JosephusA(15,2,9);}}第二部分：（4）、package ex2;public class Node<T> {public T data; //数据域public Node<T> next; //地址域，后继结点//构造结点public Node(T data,Node<T> next){this.data =data;this.next=next;}//构造空结点public Node(){this(null,null);}//描述字符串public String toString(){return this.data.toString();}}package ex2;public class SinglyList<T> {public Node<T>head;//构造空单链表public SinglyList(){head=new Node<T>();}//构造单链表，由values数组数组提供元素public SinglyList(T[] values){this();Node<T>rear=this.head;for(int i=0;i<values.length ;i++){rear.next=newNode<T>(values[i],null);rear=rear.next;}}public boolean isEmpty() //判断线性表是否空{return this.head.next ==null;}public T get(int i) //返回第i（i≥0）个元素{N ode<T>p=head.next ;f or(int j=0;p!=null&&j<i;j++)p=p.next;r eturn (p!=null&&i>=0) ?p.data:null;}public void set(int i, T x) //设置第i个元素值为x{i f(x==null)throw newNullPointerException("x==null"); //抛出空对象异常N ode<T>p=this.head.next; //0f or(int j=0;p!=null&&j<i;j++)//遍历寻找第i个结点（p指向）p=p.next;i f(i>0&&p!=null)p.data=x;}public int size() //返回线性表长度{int i=0;for(Node<T>p=this.head.next;p!=null;p=p.next)i++;r eturn i;}public Node<T> insert(int i, T x) //插入x作为第i个元素{i f(x==null)throw newNullPointerException("x=null");N ode<T>front=this.head ; //指定头结点f or(intj=0;front.next!=null&&j<i;j++)front=front.next; //以此循环找i-1f ront.next=newNode<T>(x,front.next );r eturn front.next;}public Node<T> insert(T x){ if (x==null)throw newNullPointerException("x==null");//抛出空对象异常Node<T> front=this.head; //front指向头结点for (; front.next!=null;) //寻找第i-1个或最后一个结点（front指向）front = front.next;front.next = new Node<T>(x,front.next); //在front之后插入值为x结点，包括头插入、中间/尾插入return front.next;}public T remove(int i) //删除第i个元素并返回被删除对象{N ode<T>p=this.head; //让p指向头结点f or(int j=0;j<i&&p.next!=null;j++)p=p.next;if(p.next!=null){T old=p.next.data ;p.next=p.next.next;return old;}r eturn null;}public void removeAll() //删除线性表所有元素{this.head.next=null; //让头结点直接为空}public Node<T> search(T key) //查找，返回首次出现的关键字为key元素{f or(Node<T> p=this.head;p.next!=null;p=p.next)if( key.equals(p.data))return p;r eturn null;}public String toString() //返回顺序表所有元素的描述字符串，形式为“（，）”{Stringstr=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+")";}}（5）、package ex2;public class SortedSinglyList<T extends Comparable <? super T>> extends SinglyList<T>{//构造空排序单链表public SortedSinglyList(){super(); //默认调用父类构造方法SinglyList()}publicSortedSinglyList(SinglyList<T> list){super(); //构造空单链表for (Node<T> p=list.head.next; p!=null; p=p.next)//直接插入排序，每趟插入1个元素this.insert(p.data); //排序单链表按值插入}//构造，将values数组中的所有对象按值插入public SortedSinglyList(T values[]) {super();for(int i=0;i<values.length;i++)this.insert(values[i]);}public void set(int i, T x) //设置第i个元素值为x{throw 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)"); //不支持父类方法，覆盖并抛出异常}public Node<T> insert(T x)//在线性表最后插入x元素{Node<T>p=this.head;for(;p.next!=null&&pareTo(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&&pareT o(p.data)<=0;p=p.next)if(pareTo(p.next.data)==0) return p;return null;}（6）、e、package ex2;public class Del1 {public Del1(int i,int k){Integer[] values={1,5,6,10,13};SinglyList<Integer> list= new SinglyList<Integer>(values);System.out.println( list.toString()) ;for(int j=0;j<k ;j++)list.remove(i);System.out.println("删除后："+list.toString());}public static void main(String[] args){new Del1(2,2);}}f、package ex2;public class Del2 {public Del2(int mink,int maxk){Integer[] values={1,3,9,17,34};SortedSinglyList<Integer> list = new SortedSinglyList<Integer>(values);System.out.println(list.toString());Node<Integer> 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<maxk){list.remove(j);}System.out.println("list="+list.toSt ring());}public static void main(String args[]) {new Del2(2,18);}}g、package ex2;public class Meger{public Meger(){Integer[] values1={1,2,5,7,9}; SortedSinglyList<Integer> val1=new SortedSinglyList<Integer>(values1); Integer[] values2= {1,0,5,8,9}; SortedSinglyList<Integer> val2=new SortedSinglyList<Integer>(values2); SortedSinglyList<Integer> val=new SortedSinglyList<Integer>();int i=0;int j = 0;while(i<val1.size()&&j<val2.size()) {if(val1.get(i)<=val2.get(j)){val.insert(val1.get(i));if(val1.get(i)==val2.get(j))j++;i++;}else{val.insert(val2.get(j));j++;}}while(i<val1.size()){val.insert(val2.get(i));i++;}while(j<val2.size()){val.insert(val2.get(j));j++;}System.out.println(val1.toString()); System.out.println(val2.toString()); System.out.println(val.toString());}public static void main(String args[]) {new Meger();}}(7)、package Poly;public interface Subible<T> //可相加接口，T表示数据元素的数据类型{public void sub(T t);。