Alguns videos bem interessantes do grupo Algorisos

Estrutura de dados / Ponteiros

O ponteiro nada mais é do que uma variável que guarda o endereço de memória, ou seja, ela aponta para um determinado espaço que foi alocado na memória. A declaração de ponteiros é feita das três seguintes formas:

1. permitem a modificação de argumentos de funções: Permite que as funções altere valores de variáveis não globais e não locais e ela através da referência ao endereço de memória da variável passada como parâmetro para a função;
   
#include <stdio.h>

void _f_modifica(int *); ///assinatura da função

void _f_modifica(int *p) {
    *p = 5;
}

int main() {

    int i;

    i = 10;

    printf("\nValor de i = %d", i);

    _f_modifica(&i); //passando o endereço de meḿória da variável i

    printf("\nValor de i = %d", i);

    return 0;
}
2. Permitem o uso de rotinas de alocação dinâmica de memória: alocação e desalocação de memória em tempo de execução conforme a necessidade do programa;
   
char *ptr;
ptr = malloc (1);
3. Aumento de eficiência em determinadas rotinas. A forma de declaração de uma variável ponteiro é:
   
   tipo *nome_variável
   Onde tipo é o tipo de variável apontada pela variável ponteiro.

Lista Dinâmica Encadeada

Nessa Vídeo aula  fica bem claro como funciona a inserção de elementos em uma lista encadeada:

- Exercício  Lista encadeada -

Este exercitório foi proposto no dia 08/10 , espero que as respostas estejam corretas, caso alguém identifique algum erro peço que nós informe.

Dada uma lista encadeada simples, apresente graficamente por meio de um esboço e também descreva cada etapa das seguintes condições

1 ► Retire o elemento do meio .

O   ponteiro do  segundo elemento  passa a pontar para o quarto  elemento , deixando assim o  terceiro fora da lista.

2 ► Inclua 2 novos componentes ao final da lista.

Os ponteiros quatro e cinco passam a apontar para dois novos elementos e o ultimo aponta aponta para o NULL.

3 ► exclua o primeiro elemento. 

O primeiro elemento passa a apontar para o NULL, ao invés de apontar para o segundo elemento. 

4 ► Inclua 2 novos componentes no começo da lista.

A primeira estrutura passa a apontar para um novo elemento e o primeiro aponta para o NULL.

5 ►  Inclua 2 novos elementos a partir do terceiro componente da lista.

O segundo elemento passa a apontar para um novo elemento e o novo aponta para outro novo.

OBS : OS NÚMEROS DENTRO DOS QUADRINHOS SÃO APENAS PARA INDICAR QUAIS ELEMENTOS ELES  ERAM ANTERIORMENTE.

Considerações Finais Sobre Encadeamentos e Nós

Listas encadeadas

Uma lista encadeada é uma representação de uma sequência de objetos na memória do computador. Cada elemento da sequência é armazenado em uma célula da lista: o primeiro elemento na primeira célula, o segundo na segunda e assim por diante.

Estrutura de uma lista encadeada

Uma lista encadeada  (= linked list = lista ligada)  é uma sequência de células; cada célula contém um objeto de algum tipo e o endereço da célula seguinte.   Suporemos nesta página que os objetos armazenados nas células são do tipo int.  A estrutura de cada célula de uma tal lista pode ser definida assim:

struct cel {                                          
       int         conteudo;                                
       struct cel *prox;                                             
    };   
         

conteudo	prox

É conveniente tratar as células como um novo tipo-de-dados e atribuir um nome a esse novo tipo:

   typedef struct cel celula;

Uma célula  c  e um ponteiro  p  para uma célula podem ser declarados assim:

   celula  c;

   celula *p;

Se c é uma célula então  c.conteudo  é o conteúdo da célula e  c.prox  é o endereço da próxima célula. Se  p  é o endereço de uma célula, então  p->conteudo  é o conteúdo da célula e  p->prox  é o endereço da próxima célula.  Se  p  é o endereço da última célula da lista então   p->prox  vale NULL 

Endereço de uma lista encadeada

O endereço de uma lista encadeada é o endereço de sua primeira célula.  Se p é o endereço de uma lista, convém, às vezes, dizer simplesmente

"p é uma lista".

Listas são animais eminentemente recursivos. Para tornar isso evidente, basta fazer a seguinte observação:  se p é uma lista então vale uma das seguintes alternativas:

p == NULL  ou

p->prox  é uma lista.

Listas com cabeça e sem cabeça

Uma lista encadeada pode ser organizada de duas maneiras diferentes, um óbvia e outra menos óbvia.

Lista com cabeça.  O conteúdo da primeira célula é irrelevante: ela serve apenas para marcar o início da lista.  A primeira célula é a cabeça (= head cell = dummy cell) da lista.  A primeira célula está sempre no mesmo lugar na memória, mesmo que a lista fique vazia.  Digamos que ini é o endereço da primeira célula. Então  ini->prox == NULL  se e somente se a lista está vazia. Para criar uma lista vazia, basta dizer:

   celula c, *ini;

   c.prox = NULL;

   ini = &c;

ou

   celula *ini;

   ini = malloc( sizeof (celula));

   ini->prox = NULL;

Lista sem cabeça.  O conteúdo da primeira célula é tão relevante quanto o das demais. Nesse caso, a lista está vazia se o endereço de sua primeira célula é NULL.  Para criar uma lista vazia basta fazer:

   celula *ini;  

   ini = NULL;

[Veja "Alocação dinâmica de memória".]

Suporemos no que segue que nossas listas têm cabeça. O caso de listas sem cabeça será tratado nos exercícios. Eu prefiro listas sem cabeça (porque são mais "puras"), mas a vida do programador fica mais fácil quando a lista tem cabeça.

Exemplos

Eis como se imprime o conteúdo de uma lista encadeada com cabeça:

// Imprime o conteúdo de uma lista encadeada

// com cabeça. O endereço da primeira célula é ini.

void imprima( celula *ini)

{

   celula *p;

   for (p = ini->prox; p != NULL; p = p->prox) 

      printf( "%d\n", p->conteudo);

}

Eis a correspondente função para lista sem cabeça:

// Imprime o conteúdo de uma lista encadeada ini.

// A lista não tem cabeça.

void imprima( celula *ini)

{

   celula *p;

   for (p = ini; p != NULL; p = p->prox) 

      printf( "%d\n", p->conteudo);

}

Busca em uma lista encadeada

Veja como é fácil verificar se um inteiro x pertence a uma lista encadeada, ou seja, se é igual ao conteúdo de alguma célula da lista:

// Esta função recebe um inteiro x e uma lista

// encadeada de inteiros. O endereço da lista é

// ini e ela tem uma celula-cabeça. A função

// devolve o endereço de uma celula que contém x.

// Se tal celula não existe, a função devolve NULL.

celula *busca( int x, celula *ini)

{

   celula *p;

   p = ini->prox;

   while (p != NULL && p->conteudo != x) 

      p = p->prox; 

   return p; 

}

Que beleza! Nada de variáveis booleanas! A função se comporta bem até mesmo quando a lista está vazia.

Eis uma versão recursiva da mesma função:

celula *busca2( int x, celula *ini)

{

   if (ini->prox == NULL) 

      return NULL;

   if (ini->prox->conteudo == x) 

      return ini->prox;

   return busca2( x, ini->prox);

}

Conteúdo extraído de http://www.ime.usp.br/

VAMOS SEGUIR UM TUTORIAL 

Aproveitando e seguindo um tutorial simplificado falando de listas encadeadas para melhor aplicação prática.

Fechando com chave de ouro e bom humor, aqui vai uma importante mensagem:

Recomendo >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

.

  Mais detalhes...

Em homenagem às primeiras aulas do Profº Valente, seguem os ideogramas comentados:

	X 3 =
árvore		floresta

Aqui temos um outro exemplo simples, com o kanji 日、que significa sol ou dia. Se um sol já é brilhante, imagina então três:

	X 3 =
dia, sol		cristalino, claro, brilhante

Por último temos aqui o kanji de mulher. Com várias mulheres temos o que?

	X 3 =
mulher		barulhenta, imoral

Kanji

 /*  VIDA DE PROGRAMADOR  */

/*---------------------------------------------------------------------------------------------------------------------------------------- */

HISTORIA REAL

   

Encadeamento de nós

Entendendo o encadeamento de nós nas estruturas:

As estruturas de dados giram em torno do encadeamento dos nós que contém as informações armazenadas e processadas nestas estruturas. Em todas as estruturas nós temos a ocorrências de nós. E cada nó aponta para um ou vários nós de seu tipo.

Em C, o perfeito entendimento do encadeamento de nós é essencial para assimilar as estruturas de dados. Sendo assim, considero que a leitura desta dica o ajudará muito na implementação e alteração dos códigos contidos na minha seção de estruturas de dados.

Nas estruturas de dados em C, um nó é implementado como uma estrutura. Assim, a seguinte estrutura:


struct Pessoa{
  int codigo;
  char nome[80];
  struct Pessoa *proximo;
};


representa uma pessoa, contendo um código, um nome e um ponteiro para uma estrutura do mesmo tipo, ou seja, outra pessoa. Analise o código a seguir cuidadosamente:



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

// estrutura Pessoa
struct Pessoa{
  int codigo;
  char nome[80];
  struct Pessoa *proximo;
};
// fim da estrutura Pessoa

int main(int argc, char *argv[])
{
  // vamos criar a primeira Pessoa
  struct Pessoa *pessoa1 = (struct Pessoa*)malloc(
    sizeof(struct Pessoa));
  pessoa1->codigo = 1;
  strcpy(pessoa1->nome, "Osmar J. Silva");
  pessoa1->proximo = NULL;

  // vamos criar a segunda Pessoa
  struct Pessoa *pessoa2 = (struct Pessoa*)malloc(
    sizeof(struct Pessoa));
  pessoa2->codigo = 2;
  strcpy(pessoa2->nome, "Marcos S. Teixeira");
  pessoa2->proximo = NULL;

  // vamos criar a terceira Pessoa
  struct Pessoa *pessoa3 = (struct Pessoa*)malloc(
    sizeof(struct Pessoa));
  pessoa3->codigo = 3;
  strcpy(pessoa3->nome, "Fernanda Souza Xavier");
  pessoa3->proximo = NULL;

  // vamos exibir os dados destas estruturas
  printf("%d - %s\n", pessoa1->codigo, pessoa1->nome);
  printf("%d - %s\n", pessoa2->codigo, pessoa2->nome);
  printf("%d - %s\n\n", pessoa3->codigo, pessoa3->nome);

  system("pause");
  return 0;
}




Neste código nós temos a criação de três estruturas do tipo Pessoa, cada uma contendo dados diferentes. Note que o campo proximo de cada uma recebe o valor NULL, ou seja, não aponta para lugar nenhum. Vamos concentrar nossa atenção neste campo proximo. Veja o trecho de código a seguir:



// o campo proximo da primeira pessoa aponta para a
// segunda pessoa
pessoa1->proximo = pessoa2;
// o campo proximo da segunda pessoa aponta para a
// terceira pessoa
pessoa2->proximo = pessoa3;
// só temos três pessoas, então o campo proximo da
// terceira pessoa continua apontando para lugar nenhum
pessoa3->proximo = NULL;



É aqui que a mágica do encadeamento acontece. Note que o campo proximo de cada estrutura aponta para a estrutura seguinte, com exceção da terceira estrutura, que continua apontando para NULL.

E, agora que o encadeamento está feito, "pular" de uma estrutura para outra é questão de seguir a ligação entre os nós. Veja, por exemplo, como exibimos os dados da terceira estrutura a partir de uma referência à primeira estrutura:


printf("%d - %s\n", pessoa1->proximo->proximo->codigo,
  pessoa1->proximo->proximo->nome);



É claro que se tivermos algumas centenas de nós, o uso desta forma de encadeamento não é nada viável. Mas isso é assunto para as outras dicas. Para finalizar, veja o código completo para esta discussão:



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

// estrutura Pessoa
struct Pessoa{
  int codigo;
  char nome[80];
  struct Pessoa *proximo;
};
// fim da estrutura Pessoa

int main(int argc, char *argv[])
{
  // vamos criar a primeira Pessoa
  struct Pessoa *pessoa1 = (struct Pessoa*)malloc(
    sizeof(struct Pessoa));
  pessoa1->codigo = 1;
  strcpy(pessoa1->nome, "Osmar J. Silva");
  pessoa1->proximo = NULL;

  // vamos criar a segunda Pessoa
  struct Pessoa *pessoa2 = (struct Pessoa*)malloc(
    sizeof(struct Pessoa));
  pessoa2->codigo = 2;
  strcpy(pessoa2->nome, "Marcos S. Teixeira");
  pessoa2->proximo = NULL;

  // vamos criar a terceira Pessoa
  struct Pessoa *pessoa3 = (struct Pessoa*)malloc(
    sizeof(struct Pessoa));
  pessoa3->codigo = 3;
  strcpy(pessoa3->nome, "Fernanda Souza Xavier");
  pessoa3->proximo = NULL;

  // o campo proximo da primeira pessoa aponta para a
  // segunda pessoa
  pessoa1->proximo = pessoa2;
  // o campo proximo da segunda pessoa aponta para a
  // terceira pessoa
  pessoa2->proximo = pessoa3;
  // só temos três pessoas, então o campo proximo da
  // terceira pessoa continua apontando para lugar nenhum
  pessoa3->proximo = NULL;

  // exibe os dados do primeiro nó
  printf("%d - %s\n", pessoa1->codigo,
    pessoa1->nome);

  // exibe os dados do segundo nó
  printf("%d - %s\n", pessoa1->proximo->codigo,
    pessoa1->proximo->nome);

  // exibe os dados do terceiro nó
  printf("%d - %s\n", pessoa1->proximo->proximo->codigo,
    pessoa1->proximo->proximo->nome);

  system("pause");
  return 0;
}

Este Vídeo é um trechinho da aula do Professor Valente, onde ele aborda alguns aspectos desse assunto:

Estrutura de Dados - Alocação Estática e Dinâmica de Memória

Alocação de Memória

Ao criar um programa em “C” usualmente temos que especificar as variáveis que vamos usar antes
de começar a executar o programa, reservando assim um espaço na memória.
As variáveis que são alocadas em posições fixas da memória são chamadas de variáveis estáticas, e as

variáveis que não possuem uma posição fixa e que são criadas e destruídas durante a execução 

do programa são chamadas de variáveis dinâmicas.

A alocação de memória no computador pode ser dividida em dois grupos principais:

• Alocação Estática: os dados tem um tamanho fixo e estão organizados sequencialmente na memória do computador. Um exemplo típico de alocação estática são as variáveis globais, e os vetores (estáticos).
• Alocação Dinâmica: os dados não precisam ter um tamanho fixo, pois podemos definir para cada dado quanto de memória que desejamos usar. Sendo assim vamos alocar espaços de memória (blocos) que não precisam estar necessariamente organizados de maneira sequencial, podendo estar distribuídos de forma esparsa na memória do computador. Na alocação dinâmica, vamos pedir para alocar/desalocar blocos de memória, de acordo com a nossa necessidade, reservando ou liberando blocos de memória durante a execução de um programa. Para poder “achar” os blocos esparsos na memória usamos as variáveis do tipo Ponteiro (indicadores de endereços de memória). As variáveis locais e os parâmetros passados por valor são alocados dinamicamente.

Alocação Estática de Memória:

As estruturas de dados para armazenar um conjunto de dados (exemplo: um cadastro com

vários registros), podem ser organizadas de formas diferentes, de acordo com a maneira que os

dados são inseridos e retirados da memória do computador. As formas mais usuais são: as listas

lineares sequenciais (vetores simples), as filas, as pilhas e os deques.

Listas lineares sequenciais:

Uma maneira interessante de manipular este tipo de estruturas de dados, é através da

construção de um conjunto de rotinas genéricas e modulares de manipulação de listas seqüenciais.

Vamos aqui descrever uma possível proposta de um conjunto de rotinas empregadas para este fim.

Rotinas básicas de manipulação de Vetores:

- Estruturas de dados com alocação estática

- Inserção no final do vetor

- Remoção lógica dos elementos

Aplicação típica:

- Pequenos cadastros

Estrutura de dados: 

         typedef int Tipo_Dado;
         typedef struct {
                                 Tipo_Dado Dado [MAX_VETOR];
                                 int Excluido [MAX_VETOR];
                                 int Inicio, Fim;
         } Tipo_Vetor;

Rotinas:

  void inicializa_vetor (Tipo_Vetor *V);

  int insere_vetor (Tipo_Vetor *V; Tipo_Dado Dado);

  int consulta_vetor (Tipo_Vetor V; int Indice; Tipo_Dado *Dado);

  int acha_vetor (Tipo_Vetor V; Tipo_Dado Dado; int *Indice);

  void lista_vetor (Tipo_Vetor V);

  int exclui_vetor (Tipo_Vetor *V; int Indice);

  int atualiza_vetor (Tipo_Vetor *V; int Indice; Tipo_Dado Novo_Dado);

  void compacta_vetor (Tipo_Vetor *V);

  int vazio_vetor (Tipo_Vetor V);

  int quantidade_vetor (Tipo_Vetor V);

Exemplo: inserção de dados no vetor

 int insere_vetor (V, Dado)

 Tipo_Vetor *V;

 Tipo_Dado Dado;

 {

   if (V->Fim < MAX_VETOR) /* Vetor nao esta cheio ? */

     {

       V->Dado[V->Fim]=Dado;

       V->Excluido[V->Fim]=FALSO;

      (V->Fim)++;

       return(OK);

      }

   else

     return(ERRO);

  }

                                    

Filas – FIFO = “First In, First Out”:

Construção de um conjunto de rotinas genéricas e modulares de manipulação de filas.

Vamos aqui descrever uma possível proposta de um conjunto de rotinas empregadas para este fim.

Rotinas básicas de manipulação de FILAS usando vetores:

- Estruturas de dados com alocação estática

- Inserção no final da fila

- Remoção do início da fila

- Fila circular

Aplicação típica:

- Lista de elementos a espera de um tratamento

Estrutura de dados:

 typedef int Tipo_Dado;

 typedef struct {

                          Tipo_Dado Dado [MAX_FILA];

                          int Inicio, Fim;

                         } Tipo_Fila;

Rotinas:

 void inicializa_fila (Tipo_Fila *F);

 int insere_fila (Tipo_Fila *F; Tipo_Dado Dado);

 int retira_fila (Tipo_Fila *F; Tipo_Dado *Dado);

 void lista_fila (Tipo_Fila F);

 int consulta_fila (Tipo_Fila F; int Indice; Tipo_Dado *Dado);

 int cheia_fila (Tipo_Fila F);

 int vazia_fila (Tipo_Fila F);

 int quantidade_fila (Tipo_Fila F);

 int acha_fila (Tipo_Fila F; Tipo_Dado Dado; int *Indice);

Exemplo: inserção de dados na fila

 int insere_fila (F, Dado)

 Tipo_Fila *F;

 Tipo_Dado Dado;

 {

   int prox;

   prox=F->Fim+1;

   if (prox == MAX_FILA)

        prox=0;

   if (prox == F->Inicio)

       return(ERRO);

   else

        {

          F->Dado[F->Fim]=Dado;

          F->Fim=prox;

          return(OK);

        } 

  }

Pilhas – LIFO = “Last In, First Out”:

Construção de um conjunto de rotinas genéricas e modulares de manipulação de pilhas.

Vamos aqui descrever uma possível proposta de um conjunto de rotinas empregadas para este fim.

Rotinas básicas de manipulação de PILHAS usando vetores:

- Estruturas de dados com alocação estática

- Inserção no topo da pilha

- Remoção do topo da pilha

Aplicação típica:

- Lista de “tarefas pendentes”, passagem de parâmetros nas linguagens de programação

Estrutura de dados:

 typedef int Tipo_Dado;

 typedef struct {

                         Tipo_Dado Dado [MAX_PILHA];

                         int Base, Topo;

                        } Tipo_Pilha;

Rotinas:

 void inicializa_pilha (Tipo_Pilha *P);

 int insere_pilha (Tipo_Pilha *P; Tipo_Dado Dado);

 int retira_pilha (Tipo_Pilha *P; Tipo_Dado *Dado);

 void exibe_pilha (Tipo_Pilha P);

 int quantidade_pilha (Tipo_Pilha P);

 int cheia_pilha (Tipo_Pilha P);

 int vazia_pilha (Tipo_Pilha P);

 void esvazia_pilha (Tipo_Pilha *P);

Exemplo: inserção de dados na pilha

 int insere_vetor (P, Dado)

 Tipo_Vetor *P;

 Tipo_Dado Dado;

 {

   if (V->Fim < MAX_VETOR) 

     {

       P->Dado[P->Fim]=Dado;

       P->Excluido[P->Fim]=FALSO;

      (P->Fim)++;

       return(OK);

      }

   else

     return(ERRO);

  }

Deque – “Double Ended Queue”:

Construção de um conjunto de rotinas genéricas e modulares de manipulação de deques.

Vamos aqui descrever uma possível proposta de um conjunto de rotinas empregadas para este fim.

Rotinas básicas de manipulação de DEQUES usando vetores:

- Estruturas de dados com alocação estática

- Inserção no início ou no final do deque

- Remoção do início ou do final do deque

- Estrutura de dados “circular”

Aplicação típica:

- Lista de elementos com múltiplas formas de considerar/manipular a ordem destes

Estrutura de dados:

 typedef int Tipo_Dado;

 typedef struct {

                         Tipo_Dado Dado [MAX_DEQUE];

                          int Inicio, Fim;

                        } Tipo_Deque;

Rotinas:

 void inicializa_deque (Tipo_Deque *D);

 int insere_inicio_deque (Tipo_Deque *D; Tipo_Dado Dado);

 int insere_final_deque (Tipo_Deque *D, Tipo_Dado Dado);

 int retira_inicio_deque (Tipo_Deque *D; Tipo_Dado *Dado);

 int retira_final_deque (Tipo_Deque *D; Tipo_Dado *Dado);

 void lista_deque (Tipo_Deque D);

 int acha_deque (Tipo_Deque D; Tipo_Dado Dado; int *Indice);

 int cheio_deque (Tipo_Deque D);

 int vazio_deque (Tipo_Deque D);

 int quantidade_deque (Tipo_Deque D);

 void apaga_deque (Tipo_Deque *D);

Alocação de Dinâmica de Memória:

As principais características da alocação dinâmica de memória são:

- Os dados se encontram espalhados na memória do computador em vários blocos;

- Geralmente as estruturas de dados são compostas por registros que incluem um campo

do tipo ponteiro (elo/link), o que nos permite encadear os dados e indicar onde está o

dado seguinte na memória (visto que os dados estão espalhados na memória do

computador);

- Podemos ir solicitando mais e mais memória a medida em que precisarmos de mais

espaço para armazenar as informações. Isso nos permite criar programas que usam

apenas a memória necessária... e por conseqüência, podemos rodar outros programas,

em uma mesma máquina, sem que um único programa monopolize toda a memória

disponível desta.

- Podemos liberar espaços de memória quando estes não forem mais necessários ao

programa.

Estas estruturas criadas com registros que são encadeados através do uso de ponteiros, que

estes blocos espalhados pela memória, vão resultar em estruturas denominadas de “listas

encadeadas” de alocação dinâmica. A figura abaixo mostra um exemplo de lista encadeada,

baseada na estrutura de dados descrita logo mais abaixo:

Listas encadeadas simples:

Construção de um conjunto de rotinas genéricas e modulares de manipulação de listas

encadeadas simples. Vamos aqui descrever uma possível proposta de um conjunto de rotinas

empregadas para este fim.

Rotinas básicas de manipulação de listas encadeadas simples:

- Estruturas de dados com alocação dinâmica

- Inserção no inicio da lista, no final da lista, ou de modo ordenado

- Remoção de qualquer elemento da lista (início, final, ou elemento especificado)

Aplicação típica:

- Lista de elementos de tamanho variável

Estrutura de dados:

 typedef int Tipo_Dado;

 typedef struct bloco {

                                   Tipo_Dado Dado;

                                   struct bloco *Proximo;

                                   } Nodo;

Rotinas:

 void inicializa_lista (Nodo **N);

 int insere_inicio_lista (Nodo **N, Tipo_Dado Dado);

 int insere_fim_lista (Nodo **N, Tipo_Dado Dado);

 int insere_ordenando_lista (Nodo **N, Tipo_Dado Dado);

 int remove_inicio_lista (Nodo **N, Tipo_Dado *Dado);

 int remove_fim_lista (Nodo **N, Tipo_Dado *Dado);

 int remove_elemento_lista (Nodo **N, Tipo_Dado Dado);

 int quantidade_lista (Nodo *N);

 void exibe_lista (Nodo *N);

 int pesquisa_lista (Nodo **N, Tipo_Dado Dado);

 int percorre_lista (Nodo **N, Tipo_Dado *Dado);

 void apaga_lista (Nodo **N);

Exemplo: inserção de dados no inicio da lista encadeada

 int insere_inicio_lista (N, Dado)

 Nodo **N;

 Tipo_Dado Dado;

 {

   Nodo *novo;

    novo = (Nodo *) calloc ( 1, sizeof (Nodo) );

    if ( novo == NULL )

         return (ERRO); /* Não conseguiu alocar espaço na memória */

         novo -> Dado = Dado;

         novo -> Proximo = *N;

        *N = novo;

         return (OK);

  }

Exemplo: inserção de dados no final da lista encadeada

 int insere_fim_lista (N, Dado)

 Nodo **N;

 Tipo_Dado Dado;

{

  Nodo *aux, *novo;

  novo = (Nodo *) calloc ( 1, sizeof (Nodo) );

  if ( novo == NULL )

       return(ERRO);

       novo -> Dado = Dado;

       novo -> Proximo = NULL;

  if ( *N == NULL )

       *N = novo;

  else {

           aux = *N;

           while ( aux -> Proximo != NULL )

                      aux = aux -> Proximo;

                      aux -> Proximo = novo;

         }

  return (OK)

 }

Listas duplamente encadeadas

Construção de um conjunto de rotinas genéricas e modulares de manipulação de listas

duplamente encadeadas. Vamos aqui descrever uma possível proposta de um conjunto de rotinas

empregadas para este fim.

Rotinas básicas de manipulação de listas duplamente encadeadas:

- Estruturas de dados com alocação dinâmica

- Inserção no inicio da lista, no final da lista, ou de modo ordenado

- Remoção de qualquer elemento da lista (início, final, ou elemento especificado)

Aplicação típica:

- Lista de elementos de tamanho variável, permite percorrer a lista nos dois sentidos

Estrutura de dados:

 typedef int Tipo_Dado;

 typedef struct bloco_ld {

                                        Tipo_Dado Dado;

                                        struct bloco_ld *Proximo, *Anterior;

                                       } Nodo_LD;

Rotinas:

 void inicializa_ld (Nodo_LD **LD);

 void posiciona_inicio_ld (Nodo_LD **LD);

 void posiciona_fim_ld (Nodo_LD **LD);

 int insere_antes_ld (Nodo_LD **LD, Tipo_Dado Dado);

 int insere_depois_ld (Nodo_LD **LD, Tipo_Dado Dado);

 int insere_inicio_ld (Nodo_LD **LD, Tipo_Dado Dado);

 int insere_fim_ld (Nodo_LD **LD, Tipo_Dado Dado);

 int insere_ordenando_ld (Nodo_LD **LD, Tipo_Dado Dado);

 int pesquisa_ld (Nodo_LD **LD, Tipo_Dado Dado);

 int remove_nodo_ld (Nodo_LD **LD, Tipo_Dado *Dado);

 int remove_dado_ld (Nodo_LD **LD, Tipo_Dado *Dado);

 int quantidade_ld (Nodo_LD *LD);

 void exibe_ld (Nodo_LD *LD);

 int percorre_lista (Nodo_LD **LD, Tipo_Dado *Dado);

 void apaga_ld (Nodo_LD **LD);

Exemplo: posiciona o ponteiro no início da lista duplamente encadeada

 void posiciona_inicio_ld (LD)

 Nodo_LD **LD;

{

  if ( *LD != NULL )

                                 {

                                   while ( (*LD) -> Anterior != NULL )

                                 *LD = (*LD) -> Anterior;

                                  }

}

Exemplo: inserção de dados antes da posição apontada na lista duplamente encadeada

int insere_antes_ld (LD, Dado)

Nodo_LD **LD;

Tipo_Dado Dado;

{

 Nodo_LD *novo, *aux;

 novo = (Nodo_LD *) calloc ( 1, sizeof (Nodo_LD) );

 if ( novo == NULL )

                                 return (ERRO);

                                 novo -> Dado = Dado;

if ( *LD == NULL )

                                {

                                  *LD = novo;

                                   novo -> Anterior = NULL;

                                   novo -> Proximo = NULL;

}

else

     {

      aux = (*LD) -> Anterior;

      (*LD) -> Anterior = novo;

      novo -> Proximo = (*LD)

      novo -> Anterior = aux;

      if ( aux != NULL )

      aux -> Proximo = novo;

     }

return (OK);

}

Exemplo: inserção de dados no início da lista duplamente encadeada

int insere_inicio_ld (LD, Dado)

Nodo_LD **LD;

Tipo_Dado Dado;

{

  posiciona_inicio_ld(LD);

  return ( insere_antes_ld (LD, Dado) );

}

Filas, Pilhas, Deques e Ordenação usando alocação dinâmica:

As filas, pilhas e deques podem ser facilmente implementadas usando rotinas genéricas de

manipulação de listas, sejam estas simples ou duplamente encadeadas. Uma vez que podemos

implementar facilmente rotinas de inserção no início e/ou no fim de uma lista encadeada, e também

podemos implementar facilmente rotinas de remoção do início e/ou do fim de uma lista encadeada

com alocação dinâmica, por conseqüência, podemos criar rotinas de manipulação destas outras

estruturas de dados baseadas nas rotinas descritas anteriormente. É importante salientar que em

alguns casos talvez seja interessante criar rotinas mais otimizadas, como por exemplo, na inserção

de nodos no final de uma lista. Neste caso, seria interessante que fosse evitada a necessidade de

percorrer toda a lista até encontrar o nodo final, cada vez que um novo nodo fosse adicionado no

final desta lista.

Filas:

- Insere no início

- Retira do fim

Pilhas:

- Insere no fim

- Retira do fim

Deques:

- Insere no início ou no fim

- Retira do início ou do fim

Ordenação: 

- A inserção pode ser feita em qualquer posição, o que facilita a ordenação

Caso queiram ter uma menor abstração e aprimorar os conceitos do conteúdo abordado neste post, recomendo os videos abaixo: 

Estrutura de dados - Lista estática

Estrutura de dados - Pilhas, Filas e Deque

Estrutura de dados - Alocação dinâmica de memória

S T R U C T

Struct em linguagem C


Uma struct é uma variável especial que contém diversas outras variáveis normalmente de tipos diferentes.

As variáveis internas contidas pela struct são denominadas membros da struct.

Podemos dizer que as structs da linguagem C são o equivalente ao que se denomina registros em outras linguagens de programação.

A palavra reservada struct indica ao compilador que está sendo criada uma estrutura.


Abaixo a sintaxe e modo de utilização de uma  S t r u c t :

  " struct nome_da_estrutura { tipo_de_dado nome_do_membro; }; "

struct data {

int dia;

int mes;

int ano;

};

int main (void){

data hoje;

hoje.dia = 24;

hoje.mes = 9;

hoje.ano = 2014;

}

Inicialização dos campos da estruturas

A inicialização dos campos de uma estruturas é semelhante à inicialização de um arranjo. Os valores para cada um dos membros são escritos entre chaves e separados por vírgula, na ordem em que foram declarados.

Exemplo 1 :

struct funcionario

{ char nome[50];

double salario;

} x, y, z;

struct funcionario x = {“Jõao da Silva”, 370.00};

struct funcionario y = {“Fernando de Souza Junior”, 450.00};

struct funcionario z = {“Geremias dos Santos”, 1530.00}; 

Exemplo 2 :

struct data {

int dia;

int mes;

int ano;

} hoje;

struct data hoje={24,09,2014};

Se ainda surgir dúvidas sobre o assunto  STRUCT  basta assistir o vídeo abaixo para ajudá-lo a desenvolver melhor o conceito de estruturas em C . 

Espero que tenham gostado do assunto.


Em breve mais informações sobre linguagem C e estruturas de dados .

Ponteiros

PONTEIROS

Os conceitos de endereço e ponteiro são fundamentais em qualquer linguagem de programação (embora sejam mais visíveis em C que em outras linguagens).  O conceito de ponteiro é muito útil mas difícil; seu domínio exige um certo esforço.

Da mesma maneira que existem em C variáveis do tipo char, int e float, existem variáveis do tipo ponteiro. As variáveis do tipo ponteiro armazenam endereços de memória e são utilizadas por 3 razões específicas na programação:

·                     permitem a modificação de argumentos de funções: permitem que uma função altere valores de variáveis não globais e não locais a ela através da referência ao endereço de memória da variável passada como parâmetro para a função;

·                     permitem o uso de rotinas de alocação dinâmica de memória: alocação e desalocação de memória em tempo de execução conforme a necessidade do programa;

·                     aumento de eficiência em determinadas rotinas.

O ponteiro nada mais é do que uma variável que guarda o endereço de uma outra variável. A forma de declaração de uma variável ponteiro é:

tipo  *nome_variável      //tipo = char, int ou float

onde tipo é o tipo de variável apontada pela variável ponteiro.

Por exemplo:

float  *p;      // p é um ponteiro de float

Ou seja, p apontará para uma região de memória que armazena um valor float. 

A declaração de ponteiro não tem o mesmo significado da declaração de uma variável. Ela indica apenas o tipo de objeto de dados apontado e, desde que contém endereço de memória, o tamanho em bytes que ocupa não tem relação com o tamanho do objeto apontado. O tamanho do ponteiro é fixo e depende apenas do modelo de memória do sistema (2 bytes ou 4 bytes, normalmente).

Para declarar mais de um ponteiro por linha, usa-se um operador indireto (*) para cada

char *ch1, *ch2; (são ponteiros para o tipo char).

Se um operador for omitido (exemplo: char *ch1, ch2;), a variável correspondente não será ponteiro e, certamente, provocará erro de execução se usada como tal.

O ponteiro pode ser declarado para qualquer tipo legal de variável em C (char, int, float, double, etc), além de void, que seria um genérico, podendo apontar para qualquer tipo de dado.

INICIALIZANDO UM PONTEIRO

A simples declaração de um ponteiro não o faz útil. É necessária a indicação da variável para a qual ele aponta.

int var;

int *ptr;

var = 10;

ptr = &var;

Na seqüência acima, são declarados uma variável tipo int (var) e um ponteiro para o mesmo tipo (ptr). A terceira linha atribui o valor 10 a var e a última linha inicializa o ponteiro ptr.

Observa-se o uso do operador de endereçamento (&) para inicialização do ponteiro. Isso significa, no código ptr = &var;, que ptr passa a conter o endereço de var, não o seu valor.

Supondo que o sistema é endereçado por 2 bytes, a Figura 01 acima dá uma idéia gráfica dessa associação: o conteúdo de ptr é 4052, que é o endereço do primeiro byte da variável var (ptr ocupa 2 bytes por causa do endereçamento do sistema e var também ocupa 2 bytes, mas por ser do tipo int).

O valor 4052 para a posição de memória de var é apenas ilustrativo. Na prática, dependerá do local de memória onde o programa foi carregado.

Com ptr apontando para var, é possível realizar operações com esta última de forma indireta, a partir de ptr. Exemplos a seguir.

Acrescentando a linha:

int newVar = *ptr;

ao código anterior, o valor de newVar é 10, que é o valor de var lido indiretamente através de ptr.

E a linha:

*ptr = 20;

modifica o valor de var para 20, ou seja, altera de forma indireta através de ptr.

É importante lembrar que um ponteiro declarado e não inicializado poderá ter conteúdo nulo ou aleatório, a depender da alocação sistema. Nessa condição, se o conteúdo apontado for modificado, algumas posições de memória terão seus valores indevidamente alterados e as consequências serão imprevisíveis.

CONCLUSÃO

Um ponteiro é uma variável que guarda um endereço de uma outra variável. Sabemos como declara-las e que antes de utiliza-las é necessário atribuir um endereço válido. Podemos utilizar ponteiros para ponteiros. O uso de ponteiro é importante em muitos casos e que se deve tomar muito cuidado ao usa-los.