顺序表的查找

喜欢ヅ旅行 2023-10-17 17:04 28阅读 0赞

（1）随机产生n个两位整数，构造一个查找表。  
（2）输入一个整数，利用顺序查找法在查找表中查找该整数是否存在。若查找成功，返回该整数在表中的位置；查找失败则返回0。  
（3）对查找表按递增顺序进行排序。  
（4）输入一个整数，利用折半查找法在有序表中查找该整数是否存在。若查找成功，返回该整数在表中的位置；查找失败则返回0。

\#include <stdio.h>  
\#include <string.h>  
\#include <stdlib.h>  
\#include <time.h>  
typedef struct table\{  
int \*elem;  
int length;  
\}SSTable;  
void InitTable(SSTable &ST)  
\{  
int i,j,n;  
srand(time(0));  
printf("请输入随机生成数的个数:");  
scanf("%d",&n);  
ST.elem=(int \*)malloc(sizeof(int)\*(n+1));  
for(i=1;i<=n;i++)  
ST.elem\[i\]=rand()%90+10;  
ST.length=n;  
\}  
  
int S\_Search(SSTable ST,int key)  
\{  
int n,i,j;  
ST.elem\[0\]=key;  
for(i=ST.length;ST.elem\[i\]!=key;i--);  
return i;  
\}  
  
void Display(SSTable ST)  
\{  
int i;  
for(i=1;i<=ST.length;i++)  
printf("%d ",ST.elem\[i\]);  
putchar('\\n');  
\}  
  
void Sort(SSTable ST)  
\{  
int i,j;  
int temp;  
for(i=1;i<ST.length;i++)  
\{  
for(j=i+1;j<=ST.length;j++)  
\{  
if(ST.elem\[i\]>ST.elem\[j\])  
\{  
temp=ST.elem\[i\];  
ST.elem\[i\]=ST.elem\[j\];  
ST.elem\[j\]=temp;  
\}  
\}  
\}  
  
\}  
int Search\_Bin(SSTable ST,int key)  
\{  
int i,j;  
int left=1,right=ST.length;  
int mid=(left+right)/2;  
  
while(left<=right)  
\{  
if(ST.elem\[mid\]==key)  
return mid;  
if(ST.elem\[mid\]<key)  
\{  
left=mid+1;  
mid=(left+right)/2;  
\}  
if(ST.elem\[mid\]>key)  
\{  
right=mid-1;  
mid=(left+right)/2;  
\}  
\}  
return 0;  
\}  
int main()  
\{  
SSTable ST;  
int i,j,n,key;  
InitTable(ST);  
Display(ST);  
printf("顺序查找\\n");  
printf("请输入要查找的数:");  
scanf("%d",&key);  
j=S\_Search(ST,key);  
printf("该数字在表中的位置为:%d\\n",j);  
printf("排序\\n");  
Sort(ST);  
Display(ST);  
printf("折半查找\\n");  
printf("请输入要查找的数:");  
scanf("%d",&key);  
j=Search\_Bin(ST,key);  
printf("该数字在表中的位置为:%d\\n",j);  
return 0;  
  
\}