Estrutura de dados

Disponível somente no TrabalhosFeitos
  • Páginas : 11 (2534 palavras )
  • Download(s) : 0
  • Publicado : 27 de março de 2012
Ler documento completo
Amostra do texto
Estrutura de dados

Uma árvore binária é uma estrutura de dados.
Uma estrutura de dados é um modo particular de armazenamento e organização de dados em um computador de modo que possam ser usados eficientemente.
Estruturas de dados e algoritmos são temas fundamentais em desenvoldimento de sistemas, sendo utilizados nas mais diversas áreas do conhecimento e com os mais diferentes propósitosde aplicação. Sabe-se que algoritmos manipulam dados. Quando estes dados estão organizados (dispostos) de forma coerente, caracterizam uma forma, uma estrutura de dados. A organização e os métodos para manipular essa estrutura é que lhe conferem singularidade.
As estruturas de dados são chamadas tipos de dados compostos que dividem-se em homogêneos (vetores e matrizes) e heterogêneos (registros).As estruturas homogêneas são conjuntos de dados formados pelo mesmo tipo de dado primitivo. As estruturas heterogêneas são conjuntos de dados formados por tipos de dados primitivos diferentes (campos do registro) em uma mesma estrutura. A escolha de uma estrutura de dados apropriada pode tornar um problema complicado em um de solução relativamente simples. O estudo das estruturas de dados está emconstante desenvolvimento (assim como o de algoritmos), mas, apesar disso, existem certas estruturas clássicas que se comportam como padrões e nesse trabalho iremos mostrar a estrutura de Lista, Fila e Pilha.

Lista

Uma Lista é uma estrutura de dados linear. Uma lista ligada, também chamada de encadeada, é linear e dinâmica, é composta por nós que apontam para o próximo elemento da lista, comexceção do último, que não aponta para ninguém. Para compor uma lista encadeada, basta guardar seu primeiro elemento.

Para exemplificar a implementação de listas encadeadas em C, vamos considerar um
exemplo simples em que queremos armazenar valores inteiros numa lista encadeada. O
nó da lista pode ser representado pela estrutura abaixo:

struct lista {
int info;
struct lista* prox;};
typedef struct lista Lista;

Vejamos algumas funções de Listas:
Função de inicialização

A função que inicializa uma lista deve criar uma lista vazia, sem nenhum elemento.
Como a lista é representada pelo ponteiro para o primeiro elemento, uma lista vazia é
representada pelo ponteiro NULL, pois não existem elementos na lista. A função tem
como valor de retorno a lista vaziainicializada, isto é, o valor de retorno é NULL. Uma
possível implementação da função de inicialização é mostrada a seguir:

/* função de inicialização: retorna uma lista vazia */
Lista* inicializa (void)
{
return NULL;
}

Função de inserção

Uma vez criada a lista vazia, podemos inserir novos elementos nela. Para cada elemento
inserido na lista, devemos alocar dinamicamente a memórianecessária para armazenar
o elemento e encadeá-lo na lista existente. A função de inserção mais simples insere o
novo elemento no início da lista.

Uma possível implementação dessa função é mostrada a seguir. Devemos notar que o
ponteiro que representa a lista deve ter seu valor atualizado, pois a lista deve passar a
ser representada pelo ponteiro para o novo primeiro elemento. Por esta razão, afunção
de inserção recebe como parâmetros de entrada a lista onde será inserido o novo
elemento e a informação do novo elemento, e tem como valor de retorno a nova lista,
representada pelo ponteiro para o novo elemento.

/* inserção no início: retorna a lista atualizada */
Lista* insere (Lista* l, int i)
{
Lista* novo = (Lista*) malloc(sizeof(Lista));
novo->info = i;novo->prox = l;
return novo;
}

Esta função aloca dinamicamente o espaço para armazenar o novo nó da lista, guarda a
informação no novo nó e faz este nó apontar para (isto é, ter como próximo elemento) o
elemento que era o primeiro da lista. A função então retorna o novo valor que
representa a lista, que é o ponteiro para o novo primeiro elemento.
A seguir,...
tracking img