Ponteiros, Recursividade e Listas Encadeadas em C

Tipos de Dados e Endereços de Memória

Byte → célula de 8 bits.
Endereço → número pelo qual a 1ª célula da memória é identificada.

short int → ocupa 2 bytes; int → 2 a 4 bytes; long → 4 a 8 bytes; float → 4 bytes.

double → 8 bytes.

Ponteiros

Ponteiro → números que representam a posição inicial na memória e que têm como conteúdo o endereço de memória de outro dado. Indica o 1º dado de um conjunto; é utilizado para construção de estruturas de dados, retorno de dados de funções e operações sobre vetores.

& → operador unário que fornece o endereço de memória de uma variável.

* → operador unário que retorna o valor apontado por um ponteiro.

Operadores

int *p → ponteiro para int; double *q → ponteiro para double; type *s → ponteiro para um tipo definido, como uma struct.

O ponteiro é inicializado com o operador &:
int x = 5;
int *ptr_x = &x;

O uso do operador * no corpo do programa permite acessar o conteúdo do endereço de memória apontado pelo ponteiro:
int x = 10;
int *ptr_x = &x;
printf("%d", x); → 10
printf("%d", *ptr_x); → 10

Por que um ponteiro tem que possuir um tipo de dado?

Para saber quantos bytes ocupará na memória.

Como obter o número de bytes ocupado por uma variável?

Obtém-se o número de bytes ocupado por uma variável com o operador sizeof.

Para que os ponteiros são utilizados?

Para a manipulação de vetores.

A que corresponde o nome de uma variável vetor?

Ao endereço de memória do 1º elemento do vetor. Ex.: int v[4] = {1,2,3,4}; → v ---> v[0].

Quais são as possíveis operações aritméticas com ponteiros?

Incremento → adição do número de bytes ocupados pelo tipo de dado ao conteúdo do ponteiro: ptr++; ptr = ptr + 2;

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

int main(int argc, char** argv){
    int x = 5, *px = &x;
    float y = 5.0, *py = &y;
    printf("%d %ld \n", x, (long) px);
    printf("%d %ld \n", x + 1, (long) (px + 1));
    printf("%f %ld \n", y, (long) py);
    printf("%f %ld \n", y + 1, (long) (py + 1));
}

Decremento

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

int main(int argc, char** argv){
    int x = 5, *px = &x;
    float y = 5.0, *py = &y;
    printf("%d %ld \n", x, (long) px);
    printf("%d %ld \n", x + 1, (long) (px - 1));
    printf("%f %ld \n", y, (long) py);
    printf("%f %ld \n", y + 1, (long) (py - 1));
}

Diferença → identifica quantos elementos do mesmo tipo existem entre um ponteiro e outro (só pode ser aplicada a ponteiros do mesmo tipo).

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

int tamanhoString(char *s){
    char *ptr = s;
    while (*ptr != '\0'){
        ptr++;
    }
    return (int) (ptr - s);
}

int main(){
    char string[100];
    printf("informe a string: \n");
    gets(string);
    printf("tamanho da string informada: %d \n", tamanhoString(string));
}

Comparação → compara-se dois ponteiros do mesmo tipo usando operadores relacionais: >, >=, <, <=, ==, !=.

A variável ponteiro também possui endereço de memória.
Podemos ter ponteiros que apontam para ponteiros.

Ponteiros de ponteiros

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

int main(){
    float x = 3;
    float *ptr_x;
    float **ptr_ptr_x;
    ptr_x = &x;
    ptr_ptr_x = &ptr_x;
    printf("x = %f -> &x = %ld \n", x, &x);
    printf("x = %f -> &x = %ld \n", *ptr_x, ptr_x);
    printf("x = %f -> &x = %ld \n", **ptr_ptr_x, *ptr_ptr_x);
}

Recursividade

O que é recursividade? É uma técnica em que uma rotina chama a si mesma.

Em programação, a recursividade se dá através de sub-rotinas: a sub-rotina chama a própria sub-rotina.

A recursividade deve ser finita. Um algoritmo recursivo requer a definição de um critério de parada. As chamadas recursivas, em algum momento, devem se tornar falsas; a isso damos o nome de condição de escape, que deve ser a primeira linha de código.

Função recursiva em C para cálculo do fatorial

long int fatrec(int n){
    if ((n == 0) || (n == 1)){
        return (1);
    } else {
        return (n * fatrec(n - 1));
    }
}

int main(){
    int n = mil;
    long int x = fatrec(n);
    printf("fatorial (%d) = %ld", n, x);
}

Execução do algoritmo fatorial recursivo para n = 3

long int fatrec(int n){
    if ((n == 0) || (n == 1)){
        return (1);
    } else {
        return (n * fatrec(n - 1));
    }
}

int main(){
    int f = 3;
    long int x = fatrec(f);
    printf("fatorial (%d) = %ld", f, x);
}

Características da recursividade

• Há algoritmos que são mais eficientes quando implementados de forma recursiva;
• Requer área para armazenamento a cada chamada;
• Muitas chamadas recursivas podem levar à falta de memória.

Tipos de recursividade

• Própria ou direta → a sub-rotina A chama explicitamente a sub-rotina A;
• Mútua ou indireta → a sub-rotina A chama a sub-rotina B, que chama novamente a sub-rotina A.

Função em C para apresentar os n primeiros números inteiros (0 a n)

int exibe_n_numeros(int n, int z){
    printf("entrada !\n");
    if (z <= n){
        printf("%d", z);
        exibe_n_numeros(n, z + 1);
    }
    printf("saida !\n");
}

int main(){
    printf("inicio !\n");
    exibe_n_numeros(4, 0);
    printf("fim !");
}

Arrays e Listas Encadeadas

Array → conjunto de elementos de um mesmo tipo, posicionados de forma contígua na memória e acessados através de uma única variável.

Lista encadeada simples → coleção de elementos ou nós que podem ser alocados em regiões não contíguas da memória. Cada elemento possui um campo que indica a localização do nó seguinte da lista.

• Possibilita a criação de "arrays dinâmicos";
• O número de elementos da lista pode crescer e decrescer em tempo de execução.

Estrutura que define o novo tipo de dado

typedef struct aluno_list{
    char nome[80];
    int matricula;
    struct aluno_list * proximo;
} list;

Principais operações

• create_new_element → cria elemento/nó da lista;
• insert → insere elemento na lista;
• remove → remove elemento da lista;
• show_list → exibe elementos da lista.

Operação de criação de elementos: create_new_element

• Criar um elemento do tipo lista;
• Atribuir a informação do elemento;
• Ajustar a referência de próximo elemento da lista para NULL.

Operação inserir no final de uma lista: lista = insert(lista, novo)

• Recebe a referência de início da lista;
• Recebe o novo elemento a ser inserido;
• Percorre a lista até o último elemento;
• Liga o último elemento da lista ao novo elemento a ser inserido.

Operação exibir: show(lista)

• Partimos do elemento inicial da lista;
• Buscamos o próximo elemento através do ponteiro;
• Condição de parada: ponteiro apontando para NULL.

Operação remover no início de uma lista: lista = remove(lista)

• Ponteiro auxiliar aponta para o início da lista: aux = lista;
• Início da lista aponta para o próximo elemento: lista = lista->next;
• Desfaz o apontamento do elemento a ser removido: aux->next = NULL;
• Libera a memória ocupada pelo ponteiro auxiliar: free(aux);
• Retorna a referência ao início da lista: return lista;

Operação remover no final de uma lista: lista = remove(lista)

• Percorrer a lista até o último elemento: aux2 = aux; aux = aux->next;
• Desfazer o apontamento do elemento a ser removido: aux2->next = NULL;
• Liberar a memória ocupada pelo elemento a ser removido: free(aux);
• Retornar a referência de início da lista: return lista;

Lista encadeada dupla → variação da lista simplesmente encadeada. Cada elemento possui um campo que indica a localização do nó anterior e outro que indica a localização do nó seguinte.

• Também possibilita a criação de "arrays dinâmicos";
• Diferentemente da lista simples, podemos encontrar o início e o final da lista partindo de qualquer ponto da lista.

Estrutura que define este novo tipo de dado

typedef struct aluno_list{
    char nome[80];
    int matricula;
    int idade;
    struct aluno_list * anterior;
    struct aluno_list * proximo;
} list;

Principais operações

• create_new_element → criar elemento/nó da lista;
• insert → inserir elemento na lista;
• remove → remover elemento da lista;
• show_list → exibir elementos da lista.

Operação de criação de elementos: create_new_element

• Criar um elemento do tipo da lista;
• Atribuir a informação do elemento;
• Ajustar a referência de elemento anterior da lista para NULL;
• Ajustar a referência de próximo elemento da lista para NULL.

Operação inserir ao final da lista: lista = insert(lista, novo)

• Recebe a referência de início da lista;
• Recebe o novo elemento a ser inserido;
• Percorre a lista até o último elemento;
• Liga o último elemento da lista ao novo elemento a ser inserido.

Operação remover no fim de uma lista: lista = remove_last(lista)

• Recebe a referência de início da lista;
• Percorre a lista até o último elemento;
• Desfaz a ligação entre o penúltimo e o último elemento da lista;
• Remove o último elemento da lista.

Percorrendo um vetor com ponteiros

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

int main(){
    int v[4] = {1, 2, 3, 4};
    int *ptr_v = v;
    int i;
    for (i = 0; i < 4; i++){
        printf("%d \n", *ptr_v);
        ptr_v++;
    }
    printf("\n");
    system("pause");
}

Percorrendo um vetor com ponteiros (versão 2)

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

int main(){
    int v[4] = {1, 2, 3, 4};
    int *ptr_v = v;
    int i;
    for (i = 0; i < 4; i++){
        printf("%d \n", *(ptr_v + i));
    }
    printf("\n");
    system("pause");
}

Percorrendo um vetor com ponteiros (versão 3)

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

int main(){
    int v[4] = {1, 2, 3, 4};
    int *ptr_v = v;
    int *ptr_v2;
    for (ptr_v2 = ptr_v; ptr_v < (ptr_v2 + 4); ptr_v++){
        printf("%d \n", *ptr_v);
    }
    printf("\n");
    system("pause");
}

Lista simples completa em C

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

// define a estrutura da lista encadeada (define o que será cada elemento/nó da lista)
typedef struct list{
    int idade;          // dados da lista
    char nome[30];
    struct list *prox;  // ponteiro para o próximo elemento da lista
} list;

// função que cria 1 elemento; retorna um ponteiro para o elemento criado
list * cria_elemento(int idade, char nome[]){
    list *novo;
    novo = (list *) malloc(sizeof(list));
    novo->idade = idade;
    strcpy(novo->nome, nome);
    novo->prox = NULL;
    return novo;
}

// função para inserir 1 elemento na primeira posição da lista
list * insere_1o(list * lista, list * novo){
    novo->prox = lista;
    return novo;
}

// insere o novo elemento na última posição da lista
list * insert(list * lista, list * novo){
    if (lista != NULL) {
        list * aux = lista;
        while (aux->prox != NULL){
            aux = aux->prox;
        }
        aux->prox = novo;
        return lista;
    } else {
        return novo;
    }
}

list * remove_first(list * lista){
    list * aux = lista;
    // se lista vazia, não há o que ser feito!
    if (lista != NULL){
        lista = lista->prox;
        aux->prox = NULL;
        free(aux);
    }
    return lista;
}

list * remove_last(list * lista){
    list * aux = lista;
    list * aux2 = NULL;
    // se lista vazia, não há o que ser feito!
    if (aux != NULL){
        // percorre a lista até o último elemento
        while (aux->prox != NULL){
            aux2 = aux;
            aux = aux->prox;
        }
        if (aux2 == NULL){
            // se aux2 = NULL, a lista tem apenas 1 elemento
            free(aux);
            return NULL;
        } else {
            // se aux2 != NULL, a lista tem 2 ou mais elementos
            aux2->prox = NULL;
            free(aux);
        }
    }
    return lista;
}

void show_list(list * lista){
    // percorrendo os elementos da lista
    if (lista != NULL){
        printf("|");
        while (lista != NULL){
            printf("%d <--> %s| \n", lista->idade, lista->nome);
            lista = lista->prox;
        }
        printf("\n");
    }
    system("pause");
}

int main() {
    int idade, op;
    char nome[30];
    // nó de referência - início da lista
    list * lista = NULL;

    // insere elementos até que o usuário informe a opção zero
    do{
        printf("\t 1 - cadastrar 1 pessoa\n");
        printf("\t 2 - excluir 1 pessoa do início da lista\n");
        printf("\t 3 - excluir 1 pessoa do final da lista\n");
        printf("\t 4 - exibir pessoas cadastradas\n");
        printf("\t 0 - sair\n");
        printf("informe a opção desejada:\n");
        scanf(" %d", &op);

        switch(op){
            case 0:
                break;
            case 1:
                printf("informe a idade: \n");
                scanf(" %d", &idade);
                printf("informe o nome: \n");
                fflush(stdin);
                gets(nome);
                list * novo = cria_elemento(idade, nome);
                lista = insert(lista, novo);
                break;
            case 2:
                lista = remove_first(lista);
                break;
            case 3:
                lista = remove_last(lista);
                break;
            case 4:
                show_list(lista);
                break;
            default:
                printf("opção inválida \n");
        }
        system("cls");
    } while(op != 0);
}

1. Cria-se a estrutura da lista:
   
2. Cria-se a lista:
   
   1. Criar elemento/nó na lista.
      Exemplo:
      

1. Inserir no início de uma lista:
   Exemplo:
   
   1. Inserir no final de uma lista:
      Exemplo:
      

1. Remover do início de uma lista:
   Exemplo:
   
   

1. Percorrer/apresentar a lista:
   Exemplo:
   
   1. Inserir elemento em posição específica da lista:
      Exemplo:
      
      

Vantagens e desvantagens das listas

Vantagens de uma lista simples

• A inserção ou remoção não necessita que outros elementos sejam deslocados;
• Não há necessidade de se conhecer o tamanho da lista, pois a alocação é feita dinamicamente.

Desvantagens de uma lista simples

• A procura de um elemento em uma certa posição obriga que seja percorrido todo o caminho até esta posição;
• Sua implementação é mais complexa.

Vantagens de uma lista dupla

• Permite caminhar nas duas direções da lista;
• Inclusão e remoção de elementos são realizadas com mais facilidade.

Desvantagens de uma lista dupla

• Maior espaço alocado;
• Manipulação de um ponteiro extra.

Lista duplamente encadeada em C

struct no_lista{
    int elem;
    struct no_lista *prox;  /* guarda a posição do próximo elemento na lista */
    struct no_lista *ante;  /* guarda a posição do elemento anterior na lista */
};

struct lista{
    struct no_lista *head;  /* guarda o endereço do primeiro elemento da lista */
};

void Insere_Elemento(struct lista *L, int A){
    struct no_lista *aux, *ant, *atu;

    if ((aux = (struct no_lista *) malloc(sizeof(struct no_lista))) != NULL){
        aux->elem = A;
        if (L->head == NULL){
            aux->prox = NULL;
            aux->ante = NULL;
            L->head = aux;
        } else {
            atu = L->head;
            ant = NULL;
            while ((atu != NULL) && (atu->elem <= A)){
                ant = atu;
                atu = atu->prox;
            }
            if (ant == NULL){
                /* inserir na primeira posição da lista */
                aux->prox = L->head;
                aux->ante = NULL;
                L->head->ante = aux;
                L->head = aux;
            } else {
                aux->prox = ant->prox;
                aux->ante = ant;
                if (ant->prox != NULL)
                    ant->prox->ante = aux;
                ant->prox = aux;
            }
        }
    } else {
        exit(0);
    }
    return;
}