一、【实验目的】

              掌握顺序查找（设置监视哨）、折半查找等典型的查找算法

二、【实验内容】

实现顺序查找算法，将顺序表的第一个位置设为监视哨。

顺序查找表定义为：

-------------------------

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

typedef struct{
    int *elem;
    int length;
}SSTable;

main()
{
    SSTable ST;
    int i,num,mykeyname,flag;
int search(SSTable *ST,int mykeyname);
int search2(SSTable *ST,int mykeyname);

    printf("size:");
    scanf("%d",&ST.length);
    ST.elem=(int*)malloc(sizeof(int)*(ST.length));
    printf("numbers:");
    for(i=1;i<=ST.length-1;i++)
    {
        scanf("%d",&num);
        ST.elem[i]=num;
        printf("%d ",ST.elem[i]);
    }
    printf("mykeynameword:");
    scanf("%d",&mykeyname);
    ST.elem[0]=mykeyname;
    flag=0;

flag=search2(&ST,mykeyname);

    if (flag) printf("ok. position:%d",flag);
    else
    printf("not found");
getch();
}

//顺序查找
int search(SSTable *ST,int mykeyname)
{
int i=ST->length-1;
while (ST->elem[i]!=mykeyname) i--;
return i;
}

//折半查找
int search2(SSTable *ST,int mykeyname)
{
int p,q,i;
p=1;
q=ST->length-1;
i=(p+q)/2;
while (ST->elem[i]!=mykeyname)
{
   if (p==q) break;
   i=(p+q)/2;
   if (mykeyname>ST->elem[i]) p=i+1;
   else if (mykeyname<ST->elem[i]) q=i-1;
   if (p==q) {i=p;break;};
}
if (ST->elem[i]!=mykeyname) i=0;

return i;
}