采用折半的方法在已经有序的字符串中找字符
采用折半的方法在已经有序的字符串中找字符
方法一：
程序代码如下：
#include"stdio.h"
#include"string.h"
int main ()
{
int n;
char a[20] = "abcdefghijk";
n = strlen(a)-1;
char ch;
int i, top, bot, mid;
printf ("Input a character\n");
scanf ("%c",&ch);
printf ("ch = \'%c\'\n",ch);
for (top = 0,bot = n;top <= bot; )
{
mid = (bot+top)/2;
if(ch ==a[mid])
{
printf("the position is %d\n",mid+1);
break;
}
else if(ch > a[mid])
top = mid+1;
else
bot = mid-1;
}
if(top > bot)
printf ("* *\n");
}
方法二：
源程序代码：
/*
2017年3月12日07:49:08
功能：采用折半的方法在已经有序的字符串中找字符
*/
#include"stdio.h"
#include"string.h"
int fun(char , int , int , char *); //声明一个fun函数
int main()
{
char input_string[100];
char ch;
int a = 0; //字符数组第一个元素的下标
printf("请按顺序输入一个字符串：");
gets(input_string); //input_string是待查找的字符串
printf("请输入你要查找的字符：");
scanf("%c", &ch);
int len = strlen(input_string) - 1; //字符串的元素总长度不包括结尾标识符'\0'的长度
printf("%c这个字符在字符串中的第%d个位置\n", ch, fun(ch, a, len, input_string)); //ch是需要在字符串中查找的字符，
}
int fun(char ch ,int a ,int len,char *s) //调用fun函数
{ //判断ch字符在字符串input_string的大致范围
//判断确定ch的位置，采用折半判断ch是否等于中间值
if (ch >= s[a] && ch <= s[len / 2 + a])
{
if (ch == s[len / 2 + a])
return a + len / 2 +1;
else //在小范围区间再一次采取折半
fun(ch,a,len / 2, s);
}
else
{
if (ch == s[len / 2 + a])
return a + len / 2 +1;
else
fun(ch, len / 2, len / 2 + a, s);
}
}
/*
总结：
在VC++6.0中显示的结果:
———————————————————————
请按顺序输入一个字符串：123456789
请输入你要查找的字符：5
5这个字符在字符串中的第5个位置
请按顺序输入一个字符串：12345678
请输入你要查找的字符：4
4这个字符在字符串中的第4个位置
———————————————————————
*/