抽象数据类型（abstract data type,ADT）：带有一组操作的一些队形的集合，如：表、集合、图以及与他们各自的操作一起形成的这些对象都可以被看做是抽象数据类型,就像整数、实数、布尔数都是基本数据类型一样；
3.3 Java collections API 中的表
collection(集合) ： 它存储一组类型相同的对象。Collection 接口扩展了Iterable 接口 .
实验Iteration 接口 的类可以拥有增强的for 循环。
Iteration 接口的思路是，集合通过iterater() 方法的调用，每个集合均可创建并返回给客户一个实现Iterator接口的对象，“并将当前位置的概念在对象内部存储下来？（这里不是很懂）”。每次对next()的调用都给出集合的（尚未出现的）下一项。hasNext()返回是否存在下一项。
当要删除集合中的某个元素时，Iterator 的remove() 方法比Collection 集合里的remove()方法安全，所以尽量使用Iterator.remove() 方法。Iterator.remove()方法删除由iterator.next()返回的对象，所以在调用iterator.remove()方法前必须先调用iterator.next()方法。其优点在于： 1、Collection的remove() 必须首先找到要被删除的项，如果知道所要删除的项的准备位置，那么删除它的开销很可能要小很多。 2、如果对正在被迭代的集合进行结构上的改变（即调用Collection的add()/remove()/clear()方法），那么迭代器就不再合法（并会抛出Concurrent-ModificationException异常）。这是为了避免迭代器准备给出的某一项作为下一项，而该项之后的后者被删除，或者一个新的项正好插入到该项的前面的情形（这在并发中很容易出现）；所以在当在需要删除某项时尽量使用Iterator.remove()方法，该点在阿里的开发文档中也是被强调的；
List 接口、ArrayList 类和LinkedList类
List 继承了 Collection 接口,因此它具有包含Collection 接口的所有方法，外加其他定义的方法。
ArrayList 提供了List ADT 的一种可增长数组的实现。其优点在于，对get()和set()的调用花费时间是常数级的，其缺点是新项的插入和已有项的删除需要将该项后面的数全都移动（前/后）一位其开销很大。除非是在末端新增或删除。
LinkList t提供了 List ADT 的一种双向链表实现。其优点新的插入项和现有的删除项开销是常数级的（假设变动项的位置已知），其缺点是不容易做索引，所以其get()方法的调用是昂贵的。
最近加班多，自己时间不多······ 就记一些自己觉得重要的了
练习题：
3.6：Josephus problem:
/**
* Josephus problem: N个人编号从1 到N ，围坐成一个圆圈，从1号开始传递一个热土豆，进过M次传递之后拿着热土豆的人被
* 清楚，围坐继续，最后剩下的人取胜，因此，如果M=0,和 N =5，则5 号游戏人获胜，若M = 1 ，N = 5 那么背清除的人是 2， 4,1，5 则 3 号获胜，编写程解决M 和 N 在一般值下的问题
*/
看到这题有一点朦胧的印象，应该以前上学的时候老师讲过，但我估计上课睡着了，只记得老师说的是一道一群人围成一圈自杀的题。看到这题我首先想到的是用双向链表去实现。因为每次经过M次的传递必须减少一位数，链表结构的删除比数组结构的要快，而且游戏说的是玩家围成一个圈，感觉链表结构更形象一点。首先是创建列表，游戏中就是将人先围成一圈也就是遍历N创建节点个数。其次将末尾的节点的后导.next指向首节点first,将首节点的前导.pre指向最后一个节点：先看代码吧
之后从第一位玩家开始传递，传递了m 次后指针指向了当前要被杀死的人。将当前节点前一个人的后导.next指向当前节点的下一节点，当前的下一个节点的前导指向当前节点的前一个节点，这样当前节点就相当于被删除在该列表中，然后指针指向下一个节点。直到当前节点的下一位是自己的时候，表明游戏结束，当前节点是最后存活下来的人。
第四章 树
二叉树：其中每个节点都不能有多于两个儿子
树的先序遍历：
树的中序遍历：
树的后序遍历：
二叉查找树：
网友评论