实验二线性表.docx
- 文档编号:16715368
- 上传时间:2023-07-16
- 格式:DOCX
- 页数:20
- 大小:66.49KB
实验二线性表.docx
《实验二线性表.docx》由会员分享,可在线阅读,更多相关《实验二线性表.docx(20页珍藏版)》请在冰点文库上搜索。
实验二线性表
实验报告二线性表
一、实验目的:
(1)理解线性表的逻辑结构、两种存储结构和数据操作;
(2)应用顺序表的基本算法实现集合A=AUB算法,应用顺序表的基本算法实现两有序顺序表的归并算法;(单链表的归并算法)
(3)掌握单链表的遍历、插入和删除等操作算法,实现多项式相加。
二、实验容:
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)
实现代码:
packageQ1_1;
publicclassNode
publicTdata;
publicNode
publicNode(Tdata,Node
this.data=data;
this.next=next;
}
publicNode(){
this(null,null);
}
}
packageQ1_1;
importQ1_2.Node;
publicclassLList{
publicstaticNode
publicstaticNode
publicstaticNode
int[]A={3,5,8,11};
Node
headA=LA;
for(inti=0;i LA.next=newNode LA=LA.next; } returnheadA; } publicstaticNode int[]B={2,6,8,9,11,15,20}; Node headB=LB; for(inti=0;i LB.next=newNode LB=LB.next; } returnheadB; } publicstaticbooleanpare(Node Node booleanflag=false; while(p! =null){ if(p.data==t) flag=true; p=p.next; } returnflag; } publicstaticNode LB=LB.next;LA=LA.next; booleanflag; Node while(LA! =null){ rear=LA; LA=LA.next; } while(LB! =null){ flag=pare(headA,LB.data); if(flag==false){ Node rear.next=temp; rear=rear.next; LB=LB.next; }else LB=LB.next; } returnheadA; } publicstaticvoidmain(String[]args){ Node headA=CreateLA(); headB=CreateLB(); t=link(headA,headB); while(t.next! =null){ System.out.printf("%-3d",t.next.data); t=t.next; } } } 粘贴运行结果: ②将LA与LB表归并,要求仍有序(相同元素要保留) 预测输出: LC=(2,3,5,6,8,8,9,11,11,15,20) packageQ1_2; publicclassNode publicTdata; publicNode publicNode(Tdata,Node this.data=data; this.next=next; } publicNode(){ this(null,null); } } packageQ1_2; importjava.util.*; publicclassLList{ publicstaticNode publicstaticNode publicstaticNode int[]A={3,5,8,11}; Node headA=LA; for(inti=0;i LA.next=newNode LA=LA.next; } returnheadA; } publicstaticNode int[]B={2,6,8,9,11,15,20}; Node headB=LB; for(inti=0;i LB.next=newNode LB=LB.next; } returnheadB; } publicstaticNode LB=LB.next;LA=LA.next; while(LA! =null){ if(LB.data<=LA.data&&LA.data Node temp.next=LB.next; LB.next=temp; LA=LA.next; } else LB=LB.next; } returnheadB; } publicstaticvoidmain(String[]args){ Node headA=CreateLA(); headB=CreateLB(); t=pare(headA,headB); while(t.next! =null){ System.out.printf("%-3d",t.next.data); t=t.next; } } } 粘贴运行结果: 2、在SinglyLinkedList类中增加下列成员方法。 publicSinglyLinkedList(E[]element)//由指定数组中的多个对象构造单链表 publicSinglyLinkedList(SinglyLinkedListlist)//以单链表list构造新的单链表,复制单链表 publicvoidconcat(SinglyLinkedListlist)//将指定单链表list在当前单链表之后 publicNode publicbooleancontain(Eelement)//以查找结果判断单链表是否包含指定对象 publicbooleanremove(Eelement)//移去首次出现的指定对象 publicbooleanreplace(Objectobj,Eelement)//将单链表中的obj对象替换为对象element publicbooleanequals(Objectobj)//比较两条单链表是否相等 实现代码: packageQ2; publicclassNode publicTdata; publicNode publicNode(Tdata,Node this.data=data; this.next=next; } publicNode(){ this(null,null); } } packageQ2; publicclassSinglyLinkedList Node publicSinglyLinkedList(E[]element){//由指定数组中的多个对象构造单链表 head=newNode Node for(inti=0;i List.next=newNode(element[i],null); List=List.next; } } publicSinglyLinkedList(SinglyLinkedListlist){//以单链表list构造新的单链表,复制单链表 head=newNode Node Node if(p.data==null){ p=p.next; list_new=list_new.next; } while(p! =null){ list_new.next=newNode list_new=list_new.next; p=p.next; } } publicvoidconcat(SinglyLinkedListlist){//将指定单链表list在当前单链表之后 Node Node Node if(p.data==null) p=p.next; while(p! =null){ rear=p; p=p.next; } if(q==null){ q=q.next; } rear.next=q; } publicNode Node Node if(p==null) p=p.next; while(p.next! =null){ if(p.data==element){ temp=p; } p=p.next; } returntemp; } publicbooleancontain(Eelement){//以查找结果判断单链表是否包含指定对象 booleanflag=false; Node Node if(p==null) p=p.next; while(p! =null){ if(p.data==element){ flag=true; } p=p.next; } returnflag; } publicbooleanremove(Eelement){//移去首次出现的指定对象 Node Node Node booleanflag=false; if(p==null) p=p.next; while(p! =null&&temp==null){ if(p.data==element){ temp=p; flag=true; break; } p=p.next; front=front.next; } front=p.next; returnflag; } publicbooleanreplace(Objectobj,Eelement){//将单链表中的obj对象替换为对象element booleanflag=false; if(obj! =null&&element! =null){ Node while(p! =null){ if(obj.equals(p.data)){ p.data=element; flag=true; } p=p.next; } } returnflag; } publicbooleanequals(Objectobj){//比较两条单链表是否相等 booleanflag=true; SinglyLinkedListx=(SinglyLinkedList)obj; Nodet=x.head.next; Nodes=this.head.next; while(t! =null&&s! =null){ if(t.data! =s.data){ flag=false; break; } t=t.next; s=s.next; } returnflag; } } packageQ2; importjava.util.*; publicclassTest{ staticInteger[]x={3,5,8,11}; staticInteger[]x1={3,5,8,11}; staticInteger[]x2={2,6,8,9,11,15,20}; staticSinglyLinkedList staticSinglyLinkedList staticSinglyLinkedList publicstaticvoiddisList(SinglyLinkedListList){ for(Nodetemp=List.head.next;temp! =null;temp=temp.next){ System.out.printf("%-5d",temp.data); } System.out.println(); } publicstaticvoidconcat(){ List1.concat(List3); } publicstaticvoidFind(){ System.out.println("请输入需要查找的数: "); Scannerscan=newScanner(System.in); Integerelement=scan.nextInt(); Nodet=List1.search(element); if(t! =null) System.out.println(t.data); else System.out.println("List1中找不到指定的数。 "); } publicstaticvoidContain(){ System.out.println("请输入所需包含的数: "); Scannerscan=newScanner(System.in); Integerelement=scan.nextInt(); if(List3.contain(element)) System.out.printf("List3包含指定的数%-5d\n",element); else System.out.printf("List3不包含指定的数%-5d\n",element); } publicstaticvoidremove(){ System.out.println("请输入指定移除的数: "); Scannerscan=newScanner(System.in); Integerelement=scan.nextInt(); if(List3.remove(element)) System.out.printf("%-5d已在List3中移除\n",element); elseSystem.out.printf("%-5d无法在List3中找到,无法移除\n",element); } publicstaticvoidreplace(){ System.out.println("请输入所需交换的两个数: "); Scannerscan=newScanner(System.in); Integerobj=scan.nextInt(); Integerelement=scan.nextInt(); if(List3.replace(obj,element)) System.out.printf("%-5d与%-5d两个数成功交换\n",obj,element); elseSystem.out.println("无法改动"); } publicstaticvoidequals(){ if(List1.equals(List2)) System.out.println("List1与List2两个单链表相等"); elseSystem.out.println("List1与List2两个单链表不相等"); if(List1.equals(List3)) System.out.println("List1与List3两个单链表相等"); elseSystem.out.println("List1与List3两个单链表不相等"); } publicstaticvoidmain(String[]args){ disList(List1); disList(List2); disList(List3); concat(); disList(List1); Find(); Contain(); remove(); replace(); equals(); } } 3、算法实现: 多项式相加 一条单链表可以表示一个一元多项式,每个结点包含三个域: 指数域、系数域和后继结点链。 表示多项式 的单链表如图1所示。 给定两个多项式,实现两个多项式相加算法。 系数指数链 head 实现代码: packageQ3; publicclassNode publicTbase; publicTindex; publicNode publicNode(Tbase,Tindex,Node this.base=base; this.index=index; this.next=next; } publicNode(){ this(null,null,null); } } packageQ3; publicclassPolynomial{ publicstaticNode publicstaticNode Node head=p; for(inti=0;i p.next=newNode p=p.next; } print(head); returnhead; } publicstaticvoidprint(Node a=a.next; while(a.next! =null){ System.out.print(a.base+"^"+a.index+"+"); a=a.next; } System.out.print(a.base+"^"+a.index); System.out.println(); } publicstaticNode Node head=p; a=a.next; b=b.next; while(a! =null&&b! =null){ if(a.index<=b.index){ if(a.index==b.index){ p.next=newNode p=p.next; a=a.next; b=b.next; } else{ p.next=newNode p=p.next; a=a.next; } } else{ p.next=newNode p=p.next; b=b.next; } } if(a==null){ while(b! =null){ p.next=newNode
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 线性