Lista encadeada na linguagem C • Chalet Blog

Lista encadeada na linguagem C

By marcosChalet

2023-06-16

Sumário

O que são?
Algumas funções auxiliares
Criar lista
Inserir elemento na lista
- Inserir no início da lista
- Inserir no fim da lista
- Inserir de forma ordenada na lista
Remover elemento na lista
- Remover no início da lista
- Remover no fim da lista
- Remover por valor da lista
Destruir lista
Mostrar lista
Como organizar melhor o código
- Arquivo lista.h
- Arquivo lista.c
- Arquivo main.c

O que são?

Lista é uma estrutura de dados que tem como característica a ligação de elementos, que chamamos de nós, de modo que cada um tenha pelo menos uma referência para o próximo da cadeia sem restrições específicas quanto a acesso, busca e remoção de nós.

As listas podem ser classificadas em dois tipos: listas simplesmente encadeadas e listas duplamente encadeadas. Na lista encadeada, cada nó mantém uma referência para o próximo elemento da estrutura de dados. Já na duplamente encadeada, cada um possui duas referências: uma para o próximo nó da lista e outra para o anterior. Veja a representação.

Imagem com a representação da lista encadeada e duplamente encadeada.

Algumas funções auxiliares

int tamanho (Lista *lse) {
	if (lse == NULL)
		return -1;
	return lse->qtd;
}

int cheia (Lista *lse) {
	if (lse == NULL)
		return -1;
	else if (lse->qtd == MAX)
		return 1;
	else
		return 0;
}

int vazia (Lista *lse) {
	if (lse == NULL)
		return -1;
	else if (lse->qtd == 0)
		return 1;
	else
		return 0;
}

Criar lista

struct lista {
	int qtd;
    struct aluno dados[MAX];
};

Lista* criar () {
    Lista *lse;
    lse = (Lista*)malloc(sizeof(Lista));

    if (lse != NULL)
      lse->qtd = 0;

    return lse;
}

Inserir elemento na lista

Breve explicação de como deve-se inserir...

Inserir no início da lista

int inserirInicio (Lista *lse, struct aluno novo) {
	if (lse == NULL) {
		return 0;
	}
	else if (cheia(lse)) {
		return 0;
	}
	else {
		int i;
		for (i = (lse->qtd)-1; i >= 0; i--) {
			lse->dados[i+1] = lse->dados[i];
		}
		lse->dados[0] = novo;
		lse->qtd++;
	}
	return 1;
}

Inserir no fim da lista

int inserirFim (Lista *lse, struct aluno novo) {

	if (lse == NULL) {
		return 0;
	}
	else if (cheia(lse)) {
		return 0;
	}
	else {
		lse->dados[lse->qtd] = novo;
		lse->qtd++;
	}
	return 1;
}

Inserir de forma ordenada na lista

int inserirOrdenado (Lista *lse, struct aluno novo) {
	if (lse == NULL) {
		return 0;
	}
	else if (cheia(lse)) {
		return 0;
	}
	else {
		int i, pos = 0;

		while (lse->dados[pos].matricula < novo.matricula && pos < lse->qtd)
			pos++;

		for (i = (lse->qtd)-1; i >= pos; i--) {
			lse->dados[i+1] = lse->dados[i];
		}
		lse->dados[pos] = novo;
		lse->qtd++;
	}
	return 1;
}

Remover elemento na lista

Explicação de como a remoção funciona...

Remover no início da lista

int removerInicio (Lista *lse) {
	if (lse == NULL) {
		return 0;
	}
	else if (vazia(lse)) {
		return 0;
	}
	else {
		int i;
		for (i = 0; i < lse->qtd-1; i++)
			lse->dados[i] = lse->dados[i+1];
		lse->qtd--;
	}
	return 1;
}

Remover no fim da lista

int removerFim (Lista *lse) {
	if (lse == NULL)
		return 0;
	else if (vazia(lse))
		return 0;
	else
		lse->qtd--;

	return 1;
}

Remover por valor da lista

int removerValor (Lista *lse, int x) {
	if (lse == NULL) {
		return 0;
	}
	else if (vazia(lse)) {
		return 0;
	}
	else {
		int i, pos = 0;

		while (lse->dados[pos].matricula != x && pos < lse->qtd)
			pos++;

		if (pos == lse->qtd)
			return 0;

		for (i = pos; i < lse->qtd-1; i++)
			lse->dados[i] = lse->dados[i+1];
		lse->qtd--;
	}
	return 1;
}

Destruir lista

void destruir (Lista *lse) {
	free(lse);
}

Mostrar lista

void mostrar (Lista *lse) {
    if(lse == NULL) return;
    if(vazia(lse)) return;

    /* Mostra do início até o fim */
    int cont = 0;

    printf("Lista -> ");
    while (cont < lse->qtd-1) {
        printf("[%d] -> ", lse->dados[cont].matricula);
        cont++;
    }
    printf("[%d] -> ||\n", lse->dados[cont].matricula);


    /* Mostra do fim até o início */
    printf("Lista -> ");
    while(cont >= 0) {
        printf("[%d] -> ", lse->dados[cont].matricula);
        cont--;
    }
    printf("||\n");
}

Como organizar melhor o código

Arquivo lista.h

#ifndef _LISTAESTATICA_H
#define _LISTAESTATICA_H

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

#define MAX 100

struct aluno {
    char nome[50];
    int matricula;
    float av1;
    float av2;
    float av3;
};

typedef struct lista Lista;

Lista* criar ();
void destruir (Lista *);

int tamanho (Lista *);
int cheia (Lista *);
int vazia (Lista *);

int inserirFim (Lista *, struct aluno );
int inserirInicio (Lista *, struct aluno );
int inserirOrdenado (Lista *, struct aluno );

int removerFim (Lista *);
int removerInicio (Lista *);
int removerValor (Lista *, int);

int acessarIndice (Lista *, int , struct aluno *);
int acessarValor (Lista *, int , struct aluno *);

void mostrar (Lista *);

#endif

Arquivo lista.c

#include "listaEstatica.h"

struct lista {
	int qtd;
    struct aluno dados[MAX];
};

Lista* criar () {
    /*
     * Aloca uma lista e seta ela como vazia caso a alocação ocorra
     * correntamente.
     * */

    Lista *lse;
    lse = (Lista*)malloc(sizeof(Lista));

    if (lse != NULL)
            lse->qtd = 0;

    return lse;
}


void destruir (Lista *lse) {
	free(lse);
}


int tamanho (Lista *lse) {
	if (lse == NULL)
		return -1;
	return lse->qtd;
}


int cheia (Lista *lse) {
	if (lse == NULL)
		return -1;
	else if (lse->qtd == MAX)
		return 1;
	else
		return 0;
}


int vazia (Lista *lse) {
	if (lse == NULL)
		return -1;
	else if (lse->qtd == 0)
		return 1;
	else
		return 0;
}


int inserirFim (Lista *lse, struct aluno novo) {

	if (lse == NULL) {
		return 0;
	}
	else if (cheia(lse)) {
		return 0;
	}
	else {
		lse->dados[lse->qtd] = novo;
		lse->qtd++;
	}
	return 1;
}


int inserirInicio (Lista *lse, struct aluno novo) {
	if (lse == NULL) {
		return 0;
	}
	else if (cheia(lse)) {
		return 0;
	}
	else {
		int i;
		for (i = (lse->qtd)-1; i >= 0; i--) {
			lse->dados[i+1] = lse->dados[i];
		}
		lse->dados[0] = novo;
		lse->qtd++;
	}
	return 1;
}


int inserirOrdenado (Lista *lse, struct aluno novo) {
	if (lse == NULL) {
		return 0;
	}
	else if (cheia(lse)) {
		return 0;
	}
	else {
		int i, pos = 0;

		while (lse->dados[pos].matricula < novo.matricula && pos < lse->qtd)
			pos++;

		for (i = (lse->qtd)-1; i >= pos; i--) {
			lse->dados[i+1] = lse->dados[i];
		}
		lse->dados[pos] = novo;
		lse->qtd++;
	}
	return 1;
}


int removerFim (Lista *lse) {
	if (lse == NULL)
		return 0;
	else if (vazia(lse))
		return 0;
	else
		lse->qtd--;

	return 1;
}


int removerInicio (Lista *lse) {
	if (lse == NULL) {
		return 0;
	}
	else if (vazia(lse)) {
		return 0;
	}
	else {
		int i;
		for (i = 0; i < lse->qtd-1; i++)
			lse->dados[i] = lse->dados[i+1];
		lse->qtd--;
	}
	return 1;
}


int removerValor (Lista *lse, int x) {
	if (lse == NULL) {
		return 0;
	}
	else if (vazia(lse)) {
		return 0;
	}
	else {
		int i, pos = 0;

		while (lse->dados[pos].matricula != x && pos < lse->qtd)
			pos++;

		if (pos == lse->qtd)
			return 0;

		for (i = pos; i < lse->qtd-1; i++)
			lse->dados[i] = lse->dados[i+1];
		lse->qtd--;
	}
	return 1;
}


int acessarIndice (Lista *lse, int pos, struct aluno *a) {
	if (lse == NULL)
		return 0;
	else if (pos < 0 || pos >= lse->qtd)
		return 0;
	else
		*a = lse->dados[pos];

	return 1;
}


int acessarValor (Lista *lse, int x, struct aluno *a) {
	if (lse == NULL) {
		return 0;
	}
	else {
		int pos = 0;

		while (lse->dados[pos].matricula != x && pos < lse->qtd)
			pos++;

		if (pos == lse->qtd)
			return 0;
		else
			*a = lse->dados[pos];
	}
	return 1;
}


void mostrar (Lista *lse) {
    if(lse == NULL) return;
    if(vazia(lse)) return;

    /* Mostra do início até o fim */
    int cont = 0;

    printf("Lista -> ");
    while (cont < lse->qtd-1) {
        printf("[%d] -> ", lse->dados[cont].matricula);
        cont++;
    }
    printf("[%d] -> ||\n", lse->dados[cont].matricula);


    /* Mostra do fim até o início */
    printf("Lista -> ");
    while(cont >= 0) {
        printf("[%d] -> ", lse->dados[cont].matricula);
        cont--;
    }
    printf("||\n");
}

Arquivo main.c

#include "listaEstatica.h"

int main () {

	Lista *lse;
	lse = NULL;
	lse = criar();
	struct aluno aluno;
/*
	aluno.matricula = 12345;
	inserirInicio(lse, aluno);

	aluno.matricula = 11111;
	inserirInicio(lse, aluno);

	aluno.matricula = 44411;
	inserirInicio(lse, aluno);

	aluno.matricula = 55555;
	inserirFim(lse, aluno);
*/

	aluno.matricula = 12345;
	inserirOrdenado(lse, aluno);

	aluno.matricula = 11111;
	inserirOrdenado(lse, aluno);

	aluno.matricula = 44411;
	inserirOrdenado(lse, aluno);

	aluno.matricula = 55555;
	inserirOrdenado(lse, aluno);

	aluno.matricula = 99925;
	inserirOrdenado(lse, aluno);

	aluno.matricula = 10000;
	inserirOrdenado(lse, aluno);

	removerInicio(lse);
	removerFim(lse);
	removerValor(lse, 44411);

	mostrar(lse);
	return 0;
}