java数据结构lab2.docx

java数据结构lab2.docx

《java数据结构lab2.docx》由会员分享，可在线阅读，更多相关《java数据结构lab2.docx（30页珍藏版）》请在冰点文库上搜索。

java数据结构lab2

实验报告二线性表

班级2013055姓名：

学号：

20133732专业：

计算机科学与技术

一、实验目的：

（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）

实现代码：

packagehomework2;

顺序存储：

publicclassSeqList{

publicObject[]element;

publicintlen;

publicSeqList（T[]ele）

{

this.element=newObject[ele.length];

element=ele;

this.len=element.length;

}

publicSeqList（）

{

this（null）;

}

publicvoidappend（SeqListlist）

{

Object[]temp=this.element;

this.element=newObject[this.len+list.len];

for（inti=0;i

{

element[i]=temp[i];

}

for（intj=this.len,k=0;j

{

element[j]=list.element[k];

}

}

}

publicclassSeqCombine{

publicstaticvoidmain（Stringargs[]）

{

Integer[]a={3,5,8,11};

Integer[]b={2,6,8,9,11,15,20};

SeqListA=newSeqList（a）;

SeqListB=newSeqList（b）;

A.append（B）;

for（inti=0;i<=A.element.length-1;i++）

{

System.out.print（A.element[i]+","）;

}

}

}

链式存储

使用尾节点

publicclassNode{

Tdata;

Nodenext;

Node（Tdata,Nodenext）

{

this.data=data;

this.next=next;

}

Node（）

{

this（null,null）;

}

}

publicclassSinglyLinkedList{

publicNodehead;

publicNoderear;

publicSinglyLinkedList（）

{

this.head=newNode（）;

this.rear=newNode（）;

}

publicSinglyLinkedList（T[]element）

{

this（）;

rear=this.head;

for（inti=0;i

{

rear.next=（Node）newNode（element[i],null）;

rear=rear.next;

}

}

}

publicclassCombine{

publicstaticvoidmain（Stringargs[]）

{

Integer[]a={3,5,8,11};

Integer[]b={2,6,8,9,11,15,20};

SinglyLinkedListA=newSinglyLinkedList（a）;

SinglyLinkedListB=newSinglyLinkedList（b）;

A.rear.next=B.head.next;

Nodep=A.head.next;

while（p!

=null）

{

System.out.print（p.data+","）;

p=p.next;

}

}

}

不用尾节点。

publicclassSinglyLinkedList{

publicNodehead;

publicSinglyLinkedList（）

{

this.head=newNode（）;

}

publicSinglyLinkedList（T[]element）

{

this（）;

Noderear=this.head;

for（inti=0;i

{

rear.next=（Node）newNode（element[i],null）;

rear=rear.next;

}

}

}

publicclassCombine{

publicstaticvoidmain（Stringargs[]）

{

Integer[]a={3,5,8,11};

Integer[]b={2,6,8,9,11,15,20};

SinglyLinkedListA=newSinglyLinkedList（a）;

SinglyLinkedListB=newSinglyLinkedList（b）;

Nodep=A.head;

while（p.next!

=null）

{

p=p.next;

}

p.next=B.head.next;

Nodeq=A.head.next;

while（q!

=null）

{

System.out.print（q.data+","）;

q=q.next;

}

}

}

粘贴运行结果

输出：

3,5,8,11,2,6,9,11,15,20

②将LA与LB表归并，要求仍有序（相同元素要保留）

预测输出：

LC=（2,3,5,6,8,8,9,11,11,15,20）

----------顺序存储

publicclassSeqList{

publicObject[]element;

publicintlen;

publicSeqList（T[]ele）

{

this.element=newObject[ele.length];

element=ele;

this.len=element.length;

}

publicSeqList（）

{

this（null）;

}

publicvoidinsert（inti,Tx）

{

if（x==null）

return;

Object[]temp=this.element;

this.element=newObject[temp.length+1];

for（intj=0;j

element[j]=temp[j];

if（i<0）i=0;

if（i>this.len）i=this.len;

for（intj=this.len-1;j>=i;j--）

this.element[j+1]=this.element[j];

this.element[i]=x;

this.len++;

}

}

publicclassSeqCombine{

publicstaticvoidmain（Stringargs[]）

{

Integer[]a={3,5,8,11};

Integer[]b={2,6,8,9,11,15,20};

SeqListA=newSeqList（a）;

SeqListB=newSeqList（b）;

inti=0,j=0;

while（i

{

if（（Integer）A.element[i]<（Integer）B.element[j]）

{

B.insert（j,（Integer）A.element[i]）;

}

if（（j+1）（Integer）B.element[j]&&（Integer）A.element[i]<（Integer）B.element[j+1]）

{

j++;

B.insert（j,（Integer）A.element[i]）;

i++;

if（i>=A.len）

break;

}

if（j（Integer）B.element[j+1]）

{

j++;

}

if（（j+1）

{

B.insert（j+1,（Integer）A.element[i]）;

i++;

j++;

if（i>=A.len）

break;

}

if（（j+1）>=B.len&&（Integer）A.element[i]>（Integer）B.element[j]）

{

B.insert（j+1,（Integer）A.element[i]）;

i++;

}

}

for（intk=0;k

{

System.out.print（B.element[k]+","）;

}

}

}

输出：

2,3,5,6,8,8,9,11,11,15,20

publicclassSeqCombine{

publicstaticvoidmain（Stringargs[]）

{

Integer[]a={3,5,8,11};

Integer[]b={2,6,8,9,11,15,20};

SeqListA=newSeqList（a）;

SeqListB=newSeqList（b）;

inti=0,j=0;

while（i

{

if（（Integer）A.element[i]<（Integer）B.element[j]）

{

B.insert（j,（Integer）A.element[i]）;

}

if（（j+1）（Integer）B.element[j]&&（Integer）A.element[i]<（Integer）B.element[j+1]）

{

j++;

B.insert（j,（Integer）A.element[i]）;

i++;

if（i>=A.len）

break;

}

if（j（Integer）B.element[j+1]）

{

j++;

}

if（（j+1）

{

i++;

j++;

if（i>=A.len）

break;

}

if（（j+1）>=B.len&&（Integer）A.element[i]>（Integer）B.element[j]）

{

B.insert（j+1,（Integer）A.element[i]）;

i++;

}

}

for（intk=0;k

{

System.out.print（B.element[k]+","）;

}

}

}

输出：

2,3,5,6,8,9,11,15,20

-------------链式存储

publicclassNode{

Tdata;

Nodenext;

Node（Tdata,Nodenext）

{

this.data=data;

this.next=next;

}

Node（）

{

this（null,null）;

}

}

publicclassSinglyLinkedList{

publicNodehead;

publicNodelistNode;

publicSinglyLinkedList（）

{

this.head=newNode（）;

}

publicSinglyLinkedList（T[]element）

{

this（）;

Noderear=this.head;

for（inti=0;i

{

rear.next=（Node）newNode（element[i],null）;

rear=rear.next;

}

listNode=this.head.next;

}

//插入

publicvoidinsert（NodeotherNode）

{

otherNode.next=this.listNode.next;

this.listNode.next=otherNode;

}

publicclassSequenceCombine{

publicstaticvoidmain（Stringargs[]）

{

Integer[]a={3,5,8,11};

Integer[]b={2,6,8,9,11,15,20};

SinglyLinkedListA=newSinglyLinkedList（a）;

SinglyLinkedListB=newSinglyLinkedList（b）;

while（A.listNode!

=null）

{

if（A.listNode.data

{

Nodetemp=newNode（A.listNode.data,A.listNode.next）;

temp.next=B.listNode;

B.head.next=temp;

A.listNode=A.listNode.next;

}

if（A.listNode.data>B.listNode.data&&A.listNode.data<=B.listNode.next.data&&B.listNode.next!

=null）

{

B.insert（newNode（A.listNode.data,A.listNode.next））;

if（A.listNode.next!

=null）

{

A.listNode=A.listNode.next;

B.listNode=B.listNode.next;

}

elsebreak;

}

if（A.listNode.data>B.listNode.next.data&&B.listNode.next!

=null）

{

B.listNode=B.listNode.next;

}

if（A.listNode.data>B.listNode.data&&B.listNode.next==null）

{

B.listNode.next=A.listNode;

A.listNode=A.listNode.next;

}

}

//输出

Nodep=B.head.next;

while（p!

=null）

{

System.out.print（p.data+","）;

p=p.next;

}

}

}

输出：

2,3,5,6,8,8,9,11,11,15,20

publicclassSequenceCombine{

publicstaticvoidmain（Stringargs[]）

{

Integer[]a={3,5,8,11};

Integer[]b={2,6,8,9,11,15,20};

SinglyLinkedListA=newSinglyLinkedList（a）;

SinglyLinkedListB=newSinglyLinkedList（b）;

while（A.listNode!

=null）

{

if（A.listNode.data

{

Nodetemp=newNode（A.listNode.data,A.listNode.next）;

temp.next=B.listNode;

B.head.next=temp;

A.listNode=A.listNode.next;

}

if（B.listNode.next!

=null&&A.listNode.data>B.listNode.data&&A.listNode.data

{

B.insert（newNode（A.listNode.data,A.listNode.next））;

if（A.listNode.next!

=null）

{

A.listNode=A.listNode.next;

B.listNode=B.listNode.next;

}

elsebreak;

}

if（B.listNode.next!

=null&&A.listNode.data>B.listNode.next.data&&B.listNode.next!

=null）

{

B.listNode=B.listNode.next;

}

if（B.listNode.next!

=null&&A.listNode.data==B.listNode.next.data）

{

if（A.listNode.next!

=null）

{

A.listNode=A.listNode.next;

B.listNode=B.listNode.next;

}

elsebreak;

}

if（A.listNode.data>B.listNode.data&&B.listNode.next==null）

{

B.listNode.next=A.listNode;

A.listNode=A.listNode.next;

B.listNode=B.listNode.next;

}

}

//输出

Nodep=B.head.next;

while（p!

=null）

{

System.out.print（p.data+","）;

p=p.next;

}

}

}

输出：

2,3,5,6,8,9,11,15,20

粘贴运行结果：

2、在SinglyLinkedList类中增加下列成员方法。

publicSinglyLinkedList（E[]element）//由指定数组中的多个对象构造单链表

publicSinglyLinkedList（SinglyLinkedListlist）//以单链表list构造新的单链表，复制单链表

publicvoidconcat（SinglyLinkedListlist）//将指定单链表list链接在当前单链表之后

publicNodesearch（Eelement）//若查找到指定，则返回结点，否则返回null

publicbooleancontain（Eelement）//以查找结果判断单链表是否包含指定对象

publicbooleanremove（Eelement）//移去首次出现的指定对象

publicbooleanreplace（Objectobj,Eelement）//将单链表中的obj对象替换为对象element

publicbooleanequals（Objectobj）//比较两条单链表是否相等

实现代码：

importExericse1.Node;

publicclassSinglyLinkedList2{

publicNodehead;

publicNoderear;