Java杂记
1.private等相当于权限。这样太抽象了，举个例子，就是为了防止被入侵，设置的自我保护锁。这样就粗暴地懂了吧。
那么是被谁入侵呢？
自己肯定不用担心自己了。所有最严格的private都是对自己内部的方法都是开放的。
那么这里的权限就是针对其他类来说了。
设置权限就是为了防止其他类的对象随意入侵自己的领地。
也就是设置哪些类可以使用自己的变量以及方法。
2.为什么c++中创建类的时候末尾需要加分号；而java中不加？
c++中加分号，是因为在创建类的时候同时也可以直接实例化对象，
，也可以只创建类不声明对象。而分号；代表一个结尾。也是用于
区分这两种情况。
而java中不存在创建类的同时实例化对象的情况，因此没有分号；
3.c++中有指针，java中没有指针。
java中引用类型创建的变量都是对象的引用，
并没有存放对象本身。
所以java中引用类型的变量在被赋值之前不会成为引用，
它保存一个被称作null的特殊对象的引用，
而如果尝试使用一个没有被赋值的变量，编译器会报错。
可以将引用认为是普通变量语法中的指针，
c++中也有引用变量，但是他们必须使用&符号显式说明。
所以java中的赋值=和c++中的赋值也不一样。
a=a2;
c++中是将a2对象的所有数据都拷贝到另一个a的对象中。
java中是只向a中拷贝了a2指向的存储地址。
现在他们指向的是同一个对象。
java中任何创建对象的工作都必须使用new
new在java中返回一个引用；
new在c++中返回一个指针。
java中不需要对释放空间担心，如果这个引用不存在，系统会自动将这块孔家归入空闲内存区。
这个过程被称为垃圾收集。
内存泄漏在java中不可能出现，或者几乎没有。
参数“c++中通过指针在函数之间传递对象，
从而避免拷贝一个大的对象的系统开销。
在java中，对象经常以引用的形式传递。
这种方法同样避免了对象的拷贝。
相等与同一
java中，对于基本数据类型，可以用过==来判断
是否含有相同的值；
而当使用==判断类时，实际上判断的是类的引用是否一致，
即他们是否指向的是同一个对象。
如果在java中要判断两个对象中是否含有相同的数据，
要使用Object类中的equals（）方法。
而能够使用这个方法是因为java中所有的类都是
从Object类中派生而来的。
java中没有重载操作符。在java中，任何类似的
重新定义都是不可能的。可以使用命名的方法，
例如add（）或其他名字。
java中基本数据类型：
boolean
byte
char 无符号的。
short
int 固定的永远是32位
long
float
double
java与c/c++相比，属于强类型语言，
在其他语言中可以由系统自动进行的转换，
在java中需要显式地转换。
4.数组
正如大多数编程语言一样，一旦创建数组，数组大小便不可改变。
初始化：
当创建整型数组之后，如果不另行指定，那么
整型数组会自动初始化为空。
除非将特定的值赋给数组的数据项，否则他们一直是
特殊的null对象。
如果尝试访问一个含有null的数组数据项，程序就会出现
Null Pointer Assignment
空指针赋值的运行时错误。
java中对数组的正确用法是将java数组封装进
一个类中，类中的数组隐藏起来，他是私有的，所以
只有对应的类中的方法才可以访问他。
用来存储数据对象的类有时被称作容器类。
通常容器类不仅存储数据，并且提供访问
数据的方法和其他诸如排序等复杂操作。
接口：
既然划分了各种各样的类，那么类之间是如何相互通信呢？
类之间的责任分配是面向对象编程的重要方面。
由于类的字段经常是私有的，所以当我们
讨论接口时，经常是指类的方法，他们是用来干什么的
以及他们的参数是什么。
通过调用这些方法，类用户与类对象进行交互。
面向对象最重要的优点之一就是类的接口
可以设计得尽可能方便且高效。
那么如何设计高效的接口呢？
需要重新分配类之间的责任。
类用户需要提出的是什么东西做什么，而不是怎么做。
也就是用户不用考虑底层实现。
在这个过程中相对什么是 类用户可见的，就是抽象。
针对有序数组进行的二分查找：
public int find(long searchKey){
int lowerBound = 0;
int upperBound = nElems -1;
int curIn;
while(true){
curIn = (lowerBound + upperBound )/2;
if(a[curIn] == searchKey ){
return curIn;
}else if (lowerBound > upperBound ){
return nElems;
}else {
if(a[curIn] < searchKey ){
lowerBound = curIn + 1;
}else{
upperBound =curIn - 1;
}
}
}
}
如果lowerBound比upperBound大，那么范围已经不存在了。
当lowerBound等于upperBound，那么范围是一个数据项所以
还需要再一次循环。
有序数组的优点：
最主要的好处是查找的速度比无序数组快多了。
不好的方面是在插入操作中由于所有靠后的数据都需要移动来腾开空间，
所以速度较慢。
有序数组和无序数组中的删除操作都较慢，
这是因为数据项必须向前移动来填补已经删除的数据项的空洞。
有序数组在查找频繁的情况下十分有用，
但是若是插入和删除较为频繁时，无法高效工作。
比如，零售商店的存货清单不适合用有序数组来实现，
这是因为与频繁的进货和出货对应的插入和删除操作会执行得很慢。
创建自己的向量类。
当类用户使用类中的内部数组将要溢出时，
插入算法创建一个大一点的数组，把就数组中的内容复制到新数组中
，然后再插入新数据项，整个过程对于类用户来说是不可见的。
package com.jerry.test;
class Person{
private String lastName;
private String firstName;
private int age;
public Person(String last,String first,int a){
lastName = last;
firstName =first;
age = a;
}
public void displayPerson(){
System.out.print(" Last name: "+lastName);
System.out.print(",First name: "+firstName);
System.out.println(",Age: "+age);
}
public String getLast(){ //get last name
return lastName;
}
}
class ClassDataArray{
private Person[] a; //reference to array
private int nElems; //number of data items;
public ClassDataArray(int max){
a = new Person[max];
nElems = 0;
}
public Person find(String searchName){
int j;
for (j=0; j<nElems ; j++ ){
if (a[j].getLast().equals(searchName) ){
break;
}
}
if (j == nElems){
return null; //can not find it
}else{
return a[j]; //found it
}
}
public void insert(String last,String first,int age){
a[nElems] = new Person(last,first,age);
nElems++;
}
public boolean delete(String searchName){
int j;
for (j=0; j<nElems; j++){
if (a[j].getLast().equals(searchName)){
break;
}
}
if (j==nElems ){
return false;
}else{ //shift down
for (int k=j; k<nElems; k++){
a[k] = a[k+1];
}
nElems--;
return true;
}
}
public void displayA(){
for (int j=0; j<nElems; j++){
a[j].displayPerson();
}
}
}
public class Test {
public static void main(String[] args){
int maxSize = 100;
ClassDataArray arr;
arr = new ClassDataArray(maxSize);
arr.insert("Evvans","Patty",24);
arr.insert("Smith","Lorraine",37);
arr.insert("Yee","Tom",43);
arr.insert("Adams","Henry",63);
arr.insert("Hashimoto","Sato",21);
arr.insert("Stimson","Henry",29);
arr.insert("Velasquez","Jose",72);
arr.insert("Lamarque","Henry",54);
arr.insert("Vang","Minh",22);
arr.insert("Creswell","Lucinda",18);
arr.displayA();
String searchKey = "Stimson";
Person found;
found = arr.find(searchKey);
if(found != null){
System.out.print("Found ");
found.displayPerson();
}else {
System.out.println("can not find "+searchKey);
}
System.out.println("Deleting Smith,Yee,andCreswell...");
arr.delete("Smith");
arr.delete("Yee");
arr.delete("Creswell");
arr.displayA();
}
}
结果：
Last name: Evvans,First name: Patty,Age: 24
Last name: Smith,First name: Lorraine,Age: 37
Last name: Yee,First name: Tom,Age: 43
Last name: Adams,First name: Henry,Age: 63
Last name: Hashimoto,First name: Sato,Age: 21
Last name: Stimson,First name: Henry,Age: 29
Last name: Velasquez,First name: Jose,Age: 72
Last name: Lamarque,First name: Henry,Age: 54
Last name: Vang,First name: Minh,Age: 22
Last name: Creswell,First name: Lucinda,Age: 18
Found Last name: Stimson,First name: Henry,Age: 29
Deleting Smith,Yee,andCreswell…
Last name: Evvans,First name: Patty,Age: 24
Last name: Adams,First name: Henry,Age: 63
Last name: Hashimoto,First name: Sato,Age: 21
Last name: Stimson,First name: Henry,Age: 29
Last name: Velasquez,First name: Jose,Age: 72
Last name: Lamarque,First name: Henry,Age: 54
Last name: Vang,First name: Minh,Age: 22
Process finished with exit code 0
5.简单排序
一旦建立了一个重要的数据库之后，就可能根据某些需求
对数据进行不同方式的排序。
比如对姓名按字母序排序，对学生按年级排序，
对城市按人口增长率排序，对国家按国民生产总值排序。
对数据进行排序有可能只是检索的一个初始步骤。
排序算法固有步骤：
1.比较两个数据项；
2.交换两个数据项，或复制其中一项。
冒泡排序，对应的，沉底排序。
规则：
1.比较两个队员；
2.如果左边的队员高，则两队员交换位置；
3.向右移动一个位置，比较下面两个队员。
沿着这个队列照刚才那样比较下去，一直比较到队列的最右端。
虽然没有完全把所有队员都排好序，但是最高的队员确实已经被排在最优边。
这样，在算法执行的时候，最大的数据项总是“冒泡”到数组的顶端。
在对所有的队员进行了第一趟排序后，进行了n-1次比较，
并且按照队员们的初始位置，进行了最少0次，
最多n-1次的交换。数组最末端的那个数据项就此排定，不需要再移动了。
4。当碰到第一个排定的队员后，就返回队列的左端重新开始下一趟排序。
public void bubbleSort(){
int out,in;
for (out = nElems-1; out>1;out--){
for (in=0; in<out; in++){
if(a[in]>a[in+1]){
swap(in,in+1);
}
}
}
}
private void swap(int one,int two){
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
不变性，反复检查不变性是否为真。
这里不变性是指out右边的所有数据项为有序，
在算法的整个运行过程中这个条件始终为真。
冒泡排序的效率。
第一趟9次比较，第二趟8次比较。。。
一般来说，数组中有n个数据项，那么第一趟就有n-1次，
第二趟就有n-2次，如此类推，
相加之后为n*（n-1）/2
交换和比较次数都和n^2成正比。
选择排序：
选择排序改进了冒泡排序，将必要的交换次数从n^2
减少到了n，不幸的是比较次数仍然保持为n^2.
在选择排序中，不再只比较两个相邻的队员。
因此，需要记录下某一个指定队员的高度。
进行选择排序就是把所有的队员扫描一遍，从中挑出，‘
或者说是选择最矮的一个队员。最爱的这个队员和站在队列最左端的队员交换位置，
就是站到0号位置。现在最左端的队员是有序的了，不需要再交换位置了。
注意，在这个算法中，有序的队员都排列在队列的左边
较小的下标值，而在冒泡排序中则是排列在队列的右边的。
再次扫描球队队列时，就从1号位置开始，还是寻找最矮的，然后和
1号位置的队员进行交换。这个过程持续到所有的队员都排定。
public void selectionSort(){
int out,in,min;
for (out=0; out<nElems-1;out++){
min=out;
for (in=out+1; in<nElems; in++){
if(a[in] <a[min]){
min=in;
}
swap(out,min);
}
}
}
private void swap(int one,int two){
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
因为总共有nElems个数，两两比较，所有
比较的次数一共是nElems-1次，也就是对应的
外层循环的次数为nElems-1次。
不变性：
在选择排序中，下标小于或等于out位置的数据项总是有序的。
选择排序和冒泡排序执行了相同次数的比较。
但是选择排序无疑更快，因为它进行的交换少的多。
插入排序：
在大多数情况下，插入排序算法是这3中简单排序中算法最好的一种。
虽然插入排序算法仍然需要n^2的时间，但是一般情况下，他要比冒泡排序快一倍，比
选择排序还要快一点。
插入排序要做的是在局部有序组中的适当位置插入被标记的队员。
然而要做到这一点，需要把部分已排序的队员右移腾出空间。’
为了提供移动所需的空间，就先让被标记的队员出列。
在程序中，表现出来就是这个数据项被存储在一个
临时变量里面。
现在移动已经排过序的队员来腾出空间。将局部有序中最高的队员
移动到原来被标记队员所在的位置，次高的以此类推。
这个移动过程什么时候结束呢?
在每个位置上队员都向右移动一位，同时被标记的队员和
下一个要移动的队员比较身高。
当吧最后一个比被标记的队员还高的队员一位之后，这个移动的过程就停止了。
最后，局部有序的部分里多了一个队员，而未排序的
不分离少了一个队员。这个队员就是被标记的队员。
下一个要做标记的，应该是未排序部分的最左边的队员。
重复这个过程，直到所有未排序的队员都被插入到
局部有序队列中合适的位置。
public void insertionSort(){
int in,out;
for (out =1; out<nElems; out++){
long temp = a[out];
in =out;
while(in>0 && a[in-1] >= temp){
a[in] = a[in-1];
--in;
}
a[in] = temp;
}
}
插入排序中的不变性：
在每趟结束时，在将temp位置的项插入后，比outer变量
下标号小的数据项都是局部有序的。
对于已经有序或基本有序的数据来说，插入排序要
好得多。当数据有序的时候，while循环的条件总是假，
所以它变成了外层玄幻中的一个简单语句，执行n-1次。
在这种情况下，算法运行只需要n的时间。
然而，如果对于逆序排列的数据，每次比较和移动都会执行，
所以插入排序不比冒泡排序快。
如何针对具体的对象进行排序？
用string类中的compareTo()方法执行insertSort（）方法中的比较工作。
下面是一个含有这个方法的表达式：
a[in-1].getLast().compareTo(temp.getLast())>0
compareTo()方法根据两个string的字典顺序返回给调用者不同的整数值
这两个string，一个是方法的调用者，一个是这个方法的参数。
这里的3种排序算法都可以“就地”完成排序，也就是除了
初始的数组外几乎不需要其他的内存空间。
所有排序算法都需要一个额外的变量来暂时存储交换时的数据项。
6.栈
class StackX{
private int maxSize;
private long[] stackArray;
private int top;
public StackX(int s){
maxSize = s;
stackArray = new long[maxSize];
top = -1;
}
public void push(long j){
stackArray[++top] = j;
}
public long pop(){
return stackArray[top--];
}
public long peek(){
return stackArray[top];
}
public boolean isEmpty(){
return (top == -1);
}
public boolean isFull(){
return (top == maxSize-1);
}
}
出错处理：
当向一个已经满了的栈中再添加一个数据项，
或要从空栈中弹出一个数据项时会发生什么情况。
java语言中，对栈来说，发现这些错误一个好的方法是抛出异常，
异常可以被用户捕获并处理。
栈实例：
1.单词逆序：
package com.jerry.test;
import java.io.*;
class StackX{
private int maxSize;
private char[] stackArray;
private int top;
public StackX(int s){
maxSize = s;
stackArray = new char[maxSize];
top = -1;
}
public void push(char j){
stackArray[++top] = j;
}
public char pop(){
return stackArray[top--];
}
public char peek(){
return stackArray[top];
}
public boolean isEmpty(){
return (top == -1);
}
public boolean isFull(){
return (top == maxSize-1);
}
}
class Reverser{
private String input;
private String output;
public Reverser(String in){
input = in;
}
public String doRev(){
int stackSize = input.length();
StackX theStack = new StackX(stackSize);
for (int j=0; j<input.length(); j++){
char ch = input.charAt(j);
theStack.push(ch);
}
output = "";
while(!theStack.isEmpty()){
char ch = theStack.pop();
output = output+ch;
}
return output;
}
}
public class Stack {
public static void main(String[] args) throws IOException {
String input,output;
while (true){
System.out.print("Enter a string: ");
System.out.flush();
input = getString();
if(input.equals("")){
break;
}
Reverser theReverser = new Reverser(input);
output = theReverser.doRev();
System.out.println("Reversed: "+output);
}
}
public static String getString() throws IOException{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
}
结果：
Enter a string: 李智宇
Reversed: 宇智李
Enter a string: this is a good day!
Reversed: !yad doog a si siht
Enter a string:
栈实例2：分隔符匹配
栈通常用于解析某种类型的文本串。通常，
文本串是用计算机语言写的代码行，而解析他们的程序就是编译器。
栈中的左分隔符
分隔符匹配程序从字符串中不断地读取字符，每次读取一个字符。
若发现他是左分隔符，将他压入栈中。
当从输入中读到一个右分隔符时，弹出 栈顶的左分隔符，并且查看它是否和
右分隔符相匹配。如果他们不匹配，加入一个左大括号一个→小括号，那么程序报错。
package com.jerry.test;
import java.io.*;
import java.security.PublicKey;
class StackX{
private int maxSize;
private char[] stackArray;
private int top;
public StackX(int s){
maxSize = s;
stackArray = new char[maxSize];
top = -1;
}
public void push(char j){
stackArray[++top] = j;
}
public char pop(){
return stackArray[top--];
}
public char peek(){
return stackArray[top];
}
public boolean isEmpty(){
return (top == -1);
}
public boolean isFull(){
return (top == maxSize-1);
}
}
class Reverser{
private String input;
private String output;
public Reverser(String in){
input = in;
}
public String doRev(){
int stackSize = input.length();
StackX theStack = new StackX(stackSize);
for (int j=0; j<input.length(); j++){
char ch = input.charAt(j);
theStack.push(ch);
}
output = "";
while(!theStack.isEmpty()){
char ch = theStack.pop();
output = output+ch;
}
return output;
}
}
class BracketChecker{
private String input;
public BracketChecker(String in){
input = in;
}
public void check(){
int stackSize = input.length();
StackX theStack = new StackX(stackSize);
for (int j=0; j<input.length(); j++){
char ch = input.charAt(j);
switch (ch){
case '{':
case '[':
case '(':
theStack.push(ch);
break;
case '}':
case ']':
case ')':
if (!theStack.isEmpty()){
char chx = theStack.pop();
if ( (ch=='}' && chx!='{' )
|| (ch==']' && chx!='[')
|| (ch==')' && chx!='(') ){
System.out.println("Error: "
+ch+" at "+j);
}
}else {
System.out.println("Error: "
+ch+" at "+j);
}
break;
default:
break;
}
}
if (!theStack.isEmpty()){
System.out.println("Error:missing right delimiter");
}
}
}
public class Stack {
public static void main(String[] args) throws IOException {
String input;
while (true){
System.out.print("Enter string containing" +
"delimiters: ");
System.out.flush();
input = getString();
if(input.equals("")){
break;
}
BracketChecker theChecker = new BracketChecker(input);
theChecker.check();
}
}
public static String getString() throws IOException{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
}
结果：
Enter string containingdelimiters: a{b(c]d}e
Error: ] at 5
Enter string containingdelimiters:
栈是一个概念上的辅助工具，
如果说数组和链表多用于数据的存储。
那么栈、队列等就是经常配合算法用于对数据进行操作。
入栈和出栈的时间复杂度都是1。
7.队列
package com.jerry.test;
class Queue{
private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
public Queue(int s){
maxSize = s;
queArray = new long[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
public void insert(long j){
if(rear == maxSize-1){
rear = -1;
}
queArray[++rear] = j;
nItems++;
}
public long remove(){
long temp = queArray[front++];
if(front == maxSize){
front = 0;
}
nItems--;
return temp;
}
public long peekFront(){
return queArray[front];
}
public boolean isEmpty(){
return (nItems == 0);
}
private boolean isFull(){
return (nItems == maxSize);
}
public int size(){
return nItems;
}
}
public class QueueApp {
public static void main(String[] args){
Queue theQueue = new Queue(5);
theQueue.insert(10);
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.remove();
theQueue.remove();
theQueue.remove();
theQueue.insert(50);
theQueue.insert(60);
theQueue.insert(70);
theQueue.insert(80);
while (!theQueue.isEmpty()){
long n= theQueue.remove();
System.out.print(n);
System.out.print(" ");
}
System.out.println("");
}
}
结果：
40 50 60 70 80
插入：
一般情况，插入操作是rear队尾指针加一后，在队尾指针所指的位置处
插入新的数据。但是，当rear指针指向数组的顶端，
即maxSize-1位置的时候，在插入数据项之前，它必须回绕到数组的
底端。回绕操作把rear设置为-1，因此当rear加1后，它等于0，
是数组底端的下标值。最后nItem加一。
删除：
移除操作总是由front指针得到队头数据项的值，
然后将front加一。但是，如果这样做使front的值超过数组的顶端，front就必须绕回到数组下标为0
的位置上。作这种检验的同时，先将返回值临时存储起来。
最后nItem减一。
那么循环队列出现一个问题。当队列满的时候，
front指针和rear指针取一定的位置，但是当队列为空时，
也可能呈现相同的位置关系。
于是同一时间，队列似乎可能是满的，也可能是空的。
这个问题可以这样解决：
让数组容量比队列数据项个数的最大值还要大一。
队列的效率：
和栈一样，队列中插入数据项和移除数据项的时间复杂度均为1
双端队列：
双端队列就是一个两端都是结尾的队列。队列的每一端
都可以插入数据项和移除数据项。
优先级队列：
像普通队列一样，优先级队列有一个队头和一个队尾，
并且也是从队头移除数据项。
不过在优先级队列中，数据项按关键字的值有序，这样关键字最小的数据项
总是在队头。数据项插入的时候
会按照顺序插入到合适的位置以确保队列的顺序。
在图的最小生成树算法中可以应用优先级队列。
像普通的队列一样，优先级队列在某些计算机系统
中也有很多应用。
例如，在抢占式多任务操作系统中，程序排列在优先级队列中，
这样优先级最高的程序就会得到时间片并得以运行。
很多情况下需要访问具有最小关键字值的数据项，
比如要寻找最便宜的方法或最短的路径去做某件事。
因此，具有最小关键字值的数据项具有最高的优先级。
优先级队列实现中关键的不同是insert函数
public void insert(long item){
int j;
if(nItems == 0){
queArray[nItems++] = item;
}else{
for (j=nItems-1; j>=0 ;j--){
if (item > queArray[j]){
queArray[j+1] = queArray[j];
}else{
break;
}
queArray[j+1] = item;
nItems++;
}
}
}
优先级队列的效率：
插入操作需要n的时间，而删除操作则需要1的时间。
解析算法表达式，之前做过，可以参考
三个一工程阶段的报告。
8.链表
链表，数组之后的第二大主功能为存储数据的数据结构。
这里涉及到一个问题。
在Link类中定义了一个Link类型的域，这看起来很奇怪。
编译器怎样才能不混淆呢？
编译器在不知道一个Link对象占多大空间的情况下，
如何能知道一个包含了相同对象的LInk对象占用多大的空间呢？
在Java语言中这个问题的答案是Link对象是并没有真正地包含
另外一个Link对象，尽管看起来好像包含了。
类型为Link的next字段仅仅是对另外一个Link对象的“引用”
，而不是一个对象。
一个引用是一个对某个对象的参照数值，他是一个极端及内存中的对象地址，
然而不需要知道他的具体值；只要把他当成是一个其买哦的数，它会
告诉你对象在哪里。在给定的计算机操作系统中，所有的引用，不管他指向谁，
大小都是一样的。因此，对编译器来说，知道这个字段的大小
并由此构造出整个Link对象，是没有任何问题的。
链表的不变性：
在链表中，寻找一个特定元素的唯一方法就是沿着这个元素的链
一直向下寻找。
单链表：
在链表头插入一个数据项；
在链表头删除一个数据项
遍历链表显示他的内容
class Link{
public int iData;
public double dData;
public Link next;
public Link(int id,double dd){
iData =id;
dData =dd;
}
public void displayLink(){
System.out.print("{"+iData+" , "+dData+"}");
}
}
构造函数初始化数据，但是这里不需要初始化next字段，
因为当它被创建时自动赋成null值。
当然，为了清晰可见，也可以明确的把他赋成null值。
null值意味着这个字段不指向任何结点，
除非该链结点后来被连接到其他的链结点才改变。
link各个字段的存取权限设为public。
如果他们是private，必须提供公开的方法来访问他们，
这需要额外的代码。
理想情况下，为了安全，可能需要把对link对象的访问
都约束在linklist类的方法中。
然而，如果在这些类中没哟继承的关系，这样做并不太方便。
我们可以使用缺省访问指示符使数据具有“包访问权限”
这样做对这些示例程序倒是没有任何影响的，因为
他们都在用一个目录下。
在一个更加正式的程序中 ，可能需要使link类中的所有数据
字段都设成private的。
linklist类只包含一个数据项：即对链表中国第一个链结点的引用，‘
叫做first。
他是唯一的链表需要维护的永久信息，
用以定位所有其他的链结点。
从first出发，沿着链表通过每个链结点的next字段。
就可以找到其他的链结点。
linklist的构造函数把first赋成null值。
实际上这不是必须的。
正如上面提到的，引用类型在创建之初会自动赋成null值。
public void insertFirst(int id,double dd){
Link newLink = new Link(id,dd);
newLink.next = first;
first = newLink;
}
头结点永远是最新插入的结点。
public Link deleteFirst(){
Link temp = first;
first = first.next;
return temp;
}
删除头结点之前，其实应该先用isEmpty（）方法来核实这一点。
在c++和类似的语言中，在从链表中取下一个链结点后，
需要考虑如何删除这个链结点。
它仍然存在内存中的某个地方法，但是现在没有任何东西指向他。
将如何处理 它呢？
在Java语言中，垃圾收集进程将在未来的某个时刻销毁他，
现在这不是程序员操心的工作。
public void displayList(){
System.out.print("LIst (first-->last): ");
Link current = first;
while (current!=null){
current.displayLink();
current = current.next;
}
System.out.println("");
}
链表的尾端是最后一个链结点，它的next字段为null值，
而不是其他的链结点。这个字段怎么会变成null呢？
因为在连接点被创建时这个字段就是null，而该链结点总是停留在链表的尾端，
后来再也没有改变过。当执行到链表的尾端时，
while循环使用这个条件来终止自己。
双端链表
对最后一个链结点的引用允许像在表头一样，
在表尾直接插入一个链结点。
注意，不要把双端链表和双向链表搞混！！！！
链表的效率：
在表头插入和删除速度很快，仅需要改变一两个引用值，
所以花费1的时间。
链表比数组优越的另外一个重要方面就是
链表需要多少内存就可以用多少内存，并且可以扩展到
所有可用内存。
数组的大小在他创建的时候就固定了；所以经常由于数组太大导致效率低下，
或者数组太小导致空间溢出。
向量是一种可扩展的数组，他可以通过可变长度来解决这个问题
，但是他经常只允许以固定大小的增量来扩展。
例如，快溢出的时候，就增加一倍数组容量。
这个解决方案在内存使用效率上来说还是要比链表的低。
链表实现linkStack
注意整个程序的组织。
linkStackApp类中的main（）方法
只和LinkStack类有关。LinkStack类只和
LinkList类有关。
main（）方法和LinkList类是不进行通信的。
更特别的是，当main（）方法中的一语句调用LinkStakc类中的
push（）操作时，这个方法就调用LinkList类中的
insertFirst()方法插入数据。
9.抽象数据类型
说实话，这个名字就挺抽象的。
抽象是什么？反正你不懂，摸不清楚它的底细，这就叫抽象。
官方解释就是不考虑细节的描述和实现。
就是老板干的活。
ADT中有一个经常被叫做“接口”的规范。他是给类用户看的。
通常是类的共有方法。
在栈中，push（）方法、pop（）方法和其他
类似的方法形成了接口。
有序链表的效率：
在有序链表插入和删除某一项最多需要n次比较，
平均n/2，因为必须沿着链表上一步一步走才能找到正确的位置。
然而，可以在1的时间内找到或删除最小值，
因为它总在表头。
如果一个应用频繁地存取最小项，且不需要快速地插入，
那么有序链表是一个有效的方案选择。
例如：优先级队列可以用有序链表来实现。
表插入排序：
有序链表可以用于一种高效的排序机制。
假设有一个无需数组。
如果从这个数组中取出数据，
然后一个一个地插入有序链表，
他们自动地按顺序排列。把他们从有序表中删除，
重新放入数组，
那么数组就会排好序了。
和基于数组的插入排序相比，表插入排序有一个缺点，
就是它要开辟差不多两倍的空间：
数组和链表必须同时在内存中存在。
但如果有现成的有序链表可用，那么
表插入排序对不太大的数组排序还是比较便利的。
双向链表：
双向链表允许向前遍历，也允许向后遍历整个链表。
双向链表的缺点是每次插入或删除一个链结点的时候，
要处理四个链结点的引用，而不是两个：
两个连接前一个链结点，两个连接后一个链结点。
当然，由于多了两个引用，链结点的占用空间也变大了一点。
迭代器：
人为创造类似于数组下标的链表结点下标。
为什么要这样做呢？
作为类的用户，需要能存取指向任意链结点的引用。
这样就可以考查和修改链结点。引用应该能递增，
因此，可以沿着整个链表遍历，依次查看每个链结点，
而且可以访问这个引用所指向的链结点。
因为无法确定用户需要多少数量的引用，所以，这里我们引出迭代器类
最初的定义：
class ListIterator(){
private Link current;
...
}
current字段包含迭代器当前指向的链结点的一个引用。
为了使用这样的迭代器，
用户可以创建一个链表，然后创建一个
和链表相关联的迭代器对象。
实际上，当链表产生时，让它创建迭代器更容易一些，
它能向迭代器传递必要的信息，例如它的first
字段的一个引用。因此，在链表类中增加一个
getIterator()方法。这个方法返回给用户一个恰当
的迭代器对象。
迭代器总是指向链表中的一些链结点。
它同链表相关联，但并不等同于链表或是链结点。
迭代器如果是一个单独类的对象，那么
它如何能访问first这样的私有字段呢？
一种解决方法是链表创建迭代器时，传递一个引用给迭代器。
这个引用存储在迭代器的一个字段中。
链表必须提供公有方法，允许迭代器改变first的值。
linklist类中的这些方法是
getFirst（）和setFirst（）方法
这种方式的缺点是这些方法允许任何人呢修改first，这就引入了危险的因素。
c++程序员会注意到在c++语言中，迭代器和链表之间的
连接是通过把迭代器类设为链表类的
“友元”来实现的。
然而，Java中没有友元的概念，友元在任何情况下都是
有争议的，因为它如同是数据隐藏这个盔甲上的裂缝。
迭代器的方法：
reset()---把迭代器设在表头
nextLink()---把迭代器移动到下一个链结点
getCurrent()---返回迭代器指向的链结点
atEnd()---如果迭代器到达表尾，返回true
insertAfter()---在迭代器后面插入一个新链结点
insertBefore()---在迭代器前面插入一个新链结点
deleteCurrent()---删除迭代器所指链结点
用户可以用reset()方法和nextLine（）方法来定位迭代器，
用atEnd()方法来检查是否它在表尾。
迭代器指向哪里？
最后一个，还是最后一个的下一个。
10.递归
递归方法的特征：
1.调用自身；
2.当他调用自身的时候，它这样做是为了解决更小的问题；
3.存在某个足够简单的问题的层次，
在这一层算法不需要调用自己就可以直接解答且返回结果。
递归方法的低效性：
1.函数调用的开销；
2.系统内存空间存储所有的中间参数以及返回值，
如果有大量的数据需要存储，这就会引起栈溢出的问题。
数学归纳法、阶乘、三角数
变位字，也就是字母的全排列
步骤：
1.全排列最右边的n-1个字母；
2.轮换所有n个字母；
3.重复以上步骤n次；
这里的轮换意味着所有的字母向左移一位，
但组左边的字母例外，它“转换”至最右边字母的后边。
归并排序：
效率是n*logn
归并排序的一个缺点是他需要在存储器中有另一个
大小等于被排序的数据项数目的数组，
如果初始数组几乎占满整个存储器，那么归并排序将不能工作。
但是，如果有足够的空间，归并排序会是一个很好的选择。
归并算法：
归并算法的中心是归并两个已经有序的数组。归并连个有序数组
A和B，就生成了第三个数组C，数组C包含数组A和数组B
的所有数据项，并且使他们有序的排列在数组C中。
merge（）方法有3个while循环。
第一个while循环是沿着
数组arrayA和数组arrayB走，比较他们的数据项，
并且复制他们中较小的数据项到数组arrayC中.
第二个while循环处理当数组arrayB的所有数据项都已经
溢出，而数组arrayA还有剩余数据项的情况。
这个循环吧剩余的数据项直接从数组arrayA中复制到ArrayC中。
第三个循环处理相似的情况，即当数组arrayA所有的数据项都已经
移出，而数组arrayB还有剩余数据项的情况：
将那些剩余的数据项复制到数组arrayC中。
归并排序的思想是把一个数组分成两半，排序每一半，
然后用merge（）方法把数组的两半归并成一个有序的属
数组。
当mergesort（）方法发现两个只有一个数据项的而数组时，
它就返回，把这两个数据项归并到一个有两个数据项的
有序数组中。每个生成的一对两个数据项的数组又被合并成一个有
4个数据项的有序数组。这个过程一直持续下去，数组越来越大直到整个数组有序。
public void mergeSort(){
long[] workSpace = new long[nElems];
recMergeSort(workSpace,0,nElems-1);
}
private void recMergeSort(long[] workSpace
,int lowerBound,int upperBound){
if(lowerBound == upperBound){
return;
}else{
int mid = (lowerBound+upperBound)/2;
recMergeSort(workSpace,lowerBound,mid);
recMergeSort(workSpace,mid+1,upperBound);
merge(workSpace,lowerBound,mid+1,upperBound);
}
}
private void merge(long[] workSpace
,int lowPtr,int highPtr,int upperBound){
int j=0;
int lowerBound = lowPtr;
int mid = highPtr-1;
int n = upperBound-lowerBound+1;
while(lowPtr <= mid && highPtr<= upperBound)
{
if(theArray[lowPtr] < theArray[highPtr] )
{
workSpace[j++] = theArray[lowPtr++];
}else{
workSpace[j++]=theArray[highPtr++];
}
}
while(lowPtr <= mid){
workSpace[j++]=theArray[highPtr++];
}
while(highPtr <= upperBound ){
workSpace[j++] = theArray[highPtr++];
}
for(j=0; j<n; j++ ){
theArray[lowerBound+j] = workSpace[j];
}
}
递归和栈：
递归和栈之间有一种紧密的联系。事实上，大部分的编译器
都是使用栈来实现递归的。
递归的应用：
1.求一个数的乘方；
2.背包问题；
3.组合；
假设把从5个人中选出3个人的组合简写为（5,3）。
规定n是这群人的大小，并且k是组队的大小。
那么根据法则可以这么说：
(n,k) = (n-1,k-1) + (n-1,k)
递归的方法可能效率低。如果是这样的话，
有时可以用一个简单循环或者是一个基于栈的方法来替代他。
11.高级排序
1.希尔排序
希尔排序是基于插入排序的。
下面是插入排序带来的问题：
假设一个很小的数据项在很靠近右端的位置上，
这里本来应该是值比较大的数据项所在的位置。
把这个小数据项移动到在左边正确位置上，所有的中间数据项
都必须向右移动一位。
这个步骤对每一个数据项都执行了将近n次的复制。
虽不是所有数据项都必须移动n个位置，但是数据项
平均移动了n/2个位置。
所以，如果能以某种方式不必一个一个地移动所有中间的数据项，就能把较小的数据项移动到左边，
那么这个算法的执行效率就会有很大的改进。
n-增量排序
希尔排序通过加大插入排序中元素之间的间隔，
并在这些有间隔的元素找那个进行插入排序，从而
使数据项能大跨度地移动。当这些数据项拍过一趟序后，
希尔排序算法减小数据项的间隔再进行排序，依次进行下去。
进行这些排序时数据项之间的间隔被称为增量，
并且习惯上用字母h来表示。
希尔排序中子数组相互交错排列，然而彼此独立。
数组实现“基本有序”，这正是希尔排序的奥秘所在。
通过创建这种交错的内部有序的数据项集合，把完成排序所必需的
工作量降到了最小。
正如之前讲的，插入排序对基本有序的数组进行排序是
非常有效的。
如果插入排序只需要把数据项移动一位或两位，那么
算法大概需要n的时间。
那么当这个间隔为1的时候，其实就是插入排序了。
所以我们应该生成一个间隔序列，这个
序列应该由大变小，最终变为1.
那么，序列如何生成呢？
使用Knuth序列进行希尔排序的情况：
在排序算法中，首先在一个短小的循环中使用序列
的生成公式来计算出最初的间隔。
h值最初被赋为1，然后应用公式：
h=3*h+1
生成序列：1,4,13,40,121,364等等。
当间隔大于数组大小的时候，这个过程就停止。
对于一个含有1000个数据项的数组，序列的
第七个数字，1093就太大了。
因此，使用序列的第六个数字作为最大的数字来开始
这个排序过程，
作364-增量排序。
然后没完成一次排序例程的外部循环，
用前面提供的此公式的到退市来减小间隔。
希尔排序比插入排序快很多，这是为什么呢？
当h值大的时候，数据项每一趟排序需要移动元素的个数
很少，但是数据项移动的距离很长。这是非常有效率的。
当h值减小时，每一趟排序需要移动的元素的个数增多，
但是此时数据项已经接近于他们排序后最终的位置，
也就是趋于有序状态。
这对于插入排序可以更有效率。
正是这两种情况的结合才使希尔排序的效率那么高。
注意后期的排序过程，也就是
h值减小的过程中不撤销前期排序，也就是
h值增大的过程中所作的工作。
例如：如果已经完成了以40-增量的排序的数组，
在经过13-增量的排序后仍然保持了
以40-增量的排序的结果。
如果不是这样的话，希尔排序就无法实现排序的目的。
class ArraySh{
private long[] theArray;
private int nElems;//number of data items
public ArraySh(int max){
theArray = new long[max];
nElems = 0;
}
public void insert(long value){
theArray[nElems] = value;
nElems++;
}
public void shellSort(){
int inner,outer;
long temp;
int h=1;
while(h<=nElems/3)
{
h = h*3 +1;
}
while( h>0 ){
for(outer =h; outer < nElems;outer++){
temp = theArray[outer];
inner = outer;
while(inner > h-1 && theArray[inner-h]>=temp )
{
theArray[inner] = theArray[inner-h];
inner -= h;
}
theArray[inner] = temp;
}
h = (h-1)/3;
}
}
}
希尔排序的效率是
n的3/2次方到n的7/6次方。
总之，大于n*logn
效率不如快速排序。
快速排序：
基本的递归的快速排序算法代码：
public void quickSort(){
recQuickSort(0,nElems-1);
}
public void recQuickSort(int left,int right){
if(right-left <= 0){
return;
}else{
long pivot = theArray[right];
int partition = partitionIt(left,right);
recQuickSort(left,partition-1);
recQuickSort(partition+1,right);
}
}
public int partitionIt(int left,int right,long pivot){
int leftPtr = left-1;
int rightPtr = right;
while(true){
while( theArray[++leftPtr] < pivot )
{
;//nop
}
while( rightPtr >0 && theArray[--rightPtr] >pivot )
{
;//nop
}
if(leftPtr >= rightPtr){
break;
}else{
swap(leftPtr,rightPtr);
}
}
swap(leftPtr,right);
return leftPtr;
}
上面的过程分为3个步骤：
1.把数组或者子数组划分成
左边较小的关键字的一组
和
右边较大的关键字的一组。
2.调用自身对左边的一组进行排序；
3.再次调用自身对右边的一组进行排序。
经过一次划分之后，所有在左边子数组的
的数据项都小于在右边子数组的数据项。
只要对左边子数组和右边子数组分别进行排序，
整个数组就是有序的了。
如何对子树组进行排序呢？
通过递归的调用排序算法自身就可以了。
划分之后的左边的子数组包含的所有数据项
<枢纽
<划分之后的右边的子数组包含的所有数据项。
选择最右端的数据项作为枢纽不属于完全随意地选择，但是这样消除了不必要的检测，
以此来加速代码的执行。
选择某个其他位置的数据项作为枢纽不能体现这个优势。
理想状态下，应该选择被排序的数据项的终止数据项
作为枢纽。
也就是说，应该有一半的数据项大于枢纽，
一半的数据项小于枢纽。
这会使数组被划分成两个大小相等的子数组。
对快速排序算法来说拥有两个大小相等的子数组是
最优的情况。如果快速排序算法必须要对划分的
一大一小两个子数组进行排序，那么将会降低
算法的效率，这是因为较大的子数组必须要划分更多三次。
n个数据项的数组的最坏的划分情况是一个子数组
只有一个数据项，但是另一个子数组含有n-1个数据项。
如果在每一趟划分中都出现这种情况，
那么每一个数据项都需要一次单独的划分步骤。
在逆序排列的数据项中实际上发生的就是这种情况；
快速排序最慢为n^2.
快速排序当以n^2运行的时候，除了慢还有
另外一个潜在的问题。
当划分的次数增加的时候，
递归方法的调用次数也增加了。
每一个方法调用都要增加所需递归工作栈的大小。
如果调用次数太多，递归工作栈可能会发生溢出，
从而是系统发生瘫痪。
所以，为了避免上面的情况。
我们有了三数据项取中法。
对子数组的左、右、中三个下标处的值进行比较
取出中间值作为枢纽继续下面的操作。
12.二叉树
为什么使用二叉树？
因为它通常结合了另外良好总数据结构的优点：
一种是有序数组，另一种是链表。
在树中查找数据项的速度和在有序数组中查找一样快，
并且插入数据项和删除数据项的速度也和链表一样。
Java语言编写的程序中常常用引用来表示边
（或者c/c++程序中可能会使用指针）
树的层数从0开始，从高处开始。
文件结构就是一个典型的树结构。
13.
14
20.应用场合
通用数据结构：数组，链表，树，哈希表
专用数据结构：栈，队列，优先级队列
排序：冒泡排序，选择排序，插入排序，希尔排序，归并排序，快速排序
图：邻接矩阵，邻接表
外部存储：顺序存储，索引文件，B-树，哈希方法
若想存储真实世界中的类似人事记录、存货目录、
合同表和销售业绩等数据，则只需要一般用途的
数据结构。
在这里数据这种结构的有数组、链表、树和哈希表。
他们被称为通用的数据结构是因为
他们通过关键字的值来存储并查找数据，
这一点在通用数据库程序中常见到。
速度与算法：
数组和链表是最慢的，树相对较快，哈希表是最快的。
但是这些最快的结构也有缺陷。
首先，他们的程序在不同程度上比数组和链表复杂；
其次，哈希表要求预先知道要存储多少数据，
数据对存储空间的利用率也不是非常高。
普通的二叉树对顺序的数据来说，会变成缓慢的n级操作。
而平衡树虽然避免了上述的额问题，
但是他的程序编制起来比较困难。
数组：
当存储和操作数据是，在大多数情况下数组是首先应该考虑的结构。
1.数据量较小；
2.数据量的大小事先可预测。
链表：
如果需要存储的数据量不能预知或者需要频繁地插入
删除数据元素时，考虑使用链表。
当有新的元素加入时，链表就开辟新的所需要的空间，
所以它甚至可以占满全部可用内存；
在删除过程中没有必要像数组那样填补“空洞”
二叉搜索树：
当确认数组和链表过慢时，二叉树是最先应该考虑的结构。
树可以提供快速的logn的插入、查找和删除。
遍历的时间复杂度为n级，这是任何数据结构比那里的最大值。
对于程序来说，不平衡的二叉树要比平衡二叉树
简单得多，
但不幸的是，有序数据能将他的性能降职n级，
不比一个链表好多少。然而如果可以保证数据是随机
进入的，就不需要用平衡二叉树。
平衡树
在众多的平衡树中，这里红黑树和2-3-4树，他们都是平衡树，
并且无论输入数据是否有序，他们都能保证性能为logn。
然而对于编程来说，这些平衡树都是很有挑战性的。
其中最难的就是红黑是。
他们也因用了附加存储而产生了额外耗费，这对系统或多或少有些
影响。
平衡树有许多种，
其中包括AVL树，splay树，2-3树等，
但是都不如红-黑树使用广泛。
哈希表：
哈希表在数据存储结构中速度最快。
哈希表通常用于拼写检查器和作为计算机语言编译器中的符号表，
在这些应用中，程序必须在几分之一秒的时间里检查上千的词或符号。
哈希表对数据的插入的顺序并不敏感，因此可以取代平衡树。
但是哈希表的编程却比平衡树简单多了。
哈希表需要有额外的存储空间，
尤其对于开放定址法。
因为哈希表用数组作为基本结构，所以，
必须预先精确地知道待存储的数据量。
用链地址法处理冲突的哈希表是最健壮的实现方法。
若能预先精确地知道数据量，
在这种情况下用开放定址法编程最简单，
因为不需要用到链表法。
哈希表并不能提供任何形式的有序遍历，
或对最大最小值元素进行存取。
如果这些功能重要的话，使用二叉搜索树更好。
21.外部存储
如果数据量大到内存容不下时，只能被存到外部存储孔家。
他们经常被称为磁盘文件。
存在磁盘文件中具有固定大小单元的数据被称为块，
每一个块都存储一定数量的记录。
磁盘文件中的记录拥有与主存中对象相同的数据类型。
与对象一样，每条记录都有一个关键字值，
通过他可以访问到这条记录。
同样，我们假设了读写操作总是在一个单一的块中进行，
这些读写操作比对主存中的数据进行任何操作都要耗时的多。
因此，为了提高操作速度必须将磁盘的存取次数
减到最小。
顺序存储：
通过特定的关键字进行搜索的最简单的方法是
随机记录然后顺序读取。
新的记录可以被简单地插入在文件的最后。
已删除的记录可以标记为已删除，或将记录
顺次移动，如同数组中来填补空缺。
就平均而言，查找和删除会涉及读取半数的块，
所以顺序存储并不很快，
时间复杂度为n。
但是对于小量的数据来说，他是令人满意的。
索引文件：
当使用索引文件时，速度会明显的提高。
在这种方法中关键字的索引和相应块的号数
被存放在内存中。
当通过一个特殊的关键字访问一条记录时，
程序会先向索引询问。索引提供这个关键字的
块号数，然后只需要读取这一个块，仅耗费1级时间。
可以使用多种关键字来做多种索引
名字做一个，社会安全号码做一个等等。
只要索引数量能在内存的存储范围之内，
这种方法表现很好。
通常，索引文件存储在磁盘上，只有在需要的时候才复制进内存中。
索引文件的缺点是必须先创建索引，
这有可能对磁盘上的文件进行顺序读取，
所以创建索引是很慢的。
同样，当记录被加入文件时，索引还需要更新。
B-树：
B-树是多叉树，通常用于外部存储，
树中的结点对应于磁盘中的块。同其他树一样，
通过算法来遍历树，在每一层上读取一个块。
B-树可以在logn级的时间内进行查找、插入和删除。
这是相当快的，并且他对很大的文件也很有效。
但是他的编程很繁琐。
哈希方法
如果可以占用一个文件通常大小两倍以上的外部存储空间的话，
外部哈希会是一个很好的选择。
他同索引文件一样有着相同的存取时间1，但它可以对更大的文件进行操作。
虚拟内存：
有时可以通过操作系统的虚拟内存的能力，
来解决磁盘存取问题，而不需要通过编程。
如果读取一个大小超过主存的文件，虚拟内存系统会读取合适主存大小的
部分并将其他存储在磁盘上。
当访问文件的不同部分时，他们会自动从磁盘读入
并放置于内存中。
可以对整个文件使用内部存储的算法，使他们好像同时都在内存中一样；
如果文件的那个部分不在内存中，也让操作系统去读取他们。
当然，这样的操作比整个文件在内存中的速度要
慢很多，但是通过外部存储算法一块一块地处理文件的话，
速度也是一样的慢。
不要在乎文件的大小适合放在内存中，在虚拟内存的帮助下验证算法工作的好坏是有益的，
尤其对于那些比可用的内存大不了多少的文件
来说，这更是一个简单的解决方案。
京公网安备 11010502036488号