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: