Lesson14

Vejamos como implementar listas simplesmente ligadas e duplamente ligadas em que a cabeça da lista é passada como parâmetro das funções de inserção e remoção, que também terão de retornar a cabeça da lista para o caso de esta ter mudado.

Lista simplesmente ligada

struct node {
  int value;
  struct node *next;
};

typedef struct node *link;

/* Insercao ordenada numa lista simplesmente ligada de inteiros */
link list_insert(link head, int value)
{
  link node, prev, curr;

  prev = NULL;
  curr = head;

  while(curr != NULL && curr->value < value) {
    prev = curr;
    curr = curr->next;
  }

  node = (link) malloc(sizeof(struct node));
  node->value = value;
  node->next = curr;

  if (prev != NULL)
    prev->next = node;
  else
    head = node;

  return head;
}

/* Remocao de um elemento da lista */
link list_delete(link head, int value)
{
  link prev, curr;

  prev = NULL;
  curr = head;

  while (curr != NULL && curr->value < value) {
    prev = curr;
    curr = curr->next;
  }

  /* Encontramos o elemento? */
  if (curr !=NULL && curr->value == value) {
    
    if (prev != NULL)
      prev->next = curr->next;
    else
      head = curr->next;

    free(curr);
  }

  return head;
}

Lista duplamente ligada

struct node {
  int value;
  struct node *next, *prev;
};

typedef struct node *link;

/* Insercao ordenada numa lista simplesmente ligada de inteiros */
link list_insert(link head, int value)
{
  link node, prev, curr;

  prev = NULL;
  curr = head;

  while(curr != NULL && curr->value < value) {
    prev = curr;
    curr = curr->next;
  }

  node = (link) malloc(sizeof(struct node));
  node->value = value;
  node->next = curr;
  node->prev = prev;

  if (prev != NULL)
    prev->next = node;
  else
    head = node;

  if (curr != NULL)
    curr->prev = node;

  return head;
}

/* Remocao de um elemento da lista */
link list_delete(link head, int value)
{
  link curr = head;

  while (curr != NULL && curr->value < value)
    curr = curr->next;

  /* Encontramos o elemento? */
  if (curr !=NULL && curr->value == value) {
    
    if (curr->prev != NULL)
      curr->prev->next = curr->next;
    else
      head = curr->next;

    if (curr->next != NULL)
      curr->next->prev = curr->prev;

    free(curr);
  }

  return head;
}

Exemplo: pilha dinâmica de inteiros

Neste exemplo não podemos perder a referência para o topo da pilha, ou seja, o ponteiro top.

#include <stdio.h>
#include <stdlib.h>

/*
 *         +----+   +----+   +----+
 *  top -->| 10 |   |  8 |   | 15 |
 *         +----+   +----+   +----+
 *         |   -+-->|   -+-->|   -+--> NULL
 *         +--+-+   +----+   +----+
 */

struct node{
  int value;
  struct node*next;
};

static struct node *top;

void init() /* inicializa a pilha */
{
  top = NULL;
}

void push(int value) /* introduz novo elemento no topo */
{
  struct node *new;

  new = (struct node *) malloc(sizeof(struct item));
  new->value = value;
  new->next = top;
  top = new;
}

int is_empty() /* pergunta se está vazia */
{
  return top == NULL;
}

int pop() /* apaga o topo */
{
  int value;
  struct node *old;

  if (!is_empty()) {
    value = top->value;
    old = top;
    top = top->next;
    free(old);
    return value;
  }
  else
    return -1;
}

Problema: Como obter o número de elementos da Pilha?
Solução: É necessário percorrer toda a Pilha! Alternativa?

Exemplos lista de strings

Vamos utilizar uma lista simplesmente ligada mas em que Item é char *. Notar que neste exemplo não podemos perder a referência para o início da lista.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
    char *text;
    struct node *next;
}Node; 

typedef Node *link;

link NEW(char* text)
{
    link x = (link) malloc(sizeof(struct node));
    x->text = 
       (char*) malloc(sizeof(char)*(strlen(text)+1));
    strcpy(x->text, text);
    x->next = NULL;
    return x;
}

link insertBegin(link head, char* text)
{
    link x = NEW(text);
    x->next = head;
    return x;
}

link insertEnd(link head, char* text)
{
    link x;
    if(head == NULL)
        return NEW(text);
    for(x = head; x->next != NULL; x = x->next)
        ;
    x->next = NEW(text);
    return head;
}

link lookup(link head, char* text)
{
    link t;
    for(t = head; t != NULL; t = t->next)
        if(strcmp(t->text, text) == 0)
            return t;
    return NULL;
}

link delete(link head, char* text)
{
    link t, prev;
    for(t = head, prev = NULL; t != NULL;
        prev = t, t = t->next) {
        if(strcmp(t->text, text) == 0) {
            if(t == head)
                head = t->next;
            else
                prev->next = t->next;
            free(t);
        }
    }
    return head;
}

/* Criar lista com argumentos da linha de comandos */
int main(int argc, char* argv[])
{
    int i;
    link head = NULL;
    /* inserir todos os elementos na lista*/
    for(i = 1; i < argc; i++)
        head = insertEnd(head, argv[i]);
    print(head);		/* imprime toda a lista*/
    /* remover o um elemento (lido do stdin) */
    scanf("%d", &i);
    head = delete(head, argv[i]);
    print(head);	/* voltamos a imprimir toda a lista */
    return 0;
}

Em alternativa, podemos também implementar a inserção no início sem retornar:

void insertBegin(link *headptr, char *text)
{
    link x = NEW(text);
    x->next = *headptr;
    *headptr = x;
}