数据结构实验二-线性表

实验报告二线性表班级：姓名：学号：专业：实验目的：理解线性表的逻辑结构、两种存储结构和数据操作；应用顺序表的基本算法实现集合A=AUB算法，应用顺序表的基本算法实现两有序顺序表的归并算法；掌握单链表的遍历、插入和删除等操作算法，实现多项式相加。实验内容：1、设有线性表LA＝（3,5,8,11）和LB=（2,6,8,9,11,15,20）；①若LA和LB分别表示两个集合A和B，求新集合A＝AUB（‘并’操作，相同元素不保留）；预测输出：LA=（3,5,8,11,2,6,9,15,20）实现代码：packageEx1;publicclassPoint{ inta=0; publicPointnext=null; publicPoint(inta){ this(a,null); } publicPoint(inta,Pointnext){ this.a=a; this.next=next; }}-----------------------------------packageEx1;publicclassSeqList{ privatePointhead=null; privatePointtail=null; publicSeqList(){ head=null; tail=null; } publicbooleanisEmpty(){ returnhead==null; } publicvoidaddHead(inta){ head=newPoint(a,head); if(tail==null) tail=head; } publicvoidaddTail(inta){ if(isEmpty()){ this.addHead(a); } else{ Pointtemp=newPoint(a); tail.next=temp; tail=tail.next; } } publicbooleanFind(inta){ if(isEmpty()) returnfalse; else{ for(Pointtemp=head;temp!=null;temp=temp.next){ if(temp.a==a) returntrue; } } returnfalse; } publicvoidaddList(SeqListlist){ for(Pointtemp=list.head;temp!=null;temp=temp.next){ if(Find(temp.a)){ continue; } else{ Pointtemp1=newPoint(temp.a); tail.next=temp1; tail=tail.next; } } } publicvoidPri(){ //TODOAuto-generatedmethodstub for(Pointtemp=head;temp!=null;temp=temp.next){ System.out.printf("%4d",temp.a); } }}------------------------packageEx1;publicclassTest{ staticint[]x={3,5,8,11}; staticint[]x1={2,6,8,9,11,15,20}; staticSeqListList1=newSeqList(); staticSeqListList2=newSeqList(); publicstaticvoidDef(){ for(inti=0;i<x.length;i++){ List1.addTail(x[i]); } for(inti=0;i<x1.length;i++){ List2.addTail(x1[i]); } } publicstaticvoidPri(){ System.out.println("链表内容为："); List1.Pri(); System.out.println(""); List2.Pri(); System.out.println(""); } publicstaticvoidAdd(){ List1.addList(List2); } publicstaticvoidPri1(){ System.out.println("合并后链表内容为："); List1.Pri(); } publicstaticvoidmain(Stringars[]){ Def(); Pri(); Add(); Pri1(); }}粘贴运行结果：②将LA与LB表归并，要求仍有序（相同元素要保留）(两种存储结构)预测输出：LC=（2,3,5,6,8,8,9,11,11,15,20）packageEx1;publicclassPoint{ inta=0; publicPointnext=null; publicPoint(inta){ this(a,null); } publicPoint(inta,Pointnext){ this.a=a; this.next=next; }}-----------------------------------------------------packageEx1;publicclassSeqList{ Pointhead=null; Pointtail=null; publicSeqList(){ head=null; tail=null; } publicbooleanisEmpty(){ returnhead==null; } publicvoidaddHead(inta){ head=newPoint(a,head); if(tail==null) tail=head; } publicvoidaddTail(inta){ if(isEmpty()){ this.addHead(a); } else{ Pointtemp=newPoint(a); tail.next=temp; tail=tail.next; } } publicbooleanFind(inta){ if(isEmpty()) returnfalse; else{ for(Pointtemp=head;temp!=null;temp=temp.next){ if(temp.a==a) returntrue; } } returnfalse; } publicvoidaddList(SeqListlist){ for(Pointtemp=list.head;temp!=null;temp=temp.next){ if(Find(temp.a)){ continue; } else{ Pointtemp1=newPoint(temp.a); tail.next=temp1; tail=tail.next; } } } publicvoidaddList1(SeqListlist){ Pointtemp1,c,temp2; for(PointH=this.head;H!=null;H=H.next){ if(H.next==null){ H.next=list.head; break; } for(Pointtemp=list.head;temp!=null;temp=temp2){ temp2=temp.next; if(H.a<temp.a||H.a==temp.a){ if(H.a==temp.a||temp.a<H.next.a){ c=H.next; H.next=temp; temp.next=c; list.head=temp2; break; } } else{ this.head=temp; this.head.next=H; list.head=temp2; break; } } } /* Pointla=this.head; Pointlb=list.head; Pointtemp; if(la.a==0) la=la.next; for(;la!=null;la=temp){ temp=la.next; for(;lb.next!=null;lb=lb.next){ if(la.a<lb.next.a||la.a==lb.next.a){ la.next=lb.next; lb.next=la; break; } } if(lb.next==null) lb.next=la; returnlist.head; } returnlist.head; */ } publicvoidPri(){ //TODOAuto-generatedmethodstub for(Pointtemp=head;temp!=null;temp=temp.next){ System.out.printf("%4d",temp.a); } }}--------------------------------------------------------- packageEx1;importjava.util.*;publicclassTest{ staticScannerscan=newScanner(System.in); staticint[]x={3,5,8,11}; staticint[]x1={2,6,8,9,11,15,20}; staticSeqListList1=newSeqList(); staticSeqListList2=newSeqList(); publicstaticvoidDef(){ for(inti=0;i<x.length;i++){ List1.addTail(x[i]); } for(inti=0;i<x1.length;i++){ List2.addTail(x1[i]); } } publicstaticvoidPri(){ System.out.println("链表内容为："); List1.Pri(); System.out.println(""); List2.Pri(); System.out.println(""); } publicstaticvoidAdd(){ List1.addList(List2); } publicstaticvoidPri1(){ List1.Pri(); } publicstaticvoidmain(Stringars[]){ Def(); Pri(); System.out.println("请选择要进行的功能："); System.out.println("A、合并去相同项B、合并并排序，不去相同项"); Stringx=scan.next(); if(x.equals("A")){ Add(); Pri1(); } else{ List1.addList1(List2); List1.Pri(); } scan.close(); }}粘贴运行结果：2、在SinglyLinkedList类中增加下列成员方法。 publicSinglyLinkedList(E[]element)//由指定数组中的多个对象构造单链表 publicSinglyLinkedList(SinglyLinkedListlist)//以单链表list构造新的单链表，复制单链表 publicvoidconcat(SinglyLinkedListlist)//将指定单链表list链接在当前单链表之后 publicNode<E>search(Eelement)//若查找到指定，则返回结点，否则返回null publicbooleancontain(Eelement)//以查找结果判断单链表是否包含指定对象 publicbooleanremove(Eelement)//移去首次出现的指定对象 publicbooleanreplace(Objectobj,Eelement)//将单链表中的obj对象替换为对象element publicbooleanequals(Objectobj)//比较两条单链表是否相等实现代码：packageEx2;publicclassNode<E>{ Ea; Node<E>x; intk; publicNode(){ this.a=null; this.x=null; k=0; } publicNode(Ea,intk){ this.a=a; this.x=null; this.k=k; }}-----------------------------------------packageEx2;publicclassSinglyLinkedList<E>{ publicNode<E>head=null; publicNode<E>tail=null; publicSinglyLinkedList(E[]element){//由指定数组中的多个对象构造单链表 intn=0; this.head=newNode<E>(element[0],n); tail=head; for(inti=1;i<element.length;i++){ n++; tail.x=newNode<E>(element[i],n); tail=tail.x; } } publicSinglyLinkedList(SinglyLinkedList<E>list){//以单链表list构造新的单链表，复制单链表 this.head=newNode<E>((E)list.head.a,list.head.k); tail=head; for(Node<E>temp=list.head.x;temp!=null;temp=temp.x){ tail.x=newNode<E>((E)temp.a,temp.k); tail=tail.x; } } publicvoidconcat(SinglyLinkedList<E>list){//将指定单链表list链接在当前单链表之后 this.tail.x=list.head; } publicNode<E>search(Eelement){//若查找到指定，则返回结点，否则返回null Node<E>x=null; for(x=this.head;x!=null;x=x.x){ if(elementinstanceofInteger){ if(x.a==element){ returnx; } } else{ if(x.a.equals(element)){ returnx; } } } returnnull; } publicbooleancontain(Eelement){//以查找结果判断单链表是否包含指定对象 for(Node<E>temp=this.head.x;temp!=null;temp=temp.x){ if(elementinstanceofInteger){ if(temp.a==element){ returntrue; } } else{ if(temp.a.equals(element)){ returntrue; } } } returnfalse; } publicbooleanremove(Eelement){//移去首次出现的指定对象 Node<E>n1=this.head; Node<E>n2=null; n2=this.search(element); intkey=n2.k; if(n1==null) returnfalse; else{ if(n1.k==key){ this.head=n1.x; returntrue; } else{ while(n1!=null){ n2=n1.x; if(n1.k==key){ n1.x=n2.x; returntrue; } n1=n1.x; } } } returnfalse; } publicbooleanreplace(Objectobj,Eelement){//将单链表中的obj对象替换为对象element Node<E>n1=this.head; Node<E>n2=null; n2=this.search(element); intkey=n2.k; if(n1==null) returnfalse; else{ if(n1.k==key){ this.head.a=(E)obj; returntrue; } else{ while(n1!=null){ n2=n1.x; if(n2.k==key){ n2.a=(E)obj; returntrue; } n1=n1.x; } } } returnfalse; } publicbooleanequals(SinglyLinkedList<E>list){//比较两条单链表是否相等 Node<E>temp1=list.head; for(Node<E>temp=this.head;temp!=null;temp=temp.x){ if(temp1.x==null) returnfalse; if(!(temp1.a.equals(temp.a))){ returnfalse; } temp1=temp1.x; } if(temp1.x.a!=null){ returnfalse; } returntrue; }}3、算法实现：多项式相加 一条单链表可以表示一个一元多项式，每个结点包含三个域：指数域、系数域和后继结点链。表示多项式的单链表如图1所示。给定两个多项式，实现两个多项式相加算法。系数指数链51-10051-100∧-6234实现代码：packageEX3;publicclassPoint{ intfactor; intindex; Pointnext=null; publicPoint(inta,intb){ this.factor=a; this.index=b; } publicPoint(inta,intb,Pointx){ this.factor=a; this.index=b; this.next=x; }}------------------------------------packageEX3;publicclasspol{ publicPointhead=null; publicPointtail=null; publicpol(int[][]ele){ this.head=newPoint(ele[0][0],ele[0][1]); tail=head; for(inti=1;i<ele.length;i++){ tail.next=newPoint(ele[i][0],ele[i][1]); tail=tail.next; } } publicPointAdd(poll){ Pointp=l.head; Pointr=null; Pointtemp1=null; for(;p!=null;p=p.next){ for(Pointtemp=this.head;temp!=null;temp=temp.next){ if(temp==this.head&&p==l.head){ if(p.index==temp.index){ temp.factor+=p.factor; r=temp; break; }else{ if(p.index>temp.index){ r=p; r.next=temp; break; } } } if(p.index==temp.index){ temp.factor+=p.factor; break; } if(temp.next==null&&p.index!=temp.index){ temp1=newPoint(p.factor,p.index); this.tail.next=temp1; this.tail=this.tail.next; break; } } } returnr; } publicvoidcollate(){ inta,b; for(Pointtemp=this.head;temp.next!=null;temp=temp.next){ if(temp.index<temp.next.index){ a=temp.next.factor; b=temp.next.index; temp.next.fact