【问题描述】
实现可变长顺序表的查找算法。任务要求:通过顺序表的初始化、插入建立顺序表,根据查找要求,返回查找结果。
【输入形式】
第一行输入整数N(1<=N<=100),M(1<=M<=100)。N表示创建长度为N的顺序表;M表示输入M个查找的关键值。
第二行输入N个整数,表示顺序表的N个元素,依次放入表中;
接下来输入M个查找的关键值。
【输出形式】
对于每个查找关键值,若找到,输出其在顺序表的位序,若未找到,输出“no”。
【样例输入】
5 2
10 20 30 40 50
30
-9
【样例输出】
3
no
前一篇文章已经介绍了可变长顺序表的初始化,插入和删除操作,现在只需要会查找的算法就能够解决这个问题。
顺序表的查找是指在顺序表中查找某个其值等于给定值的元素位置。是从顺序表的第一个元素位置开始依次进行比较,直到找到对应的元素,则返回该元素在表中的位序;否则,表中不存在该元素,则返回失败标志。
查找操作的算法如下;
int searchSq(Sqlist *L, ElemType e){int i;for(i=0;i<L->length;i++){if(L->slist[i]==e)//若找到元素返回为序{printf("%d\n",i+1);return 1;}}printf("no\n");//没有找到返回失败标志return 0;}
完整代码的实现和运行结果
#include <stdio.h>#include <stdlib.h>#define INIT_SIZE 5#define INCREM 3typedef int ElemType;/*顺序表结构*/typedef struct Sqlist{ElemType *slist;int length;int listsize;}Sqlist;/*初始化顺序表:创建成功返回1,不成功返回0*/int initSq(Sqlist *L){L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));if(!L->slist)return 0;L->length=0;L->listsize=INIT_SIZE;return 1;}/*在i位置插入元素:插入成功返回1,不成功返回0*/int insertSq(Sqlist *L, ElemType e, int i){if(i<0||i>L->length+1)return 0;if(L->length+1>L->listsize){L->slist=(ElemType*)realloc(L->slist,(L->listsize+INCREM)*sizeof(ElemType));if(!L->slist)return 0;L->listsize+=INCREM;}int j;for(j=L->length;j>i;j--){L->slist[j]=L->slist[j-1];}L->slist[i]=e;L->length++;return 1;}/*输出顺序表元素*/void printSq(Sqlist *L){int i;for(i=0;i<L->length;i++){printf("%d ",L->slist[i]);}printf("\n");}//查找指定值的元素int searchSq(Sqlist *L, ElemType e){int i;for(i=0;i<L->length;i++){if(L->slist[i]==e){printf("%d\n",i+1);return 1;}}printf("no\n");return 0;}int main(){Sqlist sq;ElemType e;int n,m;if(initSq(&sq)){scanf("%d%d",&n,&m);/*补充代码,实现n个元素顺序表的创建,m个关键字值的查找*/int i;for(i=0;i<n;i++){scanf("%d",&e);insertSq(&sq,e,i);}for(i=0;i<m;i++){scanf("%d",&e);searchSq(&sq,e);} }return 0;}
运行结果如下: