求助,二分查找的递归调用出现了死循环。(真心求教)
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define size 1000
#define error -1
#define ok 0
#define Status int
int m,n;
typedef char ElemType;
typedef struct Sqlist
{
char *data;
int length;
} Sqlist;
Status InitList(Sqlist &l) //初始化一个顺序表
{
l.data = (char *)malloc(size*sizeof(char));
l.length = 0;
cout<<"\n";
return ok;
}
Status Input(Sqlist &l) //读取文档的内容,并存入表中
{
FILE *f;
int i = 0;
char ch;
char *filename = "E://123.txt";
f = fopen(filename,"r");
if(f == NULL)
{
cout<<"\t\t文件读取失败!\n";
return error;
}
else
{
while(!feof(f)) //数据的读入把数据存入数组中
{
ch = fgetc(f);
l.data[i] = ch;
i ++ ;
if(i >= size)
{
cout<<"\t\t内存不足!\n"<<endl;
break;
}
}
m = i - 1;
cout<<"\n";
fclose(f);
}
return ok;
}
Status Output(Sqlist &l) //读出数据
{
Input(l);
cout<<"\t内容为 : "<<"\n"<<endl;
cout<<"\t";
for(int i = 0; i < m; i++)
cout<<l.data[i];
cout<<"\n\n";
cout<<"\t整理后的排序为:\n\n";
sort(l.data,l.data+m);
cout<<"\t";
for(int i = 0 ; i < m; i++)
cout<<l.data[i]<<" ";
cout<<"\n\n";
return ok;
}
Status Search_Bin(Sqlist &l,char bh,int low,int higth,int count) //递归调用二分
{
// double asl;
int mid = (low+higth)/2;
cout<<"\t"<<mid;
int fale = 1;
while(fale)
{
if(low>higth&&higth<0)
fale = 0;
if(bh == l.data[mid])
count++;
cout<<l.data[mid]<<endl;
if((bh < l.data[mid])&&(low >= 0)&&(higth >= low))
{
higth = mid - 1;
Search_Bin(l,bh,low,higth,count);
}
else if((bh > l.data[mid])&&(low >= 0)&&(low <= higth))
{
low = mid + 1;
Search_Bin(l,bh,low,higth,count);
}
}
n = count;
return ok;
}
int main()
{
int k = 1;
int i;
Sqlist l;
ElemType ch;
int low;
int higth,count = 0;
cout<<"$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n";
cout<<"$$$$$$$$$$$$$$$ $$$$$$$$$$$$$$$\n";
cout<<"$$$$$$$$$$ $$$$$$$$$$\n";
cout<<"$$$$$$ 请输入操作 $$$$$$\n";
cout<<"$$$$ (0)建立顺序表 $$$$\n";
cout<<"$$ (1)读取程序代码 $$\n";
cout<<"$$ (2)显示代码 $$\n";
cout<<"$$$$ (3)查找的关键字 $$$$\n";
cout<<"$$$$$$ (4)退出 $$$$$$\n";
cout<<"$$$$$$$$$$ $$$$$$$$$$\n";
cout<<"$$$$$$$$$$$$$$$ $$$$$$$$$$$$$$$\n";
cout<<"$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n";
cout<<""<<endl;
while(k)
{
cout<<"\t请输入指令 :";
cin>>i;
if(i == 4)
break;
switch(i)
{
case 0:
InitList(l);
cout<<"\t表已经建立成功!\n"<<endl;
break;
case 1:
Input(l);
cout<<"\t程序已经读取!\n"<<endl;
break;
case 2:
Output(l);
cout<<"\t程序已经读取完毕!\n"<<endl;
cout<<"\t长度为:"<<m<<endl;
cout<<"\n";
break;
case 3:
low = 0;
higth = m - 1;
cout<<"\n";
cout<<"\t请输入要查找的数 : ";
cin>>ch;
cout<<"\n";
Search_Bin(l,ch,low,higth,count);
cout<<"\t"<<ch<<" 共出现 "<<n<<" 次 !\n"<<endl;
break;
default:
cout<<"\t指令错误!"<<endl;
continue;
}
}
exit(ok);
}
分享到:
[解决办法]
用递归遍历也没关系,别用二分查找了,查找是想要某一个值的位置。递归的话我觉得循环就没必要了,记得要明确递归函数的返回条件
[解决办法]
“给定一个小点的输入,完整单步跟踪(同时按Alt+7键查看Call Stack里面从上到下列出的对应从里层到外层的函数调用历史)一遍。”是理解递归函数工作原理的不二法门!
递归函数关注以下几个因素
·退出条件
·参数有哪些
·返回值是什么
·局部变量有哪些
·全局变量有哪些
·何时输出
·会不会导致堆栈溢出