1、线性结构的查找

1-1 顺序查找

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

#define NUMBER (10 + 1)
#define MIN ((1<<31))

typedef struct {
        int *data;
        int length;
}SSTable;

int search_seq1(SSTable* ST, int key){
        int i;
        ST->data[0] = key;       // 哨兵
        for(i = ST->length; ST->data[i] != key; i--);
        return i;               // 当查找不到返回0
}

int main()
{
        int d;
        SSTable T;
        T.length = NUMBER;
        T.data = (int *)malloc(sizeof(int) * NUMBER);
        T.data[0] = MIN, T.data[1] = 3, T.data[3] = 4;//...

        while(~scanf("%d", &d)){
                printf("the %d at No.%d\n", d, search_seq1(&T, d));
        }

        return 0;
}

1-2 折半查找

#include <stdio.h>

#define NUMBER (10)

typedef struct {
        int data[NUMBER];
        int length;
}SeqList;

int binary_search(int data[], int length, int key){
        int low = 0, high = length - 1, mid;
        while(low <= high){
            mid = (low + high)/2;
            if(data[mid] == key) return mid;
            else if(data[mid] > key) high = mid - 1;
            else low = mid + 1;
        }
        return -1;
}

int main()
{
        int d;
        SeqList L;
        L.length = NUMBER;
        L.data[0] = 7;
        L.data[1] = 10;
        L.data[2] = 13;
        L.data[3] = 16;
        L.data[4] = 29;
        L.data[5] = 32;
        L.data[6] = 33;
        L.data[7] = 37;
        L.data[8] = 41;
        L.data[9] = 43;//ordered...

        while(scanf("%d", &d) != EOF){
                printf("the %d at index: %d\n", d, binary_search(L.data, L.length, d));
        }

        return 0;
}

1-3 分块查找

2、树形结构的查找

2-1 二叉查找树

2-2 二叉平衡树

2-3 B-tree和B+tree

B-tree是一种多路平衡查找树，B-tree中的所有结点中的孩子节点数的最大值称为B-tree的阶，通常用m表



时，并不终止，而是继续向下查找直到叶节点上的该关键字为止。所以，在B+树查找，无论查找成功与否，每次查找都是一条从根节点到叶节点的路径。

3、散列结构的查找

3-1 哈希(hash散列)表

4、字符串模式匹配

4-1 简单的模式匹配算法

4-2 KMP 算法

/**
 * Copyright ? 2016 Authors. All rights reserved.
 *
 * FileName: .cpp
 * Author: Wu_Being <1040003585@qq.com>
 * Date/Time: 
 * Description:
 */
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> Pii;

const int inf  = 0x7e7e7e7e;
const LL infLL = 0x7e7e7e7e7e7e7e7eLL;
const unsigned uinf  = 0xfcfcfcfc;
const ULL uinfLL = 0xfcfcfcfcfcfcfcfcLL;

char s[100000];

void get_next(char T[],int next[]){
    //T[0]存放T的长度 
    int i=1;
    next[1]=0;
    int j=0;
    while(i<=T[0]){
        if(j==0||T[i]==T[j]){
            i++;j++;next[i]=j;
        }else{
            j=next[j];
        }
    }
}
int KMP(char S[],char T[],int next[],int pos){
//1<=pos<=strlen(s) 从主串的pos位置开始 
    int i=pos;int j=1;
    while(i<=S[0]&&j<=T[0]){
        if(j==0||S[i]==T[j]){
            i++;j++;
        }else{
            j=next[j];
        }
    }
}
void input(){
    scanf("%s",s+1);
    s[0]=strlen(s);
    cout<<strlen(s)<<endl;
    cout<<s[0]<<endl;
    printf("%d ",s[0]); cout<<s+1<<endl;
}
int main(int argc,char* argv[])
{
    input();
    //KMP();
    return 0;
}

Wu_Being 博客声明：本人博客欢迎转载，请标明博客原文和原链接！谢谢！
《【数据结构7】查找》
http://blog.csdn.net/u014134180/article/details/55506265

如果你看完这篇博文，觉得对你有帮助，并且愿意付赞助费，那么我会更有动力写下去。