查找和排序源程序

#include <stdio.h>

#include <math.h>

#define MAXL 1000

#define INF 32767

int process[MAXL],pn;

//顺序表的存储结构

typedef int KeyType;

typedef int InfoType;

typedef struct

{ KeyType key;

InfoType data;

} NodeType;

typedef NodeType SeqList[MAXL];

//索引表的存储结构

typedef struct

{ KeyType key;

int link;

} IdxType;

typedef IdxType IDX[MAXL];

//顺序查找算法

int SeqSearch(SeqList R,int n,KeyType k)

{

int i=0;

pn=0;

while(i<n&&R[i].key!=k)

{ process[pn++]=R[i].key;

i++;

}

if(i>=n) return -1;

else return i;

}

//折半查找算法

int BinSearch(SeqList R,int n,KeyType k)

{ int low=0,high=n-1,mid;

pn=0;

while(low<=high)

{

mid=(low+high)/2;

if(R[mid].key==k) return mid;

if(R[mid].key>k)

{

process[pn++]=R[mid].key;

high=mid-1;

} else

{ process[pn++]=R[mid].key;

low=mid+1;

}

}

return -1;

}

int main()

{

int n,i,k,m;

SeqList R;

IDX I;

printf("请输入无序顺序表的元素个数：");//10

while(scanf("%d",&n)!=EOF)

{

printf("请输入无序顺序表的%d个元素：\n",n);

//3 6 2 10 1 8 5 7 4 9

for(i=0;i<n;i++) scanf("%d",&R[i].key);

printf("请输入要查找的关键字：");scanf("%d",&k);//5

printf("使用顺序查找算法，");

if(SeqSearch(R,n,k)!=-1)

{

printf("关键字%d的下标为：%d\t查找过程为：",k,SeqSearch(R,n,k)); for(i=0;i<pn;i++) printf("%d ",process[i]);

printf("%d\n\n",k);

}

else printf("要查找的关键字%d不在无序顺序表中\n\n",k);

printf("请输入有序顺序表的元素个数：");//10

scanf("%d",&n);printf("请输入有序顺序表的%d个元素：\n",n); //1 2 3 4 5 6 7 8 9 10

for(i=0;i<n;i++) scanf("%d",&R[i].key);

printf("请输入要查找的关键字：");scanf("%d",&k);//9

printf("折半查找算法");

if(BinSearch(R,n,k)!=-1)

{

printf("关键字%d的下标为：%d\t查找过程为：",k,BinSearch(R,n,k)); for(i=0;i<pn;i++) printf("%d ",process[i]);

printf("%d\n\n",k);

}

else printf("要查找的关键字%d不在有序顺序表中\n\n",k);

return 0;

}

}