譯者序(摘選)
有關(guān)數(shù)據(jù)結(jié)構(gòu)和算法題材的經(jīng)典書籍有很多,如《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》,《算法導(dǎo)論》等,但本書絕不同于之前的相關(guān)書籍.當(dāng)我們?cè)趯W(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法時(shí),往往花費(fèi)了大量的時(shí)間糾結(jié)于各種公式和理論證明上,學(xué)究氣息過(guò)于濃厚而少了幾分實(shí)踐感.
將一個(gè)實(shí)際問(wèn)題同我們學(xué)到的算法和數(shù)據(jù)結(jié)構(gòu)相結(jié)合起來(lái),這正是軟件開(kāi)發(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)效率的問(wèn)題.
3.書中所有的應(yīng)用舉例都來(lái)自于真實(shí)的應(yīng)用.包括操作系統(tǒng)中的頁(yè)幀管理,頁(yè)面置換算法,表達(dá)式處理等
出版時(shí)間已經(jīng)超過(guò)15年之久...
問(wèn)與答模塊挺不錯(cuò)的，有三四個(gè)關(guān)于本章內(nèi)容的問(wèn)答題，類似于面試題，加強(qiáng)了印象，非常好，但問(wèn)題還算能答上來(lái)，描述有點(diǎn)多，就不記錄了，可以去看看書。
第一章 概述
第二章 指針操作
第三章 遞歸
第四章 算法分析
第五章 鏈表
第六章 棧和隊(duì)列
第七章 集合
第八章 哈希表
第一章 概述
使用數(shù)據(jù)結(jié)構(gòu)的三個(gè)原因是：
1、效率：數(shù)據(jù)結(jié)構(gòu)組織數(shù)據(jù)的方式使得算法變得更加高效
2、抽象：數(shù)據(jù)結(jié)構(gòu)使我們以一種更加容易理解的方式去看待數(shù)據(jù)，為解決問(wèn)題提供了一層抽象概念
3、重用性：模塊化且上下文無(wú)關(guān)的
使用算法的三個(gè)原因是：
1、效率：人們已經(jīng)找到了許多高效的方法來(lái)解決問(wèn)題
2、抽象：許多看似復(fù)雜的問(wèn)題都可以用已存在的著名算法來(lái)簡(jiǎn)化
3、重用性：能在很多不同場(chǎng)景下重用
算法設(shè)計(jì)的一般方法：
按照算法采用的方法和思路給它們分類
隨機(jī)法：依賴于隨機(jī)數(shù)的統(tǒng)計(jì)特性。例子是快速排序
分治法：分解，將數(shù)據(jù)分解為更小，更容易管理的部分。求解，對(duì)每個(gè)分解出的部分進(jìn)行處理。合并，將每部分處理的結(jié)果合并。例子是歸并排序
動(dòng)態(tài)規(guī)劃：與分治法類似，但子問(wèn)題之間并不是獨(dú)立的，可能是有關(guān)系的，這本書里面沒(méi)有這個(gè)例子
貪心法：在求解問(wèn)題時(shí)總能做出在當(dāng)前的最佳選擇。不是從整體最優(yōu)上考慮，而僅僅是在某種意義上的局部最優(yōu)解。例子是霍夫曼編碼
近似法：并不計(jì)算出最優(yōu)解，只計(jì)算出“差不多好”的解。解決那些計(jì)算成本很高但又不能放棄的問(wèn)題。例子是推銷員問(wèn)題
第二章 指針操作
指針：一個(gè)指針其實(shí)只是一個(gè)變量，它存儲(chǔ)數(shù)據(jù)在內(nèi)存中的地址。
結(jié)構(gòu)：結(jié)構(gòu)不允許包含自身的實(shí)例，但可以包含指向自身實(shí)例的指針
數(shù)組：a[i] = * (a+i)
范型指針（void指針）：void * 可以通過(guò)void指針存儲(chǔ)和檢索任何類型的數(shù)據(jù)
指針的類型轉(zhuǎn)換：a為A類型,b為B類型; a=(A * )b;
函數(shù)指針：函數(shù)名和用括號(hào)括起來(lái)，指向可執(zhí)行代碼段的信息塊 int( match)(int * value1,int * value2)
這一章就是介紹了指針的一些基礎(chǔ)知識(shí)
第三章 遞歸
基本遞歸
用階乘來(lái)介紹基本遞歸：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個(gè)區(qū)域組成：
代碼段：程序運(yùn)行時(shí)所執(zhí)行的機(jī)器指令
靜態(tài)數(shù)據(jù)區(qū)：在程序生命周期內(nèi)一直持久的數(shù)據(jù)，比如全局變量和靜態(tài)局部變量。
堆：程序運(yùn)行時(shí)動(dòng)態(tài)分配的存儲(chǔ)空間
棧：函數(shù)調(diào)用的信息。
尾遞歸
一個(gè)函數(shù)中所有遞歸形式的調(diào)用都出現(xiàn)在函數(shù)的末尾
遞歸調(diào)用是整個(gè)函數(shù)體中最后執(zhí)行的語(yǔ)句且它的返回值不屬于表達(dá)式的一部分
同樣用階乘來(lái)介紹尾遞歸：F(n,a)=F(n-1,na) 當(dāng)n>1; F(n,a)=a 當(dāng)n=0,n=1;
就是多了第二個(gè)參數(shù)a（默認(rèn)為1）,a記錄當(dāng)前值，維護(hù)遞歸層次的深度，避免了每次還需要將返回值再乘以n
問(wèn)與答：
1.歸并排序用遞歸的實(shí)現(xiàn)：
T(n)=2T(n/2)+n 當(dāng)n>1; T(n)=1 當(dāng)n=1;
要注意的是判斷條件要對(duì)
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)無(wú)法滿足時(shí)，會(huì)出現(xiàn)什么情況？
棧的增長(zhǎng)會(huì)超過(guò)可接受的值，程序會(huì)因?yàn)闂Ｒ绯龆K止運(yùn)行
...
第四章 算法分析
最壞情況分析：告訴我們算法性能的上限，而最好情況都是1次。
講了下O表示法的簡(jiǎn)單規(guī)則：常數(shù)項(xiàng)為O(1)，忽略常量因子，兩個(gè)運(yùn)行時(shí)間函數(shù)加法運(yùn)算取最大值，乘法結(jié)果不變
因?yàn)樵诤瘮?shù)運(yùn)算次數(shù)逐漸變大的時(shí)候，這些條件占據(jù)整個(gè)運(yùn)行時(shí)間的比例會(huì)越來(lái)越大，直至小的條件占比幾乎被忽略
然后介紹了如何計(jì)算算法復(fù)雜度：按照算法的步驟歸納成公式，最后用O表示法簡(jiǎn)化
然后分析了下插入排序，得出插入排序的算法復(fù)雜度為O(n2)
問(wèn)與答就是幾個(gè)計(jì)算時(shí)間復(fù)雜度的題
相關(guān)擴(kuò)展：
表示算法性能的其他表示法：（不僅僅只有大O表示法）
O表示法：描述的是在一定條件約束下函數(shù)的上限值
Ω表示法：描述的是在一定的條件約束下函數(shù)的下限值
θ表示法：描述函數(shù)的區(qū)間值
W表示法：類似Ω表示法，只是更精確
NP完全問(wèn)題：
沒(méi)有已知的求解多項(xiàng)式時(shí)間的算法，但也無(wú)法證明此多項(xiàng)式不存在，這類問(wèn)題稱為NP完全問(wèn)題。
很多有用且看似困難的問(wèn)題都?xì)w為此類，一直是計(jì)算機(jī)科學(xué)領(lǐng)域令人困惑和煩惱的問(wèn)題。
第五章 鏈表
單鏈表：
簡(jiǎn)稱為鏈表，由各個(gè)元素之間通過(guò)一個(gè)指針彼此鏈接起來(lái)而組成。每個(gè)元素包含數(shù)據(jù)成員、next指針，指向后面的元素。
單鏈表只能從頭到尾以一個(gè)方向進(jìn)行遍歷。
list文件給出了單鏈表的抽象數(shù)據(jù)類型定義
list文件貼出來(lái)看一下，作者整本書都是這樣的風(fēng)格，用代碼來(lái)講解。我認(rèn)為比較重要的就貼出來(lái)，其他的還是下載源碼查看吧，太多了。
不過(guò)如果有需要的話可以留言，我可以全部貼出來(lái)
// 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;
//初始化一個(gè)鏈表 O(1)
void list_init(List *list,void (*destroy)(void *data));
//銷毀鏈表 O(n)
void list_destroy(List *list);
//在鏈表list的element后面插入一個(gè)新元素,如果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中元素的個(gè)數(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的下一個(gè)結(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>
//初始化一個(gè)鏈表
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;
//每個(gè)元素都調(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個(gè)字節(jié)用0替換并返回list
memset(list,0,sizeof(List));
return;
}
//在鏈表list的element后面插入一個(gè)新元素
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指針指向它之后的那個(gè)元素，
//然后將新元素位置之前的結(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)前一個(gè)元素的next指針指向目標(biāo)節(jié)點(diǎn)下一個(gè)元素
*data = list->head->data;
old_element = list->head;
list->head = list->head->next;
//當(dāng)移除操作使整個(gè)鏈表稱為空鏈表
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)用：管理頁(yè)幀
frames文件是使用鏈表管理頁(yè)幀的例子
在一些支持虛擬內(nèi)存的系統(tǒng)中，用鏈表來(lái)管理頁(yè)幀是非常好的辦法，因?yàn)轫?yè)幀的分配將涉及頻繁的插入和刪除操作，而且這些操作都發(fā)生在鏈表頭
虛擬內(nèi)存：一種地址空間的映射機(jī)制，它允許進(jìn)程不必完全加載到物理內(nèi)存（系統(tǒng)的實(shí)際內(nèi)存）中也可以運(yùn)行。優(yōu)點(diǎn)是進(jìn)程可以使用比物理內(nèi)存大得多的空間，多個(gè)進(jìn)程能夠共享系統(tǒng)的內(nèi)存以并發(fā)的方式執(zhí)行。
而運(yùn)行虛擬內(nèi)存下的進(jìn)程需要處理虛擬地址，必須由操作系統(tǒng)做轉(zhuǎn)換，每一個(gè)進(jìn)程都有自己的頁(yè)表，將虛擬地址空間中的頁(yè)映射到物理內(nèi)存中的頁(yè)幀上。
對(duì)于開(kāi)發(fā)來(lái)說(shuō)可能用處不大，不過(guò)可以更好的理解鏈表的使用
雙向鏈表：
鏈表元素之間由兩個(gè)指針鏈接。每個(gè)元素包含數(shù)據(jù)成員、next指針、prev指針，指向前驅(qū)元素。
雙向鏈表書上沒(méi)有例子與應(yīng)用，直接看看源碼dlist文件吧
循環(huán)鏈表：
有尾部元素的鏈表，可以是單向的或雙向的，源碼clist文件
循環(huán)鏈表的應(yīng)用：第二次機(jī)會(huì)頁(yè)面置換法
第二次機(jī)會(huì)頁(yè)面置換法，也稱時(shí)鐘算法，是最近最少使用算法（也稱為L(zhǎng)RU頁(yè)面替換法，Least Recenty Used）
跟隨上面,是系統(tǒng)管理內(nèi)存頁(yè)幀分配的例子，解決空閑頁(yè)面鏈表為空時(shí)，系統(tǒng)為其分配新的頁(yè)幀。
大概就是當(dāng)需要某個(gè)頁(yè)幀時(shí)，系統(tǒng)遍歷鏈表，找到上次遍歷沒(méi)有被系統(tǒng)訪問(wèn)過(guò)的頁(yè)面，因?yàn)樽詈笠氐奖闅v開(kāi)始的頁(yè)面，所以循環(huán)鏈表最適合。
作者花了一整頁(yè)篇幅來(lái)講解，但我認(rèn)為對(duì)于開(kāi)發(fā)來(lái)說(shuō)可能用處不大，建議看看源碼page文件即可
問(wèn)與答：
1、數(shù)組與鏈表的使用情況：
進(jìn)行頻繁的插入和刪除時(shí)，鏈表更適合，而數(shù)組的元素是連續(xù)排列的，更適合通過(guò)索引查找
2、鏈表的增刪改查與數(shù)組相比有何差異？
的確，鏈表除了銷毀操作之外，其他操作都是O(1)，但是都需要一個(gè)想要操作的元素指針，而得到該指針的代價(jià)是很高的，需要遍歷鏈表
插入本身復(fù)雜度是O(1)，但是訪問(wèn)特定位置的元素復(fù)雜度是O(n)
3、為什么單鏈表和循環(huán)鏈表不能指定移除該元素，而是該元素下一個(gè)元素？
因?yàn)闆](méi)有指向前驅(qū)結(jié)點(diǎn)的指針，所以找不到前驅(qū)結(jié)點(diǎn)來(lái)指向被移除元素的后繼結(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中壓入一個(gè)元素 O(1)
int stack_push(Stack *stack,const void *data);
//從stack中彈出一個(gè)元素 O(1)
int stack_pop(Stack *stack,void **data);
//皆為 O(1)
//獲取棧頂部的元素
void *stack_peek(const Stack *stack);
//獲取棧中元素個(gè)數(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中壓入一個(gè)元素 O(1)
int stack_push(Stack *stack,const void *data)
{
return list_ins_next(stack, NULL, data);
}
//從stack中彈出一個(gè)元素 O(1)
int stack_pop(Stack *stack,void **data)
{
return list_rem_next(stack, NULL, data);
}
隊(duì)列
先進(jìn)先出，排隊(duì)
作者也是使用鏈表來(lái)實(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ū)動(dòng)來(lái)舉例隊(duì)列的作用，因?yàn)橛?jì)算機(jī)的應(yīng)用主要遵循的是實(shí)時(shí)發(fā)生的順序來(lái)執(zhí)行，需要有序地存儲(chǔ)和管理事件。
當(dāng)告知應(yīng)用程序有事件將進(jìn)行處理時(shí)，將一個(gè)事件入隊(duì)，當(dāng)應(yīng)用程序認(rèn)為是時(shí)候處理一個(gè)事件時(shí)，將一個(gè)事件出隊(duì)
問(wèn)與答：
1、從一個(gè)隊(duì)列中刪除一些元素，剩下的按順序留在隊(duì)列中，用隊(duì)列和鏈表如何處理
隊(duì)列：從頭開(kāi)始出隊(duì)，不刪除的出隊(duì)后再入隊(duì)
鏈表：遍歷，遍歷到元素后用list_rem_next函數(shù)刪除即可
第七章 集合
集合是不同對(duì)象的無(wú)序聚集。成員是無(wú)序的，每個(gè)成員都只在集合中出現(xiàn)一次
是數(shù)學(xué)中集合的概念，有子集，并集，空集等等，操作也是交集，并集，差集等
作者也是使用鏈表來(lái)實(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)化求解問(wèn)題
每次開(kāi)始都在subsets中找出能夠覆蓋到members的最大交集，然后加到covering中，所以有可能解會(huì)有小小的多余，是一種近似最優(yōu)解
int cover(Set *members,Set *subsets,Set *covering);
members為S，subsets為P中的子集如A1， covering為C
第八章 哈希表
散列表，通過(guò)一個(gè)哈希函數(shù)，在所有可能的鍵與槽位之間建立一張映射表。
1 鏈?zhǔn)焦１?/h6>
由一組鏈表構(gòu)成，每個(gè)鏈表都可以看做一個(gè)桶，所有的元素通過(guò)散列的方式放到具體的不同的桶中
#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ù)，會(huì)將鍵散列
//match判斷兩個(gè)鍵是否匹配
//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));
//銷毀，刪除每個(gè)桶中的元素
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;
}
//銷毀，刪除每個(gè)桶中的元素
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;
}
解決沖突
兩個(gè)鍵散列到一個(gè)相同的槽位時(shí)，兩個(gè)鍵之間會(huì)產(chǎn)生沖突
鏈?zhǔn)焦１砭椭苯訉⒃胤湃胪爸?，但桶有可能越?lái)越大
一個(gè)好的哈希函數(shù)會(huì)盡可能做到均勻散列
h(k) = m 一般k為整型
轉(zhuǎn)換鍵的方法：
取余法：計(jì)算k除以m的所得到的余數(shù)，將k映射到m槽位
h(k)=k mod m
乘法：將整型鍵k乘以一個(gè)常數(shù)A(0<A<1)，取結(jié)果的小數(shù)部分，然后乘以m取結(jié)果的整數(shù)部分。
鏈?zhǔn)焦１淼膽?yīng)用：符號(hào)表
在編譯器中用來(lái)維護(hù)程序中出現(xiàn)的符號(hào)信息。
編譯器在翻譯時(shí)，為了能夠更加有效地管理程序中的符號(hào)信息，使用符號(hào)表
2 開(kāi)地址哈希表
元素存放在表本身，用于依賴于固定大小表的應(yīng)用
#ifndef ohtbl_h
#define ohtbl_h
#include <stdio.h>
typedef struct OHTbl_{
int positions;//哈希表中分配的槽位數(shù)目
void *vacated;//曾經(jīng)刪除的一個(gè)元素
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;//存儲(chǔ)元素的數(shù)組
}OHTbl;
//positions為槽位的個(gè)數(shù)
//h1，h2指向哈希函數(shù)，會(huì)將鍵散列
//match判斷兩個(gè)鍵是否匹配
//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;
}
解決沖突
探查這個(gè)表，直到找到一個(gè)可以放置元素的槽
探查槽位的哈希函數(shù)定義為：h(k,i)=x
k是鍵，i是探查的次數(shù)，x是得到的哈希編碼
線性探查
用哈希函數(shù)定位到某一數(shù)值后探查表中連續(xù)的槽位
h(k,i) = (h(k)+i) mod m
雙散列
通過(guò)計(jì)算兩個(gè)輔助哈希函數(shù)哈希編碼的和來(lái)得到哈希編碼
h(k,i) = (h1(k)+ih2(k)) mod m
h1與h2為兩個(gè)輔助哈希函數(shù)，能夠在表中探查并產(chǎn)生較好的元素分布
問(wèn)與答：
1、鏈?zhǔn)焦１淼淖顗男阅?？如何保證不會(huì)發(fā)生？
所有元素全部散列在一個(gè)桶中時(shí)，性能最差
選擇一個(gè)好的哈希函數(shù)??
2、開(kāi)地址哈希表的最壞性能？如何保證不會(huì)發(fā)生？
表已經(jīng)滿了，而且要查找的元素不在此表中，性能最差
不要讓元素的個(gè)數(shù)超過(guò)表容量的80%
