Material didático para princípios de desenvolvimento de Algoritmos

LinhaCodigo
001// Prof. Leo^nidas - http://www.matematica.br http://line.ime.usp.br
002// MAC0122 - 2017/09
003
004// Introducao `as listas ligadas em C
005// Principio: usando alocacao dinamica de memoria, podemos usar registros e apontadores para definir a ordem dos dados.
006// Exemplo de lista com insercao ao final
007// Se 'prox' tiver com o valor nulo (NULL), entao a lista finalizou.
008
009// Para ajudar na depuracao, compilar com diretivas para verificar acesso `a posicoes invalidas (via apontadores ou vetores)
010// $ gcc -fsanitize=address -g -o introducao_lista_ligada introducao_lista_ligada.c
011
012#include <stdio.h>
013#include <string.h> // para 'strcpy(...)'
014#include <stdlib.h> // para o 'malloc(...)' e 'free(...)'
015
016#define TAM 10 // limite para numero de caracteres em campo do registro
017#define M 5    // limite para vetor de registros
018
019typedef struct reg {  // define estrutura 'dado'
020  int id;
021  char nome[TAM];   // precisa deste espaco
022  struct reg *prox; // aponta para uma estrutura 'dado'
023  } tipoRegistro;
024
025// Cria um registro devolvendo um apontador para ele
026tipoRegistro *criaRegistro (char *nome, int id) {
027  tipoRegistro *item = malloc(sizeof(tipoRegistro));
028  //tipoRegistro *item = malloc(TAM * sizeof(char) + sizeof(int) + sizeof(tipoRegistro *));
029  strcpy(item->nome, nome);
030  item->id = id;
031  item->prox = NULL;
032  return item;
033  }
034
035// Construir uma lista ligada de itens (registros), inserindo sempre na ultima posicao
036// Exercicios 1. Implementar uma funcao que insere na ultima posicao (ja' no codigo, mas dentro da "main")
037// Exercicios 2. Implementar uma funcao que remova o elemento cujo campo 'nome' tenha determinado valor
038// Exercicios 3. Implementar uma funcao que remova o elemento cujo campo 'id' tenha determinado valor
039// ATENCAO: nos exercicios 2 e 3, cuidado com situacoes extremas (lista vazia, item a ser removido ser o primeiro ou ser o ultimo)
040int main (void) {
041  int i;
042  char nomes[][TAM] = { "aluno 1", "aluno 2", "aluno 3", "aluno 4", "aluno 5" }; // vetor de nomes estatico (para NAO precisar digitar...)
043  tipoRegistro *primeiro, *apont, *novo;
044
045  primeiro = criaRegistro(nomes[0], 0); // crie o primeiro elemento
046  apont = primeiro;
047  for (i=1; i<5; i++) {
048    novo = criaRegistro(nomes[i], i); // crie novo elemento
049    apont->prox = novo;                 // faca com que o apontador para proximo do ultimo aponte para este novo registro
050    apont = novo;
051    }
052  apont = primeiro;
053  while (apont!=NULL) {
054    printf(" - %d : %s\n", apont->id, apont->nome);
055    // Depois de usar, se NAO mais precisar do registro pode devolve-lo ao "banco de memoria" usando
056    // free(apont);
057    apont = apont->prox; // pegue o proximo registro
058    }
059
060  return 0;
061  }