编程实现顺序查找("哨兵"的使用)与折半查找(有序表)算法.

发布网友 发布时间：2022-04-29 10:50

我来回答

共1个回答

热心网友 时间：2022-06-26 11:33

顺序查找
#include
<stdio.h>
#include
<stdlib.h>
#define
MAX_LENGTH
100typedef
int
KeyType;
typedef
struct
{
KeyType
*elem;
int
length;
}SSTable;
//顺序表的存储结构
int
Search_Seq(SSTable
ST,
KeyType
key){
int
i;
ST.elem[0]
=
key;
//“哨兵”，如果顺序表中不存在要查找的数据的话，则查找指针必定指向该哨兵
for(i
=
ST.length;
ST.elem[i]
!=
key;
i--)
;
return
i;
//找到的话，则i
!=
0,否则i
=
0
}
void
main()
{
int
i,
key;
SSTable
T;
T.elem
=
(KeyType
*)malloc(sizeof(KeyType));
printf("How
Many
Entries
Do
You
Want
input\n");
scanf("%d",
&T.length);
for(i=1;
i<=T.length;
i++){
printf("Please
input
the
%dth
entries
\n",
i);
scanf("%d",
&T.elem[i]);
}
for
(i=1;
i<=T.length;
i++)
printf("%5d",T.elem[i]);
//显示已经输入的所有数据
printf("\nPlease
input
the
data
you
want
to
search\n");
scanf("%d",
&key);
i
=
Search_Seq(T,key);
printf("the
search
data
is
locate
the
%dth(0
indicate
can
not
find)\n",i);
}
折半查找
#include
<stdio.h>
#include
<stdlib.h>
int
binSearch(const
int
*Array,int
start,int
end,int
key)
{
int
left,right;
int
mid;
left=start;
right=end;
while
(left<=right)
{
mid=(left+right)/2;
if
(key<Array[mid])
{
right=mid-1;
}
else
if(key>Array[mid])
{
left=mid+1;
}
else
return
mid;
}
return
-1;
}
void
main()
{
int
A[]={10,20,30,40,50,60,70,80};
int
n;
printf("Please
search
num:");
scanf("%d",&n);
int
index=binSearch(A,0,8,n);
if(index==-1)
{
printf("no
num");
}
else
{
printf("index=%d",index+1);
}
}