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

1/30实验报告课程名称数据结构实验工程线性表的实现及应用实验仪器PC机一台学院_____专业班级/学号姓名实验日期成绩指导教师2/30北京信息科技大学信息管理学院（数据结构课程上机）实验报告专业:班级:学号:姓名:成绩:实验名称线性表的实现及应用实验地点实验时间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）顺序表的简单应用3/30a)运用基本操作编写算法删除第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元素4/30（6）基于排序单链表实现线性表的以下综合应用：e)删除第i个开始的k个元素。f)删除递增有序单链表中所有值大于mink且小于maxk的元素。g)将两个单链表合并为一个单链表，保持有序。h)若两个元素按值递增有序排列的单链表A和B，且同一表中的元素值各不相同。试构造一个单链表C，其元素为A和B中元素的交集，且表C中的元素也按值递增有序排列。要求利用原有链表中的元素。（7）一元多项式的基本运算用排序单链表表示一元多项式，并实现以下基本运算：一元多项式的建立一元多项式的减法运算（要求：在运算过程中不能创建新结点即A=A-B）（8）备份自己程序4.实验准备：复习教材第2章线性表的知识点熟悉Java编程环境提前熟悉实验内容，设计相关算法5/305.实验过程：第一部分：（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数组提供元素，忽略其中空对象{6/30this(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。//数组变量7/30引用赋值，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的元素的位8/30System.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的