数据结构实验二 线性表.docx

数据结构实验二 线性表实验报告二 线性表 班级： 姓名： 学号： 专业： 一、 实验目的： 理解线性表的逻辑结构、两种存储结构和数据操作； 应用顺序表的基本算法实现集合A=AUB算法，应用顺序表的基本算法实现两有序顺序表的归并算法； 掌握单链表的遍历、插入和删除等操作算法，实现多项式相加。 二、 实验内容： 1、设有线性表 LA和 LB=； 若LA和LB分别表示两个集合A和B，求新集合 AA U B； 预测输出：LA= 实现代码： package Ex1; public class Point int a=0; public Point next=null; public Point(int a) public Point(int a, Point next) this.a=a; this.next=next; this(a,null); - package Ex1; public class SeqList private Point head=null; private Point tail=null; public SeqList public boolean isEmpty public void addHead(int a) head=new Point(a,head); return head=null; head=null; tail=null; if(tail=null) tail=head; public void addTail(int a) public boolean Find(int a) public void addList(SeqList list) public void Pri / TODO Auto-generated method stub for(Point temp=head;temp!=null;temp=temp.next) System.out.printf("%4d",temp.a); for(Point temp=list.head;temp!=null;temp=temp.next) if(Find(temp.a) else Point temp1=new Point(temp.a); tail.next=temp1; tail=tail.next; continue; if(isEmpty) return false; return false; for(Point temp=head;temp!=null;temp=temp.next) if(temp.a=a) return true; else if(isEmpty) else Point temp=new Point(a); tail.next=temp; tail=tail.next; this.addHead(a); - package Ex1; public class Test static int x=3,5,8,11; static int x1=2,6,8,9,11,15,20; static SeqList List1=new SeqList; static SeqList List2=new SeqList; public static void Def public static void Pri public static void Add public static void Pri1 public static void main(String ars) Def; Pri; Add; Pri1; System.out.println("合并后链表内容为："); List1.Pri; List1.addList(List2); System.out.println("链表内容为："); List1.Pri; System.out.println(""); List2.Pri; System.out.println(""); for(int i=0;i<x.length;i+) for(int i=0;i<x1.length;i+) List2.addTail(x1i); List1.addTail(xi); 粘贴运行结果： 将LA与LB表归并，要求仍有序(两种存储结构) 预测输出：LC= package Ex1; public class Point int a=0; public Point next=null; public Point(int a) public Point(int a, Point next) this.a=a; this.next=next; this(a,null); - package Ex1; public class SeqList Point head=null; Point tail=null; public SeqList public boolean isEmpty return head=null; head=null; tail=null; public void addHead(int a) public void addTail(int a) public boolean Find(int a) public void addList(SeqList list) public void addList1(SeqList list) Point temp1,c,temp2; for(Point H=this.head;H!=null;H=H.next) if(H.next=null) for(Point temp=list.head;temp!=null;temp=temp.next) if(Find(temp.a) else Point temp1=new Point(temp.a); tail.next=temp1; tail=tail.next; continue; if(isEmpty) return false; return false; for(Point temp=head;temp!=null;temp=temp.next) if(temp.a=a) return true; else if(isEmpty) else Point temp=new Point(a); tail.next=temp; tail=tail.next; this.addHead(a); head=new Point(a,head); if(tail=null) tail=head; /* H.next=list.head; break; for(Point temp=list.head;temp!=null;temp=temp2) temp2=temp.next; if(H.a<temp.a | H.a=temp.a) else this.head=temp; this.head.next=H; list.head=temp2; break; if(H.a=temp.a | temp.a<H.next.a) c=H.next; H.next=temp; temp.next=c; list.head=temp2; break; Point la=this.head; Point lb=list.head; Point temp; if(la.a=0) return list.head; la=la.next; temp=la.next; for(;lb.next!=null;lb=lb.next) if(lb.next=null) lb.next=la; return list.head; if(la.a<lb.next.a | la.a=lb.next.a) la.next=lb.next; lb.next=la; break; for(;la!=null;la=temp) */ public void Pri / TODO Auto-generated method stub for(Point temp=head;temp!=null;temp=temp.next) System.out.printf("%4d",temp.a); - import java.util.*; public class Test static Scanner scan=new Scanner(System.in); static int x=3,5,8,11; static int x1=2,6,8,9,11,15,20; static SeqList List1=new SeqList; static SeqList List2=new SeqList; public static void Def public static void Pri public static void Add List1.addList(List2); System.out.println("链表内容为："); List1.Pri; System.out.println(""); List2.Pri; System.out.println(""); for(int i=0;i<x.length;i+) for(int i=0;i<x1.length;i+) List2.addTail(x1i); List1.addTail(xi); package Ex1; public static void Pri1 public static void main(String ars) Def; Pri; System.out.println("请选择要进行的功能："); System.out.println(" A、合并去相同项 B、合并并排序，不去String x=scan.next; if(x.equals("A") else scan.close; List1.addList1(List2); List1.Pri; Add; Pri1; List1.Pri; 相同项"); 粘贴运行结果： 2、在SinglyLinkedList类中增加下列成员方法。 public SinglyLinkedList(E element)/由指定数组中的多个对象构造单链表 public SinglyLinkedList(SinglyLinkedList list)/以单链表list构造新的单链表，复制单链表 public void concat(SinglyLinkedList list)/将指定单链表list链接在当前单链表之后 public Node<E> search(E element)/若查找到指定，则返回结点，否则返回null public boolean contain (E element)/以查找结果判断单链表是否包含指定对象 public boolean remove (E element)/移去首次出现的指定对象 public boolean replace (Object obj, E element)/将单链表中的obj对象替换为对象element public boolean equals(Object obj)/比较两条单链表是否相等 实现代码： package Ex2; public class Node<E> E a; Node<E> x; int k; public Node public Node(E a,int k) this.a=a; this.x=null; this.k=k; this.a=null; this.x=null; k=0; - package Ex2; public class SinglyLinkedList<E> public Node<E> head=null; public Node<E> tail=null; public SinglyLinkedList(E element)/由指定数组中的多个对象构造单链表 public SinglyLinkedList(SinglyLinkedList<E> list)/以单链表list构造新的单int n=0; this.head=new Node<E>(element0,n); tail=head; for(int i=1;i<element.length;i+) n+; tail.x=new Node<E>(elementi,n); tail=tail.x; 链表，复制单链表 this.head=new Node<E> (E) list.head.a,list.head.k); tail=head; for(Node<E> temp=list.head.x;temp!=null;temp=temp.x) tail.x=new Node<E>(E) temp.a,temp.k); tail=tail.x; public void concat(SinglyLinkedList<E> list)/将指定单链表list链接在当前 public Node<E> search(E element)/若查找到指定，则返回结点，否则返回null public boolean contain (E element)/以查找结果判断单链表是否包含指定对象 public boolean remove (E element)/移去首次出现的指定对象 Node<E> n1=this.head; for(Node<E> temp=this.head.x;temp!=null;temp=temp.x) return false; if(element instanceof Integer) else if(temp.a.equals(element) return true; if(temp.a=element) return true; Node<E> x = null; for(x=this.head;x!=null;x=x.x) return null; if(element instanceof Integer) else if(x.a.equals(element) return x; if(x.a=element) return x; this.tail.x=list.head; 单链表之后 Node<E> n2=null; n2=this.search(element); int key=n2.k; if(n1=null) return false; return false; if(n1.k=key) else while(n1!=null) n2=n1.x; if(n1.k=key) n1=n1.x; n1.x=n2.x; return true; this.head=n1.x; return true; else public boolean replace (Object obj, E element)/将单链表中的obj对象替换为 Node<E> n1=this.head; Node<E> n2=null; n2=this.search(element); int key=n2.k; if(n1=null) return false; if(n1.k=key) else while(n1!=null) n2=n1.x; if(n2.k=key) n2.a=(E) obj; return true; this.head.a=(E) obj; return true; else 对象element n1=n1.x; return false; public boolean equals(SinglyLinkedList<E> list)/比较两条单链表是否相等 Node<E> temp1=list.head; for(Node<E> temp=this.head;temp!=null;temp=temp.x) if(temp1.x.a!=null) return true; return false; if(temp1.x=null) temp1=temp1.x; return false; return false; if(!(temp1.a.equals(temp.a) 3、算法实现：多项式相加 一条单链表可以表示一个一元多项式，每个结点包含三个域：指数域、系数域和后继42结点链。表示多项式3x-6x+5x-10的单链表如图1所示。给定两个多项式，实现两个多项式相加算法。 系数 指数 链 head 3 4 -6 2 5 1 -10 0 实现代码： package EX3; public class Point int factor ; int index ; Point next=null; public Point(int a,int b) public Point(int a,int b,Point x) this.factor=a; this.index=b; this.factor=a; this.index=b; this.next=x; - package EX3; public class pol public Point head=null; public Point tail=null; public pol(int ele) public Point Add(pol l) Point p=l.head; Point r=null; Point temp1=null; for(;p!=null;p=p.next) for(Point temp=this.head;temp!=null;temp=temp.next) if(temp=this.head && p=l.head) if(p.index=temp.index) if(p.index=temp.index) temp.factor+=p.factor; r=temp; break; if(p.index>temp.index) r=p; r.next=temp; break; this.head=new Point(ele00,ele01); tail=head; for(int i=1;i<ele.length;i+) tail.next=new Point(elei0,elei1); tail=tail.next; else temp.factor+=p.factor; break; if(temp.next=null && p.index!=temp.index) temp1=new Point(p.factor,p.index); this.tail.next=temp1; this.tail=this.tail.next; break; return r; public void collate public String Pri String s=null; for(Point temp=this.head;temp!=null;temp=temp.next) if(temp=this.head) if(temp.next=null) if(temp.next.factor>0 && temp.next!=null) s+=(temp.factor+"x"+temp.index+"+") ; s+=(temp.factor+"x"+temp.index); break; if(temp.next.factor>0 && temp.next!=null) s=(temp.factor+"x"+temp.index+"+") ; s=(temp.factor+"x"+temp.index) ; else continue; int a,b; for(Point temp=this.head;temp.next!=null;temp=temp.next) if(temp.index<temp.next.index) a=temp.next.factor; b=temp.next.index; temp.next.factor=temp.factor; temp.next.index=temp.index; temp.factor=a; temp.index=b; else s+=(temp.factor+"x"+temp.index) ; return s; - package EX3; public class test static int a=10,4,5,3,2,2,3,0; static int b=5,4,5,2,6,1,4,0; static pol p1=new pol(a); static pol p2=new pol(b); public static void main(String args) Point r=p1.Add(p2); p1.head=r; p1.collate; System.out.println(p1.Pri); for(Point temp=p1.head;temp!=null;temp=temp.next) System.out.println(temp.factor+" "+temp.index); 粘贴运行结果： 三、 心得体会：