C/Traballar con listas encadeadas: Diferenzas entre revisións
Contido eliminado Contido engadido
Creo baleira, comezarei a completala mañá (espero) |
Vou gardando, sigo tomando apuntes pero non sei se haberá máis. |
||
Liña 1:
{{Navegador|Traballar con ficheiros|Comentarios}}
As '''listas encadeadas''' son un tipo de estrutura lineal de datos. Ao contrario que as [[{{BASEPAGENAME}}/Matrices|matrices]], nas que un [[{{BASEPAGENAME}}/Punteiros|punteiro]] sinala a un bloque que contén varios datos, nas listas encadeadas un punteiro sinala ao primeiro bloque de memoria, que á súa vez ─ademais de conter unha serie de datos─ sinala ao segundo, que á súa vez sinala ao terceiro, etc.
Mentres que no traballo con matrices o acceso aos datos ─orde lóxica─ adoita facerse do mesmo xeito en que están almacenados ─orde física─, lendo os datos un tras o outro, nas listas encadeadas a orde física e a orde lóxica non coinciden.
Dende o punto de vista da memoria, a matriz resulta máis eficiente, pois precisa de menos memoria. Pero existen outros factores a ter en conta á hora de comparar matrices e listas encadeadas.
Por exemplo, imaxinemos que temo unha matriz que conta con, digamos, 30 datos. Agora pensemos que queremos meter un dato adicional tras o segundo dato. No caso da matriz, sería preciso ampliar a matriz e mover en memoria todos os datos que contén a matriz a partires do espazo en que queremos meter o novo dato. Porén, no caso dunha lista encadeada, abondaría con engadir en memoria o novo dato, e simplemente modificar o dato anterior de xeito que apunte ao novo dato, así como facer que o novo dato apunte ao seguinte dato.
É dicir, en casos en que se sabe que se van ir introducindo e borrando datos en distintas posicións, será máis eficiente traballar con listas encadeadas, pois este tipo de operacións con matrices resultarían, como mínimo, pouco útiles.
==Declaración==
Para declarar unha lista encadeada cómpre ter claro previamente o comportamento das [[{{BASEPAGENAME}}/Estruturas|estruturas]]. Cada elemento da lista ─bloque─ será unha estrutura conformada polos datos do bloque e un punteiro a unha estrutura do mesmo tipo, que será o que apunte ao seguinte bloque (salvo que se trate do derradeiro bloque da lista encadeada.
Por suposto, necesitaremos ademais dos bloques un punteiro solto que apunte ao primeiro bloque da lista encadeada. Esta será a única variable local, é dicir, a única que non se vai reservar en memoria dinámica. Cómpre ''inicializar'' este punteiro ao primeiro bloque co valor nulo, de xeito que isto permita saber que a lista está, en principio, baleira.
==Traballo con listas==
===Pasarlle unha lista a unha función===
Ao pasarlle unha lista a unha función que vai traballar con ela (engadir ou borrar datos), hai que pasarlle o punteiro da lista “por referencia”. Iso significa que á función se lle pasa o enderezo en memoria do punteiro que á súa vez contén o enderezo en memoria do primeiro elemento da lista, o que permitirá ao programador modificar o valor deste punteiro. Isto quedaría da seguinte forma na función que recibe a lista encadeada:
<source lang=c>
tipo función(estrutura ** punteiro, ...){...}
</source>
Se o que se vai facer é percorrer a lista encadeada (contar os elementos, visualizalos, copialos en disco, liberar a lista, etc.), isto non será necesario, e abondará con pasarlle a lista na seguinte forma:
<source lang=c>
tipo función(estrutura * punteiro, ...){...}
</source>
De xeito que se poida acceder a todos os bloques da lista, pero non se poida modificar o valor do punteiro da lista, é dicir, o punteiro ao primeiro bloque.
===Engadir bloques á lista===
Para crear bloques para a lista, farase xeralmente un a un a través dunha función como a seguinte:
<source lang=c>
estrutura * función(void)
{
estrutura * punteiro;
punteiro = (estrutura) malloc(sizeof(estrutura));
if(punteiro == NULL)
{
printf("Houbo un erro: non hai memoria abondo.\n");
return punteiro;
}
return punteiro;
}
</source>
O programa que chamase a función debería controlar o valor que devolvese a función, e en caso de ser o punteiro nulo, actuar en consecuencia.
==Véxase tamén==
| |||