顺序表的查找实现.doc
#include "stdio.h"#include"stdlib.h"#define MaxSize 100#define IndexSize 20typedef int KeyType;typedef structKeyType key;DataType;typedef structDataType listMaxSize;int length;SSTable;typedef structKeyType maxkey;int index;IndexTableIndexSize;int SeqSearch(SSTable S,DataType x)int i=0;while(i<S.length&&S.listi.key!=x.key)i+;if(S.listi.key=x.key)return i+1;elsereturn 0; int BinarySearch(SSTable S,DataType x)int low,high,mid;low=0,high=S.length-1;while(low<=high)mid=(low+high)/2;if(S.listmid.key=x.key)return mid+1;else if(S.listmid.key<x.key)low=mid+1;else if(S.listmid.key>x.key)high=mid-1;return 0;int SeqIndexSearch(SSTable S,IndexTable T,int m,DataType x)int i,j,b1;for(i=0;i<m;i+)if(Ti.maxkey>=x.key)break;if(i>=m)return 0;j=Ti.index;if(i<m-1)b1=Ti+1.index-Ti.index;elseb1=S.length-Ti.index;while(j<Ti.index+b1)if(S.listj.key=x.key)return j+1;elsej+;return 0;void main()SSTable S1=123,23,34,6,8,355,32,67,8;SSTable S2=11,23,32,35,39,41,45,67,8;SSTable S3=6,12,23,16,21,19,41,32,37,35,29,46,49,47,52,61,59,76,68,72,20;IndexTable T=23,0,41,5,52,10,76,15;DataType x=32;int pos;if(pos=SeqSearch(S1,x)!=0)printf("顺序表的查找: 关键字32在主表中的位置是: %2dn",pos);elseprintf("查找失败n");if(BinarySearch(S2,x)!=0)printf("折半查找: 关键字32在主表中的位置是: %2dn",pos);elseprintf("查找失败n");if(SeqIndexSearch(S3, T,4, x)!=0)printf("索引顺序表的查找: 关键字32在主表中的位置是: %2dn",pos);elseprintf("查找失败n");