Общий размер связанного списка в C

Question

Хорошо ... мое введение в структуры данных из CS настолько ржаво, что мне нужно спросить об этом здесь.

У меня есть связанный список, структура которого:

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

Теперь, в какой-то момент в моем приложении я заполнил список данными.

Вопрос в том, как мне получить общий размер хранящихся там данных? Сколько символов там? Что-то вроде

sizeof(MyData);

Возвращает размер информации, хранящейся в списке.

код приветствуется.

Спасибо!

EDIT : К сожалению, это не домашнее задание. Я закончил школу более 20 лет назад, и, честно говоря, мне никогда не приходилось использовать связанные списки ни для чего. Я просто не помню. Я перебираю список, получаю strlen () каждого элемента и сохраняю его в глобальном размере, но я хотел знать, есть ли лучший способ.

и НЕТ, мне не нужен размер связанных лайков (количество узлов), я просто хочу узнать, сколько символов там хранится.

спасибо

Answer 1

Обычно вы просматриваете список до тех пор, пока не достигнете конечного пункта во время подсчета, код должен выглядеть примерно так:

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

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

  return size;
}

Имейте в виду, что сложность этой операции линейна с размером списка, поэтому она равна O (n) и совершенно неэффективна. Вы можете где-то хранить размер и обновлять его путем добавления и удаления списка, чтобы избежать каких-либо накладных расходов и иметь возможность рассчитать его за постоянное время O (1) .

EDIT: Не заметил, что вам нужен размер всех данных, включенных в список. В вашем случае вы можете использовать тот же подход, что и при расчете длины, но вместо добавления 1 для каждого элемента вы должны добавить общую длину строк:

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

Имейте в виду, что поскольку данные внутри элемента списка типа char*, эффективный размер Data_Struct составляет всего 4 указателя, поэтому вам нужно использовать вспомогательную функцию, например strlen, иначе вы не сможете получить real размерность строк.

Какая разница?

sizeof(Data_Struct) == 16

, поскольку тип Data_Struct содержит 4 указателя, три для указателей на символ и один для следующего элемента в списке

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

потому что эти переменные имеют тип указатель на символ , поэтому они являются указателем, а не конкретным значением, и обычно это 4 байта (я предполагаю, что 32-битная архитектура)

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

потому что функция работает точно для расчета длины строки.

Answer 2

Как только вы выделите память для узла (используя malloc), вы сможете использовать sizeof (yourDataType).Таким образом, чтобы получить общий размер связанного списка, вы просматриваете список и получаете количество узлов:

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

Например:

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;
}

Затем вы берете это количество и умножаетесь наsize:

size = getCountOfList * sizeof (mydatatype);

Это даст вам размер фактического связанного списка, но будьте осторожны, так как узел связанного списка имеет элементы указателя, которые в исами по себе могут выделить память, а также.Это необходимо учитывать ...

Например, один из этих элементов char * в узле может выделять немного больше места и занимать немного памяти.

Если вына самом деле нужен весь размер списка, включая выделенные элементы для всех других указателей char *, например, вы просто:

1) просмотрите список и загляните в каждый узел

2) для каждого узлаВы проверяете, указывают ли элементы каждого узла на какое-либо другое распределение (например, данные char * могут выделять 50 символов для хранения).Если оно не равно нулю, вы получаете длину строки + 1 (для завершения символа) и умножаете ее на sizeof (char) (для этого примера)

3) Вы делаете это для каждого узла и сохраняетеэтого размера, затем перейдите к следующему узлу

4) Вы берете сумму всех этих символов * (в данном случае) для каждого узла и накапливаете для всего списка.

5) Один разу вас есть это просто добавить эту сумму, которая даст вам размер всех узлов.

Тогда общий размер становится:

SizeOfAllNode + (SizeOf(dataType) * CountOfNodes)

Answer 3

Ну, вы можете пройти по списку, чтобы довольно легко рассчитать счет. Очевидно, что общая память будет равна количеству элементов, умноженному на размер каждого элемента (sizeof(Data_Struct)).

Конечно, это будет размер самого связанного списка и не включает память, выделенную для строк. Указатель не имеет никакой информации о количестве выделенной памяти, на которую он ссылается, поэтому, строго говоря, вы не можете рассчитать объем общей памяти, выделенной напрямую, просто посмотрев на подобный связанный список. Кроме того, в связанном списке могут быть повторяющиеся указатели, которые вам необходимо отслеживать. Тем не менее, предполагая, что все указатели уникальны, вы можете вычислить количество символов в каждом элементе, суммируя возвращаемые значения вызовов strlen для каждого указателя при обходе списка (что должно быть довольно просто).

Answer 4

Сохраняйте счетчик при добавлении или удалении узлов. Таким образом, вам не нужно обходить список, суммируя каждый узел каждый раз, когда вы хотите подсчитать. Просто укажите ваше актуальное значение.

Answer 5

Вы можете перебирать всех членов вашего списка и накапливать количество символов в имени, задании и позиции.

Однако, если вы собираетесь сделать это несколько раз, я бы сохранил числосимволов каждого поля при заполнении узла вместо подсчета их один раз и еще раз.

Итак, ваша структура будет определяться следующим образом:

struct Data_Struct {
    char *Name;
    int   NameCount;

    char *Task;
    int   TaskCount;

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

и повторение списка может бытьчто-то вроде:

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;
}

Answer 6

Если вам нужно получить размер данных более одного раза, то было бы разумнее отслеживать его, когда вы добавляете элементы в список, но код, позволяющий выяснить это методом грубой силы, довольно прост.

 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;

Answer 7

Чтобы вычислить размер самого списка, просто возьмите sizeof(MyData) и умножьте на количество узлов.

Если вы хотите включить размер строковых данных в список, вы можете рассчитать объем памяти, используемый строкой, как (strlen(str) + 1) * sizeof(char) - при условии, конечно, что строка была выделена точно на правильный размер.