c ++函数中链表的大小

Question

有人可以告诉我们检查链表大小(节点数)的代码是什么.这就是我的代码(插入nd删除头+所有节点的打印信息)

struct node 
{
    int info;
    node *nextptr;
};

class list
{
private:
    node *L,*tail;
     int count;

public:
    list()
    {
        L=tail=NULL;
        count=0;
    }

    void InsertHead(int info);
    int RemoveHead();
    void Print();
}; 

Answer 1

有两种方法可以管理链表的大小,两者都有缺点.最简单的方法是管理一个count变量,你的类有这样一个变量,每次你向列表中添加一个节点时都会增加它,并在每次删除一个节点时递减它.

在这种情况下,您可以在恒定时间内获取链表的大小.缺点是一个有用的操作,拼接,你在一个列表中将它切成两个较小的列表在中间的某个地方,变成线性复杂性,因为现在你必须计算子列表中有多少个节点.

如果希望splice保持不变,则无法跟踪列表的大小.因此,只要您想获得列表的大小,就必须计算有多少节点.

Answer 2

那么最简单的方法是在功能InsertHead add ++ count和RemoveHead do --count中添加

否则，您可以使用循环遍历列表

例如

node* p = L; 
while (p != NULL) 
{ 
  ++count; 
  p = p->nextptr; 
}