数据结构

“Algorithm + Data Structures = Programs” - Niklaus Wirth

栈和队列

栈和队列都是动态集合，且在其上进行 DELETE 操作所移除的元素都是预先设定的。

在栈（stack）中，被删除的是最近插入的元素；栈实现的是一种后进先出（last-in first out, LIFO）策略。
在队列（queue）中，被删去的总是在集合中存在时间最长的那个元素；队列实现的是一种先进先出（First-in first out, FIFO）策略。

栈

可以用一个数组 \(S[1..n]\) 来实现一个最多可容纳 \(n\) 个元素的栈。该数组有一个属性 S.top，指向最新插入的元素。栈中包含的元素为 \(S[1..S.top]\)，其中 \(S[1]\) 是栈底元素，而 \(S[S.top]\) 是栈顶元素。

实现

C语言实现的倒序打印：

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

int stack[512];
int top = 0;

int isEmpty()
{
    if (top > 0)
        return 1;
    else
        return 0;
}

int pop()
{
    if (isEmpty())
        return stack[top--];
}

void push(int num)
{
    stack[++top] = num;
}

int main(void){
    int i;
    for (i = 0; i<10; i++) {
        push(i);
    }
    while(!isEmpty()){
        printf("%d ", pop());
    }
}

链表

链表（linked list）是一种这样的数据结构，其中的各对象按线性顺序排列。数组的线性顺序是由数组下标决定的，然而与数组不同的是，链表的顺序是由各个对象里的指针决定的。链表为动态集合提供了一种简单而灵活的表示方法，并且可以支持大多数动态集合的操作。

每个链表有一个头指针（head），通过头指针可以找到第一个节点，每个节点都可以通过指针域找到它的后继（next），最后一个节点的指针域为NULL，表示没有后继。数组在内存中是连续存放的，而链表在内存中的布局是不规则的，我们知道访问某个数组元素 b[n] 时可以通过基地址+n×每个元素的字节数得到它地址，或者说数组支持随机访问，而链表是不支持随机访问的，只能通过前一个元素的指针域得知后一个元素的地址，因此只能从头指针开始顺序访问各节点。

定义

typedef struct Node{
    int data;
    Node *next;
}Node, *list;

创建结点

Node* createNode(int data)
{
    Node *p = new Node;
    p->data = data;
    p->next = NULL;
    return p;
}

删除结点

void freeNode(Node *p)
{
    delete p;
}

遍历所有结点

void visit(Node *p)
{
    printf("%d ", p->data);    
}

void traverse(Node *head, void (*visit)(Node *))
{
    for (Node *p = head; p; p = p->next){
        visit(p);        
    }
}

查找结点

查找第一个值为 key 的结点

Node* searchNode(Node *head, int key)
{
    for(Node *p = head; p; p = p->next){
        if (p->data == key) return p;
    }
    return NULL;
}

查找第 pos 个位置的结点

Node* accessNode (Node *head, int pos){
    if (pos < 0) {
        perror("Incorrect position!");
        return NULL;
    }
    if (pos == 0) return head;
    Node *p = head;
    int i;
    for (i = 0; i < pos && p; i++){
        p = p->next;
    }
    if (i == pos) return p;
    else {
        printf("Incorrect position!");
        return NULL;
    }    
}

插入结点

头插入

Node* insertHead(Node *head, Node *nd){
    nd->next = head;
    head = nd;
    return head;
}

Node* insertHead(Node *head, int data){
    Node *nd = createNode(data);
    head = insertHead(head, nd);
    return head;
}

尾插入

Node* insertTail(Node *head, Node *nd){
    if (!head){
        head = nd;
    } else {
        Node *p;
        for (p = head; p->next; p = p->next);
        p->next = nd;
        p = nd;
    }
    return head;
}


Node* insertTail(Node *head, int data){
    Node *nd = createNode(data);
    head = insertTail(head, nd);
    return head;
}

任意位置插入

Node* insertNode(Node *head, int pos, Node *nd){
    if (pos < 0) {
        perror("Incorrect position!");
        return head;
    }
    if (pos == 0 && !head){
        head = nd;
        return NULL;
    }
    Node *p = accessNode(head, pos-1);
    if (p != NULL){
        nd->next = p->next;
        p->next = nd;
    } else {
        perror("Incorrect position!");
    }
    return head;
}

Node* insertNode(Node *head, int pos, int data){
    Node *nd = createNode(data);
    insertNode(head, pos, nd);
    return head;
}

删除结点

Node* deleteNode(Node *head, int pos)
{
    if (pos < 0){
        perror("Invalidate position!");
        return head;
    }
    if (!head){
        perror("Link is empty!");
        return NULL;
    }
    Node *p;
    if (pos == 0){
        p = head;
        head = head->next;
        freeNode(p);
        return head;
    }
    p = accessNode(head, pos-1);
    if (p != NULL && p->next != NULL){
        Node *item = p->next;
        p->next = item->next;
        freeNode(item);
    } else {
        perror("Invalidate position!");
    }
    return head;
}

用数组初始化一个链表

Node* init(int a[], int n)
{
    Node *head = NULL;
    if (n < 0){
        perror("Invalidate length!");
        return NULL;
    }
    Node *p;
    for (int i = 0; i < n; ++i){
        //or: insertNode(i, a[i]);
        //or: insertTail(a[i]);
        Node *nd = createNode(a[i]);
        if (NULL == head){
            head = p = nd;
            continue;
        }
        p->next = nd;
        p = nd;
    }
    return head;
}

清空一个链表

Node* destroy(Node *head)
{
    Node *p = head;
    Node *q;
    while(p){
        q = p;
        p = p->next;
        freeNode(q);
    }
    head = NULL;
    return head;
}

求链表长

int length(Node *head)
{
    Node *p = head;
    int i;
    for(i = 0; p; ++i){
        p = p->next;
    }
    return i;
}

获取链表中间结点

用一个快指针和一个慢指针实现。慢指针移动的速度是快指针的一半，当快指针走完链表时，输出慢指针。

Node* accessMid(Node *head)
{
    Node *slow = head;
    Node *fast = head;
    int i = 0;
    int j = 0;
    while(fast){
        if (j < i/2){
            slow = slow->next;
            ++j;
        }
        fast = fast->next;
        ++i;
    }
    return slow;
}

单链表排序

最简单的可以使用选择排序实现：

Node* selectionSort(Node *head)
{
    if (!head) return head;

    Node *p, *q, *min;
    int t;
    for (p = head; p; p = p->next){
        min = p;
        for (q = p; q; q = q->next)
            if (q->data < min->data) min = q;
        if (min != p){
            t = min->data;
            min->data = p->data;
            p->data = t;
        }
    }
    return head;
}

将单链表反转

从头到尾遍历原链表，每遍历一个结点，将其摘下放在新链表的最前端。注意链表为空和只有一个结点的情况。时间复杂度为O（n）。参考代码如下：

// 反转单链表  
Node * reverseList(Node * pHead)  
{  
    // 如果链表为空或只有一个结点，无需反转，直接返回原链表头指针  
    if(pHead == NULL || pHead->next == NULL)    
        return pHead;  
  
    Node *pReversedHead = NULL; // 反转后的新链表头指针，初始为NULL  
    Node *pCurrent = pHead;  
    while(pCurrent != NULL)  
    {  
        Node *pTemp = pCurrent;  
        pCurrent = pCurrent->next;  
        pTemp->next = pReversedHead; // 将当前结点摘下，插入新链表的最前端  
        pReversedHead = pTemp;  
    }  
    return pReversedHead;  
}

逆序打印单链表

对于这种颠倒顺序的问题，我们应该就会想到栈，后进先出。所以，这一题要么自己使用栈，要么让系统使用栈，也就是递归。注意链表为空的情况。时间复杂度为O（n）。参考代码如下：

// 从尾到头打印链表，使用递归  
void reversePrint(Node *pHead)  
{
    if(pHead == NULL)
    {
        return;
    }
    else
    {
        reversePrint(pHead->next);
        printf("%d\t", pHead->data);
    }
}

判断是否存在环

用一个快指针和一个慢指针实现。慢指针每次移动一步，快指针就移动两步。如果两个指针能够相遇，证明存在环。

bool isLoop(Node *head)
{
    Node *slow = head, *fast = head;

    if (NULL == head || NULL == head->next) return false;
    
    do {
        fast = fast->next->next;
        slow = slow->next;        
    }
    while (fast && fast->next && fast!=slow);
    
    if (fast == slow){        
        return true;
    }
    else return false;
}

找出环的起点

当快指针和慢指针相遇后，慢指针返回链表头，快指针从相遇点开始，两个指针重新恢复一次一步的速度移动。如果再次相遇，则该相遇的地点即为环的起点。

Node* loopstart(Node *head)
{
    if (NULL == head || NULL == head->next) return NULL;
    Node *slow = head, *fast = head;
    while(fast && fast->next){
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) break;
    }
    if(!fast || !fast->next) return NULL;
    slow = head;
    while(fast != slow){
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

判断两个单链表是否相交

如果两个链表相交于某一节点，那么在这个相交节点之后的所有节点都是两个链表所共有的。也就是说，如果两个链表相交，那么最后一个节点肯定是共有的。先遍历第一个链表，记住最后一个节点，然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则不相交。时间复杂度为O(len1+len2)，因为只需要一个额外指针保存最后一个节点地址，空间复杂度为 O(1)。参考代码如下：

bool isIntersected(Node *pHead1, Node *pHead2)  
{  
    if(pHead1 == NULL || pHead2 == NULL)  
        return false;  

    Node* pTail1 = pHead1;  
    while(pTail1->next != NULL)  
        pTail1 = pTail1->next;  

    Node* pTail2 = pHead2;  
    while(pTail2->next != NULL)  
        pTail2 = pTail2->next;  
    return pTail1 == pTail2;  
}

求两个单链表相交的第一个节点

对第一个链表遍历，计算长度len1，同时保存最后一个节点的地址。
对第二个链表遍历，计算长度len2，同时检查最后一个节点是否和第一个链表的最后一个节点相同，若不相同，不相交，结束。

两个链表均从头节点开始，假设len1大于len2，那么将第一个链表先遍历len1-len2个节点，此时两个链表当前节点到第一个相交节点的距离就相等了，然后一起向后遍历，直到两个节点的地址相同。

时间复杂度，O(len1+len2)。参考代码如下：

Node* GetFirstCommonNode(Node *pHead1, Node * pHead2)  
{  
    if(pHead1 == NULL || pHead2 == NULL)  
        return NULL;  
  
    int len1 = 1;  
    Node * pTail1 = pHead1;  
    while(pTail1->next != NULL)  
    {  
        pTail1 = pTail1->next;  
        len1++;  
    }  
  
    int len2 = 1;  
    Node * pTail2 = pHead2;  
    while(pTail2->next != NULL)  
    {  
        pTail2 = pTail2->next;  
        len2++;  
    }  
  
    if(pTail1 != pTail2) // 不相交直接返回NULL  
        return NULL;  
  
    Node *pNode1 = pHead1;  
    Node *pNode2 = pHead2;  
    // 先对齐两个链表的当前结点，使之到尾节点的距离相等  
    if(len1 > len2)  
    {  
        int k = len1 - len2;  
        while(k--)  
            pNode1 = pNode1->next;  
    }  
    else  
    {  
        int k = len2 - len1;  
        while(k--)  
            pNode2 = pNode2->next;  
    }  
    while(pNode1 != pNode2)  
    {  
        pNode1 = pNode1->next;  
        pNode2 = pNode2->next;  
    }  
        return pNode1;  
}

二叉树

二叉树是一种特殊的树，在二叉树中每个节点最多有两个子节点，一般称为左子节点和右子节点（或左孩子和右孩子），并且二叉树的子树有左右之分，其次序不能任意颠倒。

节点定义

struct Node
{
    int data;
    Node* lchild;
    Node* rchild;
};

有些实现还会带上父节点：

struct Node
{
    int data;
    Node* lchild;
    Node* rchild;
    Node* parent;
};

求节点数

递归解法：

如果二叉树为空，节点个数为0
如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1

int getNodeNum(Node *pRoot)
{
    if(pRoot == NULL) return 0;
    return getNodeNum(pRoot->lchild) + getNodeNum(pRoot->rchild) + 1;
}

求树高

递归解法：

如果二叉树为空，二叉树的树高为0
如果二叉树不为空，二叉树的树高 = max(左子树树高，右子树树高) + 1

int getDepth(Node *pRoot){
    if(pRoot == NULL) return 0;
    int ld = getDepth(pRoot->lchild);
    int rd = getDepth(pRoot->rchild);
    return ld > rd ? (ld + 1) : (rd + 1);
}

遍历

前序遍历

递归解法：

如果二叉树为空，空操作
如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树

void preOrderTraverse(Node *pRoot)
{
    if(pRoot == NULL) return;
    visit(pRoot); // 访问根节点  
    preOrderTraverse(pRoot->lchild); // 前序遍历左子树  
    preOrderTraverse(pRoot->rchild); // 前序遍历右子树  
}

中序遍历

递归解法：

如果二叉树为空，空操作
如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树

void inOrderTraverse(Node *pRoot)
{
    if(pRoot == NULL) return;
    inOrderTraverse(pRoot->lchild); // 中序遍历左子树  
    visit(pRoot); // 访问根节点  
    inOrderTraverse(pRoot->rchild); // 中序遍历右子树  
}

后序遍历

递归解法：

如果二叉树为空，空操作
如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点

void postOrderTraverse(Node *pRoot)
{
    if(pRoot == NULL) return;
    postOrderTraverse(pRoot->lchild); // 后序遍历左子树  
    postOrderTraverse(pRoot->rchild); // 后序遍历右子树  
    visit(pRoot); // 访问根节点
}

层序遍历

相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。

void levelTraverse(Node *pRoot)
{
    if(pRoot == NULL) return;
    queue<Node*> q;
    q.push(pRoot);
    while(!q.empty())
    {
        Node *pNode = q.front();
        q.pop();
        visit(pNode); // 访问节点
        if(pNode->lchild != NULL)
            q.push(pNode->lchild);
        if(pNode->rchild != NULL)
            q.push(pNode->rchild);
    }
    return;
}

求二叉树第K层的节点个数

递归解法：

如果二叉树为空或者k<1返回0
如果二叉树不为空并且k==1，返回1
如果二叉树不为空且k>1，返回左子树中k-1层的节点个数与右子树k-1层节点个数之和

int getNodeNumKthLevel(Node *pRoot, int k)
{
    if(pRoot == NULL || k < 1) return 0;  
    if(k == 1) return 1;
    int numLeft = getNodeNumKthLevel(pRoot->lchild, k-1); // 左子树中k-1层的节点个数  
    int numRight = getNodeNumKthLevel(pRoot->rchild, k-1); // 右子树中k-1层的节点个数  
    return (numLeft + numRight);
}

求二叉树中叶子节点的个数

递归解法：

如果二叉树为空，返回0
如果二叉树不为空且左右子树为空，返回1
如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数

int getLeafNodeNum(Node * pRoot)  
{
    if(pRoot == NULL)  
        return 0;  
    if(pRoot->lchild == NULL && pRoot->rchild == NULL)  
        return 1;
    int numLeft = getLeafNodeNum(pRoot->lchild); // 左子树中叶节点的个数  
    int numRight = getLeafNodeNum(pRoot->rchild); // 右子树中叶节点的个数  
    return (numLeft + numRight);
}

判断二叉树是不是平衡二叉树

递归解法：

如果二叉树为空，返回真
如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假

bool isAVL(Node *pRoot, int &height)
{
    if(pRoot == NULL) // 空树，返回真
    {
        height = 0;
        return true;
    }
    int heightLeft;
    bool resultLeft = isAVL(pRoot->lchild, heightLeft);
    int heightRight;
    bool resultRight = isAVL(pRoot->rchild, heightRighte);
    if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1) // 左子树和右子树都是AVL，并且高度相差不大于1，返回真  
    {
        height = max(heightLeft, heightRight) + 1;
        return true;  
    } else {
        height = max(heightLeft, heightRight) + 1;
        return false;  
    }
}

求二叉树的镜像

递归解法：

如果二叉树为空，返回空
如果二叉树不为空，求左子树和右子树的镜像，然后交换左子树和右子树

Node* mirror(Node *pRoot)
{  
    if(pRoot == NULL) return NULL;
    Node *pLeft = mirror(pRoot->lchild); // 求左子树镜像
    Node *pRight = mirror(pRoot->rchild); // 求右子树镜像
    // 交换左子树和右子树
    pRoot->lchild = pRight;
    pRoot->rchild = pLeft;
    return pRoot;
}

由前序遍历序列和中序遍历序列重建二叉树

二叉树前序遍历序列中，第一个元素总是树的根节点的值。中序遍历序列中，左子树的节点的值位于根节点的值的左边，右子树的节点的值位于根节点的值的右边。

递归解法：

如果前序遍历为空或中序遍历为空或节点个数小于等于0，返回NULL。
创建根节点。前序遍历的第一个数据就是根节点的数据，在中序遍历中找到根节点的位置，可分别得知左子树和右子树的前序和中序遍历序列，重建左右子树。

Node* rebuildBinaryTree(int* pPreOrder, int* pInOrder, int nodeNum)
{
    if(pPreOrder == NULL || pInOrder == NULL || nodeNum <= 0)
        return NULL;
    Node *pRoot = new Node;
    // 前序遍历的第一个数据就是根节点数据  
    pRoot->data = pPreOrder[0]; 
    pRoot->lchild = NULL;
    pRoot->rchild = NULL;
    // 查找根节点在中序遍历中的位置，中序遍历中，根节点左边为左子树，右边为右子树
    int rootPositionInOrder = -1;
    for(int i = 0; i < nodeNum; i++)
        if(pInOrder[i] == pRoot->data)
        {
            rootPositionInOrder = i;
            break;
        }
    if(rootPositionInOrder == -1)
    {
        throw std::exception("Invalid input.");
    }
    // 重建左子树  
    int nodeNumLeft = rootPositionInOrder;
    int * pPreOrderLeft = pPreOrder + 1;
    int * pInOrderLeft = pInOrder;
    pRoot->lchild = rebuildBinaryTree(pPreOrderLeft, pInOrderLeft, nodeNumLeft);
    // 重建右子树  
    int nodeNumRight = nodeNum - nodeNumLeft - 1;
    int *pPreOrderRight = pPreOrder + 1 + nodeNumLeft;
    int *pInOrderRight = pInOrder + nodeNumLeft + 1;
    pRoot->rchild = rebuildBinaryTree(pPreOrderRight, pInOrderRight, nodeNumRight);
    return pRoot;
}

同样，有中序遍历序列和后序遍历序列，类似的方法可重建二叉树，但前序遍历序列和后序遍历序列不能恢复一棵二叉树，证明略。

前序遍历序列和后序遍历序列不能恢复一棵二叉树。

判断二叉树是不是完全二叉树

若设二叉树的深度为h，除第 h 层外，其它各层（1～h-1）的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

有如下算法：按层次（从上到下，从左到右）遍历二叉树，当遇到一个节点的左子树为空时，则该节点右子树必须为空，且后面遍历的节点左右子树都必须为空，否则不是完全二叉树。

bool IsCompleteBinaryTree(Node *pRoot)
{
    if(pRoot == NULL)
        return false;
    queue<Node*> q;
    q.push(pRoot);
    bool mustHaveNoChild = false;
    bool result = true;
    while(!q.empty())
    {
        Node* pNode = q.front();
        q.pop();
        if(mustHaveNoChild) // 已经出现了有空子树的节点了，后面出现的必须为叶节点（左右子树都为空）  
        {
            if(pNode->lchild != NULL || pNode->rchild != NULL)
            {
                result = false;
                break;
            }
        }
        else  
        {  
            if(pNode->lchild != NULL && pNode->rchild != NULL)  
            {  
                q.push(pNode->lchild);  
                q.push(pNode->rchild);  
            }  
            else if(pNode->lchild != NULL && pNode->rchild == NULL)  
            {  
                mustHaveNoChild = true;  
                q.push(pNode->lchild);  
            }  
            else if(pNode->lchild == NULL && pNode->rchild != NULL)  
            {  
                result = false;  
                break;  
            }  
            else  
            {  
                mustHaveNoChild = true;  
            }  
        }  
    }  
    return result;  
}

二叉查找树

如果我们给二叉树加一个额外的条件，就可以得到一种被称作二叉查找树(binary search tree)的特殊二叉树。二叉查找树要求：每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大。

插入节点

首先执行查找算法，找出被插结点的父亲结点。

判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。

若二叉树为空。则首先单独生成根结点。

注意：新插入的结点总是叶子结点。

void insertNode(Node* &pRoot, int x){
    if(pRoot == NULL){
        pRoot = new Node;
        pRoot->lchild = pRoot->rchild = NULL;
        pRoot->data = x;
        return;
    }
    if(x < pRoot->data)
        insertNode(pRoot->lchild, x);
    else
        insertNode(pRoot->rchild, x);
}

删除节点

删除某个结点后依然要保持二叉查找树的特性。例子中的删除过程如下：

若删除点是叶子结点，则设置其双亲结点的指针为空。
若删除点只有左子树，或只有右子树，则设置其双亲结点的指针指向左子树或右子树。
若删除点的左右子树均不为空，则：
- 查询删除点的右子树的左子树是否为空，若为空，则把删除点的左子树设为删除点的右子树的左子树。
- 若不为空，则继续查询左子树，直到找到最底层的左子树为止。

void deleteNode(Node *root, int data)  
{
    Node p = *root, parent, s;
  
    if (NULL == p) return;
  
    if (p->data == data) {
        // It's a leaf node
        if (!p->rchild && !p->lchild) {
            *root = NULL;
            free(p);
        }
        // the right child is NULL
        else if (!p->rchild) {
            *root = p->lchild;
            free(p);  
        }
        else if (!p->lchild) {
            *root = p->rchild;
            free(p);
        }
        // the node has both children
        else {
            s = p->rchild;
            if (!s->lchild)
            s->lchild = p->lchild;
            else {  
            while (s->lchild) {  
                parent = s;
                s = s->lchild;
            }  
            parent->lchild = s->rchild;
            s->lchild = p->lchild;
            s->rchild = p->rchild;
            }  
            *root = s;
            free(p);
        }  
    }   
    else if (data > p->data) {
        deleteNode(&(p->rchild), data);
    }
    else if (data < p->data) {
        deleteNode(&(p->lchild), data);
    }
}

查找节点

递归解法：

若当前节点为空，返回空节点；
若当前节点的值与要查找的值相同，返回当前节点；
若当前节点的值大于要查找的值，在左子树中继续查找该值；
若当前节点的值小于要查找的值，在右子树中继续查找该值。

Node* searchNode(Node* &pRoot, int x){
    if (pRoot == NULL) return NULL;
    if (pRoot->data == x) return pRoot;
    if(x < pRoot->data)
        searchNode(pRoot->lchild, x);
    else
        searchNode(pRoot->rchild, x);
}

哈希表

下图示意了哈希表（Hash Table）这样的数据结构。

如上图所示，首先分配一个指针数组，数组的每个元素是一个链表的头指针，每个链表称为一个 槽（Slot） 。哪个数据应该放入哪个槽中由哈希函数决定，在这个例子中我们简单地选取哈希函数h(x) = x % 11，这样任意数据x都可以映射成0~10之间的一个数，就是槽的编号，将数据放入某个槽的操作就是链表的插入操作。

如果每个槽里至多只有一个数据，可以想像这种情况下search、insert和delete操作的时间复杂度都是O(1)，但有时会有多个数据被哈希函数映射到同一个槽中，这称为碰撞（Collision），设计一个好的哈希函数可以把数据比较均匀地分布到各个槽中，尽量避免碰撞。如果能把n个数据比较均匀地分布到m个槽中，每个糟里约有n/m个数据，则search、insert和delete和操作的时间复杂度都是O(n/m)，如果n和m的比是常数，则时间复杂度仍然是O(1)。一般来说，要处理的数据越多，构造哈希表时分配的槽也应该越多，所以n和m成正比这个假设是成立的。

如果用我们学过的各种数据结构来表示n个数据的集合，下表是search、insert和delete操作在平均情况下的时间复杂度比较。

数据结构	search	insert	delete
数组	O(n)，有序数组折半查找是O(lgn)	O(n)	O(n)
双向链表	O(n)	O(1)	O(1)
排序二叉树	O(lgn)	O(lgn)	O(lgn)
哈希表（n与槽数m成正比）	O(1)	O(1)	O(1)

典型应用

统计一个文本文件中每个单词的出现次数

栈和队列

栈

实现

链表

定义

创建结点

删除结点

遍历所有结点

查找结点

查找第一个值为 key 的结点

查找第 pos 个位置的结点

插入结点

头插入

尾插入

任意位置插入

删除结点

用数组初始化一个链表

清空一个链表

求链表长

获取链表中间结点

单链表排序

将单链表反转

逆序打印单链表

判断是否存在环

找出环的起点

判断两个单链表是否相交

求两个单链表相交的第一个节点

二叉树

节点定义

求节点数

求树高

遍历

前序遍历

中序遍历

后序遍历

层序遍历

求二叉树第K层的节点个数

求二叉树中叶子节点的个数

判断二叉树是不是平衡二叉树

求二叉树的镜像

由前序遍历序列和中序遍历序列重建二叉树

判断二叉树是不是完全二叉树

二叉查找树

插入节点

删除节点

查找节点

哈希表

典型应用

深入阅读

Comments