一个折半查找的有关问题,希望大家帮忙!
一个折半查找的问题,希望大家帮忙!!!
include <stdio.h>
#include <malloc.h>
#include <conio.h>
#define SIZE 10
#define OK 1
#define OVERFLOW -2
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a) <(b))
typedef int KeyType;
typedef int Status;
typedef struct{
KeyType key;
char name[10];
}ElemType;
typedef struct{
ElemType *elem;
int length;
}SSTable;
Status Init_SSTable(SSTable *ST){
ST-> elem=(ElemType *)malloc(SIZE*sizeof(ElemType));
if(!ST-> elem)exit(OVERFLOW);
ST-> length=0;
return OK;
}
Status Search_Bin(SSTable ST,KeyType key,int n){
int low,high,mid;
low=1;high=n-1;
while(low <=high){
mid=(low+high)/2;
if(EQ(key,ST.elem[mid].key)) printf( "what you search is:%d ",ST.elem[mid].name);
else if(LT(key,ST.elem[mid].key)) high=mid-1;
else low=mid+1;
}
return 0;
}
void swap(int *a,int *b,char *c,char *d)
{ char name_tmp[10];
int t;
if(*a> =*b)
{
t=*a;
*a=*b;
*b=t;
strcpy(name_tmp,c);
strcpy(c,d);
strcpy(d,name_tmp);
}
}
void sort(ElemType *p,int n)
{ int i,j;
int *m,*q;
char *ap,*bp,c[10],d[10];
for(j=0;j <n-1;j++)
for(i=0;i <n-1;i++)
{ m=&((p+i)-> key);
q=&((p+i+1)-> key);
ap=((p+i)-> name);
bp=((p+i+1)-> name);
swap(m,q,ap,bp);
}
}
void print(SSTable ST,int n)
{ int i;
for(i=0;i <n;i++)
printf( "%d %s\n ",ST.elem[i].key,ST.elem[i].name);
}
void main()
{ int Key,i,n,a;
char *p,c[10];
ElemType *m;
SSTable *ST,Q;
clrscr();
ST=&Q;
p=c;
Init_SSTable(ST);
printf( "\nHow many elem do you want to input:\n ");
scanf( "%d ",&n);
(*ST).length=n;
printf( "input number and name:\n ");
for(i=0;i <n;i++)
{scanf( "%d %s ",&(ST-> elem[i].key),p);
strcpy(ST-> elem[i].name,p);}
printf( "\nWhat you input is:\n ");
print(*ST,n);
m=(ST-> elem);
sort(m,n);
printf( "\nAfter sort the elem is:\n ");
print(*ST,n);
printf( "\nwhich number do you want to fine :\n ");
scanf( "%d ",&Key);
Search_Bin(*ST,Key,n);
getch();
}
程序开始是先输入不是顺序排列的元素(包含:数字,字符串),然后进行排序成顺序的元素,到这里程序没有问题,接下来要对数据进行折半查找,就出现问题了,运行时会出现死循环,应该是出在折半查找的函数里面,请大家帮忙,谢谢了!!!
------解决方案--------------------
不需要改了。
还有,你用的是什么数组,竟然用low=1;high=n-1;而不是low = 0; high = n-1;
include <stdio.h>
#include <malloc.h>
#include <conio.h>
#define SIZE 10
#define OK 1
#define OVERFLOW -2
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a) <(b))
typedef int KeyType;
typedef int Status;
typedef struct{
KeyType key;
char name[10];
}ElemType;
typedef struct{
ElemType *elem;
int length;
}SSTable;
Status Init_SSTable(SSTable *ST){
ST-> elem=(ElemType *)malloc(SIZE*sizeof(ElemType));
if(!ST-> elem)exit(OVERFLOW);
ST-> length=0;
return OK;
}
Status Search_Bin(SSTable ST,KeyType key,int n){
int low,high,mid;
low=1;high=n-1;
while(low <=high){
mid=(low+high)/2;
if(EQ(key,ST.elem[mid].key)) printf( "what you search is:%d ",ST.elem[mid].name);
else if(LT(key,ST.elem[mid].key)) high=mid-1;
else low=mid+1;
}
return 0;
}
void swap(int *a,int *b,char *c,char *d)
{ char name_tmp[10];
int t;
if(*a> =*b)
{
t=*a;
*a=*b;
*b=t;
strcpy(name_tmp,c);
strcpy(c,d);
strcpy(d,name_tmp);
}
}
void sort(ElemType *p,int n)
{ int i,j;
int *m,*q;
char *ap,*bp,c[10],d[10];
for(j=0;j <n-1;j++)
for(i=0;i <n-1;i++)
{ m=&((p+i)-> key);
q=&((p+i+1)-> key);
ap=((p+i)-> name);
bp=((p+i+1)-> name);
swap(m,q,ap,bp);
}
}
void print(SSTable ST,int n)
{ int i;
for(i=0;i <n;i++)
printf( "%d %s\n ",ST.elem[i].key,ST.elem[i].name);
}
void main()
{ int Key,i,n,a;
char *p,c[10];
ElemType *m;
SSTable *ST,Q;
clrscr();
ST=&Q;
p=c;
Init_SSTable(ST);
printf( "\nHow many elem do you want to input:\n ");
scanf( "%d ",&n);
(*ST).length=n;
printf( "input number and name:\n ");
for(i=0;i <n;i++)
{scanf( "%d %s ",&(ST-> elem[i].key),p);
strcpy(ST-> elem[i].name,p);}
printf( "\nWhat you input is:\n ");
print(*ST,n);
m=(ST-> elem);
sort(m,n);
printf( "\nAfter sort the elem is:\n ");
print(*ST,n);
printf( "\nwhich number do you want to fine :\n ");
scanf( "%d ",&Key);
Search_Bin(*ST,Key,n);
getch();
}
程序开始是先输入不是顺序排列的元素(包含:数字,字符串),然后进行排序成顺序的元素,到这里程序没有问题,接下来要对数据进行折半查找,就出现问题了,运行时会出现死循环,应该是出在折半查找的函数里面,请大家帮忙,谢谢了!!!
------解决方案--------------------
不需要改了。
还有,你用的是什么数组,竟然用low=1;high=n-1;而不是low = 0; high = n-1;