【C语言数据结构】查找-顺序查找&折半查找

---

---

代码实现

#include
#include
#include

//将数据元素类型标为int
typedef int ElemType;

//定义线性表
typedef struct{
    //数据元素数组(0号留空，作为"哨兵"，方便查找)
    ElemType *elem;
    //线性表长度
    int TableLen;
}SSTable;

//顺序查找(非递归算法)
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0] = key; //哨兵

    //数组下标
    int i;

    for(i = ST.TableLen;ST.elem[i]!=key;--i);

    return i;
}

//折半查找(非递归算法)
int Binary_Search(SSTable ST,ElemType key){
    //定义前后指针
    int low = 0,high = ST.TableLen;
    //定义中间指针
    int mid;

    while(low<=high){
        mid = (low+high)/2;
        if(ST.elem[mid] == key)
            return mid;
        else if(ST.elem[mid] > key)
            high = mid-1;
        else
            low = mid+1;
    }
    return -1;
}

//折半查找(递归算法)（初始调用时，low为1，high为ST.TableLen）
int Binary_Search_Rec(SSTable ST,ElemType key,int low,int high){
    if(low>high)
        return -1;
    int mid = (low+high)/2;
    if(ST.elem[mid] == key)
        return mid;
    else if(ST.elem[mid] > key)
        return Binary_Search_Rec(ST,key,low,mid-1);
    else
        return Binary_Search_Rec(ST,key,mid+1,high);
}

//初始化线性表
void InitTable(SSTable *ST){
    ST->TableLen = 0;
}

//添加线性表元素
bool AddElem(SSTable *ST,ElemType elem){
    //保留0号位为空
    ST->elem[ST->TableLen+1] = elem;

    //线性表长度+1
    ST->TableLen++;
}

int main(){
    //定义数组下标
    int index;

    //创建顺序表
    SSTable ST;

    //初始化线性表
    InitTable(&ST);

    //添加线性表元素
    AddElem(&ST,1);
    AddElem(&ST,4);
    AddElem(&ST,3);
    AddElem(&ST,2);
    AddElem(&ST,9);
    AddElem(&ST,8);
    AddElem(&ST,10);
    AddElem(&ST,7);
    AddElem(&ST,6);
    AddElem(&ST,5);
    AddElem(&ST,13);
    AddElem(&ST,421);
    AddElem(&ST,999);

    //顺序查找
    printf("顺序查找：\n");
    index = Search_Seq(ST,13);
    if(index == 0)
        printf("未找到数据元素13\n");
    else
        printf("数据元素13的位置为%d\n",index);

    index = Search_Seq(ST,19);
    if(index == 0)
        printf("未找到数据元素19\n");
    else
        printf("数据元素19的位置为%d\n",index);
    printf("\n");

    //折半查找(非递归)
    printf("折半查找(非递归)：\n");
    index = Binary_Search(ST,13);
    if(index == -1)
        printf("未找到数据元素13\n");
    else
        printf("数据元素13的位置为%d\n",index);

    index = Binary_Search(ST,19);
    if(index == -1)
        printf("未找到数据元素19\n");
    else
        printf("数据元素19的位置为%d\n",index);
    printf("\n");

    //折半查找(递归)
    printf("折半查找(递归)：\n");
    index = Binary_Search_Rec(ST,13,1,ST.TableLen);
    if(index == -1)
        printf("未找到数据元素13\n");
    else
        printf("数据元素13的位置为%d\n",index);

    index = Binary_Search_Rec(ST,19,1,ST.TableLen);
    if(index == -1)
        printf("未找到数据元素19\n");
    else
        printf("数据元素19的位置为%d\n",index);
    printf("\n");

}
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144