查找

结构体定义

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define KeyType int
using namespace std;
typedef struct {
    KeyType key; 
}ElemType;

typedef struct{
    ElemType *elem;
    int Length;
}SSTable;

创建一个表

1
2
3
4
5
6
7
8
9
void Create(SSTable **ST, int length){
    (*ST) = (SSTable*) malloc (sizeof(SSTable));
    (*ST)->Length = length;
    (*ST)->elem = (ElemType*) malloc ((length + 1) * sizeof(ElemType));
    cout << "输入表中的数据元素: " << endl;
    for (int i = 1; i <= length; i++) {
        scanf("%d", &((*ST)->elem[i].key));
    }
}

顺序查找

1
2
3
4
5
6
7
int SeqSearch(SSTable ST, KeyType key) {
    int i = ST.Length;
    while (ST.elem[i].key != key) {
        i--;
    }
    return i;
}

折半查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int BinSearch(SSTable ST, KeyType key) {
    int L = 1, M;
    int H = ST.Length;
    while (L <= H) {
        M = (L + H)/2;
        if(ST.elem[M].key == key){
            return M;
        }else if(ST.elem[M].key > key){
            H = M - 1;
        }else{
            L = M + 1;
        }
    }
    return 0;
}

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int main() {
    SSTable *ST;
    int n;
    cout << "请输入表的长度: ";
    cin >> n;
    Create(&ST, n);
    getchar();
    cout << "请输入查找数据的关键字: ";
    int key;
    cin >> key;
    int sl = SeqSearch(*ST, key);
    int bl = SeqSearch(*ST, key);
    cout << "顺序查找: " << endl; 
    if (sl == 0) {
        cout << "查找失败" << endl;
    }else{
        cout << "数据在查找表中的位置为: " << sl << endl;
    }
    cout << "折半查找: " << endl; 
    if (bl == 0) {
        cout << "查找失败" << endl;
    }else{
        cout << "数据在查找表中的位置为: " << bl << endl;
    }
    return 0;
}