C/Traballar con listas encadeadas: Diferenzas entre revisións
Contido eliminado Contido engadido
m Eliminadas unhas chaves innecesarias. |
Amplío (continuará...) |
||
Liña 7:
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
É dicir, en casos en que se sabe que se van ir introducindo e borrando datos en distintas posicións que non van ser sempre a última (como se faría no caso das matrices), será máis eficiente traballar con listas encadeadas, pois este tipo de operacións con matrices resultarían, como mínimo, pouco útiles.
==Tipos==
Existen distintos tipos de listas encadeadas, que fundamentalmente consisten no mesmo, pero que difiren na súa función, e por tanto tamén difiren lixeiramente na forma en que se traballa con elas. Así, segundo o que vaiamos facer con elas, falaremos de:
;Lista encadeada simple
:Este tipo de lista sempre está ordenada por un dos datos dos seus elementos.
;Pila
:É un contedor de datos non ordenados, que simplemente se van introducindo ao principio da pila, en lugar de ao final ─que é como se faría no caso das matrices─. É por iso que nas funcións que traballar con pilas non se fornece nunca un dato a buscar, xa que sempre se traballa co primeiro dato da pila.
:As funcións das pilas son catro:
:*engadir elementos á pila,
:*borrar elementos da pila,
:*gravar a pila en disco e
:*eliminar a pila.
;Cola
:Ao igual que as pilas, tampouco está ordenada por ningún dos datos dos seus elementos. A diferencia con respecto ás pilas é que, mentres que nas pilas se traballa co último elemento engadido á mesma, no caso das colas sempre se traballará co último elemento, é dicir, se traballará cos seus elementos en orde de chegada.
:Isto significa que para traballar con colas teremos que ter non só o enderezo en memoria do primeiro elemento, senón tamén o enderezo do último dos seus elementos. O primeiro valerá para introducir novos datos, e o segundo para traballar cos datos e borralos unha vez se utilicen.
==Declaración==
Para declarar unha lista encadeada cómpre ter claro previamente o comportamento das [[{{BASEPAGENAME}}/Estruturas|estruturas]]. Cada elemento da lista ─elemento─ será unha estrutura conformada polos datos do elemento e un punteiro a unha estrutura do mesmo tipo, que será o que apunte ao seguinte elemento (salvo que se trate do
Por suposto, necesitaremos ademais dos elementos un punteiro solto que apunte ao primeiro elemento da lista encadeada
==Traballo con listas==
Liña 30 ⟶ 48:
De xeito que se poida acceder a todos os elementos da lista, pero non se poida modificar o valor do punteiro da lista, é dicir, o punteiro ao primeiro elemento.
===Engadir
====Crear un elemento====
Antes de engadir un elemento a unha lista será necesario crealo, é dicir, facerlle espazo en memoria, xeralmente un a un a través dunha función como a seguinte:
<source lang=c>
estrutura * CrearUnElemento(void)
Liña 45 ⟶ 64:
</source>
O programa que chamase á función debería controlar o valor que devolvese a función, e en caso de ser o punteiro nulo, actuar en consecuencia.
====Engadir un elemento a unha lista simple====
Imaxinemos unha lista encadeada simple en que os seus elementos conteñen só un dato de tipo <code>signed int</code> ─ademais de conter o punteiro que sinala ao seguinte elemento da lista─. Isto simplificará o exemplo, pero valerá para ilustrar calquera caso. Para introducir novos datos nesta lista encadeada simple de exemplo utilizaríase unha función como a seguinte:
<source lang=c>
signed short int
{
// Declaración de variables
Liña 81 ⟶ 103:
</source>
Cómpre ter en conta que este é o programa base á hora de engadir novos datos a unha lista encadeada simple e, xa que logo, pode ser que o programador queira modificalo para personalizalo. E por suposto, será necesario facer polo menos as modificacións necesarias para que a función se adapte a un tipo de elemento distinto ─cuxo contido non sexa un simple <code>signed int</code>─.
====Engadir un elemento a unha pila====
Imaxinemos unha pila en que os seus elementos conteñen só un dato de tipo <code>signed int</code> ─ademais de conter o punteiro que sinala ao seguinte elemento na pila─. Isto simplificará o exemplo, pero valerá para ilustrar calquera caso. Para introducir novos datos nesta pila de exemplo utilizaríase unha función como a seguinte:
<source lang=c>
signed short int
{
// Declaración de variables
estrutura * pila = NULL;
estrutura * novo = NULL;
// Recíbese a pila.
pila = *punteiro;
// Créase espazo en memoria para un novo elemento (esta función viuse máis arriba).
novo = CrearUnElemento();
if(novo == NULL)
{
printf("Non se puido reservar espazo para un novo elemento.\n");
return -1;
}
// Almacénanse os datos no novo elemento (neste exemplo só un dato).
novo->dato = dato;
// Apúntase o enderezo do seguinte elemento no novo elemento.
novo->seguinte = pila;
// Facer que o punteiro da pila apunte ao novo elemento, que será o primeiro.
*punteiro = novo;
return 0; // Saída correcta da función.
}
</source>
Cómpre ter en conta que este é o programa base á hora de engadir novos datos a unha pila e, xa que logo, pode ser que o programador queira modificalo para personalizalo. E por suposto, será necesario facer polo menos as modificacións necesarias para que a función se adapte a un tipo de elemento distinto ─cuxo contido non sexa un simple <code>signed int</code>─.
====Engadir un elemento a unha cola====<!-- Sen completar. -->
Imaxinemos unha pila en que os seus elementos conteñen só un dato de tipo <code>signed int</code> ─ademais de conter o punteiro que sinala ao seguinte elemento na cola─. Isto simplificará o exemplo, pero valerá para ilustrar calquera caso. Para introducir novos datos nesta cola de exemplo utilizaríase unha función como a seguinte:
<source lang=c>
signed short int InserirUnElemento(estrutura ** punteiro, signed int dato)
{
// Declaración de variables
estrutura * pila = NULL;
estrutura * novo = NULL;
// Recíbese a pila.
pila = *punteiro;
// Créase espazo en memoria para un novo elemento (esta función viuse máis arriba).
novo = CrearUnElemento();
if(novo == NULL)
{
printf("Non se puido reservar espazo para un novo elemento.\n");
return -1;
}
// Almacénanse os datos no novo elemento (neste exemplo só un dato).
novo->dato = dato;
// Apúntase o enderezo do seguinte elemento no novo elemento.
novo->seguinte = pila;
// Facer que o punteiro da pila apunte ao novo elemento, que será o primeiro.
*punteiro = novo;
return 0; // Saída correcta da función.
}
</source>
Cómpre ter en conta que este é o programa base á hora de engadir novos datos a unha pila e, xa que logo, pode ser que o programador queira modificalo para personalizalo. E por suposto, será necesario facer polo menos as modificacións necesarias para que a función se adapte a un tipo de elemento distinto ─cuxo contido non sexa un simple <code>signed int</code>─.
===Borrar elementos das listas===
====Borrar un elemento dunha lista simple====
Para borrar un elemento dunha lista encadeada simple, utilizarase unha función como a seguinte, sempre partindo do exemplo anterior dunha estrutura cun único dato <code>signed int</code> ─ademais do punteiro ao seguinte elemento da lista─:
<source lang=c>
signed short int BorrarUnElemento(estrutura ** punteiro, signed int dato)
{
// Declaración de variables
Liña 118 ⟶ 211:
}
</source>
====Sacar un elemento dunha pila====
Para sacar un elemento dunha pila, que será sempre o primeiro elemento desta dada a súa natureza, utilizarase unha función como a seguinte, sempre partindo do exemplo anterior dunha estrutura cun único dato <code>signed int</code> ─ademais do punteiro ao seguinte elemento da lista─:
<source lang=c>
signed int BorrarUnElemento(estrutura ** punteiro)
{
// Declaración de variables
estrutura * pila = NULL;
signed int dato;
// Recíbese a pila en “pila”, o punteiro ao que apunta “punteiro”.
pila = *punteiro;
// Grávase o dato do elemento a borrar nunha variable local.
dato = pila->dato;
// Ponse o inicio da pila no seguinte elemento da mesma.
*punteiro = pila->seguinte;
// Libérase o espazo en memoria do elemento a borrar.
free(pila);
// Devolución do dato que contiña o elemento borrado.
return dato;
}
</source>
Nótese que nunha pila non ten sentido borrar un elemento se non é para traballar con el e logo borralo, emporiso que a operación de borrado devolve o dato borrado en vez de recibir o dato que se quere borrar.
==Véxase tamén==
| |||