请选择 进入手机版 | 继续访问电脑版
查看: 413|回复: 0

[软件工程] 数据结构上机:实验五(顺序查找,二分查找)

686

主题

686

帖子

2071

积分

猿er

Rank: 1

积分
2071
发表于 2016-8-14 17:54:14
<无详细内容>
  1. /*
  2. * @文件:search.c
  3. * @内容:顺序查找,二分查找,文件存储。
  4. * @作者:Luke
  5. * @时间:2014.11.11
  6. */
  7. #include <stdio.h>
  8. #include <limits.h>
  9. #include <time.h>
  10. /*
  11. * 功能:从指定文件内输入一组int型数组。
  12. * 返回值:-1代表失败,0代表成功。
  13. */
  14. int init_file(char *in_file, int a[], int n) {
  15. FILE *fp = fopen(in_file, "r");
  16. if (!fp) {
  17. printf("Not such a file: %s\n", in_file);
  18. return -1;
  19. }
  20. int i;
  21. // 读入数组长度,再读入数据。
  22. fscanf(fp, "%d", &n);
  23. for (i = 0; i < n; i++) {
  24. fscanf(fp, "%d", a+i);
  25. }
  26. printf("读取数据成功!\n");
  27. fclose(fp);
  28. return 0;
  29. }
  30. /*
  31. * 功能:测试,产生0~99的随机数,并存入文件
  32. */
  33. int generate_data(char *out_file, int n) {
  34. FILE *fp = fopen(out_file, "w");
  35. if (!fp) {
  36. printf("Not such a file: %s\n", out_file);
  37. return -1;
  38. }
  39. int i;
  40. time_t second = 0;
  41. // 第一行写随机数的个数。
  42. fprintf(fp, "%d\n", n);
  43. // 第二行写随机数,空格分开。
  44. // 时间函数time()的用法,返回1970.1.1.00:00:00到现在的秒数。
  45. // time_t其实就是unsigned int的另一个名字。
  46. second = time(NULL);
  47. srand(second);
  48. for (i = 1; i <= n; i ++)
  49. fprintf(fp, "%d ", rand()%100);
  50. printf("写入数据成功!\n");
  51. fclose(fp);
  52. return 0;
  53. }
  54. /*
  55. * 功能:在长度为n的数组a内,顺序查找指定的数x。
  56. * 返回值:如果查找成功,则返回数组下标,否则返回最小整型INT_MIN。
  57. */
  58. int sequence_search(int a[], int n, int x) {
  59. int i;
  60. for (i = 0; i < n; i ++) {
  61. if (a[i] == x)
  62. return i;
  63. }
  64. return INT_MIN;
  65. }
  66. /*
  67. * 功能:排序(由小到大),应用在二分查找中。
  68. */
  69. void sort(int a[], int n) {
  70. // 直接冒泡好了。
  71. int i, j, temp;
  72. for (i = 1; i < n; i ++)
  73. for (j = 0; j < n-i; j ++) {
  74. if (a[j] > a[j+1]) {
  75. temp = a[j];
  76. a[j] = a[j+1];
  77. a[j+1] = temp;
  78. }
  79. }
  80. }
  81. /*
  82. * 功能:在长度为n从小到大排列的数组a内,二分查找指定的数x。
  83. * 返回值:如果查找成功,返回数组下标,否则返回最小整型INT_MIN
  84. */
  85. int binary_search(int a[], int r, int l, int x) {
  86. // 这个是递归函数的版本。
  87. /*
  88. if (r > l)
  89. return INT_MIN;
  90. int m = r + (l-r)/2;
  91. if (a[m] == x)
  92. return m;
  93. else if (a[m] > x)
  94. return binary_search(a, r, m-1, x);
  95. else
  96. return binary_search(a, m+1, l, x);
  97. */
  98. // 下面的版本是迭代,比上面要优。
  99. int m;
  100. while (r <= l) {
  101. m = r + (l-r)/2;
  102. if (a[m] == x)
  103. return m;
  104. else if (a[m] > x)
  105. l = m-1;
  106. else
  107. r = m+1;
  108. }
  109. return INT_MIN;
  110. }
  111. int main(void) {
  112. int a[10] = {23, 1, 30, 93, 12, 4, 98, 44, 20, 10};
  113. int i, temp;
  114. // 首先我们来产生10个0~99的随机数,存入文件data.txt。
  115. generate_data("data.txt", 10);
  116. printf("-------------------\n");
  117. // 然后读取data.txt数据存入数组a里。
  118. init_file("data.txt", a, 10);
  119. printf("-------------------\n");
  120. // 输出原始数据查看。
  121. printf("原始数据:");
  122. for (i = 0; i < 10; i ++)
  123. printf("%-3d", a[i]);
  124. printf("\n");
  125. printf("-------------------\n");
  126. // 顺序查找,用0~100的数据一次查找,并且输出结果!
  127. printf("顺序找结果:\n");
  128. printf("被查数\t结果\n");
  129. for (i = 0; i < 100; i ++) {
  130. temp = sequence_search(a, 10, i);
  131. if (temp == INT_MIN)
  132. printf("%-3d:\tfailed!\n", i);
  133. else
  134. printf("%-3d:\t%-3d\n", i, temp);
  135. }
  136. printf("-------------------\n");
  137. // 接下来由小到大排序。
  138. sort(a, 10);
  139. // 输出排序结果。
  140. printf("排序结果:\n");
  141. for (i = 0; i < 10; i ++)
  142. printf("%-3d", a[i]);
  143. printf("\n");
  144. printf("-------------------\n");
  145. // 二分查找,用0~100的数据进行查找,并且输出结果!
  146. printf("二分查找结果:\n");
  147. printf("被查数\t结果\n");
  148. for (i = 0; i < 100; i ++) {
  149. temp = binary_search(a, 0, 9, i);
  150. if (temp == INT_MIN)
  151. printf("%-3d:\tfailed!\n", i);
  152. else
  153. printf("%-3d:\t%-3d\n", i, temp);
  154. }
  155. printf("-------------------\n");
  156. printf("结束!\n");
  157. return 0;
  158. }
复制代码


回复

使用道具 举报