推荐看👉 OI Wiki

数据结构：数据结构是为算法服务而设计的。

算法：充分且合理利用计算机资源处理数据而诞生。

数据结构部分

一. 数据结构的存储方式有两种

1.顺序存储(数组,内存连续)

2.链式存储(链表,内存不连续,依靠节点的指针指向下一个节点)

常见的数据结构有：

数组(array),链表(LinkedList),

双向链表(doubly-linked-list),

树：

二叉树(Binary tree),

二叉查找树(Binary Search Tree),平衡二叉树(AVL),

2-3-4树

红黑树(Red Black Tree), B树, B+树, B*树, AA-树

treap树, k-d树, 伸展树(Splay Tree)

最小生成树(Minimum Spanning Tree)

图(graph),

栈(stack), 堆(heap),队列(queue),

散列表(hash), 位图(bitmap),

字典(map)

二常见数据结构实现

1.链表

链表(LinkedList)

避免数组插入和删除的线性开销,我们需要允许表可以不连续存储,防止数据大量移动

链表的设计

设计成一个链表节点至少包含两部分：

数据部和指针部

数据部为我们要存储的数据,指针部为指向下一个链表节点

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

单向链表

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

例子

/*1ist.h*/
#ifndef LIST_H 
#define LIST_H
#include <stdlib.h>
/* Define a structure for linked list elements. */ 
typedef struct ListElnt_ {
    void *data:
	struct ListElnt *next;
} ListElmt;

/* Define a structure for linked lists, */ 
typedef struct List_ {
    int size:
	int (*match()const void *keyl, const void *key2);
    void (*destroy)(void *data);
	ListElmt *head;
    ListElmt *tail;
} List;

/* Public Interface*/
void list_init(List *list, void (*destroy)(void *data)); // 初始化一个链表以便于进行后续操作
void list_destroy(List *list);	
int list_ins_next(List *list, ListEInt *element, const void *data); 
int list_rem_next(List *list, ListElnt *element, void **data); 

#define list_size(list()(list)->size)
#define list_head(list()(list)->head) 
#define list_tail(1ist()(1ist)->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.c*/
#include <stdlib.h>
#include "list.h"
/*list init */
void list_init(List *list, void (*destroy)(void *data)) {
	/* Initialize the list. */
	list->size = 0;
	list->destroy = destroy; 
    list->head = NULL; 
    list->tail = NULL;
}

/*listdestroy*/
void list_destroy(List *list) {
	void* data;
    /* Remove each element.*/
    while (list_size(list) > 0) {
        if (0 == list_rem_next(list, NULL, (void **)&data) && NULL != list->destroy){
    /* Call a user-defined function to free dynanically allocated data, */ 
        	list->destroy(data);
        }
    }
	/* No operations are allowed now, but clear the structure as a precaution. */ 
    memset(list, 0, sizeof(List));
}

/*list_ins_next*/
int list_ins_next(List *list, ListElmt *element,const void *data) { 
    ListElmt*	new_element;
    /*Allocate storage for the element. */
    if(NULL == (new_element-(ListElmt*)malloc(sizeof(ListElmt))))
    	return -1;
    /* Insert the element into the list. */ 
    new_element->data = (void *)data; 
    if (element == NULL) {
    	/* Handle insertion at the head of the list. */ 
        if (list_size(list)==0)
        	list->tail = new _element;
        new_element->next = list->head; 
        list->head=new_element; 
    }
    else {
    	/* Handle insertion somewhere other than at the head. */ 
        if(element->next == NULL)
        list->tail = new_element;
        new_element->next = element->next;
        element->next = new_element; 
    }
    /*Adjust the size of the list to account for the inserted element. */ 
    list->size++;
    return 0;
}

/* list_rem_next */
int list_rem_next(List *list, ListElmt *element, void **data) {
    ListElmt	*old_element;
    
    /*Do not allow removal from an empty list.*/
    if (list_size(list) == 0)
		return -1;
    
	/* Remove the element from the list. */ 
    if (element == NULL) {
        /* Handle removal from the head of the list, */
        *data = list->head->data;
        old_element = list->head; 
        list->head = list->head->next;
        if (list_size(list) == 1) 
            list->tail = NULL;
    }
    else {
        /* Handle removal from somewhere other than the head. */
        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 the storage allocated by the abstract datatype. */ 
    free(old_element);
    
    /*Adjust the size of the list to account for the removed element.*/ 
    1ist—>size--; 
    return 0; 
}

双向链表

typedef struct DListEImt_ {
    void *data;
    struct DListEImt_ *prev;
    struct DListEImt_ *next;
} DListEImt;

例子

/*dlist h */
#ifndef DLIST_H
#define DLIST_H
#include <stdlib.h>

/* Define a structure for doubly-linked list elements. */
typedef struct DListEImt_ {
    void *data;
    struct DListEImt_ *prev;
    struct DListEImt_ *next;
} DListEImt;

/*Define structure for doubly-linked lists. */
typedef struct Dlist_ {
    int size;
    int (*match)(const void*key1, const void *key2);
    void (*destroy)(void *data);
    DListEImt *head;
    DListEImt *tail;
}DList;


/* Public Interface */
void dlist_init(DList *list, void (*destroy)(void *data));
void dlist_destroy(DList *list);
int dlist_ins_next(DList *list, DListEImt *element const void *data);
int dlist_ins_prev(DList *list, DListEImt *element, const void *data);
int dlist_remove(DList *list, DListEImt *element, void **data);
#define dlist_size(list)	((list)->size)
#define dlist_tail(list)	((list)->tail)
#define dlist_is_head(element)	((element)->prev == NULL ? 1: 0)
#define dlist_is_tail(element)	((element)->next == NULL ? 1: 0)
#define dlist_data(element)	((element)->data)
#define diist_next(element)	((element)->next)
#define dlist_prev(element)	(element )->prev)

/*d]主st.C*/
#include <stdlib.h>
#include <string.h>
#include dlist . h
/* dlist init */
void dlist_init(DList *list, void (*destroy)(void *data)) {
    /* Initialize the list. */
    list->size = 0;
    list->destory = destroy;
    list->head = NULL;
    list->tail = NULL;
}

/* dlist_destory */
void dlist_destroy (DList *list) {
    void *data
    /* Remove each element. */
    while (dlist_size(list) > 0) {
        if (dlist_remove(list, dlist_tail(list), (void**)adata)==0
           && list->destory != NULL) {
            /* Call a user-defined function to free dynamically allocated data. */
            list->destroy(data);
        }
    }
        
    /* No operations are allowed now, but clear the structure as a precaution. */
    memset(list, 0, sizeof(DList));
}

int dlist_ins_next(DList *list, DListElmt *element, const void *data) {
    DListElmt *new_element;
    
    /* Do not allow a NUll element unless the list is empty. */
    if (element == NULL && dlist_size(list) != 0)
        return -1;
    
    /* Allocate storage for the element. */
    if ((new_element = (DListElmt *)malloc(sizeof(DListElmt)))== NULL)
    	return -1:
    /* Insert the new_element into the list. */
    new_element->data = (void *)data;
    
    if (dlist size(list) == 0) {
        /* Handle insertion when the list is empty. */
        list->head = new_element;
        list->head->prev = NULL;
        list->head->next = NULL;
        list->tail = new_element;
    }
    else {
         /* Handle insertion when the list is not empty. */
        new_element->next = element->next;
        new_element->prev = element;
        if(element->next == NULL)
            list->tail = new_element;
        else
            element->next->prev = new_element;
        element->next = new_element;
    }
   
    /* Adjust the size of the list to account for the inserted element. */
    list->size++;
    return 0;
}

/* dlist ins_ prev */
int dlist_ins_prev(DList *list, DListElmt *element, const void *data) {
    DListElmt *new_element;
        
	/* Do not allow a NULL element unless the list is empty. */
    if (element == NULL && dlist_size(list) != 0)
    	return -1;
    
    /* Allocate storage to be managed by the abstract datatype. */
    if(new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
    	return - 1;
    
    /* Insert the new_element into the list */
    new_element->data =(void *)data;
    if (dlist_size(list)== 0) {
        /* Handle insertion when the list is empty. */
        list->head = new_element;
        list->head->prev = NULL;
        list->head->next = NULL;
        list->tail = new_element;
    }
    else {
        /* Handle inserton when the list is not empty. */
        new_element = element;
        new_element->prev = element->prev;
        
        if (element->prev == NULL)
        	list->head = new_element;
        else
        	element->prev->next = new_element;
        element->prev = new_element;
    }
    
    /* Adjust the size of the list to account for the new_element. */
    list->size++;
    return 0;
}

/* d1ist_remove */
int dlist_remove(DList *list, DListElmt. *element, void s*data) {
    /* Do not allow a NULL element or removal from an empty list. */
    if (element == NULL || dlist_size(list) == 0)
    	return -1:
    /* remove the element from the list. */
    *data s element ->data;
        
    if (element == list->head) {
        /* Handle removal from the head of the list. */
    	list->head = element->next;
        
        if (list->head == NULL)
			list->tail = NULL;
        else
        	element->next->prev = NULL;
    }
    else {
        /* Handle removal from other than the head of the list. */
        element->prev->next = element->next;

        if (element->next == NULL)
            list->tail = elenent->prev;
        else
            element->next->prev = element->prev;
    }

    /* Free the storage allocated by the abstract datatype. */
    free(element);
    
    /* Adjust the size of the list to account for the removed element */
    list->size--;
    return 0;
}

循环链表

typedef struct ClistElmt_ {
    void *data;
    struct ClistElmt_ *next;
}ClistElmt;

例子

/* clist .h */
#ifndef CLIST_H 
#define CLIST_H 
#include <stdlib.h>
/* Define a structure for circular list elements .*/
typedef struct CListElmt {
    void * data;
    struct CListElmt * next;
} CListElmt;

/* Definea structure for circular lists .*/ 
typedef struct CList_ {
    int size;
    int (*match)(constvoid * key1, const void * key2);
    void (*destroy)(void* data);
    CListElmt *head;
}CList;

/* Public Interface */ 
void clist_init(CList* list,void ( *destroy)( void* data));
void clist_destroy(CList* list);
int clist_ins_next (CList* list,CListElmt * element,const void *data);
int clist_rem_next (CList* list,CListElmt * element,void **data);
#defineclist _size(list)((list)->size)
#defineclist head (list)(()->head)
#defineclist data (element)((element)->data)
#defineclist _next(element)((element)->next)

#endif

/* clist .c */
#include <stdlib.h >
#include <string.h>
#include "clist.h"

/* clist init */
void clist_init(CList* list,void ( *destroy)( void* data)) {
    /* Initialize the list .*/ 
    list->size = 0;
    list->destroy = destroy ;
    list->head = NULL;
}

/* clist destroy */ 
void clist_destroy (CList* list) {
    void *data;
    /* Remove each element .*/ 
    while (clist_size(list) > 0) {
        if (clist_remnext (list,list->head, (void **)&data)== 0
            && list->destroy != NULL) {
            /* Call a user-defined function to free dynamically allocated data .*/ 
            list->destroy(data);
        }
    }
        
    /* No operations are allowed now ,but clear the structure as a precaution .*/
	memset (list, 0, sizeof(CList));
}
  
    /* clist ins next */
int clist_insnext (CList* list,CListElmt * element,const void * data) {
    CListElmt* new_element;
    /*Allocate storage for the element .*/
    if ((new_element = (CListElmt* )malloc(sizeof(CListElmt))) == NULL)
    	return -1;
    
    /* Insert the element into the list .*/ 
    new_element->data = (void *)data;
    if (clist_size(list) == 0) {
        /* Handle insertion when the list empty .*/
        new_element->next = new_element;
        list->head = new_element;
    }  
    else {
        /* Handle insertion when the list is not empty .*/
        new_element->next = element->next;
        element->next = new_element;
    }
    /* Adjust the size of the list to account for the inserted element .*/ 
    list->size++;
    return 0 ;
}


/* clist_rem_next */
int clist_rem_next(CList* list, CListElmt *element,void **data) {
    CListElmt * old_element;
    
    /* Do not allow removal from an empty list . */
    if (clist_size(list) == 0)
    	return -1;
    
    /* Remove the element from the list . */
    *data = element->next->data;
    if (element->next == element) {
        /* Handle removing the last element . */
        old_element = element->next;
        list->headNULL;
    }    
    else {
        /* Handle removing other than the last element . */
        old_element = element->next;
        element->next = element->next->next;
        if (old_element == clist_head(list))
        	list->head = old_element->next;
    }
        
    /* Free the storage allocated by the abstract datatype . */
    free(old_element);
    
    /* Adjust the size of the list to account for the removed element . */
    1ist->size--;
    return 0;
}

2.栈和队列

栈和队列是另一种数据的存储方式。

用于检索数据的常用数据结构称为栈,栈的检索顺序和存储元素相反

栈: 按照后进先出的顺序存储和检索数据的高效数据结构, 它检索数据的顺序和存储数据相反。

队列：按照先进先出的顺序存储和检索数据的高效数据结构, 它按照存储元素的顺序检索元素。

栈例子

/* stack .h*/
#ifndef STACK_H 
#define STACK_H 
#include <stdlib.h>
#include "list.h"
/* Implement stacks as linked lists .*/ 
typedef List Stack;
/*Public Interface */ 
#define stack_init list_init 
#define stack_destroy list_destroy
int stack_push(Stack* stack,const void * data);
int stack_pop(Stack* stack,void ** data);
#define stack_peek(stack)	((stack)->head == NULL ? NULL : (stack)->head->data)
#define stack_size list_size 
#endif

/* Stack.c */
#include <stdlib.h>

#include "list.h"
#include "Stack.h"

/* stack_push */
int stack_push(Stack* stack,const void * data) {
    /* push the data onto the stack. */
	return list_ins_next(stack, NULL, data);
}

/* stack_pop */
int stack_pop(Stack* stack,void ** data) {
    /* Pop the data off the stack. */
	return list_rem_next(stack, NULL, data);
}

队列例子

/* queue . h */ 
#ifndef QUEUE_H 
#define QUEUE_H 
#include <stdlib.h> 
#include "list.h" 
/* Implement queues as linked lists . */ 
typedef List Queue ; 
/* Public Interface */
#define queue_init list_init 
#define queue_destroy list_destroy 
int queue_enqueue (Queue * queue, const void* data ); 
int queue_dequeue (Queue * queue, void **data);
#define queue_peek(queue()(queue)->head == NULL ? NULL : (queue)->head->data)
#define queue_size list_size 
#endif

/* queue.c */ 
#include <stdlib>h > 
#include "list.h" 
#include "queue.h" 

/* queue_enqueue */
int queue_enqueue (Queue* queue, const void* data) {
    /* Enqueue the data . */ 
    return list_ins_next(queue, list_tail(queue), data); 
}
	
/* queue_dequeue */
int queue_dequeue(Queue* queue, void** data) {
    /* Dequeue the data . */ 
    return list_rem_next(queue, NULL, data); 
}

队列示例：事件处理

遵循实时事件发生的顺序执行。

/* events.c */
#include <stdlib.h>
#include <string.h>
#include "event.h"
#include "events.h"
#include "queue.h"

/* receive_event */
int receive_event(Queue *events, const Event *event) {
    Event* new_event;
    
    /* Allocate space for the event. */
    if(NULL == (new_event = (Event*)(sizeof(Event))))
        return -1;
    
    /* Make a copy of the event and enqueue it. */
	memcpy(new_event, event, sizeof(Event));
    
    if(queue_enqueue(events, new_event) != 0)
        return -1;
    return 0;
}

/* process_event */
int process_event(Queue *events, int (*dispatch)(Event* event)) {
    Event* event;
    
    if(0 == queue_size(events))
        /* Return that there are no events to dispatch. */
		return -1;
    else {
        if(0 != queue_deququq(events, (void **)&event))
            /* Return that an event could not be retrived. */
    		return -1;
        else {
            /* Call a user-defined fintion to dispatch the event. */
        	dispatch(event);
        	free(event);
        }
    }
    return 0;
}

3.集合

集合定义：集合是相关联成员的无序组合,且每个成员在集合中只出现一次

例子

/* set.h */
#ifndef SET_H
#define SET_H
#include <Stdlib.h>
#include "list.h"

/* Implement sets as linked lists. */
typedef List Set;

/* Public Interface */
void set_init(Set *set, int (*match)(const void *keyl, const void *key2), void (*destory)(void *data));
int set_insert(Set *set, const void *data);
int set_remcve(Set *set, void **data);
int set_union(Set *setu, const Set *setl, const Set *set2);
int set_intersection(Set*seti, const Set *seta, const Set *set2);
int set_difference(Set *setd, const Set *setl, const Set *set2);
int set_is_memeber(const Set *set, const void *data);
int set_is_subset(const Set *setl, const Set *set2);
int set_is_equal(const Set *setl, const Set *set2);

#define set_size(set()(set) osize)
#define set_destroy list_destroy
#endif

/* set.c */
#include <Stdlib.h>
#include "list.h"
#include "set.h"

/* set_init */
void set_init(Set *set, int (*match)(const void *keyl, const void *key2), void (*destory)(void *data)) {
    /* Initialize the set. */
    list_init(set, destory);
    set->match = match;
}

/* set_insert */
int set_insert(Set *set, const void *data) {
    /* Do not allow the insertion of duplicates. */
    if (set_in_number(set, data))
        return 1;

    /* Insert the data. */
    return list_ins_tail(set, list_tail(set), data);
}

/* set_remove. */
int set_remove(Set* set, void **data) {
    ListE1mt *member, *prev;
    
    /* Find the member to remove.*/
    prev = NULL;
    for (member = list_head(set); member != NULL; member = list_next(member)) {
        if list_data(member)))
            break;
        prev = member;
    }
       
    /* Return if the member was not found.*/
    if (member == NULL)
        return -1 ;
    
    /* Remove the member. */
    return list_rem_next(set, prev, data);
}

/* set_union */
int set_unicn(Set *setu, const Set *setl, const Set *set2) {
    ListE1mt *member;
    void *data;
    
    /* Initialize the set for the union. */
    set_init(setu, set1->match, NULL);
    
    /* Insert the members of the first set. */
    for (member = list_head(setl); member != NULL; member = list_next(member)) {
        data = list_data(member);
        if (list_ins_next(setu, list_tail(setu), data) != 0) {
            set_destroy(setu);
            return -1;
        }
	}
    /* Insert the members of the second set. */
    for (member = list_head(set2); member != NULL; member = list_next(member)) {
        if (set_is_member(setl, list_data(member))) {
             /* Do not allow the insertion of duplicates. */ 				
            continue;
        }
        else {
            data = list_data(member);
            if (list_ins_next(setu, list_tail(setu), data) != 0) {
                set_destroy(setu);
                return -1;
            }
        }
    }
    return 0;
}
    
/* set_intersection */
int set_intersection(Set *seti, const Set *setl, const Set *set2) { 
    ListElmt *member;
    void *data;
    
    /* Initialize the set for the intersection. */ 
    set_init(set1, set1->match, NULL);
    
    /* Insert the members present in both sets- */ 
    for (member = list_head(set1); member != NULL; member = list_next(member)) {
        if (set_is_member(set2, list_data(member))) {
            data = list_data(member);
            if (list_ins_next(seti, list_tail(seti), data) != 0) {
                set_destroy(seti);
                return -1;
            }
		}
    }
    return 0;
}

/* set_difference */
int set_difference(Set *setd, const Set *seti, const Set *set2) { 
    ListElmt *member;
    void *data;

    /* Initialize the set for the difference. */
    $et_init(setd, set1-Mnatch, NULL);

    /* Insert the members from setl not in set2 */
    for (member = list_head(setl); member != NULL; member = list_next(member)) { 
        if (lset_is_member(set2, list_data(member))) { 
             data = list_data(member);
             if (list_ins_next(setd, list_tail(setd), data) != 0) { 
                set_destroy(setd);
                return -1;
             }
        }
    }
    return 0;
}


/* set_ls_member */
int set_is_member(const Set *set const void *data) { 
    ListElmt *member;
    /* Determine if the data is a member of the set. */ 
    for (member = list_head(set); member != NULL; member = list_next(member)) {
        if (set->match(dataj listdata(member))) 
            return 1;
    }
    return o;
}

/* set_is_subset */
int set_is_subset(const Set *setl, const Set *set2) {
    ListElmt	*member;
    /* Do a quick test to rule out some cases. */
    if (set_size(setl) > set_size(set2)) 
        return 0;
    
    /* Determine if setl is a subset of set2, */
    for (member = list_head(set1); member != NULL; member = list_next(member)) {
        if(!list_is_member(set2, list_data(member)))
            return 0;
    }
    	
	return 1;
}

/* setis_equal */
int set_is_equal(const Set *setl, const Set *set2) {
    /* Do a quick test to rule out some cases. */
    if (set_size(setl) != set_size(set2))
        return 0;
    /* Sets of the same size are equal if they are subsets, */
    return set_is_subset(set1, set2);
}

Set示例：集合覆盖

集合覆盖是一种优化求解问题, 对很多组合数学和资源选择问题给出了漂亮的抽象模型

/* cover,c */
#include <stdlib.h>
#include "cover.h”
#include "list'h"
#include "set.h"
/* cover */
int cover(Set *members> Set 率subsets, Set *covering) {
   Set intersection;
   KSet *subset;
   ListElflit *member,
              *max_member;
   void *data;
   int max_size;
    
   /* Initialize the covering» */
   set_init(covering, subsets->match, NULL);
    
   /* Continue while there are noncovered members and candidate subsets. */ 
    while (set_size(members) > 0 && set_size(subset) > 0) {
       
        /* Find the subset that covers the most members.*/
        max_size = 0;
        for (member = list_head(subsets); member != NULL;
                    member = list_next(member)) { 
           if (set-intersectionC(&intersection, &((KSet *)list_data(member))->set, members) != 0) {
              return -1;
           }
           if (set_size(&inteisection) > max_size) {
              max_member = member;
              max_size = set_size(&intersection);
           }
           set_destroy(&intersection);
        }
        /* A covering is not possible if there was no intersection♦ */
        if (max_size == 0)
           return 1;

        /* Insert the selected subset into the covering» */
        subset = (KSet *)list_data(max_nember);

        if (set_insert(coverings, subset) != 0)
           return -1;

        /* Remove each covered member -from the set of noncovered members. */
        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->destory != NULL)
                members->destory(data);
        }

        /* Remove the subset from the set of cnadidate subsets. */
		if(set_remove(subsets, (void**)&subset) != 0)
    		return -1;
    }
    
    /* No covering is possible if there are still noncoverd member */
	if(set_size(members) > 0)
        return -1;
    
    return 0;
}

4.哈希表

哈希表是一种最有效的检索方法：散列。

从根本上来说,一个哈希表包含一个数组, 通过特殊的索引值(键)来访问数组中的元素,哈希表的主要思想是通过一个哈希函数,在所有可能的键与槽位之间建立一张映射表。哈希函数每次接受一个键将返回与键相对应的哈希编码或哈希值。键的数据类型可能多种多样,但哈希值的类型只能是整型。

链式哈希表

将数据存储在 桶 (bucket)中的哈希表。每个 “桶” 都是都是一个链表; 且链表的容量能够随着冲突的增加而增大。

解决哈希表冲突

如果想插入表中的元素数量远大于桶数量,那么即使是在一个均匀散列过的程中,表的性能会迅速降低。这种情况下桶会变得越来越深。因此我们要注意一个哈希表的负载因子。

其定义为：

α = n/m

n为表中的元素数量,m是桶中的数量(数组元素数量)。

在均匀散列情况下,链式哈希表的负载因子告诉我们表中桶能装元素的最大值

选择哈希函数

这是哈希算法的核心问题：将键随机地分散到表中,使冲突最小化。因此,选择一个能够实现这一过程的哈希函数尤为重要。

其定义为：

h(k) = x

k为要被映射的值,h()为哈希函数,x为哈希表的位置

例子

/* chtbl.h */
#ifndef CHTBL_H
#define CHTBL_H

#include <stdlib.h>

#include "list.h"

/* Define a structure for chained hash table. */
typedef struct CHTBL_ {
    int buckets;
    
    int (*h)(const void* key);
    int (*match)(const void* key1, const void *key2);
    
    int size;
    List* table;
} CHTbl;

/* Public interface */
int chtbl_init(CHTbl* htbl, int buckets, int (*h)(const void* key), int (*match)(const void* key1, const void *key2), void (*destory)(void* data));

void chtbl_destory(CHTbl *htbl);
  
int chtbl_insert(CHTbl *htbl, const void *data);

int chtbl_remove(CHTbl *htbl, void **data);

int chtbl_lookup(CHTbl *htbl, void **data);

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

#endif

/*chtbl.c*/
#include <stdlib.h>
#include <string.h>

#include "list.h"
#include "chtbl.h"

/* chtbl_init */
int chtbl_init(CHTbl* htbl, int buckets, int (*h)(const void* key), int (*match)(const void* key1, const void *key2), void (*destory)(void* data)) {
    int i;
    
   	/* Allocate space for the hash table.*/
    if ((htbl->table = (List *)malloc(buckets * sizeof(List))) == NULL) 	
    	return -1;

    /* Initialize the buckets. */
    htbl->buckets = buckets;
    for(i = 0; i < htbl->buckets; i++)
    	list_init(&htbl->table[i], destroy);
    
    /* Encapsulate the functions. */
    htbl->h = h
    htbl->match match;
    htbl->destroy = destroy;
    
    /* Initialize the number of elements in the table. */
    htbl->size = o;
    return 0;
}

/* chtbl_destroy */
void chtbl_destory(CHTbl *htbl) {   
    /* Destroy each bucket. */
    for (int i = O; i < htbl->buckets; i++) {
        list_destroy (&htbl ->tableßl) ;
    }
    	
    /*Free the storage allocated for the hash table. */
    free(htbl->table);
    
    /* No operations are allowed now, but clear the structure as a precaution.*/
    memset(htbl, 0, sizeof(CHTbl));

}

/* chtbl insert */
int chtbl_insert(CHTbl *htbl, const void *data) {
    void* temp;
    int bucket,
        retval;
    /* Do nothing if the data is already in the table. */
    temp = (void *)data;
    if(chtbl_lookup(htbl, &temp) == 0)
        return 1 ;
    
    /* Hash the key. */
    bucket = htbl->h(data) % htbl->buckets;

    /* Insert the data into the bucket. */
	if (0 == (retval = list_ins_next(&htbl->table[bucket], NULL, data)))
        htbl->size++;
    return retval; 
}

/* chtbl remove */
int chtb1_remove(CHTbl* htbl, void **data) {
    ListEImt*	element,
				*prev;
    int 		bucket;
    
    /* Hash the key. */
	bucket = htbl->h(*data) % htbl->buckets;
    
    /* Search fcy the data in the bucket. */
	prev = NULL;
    
    for (element = list_head(&htbl->table[bucket]); element != NULL; element = list_next(element)) {
		if (htbl->match(*data, list_data(element))) {
        	/* Remove the data from the bucket. */
            if(0 == list_rem_next(&htbl->table[bucket], prev, data)) {
                htbl->size--;
                return 0;
            }
        	else
                return -1;
        }
        prev = element;
    }
    
    /* Return that the data was not found. */
    return -1;
}

/* chtbl lookup */
int chtbl_lookup(CHTbl *htbl, void **data) {
    ListE1mt *element;
    int 	bucket;
    
    /* Hash the key.*/
    bucket = htbl->h(*data) % htbl->buckets;

    /* Search for the data in the bucket.*/
    for(element = list_head(&htbl->table[bucket]); element = list_next(eleemnt)) {
        if(htbl->match(*data, list_data(element))) {
            /* Pass back the data from the table. */
            *data = list_data(element);
            return 0;
        }
    }
    
    /* Return that the was not found. */ 
	return -1;
}

开地址哈希表

将数据存储在表本身中,而不是桶中的哈希表。它通过各种探查方法来避免冲突问题。

例子

/* ohtbl.h */
#ifndef OHTBL_H
#define OHTBL_H
#incluge<stdlib.h>

/*Define astructure for open-addressed hash tables.*/
typedef struct OHTbl_ {
    int 	positions; 
    void* 	vacateds

    int (*h1)(const void*key);
    int (*h2)(const void*key);
    int (*match)(const void*key1,const void*key2);
    int (*destroy)(void*data);

    int sizes;
    void **table;
}OHTbl;

/*Public Interface*/
int ohtbl_init(oHTbl*htbl,int positions,int{*hi)(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.c */
#include <stdlib.h>
#include <string.h>
#include "ohtbl.h"

/*Reserveasentinelmemoxy address for vacated elements.*/
static char vacated;

/*ohtb_linit*/
int ohtb_linit(oHTbl*htbl,int positions,int (*h1)(const void*key),int (*h2)(const void*key),int (*match)(const void*key1,const void*key2),void (*destroy)(voi*data)) {
    int i;
    
    /*Allocate space for the hash table.*/
    if ((htbl->table= (void**)malloc(positions*sizeof(void*)))==NULL)
		return -1;
    
    /*Initializeeachposition、*/
    htbl->positicns = pasitions;
    for (i=0; i< htbl->positions；i++)
        htbl->table[i] = NULL;
    
    /*Set the vacated member tothe sentinel memory address reserved for this,*/
    htbl->vacated= &vacated;
    
    /*Encapsulate the functions.*/
    htbl->h1 = h1;
    htbl->h2 = h2;
    htbl-match = match;
    htbl->destroy = destroy;
    
    /*Initialize the number of elements in the table.*/
    htbl->size = 0;
    return 0;
}

/*ohtbl_destroy*/
vold ohtbl_destroy(OHTbl*htbl) {
    int i;

    if(htbl->destroy != NULL) {
		/*Calla user-defined function to free dynamically allocated data.*/
        for(i = 0; i < htbl->positions; i++) {
            if(htbl->table[i] != NULL && htbl->table[i] != htbl->vacated)
            	htbl->destroy(htbl->table[i]); 
        }
    }
    
    /*Free the storage allocated for the hash table，*/
    free(htbl->table);
    
    /*No operations are allowed nowybut clear the structure asaprecautlon.*/
	memset(htbl, 0, sizeof(OHTbl));
}
               
/*ohtblinsert*/
int ohtb_linsert(OHTbl*htbl，constvoid *data) {
    void* temp;
	int position, i;
         
    /*Do not exceed the number of positions in the table.*/
    if (htbl->size == htbl->positions)
        return -1;

    /*Do nothing ifthe data is already in the table.*/
    temp= (void*)data;
    if (ohtbl_fookup(htbl, &temp) == 0)
        return 1;
    
    /*Use double hashing to hash the key.*/
    for (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) {
            /* Insert the data into the table.*/
            htbl->table[position] = (void*)data;
            htbl->size++;
            return 0
        }
    }
    
    /* Return that the hash funtions were selected incorrectly. */
	return -1;
}
	
/*ohtbl_remove */
int ohtbl_remove(OHTbl *htbl，void**data) {
    int position, i;
    
    /*Use touble hashingtohashthekey.*/
    for (i=0; i < htbl->positions; i++) {
        position = (htbl->h1(*data) + (i * htbl->h2(*data))) % htbl->positions;
    }

    if (htbl->table[position] == NULL) {
        /* Returnthat the data was not found，*/
        return -1；
    }
    else if (htbl->table[position]==htbl->vacated) {
        /*Seaxch beyond vacated pasitions.*/
        continue;
    }
    else if (htbl->match(htbl->table[position],*data)) {
        /* Pass back the data from the table，*/
        *data = htbl->table[position];
        htbl->table[positian] = htbl->vacated;
        htbl->size--;
        return 0; 
    }
    
    /*Return that the data wasnot found，*/
    return -1;
}

/* ohtbI_lookup */
int ohtbl_lcokup(const OHTbl *htbl, void **data) {
    int positiong, i;

    /* Use double hashing to hash the key.*/
    for (i = O; i < htbl->positions; i++) {
        positicn = (htb1->hz(*data) + (i * htb1->h2(*data))) % htb1->positions;

        if (htbl->table[position] == NULL) {
            /* Return that the data was not found.*/
            return -1;
        }
        else if(htbl->match(htbl->table[position], *data)) {
            /* Pass back the data from the table. */
            *data = htbl->table[positipon];
            return 0;
        }
    }
    
    /* Return that the data was not found. */
    return -1;
}

5.树

树的定义：

在计算机科学中，树由称之为节点的元素按照层次结构方式组织而成。层次最顶端为根(root)。与根相连的为子节点，通常子节点也有自己的子节点。二叉树是分支因子为2的树。二叉搜索树是专门用于查找的树。

二叉树

二叉树的一个节点包含三部分：一个数据部和两个左右指针部

节点二叉树

树的遍历算法

先序遍历：根(root)，左，右

中层遍历：左，根(root)，右

后序遍历：左，右，根(root)

层序遍历：根(root), 一层一层遍历到叶子

树的平衡

树的平衡是指对于给定数量的节点，保证树的高度尽可能短的过程。这意味着在结点加入下一层之前必须保证本层结点满额。也就是说树的叶子都在倒数两层，且倒数第二层叶子是满的，则称这棵树是平衡的。最后一层叶子结点靠左，则称这棵树是左平衡的。

左平衡二叉树

二叉树的接口定义：

/* bitree.h */
#ifndef BITREE_H
#define BITREE_H
#include <stdlib.h>

/* Define a structure for binary tree nodes.*/
typedef struct BiTreeNode_ {
    void *data;
    struct BiTreeNode *left;
    struct BiTreeNode_*right;
}BiTreeNode;

/* Defmne a structure for binary trees.*/
typedef struct BiTree_ {
    int size;
    int (*compare)(const void *key1, const void *key2);
    void (*destroy)(void *data);
    BiTreeNode *root;
}BiTree;

/* Public Interface */
void bitree_init(BiTree *tree, void (*destroy)(void *data));
void bitree_destroy(BiTree *tree);
int bitree_ins_left(BiTree *tree, BiTreeNode *node, const void *data);
int bitree_ins_right(BiTree *tree, BiTreeNode *node, const void *data);
void bitree_rem_left(BiTree *tree, BiTreeNode *node);
void bitree_rem_right(BiTree *tree,BiTreeNode *node);
int bitree_merge(BiTree *merge, BiTree *left,BiTree *right,const void *data);

#define bitree_size(tree)	 ((tree)->size)
#define bitree root(tree)	 ((tree)->root))
#define bitxee_is_eob(node)	 ((node) == NULL)
#define bitree_is_leaf(node) ((node)->left == NULL && (node)->right == NULL)
#define bitree_data(node) ((node)->data)
#define bitree left(node) ((node)->left)
#define bitree_right(node) ((node)->right)

#edif

/* bitree.c */
#include <stdlib.h>
#include <string.h>
#include "bitree.h"

/*bitree init*/
void bitree_init(BiTree *tree, void (*destroy)(void *data)) {
    /* Initialize the binary tree.*/
    tree->size = 0;
    tree->destroy = destroy;
    tree->root = NULL;
}

/* bitree_destroy*/
void bitree_destroy(BiTree *tree) {
    /* Remove all the nodes from the tree.*/
    bitree_rem_left(tree, NULL);
    /* No operations are aIlowed now, but clear the structure as a precaution. */
    memset(tree, 0, sizeof(BiTree);
}

/* bitree ins left */
int bitree_ins_left(BiTree *tree, BiTreeNode *node, const void *data) {
    BiTreeNode new_node, **position;

    /* Determine where to insert the node.*/
    if (node == NULL) {
        /* Allow insertion at the root only in an empty tree.*/
        if (bitree_size(tree) > 0)
            return -1;

        position = &tree->root;
    } else {
        /* Normally allow insertion only at the end of a branch.*/
        if (bitree_left(node) != NULL)
            return -1;

        position = &node->left;
    }

    /* Allocate storage for the node.*/
    if ((new_node = (BiTreeNode *)malloc(sizeof(BiTreeNcde))) == NULL)
        return -1;

    /* Insert the node into the tree.*/
    new_node->data = (void *)data;
    new_node->ieft = NULL;
    new_node->right = NULL;
    *position = new_node;

    /* Adjust the size of the tree to account for the inserted node.*/
    tree->size++;
    return 0;
}

/* bitree_ins_right */
int bitree_ins_right(BiTree *tree, BiTreeNode *node, const void *data) {
    BiTreeNode *new_node, **position;

    /* Determine where to insert the node.*/
    if (node == NULL) {
        /* Allow insertion at the root only in an empty tree.*/
        if (bitree_size(tree) > 0)
            return -1;

        position = &tree->root;
    } else {
        /* Normally allow insertion only at the end of a branch. */
        if (bitree_right(node) != NULL)
            return -1;

        position = &node->right;
    }

    /* Allocate storage for the node.*/
    if ((new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))) == NULL)
        return -1;

    /* Insert the node into the tree.*/
    new_node->data = (void *)data;
    new_node->left = NULL;
    new_node->right = NULL;
    *position = new_node;

    /* Adjust the size of the tree to account for the inserted node.*/
    tree->size++;
    return 0;
}

/* bitree_rem_left */
void bitree_rem_left(BiTree *tree, BiTreeNode *node) {
    BiTreeNode **position;
    /* Do not allow removal from an empty tree.*/
    if (bitree_size(tree) == 0)
    return;

    /*Determine where to remove nodes.*/
    if (node == NULL)
        position = &tree->root;
    else
        position = &node->left;

    /*Remove the nodes.*/
    if (*position != NULL) {
        bitree_rem_left(tree, *position);
        bitree_rem_right(tree, *position);
        if (tree->destroy != NULL) {
            /* Call a user-defined function to free dynamically allocated data.*/
            tree->destroy((*position->data);   
        }

        free(*position);
        *position = NULL;

        /* Adjust the size of the tree to account for the removed node.*/
        tree->size--;
    }
    return;
}

/* bitree_rem_right */
void bitree_rem_right(BiTzee *tree, BiTreeNode *node) {
    BiTreeNode **position;
    
    /* Do not allow removal from an empty tree. */
    if (bitree_size(tree) == 0)
        return;

    /* Determine where to remove nodes.*/
    if (node == NULL)
        position = &tree->root;
    else
        position = &node->right;

    /* Remove the nodes.*/
    if (*position != NULL) {
        bitree_rem_left(txee,*position);
        bitree_rem_right(tree,*position);
        if (tree->destroy != NULL) {
            /* CalI a user-defined function to free dynamically allocated data.*/
            tree->destroy((*position)->data);
        }

        free(*position);
        *position = NULL;

        /* Adjust the size of the tree to account for the removed node.*/
        tree->size--;
    }
    return;
}

/* bitree_merge*/
int bitree_merge(BiTree *merge, BiTree *left, BiTree *right, const void *data) {
    /* Initialize the merged tree.*/
    bitree_init(merge, left->destroy);

    /* Insert the data for the root node of the merged tree.*/
    if (bitree_ins_left(merge, NULL, data) != 0) {
        bitree_destroy(merge);
        return -1;
    }

    /* Merge the two binary trees into a single binary tree.*/
    bitree_root(merge)->left = bitree_root(left);
    bitree_root(merge)->right = bitree_root(right);

    /* Adjust the size of the new binary tree.*/
    merge->size = merge->size + bitree_size(left) + bitree_size(right);

    /* Do not let the original trees access the merged nodes.*/
    left->root = NULL;
    left->size = 0;
    right->root = NULL;
    right->size = 0;
    return 0;
}

二叉搜索树

定义：

二叉搜索树是有二叉树组成的专用于查找和搜索目的的一种数据结构。

数据插入遵循：比根节点(root)大的数插入根右边，比根节点小的数插入左边。

数据搜索遵循：要查询的值比根(root)大的数向右子节点查，比根节点小向左节点查。

不允许有重复值出现

二叉搜素树应尽量保持平衡，但比较困难。非平衡树会造成搜索的节点数量过多，最多O(n)

二叉搜索树要保持平衡最好的方法是

AVL树

其定义为：

AVL树每个节点都保持了一个平衡因子。

插入结点时AVL树需要自我调整。

平衡因子：结点的右子树高度-左子树高度，其值为+1, 0，-1。

+1：代表树是左倾斜的

-1：代表树是右倾斜的

平衡二叉树

平衡因子改变：

插入新的结点会造成平衡因子改变，因此这棵树需要重新平衡，我们称这种平衡为AVL树的旋转

AVL树旋转方法：

LL(left-left)，LR(left-right)，RR(right-right)，RL(right-left)

avl树旋转有一个更简单的方法:

把这颗树抽象成一棵自然界的树，节点的平衡因子不是-1，0，+1时，RR和LL的节点小于-1或大于+1时树的树梢向下落一层；

RL和LR的节点小于-1或大于+1时是因为不平衡的子节点引起的，找到不平衡的子节点重复LL或RR的过程，不平衡子节点旋转之后父节点重复LL或RR.

接口定义：

/* bistree.h */
#ifndef BISTREE_H
#define BISTREE_R
#include "bitree.h"

/* Define balance factors for AVL trees. */
#define AVL_LFT_HEAVY   1
#define AVL_BALANCED    0
#deftne AVERGT_HEAVY    -1

/* Define a structure for nodes in AVL trees. */
typedef struct AvlNode_ {
    void *data;
    int hidden;
    int factor;
}Av1Node;

/* Implement binary search trees as binary trees. */
typedef BiTree BisTree;

/* Public Interface */

void bistree_init(Bistree *tree, int (*compare)(const void *key1, const void *key2), void (*destroy)(void *data));
void bistree_destroy(BisTree *tree);
int bistree_insert(BisTree *tree, const void *data);
int bistree_remove(BisTree *tree, const void *data);
int bistree_lookup(BisTree *tree, void **data);
#define bistree_size(tree) ((txee) ->size)
#endif

/* bistree.c */
#include <stdlib.h>
#include <string.h>
#include "bistree.h"

static void destroy_right(BisTree *tree, BiTreeNode *node);

/* rotate_left */
static void rotate_left(BiTreeNode **node) {
    BiTreeNode *left, *grandchild;

    left = bitree_left(*node);
    if (((AvlNode *)bitree_data(left))->factor == AVL_LFT_HEAVY) {
        /* Perform an LL rotation. */
        bitree_left(*node) = bitree_right(left);
        bitree_right(left) = *node;
        ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
        ((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;
        *node = left;
    } else {
        /* Perform an LR rotation. */
        grandchild = bitree_right(left);
        bitree_right(left) = bitree_left(grandchild);
        bitree_left(grandchild) = left;
        bitree_left(*node) = bitree_right(grandchild);
        bitree_right(grandchild) = *node;

        switch (((AvlNode *)bitree_data(left))->factor) {
            case AVL_LFT_HEAVY:
                ((AvlNode *)bitree_data(*node))->factor = AVL_RGT_HEAVY;
                ((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;
                break;
            
            case AVL_BALANCED:
                ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
                ((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;
                break;
            
            case AVL_RGT_HEAVY:
                ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
                ((AvlNode *)bitree_data(left))->factor = AVL_LFT_HEAVY;
                break;
        }

        ((AvlNode *)bitree_data(grandchild))->factor = AVL_BALANCED;
        *node = grandchild;
    }
}

/* rotate_right */
static void rotate_right(BiTreeNode **node) {
    BiTreeNode *right, *grandchild;
    right = bitree_right(*node);

    if (((AvlNode *)bitree_data(right))->factor == AVL_RGT_HEAVY) {
        /* Perform an RR rotation. */
        bitree_right(*node) = bitree_right(right);
        bitree_left(right) = *node;
        ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
        ((AvlNode *)bitree_data(right))->factor = AVL_BALANCED;
        *node = right;
    } else {
        /* Perform an RL rotation. */
        grandchild = bitree_left(right);
        bitree_right(right) = bitree_right(grandchild);
        bitree_right(grandchild) = right;
        bitree_right(*node) = bitree_left(grandchild);
        bitree_left(grandchild) = *node;

        switch (((AvlNode *)bitree_data(grandchild))->factor) {
            case AVL_LFT_HEAVY:
                ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
                ((AvlNode *)bitree_data(right))->factor = AVL_RGT_HEAVY;
                break;
            
            case AVL_BALANCED:
                ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
                ((AvlNode *)bitree_data(right))->factor = AVL_BALANCED;
                break;
            
            case AVL_RGT_HEAVY:
                ((AvlNode *)bitree_data(*node))->factor = AVL_LFT_HEAVY;
                ((AvlNode *)bitree_data(right))->factor = AVL_BALANCED ;
                break;
        }

        ((AvlNode *)bitree_data(grandchild))->factor = AVL_BALANCED;
        *node = grandchild;
    }
}

/* destroy_left */
static void destroy_left(BisTree *tree, BiTreeNode *node) {
    BiTreeNode **position;

    /* Do not allow destruction of an empty tree. */
    if (bitree_size(tree) == 0)
        return;

    /* Determine where to destroy nodes.*/
    if (node == NULL)
        position = &tree->root;
    else
        position = &tree->left;

    /* Destroy the nodes. */
    if (*position != NULL) {
        destroy_left(tree, *position);
        destroy_right(tree, *position);

        if (tree->destroy != NULL) {
            /* Call a user-defined function to free dynamically allocated data. */
            tree->destory(((AvlNode *)(*position)->data)->data);
        }
        
        /* Free the AVL data in the node, then free the node itself. */
        free((*position)->data);
        free(*position);
        *position = NULL;

        /* Adjust the size of the tree to account for the destroyed node. */
        tree->size--;
    }
}

/* destroy_right */
static void destroy_right(BisTree *tree, BiTreeNode *node) {
     BiTreeNode **position;

    /* Do not allow destruction of an empty tree. */
    if (bitree_size(tree) == 0)
        return;

    /* Determine where to destroy nodes.*/
    if (node == NULL)
        position = &tree->root;
    else
        position = &tree->right;

    /* Destroy the nodes. */
    if (*position != NULL) {
        destroy_left(tree, *position);
        destroy_right(tree, *position);

        if (tree->destroy != NULL) {
            /* Call a user-defined function to free dynamically allocated data. */
            tree->destory(((AvlNode *)(*position)->data)->data);
        }
        
        /* Free the AVL data in the node, then free the node itself. */
        free((*position)->data);
        free(*position);
        *position = NULL;

        /* Adjust the size of the tree to account for the destroyed node. */
        tree->size--;
    }
}

/* insert */
static int insert(BisTree *tree, BiTreeNode **node, const void *data, int *balanced) {
    AvlNode *avl_data;
    int cmpval, retval;

    /* Insert the data into the tree. */
    if (bitree_is_eob(*node)) {
        /* Handle insertion into an empty tree.*/
        if ((avl_data = (AvlNode *)malloc(sizeof(AvlNode))) == NULL)
            return -1;
        avl data->factor = AVL_BALANCED;
        avi data->hidden = 0;
        avl_data->data = (void *)data;
        
        return bitree_ins_left(tree, *node, avl_data);
    } else {
        /* Handle insertion into a tree that is not empty. */
        cmpval = tree->compare(data, ((AvlNode *)bitree_data(*node))->data);
        if (cmpval < 0) {
            /* Move to the left. */
            if (bitree_is_eob(bitree_left(*node))) {
                if ((avl_data = (AvlNode *)malloc(sizeof(AvlNode))) == NULL)
                    return -1;
                
                avl_data->factor = AVL_BALANCED;
                avl_data->hidden = 0;
                avl_data->data = (void *)data;

                if (bitree_ins_left(tree, *node, avl_data) != 0)
                    return -1;
                
                *balance = 0;
            } else {
                if ((retval = insert(tree, &bitree_left(*node), data, balanced)) != 0)
                return retval;
            }

            /* Ensure that the tree remains balanced. */
            if (!(*balanced)) {
                switch (((AvlNode *)bitree_data(*node))->factor) {
                    case AVL_LFT_HEAVY:
                        rotate_left(node) ;
                        *balanced = 1;
                        break;
                    case AVL_BALANCED:
                        ((AvlNode *)bitree_data(*node))->factor = AVL_LFT_HEAVY;
                        break;
                    case AVL_RGT_HEAVY:
                        ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
                        *balanced = 1;
                        break;
                }
                
            }
        } /* if (cmpval < 0) */
        else if (cmpval > 0) {
            /* move to the right. */
            if (bitree_is_eob(bitree_right(*node))) {
                if ((avl_data = (AvlNode *)malloc(sizeof(AvlNode))) == NULL)
                    return -1;
                
                avl_data->factor = AVL_BALANCED;
                avl_data->hidden = 0;
                avl_data->data = (void *)data;

                if (bitree_ins_right(tree, *node, avl_data) != 0)
                    return -1;
                
                *balance = 0;
            }
            else {
                if ((retval = insert(tree, &bitree_right(*node), data, balanced)) != 0)
                    return retval;
            }

            /* Ensure that the tree remains balanced. */
            if (!(*balanced)) {
                switch (((AvlNode *)bitree_data(*node))->factor) {
                    case AVL_LFT_HEAVY:
                        ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
                        *balanced = 1;
                        break;
                    case AVL_BALANCED:
                        ((AvlNode *)bitree_data(*node))->factor = AVL_RGT_HEAVY;
                        break;
                    case AVL_RGT_HEAVY:
                        rotate_right(node) ;
                        *balanced = 1;
                        break;
                }
                
            } /* if (cmpval) > 0 */
            else { 
                /* Handle finding a copy of the data. */
                if (!((Av1Node *)bitree_data(*node))->hodden) {
                    /* Do nothing since the data is in the tree and not hidden. */
                    return 1;
                } else {
                    /* Insert the new data and mark it as not hidden. */
                    if (tree->destroy != NULL) {
                        /* Destroy the hidden data since it is being replaced. */
                        tree->destory(((Av1Node *)bitree_data(*node))->data);
                    }
                    ((Av1Node *)bitree_data(*node))->data = (void *)data;
                    ((Av1Node *)bitree_data(*node))->hidden = 0;
                    
                    /* Do not rebalance because the tree structure is unchanged. */
                    *balanced = 1;
                }
            }
        }                     
    }
    return 0;
}

/* hide */
static int hide(BisTree *tree, BiTreeNode *node, const void *data) {
    int cmpval, retval;

    if (bitree_is_eob(node)) {
        /* Return that the data was not found. */
        return -1;
    }

    cmpval = tree->compare(data, ((AvlNode *)bitree_data(node))->data);
    if (cmpval < 0) {
        /* Move to the left.*/
        retval = hide(tree, bitree_left(node), data);
    } else if (cmpval > 0) {
        /* Move to the right.*/
        retval = hide(tree, bitree_right(node), data);
    } else {
        /* Mark the node as hidden. */
        ((AvLNode *)bitree_data(node))->hidden = 1;
        retvaL = 0;
    }
    return retval;
}

/* lookup */
static int lookup(BisTree *tree, BiTreeNode *node, void *data) {
    int cmpval, retval;

    if (bitree_is_eob(node)) {
        /* Return that the data was not found. */
        return -1;
    }

    cmpval = tree->compare(data, ((AvlNode *)bitree_data(node))->data);
    if (cmpval < 0) {
        /* Move to the left.*/
        retval = lookup(tree, bitree_left(node), data);
    } else if (cmpval > 0) {
        /* Move to the right.*/
        retval = lookup(tree, bitree_right(node), data);
    } else {
        if(!((AvlNode *)bitree_data(node))-<hidden) {
            /* Pass back the data from the tree. */
            *data = ((AvlNode *)bitree_data(node))->data;
            retval = 0;
        } else {
            /* Return that the data was not found. */
            return -1; 
        }
    }
    return retval;
}

/* bistree_init */
void bistree_init(BisTree *tree, int (*cpmpare)(void *keyl, const void *key2), void (*destory)(*data)) {
    /* Initialize the tree. */
    bitree_init(tree, destory);
    tree->compare = compare;
}

/* bistree_destroy */
void bistree_destroy(BisTree *tree) {
    /* Destroy all nodes in the tree. */
    destory_left(tree, NULL);

    /* No operations are allowed now, but clear the structure as a precaution. */
    memset(tree, 0, sizeof(BisTree));
}

/* bistree_insert */
int bistree_insert(BisTree *tree, const void *data) {
    int balanced = O;
    return insert(tree, &bitree_rot(tree), data, &balanced);
}

/* bitree_remove */
int bitree_remove(BisTree *tree, const void *data) {
    return hide(tree, bitree_root(tree), data);
}

/* bistree_lookup */
int bistree_lookup(BisTree *tree, void *data) {
    return lookup(tree, bitree_root(tree), data);
}

红黑树（R-B树）

R_B_tree

定义：

红黑树 为妥协的AVL树，平衡要求没AVL树严格，因此适用范围比AVL树多

红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。待插入结点默认为红色结点，插入时按照二分插入。

性质1. 结点是红色或黑色。
性质2. 根结点是黑色。
性质3. 所有叶子都是黑色。（叶子是NIL结点）
性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
性质5. 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。

`R_B树的插入旋转法`

RR或LL，刚插入的结点的父节点是红色，叔叔结点也是红色，那么父节点和叔叔变为黑色，祖父结点变为红色

刚插入的结点的父节点是红色，叔叔结点是黑色，那么父节点和叔叔结点需要左旋或右旋，然后原父结点变为黑色，叔叔结点变为红色。

LR或RL，刚插入结点父结点是红色，叔叔结点也是红色，那么父节点和叔叔结点变为黑色，祖父结点变为红色，

刚插入结点父结点是红色，叔叔结点为黑色，那么刚插入结点和父节点需要左旋或右旋，再次执行RR或LL步骤。

R_B树的删除旋转法：

R_B树的删除为红黑树最复杂部分

1、红黑树删除的情形

一、从树中删除节点X（以寻找后继节点的方式进行删除）

情况①：如果X没有孩子，且如果X是红色，直接删除X；如果X是黑色，则以X为当前节点进行旋转调色，最后删掉X

情况②：如果X只有一个孩子C，交换X和C的数值，再对新X进行删除。根据红黑树特性，此时X不可能为红色，因为红色节点要么没有孩子，要么有两个黑孩子。此时以新X为当前节点进行情况①的判断

情况③：如果X有两个孩子，则从后继中找到最小节点D，交换X和D的数值，再对新X进行删除。此时以新X为当前节点进行情况①或②的判断

二、旋转调色（N=旋转调色的当前节点[等于情况①中的X]，P=N的父亲，W=N的兄弟，Nf=N的远侄子，Nn=N的近侄子）

情况1：N是根或者N是红色，则：直接将N设为黑色

情况2：N不是根且N是黑色，且W为红色，则：将W设为黑色，P设为红色，对P进行旋转(N为P的左子时进行左旋，N为P的右子时进行右旋)，将情况转化为情况1、2、3、4、5

情况3：N不是根且N是黑色，且W为黑色，且W的左右子均为黑色，则：将W设为红色，将P设为当前节点进行旋转调色，将情况转化为情况1、2、3、4、5

情况4：N不是根且N是黑色，且W为黑色，且Nf为黑色，Nn为红色，则：交换W与Nn的颜色，并对W进行旋转(N为P的左子进行右旋，N为P的右子进行左旋)，旋转后N的新兄弟W有一个红色WR，则转换为情况5

情况5：N不是根且N是黑色，且W为黑色，且Nf为红色，Nn为黑色，则：将W设为P的颜色，P和Nf设为黑色，并对P进行旋转(N为P的左子进行左旋，N为P的右子进行右旋)，N设为根

B树，B+树，B*树

当数据量非常大时，二叉树已经不能满足需求，如果还用二叉树那么树的深度过大，一个节点存储多个数据就应运而生了。

定义：

B树是一种平衡的多分树，通常我们说m阶的B树，它必须满足如下条件：

每个节点最多只有m个子节点。
每个非叶子节点（除了根）具有至少⌈ m/2⌉子节点。
如果根不是叶节点，则根至少有两个子节点。
具有k个子节点的非叶节点包含k -1个键。
所有叶子都出现在同一水平，没有任何信息（高度一致）。

此树的一个节点最多有4个结点，一个节点最多有三个值，

插入如删除方法：B树插入与删除

B+树

在B树的基础上增加了数据遍历优点，想要遍历整个树的数据只要把叶子节点便完毕就行，因为B+树的叶子节点数据是整棵树数据，非叶子节点是叶子节点索引。

997909-20190728114240297-169990922

B*树

B*树在B+树的基础上增加了非叶子结点之间链表相联系。

171056_sAnR_135650

2-3-4树

2-3-4树是4阶B树，2-3-4树插入与删除

treap树

所谓的Treap树堆其实就是树 + 堆。树是二叉查找树BST，堆是二叉堆，大根堆小根堆都可以。

树堆既是一棵二叉查找树，也是一个二叉堆。但是这两种数据结构貌似还是矛盾的存在，如果是二叉查找树，就不能是一个堆，如果是一个堆，那么必然不是二叉查找树。

所以树堆用了一个很巧妙的方式解决这个问题：给每个键值一个随机附加的优先级，让键值满足二叉查找树的结构，让优先级满足二叉堆的结构。

treap树的详解，插入与删除

k-d树

k-d树常用来作空间划分及近邻搜索，是二叉空间划分树的一个特例。

K-D TREE算法原理及实现

最小生成树(Minimum Spanning Tree)

对于有n个顶点的连通图，生成树有n-1条边，若边数小于此数就不可能将各顶点连通，如果边的数量多于n-1条边，必定会产生回路。

最小生成树(Minimum Spanning Tree理解

6.堆和优先队列

在许多问题中，当对数据集进行频繁的插入和删除操作时，往往需要快速确定最大或最小的元素。处理这个问题的方法之一，就是使用一个已排好序的数据集，通过这种方法，最大或最小的元素总是处在数据集的头部（这取决于使用升序还是降序排列）。然而将数据集一遍又一遍地进行排序的代价是非常高的。并且许多情况下，将元素排序并不是超越的目的，最终我们可能在真正要做的工作之外做了很多其他工作，想要快速的找到最大或最小的元素，只需要让元素储存在可以找到它的位置上就行。堆和优先队列，就是一种处理这种问题的有效方法。

本章内容包括：

堆：

它是一种树形组织，使我们能够迅速确定包含最大值的结点。维持一棵树的代价低于维持一个有序数据集。同样，我们可以确定通过堆快速地找到包含最小值的元素。

优先队列

它是一个从堆自然衍生而来的数据结构。在优先队列中，数据保存在一个堆中，这样我们能够迅速确定下一个最高优先级的结点。所谓元素的“优先级”在不同的问题中有不同的意义。

队和优先队列的一些应用：

排序：堆排序

任务调度

任务调度会告诉操作系统接下来哪个进程将在CPU上运行。操作系统会不断调整进程的优先级，用优先队列来存储进程是相对比较高效的方法，因为它可以确保下一个将在CPU中运行的进程的优先级是最高的。

包褰分拣（见本章相关章节）

快递公司通常用包裹分拣法来确定包裹递送的优先级。当扫描包裹时，高优先级的包裹将作为急快件投递出去。而非急快件将作为较低优先级的包裹投递出去。计算机系统通常使用优先队列来保证最高优先级的包在系统中运行最顺畅，因为这种方法十分高效。

霍夫曼编码

这是一种数据压缩方法，它使用霍夫曼树为数据符号分配编码（见第14章）。向出现频率较高的符号分配较短的编码,向出现频率较低的符号分配较长的编码。霍夫曼树是由较小的二叉树两两合并构成。由于每次都必须合并键值最小的二叉树，因此每次合并的两棵树都是从一个优先队列中取出的。

负载均衡

它用来维护管理一系列处理类似任务的服务。当连接请求到达时，优先队列可以确定哪个服务器能够最好地处理到达的任务。

堆排序

优先队列的描述:

优先队列将数据按照优先级顺序排列。一个优先队列由许多有序的元素构成，所以优先级最高的元素可以有效而快速地确定,例如，我们看一组用来做负载均衡的服务器，时时观察它们的使用情况。当连接请求到达时，优先队列可以告知当前哪个服务器是处理此连接请求的最佳服务器。在这种情况下，最空闲的服务器获取的优先级最高，因为它可以最好地处理服务请求。

数据结构：数据结构是为算法服务而设计的。

数据结构部分

一. 数据结构的存储方式有两种

1.顺序存储(数组,内存连续)

2.链式存储(链表,内存不连续,依靠节点的指针指向下一个节点)

二 常见数据结构实现

1.链表

单向链表

例子

双向链表

例子

循环链表

例子

2.栈和队列

栈例子

队列例子

队列示例：事件处理

3.集合

例子

Set示例：集合覆盖

4.哈希表

链式哈希表

解决哈希表冲突

选择哈希函数

例子

开地址哈希表

例子

5.树

树的定义：

二叉树

树的遍历算法

树的平衡

二叉树的接口定义：

二叉搜索树

定义：

AVL树

接口定义：

红黑树（R-B树）

定义：

R_B树的插入旋转法

R_B树的删除旋转法：

B树，B+树，B*树

2-3-4树

treap树

k-d树

最小生成树(Minimum Spanning Tree)

6.堆和优先队列

堆：

优先队列

排序：堆排序

任务调度

包褰分拣（见本章相关章节）

霍夫曼编码

负载均衡

二常见数据结构实现

`R_B树的插入旋转法`