#第一章 基础
标签(空格分隔): Algorithms学习笔记
主要讲述的是java作为一中变成语言的基本语法与概念
main()
中的 String args[]
参数来源是用户输入的命令行参数import java.util.Arrays;
public class BinarySearch{
//用于排序的算法代码
//输入一个目标值,一个待搜索数组;输出目标值在数组中的位置
public static int rank(int key, int[] a){
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
//用于运行程序的执行代码
public static void main(String args[]){
In in = new In(args[0]);//从一个文件中读取整数
int[] whitelist = in.readAllInts();//这里所谓的白名单,就是假定存在一种信息来源过滤
Arrays.sort(whitelist);//对输入的信息进行排序
// 从标准输入中读取整数值,如果不在白名单中,就打印出来
while (!StdIn.isEmpty()) {
int key = StdIn.readInt();//输入一个要搜索的整数
if (BinarySearch.indexOf(whitelist, key) == -1)//执行二分搜索算法,并返回结果
StdOut.println(key);
}
}
}
java中面向对象的一些概念
由可变数组、链表实现的bag、queue、stack
##(1)先导技术,可变数组的实现
//可以修改数组大小的resize方法,其实质就是重新创建一个数组,把已有的元素搬运过去(具体的使用条件需要其他代码来控制,这只是一个执行方法)
//输入一个数组,和一个新的长度,没有输出
private void resize(Item[] a, int newsize){//这里Item表示泛型
Item[] temp = (Item[]) new Object[newsize];
for(int i = 0; i<a.Length; i++){
temp[i] = a[i];
}
a = temp;//搬运完成之后,将数组a的应用,指向新创建的temp数组
}
##(2)链表
链表是由一堆节点按照他们所存储的特定的顺序信息组合而成的结构
对链表的数据的操作,就是对于这些节点中所存储的数据的操作;
对链表的结构的操作,就是对于这些节点中所存储的顺序信息的操作
private class Node{
Item item; //用于存储相应的信息
Node next;//用于指向下一个节点,形成链
}
污污污,小火车
从前,你有一堆小火车玩具。你得把每节车厢穿起来,拼成一辆列车,然后才能放在轨道上跑。可惜玩具的质量不太好,每节车厢都不可能是完全一样的。为了拼装出你心中最完美的列车,你开始记下这样的信息:左边有一道划痕的车厢,下面接的是右边少了个轮子的车厢。。。每次修改拼装的方案时,这样的信息也被修改,于是你终于发现,不同的拼装方案就与这每节车厢不同的链接顺序相对应。。。
for(Node x=first ; x!=null ; x=x.next){
//操作代码
}
后进先出,严格顺序
你见过“弹夹”吗?
public class Stack<Item>{
Stack()//一般会使用可变数组技术,或者是链表来实现可变容量的栈
//Stack(int size)
//定容量版本的构造方法
void push(Item item)//将下一个数据压入栈
Item pop();//弹出最近添加的元素
boolean isEmpty()//判断栈是否为空
int size()//输出栈的容量
}
public class FixedCapacityStack<Item>{
private Item[] a;
private int N;
//构造函数的作用是用来初始化各个成员变量,而非在构造方法中创建成员变量
public FixedCapacityStack(int cap){ a = (Item[]) new Object[cap]; }
public void push(Item item){ a[N++] = item; }
public Item pop(){ return a[--N]; }
public boolean isEmpty() { return N == 0; }
public int size() { return N; }
}
xbb:关于数组的计数变量
用数组来模拟后进先出的规律,可能不止应用于实现一个栈。关于计数变量 N,容易一厢情愿的按照 “有几个就是几” 的逻辑来,在实际实现的时候,千万要注意,数组为空的时候,计数指向 0,不管是 return size 还是作为扫描指针,对于计数变量,控制其起点,与 控制其规律同样重要。
此实现的策略保证数组不会溢出,且数组的使用率不会低于25%
import java.util.Iterator;
public class ResizingArrayStack<Item>{
private Item[] a = (Item[]) new Object[1]; //存储元素的数组
private int N = 0; //元素数量
private void resize(int max){
// Move stack to a new array of size max.
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i < N; i++){//不用遍历整个数组,因为只有前n个有值
temp[i] = a[i];
}
a = temp;
}
public void push(Item item){
if (N == a.length) resize(2*a.length);
a[N++] = item;
}
public Item pop()
Item item = a[--N];
a[N] = null; //防止对象游离
if (N > 0 && N == a.length/4) resize(a.length/2);
return item;
}
public boolean isEmpty() { return N == 0; }
public int size() { return N; }
}
public class Stack<Item>{
private class Node{
Item item;
Node next;
}
private Node first;//栈顶节点
private int N;
public void push(Item item){
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
N++;
}
public Item pop(){
Item item = first.item;
first = first.next;//每一个节点都是一个独立的对象,所以这里不用担心“对象游离”
N--;
return item;
}
public boolean isEmpty() { return first == null; } // Or: N == 0.
public int size() { return N; }
}
xbb:好钢用到刀刃上以链表实现栈为例,要说一个小事情。我们构造的链表节点是单向的,这意味着,对于其中一个方向的搜索是可行的,而另一个方向就呵呵了。当决定要用链表实现更高级的功能的时候,先想一下,**如果我只有一个方向可以追溯,那么对于我想做的事情来说,到底那个方向更重要呢?**你可以随意的码,反正不计好坏,基本都有实现的方法,但是 把数据结构的特性匹配到实际问题的特性中
将会是一个聪明的做法。
##(4)队列 / Queue
先进先出,严格顺序
用于按照先来后到的顺序进行操作的场合
public class Queue<Item> implements Iterable<Item>{
Queue()//构造方法
void enqueue(Item item)//将一个新的元素排列至队尾
Item dequeue()//从队列的开头拿走一个元素
boolean isEmpty()//判断队列是否为空
int size()//输出队列的容量
}
public class Queue<Item> implements Iterable<Item>{
private Node first; // link to least recently added node
private Node last; // link to most recently added node
private int N; // number of items on the queue
private class Node{
Item item;
Node next;
}
public boolean isEmpty() { return first == null; } // Or: N == 0.
public int size() { return N; }
public void enqueue(Item item){
Node oldlast = last;
last = new Node(); //last已经被声明为Node变量了,这里使用直接写 last = xxxx; 即可
last.item = item;
last.next = null; //这里对于新建的节点的next赋null是否是必须要写的代码?
if (isEmpty()) first = last; //为避免空指针一场而做的区别对待
else oldlast.next = last; //只有队列非空的情况下,所谓的oldLast才不是null
N++;
}
public Item dequeue(){
Item item = first.item;
first = first.next;
//dequeue时,一直在操作first,当队列被清空,first与last相遇的时候,也应该操作一下last
if (isEmpty()) last = null;
N--;
return item;
}
}
##(5)包 / Bag
只进不出,无序排列
用于收集特定的元素,然后迭代遍历收集到的元素
public class Bag<Item> implements Iterable<Item>{
Bag()//构造方法
void add(Item item)//添加一个新的元素
boolean isEmpty()//判断背包是否为空
int size()//输出包的容量
}
public class Bag<Item>{
private Node first; // first node in list
private class Node{
Item item;
Node next;
}
public void add(Item item){
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
}
}