C语言 C中链表的总大小

Total size of a linked list in C

提问by Jessica

Alright... my Introduction to Data Structures from CS is so rusty I need to ask this here.

好吧……我的 CS 数据结构简介太生疏了，我需要在这里问这个。

I have a linked list whose structure is:

我有一个链表，其结构是：

struct Data_Struct {
    char *Name;
    char *Task;
    char *Pos;
    struct Data_Struct *Next;
};
typedef struct Data_Struct MyData;

Now, at some point in my application I filled the list with data.

现在，在我的应用程序中的某个时刻，我用数据填充了列表。

The question is, how do I get the total size of the data stored in there? How many chars are there? Something like

问题是，如何获得存储在那里的数据的总大小？有多少个字符？就像是

sizeof(MyData);

That will return the size of the info stored in the list.

这将返回存储在列表中的信息的大小。

code is appreciated.

代码表示赞赏。

Thanks!

谢谢！

EDIT: Unfortunately this is NOT homework. I finished school more than 20 years ago and frankly i never ever had to use linked lists on anything. I just don't remember. What I am doing is iterate the list and get the strlen() of each element and keep it on a global size but I wanted to know if there was a better way.

编辑：不幸的是，这不是作业。我在 20 多年前完成了学业，坦率地说，我从来没有在任何事情上使用过链表。我就是不记得了。我正在做的是迭代列表并获取每个元素的 strlen() 并将其保持在全局大小，但我想知道是否有更好的方法。

and NO, I don't need the size of the linked likes (the count of nodes), i just want to know how many characters are stored in there.

不，我不需要链接喜欢的大小（节点数），我只想知道那里存储了多少个字符。

thanks

谢谢

采纳答案by Hyman

You usually go through the list until you reach the tail item while counting in the meanwhile, code should be something like that:

你通常会遍历列表直到你在计数的同时到达尾项，代码应该是这样的：

int listLength(struct Data_Struct* item)
{
  struct Data_Struct* cur = item;
  int size = 0;

  while (cur != null)
  {
    ++size;
    cur = cur->Next;
  }

  return size;
}

Mind that complexity of this operation is linear with the size of the list, so it's O(n)and it's quite inefficient. You could store size somewhere and update with list insertions and deletes to avoid any overhead and being able to calculate it in a constant time O(1).

请注意，此操作的复杂性与列表的大小成线性关系，因此它是O(n)并且效率很低。您可以将大小存储在某处并使用列表插入和删除进行更新以避免任何开销并能够在恒定时间O(1) 内计算它。

EDIT:Didn't notice you wanted size of the whole data included into the list. In your case you can keep the same approach used for calculating the length but instead that adding 1for every element you should add the total length of strings:

编辑：没有注意到您想要包含在列表中的整个数据的大小。在您的情况下，您可以保留用于计算长度的相同方法，而是为每个元素添加1，您应该添加字符串的总长度：

size += strlen(Name)+strlen(Task)+strlen(Pos);

Mind that since data inside your list element if of type char*the effective size of the Data_Structis just 4 pointers, that's why you need to use a support function like strlen, otherwise you can't get realdimension of the strings.

请注意，由于列表元素中的数据类型char*，如果类型的有效大小Data_Struct只有 4 个指针，这就是为什么您需要使用像 那样的支持函数strlen，否则您将无法获得字符串的真实维度。

Which is the difference?

有什么区别？

sizeof(Data_Struct) == 16

because the Data_Structtype contains 4 pointers, three for pointers to char and one for the next element in the list

因为该Data_Struct类型包含 4 个指针，三个用于指向 char 的指针，一个用于列表中的下一个元素

sizeof(Name) == sizeof(Task) == sizeof(Pos) == 4

because these variables are of type pointer to char, so they are pointer, no concrete value, and it's usually 4 bytes (I'm assuming a 32 bit architecture)

因为这些变量是指向 char 的指针类型，所以它们是指针，没有具体值，通常是 4 个字节（我假设是 32 位架构）

strlen(Name) == length in chars of the string

because the function works exactly to calculate the length of a string.

因为该函数完全可以计算字符串的长度。

回答by Mehrdad Afshari

Well, you can traverse the list to calculate the count pretty easily. Obviously the total memory will be equal to the number of items multiplied by size of each item (sizeof(Data_Struct)).

好吧，您可以很容易地遍历列表来计算计数。显然，总内存将等于项目数乘以每个项目的大小 ( sizeof(Data_Struct))。

Of course, this will be the size of the linked list itself and doesn't include the memory allocated for the strings. A pointer doesn't have any information about the amount of allocated memory it refers to, so strictly speaking, you can't calculate the amount of total memory allocated directly by just looking at a linked list like that. Additionally, there may be duplicate pointers in the linked list you will need to keep track of. That said, assuming all pointer are unique, you can calculate the number of chars in each item by summing up return values of strlencalls on each pointer as you are traversing the list (which should be pretty straightforward).

当然，这将是链表本身的大小，不包括为字符串分配的内存。一个指针没有任何关于它所引用的分配内存量的信息，所以严格来说，你不能仅仅通过查看这样的链表来直接计算分配的总内存量。此外，您需要跟踪链表中可能存在重复的指针。也就是说，假设所有指针都是唯一的，您可以通过在strlen遍历列表时对每个指针上调用的返回值求和来计算每个项目中的字符数（这应该非常简单）。

回答by JonH

Once you allocate memory for a node (using malloc) you should be able to do sizeof(yourDataType). So to get the total size of the linked list you traverse the list and get the count of nodes:

一旦为节点分配内存（使用 malloc），您应该能够执行 sizeof(yourDataType)。因此，要获得链表的总大小，请遍历列表并获取节点数：

Total Size Of Linked List = SizeOf(One Node) * Count Of Nodes

For instance:

例如：

int getCountOfList()
{
 Node* temp = head; //assign a temp node to the head of the list
 int count=0;

 while(temp) {
  count++;
  temp = temp->next; //move to next node
 }
 return count;
}

Then you take that count and multiply by size:

然后你把这个计数乘以大小：

size = getCountOfList * sizeof(mydatatype);

大小 = getCountOfList * sizeof(mydatatype);

This will give you the size of the actual linked list but becareful as the linked list node has pointer elements which in and of themselves can allocate memory as well. This will need to be accounted for...

这将为您提供实际链表的大小，但要小心，因为链表节点具有指针元素，它们本身也可以分配内存。这需要考虑...

For instance, one of those char* elements within the node could malloc some more space and use up some memory.

例如，节点中的那些 char* 元素之一可能会分配更多空间并占用一些内存。

If you actually need the entire size of the list including allocated elements for all other char* pointers for example, you simply:

例如，如果您确实需要列表的整个大小，包括为所有其他 char* 指针分配的元素，您只需：

1)Traverse the list and look into each node

1）遍历列表并查看每个节点

2)For each node you check if the elements of each node point to any other allocation (for instance char* data may allocate 50 characters to store). If it isn't null you get the length of the string + 1 (for terminating char) and you multiply that by sizeof(char) (for this example)

2）对于每个节点，您检查每个节点的元素是否指向任何其他分配（例如 char* 数据可能会分配 50 个字符来存储）。如果它不为空，您将获得字符串的长度 + 1（用于终止字符）并将其乘以 sizeof(char)（对于此示例）

3)You do that for each node and store that size, then move to next node

3）您为每个节点执行此操作并存储该大小，然后移动到下一个节点

4)You take the SUM of all of these char* (in this case) for each node and accumulate for the entire list.

4）您为每个节点计算所有这些 char*（在本例中）的总和，并为整个列表累加。

5)Once you have that simply add this sum that will give you the size of all nodes.

5）一旦你有了它，只需添加这个总和，它将为你提供所有节点的大小。

Then total size becomes:

那么总大小变为：

SizeOfAllNode + (SizeOf(dataType) * CountOfNodes)

回答by Larry

Keep a running count as you add or remove nodes. That way, you don't have to walk the list, summing up each node each time you want the count. Simply reference your up-to-date value.

在添加或删除节点时保持运行计数。这样，您不必遍历列表，每次需要计数时都对每个节点求和。只需参考您的最新值。

回答by Eric Petroelje

To calculate the size of the list itself, just take sizeof(MyData)and multiply by the number of nodes.

要计算列表本身的大小，只需sizeof(MyData)乘以节点数即可。

If you want to include the size of the string data in the list, you can calculate the memory used by a string as (strlen(str) + 1) * sizeof(char)- that is assuming of course that the string was allocated to exactly the right size.

如果您想在列表中包含字符串数据的大小，您可以将字符串使用的内存计算为(strlen(str) + 1) * sizeof(char)- 当然，假设字符串被分配到正确的大小。

回答by John Knoeller

If you need to get the size of the data more than once, then it would be wiser to keep track of it as you added elements to the list, but the code to figure it out brute force is pretty easy.

如果您需要多次获取数据的大小，那么在向列表中添加元素时跟踪它会更明智，但是找出暴力破解的代码非常简单。

 size_t cb = 0;
 int    cItems = 0;
 struct Data_Struct * pnext = &MyData;
 while (pnext)
    {
    if (pnext->Name)
       cb += (strlen(pnext->Name)+1) * sizeof(char);
    if (pnext->Task)
       cb += (strlen(pnext->Task)+1) * sizeof(char);
    if (pnext->Pos)
       cb += (strlen(pnext->Pos)+1) * sizeof(char);
    ++cItems;
    pnext = pnext->Next;
    }

 // cb has the total size of the strings, now add the size of the data structs
 cb += sizeof(struct Data_Struct) * cItems;

回答by ebasconp

You can iterate through all the members of your list and accumulating the number of characters on Name, Task, and Pos.

您可以遍历列表中的所有成员并累积 Name、Task 和 Pos 上的字符数。

However, if you are going to do this several times, I would store the number of characters of every field when populating the node instead of counting them once and once again.

但是，如果您打算多次这样做，我会在填充节点时存储每个字段的字符数，而不是一次又一次地计算它们。

So, your structure would be defined as follows:

因此，您的结构将定义如下：

struct Data_Struct {
    char *Name;
    int   NameCount;

    char *Task;
    int   TaskCount;

    char *Pos;
    int   PosCount;
    struct Data_Struct *Next;
};
typedef struct Data_Struct MyData;

and iterating through the list could be something like:

并遍历列表可能是这样的：

void getCharacterCount(struct Data_Struct* data, int* nameCount, int* taskCount, int* posCount)
{
  struct Data_Struct* auxData = data;
  int nc = tc = pc = 0;

  for (; auxData; auxData = auxData->Next())
  {
    nc += auxData->NameCount; 
    tc += auxData->TaskCount;
    pc += auxData->PosCount;
  }

  *nameCount = nc;
  *taskCount = tc;
  *posCount  = pc;
}