《Java数据结构和算法》第二版 Robert lafore 编程作业 第五章

《Java数据结构和算法》第二版 Robert lafore 编程作业 第五章

5.1 实现一个基于有序链表的优先级队例。队列的删除操作应该删除具有最小
关键字的链结点。
5.2 实现一个基于双向链表的双端队列。（参考前一章上机作业4.2。）使用
都应该能够执行双端队列的基本操作。
5.3 循环链表是一种链表，它的最后一个链结点指向第一个链结点。设计循环
链表有许多方法。有时，用一个指向链表"开始"的指针。然面这么做使链
表不像一个真正的环，而更像一个传统的链表，只不过这个链表的表头和
表尾系在了一起。编写一个类代表循环单链表，它没有表头也没有表尾。
访问这个链表的惟一方式是一个引用current，它能指向任意一个链结点。
这个引用在需要的时候可以沿链表移动。（参考上机作业5.5，那种情况
下用循环链表很合适。）你的链表应该能处理插入、查找和删除。可能会
发现如果这些操作发生在current指向的下一个链结点时将会非常方便。
（因为上一个链结点是单向连接的，不遍历整个循环链表，不可能得到它。
）你也应该可以显示链表（尽管需要在循环链表的某处切断环，以把它们
打印到屏幕上）。step()方法可以把current移动到下一个链结点，在这
个程序中可能也会派上用场。
5.4 实现一个基于上题循环链表的栈类。这个练习不是太难。（然而，实现一
个队列有些难度。除非把循环链表做成双向的。）
5.5 Josephus问题是古代一个著名的数学难题。围绕这个问题有很多故事。其
中一个说Josephus是一群被罗马人抓获的犹太人中的一个，为了不被奴役，
他们选择自杀。他们排成一个圆圈，从某个人开始，沿着圆圈计数。每报
第n个数的人就要离开圆圈去自杀。Josephus不想死，所以他制定了规则，
以使他成为最后一个离开圆圈的人。如果有（例如）20个人的话，他就是
从开头数第7个人，那么他让他们用什么数来进行报数呢？这个问题会越来
越复杂，因为随着过程进行，圆圈在缩小。使用5.3题的循环链表创建一个
应用来模拟这个问题。输入是组成圆圈的人数，要报的数和第一个开始报的
人的位置（通常是1）。输出是被消去的人的列表。当一个人出了圆圈，再
继续从他左边那个人开始计数（假设沿顺时针旋转）。这有一个例子。有7
个人，从1到7，从第一个人开始报数，报到4出圆圈，最后被消去的人的顺
序是4，1，6，5，7，3。最后剩下的人是2。
5.6 下面尝试一些不同的事情：二维链表，通常叫矩阵。这是二维数组的链表
版本。它可以用于某些应用，例如电子表格程序。如果电子表格是基于数
组的，那么在顶端附近插入一个新行时，需要移动下面N*M个单元，这可
能是一个非常缓慢的过程。如果电子表格用矩阵实现，只需要改变N个指针。
为了简单起见，假定用单链表方法（尽管双向链表方法可能对电子表格更
为适合）。每个链结点（除了在第一行和左侧面的链结点）都由它上面和
左面的链结点指着。就是说，可以从左上角的链结点开始移动，找到第三
行第五列的链结点，只要沿着指针向下两行，向右四列即可。假定矩阵有
固定的大小（例如7*10）。应该可以在某个链结点处插入值，并显示矩阵
的内容。

/* 5.1实现一个基于有序链表的优先级队例。队列的删除操作应该删除具有最小关键字的链结点。5.2实现一个基于双向链表的双端队列。（参考前一章上机作业4.2。）使用都应该能够执行双端队列的基本操作。5.3循环链表是一种链表，它的最后一个链结点指向第一个链结点。设计循环链表有许多方法。有时，用一个指向链表"开始"的指针。然面这么做使链表不像一个真正的环，而更像一个传统的链表，只不过这个链表的表头和表尾系在了一起。编写一个类代表循环单链表，它没有表头也没有表尾。访问这个链表的惟一方式是一个引用current，它能指向任意一个链结点。这个引用在需要的时候可以沿链表移动。（参考上机作业5.5，那种情况下用循环链表很合适。）你的链表应该能处理插入、查找和删除。可能会发现如果这些操作发生在current指向的下一个链结点时将会非常方便。（因为上一个链结点是单向连接的，不遍历整个循环链表，不可能得到它。）你也应该可以显示链表（尽管需要在循环链表的某处切断环，以把它们打印到屏幕上）。step()方法可以把current移动到下一个链结点，在这个程序中可能也会派上用场。5.4实现一个基于上题循环链表的栈类。这个练习不是太难。（然而，实现一个队列有些难度。除非把循环链表做成双向的。）5.5Josephus问题是古代一个著名的数学难题。围绕这个问题有很多故事。其中一个说Josephus是一群被罗马人抓获的犹太人中的一个，为了不被奴役，他们选择自杀。他们排成一个圆圈，从某个人开始，沿着圆圈计数。每报第n个数的人就要离开圆圈去自杀。Josephus不想死，所以他制定了规则，以使他成为最后一个离开圆圈的人。如果有（例如）20个人的话，他就是从开头数第7个人，那么他让他们用什么数来进行报数呢？这个问题会越来越复杂，因为随着过程进行，圆圈在缩小。使用5.3题的循环链表创建一个应用来模拟这个问题。输入是组成圆圈的人数，要报的数和第一个开始报的人的位置（通常是1）。输出是被消去的人的列表。当一个人出了圆圈，再继续从他左边那个人开始计数（假设沿顺时针旋转）。这有一个例子。有7个人，从1到7，从第一个人开始报数，报到4出圆圈，最后被消去的人的顺序是4，1，6，5，7，3。最后剩下的人是2。5.6下面尝试一些不同的事情：二维链表，通常叫矩阵。这是二维数组的链表版本。它可以用于某些应用，例如电子表格程序。如果电子表格是基于数组的，那么在顶端附近插入一个新行时，需要移动下面N*M个单元，这可能是一个非常缓慢的过程。如果电子表格用矩阵实现，只需要改变N个指针。为了简单起见，假定用单链表方法（尽管双向链表方法可能对电子表格更为适合）。每个链结点（除了在第一行和左侧面的链结点）都由它上面和左面的链结点指着。就是说，可以从左上角的链结点开始移动，找到第三行第五列的链结点，只要沿着指针向下两行，向右四列即可。假定矩阵有固定的大小（例如7*10）。应该可以在某个链结点处插入值，并显示矩阵的内容。 */package chap05;// sortedList.java// demonstrates sorted list// to run this program: C>java SortedListApp////////////////////////////////////////////////////////////////class Link {public long dData; // data itempublic Link next; // next link in list// -------------------------public Link(long dd) // constructor{dData = dd;}// -------------------------public void displayLink() // display this link{System.out.print(dData + " ");}} // end class Link// //////////////////////////////////////////////////////////////class SortedList {private Link first; // ref to first item// -------------------------public SortedList() // constructor{first = null;}// -------------------------public boolean isEmpty() // true if no links{return (first == null);}// -------------------------public void insert(long key) // insert, in order{Link newLink = new Link(key); // make new linkLink previous = null; // start at firstLink current = first;// until end of list,while (current != null && key > current.dData) { // or key > current,previous = current;current = current.next; // go to next item}if (previous == null) // at beginning of listfirst = newLink; // first --> newLinkelse// not at beginningprevious.next = newLink; // old prev --> newLinknewLink.next = current; // newLink --> old currnt} // end insert()// -------------------------public Link remove() // return & delete first link{ // (assumes non-empty list)Link temp = first; // save firstfirst = first.next; // delete firstreturn temp; // return value}// -------------------------public void displayList() {System.out.print("List (first-->last): ");Link current = first; // start at beginning of listwhile (current != null) // until end of list,{current.displayLink(); // print datacurrent = current.next; // move to next link}System.out.println("");}} // end class SortedList// //////////////////////////////////////////////////////////////// =================================================================// 编程作业 5.1class PriorityQ {private SortedList sortedList;public PriorityQ() {sortedList = new SortedList();}public void insert(long item) {sortedList.insert(item);}public long remove() {return sortedList.remove().dData;}public boolean isEmpty() {return sortedList.isEmpty();}public void display() {sortedList.displayList();}}// =================================================================public class PriorityQApp {public static void main(String[] args) {PriorityQ thePQ = new PriorityQ();thePQ.insert(30);thePQ.insert(50);thePQ.insert(10);thePQ.insert(40);thePQ.insert(20);thePQ.display();while (!thePQ.isEmpty()) {long item = thePQ.remove();System.out.print(item + " "); // 10, 20, 30, 40, 50} // end whileSystem.out.println("");} // end main()}// =================================================================// =================================================================

package chap05;// doublyLinked.java// demonstrates doubly-linked list// to run this program: C>java DoublyLinkedApp////////////////////////////////////////////////////////////////class Link1 {public long dData; // data itempublic Link1 next; // next link in listpublic Link1 previous; // previous link in list// -------------------------public Link1(long d) // constructor{dData = d;}// -------------------------public void displayLink() // display this link{System.out.print(dData + " ");}// -------------------------} // end class Link// //////////////////////////////////////////////////////////////class DoublyLinkedList {private Link1 first; // ref to first itemprivate Link1 last; // ref to last item// -------------------------public DoublyLinkedList() // constructor{first = null; // no items on list yetlast = null;}// -------------------------public boolean isEmpty() // true if no links{return first == null;}// -------------------------public void insertFirst(long dd) // insert at front of list{Link1 newLink = new Link1(dd); // make new linkif (isEmpty()) // if empty list,last = newLink; // newLink <-- lastelsefirst.previous = newLink; // newLink <-- old firstnewLink.next = first; // newLink --> old firstfirst = newLink; // first --> newLink}// -------------------------public void insertLast(long dd) // insert at end of list{Link1 newLink = new Link1(dd); // make new linkif (isEmpty()) // if empty list,first = newLink; // first --> newLinkelse {last.next = newLink; // old last --> newLinknewLink.previous = last; // old last <-- newLink}last = newLink; // newLink <-- last}// -------------------------public Link1 deleteFirst() // delete first link{ // (assumes non-empty list)Link1 temp = first;if (first.next == null) // if only one itemlast = null; // null <-- lastelsefirst.next.previous = null; // null <-- old nextfirst = first.next; // first --> old nextreturn temp;}// -------------------------public Link1 deleteLast() // delete last link{ // (assumes non-empty list)Link1 temp = last;if (first.next == null) // if only one itemfirst = null; // first --> nullelselast.previous.next = null; // old previous --> nulllast = last.previous; // old previous <-- lastreturn temp;}// -------------------------// insert dd just after keypublic boolean insertAfter(long key, long dd) { // (assumes non-empty list)Link1 current = first; // start at beginningwhile (current.dData != key) // until match is found,{current = current.next; // move to next linkif (current == null)return false; // didn't find it}Link1 newLink = new Link1(dd); // make new linkif (current == last) // if last link,{newLink.next = null; // newLink --> nulllast = newLink; // newLink <-- last} else // not last link,{newLink.next = current.next; // newLink --> old next// newLink <-- old nextcurrent.next.previous = newLink;}newLink.previous = current; // old current <-- newLinkcurrent.next = newLink; // old current --> newLinkreturn true; // found it, did insertion}// -------------------------public Link1 deleteKey(long key) // delete item w/ given key{ // (assumes non-empty list)Link1 current = first; // start at beginningwhile (current.dData != key) // until match is found,{current = current.next; // move to next linkif (current == null)return null; // didn't find it}if (current == first) // found it; first item?first = current.next; // first --> old nextelse// not first// old previous --> old nextcurrent.previous.next = current.next;if (current == last) // last item?last = current.previous; // old previous <-- lastelse// not last// old previous <-- old nextcurrent.next.previous = current.previous;return current; // return value}// -------------------------public void displayForward() {System.out.print("List (first-->last): ");Link1 current = first; // start at beginningwhile (current != null) // until end of list,{current.displayLink(); // display datacurrent = current.next; // move to next link}System.out.println("");}// -------------------------public void displayBackward() {System.out.print("List (last-->first): ");Link1 current = last; // start at endwhile (current != null) // until start of list,{current.displayLink(); // display datacurrent = current.previous; // move to previous link}System.out.println("");}// -------------------------} // end class DoublyLinkedList// //////////////////////////////////////////////////////////////// ============================================================================// 编程作业 5.2class DuQueue {private DoublyLinkedList doublyLinkedList;DuQueue() {doublyLinkedList = new DoublyLinkedList();}public void insertLeft(long value) {doublyLinkedList.insertFirst(value);}public void insertRight(long value) {doublyLinkedList.insertLast(value);}public long removeLeft() {return doublyLinkedList.deleteFirst().dData;}public long removeRight() {return doublyLinkedList.deleteLast().dData;}public boolean isEmpy() {return doublyLinkedList.isEmpty();}public void display() {doublyLinkedList.displayForward();}}// ============================================================================public class DuQueueApp {public static void main(String[] args) {DuQueue theQueue = new DuQueue(); // queue holds 5 itemstheQueue.display();theQueue.insertRight(10); // insert 4 itemstheQueue.insertRight(20);theQueue.insertRight(30);theQueue.insertRight(40);theQueue.display();theQueue.removeLeft(); // remove 3 itemstheQueue.removeLeft(); // (10, 20, 30)theQueue.removeLeft();theQueue.display();theQueue.insertLeft(50); // insert 4 more itemstheQueue.insertLeft(60); // (wraps around)theQueue.insertLeft(70);theQueue.insertLeft(80);theQueue.display();theQueue.removeRight(); // remove 3 itemstheQueue.removeRight(); // (10, 20, 30)theQueue.removeRight();theQueue.display();} // end main()} // end class QueueApp

package chap05;class Link2 {public long dData; // data itempublic Link2 next; // next link in list// -------------------------public Link2(long dd) // constructor{dData = dd;}// -------------------------public void displayLink() // display this link{System.out.print(dData + " ");}} // end class Link// ======================================================================// 编程作业 5.3class CircleList {private Link2 current;private int nItems;public CircleList() {current = null;}public void insert(long value) {Link2 link = new Link2(value);if (current == null) {current = link;link.next = link;} else {link.next = current.next;current.next = link;current = link;// 插入元素，current要移动要新元素}nItems++;}public long remove() {// list为空是没有考虑，在调用remove之前应该判断是否为空long temp = current.next.dData;// 删掉current的下一个元素if (current.next == current) { // 只有一个元素时current = null;} else {current.next = current.next.next;}nItems--;return temp;}public long peek() { // 返回最早插入的元素// 调用前要判断是否为空return current.next.dData;}public Link2 find(long value) {Link2 temp = current; // 保存原来的位置Link2 result = null;if (current == null) {return result;}do {step(); // 从current的下一个元素开始比较if (current.dData == value) {result = current;current = temp; // 还原current到原来的位置,这样就不会打乱插入的顺序，current指向最后插入的元素return result;}} while (current != temp); // current到达原来的位置,一周循环结束return result;}// 往下移一步public void step() { // 调用step()方法后，顺序会被打乱if (current != null) {current = current.next;}}public void display() {if (current != null) {Link2 temp = current;do {step(); // 从current的一下个开始显示System.out.print(current.dData + " ");} while (current != temp);}System.out.println();}public boolean isEmpty() {return current == null;}public int size() {return nItems;}}// ======================================================================public class CircleListApp {public static void main(String[] args) {CircleList theList = new CircleList(); // make new listtheList.insert(10); // insert four itemstheList.insert(20); // insert four itemstheList.insert(40); // insert four itemstheList.insert(30); // insert four itemstheList.display(); // display listSystem.out.println("最早插入的元素" + theList.peek());Link2 link = theList.find(40);if (link != null) {System.out.println("find 40!");} else {System.out.println("not find 40!");}long aLink = theList.remove(); // delete linkSystem.out.println("Deleted " + aLink); // display ittheList.display(); // display list} // end main()}

package chap05;// Queue.java// demonstrates queue// to run this program: C>java QueueApp//////////////////////////////////////////////////////////////////====================================================================================//编程作业 5.4 //这个题目有问题，题目要求实现的是栈，这里实现的是队列，栈用单向循环链表不好实现class Queue {private CircleList circleList;private int nItems;// --------------------------public Queue(int s) // constructor{circleList = new CircleList();nItems = 0;}// --------------------------public void insert(long value) // put item at rear of queue{circleList.insert(value);}// --------------------------public long remove() // take item from front of queue{return circleList.remove();}// --------------------------public long peek() // peek at front of queue{return circleList.peek();}// --------------------------public boolean isEmpty() // true if queue is empty{return (circleList.size() == 0);}// --------------------------public int size() // number of items in queue{return circleList.size();}// --------------------------public void display() {circleList.display();}// --------------------------} // end class Queue// //////////////////////////////////////////////////////////////// ====================================================================================public class QueueApp {public static void main(String[] args) {Queue theQueue = new Queue(5); // queue holds 5 itemstheQueue.insert(10); // insert 4 itemstheQueue.insert(20);theQueue.insert(30);theQueue.insert(40);theQueue.remove(); // remove 3 itemstheQueue.remove(); // (10, 20, 30)theQueue.remove();theQueue.insert(50); // insert 4 more itemstheQueue.insert(60); // (wraps around)theQueue.insert(70);theQueue.insert(80);theQueue.display();long n = theQueue.remove(); // (40, 50, 60, 70, 80)System.out.println("删掉" + n);System.out.println("队头元素是" + theQueue.peek());theQueue.display();} // end main()} // end class QueueApp// //////////////////////////////////////////////////////////////

package chap05;//===================================================================================//编程作业 5.5class Josephus {public static long getJosephus(int number) {CircleList circleList = new CircleList();for (int i = 1; i <= number; i++) { // number个人排成环circleList.insert(i);}System.out.print("原始圈子：");circleList.display();System.out.print("出圈顺序：");for (int i = 1; i < number; i++) { // 要删掉number-1个人for (int j = 1; j < 4; j++) { //不能数到四，因为remove()方法删掉的是下一个circleList.step();}System.out.print(circleList.remove() + " ");}System.out.println();return circleList.peek();}public static void main(String[] args) {long number = Josephus.getJosephus(7);System.out.println("Josephus的编号是:" + number);}}// ====================================================================================

package chap05;class Link3 {public int data;public Link3 goRight;public Link3 goDown;public Link3(int d) {data = d;goRight = null;goDown = null;}public Link3() {data = 0;goRight = null;goDown = null;}}// ==========================================================================// 编程作业 5.6// 具本实现可能和题目要求有些出入class TwoDimensionLinkList {private Link3 first;private int high;private int width;public TwoDimensionLinkList(int high, int width) {this.high = high;this.width = width;Link3 row1 = createRow(); // 生成第一行first = row1;for (int i = 2; i <= high; i++) {Link3 row = createRow();connectTwoRow(row1, row); // 连接两行row1 = row;}}// 插入或修改一个值public void insert(int row, int column, int value) {Link3 current = first;for (int i = 1; i < row; i++) {current = current.goDown;}for (int i = 1; i < column; i++) {current = current.goRight;}current.data = value;}// 插入一行public void addRow(int index) {if (high == 0) {// 空矩阵不能添加列return;}if (index < 1 || index > high + 1) {// 插入的位置非法return;}Link3 newRow = createRow(); // 新行Link3 previousRow = first;if (index == 1) { // 插到第一行connectTwoRow(newRow, previousRow);first = newRow;} else if (index == high + 1) { // 插到最后一行后面while (previousRow.goDown != null) {previousRow = previousRow.goDown; // 找到最后一行}connectTwoRow(previousRow, newRow);} else {// 插到中间for (int i = 2; i < index; i++) {previousRow = previousRow.goDown;// 插入行位置的前一行}Link3 currentRow = previousRow.goDown; // 插入行位置connectTwoRow(previousRow, newRow);connectTwoRow(newRow, currentRow);}high++;// 行数加一}// 插入一列public void addColumn(int index) {if (width == 0) {// 空矩阵不能添加列return;}if (index < 1 || index > width + 1) { // 插入的位置非法return;}Link3 newColumn = createColumn();Link3 previousColumn = first;if (index == 1) { // 插到第一列connectTwoColumn(newColumn, previousColumn);first = newColumn;} else {for (int i = 2; i < index; i++) {previousColumn = previousColumn.goRight;// 插入列位置的前一列}Link3 currentColumn = previousColumn.goRight;// 插入列位置connectTwoColumn(previousColumn, newColumn);connectTwoColumn(newColumn, currentColumn);}width++;// 列数加一}// 生成一列private Link3 createColumn() {Link3 first = new Link3();Link3 down = first;for (int i = 2; i <= high; i++) {down.goDown = new Link3();down = down.goDown;}return first;}// 生成一行private Link3 createRow() {Link3 first = new Link3();Link3 right = first;for (int i = 2; i <= width; i++) {right.goRight = new Link3();right = right.goRight;}return first;}// 合并两行private void connectTwoRow(Link3 first1, Link3 first2) {// first2可以为空if (first2 == null) {while (first1 != null) {first1.goDown = null;first1 = first1.goRight;}}while (first1 != null) {first1.goDown = first2;first1 = first1.goRight;first2 = first2.goRight;}}// 合并两列private void connectTwoColumn(Link3 first1, Link3 first2) { // first2可以为空if (first2 == null) {while (first1 != null) {first1.goRight = null;first1 = first1.goDown;}}while (first1 != null) {first1.goRight = first2;first1 = first1.goDown;first2 = first2.goDown;}}// 删除行public Link3 deleteRow(int index) {if (index < 1 || index > high) { // 删除非法行return null;}Link3 previousRow = first; // 要删除行的前一行Link3 destinationRow = first; // 要删除的行if (index == 1) { // 删除第一行first = first.goDown; // first指向第二行就行了} else {for (int i = 1; i < index; i++) {previousRow = previousRow.goDown;// 移动到目标行的前一行}destinationRow = previousRow.goDown;// 目标行Link3 behindRow = previousRow.goDown.goDown;// 目标行后一行connectTwoRow(previousRow, behindRow);}high--; // 行数减少return destinationRow;}// 删除列public Link3 deleteColumn(int index) {if (index < 1 || index > width) { // 删除非法行return null;}Link3 previousColumn = first; // 要删除列的前一列Link3 destinationColumn = first; // 要删除的列if (index == 1) { // 删除第一列first = first.goRight; // first指向第二列就行了} else {for (int i = 1; i < index; i++) {previousColumn = previousColumn.goRight;// 移动到目标列的前一列}destinationColumn = previousColumn.goRight; // 目标列Link3 behindColumn = previousColumn.goRight.goRight; // 目标列后一列connectTwoColumn(previousColumn, behindColumn);}width--; // 列数减一return destinationColumn;}// 删除值public void remove(int row, int column) {Link3 current = first;for (int i = 1; i < row; i++) {current = current.goDown;}for (int i = 1; i < column; i++) {current = current.goRight;}current.data = 0;}// 打印显示public void display() {if (first == null) {System.out.println();return;}Link3 down = first;Link3 right = first;for (int i = 0; i < high; i++) {while (right != null) {System.out.print(right.data);right = right.goRight;}System.out.println();down = down.goDown;right = down;}}}// ==========================================================================public class TwoDimensionLinkListApp {public static void main(String[] args) {TwoDimensionLinkList list = new TwoDimensionLinkList(5, 5);list.addRow(1);list.addColumn(1);list.deleteColumn(1);list.deleteRow(1);list.insert(1, 1, 5);list.insert(2, 2, 6);list.insert(3, 3, 7);list.insert(4, 4, 8);list.insert(5, 5, 9);list.display();}}