Tamaño total de una lista vinculada en C

Question

Muy bien ... mi Introducción a las estructuras de datos de CS está tan oxidada que necesito preguntar esto aquí.

Tengo una lista enlazada cuya estructura es:

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

Ahora, en algún momento de mi solicitud me llena la lista con los datos.

La pregunta es, ¿cómo obtengo el tamaño total de los datos almacenados allí? ¿Cuántos caracteres hay? Algo como

sizeof(MyData); 

Eso devolverá el tamaño de la información almacenada en la lista.

código es apreciado.

Gracias!

EDIT: Desafortunadamente esto NO es tarea. Terminé la escuela hace más de 20 años y, francamente, nunca tuve que usar listas vinculadas en nada. Simplemente no recuerdo. Lo que estoy haciendo es repetir la lista y obtener strlen() de cada elemento y mantenerlo en un tamaño global, pero quería saber si había una mejor manera.

y NO, no necesito el tamaño de los me gusta vinculados (el recuento de nodos), solo quiero saber cuántos caracteres hay almacenados allí.

gracias

Answer 1

Por lo general, va a través de la lista hasta llegar al punto de la cola mientras se cuentan entre tanto, el código debe ser algo así:

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

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

    return size; 
} 

mente que la complejidad de esta operación es lineal con el tamaño de la lista , entonces es O (n) y es bastante ineficiente. Puede almacenar el tamaño en algún lugar y actualizar con inserciones de listas y eliminaciones para evitar cualquier sobrecarga y poder calcularlo en un tiempo constante O (1).

EDIT: No notó que quería el tamaño de toda la información incluida en la lista. En su caso se puede mantener el mismo criterio utilizado para el cálculo de la longitud, pero en cambio, que la adición de para cada elemento que se debe añadir la longitud total de cadenas:

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

cuenta que desde los datos dentro de su elemento de lista si de tipo char* el tamaño efectivo de Data_Struct es solo 4 punteros, es por eso que necesita usar una función de soporte como strlen, de lo contrario no puede obtener real dimensión de las cadenas.

¿Cuál es la diferencia?

sizeof(Data_Struct) == 16 

porque el tipo Data_Struct contiene 4 punteros, tres para los punteros a char y otro para el siguiente elemento de la lista

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

porque estas variables son de tipo puntero a char, por lo que son puntero, sin valor concreto, y por lo general es de 4 bytes (estoy asumiendo una arquitectura de 32 bits)

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

becaus La función funciona exactamente para calcular la longitud de una cuerda.

Answer 2

Bueno, se puede recorrer la lista para calcular el recuento con bastante facilidad. Obviamente, la memoria total será igual al número de elementos multiplicado por el tamaño de cada elemento (sizeof(Data_Struct)).

Por supuesto, este será el tamaño de la lista vinculada en sí y no incluye la memoria asignada para las cadenas. Un puntero no tiene ninguna información sobre la cantidad de memoria asignada a la que se refiere, por lo que estrictamente hablando, no se puede calcular la cantidad de memoria total asignada directamente al solo mirar una lista vinculada como esa. Además, puede haber punteros duplicados en la lista vinculada que deberá seguir. Dicho esto, suponiendo que todos los punteros son únicos, puede calcular el número de caracteres en cada elemento sumando los valores de retorno de las llamadas strlen en cada puntero mientras atraviesa la lista (lo que debería ser bastante sencillo).

Answer 3

Una vez que asigna memoria para un nodo (utilizando malloc), debe poder hacer sizeof (yourDataType). Así que para obtener el tamaño total de la lista enlazada se recorre la lista y obtener el recuento de nodos:

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

Por ejemplo:

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

luego de tomar esa cuenta y se multiplica por el tamaño:

size = getCountOfList * sizeof (mydatatype);

Esto le dará el tamaño de la lista vinculada real, pero tenga en cuenta que el nodo de la lista vinculada tiene elementos de puntero que por sí mismos también pueden asignar memoria. Esto tendrá que ser tenido en cuenta ...

Por ejemplo, uno de esos elementos char * dentro del nodo podría malloc algo más de espacio y agotar algo de memoria.

Si realmente necesita todo el tamaño de la lista que incluye elementos asignados para todos los otros punteros char *, por ejemplo, sólo tiene que:

1) recorrer la lista y buscar en cada nodo

2) Para cada nodo verifica si los elementos de cada nodo apuntan a cualquier otra asignación (para instancia char * datos puede asignar 50 caracteres para almacenar). Si no es nulo, obtienes la longitud de la cadena + 1 (para terminar el carácter) y la multiplicas por sizeof (carácter) (para este ejemplo)

3) Lo haces para cada nodo y almacenas ese tamaño , luego pasar al siguiente nodo

4) Usted toma la SUMA de todos estos caracteres * (en este caso) para cada nodo y los acumula para toda la lista.

5) Una vez que tenga eso simplemente agregue esta suma que le dará el tamaño de todos los nodos.

tamaño Luego total se convierte en:

SizeOfAllNode + (SizeOf(dataType) * CountOfNodes) 

Answer 4

mantener una cuenta corriente como agregar o quitar nodos. De esta forma, no tiene que recorrer la lista, resumiendo cada nodo cada vez que quiera contar. Simplemente haga referencia a su valor actualizado.

Answer 5

Para calcular el tamaño de la lista, simplemente tome sizeof(MyData) y multiplique por la cantidad de nodos.

Si desea incluir el tamaño de los datos de cadena en la lista, puede calcular la memoria utilizada por una cadena como (strlen(str) + 1) * sizeof(char), suponiendo, por supuesto, que la cadena se asignó exactamente al tamaño correcto.

Answer 6

Si necesita obtener el tamaño de los datos más de una vez, sería más prudente realizar un seguimiento al agregar elementos a la lista, pero el código para calcular la fuerza bruta es bastante fácil.

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

Se puede recorrer todos los miembros de su lista y acumular el número de caracteres en el nombre, la tarea y, Pos.

Sin embargo, si va a hacer esto varias veces, almacenaría el número de caracteres de cada campo al poblar el nodo en lugar de contarlos una vez y otra vez.

lo tanto, su estructura se puede definir como sigue:

struct Data_Struct { 
    char *Name; 
    int NameCount; 

    char *Task; 
    int TaskCount; 

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

y iteración a través de la lista podría ser algo como:

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