Manipulação de listas em C

Manipulação de listas em C

Tradicionalmente, listas em C são implementadas através de estruturas (associadas aos nós) armazenadas na memória dinâmica.
A estrutura que implementa um nó de uma lista ligada deve incluir, além do contéudo da informação do nó, um ponteiro para o próximo nó. Tipicamente, a definição da estrutura é da forma:

typedef struct node {
     /* conteudo */
     ...
     /* proximo no */
     struct node* next;
  } Node;

É possível criar um conjunto de rotinas para a manipulação de listas genéricas se o conteúdo for um ponteiro para qualquer tipo de dado, void*, que pode referenciar até mesmo outras estruturas complexas. Uma variável ponteiro para void denota um endereço genérico, que pode ser atribuído a um ponteiro para qualquer outro tipo sem problemas de conversão.
A linguagem C permite que o programador utilize a área de memória dinâmica através de suas rotinas de alocação dinâmica de memória, que estão presentes na biblioteca padrão da linguagem. Há duas atividades básicas relacionadas à manipulação desta área:

1. o programa pode requisitar uma área de memória dentro do espaço livre disponível; ou
2. o programa pode liberar uma área de memória que tenha sido previamente requisitada do espaço livre e que não seja mais necessária.

Em C, a alocação de memória é suportada pela rotina malloc. Esta rotina recebe um argumento, que é a dimensão em bytes da área necessária. O valor de retorno é o endereço do início da área que o sistema operacional alocou para este pedido, um ponteiro para o tipo void. Por exemplo, para reservar o espaço necessário para o nó de uma lista, seria necessário ter inicialmente declarado a variável que receberá o ponteiro para um nó:

Node *n;

A definição do valor do ponteiro dá-se através da invocação de malloc:

n = malloc(sizeof(struct node));

O conteúdo inicial da área alocada é indefinido. Uma variante da rotina de alocação, chamada calloc, inicializa o conteúdo da área alocada para 0's. Esta rotina recebe dois argumentos ao invés de um: o primeiro argumento é o número de itens que será alocado, e o segundo é o tamanho em bytes de cada item. Por exemplo, o trecho de código para criar um nó do tipo Node em uma rotina CREATENODE poderia ser escrito usando calloc:

 
Para liberar uma área alocada por malloc ou calloc, a rotina free deve ser utilizada. Assim, o exemplo acima poderia ser complementado da seguinte forma:

 
O que a rotina free faz é retornar o espaço que havia sido pré-alocado dinamicamente para o serviço do sistema operacional que gerencia o espaço livre, que pode assim reutilizar esta área para atender a outras requisições.
Há ainda uma quarta rotina associada à gerência de espaço livre em C, realloc, que permite alterar a dimensão de uma área pré-alocada. Esta rotina recebe dois argumentos, o primeiro sendo o ponteiro para a área que já havia sido alocada e o segundo sendo a nova dimensão para esta área em bytes. O valor de retorno é o endereço (que pode eventualmente ser o mesmo que o original) para a área com a nova dimensão requisitada. Caso o endereço seja diferente, realloc se encarrega de copiar o conteúdo original para a nova área alocada.
Nesses exemplos, não se comentou o que aconteceria caso não houvesse espaço disponível em memória para atender à requisição de alocação dinâmica. Quandomalloc (calloc, realloc) não consegue obter o espaço requisitado, o valor retornado pela função é o ponteiro nulo. Este é um comportamento típico em C para indicar erros em rotinas que retornam ponteiros.

Edinilson e Verdin - 2011

Listas ligadas

Uma lista ligada é uma estrutura que corresponde a uma seqüência lógica de entradas ou nós. Tipicamente, em uma lista ligada há um ou dois pontos conhecidos de acesso -- normalmente o topo da lista (seu primeiro elemento) e eventualmente o fim da lista (seu último elemento). Cada nó armazena também a localização do próximo elemento na seqüência, ou seja, de seu nó sucessor. Desse modo, o armazenamento de uma lista não requer uma área contígua de memória. A Figura 2.3representa graficamente uma estrutura de lista ligada.

Figura: Representação de uma lista ligada.

Ponteiros

Ponteiros

Em C, é possível ter acesso não apenas ao valor de uma variável mas também ao seu endereço. O operador unário &, aplicado a uma variável, retorna o endereço de memória associado à variável. A manipulação de endereços dá-se através da utilização de ponteiros. Ponteiros constituem um dos recursos mais utilizados na programação C. Eles fornecem um mecanismo poderoso, flexível e eficiente de acesso a variáveis. Há computações que só podem ser expressas através do uso de ponteiros.

Para definir que uma variável vai guardar um endereço, o operador unário * é utilizado na declaração, como em

/* define um ponteiro para um inteiro */
      int *ap;
      /* algumas variaveis inteiras */
      int x, y;

Neste exemplo, ap é uma variável do tipo ponteiro para inteiro, ou seja, ela irá receber um endereço de uma variável inteira. Para se obter o endereço de uma variável, o operador unário & pode ser utilizado. No exemplo acima,

/* ap recebe o endereco de x */
      ap = &x;

Após esta instrução, diz-se que ap aponta para x. É possível acessar o valor da variável x através do ponteiro usando o operador unário *, como em

/* y recebe o conteudo da variavel apontada por ap */
      y = *ap;

Observe que a combinação *ap é um inteiro, que pode assim ser atribuído a outro inteiro. Esta associação pode facilitar a compreensão da declaração de ponteiros. No exemplo, int *ap pode ser lido como ``*ap é um inteiro.''

Também seria possível definir o valor de x através do ponteiro, como em

/* o conteudo da variavel apontada por ap recebe y */
      *ap = y;

Ponteiros podem tomar parte em expressões aritméticas. Assim, a seguinte expressão é perfeitamente válida:

y = *ap + 1;

ou seja, y receberia o valor de x (variável apontada por ap) incrementado de um.

Observe que a expressão ap + 1 expressa um incremento do ponteiro (endereço) e não do conteúdo. Neste caso, estaria indicando o inteiro que estivesse armazenado na posição de memória seguinte ao inteiro armazenado em ap. As únicas operações aritméticas envolvendo ponteiros que são permitidas são a soma ou subtração de um valor inteiro a um ponteiro e a diferença entre dois ponteiros. Para essas operações, a unidade corresponde ao tamanho em bytes do tipo manipulado pelo ponteiro. Assim, se o valor de ap é 1000 e em uma máquina X o inteiro é representado em dois bytes, ap+1 resulta em 1002. Porém, a mesma expressão em uma máquina Y com inteiros em quatro bytes retornaria 1004. Desse modo, o programador não precisa se preocupar com os detalhes do armazenamento, trabalhando simplesmente com ``o próximo inteiro.''

O ponteiro nulo é um valor que representa ``nenhuma posição de memória'', sendo útil para indicar condições de erro e evitar o acesso a áreas inválidas de memória. Em C, o ponteiro nulo é representado pelo valor 0.

Estrutura de Dados

Estruturas de dados

Em diversos contextos, disciplinas associadas à programação recebem a denominação de ``processamento de dados''. Esta denominação não é gratuita -- de fato, embora seja possível criar procedimentos que não manipulem nenhum dado, tais procedimentos seriam de pouco valor prático.
Uma vez que procedimentos são, efetivamente, processadores de dados, a eficiência de um procedimento está muito associada à forma como seus dados são organizados. Estrutura de dados é o ramo da computação que estuda os diversos mecanismos de organização de dados para atender aos diferentes requisitos de processamento.
As estruturas de dados definem a organização, métodos de acesso e opções de processamento para a informação manipulada pelo programa. A definição da organização interna de uma estrutura de dados é tarefa do projetista da estrutura, que define também qual a API para a estrutura, ou seja, qual o conjunto de procedimentos que podem ser usados para manipular os dados na estrutura. É esta API que determina a visão funcional da estrutura de dados, que é a única informação relevante para um programador que vá utilizar uma estrutura de dados pré-definida.
Edinilson e Verdin

FESTA DA CIDADES DE NOVA VENÉCIA

Bem vindos a festa da CIDADE DE NOVA VENÉCIA - 2011 será uma honrar em recebe-los.
Boas festas a todos.
Grato

Felicidades a todos

Passei para desejar uma boa noite a todos,está se aproximando um grande feriadão,sucesso e bom descansso a todos.
Grato
Edinilson e Verdin

Mestrado -2011

Passei para desejar a todos uma ótima semana e tudo de bom nesse restante que ainda resta e sucesso a todos nessa nova FASE de vida.