C语言中的折半查找法的一些小问题

ZXH_KK

/*出现的问题是：再准备输入是否继续进行查找时，还没有进行输入，程序就自行打印多了continue or not<y/n>? 这句话，也就是没输入，程序就自行运行完一遍了*/
程序已经打好，请各位大神帮帮忙，大家可输入12或13来看看程序错误的地方，谢谢大家

#include <stdio.h>  //折半查找法
#define N 15
void main()
{
        char c;
        int n,bott,top,mid = 0,sign = 1,local = 1,k = 1;
        int a[N] = {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29};
        bott = 0, top = N-1 ;
        printf("input number to look for:   ");
        scanf("%d",&n);
        while(n<a[0]||n>a[N-1])   //如果用户输入超出范围，提示他重新输入
        {
                printf("Input error!!! Please input again:   ");
                scanf("%d",&n);
        }
        while(k)                  //k的作用：当用户不再进行查找时（后面），令k=0，结束查找
        {
                while(bott<=top&&sign == 1)
                {
                        mid = (bott + top )/2;
                        if( a[mid] > n )
                        {
                                top = mid -1;
                        }
                        else if( a[mid]<n )
                        {
                                bott = mid +1;
                        }
                        else if( a[mid] == n)
                        {
                                printf("第%d个\n",mid+1);
                                sign = 0;                   //结束循环
                                local = 0;                  //为下一步（说明找不到）做准备
                        }
                }
                 if(local == 1)
                 { printf("cannot find %d !!!\n",n);
                 }

                printf("continue or not<y/n>? ");  //问用户是否继续查找，如果是（y）,继续输入数字进行查找。否则（n），令k=0，结束查找
                scanf("%c",&c);
                if( c == 'n')
                        k = 0;
                if( c == 'y')
                {
                        printf("input number to look for:   ");
                        scanf("%d",&n);
                        while(n<a[0]||n>a[N-1])
                        {
                                printf("Input error!!! Please input again:   ");
                                scanf("%d",&n);
                        }
                }
        }
}

小新110

真是汗颜，这个程序我也是查了资料才搞明白问题出在什么地方。
关键问题就在于第二个调用 scanf("%c",&c); 的地方。
在你第一次输入12+回车的时候，系统的缓冲区会存放有三个字符，1、2、回车。
而第二次等待输入的地方就会自动取回车来完成程序的输入。

改正：在 scanf("%c",&c); 之前加 getchar()把缓冲区中的回车取走。

username_badboy

楼上说的很对，但是这样处理是不行的，你可以试试，输入y or n 都是错的。
我的做法是在输出前清空一下缓存：
fflush(stdin);//vc中使用这个函数就能搞定
printf("continue or not<y/n>? ");  //问用户是否继续查找，如果是（y）,继续输入数字进行查找。否则（n），令k=0，结束查找
scanf("%c",&c);
原理你可以看看这篇文章：http://blog.sina.com.cn/s/blog_64b236da0100vfzv.html
这样似乎就能解决你上面的问题了，但是你的折半查找（估计就是二分查找了）的算法可能有问题，你可以测试一下。。。

ZXH_KK

小新110 发表于 2012-12-22 10:08

                               
登录/注册后可看大图

真是汗颜，这个程序我也是查了资料才搞明白问题出在什么地方。
关键问题就在于第二个调用 scanf("%c",&c); ...

好，谢谢你的解答。

ZXH_KK

小新110 发表于 2012-12-22 10:08

                               
登录/注册后可看大图

真是汗颜，这个程序我也是查了资料才搞明白问题出在什么地方。
关键问题就在于第二个调用 scanf("%c",&c); ...

请问你查的是什么资料，在哪里找的？

ZXH_KK

username_badboy 发表于 2012-12-22 13:39

                               
登录/注册后可看大图

楼上说的很对，但是这样处理是不行的，你可以试试，输入y or n 都是错的。
我的做法是在输出前清空一下缓存 ...

上面的没有问题啊？我试过是行的。但是我使用了你的方法，结果失败了，出现了以下提示
Linking...
折半查找法.obj : error LNK2001: unresolved external symbol _fflushi
Debug/折半查找法.exe : fatal error LNK1120: 1 unresolved externals
执行 link.exe 时出错.

username_badboy

ZXH_KK 发表于 2012-12-23 00:17

                               
登录/注册后可看大图

上面的没有问题啊？我试过是行的。但是我使用了你的方法，结果失败了，出现了以下提示
Linking...
折半 ...

奥，那可能就是编译器不一样引起的问题，我这儿执行他那个是不能得到正确的结果的。。。

ZXH_KK

username_badboy 发表于 2012-12-23 11:36

                               
登录/注册后可看大图

奥，那可能就是编译器不一样引起的问题，我这儿执行他那个是不能得到正确的结果的。。。

哦，还想请教一下，我的算法哪里出现问题了，虽然能运行，但是想听听你的意见

ZXH_KK

ZXH_KK 发表于 2012-12-23 00:14

                               
登录/注册后可看大图

请问你查的是什么资料，在哪里找的？

想问你一下，通常出现以下句子是出了什么错
Linking...
折半查找法.obj : error LNK2001: unresolved external symbol _fflushi
Debug/折半查找法.exe : fatal error LNK1120: 1 unresolved externals
执行 link.exe 时出错.

z____

ZXH_KK 发表于 2012-12-23 00:17

                               
登录/注册后可看大图

上面的没有问题啊？我试过是行的。但是我使用了你的方法，结果失败了，出现了以下提示
Linking...
折半 ...

仔细看提示, _fflushi 你的函数名输错了,不是人家的问题fflush没有后边的i

username_badboy

ZXH_KK 发表于 2012-12-23 12:53

                               
登录/注册后可看大图

哦，还想请教一下，我的算法哪里出现问题了，虽然能运行，但是想听听你的意见

好，我来帮你解答，好心好意的帮你解决问题。没想到你这个态度。

1.那个报错问题，我没仔细看，下面那个兄弟帮我说了，你函数名抄错了。。。
2.我说之前那个加getchar()的那个问题，一看就知道你是没有好好测试，先输入11，回车，再输入y，回车，再输入11，回车，你就能看到错误的结果了。但是这个错误造成的原因是因为你的算法问题，他这样的处理方式也是对的。
3.核心问题就是你的算法问题了，我还真不信你那样就能得到正确的结果了，自己看看我下面帮你改正的代码跟你的有什么不同。

1. #include <stdio.h>  //折半查找法
   
2. #define N 15
   
3. void main()
   
4. {
   
5.         char c;
   
6.         int n,bott,top,mid = 0,sign = 1,local = 1,k = 1;
   
7.         int a[N] = {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29};
   
8.         bott = 0, top = N-1 ;
   
9.         printf("input number to look for:   ");
   
10.         scanf("%d",&n);
    
11.         while(n<a[0]||n>a[N-1])   //如果用户输入超出范围，提示他重新输入
    
12.         {
    
13.                 printf("Input error!!! Please input again:   ");
    
14.                 scanf("%d",&n);
    
15.         }
    
16.         while(k)                  //k的作用：当用户不再进行查找时（后面），令k=0，结束查找
    
17.         {
    
18.                 //这里你下面的循环将这些值改变了，难道你不给他还原吗
    
19.                 sign = 1;
    
20.                 local = 1;
    
21.                 bott = 0;
    
22.                 top = N-1;
    
23. 
    
24.                 while(bott<=top&&sign == 1)
    
25.                 {
    
26.                         mid = (bott + top )/2;
    
27.                         if( a[mid] > n )
    
28.                         {
    
29.                                 top = mid -1;
    
30.                         }
    
31.                         else if( a[mid]<n )
    
32.                         {
    
33.                                 bott = mid +1;
    
34.                         }
    
35.                         else if( a[mid] == n)
    
36.                         {
    
37.                                 printf("第%d个\n",mid+1);
    
38.                                 sign = 0;                   //结束循环
    
39.                                 local = 0;                  //为下一步（说明找不到）做准备
    
40.                         }
    
41.                 }
    
42.                 if(local == 1)
    
43.                 {
    
44.                         printf("cannot find %d !!!\n",n);
    
45.                 }
    
46.                 fflush(stdin);//或者getchar()
    
47.                 printf("continue or not<y/n>? ");  //问用户是否继续查找，如果是（y）,继续输入数字进行查找。否则（n），令k=0，结束查找
    
48.                 scanf("%c",&c);
    
49.                 if( c == 'n')
    
50.                         k = 0;
    
51.                 if( c == 'y')
    
52.                 {
    
53.                         printf("input number to look for:   ");
    
54.                         scanf("%d",&n);
    
55.                         while(n<a[0]||n>a[N-1])
    
56.                         {
    
57.                                 printf("Input error!!! Please input again:   ");
    
58.                                 scanf("%d",&n);
    
59.                         }
    
60.                 }
    
61.         }
    
62. }

复制代码

ZXH_KK

username_badboy 发表于 2012-12-23 13:49

                               
登录/注册后可看大图

好，我来帮你解答，好心好意的帮你解决问题。没想到你这个态度。

1.那个报错问题，我没仔细看，下面那 ...

不好意思，可能是我输入有问题才导致你认为我态度有问题，真心对不起。你为我的问题想了真么多，为我解答，我很感激。谢谢你的指导

username_badboy

ZXH_KK 发表于 2012-12-23 20:16

                               
登录/注册后可看大图

不好意思，可能是我输入有问题才导致你认为我态度有问题，真心对不起。你为我的问题想了真么多，为我解答 ...

应该是我该对你道歉才对，可能是今天心情有点烦躁的缘故，so，看了你的回复都以为它带有攻击性，刚刚回去一看你的回复，怎么感觉一下就变了。太对不起你了。。。

ZXH_KK

username_badboy 发表于 2012-12-23 21:28

                               
登录/注册后可看大图

应该是我该对你道歉才对，可能是今天心情有点烦躁的缘故，so，看了你的回复都以为它带有攻击性，刚刚回去 ...

没事没事，你心情烦躁也继续帮我解答，太感谢你了:hug: