- /*
- * @文件:search.c
- * @内容:顺序查找,二分查找,文件存储。
- * @作者:Luke
- * @时间:2014.11.11
- */
- #include <stdio.h>
- #include <limits.h>
- #include <time.h>
- /*
- * 功能:从指定文件内输入一组int型数组。
- * 返回值:-1代表失败,0代表成功。
- */
- int init_file(char *in_file, int a[], int n) {
- FILE *fp = fopen(in_file, "r");
- if (!fp) {
- printf("Not such a file: %s\\n", in_file);
- return -1;
- }
- int i;
- // 读入数组长度,再读入数据。
- fscanf(fp, "%d", &n);
- for (i = 0; i < n; i++) {
- fscanf(fp, "%d", a+i);
- }
- printf("读取数据成功!\\n");
- fclose(fp);
- return 0;
- }
- /*
- * 功能:测试,产生0~99的随机数,并存入文件
- */
- int generate_data(char *out_file, int n) {
- FILE *fp = fopen(out_file, "w");
- if (!fp) {
- printf("Not such a file: %s\\n", out_file);
- return -1;
- }
- int i;
- time_t second = 0;
- // 第一行写随机数的个数。
- fprintf(fp, "%d\\n", n);
- // 第二行写随机数,空格分开。
- // 时间函数time()的用法,返回1970.1.1.00:00:00到现在的秒数。
- // time_t其实就是unsigned int的另一个名字。
- second = time(NULL);
- srand(second);
- for (i = 1; i <= n; i ++)
- fprintf(fp, "%d ", rand()%100);
- printf("写入数据成功!\\n");
- fclose(fp);
- return 0;
- }
- /*
- * 功能:在长度为n的数组a内,顺序查找指定的数x。
- * 返回值:如果查找成功,则返回数组下标,否则返回最小整型INT_MIN。
- */
- int sequence_search(int a[], int n, int x) {
- int i;
- for (i = 0; i < n; i ++) {
- if (a[i] == x)
- return i;
- }
- return INT_MIN;
- }
- /*
- * 功能:排序(由小到大),应用在二分查找中。
- */
- void sort(int a[], int n) {
- // 直接冒泡好了。
- int i, j, temp;
- for (i = 1; i < n; i ++)
- for (j = 0; j < n-i; j ++) {
- if (a[j] > a[j+1]) {
- temp = a[j];
- a[j] = a[j+1];
- a[j+1] = temp;
- }
- }
- }
- /*
- * 功能:在长度为n从小到大排列的数组a内,二分查找指定的数x。
- * 返回值:如果查找成功,返回数组下标,否则返回最小整型INT_MIN
- */
- int binary_search(int a[], int r, int l, int x) {
- // 这个是递归函数的版本。
- /*
- if (r > l)
- return INT_MIN;
- int m = r + (l-r)/2;
- if (a[m] == x)
- return m;
- else if (a[m] > x)
- return binary_search(a, r, m-1, x);
- else
- return binary_search(a, m+1, l, x);
- */
- // 下面的版本是迭代,比上面要优。
- int m;
- while (r <= l) {
- m = r + (l-r)/2;
- if (a[m] == x)
- return m;
- else if (a[m] > x)
- l = m-1;
- else
- r = m+1;
- }
- return INT_MIN;
- }
- int main(void) {
- int a[10] = {23, 1, 30, 93, 12, 4, 98, 44, 20, 10};
- int i, temp;
- // 首先我们来产生10个0~99的随机数,存入文件data.txt。
- generate_data("data.txt", 10);
- printf("-------------------\\n");
- // 然后读取data.txt数据存入数组a里。
- init_file("data.txt", a, 10);
- printf("-------------------\\n");
- // 输出原始数据查看。
- printf("原始数据:");
- for (i = 0; i < 10; i ++)
- printf("%-3d", a[i]);
- printf("\\n");
- printf("-------------------\\n");
- // 顺序查找,用0~100的数据一次查找,并且输出结果!
- printf("顺序找结果:\\n");
- printf("被查数\\t结果\\n");
- for (i = 0; i < 100; i ++) {
- temp = sequence_search(a, 10, i);
- if (temp == INT_MIN)
- printf("%-3d:\\tfailed!\\n", i);
- else
- printf("%-3d:\\t%-3d\\n", i, temp);
- }
- printf("-------------------\\n");
- // 接下来由小到大排序。
- sort(a, 10);
- // 输出排序结果。
- printf("排序结果:\\n");
- for (i = 0; i < 10; i ++)
- printf("%-3d", a[i]);
- printf("\\n");
- printf("-------------------\\n");
- // 二分查找,用0~100的数据进行查找,并且输出结果!
- printf("二分查找结果:\\n");
- printf("被查数\\t结果\\n");
- for (i = 0; i < 100; i ++) {
- temp = binary_search(a, 0, 9, i);
- if (temp == INT_MIN)
- printf("%-3d:\\tfailed!\\n", i);
- else
- printf("%-3d:\\t%-3d\\n", i, temp);
- }
- printf("-------------------\\n");
- printf("结束!\\n");
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/1603201511893.html
来源: http://www.codesnippet.cn/detail/1603201511893.html