Listas

Disponível somente no TrabalhosFeitos
  • Páginas : 17 (4239 palavras )
  • Download(s) : 0
  • Publicado : 26 de março de 2013
Ler documento completo
Amostra do texto
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 abordarextensivamente 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 eremoçã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 emposiçõ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, dependedo 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 estarordenada 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 Talunot[]);

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++) {...
tracking img