C/Traballar con listas encadeadas

C
← Volver a Traballar con ficheiros	Traballar con listas encadeadas	Seguir con Traballar con árbores →

As listas encadeadas son un tipo de estrutura lineal de datos. Ao contrario que as matrices, nas que un punteiro sinala a un elemento que contén varios datos, nas listas encadeadas un punteiro sinala ao primeiro elemento 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 temos 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 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 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 último elemento da lista encadeada).

Por suposto, necesitaremos ademais dos elementos un punteiro solto que apunte ao primeiro elemento da lista encadeada, e en caso de que traballemos cunha cola, será necesario tamén un segundo punteiro que sinale ao último elemento. Estes punteiros serán as únicas variables locais, é dicir, as únicas que non se van reservar en memoria dinámica. Cómpre inicializar estes punteiros con valor nulo, de xeito que isto permita saber que a lista está, en principio, baleira.

Traballo con listas

Nos seguintes exemplos traballarase cunha estrutura chamada elemento froito do seguinte código:

typedef struct estrutura
{
  signed int dato;
  struct estrutura * seguinte;
}
elemento;

Isto simplificará os exemplos, ao mesmo tempo que permitirá facilmente modificar as funcións par adaptalas a un código e unha función máis concretas.

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:

tipo función(elemento ** punteiro, ...){...}

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:

tipo función(elemento * punteiro, ...){...}

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 elementos ás listas

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:

elemento * CrearUnElemento(void)
{
  elemento * punteiro;

  punteiro = (elemento *) malloc(sizeof(elemento));
  if(punteiro == NULL)
    printf("Houbo un erro: non hai memoria abondo.\n");

  return punteiro;
}

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

O proceso para engadir un novo elemento a unha lista encadeada simple non é complicao de entender. A función recibirá a información nova que se vai engadir á lista e o enderezo do enderezo da lista (por se tiver que cambiar). Entón, a función traballará con tres punteiros, un para gardar un elemento da lista (o que se vai analizando), outro para gardar o elemento anterior (que irá mudando) e outro para gardar o novo elemento.

Así, o proceso consistirá básicamente en ir movéndose polos datos da lista ata atopar un elemento ─actual─ que teña que ir diante do novo elemento. Unha vez atopado, fanse as modificacións necesarias para que anterior apunte a novo e este a actual, é dicir, consisten en poñer o novo elemento entre o anterior a el e o seguinte.

Imaxinemos unha lista encadeada simple en que os seus elementos conteñen só un dato de tipo signed int ─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:

signed short int InserirUnElemento(elemento ** punteiro, signed int dato)
{
  // Declaración de variables
  elemento * novo = NULL;
  elemento * lista = NULL;
  elemento * anterior = NULL;

  novo = CrearUnElemento(); // Pídese espazo para un elemento novo. A función corresponderíase coa anterior.
  if(novo == NULL)
  {
    printf("Non se puido reservar espazo para un novo elemento.\n");
    return -1;
  }

  lista = *punteiro; // Recíbese a lista en “lista”, o punteiro ao que apunta “punteiro”.

  while(lista && lista->dato < dato) // Cómpre ter en conta que a lista sempre ten que estar ordenada.
  {
    anterior = lista; // Apúntase primeiro o elemento actual.
    lista = lista->seguinte; // Avánzase ao seguinte elemento da lista.
  }

  novo->dato = dato; // Métese o dato no elemento reservado para o mesmo.
  novo->seguinte = lista; // Punteiro ao seguinte elemento, ou a nada se é o último elemento.

  if(anterior == NULL) // Se a lista estaba baleira...
    *punteiro = novo; // O punteiro á lista apunta ao elemento, dado que é o único da lista.
  else
    anterior->seguinte = novo;

  return 0; // Saída correcta da función.
}

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 signed int─.

Engadir un elemento a unha pila

Imaxinemos unha pila en que os seus elementos conteñen só un dato de tipo signed int ─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:

signed short int InserirUnElemento(elemento ** punteiro, signed int dato)
{
  // Declaración de variables
  elemento * pila = NULL;
  elemento * 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.
}

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 signed int─.

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 signed int ─ademais do punteiro ao seguinte elemento da lista─:

signed short int BorrarUnElemento(elemento ** punteiro, signed int dato)
{
  // Declaración de variables
  elemento * lista = NULL;
  elemento * anterior = NULL;

  lista = *punteiro; // Recíbese a lista en “lista”, o punteiro ao que apunta “punteiro”.

  while(lista && lista->dato < dato) // Cómpre ter en conta que a lista sempre ten que estar ordenada.
  {
    anterior = lista; // Apúntase primeiro o elemento actual.
    lista = lista->seguinte; // Avánzase ao seguinte elemento da lista.
  }

  if(lista->dato == dato) // Se se atopou o dato a borrar...
  {
    if(anterior == NULL) // Se hai que borrar o primeiro elemento...
      *punteiro = lista->seguinte;
    else // En caso de ser calquera outro elemento...
      anterior->seguinte = lista->seguinte;

    free(lista); // Libérase a memoria almacenada en “lista”, que contén o elemento a borrar.
  }
  else // Se non se atopou o dato...
  {
    printf("Non se atopou o dato na lista.\n");
    return -1;
  }

  return 0; // Saída correcta da función.
}

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 signed int ─ademais do punteiro ao seguinte elemento da lista─:

signed int SacarUnElemento(elemento ** punteiro)
{
  // Declaración de variables
  elemento * 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;
}

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.

Borrar unha lista

Independentemente de que se trate dunha lista encadeada simple, unha pila ou unha cola, para borrar toda unha lista encadeada utilizarase unha función como a seguinte:

void BorrarALista(elemento * lista)
{
  // Declaración de variables.
  elemento * seguinte;

  // Ciclo de borrado dos sucesivos elementos da lista.
  while(lista)
  {
    seguinte = lista->seguinte;
    free(lista);
    lista = seguinte;
  }

  // Saída correcta da función.
  return;
}

Véxase tamén

Exercicios

• Exercicios de traballo con listas encadeadas

C
← Volver a Traballar con ficheiros	Traballar con listas encadeadas	Seguir con Traballar con árbores →