我遇到了这个问题,要求我们存储一个字符串和一个编号。与之关联,我们应该从列表中删除最小的编号(及其字符串),并删除存储在它之后的编号(和字符串)。输入是一个编号流,字符串对和一个输入of -1 意味着我们需要从列表中删除最小的和它上面的对。输出应该是最小编号项目之上的项目数。 例如2 abcd 1个 3分贝 -1 o/p 1(因为最小值是 1 aabb,它后面只有一项,即 3 dbbb;我们的列表现在只包含 2 abcd)。 另一个 -1 会产生 o/p 0。 我已经尝试使用链表进行此操作,但似乎花费的时间比预期的要多。我需要更好的数据结构或算法。 这是我的代码:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct data
{
int no,pos;
char *st;
struct data *next;
}data;
void insert(data *start,int n,char *s);
void minimum(data *start);
int total=0,min=100001,posn=0;//total=total no of nodes,rem=nodes after minimum
data *temp;
int main()
{
int N,n;
data *start;
start=(data*)malloc(sizeof(data));
start->pos=0;
start->no=100002;
start->next=NULL;
char c,s[16];
scanf("%d",&N);
while(N)
{
scanf("%d",&n);
if(n!=-1)
{
scanf("%c",&c);
scanf("%s",s);
total++;
posn++;
insert(start,n,s);
}
else
{
printf("%d %s\n",total-(temp->next->pos),temp->next->st);
posn=temp->pos;
total=temp->pos;
temp->next=NULL;
minimum(start);
}
N--;
}
}
void insert(data *start,int n,char *s)
{
while(start->next!=NULL)
start=start->next;
if(n<=min)
{
temp=start;
min=n;
}
start->next=(data*)malloc(sizeof(data));
start=start->next;
start->no=n;
start->st=(char*)malloc(sizeof(char)*(strlen(s)));
strcpy(start->st,s);
start->pos=posn;
start->next=NULL;
return;
}
void minimum(data *start)
{
min=100001;
while(start->next!=NULL)
{
if(start->next->no<=min)
{
min=start->next->no;
temp=start;
start=start->next;
}
}
return;
}
如有任何帮助,我们将不胜感激。
最佳答案
您的代码存在一些问题:
start=start->next;
应该在每次迭代中完成,而不仅仅是在找到新的最小值时。你总是错过列表的头部,迭代while(start != NULL)
(并检查start->no
而不是下一个节点...您缺少(请注意,将答案存储在全局变量中是一种不好的做法,更好的方法是从函数中返回它)minimum()
函数的返回类型,它不应该是void
。如果您的列表包含int
,则返回类型应该是int
,并且当您用完循环时,您应该return min;
。 (如果你有兴趣返回附加的最小字符串,存储一个额外的变量char* minElement
,当你修改min
时修改它,并返回它(minelement
) 当循环耗尽时。- 您应该将 min 初始化为
INT_MAX
而不是任意数字。
关于优化问题:
如果您只对寻找最小元素感兴趣, heap是专门为它设计的数据结构!它是一种简单且非常有效的数据结构,用于检索最小值。
另请注意,如果您的数据结构不支持删除,您可以在每次插入时缓存 min,类似于此伪代码:
加入插入功能:
if (newValue < min):
min <- newValue
和 min 很简单,只需检索缓存的 min
。
关于c - 以最优方法在链表中找到最小值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13718735/