奧萊利為啥整倆海馬當(dāng)封皮?

為什么 O’Reilly 用動物形象做書籍封面

譯者序(摘選)
有關(guān)數(shù)據(jù)結(jié)構(gòu)和算法題材的經(jīng)典書籍有很多,如《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》,《算法導(dǎo)論》等,但本書絕不同于之前的相關(guān)書籍.當(dāng)我們在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法時,往往花費(fèi)了大量的時間糾結(jié)于各種公式和理論證明上,學(xué)究氣息過于濃厚而少了幾分實(shí)踐感.
將一個實(shí)際問題同我們學(xué)到的算法和數(shù)據(jù)結(jié)構(gòu)相結(jié)合起來,這正是軟件開發(fā)中的一項(xiàng)重要技能:抽象建模能力.
本書最大的特點(diǎn)是理論與實(shí)踐相結(jié)合,這主要體現(xiàn)在以下幾點(diǎn)上:
1.本書中的數(shù)據(jù)結(jié)構(gòu)和算法實(shí)現(xiàn)能夠以接口的形式充分得到復(fù)用
2.書中的代碼實(shí)現(xiàn)主要以教學(xué)為目的,但也同樣考慮到了實(shí)現(xiàn)效率的問題.
3.書中所有的應(yīng)用舉例都來自于真實(shí)的應(yīng)用.包括操作系統(tǒng)中的頁幀管理,頁面置換算法,表達(dá)式處理等

出版時間已經(jīng)超過15年之久...
問與答模塊挺不錯的，有三四個關(guān)于本章內(nèi)容的問答題，類似于面試題逻炊，加強(qiáng)了印象平绩，非常好，但問題還算能答上來，描述有點(diǎn)多，就不記錄了，可以去看看書债蜜。

第一章 概述
第二章 指針操作
第三章 遞歸
第四章 算法分析
第五章 鏈表
第六章 棧和隊(duì)列
第七章 集合
第八章 哈希表

本文代碼地址

第一章 概述

使用數(shù)據(jù)結(jié)構(gòu)的三個原因是：
1、效率：數(shù)據(jù)結(jié)構(gòu)組織數(shù)據(jù)的方式使得算法變得更加高效
2究反、抽象：數(shù)據(jù)結(jié)構(gòu)使我們以一種更加容易理解的方式去看待數(shù)據(jù)寻定，為解決問題提供了一層抽象概念
3、重用性：模塊化且上下文無關(guān)的

使用算法的三個原因是：
1精耐、效率：人們已經(jīng)找到了許多高效的方法來解決問題
2特姐、抽象：許多看似復(fù)雜的問題都可以用已存在的著名算法來簡化
3、重用性：能在很多不同場景下重用

算法設(shè)計(jì)的一般方法：

按照算法采用的方法和思路給它們分類
隨機(jī)法：依賴于隨機(jī)數(shù)的統(tǒng)計(jì)特性黍氮。例子是快速排序

分治法：分解唐含，將數(shù)據(jù)分解為更小，更容易管理的部分沫浆。求解捷枯，對每個分解出的部分進(jìn)行處理。合并专执，將每部分處理的結(jié)果合并淮捆。例子是歸并排序

動態(tài)規(guī)劃：與分治法類似，但子問題之間并不是獨(dú)立的本股，可能是有關(guān)系的攀痊，這本書里面沒有這個例子

貪心法：在求解問題時總能做出在當(dāng)前的最佳選擇。不是從整體最優(yōu)上考慮拄显，而僅僅是在某種意義上的局部最優(yōu)解苟径。例子是霍夫曼編碼

近似法：并不計(jì)算出最優(yōu)解，只計(jì)算出“差不多好”的解躬审。解決那些計(jì)算成本很高但又不能放棄的問題棘街。例子是推銷員問題

第二章 指針操作

指針：一個指針其實(shí)只是一個變量，它存儲數(shù)據(jù)在內(nèi)存中的地址承边。
結(jié)構(gòu)：結(jié)構(gòu)不允許包含自身的實(shí)例遭殉，但可以包含指向自身實(shí)例的指針
數(shù)組：a[i] = * (a+i)
范型指針（void指針）：void * 可以通過void指針存儲和檢索任何類型的數(shù)據(jù)
指針的類型轉(zhuǎn)換：a為A類型,b為B類型; a=(A * )b;
函數(shù)指針：函數(shù)名和用括號括起來，指向可執(zhí)行代碼段的信息塊 int( match)(int * value1,int * value2)

這一章就是介紹了指針的一些基礎(chǔ)知識

第三章 遞歸

基本遞歸

用階乘來介紹基本遞歸：F(n)=nF(n-1) 當(dāng)n>1; F(n)=1 當(dāng)n=0,n=1;
然后介紹遞歸的運(yùn)行流程博助，C中函數(shù)的執(zhí)行方式险污，C在內(nèi)存中的組織方式
可執(zhí)行程序由4個區(qū)域組成：
代碼段：程序運(yùn)行時所執(zhí)行的機(jī)器指令
靜態(tài)數(shù)據(jù)區(qū)：在程序生命周期內(nèi)一直持久的數(shù)據(jù)，比如全局變量和靜態(tài)局部變量富岳。
堆：程序運(yùn)行時動態(tài)分配的存儲空間
棧：函數(shù)調(diào)用的信息蛔糯。

尾遞歸

一個函數(shù)中所有遞歸形式的調(diào)用都出現(xiàn)在函數(shù)的末尾
遞歸調(diào)用是整個函數(shù)體中最后執(zhí)行的語句且它的返回值不屬于表達(dá)式的一部分
同樣用階乘來介紹尾遞歸：F(n,a)=F(n-1,na) 當(dāng)n>1; F(n,a)=a 當(dāng)n=0,n=1;
就是多了第二個參數(shù)a（默認(rèn)為1）,a記錄當(dāng)前值里伯，維護(hù)遞歸層次的深度，避免了每次還需要將返回值再乘以n

問與答：

1.歸并排序用遞歸的實(shí)現(xiàn)：
T(n)=2T(n/2)+n 當(dāng)n>1; T(n)=1 當(dāng)n=1;
要注意的是判斷條件要對
2.用尾遞歸求解整數(shù)質(zhì)因子：
F(n,P)=F(n/i,PUi) 當(dāng)n不為素?cái)?shù); F(n,P)=PUn 當(dāng)n為素?cái)?shù);
i為n的最小質(zhì)因子渤闷，P是結(jié)果集合
3.當(dāng)遞歸的終止條件有誤，永遠(yuǎn)無法滿足時脖镀，會出現(xiàn)什么情況飒箭？
棧的增長會超過可接受的值，程序會因?yàn)闂Ｒ绯龆K止運(yùn)行
...

第四章 算法分析

最壞情況分析：告訴我們算法性能的上限蜒灰，而最好情況都是1次弦蹂。
講了下O表示法的簡單規(guī)則：常數(shù)項(xiàng)為O(1)，忽略常量因子强窖，兩個運(yùn)行時間函數(shù)加法運(yùn)算取最大值凸椿，乘法結(jié)果不變
因?yàn)樵诤瘮?shù)運(yùn)算次數(shù)逐漸變大的時候，這些條件占據(jù)整個運(yùn)行時間的比例會越來越大翅溺，直至小的條件占比幾乎被忽略
然后介紹了如何計(jì)算算法復(fù)雜度：按照算法的步驟歸納成公式脑漫，最后用O表示法簡化
然后分析了下插入排序，得出插入排序的算法復(fù)雜度為O(n2)

問與答就是幾個計(jì)算時間復(fù)雜度的題

相關(guān)擴(kuò)展：

表示算法性能的其他表示法：（不僅僅只有大O表示法）
O表示法：描述的是在一定條件約束下函數(shù)的上限值
Ω表示法：描述的是在一定的條件約束下函數(shù)的下限值
θ表示法：描述函數(shù)的區(qū)間值
W表示法：類似Ω表示法咙崎，只是更精確
NP完全問題：
沒有已知的求解多項(xiàng)式時間的算法优幸，但也無法證明此多項(xiàng)式不存在，這類問題稱為NP完全問題褪猛。
很多有用且看似困難的問題都?xì)w為此類网杆，一直是計(jì)算機(jī)科學(xué)領(lǐng)域令人困惑和煩惱的問題。

第五章 鏈表

單鏈表：

簡稱為鏈表伊滋，由各個元素之間通過一個指針彼此鏈接起來而組成碳却。每個元素包含數(shù)據(jù)成員、next指針笑旺，指向后面的元素昼浦。
單鏈表只能從頭到尾以一個方向進(jìn)行遍歷。
list文件給出了單鏈表的抽象數(shù)據(jù)類型定義

list文件貼出來看一下筒主，作者整本書都是這樣的風(fēng)格座柱，用代碼來講解。我認(rèn)為比較重要的就貼出來物舒，其他的還是下載源碼查看吧色洞，太多了。
不過如果有需要的話可以留言冠胯，我可以全部貼出來

//  list.h
//鏈表抽象數(shù)據(jù)類型

#ifndef list_h
#define list_h

#include <stdio.h>

typedef struct ListElmt_{
    void *data;
    struct ListElmt_ *next;
}ListElmt;

typedef struct List_{
    int size;
    int (*math)(const void *key1,const void *key2);
    void (*destroy)(void *data);
    ListElmt *head;
    ListElmt *tail;
}List;

//初始化一個鏈表 O(1)
void list_init(List *list,void (*destroy)(void *data));

//銷毀鏈表 O(n)
void list_destroy(List *list);

//在鏈表list的element后面插入一個新元素,如果element為NULL火诸，代表插入 頭部 O(1)
int list_ins_next(List *list,ListElmt *element,const void *data);

//移除鏈表list的element后面的元素，如果element為NULL荠察，則移除鏈表頭元素 O(1)
int list_rem_next(List *list,ListElmt *element,void **data);

//以下宏皆為O(1)
//返回list中元素的個數(shù)
int list_size(const List *list);
//返回list中頭元素的指針
ListElmt *list_head(const List *list);
//返回list中尾元素的指針
ListElmt *list_tail(const List *list);
//判斷element是否為頭結(jié)點(diǎn)
int list_is_head(const ListElmt *element);
//判斷element是否為尾結(jié)點(diǎn)
int list_is_tail(const ListElmt *element);
//element中保存的數(shù)據(jù)
void *list_data(const ListElmt *element);
//element的下一個結(jié)點(diǎn)
ListElmt *list_next(const ListElmt *element);

#define list_size(list) ((list)->size)
#define list_head(list) ((list)->head)
#define list_tail(list) ((list)->tail)
#define list_is_head(list,element) ((element) == (list)->head?1:0)
#define list_is_tail(element) ((element)->next == NULL?1:0)
#define list_data(element) ((element)->data)
#define list_next(element) ((element)->next)

#endif /* list_h */

#include "list.h"
#include <string.h>
#include <stdlib.h>

//初始化一個鏈表
void list_init(List *list,void (*destroy)(void *data))
{
    list->size = 0;
    list->destroy = destroy;
    list->head = NULL;
    list->tail = NULL;
    return;
}

//銷毀鏈表
void list_destroy(List *list)
{
    void *data;
    //每個元素都調(diào)用一次
    while (list_size(list)>0)
    {
        if (list_rem_next(list, NULL, (void **)&data)==0 && list->destroy != NULL)
        {
            list_destroy(data);
        }
    }
    //將list中當(dāng)前位置后面的n個字節(jié)用0替換并返回list
    memset(list,0,sizeof(List));
    return;
}

//在鏈表list的element后面插入一個新元素
int list_ins_next(List *list,ListElmt *element,const void *data)
{
    ListElmt *new_element;
    if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
    {
        return -1;
    }
    new_element->data = (void *)data;
    //當(dāng)新的元素將插入鏈表頭部
    if (element == NULL)
    {
        if (list_size(list) == 0)
        {
            list->tail = new_element;
        }
        //一般是將新元素的next指針指向它之后的那個元素置蜀，
        //然后將新元素位置之前的結(jié)點(diǎn)next指針指向新插入的元素
        new_element->next = list->head;
        list->head = new_element;
    }
    else
    {
        if (element->next == NULL)
        {
            list->tail = new_element;
        }
        new_element->next = element->next;
        element->next = new_element;
    }
    list->size++;
    return 0;
}

//移除鏈表list的element后面的元素
int list_rem_next(List *list,ListElmt *element,void **data)
{
    ListElmt *old_element;
    if (list_size(list) == 0)
    {
        return -1;
    }
    //移除頭結(jié)點(diǎn)
    if (element == NULL)
    {
        //將要移除的目標(biāo)節(jié)點(diǎn)前一個元素的next指針指向目標(biāo)節(jié)點(diǎn)下一個元素
        *data = list->head->data;
        old_element = list->head;
        list->head = list->head->next;
        //當(dāng)移除操作使整個鏈表稱為空鏈表
        if (list_size(list) == 1)
        {
            list->tail = NULL;
        }
    }
    else
    {
        if (element->next == NULL)
        {
            return -1;
        }
        *data = element->next->data;
        old_element = element->next;
        element->next = element->next->next;
        if (element->next == NULL)
        {
            list->tail = element;
        }
    }
    
    free(old_element);
    list->size--;
    return 0;
}

鏈表的應(yīng)用：管理頁幀
frames文件是使用鏈表管理頁幀的例子
在一些支持虛擬內(nèi)存的系統(tǒng)中奈搜，用鏈表來管理頁幀是非常好的辦法，因?yàn)轫搸姆峙鋵⑸婕邦l繁的插入和刪除操作盯荤，而且這些操作都發(fā)生在鏈表頭
虛擬內(nèi)存：一種地址空間的映射機(jī)制馋吗，它允許進(jìn)程不必完全加載到物理內(nèi)存（系統(tǒng)的實(shí)際內(nèi)存）中也可以運(yùn)行。優(yōu)點(diǎn)是進(jìn)程可以使用比物理內(nèi)存大得多的空間秋秤，多個進(jìn)程能夠共享系統(tǒng)的內(nèi)存以并發(fā)的方式執(zhí)行宏粤。
而運(yùn)行虛擬內(nèi)存下的進(jìn)程需要處理虛擬地址，必須由操作系統(tǒng)做轉(zhuǎn)換灼卢，每一個進(jìn)程都有自己的頁表绍哎，將虛擬地址空間中的頁映射到物理內(nèi)存中的頁幀上。

對于開發(fā)來說可能用處不大鞋真，不過可以更好的理解鏈表的使用

雙向鏈表：

鏈表元素之間由兩個指針鏈接崇堰。每個元素包含數(shù)據(jù)成員、next指針涩咖、prev指針海诲，指向前驅(qū)元素。

雙向鏈表書上沒有例子與應(yīng)用檩互，直接看看源碼dlist文件吧

循環(huán)鏈表：

有尾部元素的鏈表饿肺，可以是單向的或雙向的，源碼clist文件

循環(huán)鏈表的應(yīng)用：第二次機(jī)會頁面置換法
第二次機(jī)會頁面置換法盾似，也稱時鐘算法敬辣，是最近最少使用算法（也稱為LRU頁面替換法，Least Recenty Used）
跟隨上面,是系統(tǒng)管理內(nèi)存頁幀分配的例子零院，解決空閑頁面鏈表為空時溉跃，系統(tǒng)為其分配新的頁幀。
大概就是當(dāng)需要某個頁幀時告抄，系統(tǒng)遍歷鏈表撰茎，找到上次遍歷沒有被系統(tǒng)訪問過的頁面，因?yàn)樽詈笠氐奖闅v開始的頁面打洼，所以循環(huán)鏈表最適合龄糊。
作者花了一整頁篇幅來講解，但我認(rèn)為對于開發(fā)來說可能用處不大募疮，建議看看源碼page文件即可

問與答：

1炫惩、數(shù)組與鏈表的使用情況：
進(jìn)行頻繁的插入和刪除時，鏈表更適合阿浓，而數(shù)組的元素是連續(xù)排列的他嚷，更適合通過索引查找
2、鏈表的增刪改查與數(shù)組相比有何差異？
的確筋蓖，鏈表除了銷毀操作之外卸耘，其他操作都是O(1)，但是都需要一個想要操作的元素指針粘咖，而得到該指針的代價是很高的蚣抗，需要遍歷鏈表
插入本身復(fù)雜度是O(1)，但是訪問特定位置的元素復(fù)雜度是O(n)
3瓮下、為什么單鏈表和循環(huán)鏈表不能指定移除該元素翰铡，而是該元素下一個元素？
因?yàn)闆]有指向前驅(qū)結(jié)點(diǎn)的指針唱捣，所以找不到前驅(qū)結(jié)點(diǎn)來指向被移除元素的后繼結(jié)點(diǎn)。
...

第六章 棧和隊(duì)列

棧

后進(jìn)先出网梢，羽毛球筒
作者使用鏈表實(shí)現(xiàn)棧的震缭，調(diào)用的鏈表的實(shí)現(xiàn)方法

stack文件

#ifndef stack_h
#define stack_h

#include <stdio.h>
#include "list.h"

typedef List Stack;

#define stack_init list_init
#define stack_destroy list_destroy


//向stack中壓入一個元素 O(1)
int stack_push(Stack *stack,const void *data);
//從stack中彈出一個元素 O(1)
int stack_pop(Stack *stack,void **data);
//皆為 O(1)
//獲取棧頂部的元素
void *stack_peek(const Stack *stack);
//獲取棧中元素個數(shù)
int stack_size(const Stack *stack);

//獲取頂元素的信息
#define stack_peek(stack) ((stack)->head == NULL?NULL:(stack)->head->data)
#define stack_size list_size

#endif /* stack_h */

#include "stack.h"

//向stack中壓入一個元素 O(1)
int stack_push(Stack *stack,const void *data)
{
    return list_ins_next(stack, NULL, data);
}
//從stack中彈出一個元素 O(1)
int stack_pop(Stack *stack,void **data)
{
    return list_rem_next(stack, NULL, data);
}

隊(duì)列

先進(jìn)先出，排隊(duì)
作者也是使用鏈表來實(shí)現(xiàn)隊(duì)列的战虏，調(diào)用的隊(duì)列的實(shí)現(xiàn)方法

#include "queue.h"

int queue_enqueue(Queue *queue,const void *data)
{
    return list_ins_next(queue, list_tail(queue), data);
}

int queue_dequeue(Queue *queue,void **data)
{
    return list_rem_next(queue, NULL, data);
}

作者用事件驅(qū)動來舉例隊(duì)列的作用拣宰，因?yàn)橛?jì)算機(jī)的應(yīng)用主要遵循的是實(shí)時發(fā)生的順序來執(zhí)行，需要有序地存儲和管理事件烦感。
當(dāng)告知應(yīng)用程序有事件將進(jìn)行處理時巡社，將一個事件入隊(duì)，當(dāng)應(yīng)用程序認(rèn)為是時候處理一個事件時手趣，將一個事件出隊(duì)

問與答：

1晌该、從一個隊(duì)列中刪除一些元素，剩下的按順序留在隊(duì)列中绿渣，用隊(duì)列和鏈表如何處理
隊(duì)列：從頭開始出隊(duì)朝群，不刪除的出隊(duì)后再入隊(duì)
鏈表：遍歷，遍歷到元素后用list_rem_next函數(shù)刪除即可

第七章 集合

集合是不同對象的無序聚集中符。成員是無序的姜胖，每個成員都只在集合中出現(xiàn)一次
是數(shù)學(xué)中集合的概念，有子集淀散，并集右莱，空集等等，操作也是交集档插，并集慢蜓，差集等
作者也是使用鏈表來實(shí)現(xiàn)的，所以很多函數(shù)需要遍歷郭膛，性能適合小型到中等規(guī)模的集合數(shù)據(jù)
(Set的代碼在github中)

集合的應(yīng)用：集合覆蓋
在一群選手中挑選人員組建出一支隊(duì)伍胀瞪，每名選手都有特定的技能組合。目標(biāo)是組建出人數(shù)最少，但所有技能都有的隊(duì)伍凄诞。
技能集合S={a,b,c,d,e}
選手集合P={A1圆雁，A2，A3帆谍，A4}
組合集合為：A1={a,b} A2={c,d,e} A3={a,b,c,d} A4={a}
最佳集合應(yīng)為C={A1伪朽，A2}
但算法的結(jié)果為C={A3，A2,A1}

#ifndef cover_h
#define cover_h

#include <stdio.h>
#include "set.h"

typedef struct KSet_{
    void *key;
    Set set;
}KSet;

int cover(Set *members,Set *subsets,Set *covering);

#endif /* cover_h */

#include "cover.h"

int cover(Set *members,Set *subsets,Set *covering)
{
    Set intersection;
    KSet *subset;
    ListElmt *member;
    ListElmt *max_member=NULL;
    void *data;
    int max_size;
    
    set_init(covering, subsets->math, NULL);
    while (set_size(members)>0 && set_size(subsets) > 0)
    {
        max_size = 0;
        for (member = list_head(subsets); member !=NULL; member = list_next(member))
        {
            if (set_intersection(&intersection, &((KSet *)list_data(member))->set, members) != 0)
            {
                return -1;
            }
            
            if (set_size(&intersection) > max_size)
            {
                max_member = member;
                max_size = set_size(&intersection);
            }
            set_destroy(&intersection);
        }
        
        if (max_size == 0)
        {
            return 1;
        }
        
        subset = (KSet *)list_data(max_member);
        
        if (set_insert(covering, subset) != 0)
        {
            return -1;
        }
        
        for (member=list_head(&((KSet *)list_data(max_member))->set); member!=NULL; member=list_next(member))
        {
            data = list_data(member);
            if (set_remove(members, (void **)&data)==0
                &&members->destroy != NULL)
            {
                members->destroy(data);
            }
        }
        
        if (set_remove(subsets, (void **)&subset) != 0)
        {
            return -1;
        }
       
    }
    if (set_size(members)>0)
    {
        return -1;
    }
     return 0;
}

是一種優(yōu)化求解問題
每次開始都在subsets中找出能夠覆蓋到members的最大交集汛蝙，然后加到covering中烈涮，所以有可能解會有小小的多余，是一種近似最優(yōu)解
int cover(Set *members,Set *subsets,Set *covering);
members為S窖剑，subsets為P中的子集如A1坚洽， covering為C

第八章 哈希表

散列表，通過一個哈希函數(shù)西土，在所有可能的鍵與槽位之間建立一張映射表讶舰。

1 鏈?zhǔn)焦１?/h6>

由一組鏈表構(gòu)成，每個鏈表都可以看做一個桶需了，所有的元素通過散列的方式放到具體的不同的桶中

#ifndef chtbl_h
#define chtbl_h

#include <stdio.h>
#include "list.h"

typedef struct CHTbl_{
    int buckets;//桶數(shù)
    int (*h)(const void *key);
    int (*match)(const void *key1,const void *key2);
    void (*destroy)(void *data);
    int size;
    List *table;
}CHTbl;

//buckets為桶數(shù)跳昼，
//h指向哈希函數(shù)，會將鍵散列
//match判斷兩個鍵是否匹配
//destroy銷毀
int chtbl_init(CHTbl *htbl,int buckets,int(*h)(const void *key),int(*match)(const void *key1,const void *key2),void(*destroy)(void *data));

//銷毀肋乍，刪除每個桶中的元素
void chtbl_destroy(CHTbl *htbl);
int chtbl_insert(CHTbl *htbl,const void *data);
int chtbl_remove(CHTbl *htbl,void **data);
//查找
int chtbl_lookup(const CHTbl *htbl,void **data);

#define chtbl_size(htbl) ((htbl)->size)

#endif /* chtbl_h */

#include "chtbl.h"
#include <string.h>
#include <stdlib.h>

int chtbl_init(CHTbl *htbl,int buckets,int(*h)(const void *key),int(*match)(const void *key1,const void *key2),void(*destroy)(void *data))
{
    if ((htbl->table = (List *)malloc(buckets *sizeof(List))) == NULL)
    {
        return -1;
    }
    htbl->buckets = buckets;
    for (int i=0; i<htbl->buckets; i++)
    {
        list_init(&htbl->table[i], destroy);
    }
    
    htbl->h = h;
    htbl->match = match;
    htbl->destroy = destroy;
    
    htbl->size = 0;
    return 0;
}

//銷毀鹅颊，刪除每個桶中的元素
void chtbl_destroy(CHTbl *htbl)
{
    for (int i=0; i<htbl->buckets; i++)
    {
        list_destroy(&htbl->table[i]);
    }
    free(htbl->table);
    memset(htbl, 0, sizeof(CHTbl));
    return;
}

int chtbl_insert(CHTbl *htbl,const void *data)
{
    void *temp;
    int bucket,retval;
    temp = (void *)data;
    //判斷是否已經(jīng)存在
    if (chtbl_lookup(htbl, &temp) == 0)
    {
        return 1;
    }
    //哈希key
    bucket = htbl->h(data) % htbl->buckets;
    //插入
    if((retval=list_ins_next(&htbl->table[bucket], NULL, data))==0)
    {
        htbl->size++;
    }
    return retval;
}

int chtbl_remove(CHTbl *htbl,void **data)
{
    ListElmt *element,*prev;
    int bucket;
    //哈希key
    bucket = htbl->h(data) % htbl->buckets;
    prev = NULL;
    for (element = list_head(&htbl->table[bucket]); element != NULL; element = list_next(element))
    {
        if (htbl->match(*data,list_data(element)))
        {
            if (list_rem_next(&htbl->table[bucket], prev, data)==0)
            {
                htbl->size--;
                return 0;
            }else{
                return -1;
            }
        }
        prev = element;
    }
    return -1;
}

//查找
int chtbl_lookup(const CHTbl *htbl,void **data)
{
    ListElmt *element;
    int bucket;
    //哈希key
    bucket = htbl->h(data) % htbl->buckets;
    for (element = list_head(&htbl->table[bucket]); element != NULL; element = list_next(element))
    {
        if (htbl->match(*data,list_data(element)))
        {
            *data = list_data(element);
            return 0;
        }
    }
    return -1;
}

解決沖突
兩個鍵散列到一個相同的槽位時，兩個鍵之間會產(chǎn)生沖突
鏈?zhǔn)焦１砭椭苯訉⒃胤湃胪爸心乖欤坝锌赡茉絹碓酱?br> 一個好的哈希函數(shù)會盡可能做到均勻散列
h(k) = m 一般k為整型

轉(zhuǎn)換鍵的方法：
取余法：計(jì)算k除以m的所得到的余數(shù)堪伍，將k映射到m槽位
h(k)=k mod m

乘法：將整型鍵k乘以一個常數(shù)A(0<A<1)，取結(jié)果的小數(shù)部分觅闽，然后乘以m取結(jié)果的整數(shù)部分杠娱。

鏈?zhǔn)焦１淼膽?yīng)用：符號表
在編譯器中用來維護(hù)程序中出現(xiàn)的符號信息。
編譯器在翻譯時谱煤，為了能夠更加有效地管理程序中的符號信息摊求，使用符號表

2 開地址哈希表

元素存放在表本身，用于依賴于固定大小表的應(yīng)用

#ifndef ohtbl_h
#define ohtbl_h

#include <stdio.h>

typedef struct OHTbl_{
    int     positions;//哈希表中分配的槽位數(shù)目
    void    *vacated;//曾經(jīng)刪除的一個元素
    
    int     (*h1)(const void *key);
    int     (*h2)(const void *key);
    int     (*match)(const void *key1,const void *key2);
    void    (*destroy)(void *data);
    
    int     size;
    void    **table;//存儲元素的數(shù)組
}OHTbl;


//positions為槽位的個數(shù)
//h1刘离，h2指向哈希函數(shù)室叉，會將鍵散列
//match判斷兩個鍵是否匹配
//destroy銷毀
int ohtbl_init(OHTbl *htbl,int positions,int(*h1)(const void *key),int(*h2)(const void *key),int(*match)(const void *key1,const void *key2),void(*destroy)(void *data));

//銷毀
void ohtbl_destroy(OHTbl *htbl);
int ohtbl_insert(OHTbl *htbl,const void *data);
int ohtbl_remove(OHTbl *htbl,void **data);
//查找
int ohtbl_lookup(const OHTbl *htbl,void **data);

#define ohtbl_size(htbl) ((htbl)->size)


#endif /* ohtbl_h */

#include "ohtbl.h"
#include <stdlib.h>
#include <string.h>

static char vacated;

int ohtbl_init(OHTbl *htbl,int positions,int(*h1)(const void *key),int(*h2)(const void *key),int(*match)(const void *key1,const void *key2),void(*destroy)(void *data))
{
    if ((htbl->table = (void **)malloc(positions *sizeof(void *))) == NULL)
    {
        return -1;
    }
    htbl->positions = positions;
    for (int i=0; i<htbl->positions; i++)
    {
        htbl->table[i] = NULL;
    }
    htbl->vacated = &vacated;
    htbl->h1 = h1;
    htbl->h2 = h2;
    htbl->match = match;
    htbl->destroy = destroy;
    htbl->size = 0;
    return 0;
}

//銷毀
void ohtbl_destroy(OHTbl *htbl)
{
    if (htbl->destroy != NULL)
    {
        for (int i=0; i<htbl->positions; i++)
        {
            if (htbl->table[i] != NULL && htbl->table[i] != htbl->vacated)
            {
                htbl->destroy(htbl->table[i]);
            }
        }
    }
    free(htbl->table);
    memset(htbl,0,sizeof(OHTbl));
    return;
}

int ohtbl_insert(OHTbl *htbl,const void *data)
{
    void *temp;
    int position;
    if (htbl->size == htbl->positions)
    {
        return -1;
    }
    temp = (void *)data;
    if (ohtbl_lookup(htbl, &temp)==0)
    {
        return 1;
    }
    for (int i=0; i<htbl->positions; i++)
    {
        position = (htbl->h1(data)+(i*htbl->h2(data))) % htbl->positions;
        if (htbl->table[position]==NULL || htbl->table[position] == htbl->vacated)
        {
            htbl->table[position] = (void *)data;
            htbl->size++;
            return 0;
        }
    }
    return -1;
}


int ohtbl_remove(OHTbl *htbl,void **data)
{
    int position;
    for (int i=0; i<htbl->positions; i++)
    {
        position = (htbl->h1(*data) + (i*htbl->h2(*data))) % htbl->positions;
        if (htbl->table[position] == NULL)
        {
            return -1;
        }
        else if (htbl->table[position] == htbl->vacated)
        {
            continue;
        }
        else if (htbl->match(htbl->table[position],*data))
        {
            *data = htbl->table[position];
            htbl->table[position] = htbl->vacated;
            htbl->size--;
            return 0;
        }
    }
    return -1;
}
//查找
int ohtbl_lookup(const OHTbl *htbl,void **data)
{
    int position;
    for (int i=0; i<htbl->positions; i++)
    {
        position = (htbl->h1(*data) + (i*htbl->h2(*data))) % htbl->positions;
        if (htbl->table[position] == NULL)
        {
            return -1;
        }
        else if (htbl->match(htbl->table[position],*data))
        {
            *data = htbl->table[position];
            return 0;
        }
    }
    return -1;
}

解決沖突
探查這個表，直到找到一個可以放置元素的槽
探查槽位的哈希函數(shù)定義為：h(k,i)=x
k是鍵硫惕，i是探查的次數(shù)茧痕，x是得到的哈希編碼

線性探查
用哈希函數(shù)定位到某一數(shù)值后探查表中連續(xù)的槽位
h(k,i) = (h(k)+i) mod m
雙散列
通過計(jì)算兩個輔助哈希函數(shù)哈希編碼的和來得到哈希編碼
h(k,i) = (h1(k)+ih2(k)) mod m
h1與h2為兩個輔助哈希函數(shù)，能夠在表中探查并產(chǎn)生較好的元素分布

問與答：

1恼除、鏈?zhǔn)焦１淼淖顗男阅茏倏酰咳绾伪ＷC不會發(fā)生曼氛？
所有元素全部散列在一個桶中時，性能最差
選擇一個好的哈希函數(shù)??
2令野、開地址哈希表的最壞性能舀患？如何保證不會發(fā)生？
表已經(jīng)滿了气破，而且要查找的元素不在此表中聊浅，性能最差
不要讓元素的個數(shù)超過表容量的80%