设计散列表主要是对哈希函数和处理冲突碰撞的选择和设计，好的哈希函数h可以使关键字比较均匀的散列在哈希表中，冲突较少。所谓“好”的哈希函数的主导思想，是使h尽可能地随机，减少碰撞，但是不可能完全避免碰撞，因为关键字域的势 |U|>m，m为散列表的槽数，总会有两个不同的关键字映射到同一个槽中，产生碰撞。

1、哈希函数

一个好的哈希函数应（近似地）满足简单一致散列的假设：每个关键字都等可能的散列到m个槽位的任何一个中去，并与其他的关键字已被散列到哪个槽位中无关。

不幸的是，一般情况下不太可能检查这一条件是否成立，因为人们很少能知道关键字所符合的概率分布，而各关键字可能并不是完全相互独立的。

算法导论中列举了四种哈希函数：直接定址法、除法散列法、乘法散列法和全域散列法。

其中除法散列法和乘法散列法利用了启发式的方法，第三个利用了随机化的技术。

a、除法散列法（模除法）

h(k)=k mod m

m的取值常常是与2的整数幂不太接近的质数（m是指散列表的槽数）。

b、乘法散列法

h(k)=|m*(k*A mod 1)| （取底）

用关键字k乘以常数A（0<A<1），并取出kA的小数部分。然后用m乘以这个值，对结果取底。

对 m 的选择没有特别的要求，一般选择为 2 的整数次幂

Knuth认为 A=（sqrt（5）-1）=0.6180339887......，取这个值比较理想

c、全域散列

h(k)=((a*k+b) mod p) mod m   （哈希函数族）

选择一个足够大的质数p，使得每一个可能的关键字k都落到0到p-1之间（包括0和p-1）。

Zp表示集合｛0，1，……，p-1｝，Zp*表示集合｛1，2，……，p-1｝。

容易知道p>m（p>=|U|>m）

a属于Zp*，B属于Zp

从函数族中随机的选取一个作为哈希函数

d、在严蔚敏的数据结构中还介绍了其他的构造哈希函数的方法（比如平方取中法，折叠法等）

2、处理碰撞的方法

a、哈希链接法

把冲突的关键字存储在冲突槽的链表中

在简单一致散列的假设下，一次不成功查找的期望时间为O（1+α），平均情况下一次成功的查找也需要同样的时间

b、开放寻址法

线性探测    h(k,i)=(h'(k)+i) mod m,i=0,1,……，m-1

二次探测   h(k,i)=(h'(k)+c1*i+c2*i*i) mod m     严蔚敏的数据结构中 c1=0，c2=-1

双重哈希（再哈希法） h(k,i)=(h1(k)+i*h2(k)) mod m

每一个关键字的探查序列

<h(k,0)，h（k,1）,……，h(k,m-1)>    

直到探寻到合适的位置为止

c、完全散列法

基本思想比较简单，采用两级的散列方案，每一级都采用全域散列。

有点类似哈希链接法，只不过，在冲突槽的链表上再采用一次全域哈希。

d、严蔚敏的数据结构中还介绍了 建立一个公共溢出区 的方法

------------------------------------一个小例子（哈希链接法 处理冲突）-------------------------------------------------

/*
* 算法导论 第十一章 散列表
*
* 哈希函数：模除散列法
* 冲突避免：哈希链接法
* */

/* 输出：14 1

               1   0

*/

#include<stdio.h>
#include<stdlib.h>

struct hash_node{
struct hash_node *next;
int data;
};

struct hash_table{
struct hash_node *base;
unsigned int count;
unsigned int size;
};

unsigned int hash1(int key, int m)
{
/*int rt=-1;*/
return key%m;
}

unsigned int hash2(int key, int m)
{
return 1+(key%(m-1));
}

unsigned int hash(int key, int m, int i)
{
return (hash1(key,m)+i*hash2(key,m))%m;
}

void chain_insert(struct hash_table *tbl, int key)
{
unsigned int pos=-1;
struct hash_node *new_node=NULL;

new_node=(struct hash_node *)malloc(sizeof(struct hash_node));
new_node->data=key;
new_node->next=NULL;

pos=hash(key,tbl->size,0);

if(tbl[pos].count==0)
{
   tbl[pos].base=new_node;
   tbl[pos].count += 1;
}
else
{
   new_node->next=tbl[pos].base;
   tbl[pos].base=new_node;
   tbl[pos].count += 1;
}
}

void chain_search(struct hash_table *tbl, int key, unsigned int *row,unsigned int *col)
{
int i=0;
int idx=-1;
struct hash_table tb;

idx=hash(key,tbl->size,0);

if(tbl[idx].count > 0)
{
   tb=tbl[idx];
   while(tb.base!=NULL && tb.base->data!=key)
   {
    tb.base=tb.base->next;
    i += 1;
   }
  
   *row=idx;
   *col=i;
  
   if(tb.base==NULL)
   {
    *row=-1;
    *col=-1;
   }
}
else
{
   *row=-1;
   *col=-1;
}
}

#define m 13

int main()
{
int i=0;
int row, col;
struct hash_table tbl[m];

for(i=0;i<m;i++)
{
   tbl[i].base=NULL;
   tbl[i].count=0;
   tbl[i].size=m;
}
chain_insert(tbl,1);
chain_insert(tbl,14);
chain_search(tbl,14,&row,&col);

printf("%d ",tbl[1].base->data);
printf("%d ",tbl[1].base->next->data);
printf("\n%d %d\n",row,col);

return 0;
}

----------------------------------------------------------------------------------------------------------------------------

linux kernel 结束第一遍

练习使用matlab

算法导论 至少读2章

expert 至少看完第五章

对所有认识的人微笑，打招呼

对所有不认识但是眼神碰撞的人微笑

然后进行了一些修改，随机的选择中轴元素，随机化处理了一下。

对两个算法进行比较，随机产生553k的数据进行排序，分别统计花费的时间。

一开始在windows下，直接 cl 进行编译链接，可执行文件112k，输出分别是 31ms和110ms。

后来偶然使用VC6编译，运行，可执行文件544k，大了432k，输出为94ms和171ms，分别慢了3倍和60+ms。

VS到底做了什么使得效率低了下来？？！！

另外还有一个发现，在数据比较多，随机化处理过的快排算法要比没有处理的快排效率要差很大。印象中好像是应该反过来，期望运行时间应该要优于后者，因为快排的最好的情况下才是O(n*lgn)，而随机化处理过之后期望运行时间是O(n*lgn)。

或者是因为多了随机化操作、数据交换操作和过程调用时间消耗而引起的？

---------------------------------------------------------code--------------------------------------------------------------------

#include<iostream>
#include<cassert>
#include<ctime>
#include<cstdlib>
using namespace std;

void quickSort(int arr[],int p,int r);
int Partition(int arr[],int p,int r);

void random_QuickSort(int arr[],int p,int r);
int random_Partition(int arr[],int p,int r);

inline void swap(int &a,int &b);
void writeFile(string file_name);
void readFile(string file_name,int arr[],int size);
void writeToFile(string file_name,int arr[],int size);

int main()
{
/*int i=-1;
int size=-1;
int *arr=NULL;

cin>>size;
arr=new int[size];

for(i=0;i<size;i++)
{
   cin>>arr[i];
}
quickSort(arr,0,size-1);
for(i=0;i<size;i++)
   cout<<arr[i]<<" ";

delete []arr;*/
const int size=100000;
int arr[size];
int arr2[size];

string in_file="dataIn.txt";
string out_file="dataOut.txt";
string out2_file="dataOut2.txt";

writeFile(in_file);
readFile(in_file,arr,size);
readFile(in_file,arr2,size);

clock_t start=clock();
quickSort(arr,0,size-1);
clock_t end=clock();
double diff=(double)(end-start);
cout<<diff<<endl;

clock_t start2=clock();
// insert_sort_rec(arr2,size-1);
random_QuickSort(arr2,0,size-1);
clock_t end2=clock();
double diff2=(double)(end2-start2);
cout<<diff2<<endl;

writeToFile(out_file,arr,size);
writeToFile(out2_file,arr2,size);
return 0;
}

void quickSort(int arr[],int p,int r)
{
if(p<r)
{
   int q=Partition(arr,p,r);

   quickSort(arr,p,q-1);
   quickSort(arr,q+1,r);
}
}

void random_QuickSort(int arr[],int p,int r)
{
if(p<r)
{
   int q=random_Partition(arr,p,r);
   random_QuickSort(arr,p,q-1);
   random_QuickSort(arr,q+1,r);
}
}

int Partition(int arr[],int p,int r)
{
int key=arr[r];
int i=p-1;
int j=p;

for(j=p;j<r;j++)
{
   if(arr[j]<=key)
   {
    i++;
    swap(arr[i],arr[j]);
   }
}

swap(arr[i+1],arr[r]);

return i+1;
}
int random_Partition(int arr[],int p,int r)
{
srand(time(NULL));
int rd=rand()%(r-p+1)+p;

swap(arr[rd],arr[r]);

return Partition(arr,p,r);
}

inline void swap(int &a,int &b)
{
int tmp=a;
a=b;
b=tmp;
}

void writeFile(string file_name)
{
int i=0;
FILE *fp;

fp=fopen(file_name.c_str(),"w");

if(!fp)
{
   cerr<<"failed to open file"<<endl;
   exit(-1);
}

srand(time(0));

while((i++)<100000)
{
   fprintf(fp,"%d ",rand()%100);
}

fclose(fp);
}

void readFile(string file_name,int arr[],int size)
{
FILE *fp=fopen(file_name.c_str(),"r");

assert(fp!=NULL);

for(int i=0;i<size;i++)
   fscanf(fp,"%d",&arr[i]);

fclose(fp);
}

void writeToFile(string file_name,int arr[],int size)
{
FILE *fp=fopen(file_name.c_str(),"w");
assert(fp!=NULL);

for(int i=0;i<size;i++)
   fprintf(fp,"%d ",arr[i]);

fclose(fp);

}

void insert_sort_rec(int array[],int size)
{
if(size>3)
   insert_sort_rec(array,size-1);

int i=size-1;
int key;

key=array[i];
i--;

while(i>=0 && array[i]>key)
{
   array[i+1]=array[i--];
}

array[i+1]=key;
}

------------------------------宏测试小程序---------------------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

struct test_struct{
     char   ch;
     int    it;
     int    ul;
};

int main()
{
     size_t off=-1;
      struct test_struct *st,*rt;

     st = (struct test_struct *) malloc (sizeof(struct test_struct));

     st->ch='a';
     st->it=1;
     st->ul=1ul;

/*    off =(size_t)&(((struct test_struct *)0)->it);*/
      off=offsetof(struct test_struct,it);
//    rt=(struct test_struct *)((char *)(&st->it)-off);
      rt=(struct test_struct *)(((char *)&(st->it)-(char *)off));

      printf("%d %d %d",rt->it,off,sizeof(struct test_struct));


      return 0;
}
--------------------------------------------------------------------------------------------------------------
由于4字节补齐的原因，sizeof(struct test_struct)=12,而不是等于9

-----------------------------------------------------------------------------------------------------------------------------------

1、链表结构体

struct list_head {
     struct list_head *next, *prev;
};
很显然，这是一个双向链表。不过，令人疑惑的是这个链表结构中竟然没有存储节点数据的字段，这是因为
它不是单独使用的，而是需要加入到表示具体数据结构的结构体中，与表示具体数据结构的结构体组合一起
使用，才能显示出它的用途和价值。
《……设计与实现》上说“一个list_head结构体本身没有什么意义，通常需要把它嵌入到自己的结构
体中”。

例如 struct my_struct{
             struct    list_head list;
             unsigned long      dog;
             void       *cat;
     }
这样表示具体数据结构的my_struct结构体就和list_head联系起来了。就可以把my_struct的对象通过
list成员链接起来，形成一个链表。
struct my_struct *p1,*p2,*p3......

p1->list->next=p2->list;
p2->list->pre=p1->list;
p2->list->next=p3->list;
p3->list->pre=p2->list;
p3->list->next=p1->list;
p1->list->pre=p3->list;

这样就通过list_head成员把my_struct的对象链接起来。
可以通过list_entry(p1->list,struct my_struct,list)来返回指向p1的my_struct指针，也就是
通过list_entry可以实现由list域访问其所属的结构体对象的功能。

2、链表操作函数
内核中很巧妙实现了链表的操作，大都非常简洁、精炼，通过宏或者内联函数实现，其中
list_entry的实现很有意思。

··初始化链表：
static inline void INIT_LIST_HEAD(struct list_head *list)
{
            list->next = list;
            list->prev = list;
}
可以看出初始化时链表前项节点和后向节点都指向了其本身。

··添加操作（此处仅列出一个）：

static inline void list_add(struct list_head *new, struct list_head *head)
{
        __list_add(new, head, head->next);
}

static inline void __list_add(struct list_head *new,
                              struct list_head *prev,
                              struct list_head *next)
{
        next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;
}

new是新添加项，添加到结点head所在的链表中，并且是加到head之后第一个结点。

··删除操作（仅列出一个）：

static inline void list_del(struct list_head *entry)
{
        __list_del(entry->prev, entry->next);
        entry->next = LIST_POISON1;
        entry->prev = LIST_POISON2;
}

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
        next->prev = prev;
        prev->next = next;
}

从链表中删除entry，并使其指向安全的位置LIST_POISON1和LIST_POISON2，关于这两个常量的解释和定义在
linux/poison.h（22行）
/*
* These are non-NULL pointers that will result in page faults
* under normal circumstances, used to verify that nobody uses
* non-initialized list entries.
*/
#define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)

··遍历链表：

遍历链表list_for_each是一个宏，展开了就是一个for循环

#define list_for_each(pos, head) \
        for (pos = (head)->next; prefetch(pos->next), pos != (head); \
                pos = pos->next)
其中prefech(pos->next)是处理器预取pos->next，通过处理器的预取功能，对for循环进行了优化。

··访问数据操作：

#define list_entry(ptr, type, member) \
        container_of(ptr, type, member)

#define container_of(ptr, type, member) ({                      \
        const typeof(((type *)0)->member) * __mptr = (ptr);     \
        (type *)((char *)__mptr - offsetof(type, member)); } )

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

container_of是一个有点复杂的宏,使用了C扩展关键字typeof，还有不好理解的求结构体成员
变量偏移.....
·((type *)0)是将0强制转化为type *，也就是指向type类型的指针

·((type *)0)->member是访问type结构中的member成员

·const typeof( ((type *)0)->member ) *__mptr 定义一个与((type *)0)->member同种类型的
指针变量（const变量）

·const typeof( ((type *)0)->member ) *__mptr=(ptr)对常量指针变量__mptr赋值
__mptr=ptr

·((size_t) &((TYPE *)0)->MEMBER得到member在type结构体中的偏移量，
offsetof(type,member)的展开效果

·(char *)__mptr - offsetof(type,member) 将__mptr强制转化为char类型指针，也就是__mptr
的地址，然后减去member在结构体中的偏移量，的到的自然就是结构体起始地址（偏移量求的很巧妙，
又很巧妙的获得结构体起始地址）。

·(type *)( (char *)__mptr - offsetof(type,member) )最后再强制转化为(type *)类型，
得到ptr所在的结构体对象（大功告成）。
到此成功的通过结构体对象的一个域的字段，获取了结构体对象本身，即访问list_head关联的结构对象
成功。
----------------------------------------------------------------------------------
取得结构体一个字段的偏移地址的方法 offsetof(type,member) 宏，设置的十分巧妙，
取得偏移后，具体对象的member地址-偏移地址，得到type对象的起始地址，设计相当的妙。

-----------------------------------------------------------------------------------------------------------------------------------

函数可以返回指向函数的指针，但是，正确写出这种返回类型相当不容易：

// ff is a function taking an int and returning a function pointer

// the function pointed to returns an int and takes an int* and an int

int (*ff(int))(int*, int);

阅读函数指针声明的最佳方法是从声明的名字开始由里而外理解

要理解该声明的含义，首先观察：

ff(int)

将 ff 声明为一个函数，它带有一个 int 型的形参。该函数返回

int (*)(int*, int);

它是一个指向函数的指针，所指向的函数返回 int 型并带有两个分别是int* 型和 int 型的形参。

使用 typedef 可使该定义更简明易懂：

// PF is a pointer to a function returning an int, taking an int* and an int

typedef int (*PF)(int*, int);

PF ff(int);

// ff returns a pointer to function

允许将形参定义为函数类型，但函数的返回类型则必须是指向

函数的指针，而不能是函数。

具有函数类型的形参所对应的实参将被自动转换为指向相应函数类型的指针。但是，当返回的
是函数时，同样的转换操作则无法实现：

// func is a function type, not a pointer to function!

typedef int func(int*, int);

void f1(func);    // ok: f1 has a parameter of function type

func f2(int);        // error: f2 has a return type of function type

func *f3(int);       // ok: f3 returns a pointer to function type

------------------------------------------------------------------简单例子---------------------------------------------------------------------------------

#include<iostream>
using namespace std;

int (*ff(int f))(int val1,int val2);
int (*fun)(int val1,int val2);
int foo(int a,int b);

int main()
{
   fun=ff(0);
   cout<<fun(1,2)<<endl;
   return 0;
}

int foo(int a,int b)
{
   cout<<a<<" "<<b<<" foo is calling..."<<endl;
   return b+1;
}

int (*ff(int f))(int val1,int val2)
{
   cout<<f<<" ff is calling..."<<endl;
   return foo;
}

-------------------------------------------------------------------------------输出------------------------------------------------------------------------------

0 ff is calling...
1 2 foo is calling...
3

----------------------------------------------------------------------------使用typedef-----------------------------------------------------------------------

#include<iostream>
using namespace std;

typedef int (*fun)(int val1,int val2);
fun ff(int);
int foo(int a,int b);

int main()
{
   cout<<ff(0)(1,2)<<endl;
   return 0;
}

int foo(int a,int b)
{
    cout<<a<<" "<<b<<" foo is calling..."<<endl;
    return b+1;
}

fun ff(int f)
{
   cout<<f<<" ff is calling..."<<endl;
   return foo;
}

堆排序可以原地排序，这一点上优于合并排序（需要一个辅助数组）；插入排序也是原地排序，可是时间复杂度是O(n^2)

1、保持堆（大顶堆）的性质的算法（A是输入堆，从i开始保持大顶堆的性质）：

max_heapify(A,i)
    l=LEFT(i)
    r=RIGHT(i)
    if(l<=heap_size(A)&&A[l]>A[i]）
            then largest=l
    else largest=i
    if(r<=heap_size(A)&&A[r]>A[largest])
           largest=r
    if(largest!=i)
           then exchange A[i]<->A[largest]
          max_heapify(A,largest)

2、建堆（从最后一个非叶子节点开始使其保持堆的性质）：

共有n个元素，则最后一个非叶子节点位置是n/2。

不妨设最后一个非叶子节点为(n+1)/2，则其左孩子是n+1>n，矛盾，所以是n/2，则算法描述为

build_maxHeap(A)
    for i=heap_size(A)/2 downto 1
           do max_heapify(A,i)

3、堆排序

首先建立大顶堆，然后把根元素（最大元素）与最后一个叶子节点交换位置，heap-size--，然后从根元素开始调整堆，使其保持大顶堆的性质。

算法描述为

   heap_sort(A)
           build_maxHeap(A)
          for i=heap_size(A) downto 2
               do exchange A[1]<->A[i]
                    heap_size(A)=heap_size(A)-1
                    max_heapify(A,1)

-------------------------------------------------示例演示---------------------------------------------------------------------

示例输入：9                 /*堆大小*/

                  5                 /*元素个数*/

                  1 5 2 4 3     /*输入元素值*/

输出：5 4 3 2 1

-------------------------------------------------C代码实现---------------------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>

#define LEFT(i)   2*i
#define RIGHT(i) 2*i+1
#define PARENT(i) i/2

struct HeapType{
int *base;   /*base[0]存放heap_size，因此heap_size字段也可以去掉*/
int length;
int heap_size; /*可去掉，用base[0]来代替*/
};

void max_heapify(struct HeapType heap,int i);
void build_maxHeap(struct HeapType heap);
void heap_sort(struct HeapType heap);
void swap(int *val1,int *val2);

int main(void)
{
int i=-1;
int n=-1;
int val=-1;
struct HeapType heap;

heap.length=0;
heap.heap_size=0;

scanf("%d",&n);

heap.length=n;
heap.base=(int*)malloc((heap.length+1)*sizeof(int));

scanf("%d",&heap.heap_size);

if(heap.heap_size>heap.length)
   return -1;

for(i=1;i<=heap.heap_size;i++)
{
   scanf("%d",&val);
   heap.base[i]=val;
   /*heap.heap_size +=1;*/
}

heap.base[0]=heap.heap_size;
i=heap.heap_size;

heap_sort(heap);
for( ;i>0;i--)
   printf("%d ",heap.base[i]);

return 0;
}

void max_heapify(struct HeapType heap,int i)
{
int largest=-1;
int l=LEFT(i);
int r=RIGHT(i);

if(l<=heap.heap_size && heap.base[l]>heap.base[i])
   largest=l;
else
   largest=i;

if(r<=heap.heap_size && heap.base[r]>heap.base[largest])
   largest=r;

if(largest!=i)
{
   swap(&heap.base[largest],&heap.base[i]);
   max_heapify(heap,largest);
}   
}

void build_maxHeap(struct HeapType heap)
{
int i=-1;

for(i=(heap.heap_size)>>1;i>0;i--)
   max_heapify(heap,i);
}

void heap_sort(struct HeapType heap)
{
int i=-1;

build_maxHeap(heap);

for(i=heap.heap_size;i>1;i--)
{
   swap(&heap.base[1],&heap.base[i]);
   heap.heap_size -=1;
   max_heapify(heap,1);
}
}

void swap(int *val1,int *val2)
{
int tmp=*val1;
*val1=*val2;
*val2=tmp;
}

--------------------------------------C++ Primer----------------------------------------------------------------

执行语句 delete p; 后，p变成没有定义。

在很多机器上，尽管 p 没有定义，但仍然存放了它之前所指向对象的地址，然而 p 所指向的内存已经被释放，因此 p 不再有效。

删除指针后，该指针变成悬垂指针。

悬垂指针指向曾经存放对象的内存，但该对象已经不再存在了。悬垂指针往往导致程序错误，而且很难检测出来。

一旦删除了指针所指向的对象，立即将指针置为 0，这样就非常清楚地表明指针不再指向任何对象。

-------------------------------------------------------------------------------------------------------------

第一天出来的人作为“计数者”（第一个出来的人确定自己是“计数者”，其他人确定自己不是“计数者”）

如果是“计数者”就把灯打开（关闭的情况下打开），计数+1，若灯开着的话就什么也不做

如果不是“计数者”，如果是第一次出来放风而且灯开着就关闭它，否则什么也不做

当“计数者”的 counter=100的时候就可以想国王申请走人了。

-------------------------------------------------------------------------------------------------------------

这种算法需要多长的时间才可以获得释放呢，写代码验证之。答案是10000天左右，也就是20-30年的时间，够漫长的。不知道还有没有其他更好的方法。

#include<iostream>
#include<vector>
#include<ctime>
using namespace std;

int   getDays(void);
bool not_selected(vector<int> v,int key);

int main(void)
{
cout<<getDays()<<endl;
return 0;
}

int getDays(void)
{
int observer=-1;
int rd=-1;
int counter=0;
int days=0;
vector<int> prison;
volatile bool b_light=false;

srand(time(NULL));
observer=rand()%100;
b_light=true;
days++;

while(1)
{
   days++;
   if((rd=rand()%100)==observer)
   {
    if(b_light==false)
    {
     counter++;
     b_light=true;
    }
    if(counter==99)
     break;
   }
   else
   {
    if(b_light&&not_selected(prison,rd))
    {
     prison.push_back(rd);
     b_light=false;
    }
   } //else
} //while

return days;
}

bool not_selected(vector<int> v, int key)
{
for(vector<int>::iterator iter=v.begin();iter!=v.end();++iter)
{
   if(*iter==key)
    return false;
}

return true;
}