/ Listas Em Construção, com vi!!!

Data da última atualização: 24/04/2000
copyright Adriano Cruz 1999

Listas

------------------------------------
  1. Introdução
  2. Definições Básicas
  3. Listas com Alocação Seqüencial
  4. Pilhas com Alocação Seqüencial
  5. Listas com Alocação Encadeada
  6. Listas Simplesmente Encadeadas
  7. Listas Circulares
  8. Exercícios
-------------------------------------

Introdução

 

Neste capítulo iremos discutir alguns aspectos de listas e como podemos implementar esta estrutura de dados em C. Não iremos abordar extensivamente este assunto, mas apenas discutir os algoritmos mais importantes e mostrar como eles podem ser implementados em C.


 

----------------------------

Listas


---------------------------------------------

Listas - Definições Básicas

Uma lista linear de informações é uma estrutura de dados simples que armazena informações sobre dados que apresentam uma relação entre seus elementos.

As operações mais frequentes em listas são a busca, inserção e remoção de um determinado elemento. Outras operações que costumam ocorrer são a alteração de um elemento particular da lista, ordenação dos elementos da lista segundo uma determinada chave, procura do último ou do primeiro elemento da lista, etc.

Os elementos da lista podem ser armazenados em posições contíguas da memória e neste caso temos uma lista seqüencial. Podemos também armazenar os elementos em posições quaisquer da memória e neste caso temos de armazenar em cada elemento um indicador de onde está o próximo elemento da lista. Este último método é conhecido como alocação encadeada.

-----------------------------------------------------------

Listas com Alocação Seqüencial

A maneira mais simples de se manter uma lista na memória do computador é colocar seus nós em posições contíguas. Neste caso o elemento j+c estará c bytes (ou palavras, depende do sistema) à frente do elemento j da lista. A constante c corresponde ao número de bytes (ou palavras) necessário para armazenar cada elemento da lista. Cada elemento da lista é comumente chamado de nó. Um nó da lista pode conter vários tipos de informações que são armazenados em campos. Cada nó contém um (ou mais) elemento(s) que identificam unicamente o nó, a chave. Uma lista pode estar ordenada ou não de acordo com a chave.

O programa list0201.c mostra um exemplo de busca em uma lista seqüencial. O algoritmo, contido na função busca1, é simples e percorre a lista toda até encontrar o elemento. A função recebe a lista e o elemento a ser procurado. Note que o número de elementos na lista n é conhecido pelo algoritmo.
 
 

/* Programa list0201.c */
#include <stdio.h>
#define MAX 4

struct Taluno {
        char nome[40];
        unsigned long int dre;
};

int busca1 ( struct Taluno t[], unsigned long int );
void le ( struct Taluno t[]);
void imprime ( struct Taluno t[]);

void main ()
{
    int aluno;
    unsigned long dre;
    char linha[80];
    struct Taluno turma[MAX];

    le (turma); /* le dados da turma de MAX alunos */
    imprime (turma); /* imprime dados para verificar se correto */
    /* uso sscanf, mais seguro que scanf */
    puts("Qual o DRE a procurar? "); gets(linha);
    sscanf(linha, "%lu", &dre);

    aluno = busca1 (turma, dre);
    if (aluno == -1)
        puts("Nao ha aluno com este dre.");
    else
       printf("O aluno com dre %lu chama-se %s\n",
            turma[aluno].dre, turma[aluno].nome);

    exit(0);

}

void le (struct Taluno t[]) {
     int i;
     char linha[80];

     for (i=0; i<MAX; i++) {
         puts("Nome ? "); gets (t[i].nome);
         puts("DRE ? ");  gets(linha);
         sscanf(linha, "%lu", &t[i].dre);
     }
}

void imprime (struct Taluno t[]) {
     int i;

     puts("Dados da turma");
     for (i=0; i<MAX; i++) {
         printf("\nAluno %d\n", i);
         printf("Nome = %s\n", t[i].nome);
         printf("Nome = %lu\n", t[i].dre);
     } 
}

/* Busca um elemento na lista L */
int busca1 (struct Taluno turma[], unsigned long int dre) {
    int i=0; int aluno=-1;

    /* vou assumir que a lista contem MAX alunos */
    while (i < MAX) {
          if ( turma[i].dre == dre) {
             aluno = i;
             i=MAX;
          }
          else i++;
    }
    return aluno; /* se -1 nao achei, senao indice do aluno */
}
No exemplo anterior são feitas duas comparações a cada interação ( i < MAX e turma[i].dre == dre). Para diminuir o número de comparações vamos usar um artifício simples: colocar uma posição extra no final da lista e sempre que for necessário buscar um elemento na lista, o seu valor será inserido nesta posição extra. Deste modo sempre acharemos o elemento na lista. No entanto, se o elemento estiver no final da lista significa que o elemento não foi encontrado. Observar que a lista passa ter agora uma posição a mais, que é reservada para o elemento a ser procurado.

O programa list0202.c mostra um exemplo de busca em uma lista seqüencial com uma posição a mais.

/* programa list0202.c */
#include <stdio.h>

/* A lista cabem 4 elementos o elemento 5
   e para a elemento a ser procurado
*/
#define MAX 5

struct Taluno {
        char nome[40];
        unsigned long int dre;
};


int busca1 ( struct Taluno t[], unsigned long int );
void le ( struct Taluno t[]);
void imprime ( struct Taluno t[]);

void main ()
{
    int aluno;
    unsigned long dre;
    char linha[80];
    struct Taluno turma[MAX];

    le (turma);
    imprime (turma);
    puts("Qual o DRE a procurar? "); gets(linha);
    sscanf(linha, "%lu", &dre);
    aluno = busca1 (turma, dre);
    if (aluno == -1)
       puts("Nao ha aluno com este dre.");
    else
       printf("O aluno com dre %lu chama-se %s\n",
               turma[aluno].dre, turma[aluno].nome);
    exit(0);

}

void le (struct Taluno t[]) {
     int i;
     char linha[80];

     for (i=0; i<MAX-1; i++) {
         puts("Nome ? "); gets (t[i].nome);
         puts("DRE ? ");  gets(linha);
         sscanf(linha, "%lu", &t[i].dre);
     }
}

void imprime (struct Taluno t[]) {
     int i;

     puts("Dados da turma");
     for (i=0; i<MAX-1; i++) {
         printf("\nAluno %d\n", i);
         printf("Nome = %s\n", t[i].nome);
         printf("Nome = %lu\n", t[i].dre);
     } 
}

/* Busca um elemento na lista L */
int busca1 (struct Taluno turma[], unsigned long int dre) {
    int i=0;

    turma[MAX-1].dre=dre;
    while (turma[i].dre != dre) i++;
    if (i != MAX-1 ) return i;
    else return -1;
}


Os exemplos anteriores assumiam dois fatos a cerca da lista: a lista está cheia e desordenada. Quando a lista está ordenada a procura pode ser interrompida antes de chegar ao fim da lista. Neste algoritmo ao invés de procurar o elemento, o teste é se o elemento da lista é menor que o procurado.

O programa list0203.c mostra um exemplo de busca em uma lista ordenada. Para facilitar vamos mostrar apenas a rotina busca_ord que executa este algoritmo, já que todo o restante do programa é similar ao anterior. No arquivo indicado na ligação mostramos o arquivo todo.

/* programa list0203.c */

/* Busca um elemento na lista L */
int busca_ord (  Taluno turma[], unsigned long int dre) {
    int i=0;

    turma[MAX-1].dre=dre;
    while (turma[i].dre < dre) i++;
    if (i == (MAX-1) || turma[i].dre != dre ) return -1; /* nao achei. */
    else return i;
}

Um algoritmo mais eficiente para busca em uma lista ordenada é o algoritmo de busca binária. Primeiro o algoritmo procura o elemento no elemento do meio da tabela. Caso não esteja ele descarta a metade onde o elemento não está e passa a procurar no meio da metade que sobrou. O algoritmo vai dividindo a lista em duas metades, sempre descartando a metade onde o elemento não está.

O programa list0204.c mostra um exemplo de busca binária em uma lista ordenada. Para facilitar vamos mostrar somente a rotina busca_bin que implementa este algoritmo.

/* programa list0204.c */
/* Busca um elemento na lista L */
int busca_bin (  Taluno t[], unsigned long int dre) {
    int inf=0, sup=MAX-1, achou=-1, meio;

    while (inf <= sup)
    {
        meio = 0.5*(inf+sup);
        if (t[meio].dre == dre)
        {
            achou=meio;
            inf = sup+1;            
        }
        else if (t[meio].dre<dre)
                inf = meio+1;
        else sup = meio - 1 ;
    }
    return achou;
}

Agora passaremos a apresentar algoritmos para inserir e remover elementos de uma lista. Ambos os algoritmos utilizam a rotina de busca para inserir e remover.

Primeiro vamos apresentar um algoritmo de inserção que não precisa que a lista esteja ordenada. Neste algoritmo o elemento, caso ele não já esteja na lista, é inserido após o último elemento. O algoritmo de remoção move, a partir do último elemento até o elemento seguinte ao que será removido, todos os elementos uma posição para à esquerda.

O exemplo list0206.c abaixo mostra um programa que inclui estes dois algoritmos. Como a lista não estará sempre cheia, já que estaremos removendo e inserindo elementos a todo instante, iremos modificar as rotinas de busca. A modificação adiciona uma variável n que contém o número de elementos na lista no instante em questão. O programa pede ao usuário que indique através de uma letra qual operação deseja executar. As operações possíveis são as seguintes: [I]nserir, [R]emover, [L]istar e [S]air. Para facilitar o entendimento a lista utilizada contém somente números inteiros. O exercício 1, pede a construção de um programa similar a este, apenas modificando a lista de modo que ela contenha uma estrutura mais complexa.

/* programa list0206.c */
/* Busca um elemento na lista L */
#define MAX 5
#include <stdio.h>
#include <ctype.h>

char meu_menu();
void insere(int item[], int *n);
void meu_remove(int item[], int *n);
void listar(int item[], int n);
void ordena(int item[], int n);
int busca_bin (int item[], int n, int x);

void main()
{
    int item[MAX];
    int n=0, sair=0;
    int a, b, t;

    char opcao;

    do {
           opcao = meu_menu();
           switch (opcao) {
                  case 'i':
                       insere(item, &n);
                       break;
                  case 'r':
                       meu_remove(item, &n);
                       break;
                  case 'l':
                       listar(item, n);
                       break;
                  case 's':
                       sair = 1;
                       break;
                  default:
                          puts("Opcao invalida.");
                          break;
           }
    } while (!sair);
}

void ordena(int item[], int n){

     int a, b, t;

     for (a=1; a<n; ++a)
     {
        t = item[a];
        for (b=a-1; b>=0 && t < item[b]; b--) {
            item[b+1]=item[b];
        }
        item[b+1]=t;
    }
}

int busca_bin (int item[], int n, int x) {
    int inf=0, sup, meio, achou=-1;

    sup = n-1;
    while (inf <= sup) {
          meio = 0.5*(inf+sup);
          if (item[meio]==x) {
             achou=meio;
             inf = sup + 1;
          }
          else if (item[meio]<x) 
                  inf = meio+1;
               else
                   sup = meio-1;
    }
    return achou;
}

void listar (int item[], int n) {

     int i;

     for (i=0; i<n; i++) printf("elemento %d = %d \n", i, item[i]);

}

char meu_menu () {

     char opcao, linha[80];
     // limpa();
     puts("Qual a sua opcao?");
     puts("[L]istar, [I]nserir, [R]emover, [S]air");
     gets(linha);
     sscanf(linha, "%c", &opcao);
     return tolower(opcao);
}

void imprime (int item[])
{
    int i;

    for (i=0; i<5; i++) {
        printf("%d ", item[i]);
    }
    printf("\n");
}


void insere (int item[], int *n) {
     int t;
     char linha[80];

     printf("Valor a inserir? ");
     gets(linha); sscanf(linha, "%d", &t);

     if (*n < MAX-1) {
        if ( busca_bin(item, *n, t) == -1) {
           item[*n] = t;
           *n=*n+1;
           ordena (item, *n);
        }
        else puts("Elemento ja existe na tabela.");
     }
     else puts("Lista ja cheia.");


}

void meu_remove (int item[], int *n) {

     int x, indice, i;
     char linha[80];    


     if (*n != 0) {
        printf("Valor a remover? ");
        gets(linha); sscanf(linha, "%d", &x);
        indice = busca_bin(item, *n, x);
        printf("Indice = %d\n", indice);
        if (indice != -1) {
           for (i=indice; i<*n; i++) item[i] = item[i+1];
           *n = *n - 1;
        }
        else puts("Nao existe este elemento.");
     }
     else puts("Lista vazia"); 
}
-----------------------------------------------------------

Pilhas com Alocação Seqüencial

Uma pilha é uma lista em que os elementos são inseridos e removidos em uma posição especial, o topo da pilha. A figura pilha apresentada abaixo mostra como se processam operações que envolvem acesso a uma pilha.


Operações em uma pilha























Uma imagem simples pode ilustrar o funcionamento das pilhas. Considere um restaurante onde os clientes do tipo self-service. Neste restaurante, para se servirem, os clientes retiram pratos e os empregados colocam pratos limpos em uma pilha. Observe que os empregados colocam pratos no topo da pilha, o mesmo local de onde os clientes retiram os pratos.

O exemplo list0207.c, listado abaixo, mostra um programa que permite inserir e retirar elementos de uma pilha.

/* programa list0207.c */
/* Exemplo de pilha */
#define MAX 10
#include <stdio.h>
#include <ctype.h>

char meu_menu();
void insere(int item[], int *topo);
void meu_remove(int item[], int *topo);
void listar(int item[], int topo);

void main()
{
    int item[MAX];
    int topo=-1, sair=0;

    char opcao;

    do {
           opcao = meu_menu();
           switch (opcao) {
                  case 'i':
                       insere(item, &topo);
                       break;
                  case 'r':
                       meu_remove(item, &topo);
                       break;
                  case 'l':
                       listar(item, topo);
                       break;
                  case 's':
                       sair = 1;
                       break;
                  default:
                          puts("Opcao invalida.");
                          break;
           }
    } while (!sair);
}


void listar (int item[], int topo) {
  /* Esta rotina esta aqui somente para depuracao */
     int i;

     for (i=0; i<topo; i++) printf("elemento %d = %d \n", i, item[i]);

}

char meu_menu () {

     char opcao, linha[80];
     // limpa();
     puts("Qual a sua opcao?");
     puts("[L]istar, [I]nserir, [R]emover, [S]air");
     gets(linha);
     sscanf(linha, "%c", &opcao);
     return tolower(opcao);
}

void insere (int item[], int *topo) {
     int t;
     char linha[80];

     printf("Valor a inserir? ");
     gets(linha); sscanf(linha, "%d", &t);

     if (*topo < MAX) {
       *topo=*topo+1;
       item[*topo] = t;
       printf("Topo = %d\n", *topo);
     }
     else puts("Pilha cheia.");


}

void meu_remove (int item[], int *topo) {

     int x;

     if (*topo != -1) {
       x = item[*topo];
       *topo = *topo-1;
       printf("Retirei %d da pilha.\n", x);
     }
     else puts("Lista vazia"); 
}
Uma pilha pode ser usada para avaliar expressões em notação polonesa. Nesta notação não são necessários parênteses para indicar a ordem em que as operações serão avaliadas. Abaixo mostramos exemplos de expressões na notação parentizada e em notação polonesa reversa.
Parênteses  Polonesa Reversa 
a + b  a b + 
(a + b) - c  a b + c - 
(a + b) * (c -d)  a b + c d - * 
(a + ( b * c ))  a b c * + 
(a + b) * c )  a b + c * 

Observar que cada operando atua sobre os dois elementos que o precedem na expressão. Caso fossemos colocando estes operandos em uma pilha, poderíamos sempre que encontrarmos um operador tirar dois operandos da pilha, executarmos a operação e em seguida guardarmos o resultado na pilha novamente. A figura pilhaex mostrada abaixo ilustra o que acontece na pilha caso tenhamos que avaliar a expressão 3 4 5 * + .
 
 


Exemplo de avaliação de uma expressão com pilha.




O exemplo list0212.c, listado abaixo, mostra um programa que avalia uma expressão em notação polonesa reversa. Notar que o programa assume que a expressão está gramaticalmente correta.

/* programa list0212.c */
/* Calculo de expressao em notacao polonesa reversa */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX 80
#define VERDADE 1
#define FALSO 0

typedef struct {
  float item[MAX];
  int top;
} pilha;


void imprime(pilha );
float avalia (const char *);
int eOperando (char );
int eOperador (char );
float pop (pilha *);
void push (pilha *, float);
float oper (char , float ,float);

void main()
{
    char exp[MAX];
    
    puts("Entre com a expressão ?");
    gets(exp);

    puts ("Expressão original é "); puts(exp);
    printf("O resultado da expressao e %f\n", avalia(exp));

}

float avalia (const char *expr) {

  int position;
  char symb;
  pilha opndstk;
  float opnd1, opnd2, value;
  
  opndstk.top = -1; /* pilha vazia */
  position = 0; /* primeiro simbolo da expressao */
  symb = expr[position];
  while (symb != '\0') {
    if (eOperando(symb)) {
      value = atof(&symb);
      push(&opndstk, value);
      // imprime(opndstk);
    }
    else if (eOperador(symb)) {
      opnd2 = pop(&opndstk);
      opnd1 = pop(&opndstk);
      value = oper(symb, opnd1, opnd2);
      push(&opndstk, value);
      // imprime(opndstk);
    }
    if (position < MAX) {
      position++;
      symb = expr[position];
    }
  } /* fim do while  e da avaliacao */
  return pop(&opndstk);
}

float oper (char symb, float op1, float op2) {
  
  switch(symb) {
  case '+': return op1 + op2;
  case '-': return op1 - op2;
  case '*': return op1 * op2;
  case '/': 
    if (op2) return op1/op2;
    else {
      puts("Divisao por zero");
      exit(1);
    }
  }
  exit(1);
}

float pop (pilha *p) {
  
  if (p->top >= 0) {
    p->top--;
    return p->item[p->top+1];
  }
  else {
    puts("Underflow");
    exit(1);
  }
}

void push (pilha *p, float op) {
  
  if (p->top < MAX - 1){
    p->top++;
    p->item[p->top] = op;
  }
  else {
    puts("Overflow");
    exit(1);
  }
}

/* Esta funcao serve so para depuracao do programa */
void imprime (pilha p){
  
  int i;
  printf("\nPilha = ");
  for (i=0; i<=p.top; i++) printf("%f ", p.item[i]);
  printf("\n");
}

int eOperador (char c)
{
    if (c == '*' || c == '/' || c == '+' || c == '-') return VERDADE;
    else return FALSO;
}

int eOperando (char c)
{
    if (!eOperador(c) && (c != ' ')) return VERDADE;
    else return FALSO;
}


-----------------------------------------

Listas com Alocação Encadeada


-----------------------------------------

Listas Simplesmente Encadeadas

A Figura lista encadeada abaixo mostra como seria uma lista usando ponteiros para encadear os elementos da lista. O ponteiro pt aponta para o nó inicial da lista. Cada nó está representado por um retângulo dividido em duas partes. Uma das partes contém a informação e a outra o ponteiro para o próximo nó. Observar que o no último nó a seta aponta para a terra, que indica fim da lista.


lista simplesmente encadeada

O algoritmo implista mostra como percorrer uma lista encadeada simples.
void listar (struct tElemento *ptlista) {

     int i=0;
     struct tElemento *pont;

     pont = ptlista;
     while (pont) {
           printf("Elemento %d = %d\n", i++, pont->info);
           pont = pont->prox;      
     }
}
Outros algoritmos relevantes em listas são: busca, inserção e remoção. Para facilitar a busca e localização dos nós a serem removidos e das posições de inserção modificaremos a lista para incluir o que costuma ser chamado de nó cabeça. Neste tipo de lista o primeiro nó não irá conter informação, ele apenas faz com que o algoritmo de busca não necessite diferenciar o primeiro nó dos demais. A figura lista encadeada com nó cabeça ilustra esta lista.


lista encadeada com nó cabeça

A rotina de busca que iremos mostrar é um algoritmo simples que tem como protótipo ponteiros para ponteiros. O primeiro **ant aponta para o nó anterior ao nó procurado e **ponte aponta para o nó procurado.

void busca ( tElemento *ptlista, int x,  tElemento **ant, tElemento **ponte) {
    /* *ptlista ponteiro para inicio da lista 
       x elemento a ser procurado
       **ant ponteiro para ponteiro do elemento anterior 
       **pont ponteiro para ponteiro do elemento procurado 
    */
    tElemento *ptr;

    *ant = ptlista; /* aponta no anterior */
	*ponte = NULL;  /* aponta no procurado, se nao achar retorna nulo */
    ptr = ptlista->prox; /* aponta no procurado */ 

    while (ptr) {  /* procura enquanto houver chance */
          if (ptr->info < x) { /* ainda nao chegou no no */
             *ant = ptr;
             ptr = ptr->prox;
          }
          else { /* pode ser aqui */
               if (ptr->info == x) *ponte = ptr; /* achou */
               ptr = NULL; /* nao estava na lista */
          }
    }
}
Esta rotina é parte do programa list0215.c que inclui rotinas para remoção e inserção de elementos em uma lista encadeada simples.

A figura remocao de lista encadeada com nó cabeça ilustra o algoritmo de remoção, que tem o código mostrado abaixo.


remocao de lista encadeada com nó cabeça

void remover ( tElemento *ptlista) {
     int x;
     char linha[80];
      tElemento **ant, **pont;

     printf("Valor a remover? ");
     fgets(linha, 80, stdin); sscanf(linha, "%d", &x);

     ant = ( tElemento **) malloc(sizeof ( tElemento *));
     pont = ( tElemento **) malloc(sizeof ( tElemento *));
     busca (ptlista, x, ant, pont);
     if (*pont) {
        (*ant)->prox = (*pont)->prox;
        printf("Retirei %d\n", (*pont)->info);
        free(*pont);
     }
     else puts("Nao achei na lista.");
}
O algoritmo de inserção tem o seguinte código:
void insere ( tElemento *ptlista) {

     tElemento *pt, 	/* ponteiro para o novo no a inserir */
			**ant,      /* ponteiro para ponteiro na lista */
            **pont;     /* ponteiro para ponteiro do no anterior */
     int x;
     char linha[80];

     printf("Valor a inserir? ");
     fgets(linha, 80, stdin); sscanf(linha, "%d", &x);

     ant = ( tElemento **) malloc(sizeof ( tElemento *));
     pont = ( tElemento **) malloc(sizeof ( tElemento *));

     busca (ptlista, x, ant, pont);
     if (!*pont) {
        pt = ( tElemento *) malloc(sizeof( tElemento));
        pt->info = x;
        pt->prox = (*ant)->prox;
        (*ant)->prox = pt;
     } else puts("Elemento ja existe na tabela.");    
}



---------------------------------------

Listas Circulares


O algoritmo de busca em uma lista encadeada pode ser melhorado se modificarmos a lista de modo que ela passe a ser circular como está mostrado na figura listcirc abaixo.
 
 


lista circular encadeada




Neste caso o algoritmo não tem como testar o final da lista. A solução é armazenar o dado que se está procurando no nó cabeça. Ao término do algoritmo a chave é sempre encontrada, e pode-se descobrir se ela pertencia ou não a lista pelo ponteiro que foi dado como resposta. Caso o ponteiro termine apontando para o nó cabeça, podemos afirmar que o elemento não se encontra na lista.

Os algoritmos de procura, inserção e remoção em uma lista circular encadeada estão mostrados no programa list0223.c. O algoritmo de busca aparece como parte das rotinas de inserção e remoção. Neste algoritmos primeiro se procura o elemento depois se decide o que fazer. No algoritmo de busca, caso o elemento já exista na lista, não há nada a fazer, caso contrário o ponteiro ant aponta para o elemento após o qual o novo elemento será inserido. No algoritmo de remoção, a busca termina apontando para o elemento a ser removido (ponteiro pont) ou com a indicação que o elemento não se encontra na lista (pont apontando para o nó cabeça).
 

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

struct tElemento {
        int info;
        struct tElemento *prox;
};

char tela();
struct tElemento *cria_no();
void insere (struct tElemento *, int );
void meu_remove (struct tElemento *, int);
void listar(struct tElemento *);

void main()
{
    struct tElemento *ptlista;
    char linha[80];
    char opcao;
    int sair = 0, valor;

    ptlista = cria_no();
    ptlista->prox=ptlista;
 

    do {
           opcao = tela();
           switch (opcao) {
                  case 'i':
                       puts("Qual dado a inserir?"); gets(linha);
                       sscanf(linha, "%d", &valor);
                       insere(ptlista, valor);
                       break;
                  case 'r':
                       puts("Qual dado a remover?"); gets(linha);
                       sscanf(linha, "%d", &valor);
                       meu_remove(ptlista, valor);
                       break;
                  case 'l':
                       listar(ptlista);
                       break;
                  case 's':
                       sair = 1;
                       break;
                  default:
                          puts("Opcao invalida.");
                          break;
           }
    } while (!sair);
}
 

char tela () {

     char opcao, linha[80];

     puts("Qual a sua opcao?");
     puts("[L]istar, [I]nserir, [R]emover, [S]air");
     gets(linha);
     sscanf(linha, "%c", &opcao);
     return tolower(opcao);
}
 
 
 

void listar (struct tElemento *ptlista) {

     int i=0;
     struct tElemento *pont;

     pont = ptlista->prox;
     while (pont != ptlista) {
           printf("Elemento %d = %d\n", i++, pont->info);
           pont = pont->prox;
     }
}
 

void insere (struct tElemento *ptlista, int valor) {

     struct tElemento *pont, *ant, *pt;

/* Aqui esta o algoritmo de busca em uma lista circular */

   ant = ptlista; pont = ptlista->prox;
    ptlista->info = valor;

    while (pont->info < valor) {
             ant = pont;
             pont = pont->prox;
    }

    if (pont->info == valor && pont != ptlista)
       puts("Elemento ja existe na tabela.");
    else {
         pt = cria_no();
         pt->info = valor;
         pt->prox = pont;
         ant->prox = pt;
     }
}

void meu_remove (struct tElemento *ptlista, int valor) {
     struct tElemento *pont, *ant;

    ant = ptlista; pont = ptlista->prox;
    ptlista->info = valor;

    while (pont->info < valor) {
          if (pont->info < valor) {
             ant = pont;
             pont = pont->prox;
          }
    }

    if (pont->info == valor && pont != ptlista) {
       ant->prox = pont->prox;
       free(pont);
    }
    else puts("Elemento nao existe na tabela.");
}

struct tElemento *cria_no() {

       struct tElemento *pt;

       if (( pt = (struct tElemento *) malloc(sizeof(struct tElemento)) ) == NULL )
       {
            puts("Nao há espaço.");
            exit(1);
       }
       pt->info = -1;
       pt->prox = NULL;
       return pt;
}

------------------------------------------------------------------------

Exercícios

  1. Escreva um programa similar ao list0206.c. Neste programa a lista conterá elementos do seguinte tipo.
  2. typedef struct {
            char nome[40];
        unsigned long int dre;
    } Taluno;
    
    typdef struct {
            int n; /* numero de elementos na lista em determinado instante */
            Taluno alunos[50]; /* lista propriamente dita */
    } Tlista;
    Solução: list0205.c
     
  3. Escreva um programa que converta uma expressão em notação com parênteses e converta para notação polonesa reversa. Assuma que todas as operações da expressão são escritas com parênteses. Por exemplo: (A * (B + C)). Solução: list0211.c
     
  1. Um palíndromo é um conjunto de caracteres que lido nos dois sentidos fornece o mesmo resultado. Por exemplo: osso, 63736, orava o avaro. Escreva um programa que leia um conjunto de caracteres e utilizando uma pilha verifique se um conjunto de caracteres é um palíndromo. A pilha servirá para armazenar o conjunto de caracteres e permitir que ele seja lido da direita para à esquerda. Solução: palind.c

  2.  
  3. Escreva um programa que mantenha duas pilhas em um único vetor (int vetor[MAXSIZE];), de tal maneira que nenhuma das duas pilhas forneça mensagem de pilha cheia até que todo o vetor esteja cheio e uma pilha não pode ser movida para uma posição diferente dentro do vetor. Escreva as rotinas insere1, retira1, insere2 e retira2 para manter as duas pilhas. (Sugestão: as duas pilhas devem crescer, uma em direção à outra.) Solução: pilhdup.c

  4.  
  5. Escreva um programa que leia um texto de tamanho MAXLINES em que cada linha tem tamanho MAXCARACS. Imprima em ordem crescente cada palavra contida no texto e quantas vezes ela aparece. Assuma que as palavras são separadas por um ou mais caracteres brancos. Use uma lista ordenada para ir armazenando cada uma das diferentes palavras que foram sendo encontradas. O texto pode conter caracteres maiúsculos e minúsculos mas palavras escritas em diferentes caixas (maiúsculas e minúsculas) serão contadas e impressas uma vez apenas. Solução: contapal.c

  6.  
  7. Sejam duas listas ordenadas e alocadas sequencialmente sem no cabeça. Apresentar um algoritmos que intercale as duas listas de forma que a lista resultante esteja tambem ordenada. Assuma que os tamanhos das listas são conhecidos e existe um vetor com tamanho suficiente para guardar a lista resposta.

  8.  
  9. Seja uma lista encadeada contendo números inteiros armazenados segundo a ordem de armazenamento, com a seguinte configuração: num1 num2 num3num4 ... numk. Escreva um programa que, percorrendo a lista uma única vez construa uma outra lista com a  configuração: num2 num3 num4 ... numk num1. Solução::

  10.  
  11. Seja um polinômio da forma F(x) = a0xn+a1xn-1+a2xn-2+...+anx0. Escreva um programa que armazene este polinômio em uma lista encadeada e escreva um programa que calcule F(x0), onde x0 é um valor lido do teclado.
    Solução:


.
------------------------------------------------------------------------

Índice