如何获取链表的大小 [英] How to get the size of a linked list

问题描述

我遇到链接列表和递归问题我希望有人可以引导这个问题：



假设类LinkedBag没有数据成员item_count_ 。修改方法getCurrentSize，以便计算链接链中的节点数a。迭代地b。递归地



原始的GetCurrentSize（）只是

 int LinkedBag< ItemType> :: GetCurrentSize（）const 
 {
 return item_count_; 
} 

这是我到目前为止：

  int  GetCurrentSize（node * p）
 {
  if （p == NULL）
 < span class =code-keyword> return   0 ; 
  else  {
  return   1  + GetCurrentSize（cur-> next_node）; 
} 
 
} 

  int  GetCurrentSize（node * cur）{
  int  count; 
  while （cur！= NULL）{
 cur-> next_node; 
 count ++ 
} 
  return  count; 
 
} 

解决方案

除了编译无法知道哪个版本的 GetCurrentSize 您打算在任何时候使用它，因为它们具有相同的签名。您的迭代版本从循环内声明 count ，因此它的值不一定从迭代到迭代。它根本无法初始化它。并且你永远不会真正返回价值。

更像是：

  int  GetCurrentSize（node * cur）{
  int  count =  0 ; 
  while （cur！= NULL）{
 cur-> next_node; 
 count ++ 
} 
  return  count; 
} 

用于递归，您首先需要制作基本案例，例如

  if （cur == NULL） return   0 ; 

然后在其他情况下：

 其他 {
 返回  1  + GetCurrentSize（cur-> next_node）; 
} 

现在是否正确？

 <   pre     lang   =  c ++ >  
 int GetCurrentSize（node * p）
 {
 if（p == NULL）
 return 0; 
 else {
返回1 + GetCurrentSize（cur-& gt; next_node）; 
} 
 
} 
 <   / pre  >  
 <   pre     lang   =  c ++ >  
 int GetCurrentSize（node * cur）{
 int count; 
 while（cur！= NULL）{
 cur-& gt; next_node; 
 count ++ 
} 
返回计数; 
 
} 
 <   / pre  >  

I am having trouble with link lists and recursion I was hoping someone can guide through this question:

suppose that the class LinkedBag did not have the data member item_count_. Revise the method getCurrentSize so that it counts the number of nodes in the linked chain a. iterartively b. Recursively

The original GetCurrentSize() is just

int LinkedBag<ItemType>::GetCurrentSize() const
{
  return item_count_;
}  

Here is what I have so far:

int GetCurrentSize(node* p)
{
        if (p==NULL)
                return 0;
        else{
             return 1 + GetCurrentSize(cur->next_node);
             }

}

int GetCurrentSize(node* cur){
    int count;
    while(cur != NULL){     
        cur->next_node;
        count++
        }
return count;

}

解决方案

Besides the fact that the compile has no way to know which version of GetCurrentSize you intend to use at any point, because they have the same signature. Your iterative version declares the count from within the loop, so it's value is not necessarily carried from iteration to iteration. It fails to initialize it at all. And you never actually return the value.
More like:

int GetCurrentSize(node* cur){
        int count = 0;
    while(cur != NULL){
        cur->next_node;
        count++
        }
    return count;
}

for recursion you first need to make the base case e.g

if(cur==NULL) return 0;

then in other cases:

else{
return 1 + GetCurrentSize(cur->next_node);
}

Is it correct now?

<pre lang="c++">
int GetCurrentSize(node* p)
{
        if (p==NULL)
                return 0;
        else{
             return 1 + GetCurrentSize(cur-&gt;next_node);
             }

}
</pre>
<pre lang="c++">
int GetCurrentSize(node* cur){
    int count;
    while(cur != NULL){
        cur-&gt;next_node;
        count++
        }
return count;

}
</pre>

这篇关于如何获取链表的大小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！