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
如果你看完这篇博文,觉得对你有帮助,并且愿意付赞助费,那么我会更有动力写下去。