8/29/2010

右键新建文本文档, doc文件

可能很多童鞋会问,"右键-新建-文本文档"  不就行了?

但我认为这种方式有两个缺点:

首先要打开两个菜单,右键和新建这两个,尤其是新建菜单,有时候会巨慢无比!

其次是新建文本文档没有快捷键,我在注册表里找了很久也没找出怎么设置.


功能介绍

我这个是加入到右键菜单的一级目录里,而且有快捷键(T)!  这样至少可以提升一倍的效率.

而且可以自定义文件名,不用先建后改;

建好文件之后会自动打开,如果文件已存在,会提示已存在并且也会自动打开,默认用记事本打开,不喜请自己DIY.

PS:Windows 7 肯定可用, XP未测试. 欢迎小白!


下载

猛击这里下载newTxt  &  newWord

里边有两个文件newTxt.reg,newTxt.bat;

使用方法:导入reg文件,并将newText.bat放入D盘根目录就可以了.

PS:可以隐藏,或者不喜欢放到D盘可以自己修改reg文件.


简单介绍

newTxt.reg是加入右键菜单的注册表文件,类似一个链接.

newTxt.bat才是真正的实现程序.

8/28/2010

Hashtable

简介

packagejava.util;

importjava.io.*;

publicclass Hashtable<K,V>

    extends Dictionary<K,V>

implements Map<K,V>, Cloneable,java.io.Serializable

Hashtable属于包java.util,实现中使用到了包java.io中的某些类。

它继承自Dictionary类,实现了Map接口,Cloneable接口,Serializable接口

Dictionary没有继承任何类(publicabstract class Dictionary<K,V>);

变量

privatetransient Entry[] table;

privatetransient int count;

privateint threshold;

privatefloat loadFactor;

privatetransient int modCount = 0;

privatestatic final long serialVersionUID = 1421746759512286392L;

table用于实际的存储key与value对.

默认值 & 构建方法

放在了构建方法里,没用声明静态常量;这一点就没有HashMap好。

由以下的构建方法可知,默认大小为11,装载因子为0.75;

和HashMap一样有四种构建方法;

    public Hashtable() {

       this(11, 0.75f);

}

    public Hashtable(int initialCapacity) {

       this(initialCapacity, 0.75f);

}

    public Hashtable(int initialCapacity, floatloadFactor) {

       if (initialCapacity < 0)

          throw new IllegalArgumentException("Illegal Capacity: "+

                                              initialCapacity);

        if (loadFactor <= 0 || Float.isNaN(loadFactor))

            throw newIllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)

            initialCapacity = 1;

       this.loadFactor = loadFactor;

       table = new Entry[initialCapacity];

       threshold = (int)(initialCapacity *loadFactor);

    }

    public Hashtable(Map<? extends K, ?extends V> t) {

       this(Math.max(2*t.size(), 11), 0.75f);

       putAll(t);

    }

同步 & 线程安全:

Hashtable里的很多方法都是synchronized的,所以它是线程安全的。

Hash值与索引的实现:

以put为例:

publicsynchronized V put(K key, V value) {

       // Make sure the value is not null

       if (value == null) {

          throw new NullPointerException();

       }

       // Makes sure the key is not already inthe hashtable.

       Entry tab[] = table;

       int hash = key.hashCode();

       int index = (hash & 0x7FFFFFFF) %tab.length;

       for (Entry<K,V> e = tab[index] ; e!= null ; e = e.next) {

          if ((e.hash == hash) && e.key.equals(key)) {

              V old = e.value;

              e.value = value;

              return old;

          }

       }

       modCount++;

       if (count >= threshold) {

          // Rehash the table if the threshold is exceeded

          rehash();

            tab = table;

            index = (hash & 0x7FFFFFFF) %tab.length;

       }

--------------------end-----------------------

       int hash = key.hashCode();

       int index = (hash & 0x7FFFFFFF) %tab.length;

hash值就是利用这两行代码来实现的,只是取了hash数的后31位并对数组长度求余.

比HashMap的实现还粗糙.

Hash冲突的处理:

和HashMap类似,利用一种拉链法的方式来处理,HashMap的实现原理:

“计算hash值=> 找hash值在table中对应的索引=> 判断该索引是否为null:

为null,直接添加;

不为null,判断hash值和key值是否相同(即使不同的hash值得到的索引i也可能相同),相同直接更新V,不相同则继续e = e.next();直到找到具有完全相同hash值和key值的e(Entry),或e == null;

如果最终e == null; 而且未找到完全相同的Entry,则运行addEntry(hash, key, value, i);

void addEntry(int hash, K key, V value,int bucketIndex) {

Entry<K,V> e =table[bucketIndex];

table[bucketIndex] = newEntry<K,V>(hash, key, value, e);

if (size++ >= threshold)

resize(2 * table.length);    //增长方式:*2;

}

利用一个单链的方式处理hash冲突:

假如本来table[i]为A,且A.next() == null;

这时候put方法获取了一个hash值与A的相同,但key值与A的不同的参数,则利用获得的两个参数key和value以及hash值与索引i值组合生成一个Entry B, 则将B放入table[i],将B.next 指向A;

同理,put了一个C,则将C放入table[i],C.next指向B;”

只是这里的实现略有不同,它并不是将添加新的Entry封装为一个方法,而是直接生成一个Entry对象,在put()代码中去实现添加。

Null值的处理:

Hashtable中不允许任何形式的null值!

Value为null时:

put()中的

       if (value == null) {

          throw new NullPointerException();

       }

Key为null时;

因为无论是在put()还是get()里;

都是没有进行判断key是否为null而直接使用

       int hash = key.hashCode();

所以当key为null时就会抛出异常:

 Exception in thread "main"java.lang.NullPointerException

所以说Hashtable不允许任何形式的null值。

增长方式:

方法为rehash(),该方法只会在put()方法中被直接调用到:

    protected void rehash() {

       int oldCapacity = table.length;

       Entry[] oldMap = table;

       int newCapacity = oldCapacity * 2 + 1;

       Entry[] newMap = new Entry[newCapacity];

       modCount++;

       threshold = (int)(newCapacity *loadFactor);

       table = newMap;

       for (int i = oldCapacity ; i-- > 0 ;){

          for (Entry<K,V> old = oldMap[i] ; old != null ; ) {

              Entry<K,V> e = old;

              old = old.next;

              int index = (e.hash &0x7FFFFFFF) % newCapacity;

              e.next = newMap[index];

              newMap[index] = e;

          }

       }

}

由这行代码:int newCapacity = oldCapacity * 2 + 1;

可知Hashtable的增长方式为 *2 + 1;

遍历方式:

遍历Entry, Set<Map.Entry<K,V>>;
  public Set<Map.Entry<K,V>>entrySet();

遍历value, Enumeration<V> || Collection<V>

  public synchronized Enumeration<V>elements();   //与HashMap不同

public Collection<V>values();

遍历key, Enumeration<K> || Set<K>;

  public synchronized Enumeration<K>keys();   //与HashMap的实现不同

  public Set<K> keySet();

造成Hashtable和HashMap有关遍历方法的共性与差异的原因在于:共性是由于它们都实现了Map接口;差异在于Hashtable继承自Dictionary类而HashMap没有。

对于这些方法的记忆也很简单:

首先记Map接口的方法,因为Map的特性决定了key值和Entry值不能重复,而value值可以重复。所以Map接口对于key和Entry都返回set型,即keySet()和entrySet(),而value则为Collection型,即values();

Dictionary没有考虑这么多,key值直接通过Enumeration形式的keys()获得,value值通过Enumeration形式的elements()获得。

OK~

8/26/2010

HashMap

简介

packagejava.util;

importjava.io.*;

HashMap属于包java.util,实现中使用到了包java.io中的某些类。

它继承自AbstractMap,实现了Map接口,Cloneable接口,Serializable接口

默认值

staticfinal int DEFAULT_INITIAL_CAPACITY = 16;

默认容量大小为16

staticfinal int MAXIMUM_CAPACITY = 1 << 30;

最大值为2的30次方

staticfinal float DEFAULT_LOAD_FACTOR = 0.75f;

默认装载因子为0.75

transientEntry[] table;

Entry的数组,即实际存储key和value对的容器。

staticclass Entry<K,V> implements Map.Entry<K,V>{}

Entry实现了Map里的Entry接口。

四种构建方法

publicHashMap(int initialCapacity, float loadFactor)

publicHashMap(int initialCapacity)

publicHashMap()

publicHashMap(Map<? extends K, ? extends V> m)

hash的实现:

 static int hash(int h) {

        // This function ensures that hashCodesthat differ only by

        // constant multiples at each bitposition have a bounded

        // number of collisions (approximately8 at default load factor).

        h ^= (h >>> 20) ^ (h>>> 12);

        return h ^ (h >>> 7) ^ (h>>> 4);

    }

只是二进制数本身的移位与异或运算。

索引的实现:

    static int indexFor(int h, int length) {

        return h & (length-1);

    }

注意这里,就决定了length最好是2的n次方。

获取key对应的value

publicV get(Object key) {

        if (key == null)

            return getForNullKey();

        int hash = hash(key.hashCode());

        for (Entry<K,V> e =table[indexFor(hash, table.length)];

             e != null;

             e = e.next) {

            Object k;

            if (e.hash == hash && ((k =e.key) == key || key.equals(k)))

                return e.value;

        }

        return null;

    }

-----------end---------------

if(key == null)    return getForNullKey();

这一句单独用于处理key为null的情况.这也是HashMap允许任何形式null值的原因所在.

如果key不为null,则获取key的hashCode,根据静态方法hash(int h)

h^= (h >>> 20) ^ (h >>> 12);

        return h ^ (h >>> 7) ^(h >>> 4);

求得对应的hash值,然后用求得的hash值去table里找到该hash值对应的索引.

table是一个Entry数组,对应的table[i]即是一个Entry对象(实现了Map.Entry),里边有K,V,hash值,和next.

如果没有预先put进去,会是一个null值,即返回null; 如果有,则判断该处的hash值与key值是否与get(key)里的key一致,如果不一致则e= e.next();直到找到一致的或者e == null;

null值的处理

get:

    private V getForNullKey() {

        for (Entry<K,V> e = table[0]; e!= null; e = e.next) {

            if (e.key == null)

                return e.value;

        }

        return null;

}

get时,当key为null执行此方法.即是索引的0位置.

put:

    private V putForNullKey(V value) {

        for (Entry<K,V> e = table[0]; e!= null; e = e.next) {

            if (e.key == null) {

                V oldValue = e.value;

                e.value = value;

                e.recordAccess(this);

                return oldValue;

            }

        }

        modCount++;

        addEntry(0, null, value, 0);

        return null;

    }

由for循环中的循环体可知,如果table[0]位置不为null则直接将V替换掉原来Entry中的V;

否则,则在table[0]直接增加一个Entry;

put的实现 & hash值冲突的处理

   public V put(K key, V value) {

       if (key == null)

           return putForNullKey(value);

       int hash = hash(key.hashCode());

       int i = indexFor(hash, table.length);

       for (Entry<K,V> e = table[i]; e != null; e = e.next) {

           Object k;

           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

                V oldValue = e.value;

                e.value = value;

                e.recordAccess(this);

                return oldValue;

           }

       }

       modCount++;

       addEntry(hash, key, value, i);

       return null;

}

如果key为null,则直接调用null值的put方法;

否则,计算hash值 => 找hash值在table中对应的索引=> 判断该索引是否为null =>

为null,直接添加;

不为null,判断hash值和key值是否相同(即使不同的hash值得到的索引i也可能相同),相同直接更新V,不相同则继续e = e.next();直到找到具有完全相同hash值和key值的e(Entry), 或e == null;

如果最终e == null; 而且未找到完全相同的Entry,则运行addEntry(hash, key,value, i);

   void addEntry(int hash, K key, V value, int bucketIndex) {

         Entry<K,V>e = table[bucketIndex];

       table[bucketIndex] = new Entry<K,V>(hash, key, value, e);

       if (size++ >= threshold)

           resize(2 * table.length);    //增长方式: *2;

    }

利用一个单链的方式处理hash冲突.

假如本来table[i]为A,且A.next() == null;

这时候put方法获取了一个hash值与A的相同,但key值与A的不同的参数,则利用获得的两个参数key和value以及hash值与索引i值组合生成一个Entry B, 则将B放入table[i],将B.next 指向A;

同理,put了一个C,则将C放入table[i],C.next指向B;

containsKey

   public boolean containsKey(Object key) {

       return getEntry(key) != null;

}

很猥琐吧,还是少用点;

containsValue

   public boolean containsValue(Object value) {

         if(value == null)

           return containsNullValue();

         Entry[]tab = table;

       for (int i = 0; i < tab.length ; i++)

           for (Entry e = tab[i] ; e != null ; e = e.next)

                if (value.equals(e.value))

                    return true;

         returnfalse;

}

    private boolean containsNullValue() {

         Entry[] tab = table;

        for (int i = 0; i < tab.length ;i++)

            for (Entry e = tab[i] ; e != null ;e = e.next)

                if (e.value == null)

                    return true;

         return false;

    }

更猥琐.

默认值与增长方式:

默认值为16,且即使指定初值,大小也只能是第一个比指定值大的2^n!

增长方式, 只有addEntry和putAll中直接会调用

   void resize(int newCapacity) {

       Entry[] oldTable = table;

       int oldCapacity = oldTable.length;

       if (oldCapacity == MAXIMUM_CAPACITY) {

           threshold = Integer.MAX_VALUE;

           return;

       }

       Entry[] newTable = new Entry[newCapacity];

       transfer(newTable);

       table = newTable;

       threshold = (int)(newCapacity * loadFactor);

    }

   /**

    * Transfers all entries from current table to newTable.

    */

   void transfer(Entry[] newTable) {

       Entry[] src = table;

       int newCapacity = newTable.length;

       for (int j = 0; j < src.length; j++) {

           Entry<K,V> e = src[j];

           if (e != null) {

                src[j] = null;

                do {

                    Entry<K,V> next =e.next;

                    int i = indexFor(e.hash,newCapacity);

                    e.next = newTable[i];

                    newTable[i] = e;

                    e = next;

                } while (e != null);

           }

       }

}

当扩容的时候要去遍历所有的Entry,所以事先指定容量是能节约很多时间的。

遍历方式:

详见:HashMap遍历的三种方法

遍历Entry,Set<Map.Entry<K,V>>;

  publicSet<Map.Entry<K,V>> entrySet();

遍历value,Collection<V>;

  publicCollection<V> values();

遍历key, Set<K>;  //与Hashtable不同

  publicSet<K> keySet();

其他的方法基本上都是基于这些方法的.

OK~

8/25/2010

HashMap遍历的三种方法

网上都是说有两种,其实严格来说应该是三种;
而且并不是哪种一定是好,哪一种一定是坏,适应当时的情况才是最好的。

代码如下:
Map map = new HashMap();
Iterator e;
//适用于既要遍历key又要遍历value的情况;
e = map.entrySet().iterator();
while(e.hasNext())
{
Map.Entry entry = (Map.Entry) e.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
//适用于只要遍历key的情况,用这种方法去获得value的效率极低;
e = map.keySet().iterator();
while(e.hasNext())
{
Object key = e.next();
Object val = map.get(key);
}
//适用于只要遍历value的情况;
e = map.values().iterator();
while(e.hasNext())
{
Object val = e.next();
}

8/24/2010

Hashtable 和 HashMap 的区别

1.        基础:Hashtable是继承了Dictionary;
      Hashmap是实现了Map接口;
2.        同步:Hashtable是线程同步的而Hashmap不是
3.        Null值问题:Hashtable不允许任何形式的null值,而Hashmap是允许的(包括key和value);
4.        遍历:它们对于Entry的遍历都是相同的;
entry的遍历:都可以通过entrySet()实现,返回Set<Map.Entry<K,V>>;
value的遍历:都可以通过values()实现,返回Collection<V>;
但Hashtable还可以通过elements()来获取Enumeration<V>形式的迭代器;
    public synchronizedEnumeration<V> elements();
key的遍历:俩都可以通过keySet()来获取Set<K>形式的key的集合;
但Hashtable可以通过keys()来获得Enumeration<K>形式的迭代器来直接遍历key.

总体来说,HashMap无论对于Entry,key还是value都不能直接获得相关的迭代器;
而Hashtable也只能通过Set来获取Entry的集合,但对于key和value,则既可以获取其collocation形式的集合,由可以直接获取其迭代器.
造成Hashtable和HashMap有关遍历方法的共性与差异的原因在于: 共性是由于它们都实现了Map接口; 差异在于Hashtable继承自Dictionary类而HashMap没有.
对于这些方法的记忆也很简单:
首先记Map接口的方法,因为Map的特性决定了key值和Entry值不能重复,而value值可以重复。所以Map接口对于key和Entry都返回set型,即keySet()和entrySet(),而value则为Collection型,即values();
Dictionary没有考虑这么多,key值直接通过Enumeration形式的keys()获得,value值通过Enumeration形式的elements()获得。
5.        默认大小:Hashtable是11;   Hashmap是16;
大小的增长方式:
Hashtable是old*2+1;
Hashmap是old*2
    而且它的大小一定是2的指数:
    利用哈希值去找索引的实现是:returnh & (length-1);
    这里length即表示大小,所以从这个角度去看必然要求大小是2的倍数;因为如果是2^n+1,length-1刚好是10000000,会造成大量的hash冲突。
    具体的实现代码也证实了这一点,因为在自动增长的过程中肯定是×2的,所以只有可能在初始化指定大小的时候造成不为2^n的情况:
       while (capacity < initialCapacity)
            capacity <<= 1;
    只要capacity小于初始大小,就向右移1位,即×2;所以HashMap的容量肯定是2的n次方。
6.        哈希值的实现不同
HashMap:
        int hash = hash(key.hashCode());
        int i = indexFor(hash,table.length);

static int hash(int h) {
        h ^= (h >>> 20) ^ (h>>> 12);
        return h ^ (h >>> 7) ^(h >>> 4);
    }
    static int indexFor(int h, int length){
        return h & (length-1);
    }

Hashtable:
         int hash = key.hashCode();
         int index = (hash &0x7FFFFFFF) % tab.length;

8/21/2010

Chrome/Chromium设为默认浏览器的时候加参数运行

适用情况: 喜欢把Chromium放在非系统盘.

我的Chromium的启动参数为: "D:Program FilesChromiumchrome.exe" --user-data-dir=DATA --enable-apps

但是有时候点开本地的htm文件或者点开别人发送的网址时会以不加参数的情况启动.

这时候只需要改三处注册表项即可:

[HKEY_CLASSES_ROOTChromiumHTMLshellopencommand]

[HKEY_CLASSES_ROOThttpshellopencommand]

[HKEY_CLASSES_ROOThttpsshellopencommand]

将这三项中的默认值都改为:

"D:Program FilesChromiumchrome.exe" --user-data-dir=DATA --enable-apps -- "%1"

即可, -- "%1" 必选, 因为它表示输入的网址; 其他的参数自己看着弄吧.


8/19/2010

【软件推荐】ALTRun

强烈推荐!

相信不少人都喜欢用 “开始 - 运行”吧, 今天要介绍的工具可以看做是对 “运行” 的增强版。

详细的介绍已经在善用佳软发布: 神逸之作:国产快速启动软件神品ALTRun

最新的下载:http://code.google.com/p/altrun/

今天我使用之后发现只能用一个字来形容这款软件:

8/18/2010

实习笔试——C语言(一)

周一的时候参加了一个C/C++的笔试,一共六道题,一道智力题,一道数据库题,六道程序题,这次先拿出程序题中的两道说下。
题目1:下面的代码输出什么结果?
     char *p ;
     strcpy( p, "Hello" );
     printf( "%sn", p );
     delete p;
     if( p != NULL )
         strcpy( p, "Ok" );
     printf( p );
这道题大概原本想考的是,当指针p被delete后的指向问题。但是,在复制字符串前,只声明了指针p,并没有初始化,即指针p没有指向任何一块内存,因此程序在运行阶段会报如下错误:Run-Time Check Failure #3 – The variable ‘p’ is being used without being initialized。
那么,排除掉这个未初始化的问题后,这道题接下来需要讨论的重点就是,指针被delete后的情形。(我原来以为delete是C中的关键字,结果delete是C++中的关键字,C中使用free()来释放内存)
以下是Bjarne Stroustrup’s C++ Style and Technique FAQ中的内容:
Why doesn't delete zero out its operand?
Consider
       delete p;
       // ...
       delete p;
If the ... part doesn't touch p then the second "delete p;" is a serious error that a C++ implementation cannot effectively protect itself against (without unusual precautions). Since deleting a zero pointer is harmless by definition, a simple solution would be for "delete p;" to do a "p=0;" after it has done whatever else is required. However, C++ doesn't guarantee that.
One reason is that the operand of delete need not be an lvalue. Consider:
       delete p+1;
       delete f(x);
Here, the implementation of delete does not have a pointer to which it can assign zero. These examples may be rare, but they do imply that it is not possible to guarantee that ``any pointer to a deleted object is 0.'' A simpler way of bypassing that ``rule'' is to have two pointers to an object:
       T* p = new T;
       T* q = p;
       delete p;
       delete q;  // ouch!
C++ explicitly allows an implementation of delete to zero out an lvalue operand, and I had hoped that implementations would do that, but that idea doesn't seem to have become popular with implementers.
If you consider zeroing out pointers important, consider using a destroy function:
       template<class T> inline void destroy(T*& p) { delete p; p = 0; }
Consider this yet-another reason to minimize explicit use of new and delete by relying on stadard library containers, handles, etc.
Note that passing the pointer as a reference (to allow the pointer to be zero'd out) has the added benefit of preventing destroy() from being called for an rvalue:
       int* f();
       int* p;
       // ...
       destroy(f());    // error: trying to pass an rvalue by non-const reference
       destroy(p+1);  // error: trying to pass an rvalue by non-const reference
在C++中delete指针前不用进行指针是否为空的判断,因为delete的实现已经做了这件事情!使用delete来delete已释放的指针是一个严重的错误,因此要在delete完一个指针后手动把它置空。因为delete空指针是安全的。
到此为止,C++的delete操作就基本清楚了,那么C中的free()操作呢,是否也和C++中的delete一样?把题目中的delete p改为free(p),然后重新运行,得出的结论是,它们两者的操作和注意事项是完全相同的。所以,以后用C的内存释放free()完一个指针后,也需要手动把它置空。
另外一个小的问题,对于字符串指针p,打印其指向的字符串可以这样写printf(p)。我原先认为这样的写法肯定不可以,结果实验证明是可以的,具体原因的话,大概要找C标准库看看了。这种打印方法仅限于字符串指针,如果用于其它类型指针则报错,用于字符串数组则会打印出垃圾数据。而且,当指针为空时,该方法也会报错;但如果使用printf(“%s”, p)打印的话,会打印出非常人性化的“(null)”出来。因此我个人觉得还是写成后一种方式比较好。
题目2:随机数算法。
这道题目不是太会,上网查了些资料,CVS如下:
1、线性同余算法:
      现在用得最广泛的伪随机数产生算法就是所谓的线性同余算法。其随机数序列{Xn}由方程:Xn+1 = ( aXn + c ) mod m得到,其中m>0称为模数,0≤ a <m称为乘数,0≤c <m称为增量,0≤X0<m称为初始值或种子,当m、a、c、X0都是整数时,通过这个方程就能产生一系列[0,m)范围内的整数了。
很明显,对一个线性同余随机产生算法来说,最重要的是m、a、c的选择。我们希望产生的序列足够长,能包含[0,m)内所有的数,并且产生的数是随机的,最好能用32bit算术高效实现。于是乎为了有足够的空间产生足够长的队列,我们会使m足够大;为了使序列足够完整,足够像随机序列,我们会发现当m是素数,c为0时就可以使序列的周期(即序列不重复的长度)对于一定的a达到m-1;要能用32bit算术高效实现,我们的m当然不能超过32bit,幸好刚好有一个满足上述条件的很方便的素数2^31-1给我们用,于是产生函数就变成了Xn+1 = ( aXn) mod ( 2^31 – 1 )。在超过20亿个a的可选取值中,只有很少的几个可以满足上述所有条件,其中之一就是a = 7^5 = 16807。于是我们可以实现如下:
unsigned myrand()
     {
         return (seed = (seed * 10807L) & 0x7fffffffL);
     }
这种产生器得到了广泛的使用和比其它产生器都彻底的测验,其产生的随机数有在分布上有很好的特性,但是却不具备良好的不可预测性。所以我们在使用时往往会以系统时钟(模m)或系统时钟与随机数的和(模m)作为种子来重新启动序列,这也是现在绝大多数随机数产生器的做法。
另一种产生伪随机数序列的方法就是使用加密逻辑,通过加密算法的雪崩效应,输入的每一位改变就会造成输出的巨大改变,并且假如密钥被妥善保存的话从序列中前面的数推出后面的数在计算上是不可行的,于是我们可以使用一个简单的累加器作为输入,得到的随机序列可以直接使用(当然也可以把系统时间等等因素考虑进去作为输入来产生更随机的序列,不过这通常是没有必要的),这种方法常常用来产生会话密钥或是现时。具体采用的加密逻辑和运算方式有很多,这里就不一一介绍了,大家感兴趣可以找本密码学的书来看看。
在密码学领域里比较流行的一种产生安全的伪随机数的方法是BBS产生器,它用其研制者的名字命名(Blum Blum Shub,不是我们经常灌水的那个BBS),它的密码编码强度据说具有最强的公开证明。首先,我们找两个大素数p和q,要求它们被4除都余3,令n = p×q,再选择一个随机数s,使s与n互素,然后我们通过如下算法产生一系列比特Bi:
X0 = (s^2)mod n,
for i = 1 to ∞
Xi = (Xi-1^2)mod n
Bi = Xi mod 2
每次迭代都只取出最低位的bit。可以看出BBS产生随机数的过程非常复杂,运算量很大,嗯,这就是为安全性付出的代价。
2、平方截取法:
找一个大数,如123456789
平方,得15241578750190521
取中段157875019
把它平方,得24924521624250361
取中段452162425
平方.......
这样能得一个伪随机序列
123456789
157875019
452162425 
3、C语言算法示例:
/*1.从同一个种子开始*/
#include <stdio.h>
#include <conio.h>
static unsigned long int next=1;
int rand0(void)
{
next=next*1103515245+12345;
return (unsigned int)(next/65536)%32768;
}
int main(void)
{
int count;
for(count=0;count<5;count++)
    printf("%hdn",rand0());
getch();
return 0;
}

/*2.重置种子*/
#include <stdio.h>
#include <conio.h>
static unsigned long int next=1;

int rand1(void)
{
next=next*1103515245+12345;
return (unsigned int)(next/65536)%32768;
}

void srand1(unsigned int seed)
{
next=seed;
}

int main(void)
{
int count;
unsigned int seed;
printf("please input seed:");
scanf("%u",&seed);
srand1(seed);
for(count=0;count<5;count++)
    printf("%hdn",rand1());
getch();
return 0;
}

/*3.利用利用时钟产生种子
ANSI C程序库提供了rand()函数来产生随机数;
ANSI C程序库提供了srand()函数来产生种子;
ANSI C程序库提供了time()函数返回系统时间。
*/
#include <time.h>
#include <stdio.h>
#include <dos.h>
#include <conio.h>
#include <stdlib.h>
int main(void)
{
   int i;
   time_t t;
   clrscr();
   t = time(NULL);
   srand((unsigned) t);
   for(i=0; i<10; i++) printf("%dn", rand()%10);
   getch();
   return 0;
}
随机数算法应该还有很多种,回头找些书看看再说。

PS: 本篇文章作者为chenhao727,由于技术原因造成作者显示错误,请您谅解,谢谢。

输出一个文件夹下的所有文件

以前就用java写过一个实现这种功能的类。
不过那个针对百万级别的数据就会耗费大量的时间进行初始化,因为那种实现的方式是一次将所有的子文件夹以及文件都载入到内存。
这次的思想是动态地进行载入,只有必要时才会去载入新的文件或文件夹。

现在这个版本只是个雏形,将最基础的功能进行了实现,以后会陆续加入文件个数统计,文件夹数目统计,文件类型过滤,以及中间结果储存目录树的构建等。

源代码如下,欢迎大家进行测试:


import java.io.File;
import java.util.ArrayList;
import java.util.Iterator;

class dir {
private int size;// 当前目录list的大小
private int index;// index

private String path;// 路径or文件名
private File file;
private dir[] dir;// 子文件or子目录
private String[] list;// 目录的list

dir(String s) {
// 保证path的末尾不带'';
if (s.lastIndexOf('\') == s.length() - 1)
s = s.substring(0, s.length() - 1);

this.path = s;
this.file = new File(this.path);
if (this.file.isDirectory()) {
this.list = this.file.list();
this.path = this.path + "\";
this.index = 0;
this.size = this.list.length;

if (this.size > 0) {
this.dir = new dir[this.size];
this.dir[index] = new dir(this.path + this.list[index]);
}
}
}

/*
* 是否还有文件
*/
public boolean hasNext() {
if (this.index < this.size) {
return true;
} else {
return false;
}
}

/*
* 下一个文件
*/
public String next() {
String result;
if (this.index >= size)
return null;
if (this.dir[index].isFile()) {
result = this.dir[index].toString();
this.push();
return result;
} else {
if (this.dir[index].hasNext()) {
result = this.dir[index].next();
if (result == null)
result = this.next();
return result;
} else {
if (this.push()) {
result = this.next();
if (result == null) {
result = this.next();
}
return result;
} else {
return null;
}
}
}
}

/*
* 对象自己是否是一个文件
*/
public boolean isFile() {
return this.file.isFile();
}

public String toString() {
return this.path;
}

/*
* 向前推进
*/
private boolean push() {
this.index++;
if (this.index < this.size) {
this.dir[this.index] = new dir(this.path + this.list[this.index]);
return true;
}
return false;
}
}

public class Test extends Exception
// implements FileOperation
{

public static void main(String[] args) {
final String PATH = "C:\123";
// final String PATH = "D:\My Documents";
// final String PATH =
// "D:\Program Files\eclipse\configuration\org.eclipse.ui.intro.universal";
// final String PATH = "D:\Program Files\eclipse";

long start = System.currentTimeMillis();
int i = 0;

dir d = new dir(PATH);
while (d.hasNext()) {
String temp = d.next();
if (temp != null) {
System.out.println(temp);
i++;
}
}

System.out.println("共" + i + "个文件!");

long end = System.currentTimeMillis();
System.out.println(end - start);
}
}

8/15/2010

读书笔记--C Programming FAQs(1)

最近在看一本写的比较有意思的C语言书,实际上是本关于C的问答录。书的英文原名叫做“C Programming FAQs”,中文译名译的很强势,叫做“你必须知道的495个C语言问题”,译名的最大亮点是“你必须知道”,呵呵。这本书源自于作者Steve Summit从1990年5月开始在comp.lang.c上发布的常见问题(FAQ)列表收集的一些并不显而易见的问题和提供的答案。
下面选个比较有意思的问答先看下。
问:为什么以前流行的那些C语言书总是使用void main()?
答:可能这本书的作者把自己也归为目标读者的一员。很多书不负责任地在例子中使用void main(),并宣称这样是正确的。但他们错了。或者他们假定每个人都在恰巧能工作的系统上编写代码。
-------------------------------------------------华丽丽的分割线------------------------------------------------
这个问答大概也可以从一个侧面反映出C语言的一些本质:告诉你规则,但不花费大量成本去检测你是否遵守了这个规则。类似的还有对数组和指针的越界操作不检测等等。
言归正传,到网上查了下不能使用void main()的原因,CVS如下:
When people ask why using a void is wrong, (since it seems to work), the answer is usually one of the following:
Because the standard says so. (To which the answer is usually of the form "but it works for me!")
Because the startup routines that call main could be assuming that the return value will be pushed onto the stack. If main() does not do this, then this could lead to stack corruption in the program's exit sequence, and cause it to crash. (To which the answer is usually of the form "but it works for me!")
Because you are likely to return a random value to the invokation environment. This is bad, because if someone wants to check whether your program failed, or to call your program from a makefile, then they won't be able to guarantee that a non-zero return code implies failure. (To which the answer is usually of the form "that's their problem").
这段英文比较容易理解,就懒得翻译了。
下面介绍一个比较纠结的问题。
问:我遇到这样声明结构的代码:
       Struct name {
              int namelen;
              char namestr[1];
       };
然后又使用一些内存分配技巧使namestr数组用起来好像有多个元素,namelen记录了元素个数,它是怎样工作的?这样是合法的和可移植的吗?
答:不清楚这样做是否合法或可移植,但这种技术十分普遍。
……
C99引入了“灵活数组域概念”,允许结构的最后一个域省略数组大小。这为类似问题提供了一个定义明确的解决方案。
-------------------------------------------------华丽丽的分割线------------------------------------------------
首先,说明下“灵活数组域”的相关内容。它允许结构的最后一个数组变量的长度是可变的,即对这样的结构使用malloc分配内存的时候,程序员可以根据需要,对灵活数组域的数组分配任意长度的空间。
但是这个灵活数组域必须满足下面两个条件:
1、  结构体中必须有一个数组成员并且这个灵活数组成员必须放在最后一个成员的位置;
2、  包含有灵活数组成员的结构体不允许嵌套在其它的结构体或者数组中。
然后,针对问题中的结构声明,我们还可以给出另外一种声明:
       struct name {
              int namelen;
              char *namestr;
       };
书中提到“真正安全的正确做法是使用字符指针,而不是数组”,即上面的这种声明。使用字符指针的结构声明时,计算结构体大小的结果,即sizeof(name),是不包括灵活数组域成员的大小的。下面这段代码是对问题中结构的一个内存分配和赋值操作。
……
char *str = “qisinidewenrou”;
struct name *nm = (*name)malloc(sizeof(struct name) + strlen(str) + 1);
nm->namelen = strlen(str);
strcpy(nm->namestr, str);
……
从上面代码可以看出,灵活数组域的一个优点是不用两次分配和释放内存,一次搞定。但是,书中还提到了一个注意事项,“像这样一次malloc调用将第二个区域接上的技巧只有在第二个区域是char型数组的时候可移植。对于任何大一些的类型,对齐变得十分重要,必须保持”。因此有下面实验:
struct test {
              char i;
              double *d;
};
……
       tt = ( struct test * )malloc( sizeof( struct test ) + sizeof( double ) * 5 );
       if( tt != NULL ) {
              tt->i = 'i';
              tt->d[0] = 1.1;
       }
在实验中,编译通过,运行直到最后赋值语句是才报错:“该内存不能为written”。原因应该是结构中的成员在内存中没有对齐,导致了越界写等问题。
但是,在网上查阅资料时,看到有些结构声明如下:
struct test {
              char i;
              double d[];
};
在这种结构声明下,上述的实验代码可以正常赋值,也能正常读取,即书中的注意事项在这种结构声明下是无用的。分析其原因,是由于这种结构声明给予编译器足够的信息,在内存分配的时候实现了对齐,因此能够正常的读写。
不知道这个问题是否于编译器有关,我的编译器是VS2008。
PS:好久没有写文章,写一篇感觉蛮费劲的。文中肯定有很多不通顺导致不好理解的地方,先凑合看吧,以后有时间回头看的时候再改好了。

PS: 本篇文章作者为chenhao727,由于技术原因造成作者显示错误,请您谅解,谢谢。

chenhao727

New name, new life~
July 27, 2010 is a special day in my life~
^_^

红黑树

一颗二叉查找树如果满足下面的红黑性质,则为一颗红黑树:

1)      每个结点或是红的,或是黑的.

2)      根结点是黑的.

3)      每个叶结点(NIL)是黑的. (孩子结点指向null的结点重定向到NIL)

4)      如果一个结点是红的,则它的两个儿子都是黑的.

5)      对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点.

由这个定义可知, 红黑树并不是平衡二叉树, 它只是一种近似平衡的二叉搜索树.

我们知道, 在动态构建二叉树的过程中, 一定要避免出现单支树的情况; 因为在那种急坏的情况下, 查找结点的时间复杂度会大大升高. 所以才引出了平衡二叉树, 但是广泛采用的构建平衡二叉树的两种方法各有各的缺点.

一种是利用一个平衡因子的方法: 平衡因子(Balance Factor,BF)定义为该节点的左子树的深度减去其右子树的深度, 则平衡二叉树上所有节点的平衡因子只可能是-1、0和1. 只要树上有一个节点的平衡因子的绝对值大于1, 则该二叉树就是不平衡的了. 利用平衡因子可以快速准确地判断二叉树的平衡状况, 但缺点在于每次插入新结点都要迭代地去更新父结点的平衡因子, 知道根节点.

另一种是利用一个标志位去存储当前的层数: 虽然这种方法操作起来方便, 但是在旋转时需要更新旋转结点的所有子树的标志位, 而且会占用大量的空间去存储这些信息.

所以, 第一种方法需要向上迭代到根, 第二种方法需要向下迭代到叶子. 在较坏情况下的效果都不会好.

而红黑树则没有这些缺点, 它在最坏的情况下也是只需要改变有限的几个结点的颜色.

下面看看红黑树的具体实现:

插入结点:

针对插入新结点, 如果它的父节点是黑色, 这时候不会违背五条性质中的任何一条.

当然, 我们关心的是那种它的父节点是红色的情况, 因为这时候它违背了性质4. 所以必须对树的结构进行一定的调整使其继续满足红黑树的五个性质.

因为要考虑新插入结点的父亲是左孩子还是右孩子, 这些结构在拓扑上是完全对称的, 所以我们只考虑它父亲是左孩子的情况.

需要改变树的结果, 有3×2 = 6种情况:

Case1:

           B

          / 

         R    R

        /   /  

      new

新插入的结点是红的, 它父亲是红的, 它父亲的兄弟也是红的.

违背了性质4, 这时候需要进行一个调整, 使其在满足性质4的情况下而不违背性质5.

染色: 父亲与叔父染成黑的, 爷爷染成红色;

这样从它爷爷的角度去看满足了性质4, 但不能保证整个树满足性质4 (因为爷爷的父亲可能是红色); 但从整棵树的角度去看肯定是满足性质5的, 因为没有在一个分支上加入多余的黑结点.

迭代: 为了保障整棵树的角度满足性质4, 需要将新插入结点的爷爷当作新插入的结点去考虑.

Case2 & Case3:

共同的前提: 新插入的结点是红的, 它父亲是红的, 但它父亲的兄弟是黑的.

我的推论: 这时候它父亲的兄弟是NIL, 即它的爷爷只有它父亲一个孩子. 因为它爷爷有两个孩子, 但左孩子是红色, 而右孩子不是红色, 这必然会违背性质5. 即在插入前, 从它的爷爷出发到它的父亲的叶子节点之间的路径上是没有黑色结点的, 而从它爷爷向着爷爷的右孩子出发到叶子节点之间至少有一个黑色结点. 所以违背了性质5.

Case2:新插入的结点是左孩子.

           B

          / 

         R    B

        /   

      new

Case3:新插入的结点是右孩子.

           B

          / 

         R    B

        /   

          new

对于Case3:对新插入结点的父亲进行左旋,进而转换为Case2.

Case2:违背了性质4,但不违背性质5.

这就要求进行一种旋转保障不违背性质5的前提下修正违背的性质4.

染色: 父亲染为黑的,爷爷染为红的.

旋转: 右旋爷爷.

           B                R               B

          /               /              / 

         R   NIL >   B   NIL >      new  R

        /             /                    / 

    new         new                         NIL

之后即满足了所有的5个性质.

删除结点:

如果被删除的结点是红色的,则当结点被删除后,红黑性质仍然得以保持,理由如下:

a)树中各结点的黑高度都没有变化.

b)不存在两个相邻的红色结点.

c)因为如果该节点是红的,就不可能是根,所以跟仍然是黑色的.

如果被删除的结点是黑色的, 则会产生三个问题

    要删除的结点y,如果y有个不是NIL的孩子,则x为y的唯一孩子;如果y没有孩子,则x为NIL,把x的父节点(原来是y)赋值为y的父节点

①如果y原来是根结点,而y的一个红色的孩子成为了新的根,这就违反了性质2)。

②如果x和p[y](现在也是p[x])都是红的,就违反了性质4)。

③删除y将导致先前包含y的任何路径上黑结点个数少1。因此,性质5)被y的一个祖先破坏了。补救这个问题的一个办法就是把结点x视为还有额外的一重黑色。也就是说,如果将任意包含结点x的路径上黑结点的个数加1,则这种假设下,性质5)成立。当将黑节点y删除时,将其黑色“下推”至其子节点。现在问题就变为结点x可能既不是红,也不是黑,从而违反了性质1)。结点x是双重黑色或红黑,这就分别给包含x的路径上黑结点的贡献2个或1个。x的color属性仍然是red(如果x是红黑的)或者black(如果x是双重黑色)。换言之,一个结点额外的黑色反映在x指向它,而不是他的color属性。

四种情况

Case1:x的兄弟w是红的.

Case2:x的兄弟w是黑的,而且w的两个孩子都是黑的.

Case3:x的兄弟w是黑的,w的左孩子是红色的,右孩子是黑色的.

Case4:x的兄弟w是黑的,而且w的右孩子是红色的.

情况1:x的兄弟w是红色的

因为w必须有黑色的孩子,我们可以改变w和p[x]颜色,再对p[x]做一次左旋,从而红黑性质得以继续保持。现在,x的新兄弟是旋转之前w的某个孩子,其颜色为黑色。这样,我们已经将情况1)转化为情况2), 3)或4)了.

情况2:x的兄弟w是黑色的,而且w的两个孩子都是黑色的

因为w也是黑色的,故从x和w上去掉一重黑色,从而x只有一重黑色而w为红色。为了补偿从x和w中去掉一重黑色,我们想在原来是红色或者黑色的p[x]内新增一重额外的黑色。通过以p[x]为新结点x来恢复while循环。注意如果从情况1进入情况2,则新结点x是红黑色的,因为原来的p[x]是红色的。因此,新结点x的color属性的值c为red,并且在测试循环条件后循环结束。然后新结点x在第23行中被(单独)着为黑色。

情况3:x的兄弟w是黑色的,w的左孩子是红色的,右孩子是黑色的

可以交换w和其左孩子left[w]的颜色,并对w进行右旋,而红黑性质仍然保持。现在x的新兄弟w是一个有红色右孩子的黑节点,这样我们从情况3转换成情况4

情况4:x的兄弟w是黑色的,而且w的右孩子是红色的

通过做某些颜色修改并对p[x]做一次左旋,可以去掉x的额外黑色来把它变成单独黑色,而不破坏红黑性质。将x置为根后,当while循环测试其循环条件时循环结束。

本文参考了:

《算法导论》

《算法导论》笔记--红黑树(一) http://liyiwen.javaeye.com/blog/345800

《算法导论》笔记--红黑树(二) http://liyiwen.javaeye.com/blog/345799

抄袭了:

算法导论 红黑树 http://www.886s.com/blog/?p=30

8/14/2010

xcv58

网名:xcv58
Google+ twitterGoogle Reader, 腾讯微博
Email: chenyihonglove@gmail.com

iReader, 超赞的阅读器插件 - chrome插件推荐

如果你在找类似safari 5的阅读器,不要犹豫,果断的去下载吧!

地址: https://chrome.google.com/extensions/detail/ppelffpjgkifjfgnbaaldcehkpajlmbc

可能有人并不知道safari 5的阅读器功能。

但这些情况你肯定遇到过:看新闻或者博客时字体太小! 广告太多! 阅读效率低下!

有了这个插件就不用愁了,它可以把你想看的内容提取出来显示。

相当大的字体,没有广告,自动翻页,阅读新闻/博客必备。

以前没有这个插件的时候我都是专门装个safari 5来看新闻。


附:改变阅读习惯的Safari 5阅读器!http://imtx.cn/archives/1502.html


8/12/2010

实习笔试&面试——JAVA篇(一)

11号去参加了一个JAVA的实习笔试,现把当时有些疑虑的题目和回来后验证得到的答案记录于此,以备后查。
题目1:下列哪些标示符是合法的?
A.$xxx B.TwoUser C.*this D.super
解答:A选项是合法的。毅鸿对“~!@#$%^&*()”作为开头的标示符均进行了验证,发现其中只有“$”开头的标示符是合法的。B选项也是合法的。
题目2:下列哪些数组声明可以声明一个包含10个String的数组?
A.char[] B.char[][] C.String[] D.String[10]
解答:正确选项应该是B和C。当时犹豫不决的是D选项,实际上D选项这种数组声明方式是不正确的。
题目3:现有未赋初值的静态整形数组static int a[] = new int[10],问a[1]有没有初值?如果有,是多少?
静态整形数组中的每一个整形变量都有默认初值,其值为零,因此a[1]=0。
题目4:const是否为JAVA中的关键字?
解答:否。const是JAVA中的预留字,不是关键字。
题目5:JAVA中的关键字transient的作用是什么?
解答:JAVA的serialization提供了一种持久化对象实例的机制。当持久化对象时,可能有一个特殊的对象数据成员,我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization,可以在这个域前加上关键字transient。
题目6:现有char a[] = {‘a’,‘b’,‘c’,‘d’,‘e’}, String b = “abcde”, String c = “abcde”;则以下等式为真的有哪些?
A.a.equals(b) B.b.equals(c) C.a==b D.b==c
解答:选项B和D是正确的。这里就不多讲原因了,后头好好看看类String的equal方法。
题目7:在继承中,父类中的变量,子类可以访问的到么?
解答:答案是肯定的。当然,得保证父类中变量是public。
题目8:文件操作中的类FileInputStream,FilterInputStream的构造函数中包含的参数分别为什么?
解答:FileInputStream(File file) ,通过打开一个到实际文件的连接来创建一个 FileInputStream,该文件通过文件系统中的 File 对象 file 指定。
FileInputStream(String name) ,通过打开一个到实际文件的连接来创建一个 FileInputStream,该文件通过文件系统中的路径名 name 指定。
FilterInputStream(InputStream in) ,将参数 in 分配给字段 this.in,以便记住它供以后使用,通过这种方式创建一个 FilterInputStream。
以上内容均摘录于JAVA API。
今天晚上好困,先写成这样吧,以后有时间的话再做修改。

PS: 本篇文章作者为chenhao727,由于技术原因造成作者显示错误,请您谅解,谢谢。

在一天的24小时之中,时钟的时针、分针和秒针完全重合在一起的时候有几次?

在一天的24小时之中,时钟的时针、分针和秒针完全重合在一起的时候有几次?
我们做几个假设:
1.一个时钟有60个刻度;
2.秒针从0移动到60,分针移动一个刻度;
3.分针从0开始每移动12个刻度,时针则移动1个刻度.
结果是24个重合的时刻.
以下是java代码:

public static void main(String args[]) {
		final int n = 3600 * 24;
		int i1 = 0, i2 = 0, i3 = 0;
		// 分别代表时针,分针,和秒针指向的刻度.
		int x = 0;
		int sum = 0;
		for (int i = 0; i < n; i++) {
			i3 = i % 60;
			// 秒针指向的刻度
			i2 = (i / 60) % 60;
			// 走过的分钟数除60的余数.
			i1 = (i / 3600) * 5 + i2 / 12;
			// 小时数*5+分钟数/12
			if (((i1 < 60 ? i1 : i1 % 60) == i2) && (i2 == i3)) {
				System.out.println(
						String.format("%02d", (i1 / 5)) + ":"
						+ String.format("%02d", i2) + ":"
						+ String.format("%02d", i3) + ", "
						+ String.format("%05d", i) + ", "
						+ String.format("%04d", (i - x)));
				x = i;
				sum++;
			}
		}
		System.out.println(sum);
	}

结果:

00:00:00, 00000, 0000
01:05:05, 03905, 3905
02:10:10, 07810, 3905
03:16:16, 11776, 3966
04:21:21, 15681, 3905
05:27:27, 19647, 3966
06:32:32, 23552, 3905
07:38:38, 27518, 3966
08:43:43, 31423, 3905
09:49:49, 35389, 3966
10:54:54, 39294, 3905
11:59:59, 43199, 3905
12:00:00, 43200, 0001
13:05:05, 47105, 3905
14:10:10, 51010, 3905
15:16:16, 54976, 3966
16:21:21, 58881, 3905
17:27:27, 62847, 3966
18:32:32, 66752, 3905
19:38:38, 70718, 3966
20:43:43, 74623, 3905
21:49:49, 78589, 3966
22:54:54, 82494, 3905
23:59:59, 86399, 3905
24