贺老师教学链接 C语言及程序设计进阶 本课讲解
顺序查找
#include <stdio.h> #define SIZE 10 int main( ) { int d[SIZE]={34, 43, 98, 72, 12, 47, 31, 43, 1, 78}; /*也可以通过键盘输入等方式给出数据*/ int i; int key; /*key表示待查找数据*/ int index=-1; /*用index表示查找结果——关键字key出现的位置*/ printf("Input a key you want to search: "); scanf("%d" , &key); /*输入要查找的关键字*/ for(i=0; i<SIZE; i++) if(key == d[i]) /*在循环中逐个比较，如果key与某d[i]相等，表示找到了*/ { index = i; /*用index记下下标*/ break; /*退出循环，不再继续比较*/ } if(index >= 0) /*index >= 0，循环一定是由break跳出的，代表找到了。这个条件也可以用i<SIZE代替*/ printf("The index of the key is %d .\n", index); else /*没有找到，index仍保持-1*/ printf("Not found.\n"); return 0; }二分查找的实现
#include <stdio.h> #define N 10 int main( ) { int data[N] = {1, 3, 9, 12, 32, 41, 45, 62, 75, 77};/*通过初始化给出元素值*/ int first, last, mid; /*查找中记录下标的3个变量*/ int key; /*待查工的关键字*/ int index=-1; /*记录查找到的元素的下标，初值-1表示没有找到*/ printf("Input a key you want to search: "); scanf("%d" , &key); /*输入待查找的关键字*/ first=0, last=N-1; /*first和last分别是首元素和末元素的下标*/ while(first<=last) /*若first>last，也就意味着循环该结束了，找不到，不必找了*/ { mid=(first+last)/2; /*中间位置的下标*/ if(data[mid]==key) /*若相等，记录下标并退出*/ { index=mid; break; } else if(key<data[mid]) /*下一轮将在前半段找，故last=mid-1*/ last=mid-1; else /*下一轮将在后半段找，故first=mid+1*/ first=mid+1; } if(index >= 0) /*输出结果*/ printf("The index of the key is %d .\n", index); else printf("Not found.\n"); return 0; }不用比较的查找算法
#include <stdio.h> int search(int h[], int key); void store(int h[], int data); int main() { int data[1000]={0}; int m, n; int i; for (i = 0; i < 6; i++) { scanf("%d", &n); store(data, n); } scanf("%d", &m); int result = search(data, m); if (result) printf("在数组中找到.\n"); else printf("没有此数据!\n"); return 0; } int search(int d[], int key) { return d[key]; } void store(int d[], int n) { d[n]=n; }用”除留余数”哈希函数定址，开放地址法解决冲突的哈希方法
#include <stdio.h> void insertHash(int h[], int len, int key); int searchHash(int h[], int len, int key); #define N 13 /*N取素数*/ int main() { int data[N]= {0}; /*本例中数组中要存储的均为正数，初始化为全0表示值为空*/ int key; /*待查关键字*/ int i; for (i = 0; i < 6; i++) /*先演示存储数据*/ { scanf("%d" , &key); insertHash(data, N, key); /*将值为key的关键字存入长度为N的数组data中*/ } printf("Input a key you want to search: "); scanf("%d" , &key); /*输入待查找的关键字*/ int index = searchHash(data,N, key); /*在长度为N的数组data中查找关键字key*/ if(index >= 0) /*输出结果*/ printf("The index of the key is %d .\n", index); else printf("Not found.\n"); return 0; } /*将值为key的关键字存入长度为N的数组data中*/ void insertHash(int h[], int len, int key) { int i; i = key % len; /*除留余数法：计算出存储数据的位置*/ while (h[i] != 0) /*如果该位置已经存储了数据，即发生了冲突*/ { i++; /*用线性探测法找后面的位置*/ i %= len; /*如果越界了，将试探数组最开始的位置*/ } h[i] = key; /*存储关键字key*/ } /*在长度为N的数组data中查找关键字key，返回值为存储数据的位置，-1代表没找到*/ int searchHash(int h[], int len, int key) { int i; i = key % len; /*除留余数法：计算出存储数据的位置*/ while (h[i] != 0 && h[i] != key) /*确定的位置上不为空，也不是要找的数，这是由当时存储数据时发生过冲突所致*/ { i++; /*也用线性探测法找后面的位置*/ i %= len; /*如果越界了，将试探数组最开始的位置*/ } if (h[i] == 0) /*找到的是空元素，说明没有找到*/ i = -1; /*返回-1将代表没有找到*/ return i; /*返回结果*/ }