使用 O(1) find-max/find-min 实现堆栈时出错？

Question

我已经为 Stack ADT 实现了几个功能。我试图在 O(1) 时间内找到最大值和最小值，并且我已经扩充了我的堆栈结构来达到这个目的。这是我的代码：

 void mms_push(MMStack mms, int i) {

struct llnode *new = malloc(sizeof(struct llnode));
new->item = i;
if(mms->len!=0)
{
 new->next = mms->topnode;
 mms->topnode = new;
}
else 
{
 new->next = NULL;
 mms->topnode = new;
}

if (mms->len == 0)
{
mms->topnode->minc = i;
mms->topnode->maxc = i;}
else
{
  if(mms->topnode->maxc < i)
  {
      mms->topnode->maxc = i;
  }

  if(i<mms->topnode->minc)
  {
      mms->topnode->minc = i;
  }


mms->len++;}


int mms_pop(MMStack mms) {
  assert(mms);
  int ret = mms->topnode->item;
  struct llnode *backup = mms->topnode;
  mms->topnode = mms->topnode->next;
  mms->len--;


  free(backup);
  return ret;
}

我使用的结构如下：

struct llnode
{

  int item;
  struct llnode *next;
  int minc;
  int maxc;
};

struct mmstack
{
  int len ;
  struct llnode *topnode;

};


typedef struct mmstack *MMStack;

我没有得到正确的最大值和最小值。如何更正代码以便获得堆栈中最大和最小元素的正确值？

提前致谢！

Answer 1

看看这段代码：

if (mms->len == 0)
{
  mms->topnode->minc = i;
  mms->topnode->maxc = i;
}
else
{
  if(mms->topnode->maxc < i)
  {
      mms->topnode->maxc = i;
  }

  if(i<mms->topnode->minc)
  {
      mms->topnode->minc = i;
  }
}

请注意，在 else 分支中，您在初始化 mms->topnode->minc 和 mms->topnode->maxc 之前读取它们的值。我认为您打算在重新分配 mms->topnode 之前查看 mms->topnode->minc/maxc 的值。要解决此问题，请尝试执行以下操作：

else
{
  mms->topnode->maxc = mms->topnode->next->maxc;
  mms->topnode->minc = mms->topnode->next->minc;

  if(mms->topnode->maxc < i)
  {
      mms->topnode->maxc = i;
  }

  if(i<mms->topnode->minc)
  {
      mms->topnode->minc = i;
  }
}

这些额外的两行在与 i 比较之前将最小值和最大值初始化为旧的最大值，这应该确保它们得到一个值。

希望对您有所帮助！

Answer 2

你做的事情有点倒退——将 i 与新的、未初始化的节点插入堆栈后的值进行比较。

首先完全准备好新节点，然后 link 将其放入堆栈会更容易。

假设一个空栈有一个NULL顶节点：

void mms_push(MMStack mms, int i) {
   struct llnode *new = malloc(sizeof(struct llnode));
   new->item = i;
   new->next = mms->topnode;
   if (!mms->topnode)
   {
       new->minc = i;
       new->maxc = i;
   }
   else
   {
      new->minc = min(mms->topnode->minc, i);
      new->maxc = max(mms->topnode->maxc, i);
   }
   mms->topnode = new;
   mms->len++;
}

我不确定 min 和 max 是否是 C99，但它们很容易定义。

使用 O(1) find-max/find-min 实现堆栈时出错？

Error in implementation of a stack with O(1) find-max/find-min?

c

data-structures

stack