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

实验报告课程名称数据结构实验项目线性表的实现及应用实验仪器PC机一台学院_____专业班级/学号姓名实验日期成绩指导教师北京信息科技大学信息管理学院（数据结构课程上机）实验报告专业:班级:学号:姓名:成绩:实验名称线性表的实现及应用实验地点实验时间1.实验目的：（1）理解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会利用顺序表解决实际应用问题。（2）熟练掌握单链表的使用；理解用链表实现线性表的特点；了解链表的多种形式；学会利用单链表解决实际应用问题。2.实验要求：（1）学时为8学时；（2）能在机器上正确、调试运行程序；（3）本实验需提交实验报告；（4）实验报告文件命名方法：数据结构实验_信管16xx_学号_姓名.doc。3.实验内容和步骤：第一部分顺序表的实现与应用（1）基于顺序表实现线性表的以下基本操作：publicinterfaceLListT{//线性表接口，泛型参数T表示数据元素的数据类型booleanisEmpty();//判断线性表是否空intsize();//返回线性表长度Tget(inti);//返回第i（i≥0）个元素voidset(inti,Tx);//设置第i个元素值为xvoidinsert(inti,Tx);//插入x作为第i个元素voidinsert(Tx);//在线性表最后插入x元素Tremove(inti);//删除第i个元素并返回被删除对象intsearch(Tkey);//查找，返回首次出现的关键字为key的元素的位序voidremoveAll();//删除线性表所有元素publicStringtoString();//返回顺序表所有元素的描述字符串，形式为“（，）”}要求：实现后应编写代码段对每个基本操作做测试。（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）基于单链表实现线性表的以下基本操作（不需要建立接口，直接建立带头结点的单链表类）：ADTListT{booleanisEmpty();//判断线性表是否空intsize();//返回线性表长度Tget(inti);//返回第i（i≥0）个元素voidset(inti,Tx);//设置第i个元素值为xNodeTinsert(inti,Tx);//插入x作为第i个元素NodeTinsert(Tx);//在线性表最后插入x元素Tremove(inti);//删除第i个元素并返回被删除对象voidremoveAll();//删除线性表所有元素NodeTsearch(Tkey);//查找，返回首次出现的关键字为key元素publicStringtoString();//返回顺序表所有元素的描述字符串，形式为“（，）”}要求：实现后应编写代码段对每个基本操作做测试。（5）实现单链表的子类排序单链表，覆盖单链表如下方法：voidset(inti,Tx);//设置第i个元素值为xNodeTinsert(inti,Tx);//插入x作为第i个元素NodeTinsert(Tx);//在线性表最后插入x元素NodeTsearch(Tkey);//查找，返回首次出现的关键字为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）packageex1;publicinterfaceLListT{//线性表接口，泛型参数T表示数据元素的数据类型booleanisEmpty();//判断线性表是否空intlength();//返回线性表长度Tget(inti);//返回第i（i≥0）个元素voidset(inti,Tx);//设置第i个元素值为xintinsert(inti,Tx);//插入x作为第i个元素intappend(Tx);//在线性表最后插入x元素Tremove(inti);//删除第i个元素并返回被删除对象voidremoveAll();//删除线性表所有元素intsearch(Tkey);//查找，返回首次出现的关键字为key的元素的位序}类名：publicclassSeqListTimplementsLListT{protectedObject[]element;protectedintn;publicSeqList(intlength)//构造容量为length的空表{this.element=newObject[length];//申请数组的存储空间，元素为null。//若length0，Java抛出负数组长度异常java.lang.NegativeArraySizeExceptionthis.n=0;}publicSeqList()//创建默认容量的空表，构造方法重载{this(64);//调用本类已声明的指定参数列表的构造方法}publicSeqList(T[]values)//构造顺序表，由values数组提供元素，忽略其中空对象{this(values.length*2);//创建2倍values数组容量的空表//若values==null，用空对象调用方法，Java抛出空对象异常NullPointerExceptionfor(inti=0;ivalues.length;i++)//复制非空的数组元素。O(n)if(values[i]!=null)this.element[this.n++]=values[i];//对象引用赋值}publicbooleanisEmpty()//判断线性表是否空{returnthis.n==0;}publicintlength(){//返回线性表长度returnthis.n;}publicTget(inti){//返回第i（i≥0）个元素if(i=0&&ithis.n)return(T)this.element[i];//返回数组元素引用的对象，传递对象引用//returnthis.element[i];//编译错，Object对象不能返回T对象returnnull;}publicvoidset(inti,Tx){//设置第i个元素值为xif(x==null)thrownewNullPointerException(x==null);//抛出空对象异常if(i=0&&ithis.n)this.element[i]=x;elsethrownewjava.lang.IndexOutOfBoundsException(i+);//抛出序号越界异常}publicintinsert(inti,Tx){//插入x作为第i个元素if(x==null)thrownewNullPointerException(x==null);//抛出空对象异常if(i0)i=0;//插入位置i容错，插入在最前if(ithis.n)i=this.n;//插入在最后Object[]source=this.element;//数组变量引用赋值，source也引用element数组if(this.n==element.length)//若数组满，则扩充顺序表的数组容量{this.element=newObject[source.length*2];//重新申请一个容量更大的数组for(intj=0;ji;j++)//复制当前数组前i-1个元素this.element[j]=source[j];}for(intj=this.n-1;j=i;j--)//从i开始至表尾的元素向后移动，次序从后向前this.element[j+1]=source[j];this.element[i]=x;this.n++;returni;//返回x序号}publicintappend(Tx){//在线性表最后插入x元素returnthis.insert(this.n,x);}publicTremove(inti){//删除第i个元素并返回被删除对象if(this.n0&&i=0&&ithis.n){Told=(T)this.element[i];//old中存储被删除元素for(intj=i;jthis.n-1;j++)this.element[j]=this.element[j+1];//元素前移一个位置this.element[this.n-1]=null;//设置数组元素对象为空，释放原引用实例this.n--;returnold;//返回old局部变量引用的对象，传递对象引用}returnnull;}publicvoidremoveAll(){//删除线性表所有元素this.n=0;}publicintsearch(Tkey){//查找，返回首次出现的关键字为key的元素的位System.out.print(this.getClass().getName()+.indexOf(+key+)，);for(inti=0;ithis.n;i++){if(key.equals(this.element[i]))//执行T类的equals(Object)方法，运行时多态returni;}return-1;}publicStringtoString(){Stringstr=this.getClass().getName()+(;//返回类名if(this.n0)str+=this.element[0].toString();//执行T类的toString()方法，运行时多态for(inti=1;ithis.n;i++)str+=,+this.element[i].toString();//执行T类的toString()方法，运行时多态returnstr+);}publicstaticvoidmain(Stringargs[]){SeqListIntegerlist=newSeqListInteger(20);Integervalues[]={10,1,2,3,4,5,6,7,8,9};SeqListIntegerlist1=newSeqListInteger(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