问题补充说明:题目描述给出含有n个数的升序序列,保证序列中的数两两不相等,这n个数编号从1 到n。然后给出q次询问,每次询问给出一个数x,若x存在于此序列中,则输出其编号,否则输出-1。输入单组输入。首先输入一个整数n(1 <= n && n <= 3000000),接下的一行包含n个数。再接下来的一行包含一个正整数q(1 <= q && q <= 10000),表示有q次询问。再接下来的q行,每行包含一个正整数x。输出对于每次询问,输出一个整数代表答案。示例输入51 3 5 7 93158示例输出13-1
抱歉了,题主。你描述的功能我已经实现:
①输入并存储n个数字。由于题主在描乙述中说明,1≤n≤30来自00000。所以为了防止浪费存储空间,我使用了链表队列的方式。
②输入并查询p个数字。为了方便起见,我是随着输入直接进行了查询。
但在实现中和你的要求有所出入,这是因为:
没有使用递归实现查询。不是无法实现,而是由于在设计程序时使用了多文360问答件。为了避免逻辑上的脚图常缺陷,就直接使用了连续查询的方式实现查找功能。但为了方便题主借鉴,使用递归进行查询的方法也保留在了que谓水毫损等反技输算ue.c的最后。
如果题主一定要尝试递归功能(queue.c中的intsearch_by_recursion(intdata,node_t*ptr)函数),可以将queue.h中的代码定义置于main.c的最上方,queue.c中代码置于main.c的最下方,并且去除掉#include"queue.h"和分别在queue.c中的#include语句,就可以使用递归查询函数了。
同样为了实现逻辑清晰,我采用了多文件的形式分别设计了程序。其中:
①queue打航刘较优温.h:用于提供队列提供的各种等坏排属营计函数和功能。
②queue.c:具体实现了在queue.h中声明的函数。
③main.c:实现了main()函数,并实现了输入n、p等简单I/O功能。
我使用的是WindowsXPSP332-bits版本,编译器是MinGWw64。程序具体在编译(cmd下的第一条进行编译并生成main.exe文件)和运行(cmd下第二条命令为执行过程)的过程中产生的截图如下:
具体代码实现如下,为了方便理解我也尽可能的加入了注释:
----------queue.h----------
//Headerguardtokeeptheheaderbeingincludedonly1time.
#ifndefQUEUE_H_INCLUDED
#defineQUEUE_H_INCLUDED
/**
* intpus增那乱胶伯诉械兵h(intelement);
* TopushaelementintotheQueue.
*
* Returnedvalue:
* Ifpushedtheelemntsuccessfully,return1.
* Elsereturn0;
*
* Parameters:
* 1.intelement:thedatainfo.tobepushed.
**/
intpush(intelement);
/**
* intpop(int*buf);
* TopopaelementfromtheQueue.
*
* Returnedvalue:
* Ifpoptheelemntsuccessfully,return1.
* Elsereturn0;
*
* Parameters:
* 1.int*buf:thebuffertostorethee著怕绝参载lementpopedfromtheQueue.
**/
intpop(int*buf);
/**
* intis_empty(void);
* TodetermineiftheQueueisempty.
*
* Returnedvalue:
* Get1iftheQueueisempty,elseget0.
*
* Parameters:
* None.
**/
intis_empty(void)国载认此良势;
/**
* intgetlen(void);
* GetthelengthoftheQueue.
*
* Returnedvalue:
* ThelengthoftheQueue.IftheQueueisempty,ret尔张些乙复便维urn0.
*
* Parameters:
* None.
**/
intgetlen(void);
/**
* intsearch(intdata)率丰州映生阳量冷;
* SearchtheQueueifthere'sa短我elementequalsdata.
*
* Retu零识干宣硫带需控rnedvalue:
* Get1iffound,0ifnotfound.
万翻止超末析找*
* Parame跳垂评那述销这雷ters:
* 1.in和市tdata:thedatatobesearched.
**/
intsearch_by_circulat征初控六之训创样头ion(intdata);
#endif
----------queue.c----------
//TousesomeI/Ofunctions.i.e.fputs(),printf()andfprintf().
#incl研接谁念于排坏制技帮北ude<stdio.h>
//TousesomeOSinvokefunction.i.e.malloc()andfre刚开少至肥威杨章南粉际e().
#include<stdlib.h>
//TogetthedeclarationsoftheQueuefunctions.
#include"queue.h"
//TorecordthelengthoftheQueue.
staticintlen=0;
//Thedefinitionofstructnode_tintheQueue.
typedefstructnode{
intelement;
structnode*next;
}node_t;
//TheheadpointerstoretheaddressoffirstnodeoftheQueue.
node_t*head=NULL;
//ThetailpointerstoretheaddressofthelastnodeoftheQueue.
node_t*tail=NULL;
/**
* intnew_node(intelement);
* Createanewnode.
*
* Returnedvalue:
* Thepointerofnewnode.Iffailed,returnedvaluewillbeNULL.
*
* Parameters:
* 1.intelement:thedatawouldbestoredinnode.
**/
node_t*new_node(intelement){
node_t*ret_ptr=(node_t*)malloc(sizeof(*ret_ptr));
if(ret_ptr){
ret_ptr->element=element;
ret_ptr->next=NULL;
}
returnret_ptr;
}
intis_empty(void){
return(!len);
}
intgetlen(void){
returnlen;
}
intpush(intelement){
intret_val=0;
node_t*newnode=new_node(element);
if(newnode){
if(!head)
head=newnode;
else
tail->next=newnode;
tail=newnode;
ret_val=1;
len++;
}else{
fputs("Error:CannotpushelementtotheQueuebecausethesystemstackisfull.\n",stderr);
}
returnret_val;
}
intpop(int*buf){
intret_val=0;
if(!is_empty()){
node_t*popnode=head;
*buf=head->element;
head=head->next;
ret_val=1;
len--;
free(popnode);
}else{
fputs("Error:CannotpopfromtheQueuebecausetheQueueisempty.",stderr);
}
returnret_val;
}
intsearch_by_circulation(intdata){
intret_val=0;
node_t*ptr=head;
while(ptr){
if(data==ptr->element){
ret_val=1;
printf("Theelement\"%d\"wasfoundintheQueue.\n\n",data);
break;
}
ptr=ptr->next;
}
returnret_val;
}
/**
* intsearch_by_recursion(intdata,node_t*ptr);
* SearchtheQueueifthere'saelementequalsdata.
*
* Returnedvalue:
* Get1iffound,0ifnotfound.
*
* Parameters:
* 1.intdata:thedatatobesearched.
* 2.node_t*ptr:iftheelementofnodeptrequalsdata.
**/
intsearch_by_recursion(intdata,node_t*ptr){
intret_val=0;
if(ptr){
if(data==ptr->element){
ret_val=1;
printf("Theelement\"%d\"wasfoundintheQueue.\n",data);
}else{
ret_val=search_by_recursion(data,ptr->next);
}
}
returnret_val;
}
----------main.c----------
#include<stdio.h>
#include"queue.h"
#defineMIN(1)
#defineMAX(3000000)
intmain(void){
intn; //Forn
intp; //Forp
inti=1; //Acounter
intdata; //TostoreintegerfromSTDINandpushtotheQueue
printf("Pleaseinputapositivedemicalintegerforn:");
scanf("%d",&n);
if(n>=MIN&&n<=MAX){
printf("\nOk,nowpleaseinput%dnumbers:\n",n);
while(n){
printf(" No%dtostore:",i++);
scanf("%d",&data);
push(data);
n--;
}
printf("\nAndinputapositivedemicalintegerforp:");
scanf("%d",&p);
i=1;
while(p){
printf(" No.%dtosearch:",i++);
scanf("%d",&data);
if(!search_by_circulation(data)){
printf("Sorry,\"%d\"cannotfindintheQueue.\n\n",data);
}
p--;
}
}else{
printf("Error:%dshouldbegreaterthan%dandlessthan%d.\n",n,MAX,MIN);
}
return0;
}
标签:递归,语言