/ 75.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<stdio.h>
#include"malloc.h"
typedef struct
{ int key; // 关键字域
} Key;
typedef struct{
int mykey;
int link;
}Sk;
typedef struct
{ Key *elem; // 数据元素存储空间基址，建表时
// 按实际长度分配，0号单元留空
int length;
}SSTable;
typedef struct{
Sk *elem;
int length;
}SYTable;
int init(SSTable *ST,int i)//初始化线性表
{
ST->length=i;
ST->elem=(Key*)malloc(i*sizeof(Key));
for(int j=1;j<=i;j++)
{
ST->elem[j].key=j;
}
return 1;
}
int initsy(SYTable *T,int i)//初始化索引表
{
T->length=i;
T->elem=(Sk *)malloc(i*sizeof(Sk));
for(int j=1;j<=i;j++)
{
T->elem[j].mykey=j*10; //meiyikuai changdu
T->elem[j].link=j*10-9; // diyigeshu
}
return 1;
}
void PPrint(SSTable *ST)
{
int k=0;
for(int i=1;i<=ST->length;i++)
{
printf("%d ",ST->elem[i]);k++;
if(k%10==0)printf("\n ");
}
}
int EQ(int e,int k)//判断两数是否相等
{
if(e==k) return 1;
else return 0;
}
int count=0;
int Search_seq(SSTable ST,int key)//顺序表查询
{
ST.elem[0].key=key;count++;
for(int i=ST.length;!EQ(ST.elem[i].key,key);--i) count++;
return i;
}
int Search_Bin(SSTable ST,int key)//折半查找查询
{
int mid;
int low=1; int high=ST.length;
while(low<=high)
{
mid=(low+high)/2; count++;
if(EQ(key,ST.elem[mid].key)) return mid;
else if(key<ST.elem[mid].key) high=mid-1;
else low=mid+1;
}
return 0;
}
int Search_sy(SSTable ST,SYTable SY,int key)
{
int i,j,k;
for(i=1;i<=5;i++)
{
count++;
if(key<=SY.elem[i].mykey)
{
j=SY.elem[i].link;
k=SY.elem[i].link+10;
for(;key!=ST.elem[k].key&&k>=j;--k) count++;
if(k<j) return 0;
return k;
}
}
return 0;
}
int main()
{
int x,i;
SSTable *t=(SSTable *)malloc(sizeof(SSTable));
SYTable *s=(SYTable *)malloc(sizeof(SYTable));
init(t,50);
initsy(s,5);
printf("表中依次的元素是：\n");
PPrint(t);
while(true)
{
printf("输入要查找的元素：");
scanf("%d",&x);
if(i=Search_seq(*t,x))
printf("该元素在第%d位置，顺序查询次数为%d。\n",i,count);
else
printf("没有这个数,顺序查询次数为%d。\n",count);
count=0;
if(i=Search_Bin(*t,x))
printf("该元素在第%d位置，折半查询次数为%d。\n",i,count);
else
printf("没有这个数,折半查询次数为%d。\n",count);
count=0;
if(i=Search_sy(*t,*s,x))
printf("该元素在第%d位置，分块查询次数为%d。\n",i,count);
else
printf("没有这个数,分块查询次数为%d。\n",count);
printf("\n");
count=0;
}
return 0;
}
