感谢Java软件结构与数据结构 John Lewis Joseph chase 著 金名译
0. 迭代器关键概念（补充理解）
【1】迭代器是一个对象，它提供了一种依次访问集合中每个元素的方式。
【2】经常把集合定义为Iterable的，说明需要时可以提供一个迭代器。 【3】迭代器可选方法remove使得它可以remove一个元素，而无需再遍历集合。 【4】大多数迭代器是fail-fast的，当迭代器人在使用之时，如果修改集合，将抛出一个异常。 【5】不能假设迭代器访问元素的顺序，除非显式声明。 【6】迭代器往往实现为它所属的集合的内部类。 【7】迭代器检查修改技术，以确保与集合的修改计数保持一致。 【8】for-each循环只能够用于实现了iterator接口的集合中， 【9】如果不是要处理集合中的所有元素或者如果要使用迭代器的remove方法，可以使用显式迭代器而不是for-each循环。 【10】如果底层集合不是由迭代器本身进行修改的，fail-fast迭代器将快速而清晰地发生失败。 【11】fail-fast的实现：在后继的操作中，迭代器会通知集合的修改计数，确保该值不会被修改。如果改了，迭代器就会抛出ConcurrentModificationException异常。2. Java集合API列表
Java集合API提供的列表类主要是支持索引列表。在一定程度上，这些类同无序列表是重叠的。JavaAPI中没有实现事实上的有序列表。
【1】ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。 【2】对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。 【3】对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。 ArrayList和LinkedList都实现了java.util.List接口。
3. 使用无序列表：学习计划
Course.java
package ds.java.ch06;import java.io.Serializable;/** * @author LbZhang * @version 创建时间：2015年11月18日 上午10:19:57 * @description 类说明 */public class Course implements Serializable{ private String prefix; private int number; private String title; private String grade; public Course(String prefix, int number, String title, String grade) { super(); this.prefix = prefix; this.number = number; this.title = title; if(grade==null){ this.grade = ""; }else{ this.grade = grade; } } public Course(String prefix, int number, String title) { this(prefix, number, title, ""); } public String getPrefix() { return prefix; } public void setPrefix(String prefix) { this.prefix = prefix; } public int getNumber() { return number; } public void setNumber(int number) { this.number = number; } public String getTitle() { return title; } public void setTitle(String title) { this.title = title; } public String getGrade() { return grade; } public void setGrade(String grade) { this.grade = grade; } /** * Returns true if this course has been taken * * @return true if this course has been taken and false otherwise */ public boolean taken() { return !grade.equals(""); } public boolean equals(Object other) { boolean result = false; if (other instanceof Course) { Course otherCourse = (Course) other; if (prefix.equals(otherCourse.getPrefix()) && number == otherCourse.getNumber()) result = true; } return result; } public String toString() { String result = prefix + " " + number + ": " + title; if (!grade.equals("")) result += " [" + grade + "]"; return result; }} ProgramOfStudy.java
package ds.java.ch06;import java.io.FileInputStream;import java.io.FileOutputStream;import java.io.IOException;import java.io.ObjectInputStream;import java.io.ObjectOutputStream;import java.io.Serializable;import java.util.Iterator;import java.util.LinkedList;import java.util.List;/** * @author LbZhang * @version 创建时间：2015年11月17日 上午11:30:41 * @description 类说明 */public class ProgramOfStudy implements Iterable, Serializable { private List list; public ProgramOfStudy() { list = new LinkedList (); } public void addCourse(Course course) { if (course != null) list.add(course); } public Course find(String prefix, int number) { for (Course course : list) if (prefix.equals(course.getPrefix()) && number == course.getNumber()) return course; return null; } /** * 在某个元素之后添加元素 * @param target * @param newCourse */ public void addCourseAfter(Course target, Course newCourse) { if (target == null || newCourse == null) return; int targetIndex = list.indexOf(target);//获取索引 if (targetIndex != -1) list.add(targetIndex + 1, newCourse); } public void replace(Course target, Course newCourse) { if (target == null || newCourse == null) return; int targetIndex = list.indexOf(target); if (targetIndex != -1) list.set(targetIndex, newCourse); } public String toString() { String result = ""; for (Course course : list) result += course + "\n"; return result; } public Iterator iterator() { return list.iterator(); } public void save(String fileName) throws IOException { FileOutputStream fos = new FileOutputStream(fileName); ObjectOutputStream oos = new ObjectOutputStream(fos); oos.writeObject(this); oos.flush(); oos.close(); } public static ProgramOfStudy load(String fileName) throws IOException, ClassNotFoundException { FileInputStream fis = new FileInputStream(fileName); ObjectInputStream ois = new ObjectInputStream(fis); ProgramOfStudy pos = (ProgramOfStudy) ois.readObject(); System.out.println(pos); ois.close(); return pos; }}
POSTester.java
package ds.java.ch06;import java.io.IOException;/** * @author LbZhang * @version 创建时间：2015年11月18日 上午9:46:48 * @description 类说明 */public class POSTester { public static void main(String[] args) throws IOException, ClassNotFoundException { ProgramOfStudy pos = new ProgramOfStudy(); pos.addCourse(new Course("CS", 101, "Introduction to Programming", "A-")); pos.addCourse(new Course("ARCH", 305, "Building Analysis", "A")); pos.addCourse(new Course("GER", 210, "Intermediate German")); pos.addCourse(new Course("CS", 320, "Computer Architecture")); pos.addCourse(new Course("THE", 201, "The Theatre Experience")); Course arch = pos.find("CS", 320); pos.addCourseAfter(arch, new Course("CS", 321, "Operating Systems")); Course theatre = pos.find("THE", 201); theatre.setGrade("A-"); Course german = pos.find("GER", 210); pos.replace(german, new Course("FRE", 110, "Beginning French", "B+")); System.out.println(pos); pos.save("ProgramOfStudy");// pos = pos.load("ProgramOfStudy");// System.out.println(pos); }} 4. 约瑟夫问题
4.1 索引列表实现
package ds.java.ch06;import java.util.ArrayList;import java.util.List;import java.util.Scanner;/** * @author LbZhang * @version 创建时间：2015年11月18日 上午11:18:20 * @description 约瑟夫问题 * */public class Josephus { public static void main(String[] args) { int numPeople, skip, targetIndex; List list = new ArrayList (); Scanner in = new Scanner(System.in); // get the initial number of soldiers System.out.print("Enter the number of soldiers: "); numPeople = in.nextInt(); in.nextLine(); // get the number of soldiers to skip System.out.print("Enter the number of soldiers to skip: "); skip = in.nextInt(); if(numPeople 2) { System.out.println(list.remove(targetIndex)); if (list.size() > 0) targetIndex = (targetIndex + skip) % list.size(); } System.out.println(list); }} 4.2 数组实现
package ds.java.ch06;import java.util.Scanner;/** * @author LbZhang * @version 创建时间：2015年11月18日 下午12:23:55 * @description 类说明 */public class MyJosephus { private int total;// 总人数 private int numCount;// 从当前开始第几个出列 private int beginNum;// 开始编号 private int[] solider;// 士兵队列 private int[] outSequence;// 出队次序 public MyJosephus(int total, int numCount, int beginNum) { super(); this.total = total; this.numCount = numCount; this.beginNum = beginNum; this.solider = new int[total]; // 初始化 for (int i = 0; i < solider.length; i++) { solider[i] = i; } this.outSequence = new int[total]; } public void exec() { int counter = 0;// /标价变量 int i = this.beginNum; int j = 0; int killperson = 0; while (true) { if (solider[i] != -1) { // pserson[i]的值是-1，代表出环 // 没有出环，计数器加1 counter++; // 判定是否数目达到numCount if ((counter) % numCount == 0) { outSequence[j++] = i + 1;// 填入队列 killperson++; solider[i] = -1;// 杀死当前编号士兵 } } i = (i + 1) % total;// 向后遍历 if (killperson == total) { break; } } System.out.println("出环按顺序为："); for (int k = 0; k < outSequence.length; k++) { // 输出出环顺序 System.out.print(outSequence[k] + " "); } } public static void main(String[] args) { int total = 0; int numCount = 0; int begin = 0; Scanner scn = new Scanner(System.in); while (true) { System.out.println("Input total num:"); total = scn.nextInt(); System.out.println("Input numCount:"); numCount = scn.nextInt(); System.out.println("Input begin:"); begin = scn.nextInt(); if (total != 0 && numCount != 0 && total > numCount) { MyJosephus mj = new MyJosephus(total, numCount, begin); mj.exec(); break; } else { System.out.println("您输入的数据不合理，请重试！"); } } }} 输出结果：
