ED1A2-TADS – Solução de exercício de Lista Encadeada

Declaração do TAD – Tipo Adstrato de Dado

/*
* Declaração do TAD para a Lista Encadeada
* Arquivo: listaenc.h
*/

#ifndef LISTAENC_H
#define LISTAENC_H

#define POS_FINAL 0
#define MAX_ELEM 100

//-- Declaração da Estrutura de Dados --
struct No{
	char dado;
	struct No* prox;
};

struct ListaEnc{
	int tam;     //Tamanho da lista
	struct No* inicio; //Ponteiro para inicio da lista
};

//----- Protótipos das funções de manipulação da lista -----
int vazia(struct ListaEnc);
struct No* criarNo(char);
void iniciarLista(struct ListaEnc*);
void inserir(struct ListaEnc*, int, char);
void mostrarLista(struct ListaEnc);

#endif

Implementação das funções do TAD referente à lista

/*
* Implemantação das funções de manipulação da lista encadeada
* Arquivo: listaenc.c
*/

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

/*
 Verifica se uma lista encadeada esta vazia.
 @param lst - struct ListaEnc - Lista encadeada a ser verificada.
 @return 1 = Sim ou 0 = Não
*/
int vazia(struct ListaEnc lst) {
	if (lst.tam==0 && lst.inicio==NULL) 
		return 1;
	return 0;
}

/*
 Inicia uma lista encadeada para ser utilizada.
 @param lst - struct ListaEnc - Lista encadeada a ser iniciada.
 A lista é passada por referência.
*/
void iniciarLista(struct ListaEnc* lst) {
	lst->tam = 0;
	lst->inicio = NULL;
}

/*
 Cria um nó de dado para ser usado em uma lista.
 @param d - char referente ao dado para o nó.
 @return struct No* - ponteiro para o nó criado ou NULL caso haja falha.
*/
struct No* criarNo(char d) {
	struct No* no = (struct No*)malloc(sizeof(struct No));
	if (no==NULL) {
		printf("Falha ao tentar alocar memoria para nó de dado!");
	} else {
		no->dado = d;
		no->prox = NULL;
		printf("\nNo criado com %c..",d);
	}
	return no;
}

/*
 Insere um nó de dado em uma posição da lista que varia de 1 ao tamanho da lista.
 @param lst - struct ListaEnc* referência para a lista encadeada a ser manipulada.
 @param pos - int referente à posição de inserção desejada.
 @param d - char referente ao dado para o nó que será criado e inserido.
*/
void inserir(struct ListaEnc* lst, int pos, char dado) {
	if (lst->tam >= MAX_ELEM) {
		printf("\nFalha ao inserir. Lista cheia!");
	} else {
		if ((pos != POS_FINAL) && (pos < 0 || pos > lst->tam+1) )	{
			printf("\nFalha ao inserir. Posicao desejada (%d) alem dos limites!", pos);
		} else {
			struct No* noNovo = criarNo(dado);
			if (noNovo!=NULL) { //se criou nó com sucesso.
				if (pos == 1 || vazia(*lst)) { //se posicao desejada eh no inicio
					noNovo->prox = lst->inicio;
					lst->inicio = noNovo;
					printf("\nInserido %c em INICIO...", dado);
				} else {
					if (pos==POS_FINAL || pos==lst->tam+1) { //se pos desejada é no final
						int k = 1;
						struct No* noAtual = lst->inicio;
						while (noAtual->prox != NULL) {
							noAtual = noAtual->prox;
							k++;
						}
						noAtual->prox = noNovo;
						printf("\nInserido %c em POS_FINAL %d...", dado, k);
					} else {  //se a pos desejada eh intermediaria
						int k = 2;
						struct No* noAtual = lst->inicio->prox;
						struct No* noAnt = lst->inicio;
						while (kprox;
							noAnt = noAnt->prox;
							k++;
						}
						noNovo->prox = noAtual;
						noAnt->prox = noNovo;			
						printf("\nInserido %c intermediario %d...", dado, k);				
					}
				}
				lst->tam++;	//incrementa tamanho.
			} 
			
		}
	}
}

/*
 Mostra uma lista encadeada na tela.
 @param lst - struct ListaEnc lista encadeada a ser mostrada.
*/
void mostrarLista(struct ListaEnc lst) {
	if (vazia(lst)) {
		printf("Lista vazia!");
	} else {
	    struct No *noAtual = lst.inicio; //Inicia a partir de HEAD
	    printf("\n\nOs elementos da lista encadeada sao:\n");
	    int k=1;
	    while(noAtual != NULL) { //Enqaunto não for o FIM (NULL)
	        printf("%d-[%c]", k, noAtual->dado); //Mostra o dado do nó corrente
	        noAtual = noAtual->prox; //Avança ponteiro para proximo elemento
	        k++;
	        if (noAtual != NULL)
	            printf("--->"); //mostra representacao do ponteiro para proximo no.
	        else
	            printf("---NULL"); //mostra representacao de ponteiro de terminacao.
	    } 
	}
}

Teste do TAD de implementaççao da lista encadeada

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

int main(int argc, char *argv[]) {	
	struct ListaEnc le;
	printf("\nIniciando lista...");
	iniciarLista(&le);	
	mostrarLista(le);
	printf("\nInserindo O...");
	inserir(&le,POS_FINAL,'O'); //Cenario #1: insercao pos final lista vazia
	printf("\nInserindo A...");
	inserir(&le,POS_FINAL,'A');	
	printf("\nInserindo M...");
	inserir(&le,POS_FINAL,'M');	
	mostrarLista(le);  //A lista deve conter OAM
	
	inserir(&le,1,'K'); //Cenario #2: insercao no começo
	mostrarLista(le);  //A lista deve conter KOAM
	inserir(&le,3,'X'); //Cenário #3: insercao no meio
	mostrarLista(le); //A lista deve conter KOXAM
	
	inserir(&le,-2,'D'); //cenario #4: pos invalida começo
	inserir(&le,8,'D'); //cenario #5: pos invalida final	
	
	return 0;
}