《数据结构Java版》习题解答.docx

《数据结构Java版》习题解答.docx

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

《数据结构Java版》习题解答

第1章Java程序设计基础

【习1.1】实验0.1哥德巴赫猜想。

【习1.2】实验0.2杨辉三角形。

【习1.3】实验0.3金额的中文大写形式。

【习1.4】实验0.4下标和相等的数字方阵。

输出下列方阵（当n=4时）。

1267或13410

3581325911

491214681215

101115167131416

采用二维数组实现。

二维数组中，每一条斜线上各元素下标和相等，如图0.1所示。

图1.2下标和相等的数字方阵算法描述

程序如下。

publicclassUpmat

{

publicstaticvoidmain（Stringargs[]）

{

intn=4;//阶数

int[][]mat=newint[n][n];

intk=1;//k是自然数，递增变化

booleanup=true;//方向向上

for（intsum=0;sum

{

if（up）

for（inti=sum;i>=0;i--）

mat[i][sum-i]=k++;//k先赋值后自加

else

for（inti=0;i<=sum;i++）

mat[i][sum-i]=k++;

up=!

up;//方向求反

}

for（intsum=n;sum<2*n-1;sum++）//右下三角

{

if（up）

for（intj=sum-n+1;j

mat[sum-j][j]=k++;

else

for（intj=n-1;j>sum-n;j--）

mat[sum-j][j]=k++;

up=!

up;

}

for（inti=0;i

{

for（intj=0;j

System.out.print（""+mat[i][j]）;

System.out.println（）;

}

}

}

【习1.1】实验0.5找出一个二维数组的鞍点

【习1.2】实验0.6复数类。

【习1.3】实验0.8图形接口与实现图形接口的类

第2章

绪论

【习2.1】实验1.1判断数组元素是否已按升序排序。

程序见例1.4的SortedArray.java。

publicstaticbooleanisSorted（int[]table）//判断整数数组是否已按升序排序

{//若已排序返回true，否则返回false

if（table==null）

returnfalse;

for（inti=0;i

if（table[i]>table[i+1]）

returnfalse;

returntrue;

}

publicstaticbooleanisSorted（Comparable[]table）//判断对象数组是否已按升序排序

{//若已排序返回true，否则返回false

if（table==null）

returnfalse;

for（inti=0;i

if（table[i].compareTo（table[i+1]）>0）

returnfalse;

returntrue;

}

【习2.2】实验1.3用递归算法求两个整数的最大公因数。

publicclassGcd

{

publicstaticintgcd（inta,intb）//返回a,b的最大公因数，递归方法

{

if（b==0）

returna;

if（a<0）

returngcd（-a,b）;

if（b<0）

returngcd（a,-b）;

returngcd（b,a%b）;

}

publicstaticvoidmain（Stringargs[]）

{

inta=12,b=18,c=24;

System.out.println（"gcd（"+a+","+b+","+c+"）="+gcd（gcd（a,b）,c））;//获得3个整数最大公因数

}

}

第3章

线性表

【习3.1】习2-5图2.19的数据结构声明。

table数组元素为单链表，声明如下：

SinglyLinkedListtable[]

【习3.2】习2-6如果在遍历单链表时，将p=p.next语句写成p.next=p，结果会怎样？

使p.next指向p结点自己，改变了结点间的链接关系，丢失后继结点，如图2.1所示。

图3.2p.next=p将改变结点间的链接关系

【习3.1】实验2.2由指定数组中的多个对象构造单链表。

在SinglyLinkedList单链表类中，增加构造方法如下。

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

{

this.head=null;

if（element!

=null&&element.length>0）

{

this.head=newNode（element[0]）;

Noderear=this.head;

inti=1;

while（i

{

rear.next=newNode（element[i++]）;

rear=rear.next;

}

}

}

【习3.2】实验2.2单链表的查找、包含、删除操作详见8.2.1。

单链表的以下查找、包含、删除等操作方法详见8.2.1顺序查找。

publicNodesearch（Eelement,Nodestart）//从单链表结点start开始顺序查找指定对象

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

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

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

【习3.3】实验2.2单链表的替换操作。

在SinglyLinkedList单链表类中，增加替换操作方法如下。

publicbooleanreplace（Objectobj,Eelement）//将元素值为obj的结点值替换为element

{//若替换成功返回true，否则返回false，O（n）

if（obj==null||element==null）

returnfalse;

Nodep=this.head;

while（p!

=null）

{

if（obj.equals（p.data））

{

p.data=element;

returntrue;

}

p=p.next;

}

returnfalse;

}

【习3.4】实验2.2首尾相接地连接两条单链表。

在SinglyLinkedList单链表类中，增加替换操作方法如下。

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

{

if（this.head==null）

this.head=list.head;

else

{

Nodep=this.head;

while（p.next!

=null）

p=p.next;

p.next=list.head;

}

}

【习3.5】实验2.2复制单链表。

在SinglyLinkedList单链表类中，增加构造方法如下。

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

{//复制单链表

this.head=null;

if（list!

=null&&list.head!

=null）

{

this.head=newNode（list.head.data）;

Nodep=list.head.next;

Noderear=this.head;

while（p!

=null）

{

rear.next=newNode（p.data）;

rear=rear.next;

p=p.next;

}

}

}

【习3.6】实验2.2单链表构造、复制、比较等操作的递归方法。

由指定数组中的多个对象构造单链表的操作也可设计为以下的递归方法：

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

{

this.head=null;

if（element!

=null）

this.head=create（element,0）;

}

privateNodecreate（E[]element,inti）//由指定数组构造单链表，递归方法

{

Nodep=null;

if（i

{

p=newNode（element[i]）;

p.next=create（element,i+1）;

}

returnp;

}

单链表的复制操作也可设计为以下的递归方法：

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

{

this.head=copy（list.head）;

}

privateNodecopy（Nodep）//复制单链表，递归方法

{

Nodeq=null;

if（p!

=null）

{

q=newNode（p.data）;

q.next=copy（p.next）;

}

returnq;

}

比较两条单链表是否相等的操作也可设计为以下的递归方法：

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

{

if（obj==this）

returntrue;

if（objinstanceofSinglyLinkedList）

{

SinglyLinkedListlist=（SinglyLinkedList）obj;

returnequals（this.head,list.head）;

}

returnfalse;

}

privatebooleanequals（Nodep,Nodeq）//比较两条单链表是否相等，递归方法

{

if（p==null&&q==null）

returntrue;

if（p!

=null&&q!

=null）

returnp.data.equals（q.data）&&equals（p.next,q.next）;

returnfalse;

}

【习3.7】建立按升序排序的单链表（不带头结点）。

采用直接插入排序算法将一个结点插入到已排序的单链表中。

importdataStructure.linearList.Node;

importdataStructure.linearList.SinglyLinkedList;//不带头结点的单链表类

publicclassSortedSinglyLinkedListextendsSinglyLinkedList

{

publicSortedSinglyLinkedList（）

{

super（）;

}

publicbooleanadd（Eelement）//根据指定对象的大小插入在合适位置

{

if（element==null||!

（elementinstanceofComparable））

returnfalse;//不能插入null或非Comparable对象

Comparablecmp=（Comparable）element;

if（this.head==null||pareTo（this.head.data）<=0）

this.head=newNode（element,this.head）;//头插入

else

{

Nodefront=null,p=this.head;

while（p!

=null&&pareTo（p.data）>0）

{

front=p;//front是p的前驱结点

p=p.next;

}

front.next=newNode（element,p）;//中间/尾插入

}

returntrue;

}

publicstaticvoidmain（Stringargs[]）

{

SortedSinglyLinkedListlist=newSortedSinglyLinkedList（）;

intn=10;

System.out.print（"insert：

"）;

for（inti=0;i

{

intk=（int）（Math.random（）*100）;//产生随机数

if（list.add（newInteger（k）））

System.out.print（k+""）;

}

System.out.println（"\nlist:

"+list.toString（））;

}

}

程序多次运行结果如下：

insert：

2248509717119675080

list:

（9,19,22,48,50,50,67,71,71,80）

insert：

42335289131150297834

list:

（11,13,29,33,34,42,50,52,78,89）

insert：

6916990206814739076

list1:

（0,14,16,20,68,69,73,76,90,99）

【习3.8】实验2.6带头结点的循环双链表类，实现线性表接口。

packagedataStructure.linearList;

importdataStructure.linearList.DLinkNode;//导入双链表结点类

importdataStructure.linearList.LList;//导入线性表接口

publicclassCHDoublyLinkedListimplementsLList//带头结点的循环双链表类

{

protectedDLinkNodehead;//头指针

publicCHDoublyLinkedList（）//构造空链表

{

this.head=newDLinkNode（）;//创建头结点，值为null

this.head.prev=head;

this.head.next=head;

}

publicbooleanisEmpty（）//判断双链表是否为空

{

returnhead.next==head;

}

//以下算法同循环单链表，与单链表的差别在于，循环条件不同

publicintlength（）//返回双链表长度

{

inti=0;

DLinkNodep=this.head.next;//此句与单链表不同

while（p!

=head）//循环条件与单链表不同

{

i++;

p=p.next;

}

returni;

}

publicEget（intindex）//返回序号为index的对象

{

if（index>=0）

{

intj=0;

DLinkNodep=this.head.next;

while（p!

=head&&j

{

j++;

p=p.next;

}

if（p!

=head）

return（E）p.data;

}

returnnull;

}

publicEset（intindex,Eelement）//设置index序号对象为element

{

if（index>=0&&element!

=null）

{

intj=0;

DLinkNodep=this.head.next;

while（p!

=head&&j

{

j++;

p=p.next;

}

if（p!

=head）

{

Eold=（E）p.data;

p.data=element;

returnold;

}

}

returnnull;

}

publicStringtoString（）

{

Stringstr="（";

DLinkNodep=this.head.next;

while（p!

=head）

{

str+=p.data.toString（）;

p=p.next;

if（p!

=head）

str+=",";

}

returnstr+"）";

}

//双链表的插入、删除算法与单链表不同

publicbooleanadd（intindex,Eelement）//插入element对象，插入后对象序号为index

{//若操作成功返回true，O（n）

if（element==null）

returnfalse;//不能添加空对象（null）

intj=0;

DLinkNodefront=this.head;

while（front.next!

=head&&j

{

j++;

front=front.next;

}

DLinkNodeq=newDLinkNode（element,front,front.next）;//插入在front结点之后

front.next.prev=q;

front.next=q;

returntrue;

}

publicbooleanadd（Eelement）//在单链表最后添加对象，O

（1）

{

if（element==null）

returnfalse;//不能添加空对象（null）

DLinkNodeq=newDLinkNode（element,head.prev,head）;

head.prev.next=q;//插入在头结点之前，相当于尾插入

head.prev=q;

returntrue;

}

publicEremove（intindex）//移除指定位置的对象，O（n）

{//返回被移除的原对象，指定位置序号错误时返回null

Eold=null;

intj=0;

DLinkNodep=this.head.next;

while（p!

=head&&j

{

j++;

p=p.next;

}

if（p!

=head）

{

old=（E）p.data;//操作成功，返回原对象

p.prev.next=p.next;//删除p结点自己

p.next.prev=p.prev;

}

returnold;

}

publicvoidclear（）//清空线性表

{

this.head.prev=head;

this.head.next=head;

}

//以上实现LList接口

publicstaticvoidmain（Stringargs[]）

{

inti=0;

CHDoublyLinkedListlist=newCHDoublyLinkedList（）;

System.out.println（"删除第"+i+"个结点"+list.remove（0））;

System.out.println（list.toString（））;

for（i=5;i>=0;i--）

list.add（0,newString（（char）（'A'+i）+""））;

for（i=0;i<6;i++）

list.add（newString（（char）（'A'+i）+""））;

//list.add（i,newString（（char）（'A'+i）+""））;

System.out.println（list.toString（））;

System.out.println（"删除第"+i+"个结点"+list.remove（i））;

System.out.println（list.toString（））;

}

}

程序运行结果如下：

删除第0个结点null

（）

（A,B,C,D,E,F,A,B,C,D,E,F）

删除第6个结点A

（A,B,C,D,E,F,B,C,D,E,F）

【习3.9】实验2.5建立按升序排序的循环双链表。

packagedataStructure.linearList;

importdataStructure.linearList.DLinkNode;

importdataStructure.linearList.CHDoublyL