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

《《数据结构Java版》习题解答.doc》由会员分享，可在线阅读，更多相关《《数据结构Java版》习题解答.doc（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、如有侵权，请联系网站删除，仅供学习与交流数据结构Java版习题解答【精品文档】第 25 页第0章 Java程序设计基础【习0.1】 实验0.1 哥德巴赫猜想。【习0.2】 实验0.2 杨辉三角形。【习0.3】 实验0.3 金额的中文大写形式。【习0.4】 实验0.4 下标和相等的数字方阵。输出下列方阵（当n=4时）。1267 或 1341035813 25911491214 68121510111516 7131416采用二维数组实现。二维数组中，每一条斜线上各元素下标和相等，如图0.1所示。图0.1 下标和相等的数字方阵算法描述程序如下。public class Upmat public s

2、tatic void main(String args) int n=4; /阶数 int mat = new intnn; int k=1; /k是自然数，递增变化 boolean up = true; /方向向上 for (int sum=0; sum=0; i-) matisum-i = k+; /k先赋值后自加 else for (int i=0; i=sum; i+) matisum-i = k+; up=!up; /方向求反 for (int sum=n; sum2*n-1; sum+) /右下三角 if (up) for (int j=sum-n+1; jsum-n; j-) m

3、atsum-jj = k+; up=!up; for (int i=0; imat.length; i+) /输出二维数组元素 for (int j=0; jmati.length; j+) /i、j是行、列下标 System.out.print( +matij); System.out.println();【习0.5】 实验0.5 找出一个二维数组的鞍点【习0.6】 实验0.6 复数类。【习0.7】 实验0.8 图形接口与实现图形接口的类第1章 绪论【习1.1】 实验1.1 判断数组元素是否已按升序排序。程序见例1.4的SortedArray.java。public static boole

4、an isSorted(int table) /判断整数数组是否已按升序排序 /若已排序返回true，否则返回false if (table=null) return false; for (int i=0; itablei+1) return false; return true;public static boolean isSorted(Comparable table) /判断对象数组是否已按升序排序 /若已排序返回true，否则返回false if (table=null) return false; for (int i=0; i0) return false; return tr

5、ue;【习1.2】 实验1.3 用递归算法求两个整数的最大公因数。public class Gcd public static int gcd(int a, int b) /返回a,b的最大公因数，递归方法 if(b=0) return a; if(a0) return gcd(-a, b); if(b0) return gcd(a, -b); return gcd(b, a%b); public static void main(String args) int a=12, b=18, c=24; System.out.println(gcd(+a+,+b+,+c+)=+gcd(gcd(a,

6、b),c); /获得3个整数最大公因数第2章 线性表【习2.1】 习2-5 图2.19的数据结构声明。table数组元素为单链表，声明如下：SinglyLinkedList table【习2.2】 习2-6 如果在遍历单链表时，将p=p.next语句写成p.next=p，结果会怎样？使p.next指向p结点自己，改变了结点间的链接关系，丢失后继结点，如图2.1所示。图2.1 p.next=p将改变结点间的链接关系【习2.3】 实验2.2 由指定数组中的多个对象构造单链表。在SinglyLinkedList单链表类中，增加构造方法如下。public SinglyLinkedList(E elem

7、ent) /由指定数组中的多个对象构造单链表 this.head = null; if (element!=null & element.length0) this.head = new Node(element0); Node rear=this.head; int i=1; while (ielement.length) rear.next = new Node(elementi+); rear = rear.next;【习2.4】 实验2.2 单链表的查找、包含、删除操作详见8.2.1。单链表的以下查找、包含、删除等操作方法详见8.2.1顺序查找。public Node search(E

8、 element, Node start) /从单链表结点start开始顺序查找指定对象public Node search(E element) /若查找到指定对象，则返回结点，否则返回nullpublic boolean contain(E element) /以查找结果判断单链表是否包含指定对象public boolean remove(E element) /移去首次出现的指定对象【习2.5】 实验2.2 单链表的替换操作。在SinglyLinkedList单链表类中，增加替换操作方法如下。public boolean replace(Object obj, E element) /将

9、元素值为obj的结点值替换为element /若替换成功返回true，否则返回false，O(n) if (obj=null | element=null) return false; Node p=this.head; while (p!=null) if (obj.equals(p.data) p.data = element; return true; p = p.next; return false;【习2.6】 实验2.2 首尾相接地连接两条单链表。在SinglyLinkedList单链表类中，增加替换操作方法如下。public void concat(SinglyLinkedLis

10、t list) /将指定单链表list链接在当前单链表之后 if (this.head=null) this.head = list.head; else Node p=this.head; while (p.next!=null) p = p.next; p.next = list.head;【习2.7】 实验2.2 复制单链表。在SinglyLinkedList单链表类中，增加构造方法如下。public SinglyLinkedList(SinglyLinkedList list) /以单链表list构造新的单链表 /复制单链表 this.head = null; if (list!=nu

11、ll & list.head!=null) this.head = new Node(list.head.data); Node p = list.head.next; Node rear = this.head; while (p!=null) rear.next = new Node(p.data); rear = rear.next; p = p.next;【习2.8】 实验2.2 单链表构造、复制、比较等操作的递归方法。由指定数组中的多个对象构造单链表的操作也可设计为以下的递归方法：public SinglyLinkedList(E element) /由指定数组中的多个对象构造单链表

12、 this.head = null; if (element!=null) this.head = create(element,0);private Node create(E element, int i) /由指定数组构造单链表，递归方法 Node p=null; if (ielement.length) p = new Node(elementi); p.next = create(element, i+1); return p;单链表的复制操作也可设计为以下的递归方法：public SinglyLinkedList(SinglyLinkedList list) /以单链表list构造

13、新的单链表 this.head = copy(list.head);private Node copy(Node p) /复制单链表，递归方法 Node q=null; if (p!=null) q = new Node(p.data); q.next = copy(p.next); return q;比较两条单链表是否相等的操作也可设计为以下的递归方法：public boolean equals(Object obj) /比较两条单链表是否相等 if (obj = this) return true; if (obj instanceof SinglyLinkedList) SinglyLi

14、nkedList list = (SinglyLinkedList)obj; return equals(this.head, list.head); return false;private boolean equals(Node p, Node q) /比较两条单链表是否相等，递归方法 if (p=null & q=null) return true; if (p!=null & q!=null) return p.data.equals(q.data) & equals(p.next, q.next); return false;【习2.9】 建立按升序排序的单链表（不带头结点）。采用直

15、接插入排序算法将一个结点插入到已排序的单链表中。import dataStructure.linearList.Node; import dataStructure.linearList.SinglyLinkedList; /不带头结点的单链表类public class SortedSinglyLinkedList extends SinglyLinkedList public SortedSinglyLinkedList() super(); public boolean add(E element) /根据指定对象的大小插入在合适位置 if (element=null | !(elemen

16、t instanceof Comparable) return false; /不能插入null或非Comparable对象 Comparable cmp = (Comparable)element; if (this.head=null | pareTo(this.head.data)=0) this.head = new Node(element,this.head); /头插入 else Node front=null, p=this.head; while (p!=null & pareTo(p.data)0) front = p; /front是p的前驱结点 p = p.next;

17、front.next = new Node(element, p); /中间/尾插入 return true; public static void main(String args) SortedSinglyLinkedList list = new SortedSinglyLinkedList(); int n=10; System.out.print(insert： ); for (int i=0; in; i+) int k = (int) (Math.random()*100); /产生随机数 if (list.add(new Integer(k) System.out.print(

18、k+ ); System.out.println(nlist: +list.toString();程序多次运行结果如下：insert： 22 48 50 9 71 71 19 67 50 80 list: (9, 19, 22, 48, 50, 50, 67, 71, 71, 80)insert： 42 33 52 89 13 11 50 29 78 34 list: (11, 13, 29, 33, 34, 42, 50, 52, 78, 89)insert： 69 16 99 0 20 68 14 73 90 76 list1: (0, 14, 16, 20, 68, 69, 73, 76

19、, 90, 99)【习2.10】 实验2.6 带头结点的循环双链表类，实现线性表接口。package dataStructure.linearList;import dataStructure.linearList.DLinkNode; /导入双链表结点类import dataStructure.linearList.LList; /导入线性表接口public class CHDoublyLinkedList implements LList /带头结点的循环双链表类 protected DLinkNode head; /头指针 public CHDoublyLinkedList() /构造空

20、链表 this.head = new DLinkNode(); /创建头结点，值为null this.head.prev = head; this.head.next = head; public boolean isEmpty() /判断双链表是否为空 return head.next=head; /以下算法同循环单链表，与单链表的差别在于，循环条件不同 public int length() /返回双链表长度 int i=0; DLinkNode p=this.head.next; /此句与单链表不同 while (p!=head) /循环条件与单链表不同 i+; p = p.next;

21、return i; public E get(int index) /返回序号为index的对象 if (index=0) int j=0; DLinkNode p=this.head.next; while (p!=head & j=0 & element!=null) int j=0; DLinkNode p=this.head.next; while (p!=head & jindex) j+; p=p.next; if (p!=head) E old = (E)p.data; p.data = element; return old; return null; public Strin

22、g toString() String str=(; DLinkNode p = this.head.next; while (p!=head) str += p.data.toString(); p = p.next; if (p!=head) str += , ; return str+); /双链表的插入、删除算法与单链表不同 public boolean add(int index, E element) /插入element对象，插入后对象序号为index /若操作成功返回true，O(n) if (element=null) return false; /不能添加空对象（null）

23、 int j=0; DLinkNode front = this.head; while (front.next!=head & jindex) /寻找插入位置，若i=0，插入在头结点之后 j+; front = front.next; DLinkNode q = new DLinkNode(element, front, front.next); /插入在front结点之后 front.next.prev = q; front.next = q; return true; public boolean add(E element) /在单链表最后添加对象，O(1) if (element=n

24、ull) return false; /不能添加空对象（null） DLinkNode q = new DLinkNode(element, head.prev, head); head.prev.next = q; /插入在头结点之前，相当于尾插入 head.prev = q; return true; public E remove(int index) /移除指定位置的对象，O(n) /返回被移除的原对象，指定位置序号错误时返回null E old = null; int j=0; DLinkNode p=this.head.next; while (p!=head & jindex)

25、/定位到待删除结点 j+; p = p.next; if (p!=head) old = (E)p.data; /操作成功，返回原对象 p.prev.next = p.next; /删除p结点自己 p.next.prev = p.prev; return old; public void clear() /清空线性表 this.head.prev = head; this.head.next = head;/以上实现LList接口 public static void main(String args) int i=0; CHDoublyLinkedList list = new CHDoub

26、lyLinkedList(); System.out.println(删除第+i+个结点+list.remove(0); System.out.println(list.toString(); for (i=5; i=0; i-) list.add(0, new String(char)(A+i)+); for (i=0; i6; i+) list.add(new String(char)(A+i)+);/ list.add(i, new String(char)(A+i)+); System.out.println(list.toString(); System.out.println(删除

27、第+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)【习2.11】 实验2.5 建立按升序排序的循环双链表。package dataStructure.linearList;import dataStructure.linearList.DLinkNode;import dataStructure.linearList.CHDoubly

28、LinkedList; /循环双链表类public class SortedCHDLinkedList extends CHDoublyLinkedList /按升序排序的循环双链表类 public SortedCHDLinkedList() super(); public boolean add(E element) /根据指定对象的大小插入在合适位置 /若操作成功返回true，O(n) if (element=null | !(element instanceof Comparable) return false; /不能插入null或非Comparable对象 Comparable cm

29、p = (Comparable)element; if (this.head.prev!=head & pareTo(this.head.prev.data)0) /非空双链表，插入在最后，O(1) DLinkNode q = new DLinkNode(element, head.prev, head); head.prev.next = q; /插入在头结点之前，相当于尾插入 head.prev = q; return true; DLinkNode p=this.head.next; while (p!=head & pareTo(p.data)0) /寻找插入位置 p = p.next

30、; DLinkNode q = new DLinkNode(element, p.prev, p); /插入在p结点之前 p.prev.next = q; p.prev = q; return true; public boolean remove(E element) /删除指定对象 /若操作成功返回true，O(n) if (element=null | !(element instanceof Comparable) return false; Comparable cmp = (Comparable)element; DLinkNode p=this.head.next; while

31、(p!=head & pareTo(p.data)0) /定位到待删除的结点 p = p.next; if (p!=head) p.prev.next = p.next; /删除p结点自己 p.next.prev = p.prev; return true; return false; /未找到指定结点，删除不成功 public static void main(String args) SortedCHDLinkedList list = new SortedCHDLinkedList(); int n=10; System.out.print(insert： ); for (int i=0

32、; in; i+) int k = (int) (Math.random()*100); if (list.add(new Integer(k) System.out.print(k+ ); System.out.println(nlist: +list.toString();程序运行结果如下：insert： 53 1 92 84 24 3 2 73 99 99 list: (1, 2, 3, 24, 53, 73, 84, 92, 99, 99)第3章 栈和队列【习3.1】 习3-5 栈和队列有何异同？栈和队列都是特殊的线性表，两者的区别在于：栈的插入和删除操作只允许在线性表的一端进行，而队列的插