Como fazer uma lista em C -Implementação completa (inserindo e retirando nós de qualquer posição)

Dando continuidade em nossa seção sobre estrutura dinâmica de dados e ao tutorial passado sobre Listas simplesmente encadeadas, onde criamos e ensinamos a colocar nós ao fim e no início da lista, e depois como retirar nós do início e do fim de uma lista, vamos agora mostrar como colocar elementos em qualquer ponto da lista, bem como tirar nós do início, do fim e de qualquer lugar da lista.

Como programar uma lista completa em C
Listas em C

Como criar uma lista completa em C

Este é o quarto artigo de nossa série sobre listas simplesmente encadeadas com cabeça.
Aqui mostraremos como inserir e retirar qualquer nó de nossa lista, e com isso temos um código completo, totalmente explicado, passo-a-passo sobre como criar esse tipo de estrutura de dados em C.

É o mais completo, com todo o código. Porém é necessário que você tenha lido os outros tutoriais de nossa apostila de C para entender melhor o que será explicado aqui:

Como obter certificado de programador C

Alterações em nossa lista

Agora que você já deve ter se familiarizado com os conceitos e lógicas de tirar e inserir elementos em uma lista, vamos fazer algumas mudanças, deixar o programa mais robusto e flexível.

Já no tutorial passado, na parte de inserir elementos, criamosa a função aloca(), que como o próprio nome diz, ela vai alocar espaço para uma estrutura, um nó em nossa lista.
Ela pede para inserir o número, colocar na variável 'num' da struct e retorna o endereço alocado dinamicamente.

Agora, criamos também a variável global tam, que irá armazenar o tamanho de nossa lista.
Ou seja, quantos nós tem nossa lista. E para contabilizar isso, toda vez que criamos um nó, incrementamos essa variável.
Analogamente, sempre que tiramos uma struct da lista, decrementamos a variável.

Alteramos também a função exibe, que agora exibe a ordem dos elementos na lista.
Conforme podemos ver na imagem no início deste tutorial.



Como inserir nós em qualquer posição da lista

Vamos agora mostrar como criar a função insere() que recebe a LISTA e pergunta ao usuário em que posição o usuário quer inserir o elemento na lista. Ou seja, se queremos inserir na posição 'n', o elemento vai ficar nessa posição 'n' e o que estava lá antigamente vai para frente, para posição 'n+1'.
O usuário vai dizer a posição e está sera armazenada na variável pos.

Podemos inserir desde a posição 1 até a 'tam'.
Obviamente, fora desse intervalo devemos mostrar uma mensagem de erro.
Feita essa verificação da posição, vamos adicionar o elemento na dita posição.

Caso seja posição 1, não devemos nos estressar.
Afinal, inserir um elemento na posição 1 é inserir uma estrutura no início da lista, e já criamos uma função para isto, a insereInicio(), bastando chamar ela: insereInicio(LISTA);

Caso seja em qualquer outra posição, a coisa fica mais trabalhosa.
O segredo para isto é identificar dois elementos.o anterior e o elemento que está naquela posição.

Por exemplo, se queremos colocar um nó na terceira posição, devemos guardar essa posição e a anterior, pois iremos fazer o segundo elemento apontar para o novo nó, e fazer esse novo nó apontar para aquele que estava na terceira posição.

Para isso vamos usar dois ponteiros do tipo node, o tipo de nossa estrutura: o 'atual' e o 'anterior'.
O atual começa no primeiro nó da LISTA, e o anterior não está em uma posição anterior (um aponta para LISTA->prox e o outro para LISTA).

Agora temos que fazer estes dois pontos 'correrem' pela lista até chegar onde queremos.
Vamos usar um laço for para isso, e em cada iteração fazemos o seguinte:
Fazemos o ponteiro 'anterior' receber o ponteiro 'atual', e depois fazemos o 'atual' receber o próximo elemento da lista, que é o 'atual->prox'.

Se queremos chegar na posição 4, por exemplo, devemos fazer esse procedimento 3 vezes, pois partimos da primeira posição da lista. Ou seja, fazemos isso (pos - 1) vezes, e ao final deste procedimento, o ponteiro 'atual' estará no elemento que mudará de posição (para frente), e o ponteiro 'anterior' apontará para a posição anterior:

for(count=1 ; count < pos ; count++){
	anterior=atual;
	atual=atual->prox;
}

E agora vamos inserir nosso nó, que criamos ao declarar o ponteiro 'novo' e fazer ele receber um bloco alocado pela função aloca().
Vamos lá, devagar pois não é tão simples.

Temos dois nós: o 'atual' e o 'anterior'. Queremos colocar um novo nó, o 'novo', no lugar do nó 'atual' e empurrar o 'atual' pra frente.
Para isso, devemos pegar o 'anterior' e fazer apontar para o 'novo': anterior->prox = novo;
E o novo nó deve apontar para o que estava nesse posição: novo->prox = atual;
E claro, incrementar o tamanho da lista: tam++;

Pronto. Já podemos colocar um nó no início, no fim ou em qualquer lugar de nossa lista :)
Vamos para o próximo passo: retirar elementos de nossa lista.

Como retirar estruturas de uma lista

Se já leu todos nossos tutoriais sobre listas em C, certamente já deve ter em mente como implementar um algoritmo que retire um elemento.

Vamos usar exatamente a mesma ideia que usamos na parte passada do tutorial, para achar os elementos 'atual' (que vamos excluir) e o anterior a ele.
Ou seja, aquele mesmo laço while será usado, da mesma maneira.

Porém, não vamos precisar de um novo nó, afinal não vamos adicionar nada, e sim retirar a struct apontada pelo ponteiro 'atual'.
E como vimos diversas, o ato de 'retirar' um nó de uma lista é simplesmente deixar de apontar algum elemento da lista para ele.

Quem aponta para o elemento que queremos retirar é: anterior->prox
Qual elemento que vem após o elemento que vamos retirar: atual->prox
Elemento retirado, que devemos retornar da função: atual

Ou seja, para excluir, basta apontarmos o elemento anterior ao que queremos retirar, para aquele elemento que vem DEPOIS do que queremos retirar.
Isso é feito da seguinte maneira: anterior->prox = atual->prox

E pronto. A lista continua ligada, mas sem o elemento 'atual', na qual retornamos, sem antes decrementar a variável tam, já que retiramos uma estrutura da lista.

Código completo de uma Lista em C

E finalmente, após muito estudo e trabalho, nosso código completo, de uma lista em C que nos permite inserir e retirar um nó (struct) de toda e qualquer posição.

É uma lista flexível, onde há diversas maneiras de trabalhar com ela, além de exibir seus elementos de uma maneira esteticamente agradável e faz uso de pouca memória (além de liberar ela, ao final da aplicação), sendo robusta e muito e eficiente:

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

struct Node{
	int num;
	struct Node *prox;
}; 
typedef struct Node node;

int tam;

void inicia(node *LISTA);
int menu(void);
void opcao(node *LISTA, int op);
node *criaNo();
void insereFim(node *LISTA);
void insereInicio(node *LISTA);
void exibe(node *LISTA);
void libera(node *LISTA);
void insere (node *LISTA);
node *retiraInicio(node *LISTA);
node *retiraFim(node *LISTA);
node *retira(node *LISTA);


int main(void)
{
	node *LISTA = (node *) malloc(sizeof(node));
	if(!LISTA){
		printf("Sem memoria disponivel!\n");
		exit(1);
	}else{
	inicia(LISTA);
	int opt;
	
	do{
		opt=menu();
		opcao(LISTA,opt);
	}while(opt);

	free(LISTA);
	return 0;
	}
}

void inicia(node *LISTA)
{
	LISTA->prox = NULL;
	tam=0;
}

int menu(void)
{
	int opt;
	
	printf("Escolha a opcao\n");
	printf("0. Sair\n");
	printf("1. Zerar lista\n");
	printf("2. Exibir lista\n");
	printf("3. Adicionar node no inicio\n");
	printf("4. Adicionar node no final\n");
	printf("5. Escolher onde inserir\n");
	printf("6. Retirar do inicio\n");
	printf("7. Retirar do fim\n");
	printf("8. Escolher de onde tirar\n");
	printf("Opcao: "); scanf("%d", &opt);
	
	return opt;
}

void opcao(node *LISTA, int op)
{
	node *tmp;
	switch(op){
		case 0:
			libera(LISTA);
			break;
			
		case 1:
			libera(LISTA);
			inicia(LISTA);
			break;
		
		case 2:
			exibe(LISTA);
			break;
		
		case 3:
			insereInicio(LISTA);
			break;		
			
		case 4:
			insereFim(LISTA);
			break;
			
		case 5:
			insere(LISTA);
			break;
		
		case 6:
			tmp= retiraInicio(LISTA);
			printf("Retirado: %3d\n\n", tmp->num);
			break;
			
		case 7:
			tmp= retiraFim(LISTA);
			printf("Retirado: %3d\n\n", tmp->num);
			break;
		
		case 8:
			tmp= retira(LISTA);
			printf("Retirado: %3d\n\n", tmp->num);
			break;
		
		default:
			printf("Comando invalido\n\n");
	}
}

int vazia(node *LISTA)
{
	if(LISTA->prox == NULL)
		return 1;
	else
		return 0;
}

node *aloca()
{
	node *novo=(node *) malloc(sizeof(node));
	if(!novo){
		printf("Sem memoria disponivel!\n");
		exit(1);
	}else{
		printf("Novo elemento: "); scanf("%d", &novo->num);
		return novo;
	}
}


void insereFim(node *LISTA)
{
	node *novo=aloca();
	novo->prox = NULL;
	
	if(vazia(LISTA))
		LISTA->prox=novo;
	else{
		node *tmp = LISTA->prox;
		
		while(tmp->prox != NULL)
			tmp = tmp->prox;
		
		tmp->prox = novo;
	}
	tam++;
}

void insereInicio(node *LISTA)
{
	node *novo=aloca();	
	node *oldHead = LISTA->prox;
	
	LISTA->prox = novo;
	novo->prox = oldHead;
	
	tam++;
}

void exibe(node *LISTA)
{
	system("clear");
	if(vazia(LISTA)){
		printf("Lista vazia!\n\n");
		return ;
	}
	
	node *tmp;
	tmp = LISTA->prox;
	printf("Lista:");
	while( tmp != NULL){
		printf("%5d", tmp->num);
		tmp = tmp->prox;
	}
	printf("\n        ");
	int count;
	for(count=0 ; count < tam ; count++)
		printf("  ^  ");
	printf("\nOrdem:");
	for(count=0 ; count < tam ; count++)
		printf("%5d", count+1);
	
		
	printf("\n\n");
}

void libera(node *LISTA)
{
	if(!vazia(LISTA)){
		node *proxNode,
			  *atual;
		
		atual = LISTA->prox;
		while(atual != NULL){
			proxNode = atual->prox;
			free(atual);
			atual = proxNode;
		}
	}
}

void insere(node *LISTA)
{
	int pos,
		count;
	printf("Em que posicao, [de 1 ate %d] voce deseja inserir: ", tam);
	scanf("%d", &pos);
	
	if(pos>0 && pos <= tam){
		if(pos==1)
			insereInicio(LISTA);
		else{
			node *atual = LISTA->prox,
				 *anterior=LISTA; 
			node *novo=aloca();
				 
			for(count=1 ; count < pos ; count++){
					anterior=atual;
					atual=atual->prox;
			}
			anterior->prox=novo;
			novo->prox = atual;
			tam++;
		}
			
	}else
		printf("Elemento invalido\n\n");		
}

node *retiraInicio(node *LISTA)
{
	if(LISTA->prox == NULL){
		printf("Lista ja esta vazia\n");
		return NULL;
	}else{
		node *tmp = LISTA->prox;
		LISTA->prox = tmp->prox;
		tam--;
		return tmp;
	}
				
}

node *retiraFim(node *LISTA)
{
	if(LISTA->prox == NULL){
		printf("Lista ja vazia\n\n");
		return NULL;
	}else{
		node *ultimo = LISTA->prox,
			 *penultimo = LISTA;
			 
		while(ultimo->prox != NULL){
			penultimo = ultimo;
			ultimo = ultimo->prox;
		}
			 
		penultimo->prox = NULL;
		tam--;
		return ultimo;		
	}
}

node *retira(node *LISTA)
{
	int opt,
		count;
	printf("Que posicao, [de 1 ate %d] voce deseja retirar: ", tam);
	scanf("%d", &opt);
	
	if(opt>0 && opt <= tam){
		if(opt==1)
			return retiraInicio(LISTA);
		else{
			node *atual = LISTA->prox,
				 *anterior=LISTA; 
				 
			for(count=1 ; count < opt ; count++){
				anterior=atual;
				atual=atual->prox;
			}
			
		anterior->prox=atual->prox;
		tam--;
		return atual;
		}
			
	}else{
		printf("Elemento invalido\n\n");
		return NULL;
	}
}

7 comentários:

Anônimo disse...

Estudei nesse site e digo é dos melhores, ate consegui fazer uma parte desse programa com esse estudo e a parte que nao consegui é a parte da alinea que vai de B a H.

Este programa é para desenvolver um Sistema de Registro e Controle do Pessoal, devidos em 3 niveis de acesso: Funcionarios, Docentes e Alunos. O programa permitirá inserir, eliminar, verificar, mostar os dados de todos e qualquer pessoal.
Use os teus conhecimentos sobre Estruturas e lista para implementar esse sistema.
O funcionário é registado com: Nome, NIF, Função, Categoria, salário.
O Docente é registado com : Nome, Disciplinas, NIF, Categoria, salário.
O Aluno é registado com : Nome, Curso, Ano_curso, Disciplinas, Estado (regular ou irregular).
Ao arrancar, o programa deverá apresentar o seguinte menu de opções:
1- Informações dos Funcionários;
2- Informações dos Docentes
3- Informações dos Alunos;
4 - Sair.
Dentro de cada menu podemos encontrar vários submenus:
i) Inserir
ii) Eliminar
iii) Verificar
iv) Mostrar dados
1. O programa deverá ser capaz de responder as seguintes questões:
A – Inserir e eliminar e mostrar dados de até 500 funcionários.
B – Quantos funcionários estão inscritos por categoria?
C – Qual a função e categoria de um determinado funcionário (sabendo o nome ou o NIF) ?
E - Sabendo que o docente Doutor recebe 3500$ por cada hora a mais (mais de 12 horas) e Mestre recebe 2500 por hora (mais de14 horas) e que cada disciplina tem em média 16 horas mensais, mostra o salário de um determinado docente em função das suas disciplinas.
F – Verifica quantos e que professores estão afectos a uma determinada disciplina e as suas categorias.
G – Verificar numa determina turma (disciplina), quantos alunos tem e quais estão em situação irregular.
H – Verifica se um aluno esta inscrito, em que ano e que disciplinas.
D – Quanto gasta a universidade com os funcionários e o por categoria.

Azinildo Neves disse...

Este programa pretende desenvolver um Sistema de Registro e Controle do Pessoal, devidos em 3 niveis de acesso: Funcionarios, Docentes e Alunos. O programa permitirá inserir, eliminar, verificar, mostar os dados de todos e qualquer pessoal.
Use os teus conhecimentos sobre Estruturas e Ficheiro para implementar esse sistema.
O funcionário é registado com: Nome, NIF, Função, Categoria, salário.
O Docente é registado com : Nome, Disciplinas, NIF, Categoria, salário.
O Aluno é registado com : Nome, Curso, Ano_curso, Disciplinas, Estado (regular ou irregular).
Ao arrancar, o programa deverá apresentar o seguinte menu de opções:
1- Informações dos Funcionários;
2- Informações dos Docentes
3- Informações dos Alunos;
4 - Sair.
Dentro de cada menu podemos encontrar vários submenus:
i) Inserir
ii) Eliminar
iii) Verificar
iv) Mostrar dados
1. O programa deverá ser capaz de responder as seguintes questões:
A – Inserir e eliminar e mostrar dados de até 500 funcionários.
B – Quantos funcionários estão inscritos por categoria?
C – Qual a função e categoria de um determinado funcionário (sabendo o nome ou o NIF) ?
D – Quanto gasta a universidade com os funcionários e o por categoria.
E - Sabendo que o docente Doutor recebe 3500$ por cada hora a mais (mais de 12 horas) e Mestre recebe 2500 por hora (mais de14 horas) e que cada disciplina tem em média 16 horas mensais, mostra o salário de um determinado docente em função das suas disciplinas.
F – Verifica quantos e que professores estão afectos a uma determinada disciplina e as suas categorias.
G – Verificar numa determina turma (disciplina), quantos alunos tem e quais estão em situação irregular.
H – Verifica se um aluno esta inscrito, em que ano e que disciplinas.

Muito importante para mim.

LUCAS disse...

E como eu faria uma outra opção no menu, ORDENANDO a lista? Parabéns pelo blog, só tá faltando completar o cabeçalho do blog com as outras matérias, por exemplo colocar Lista Dinâmica do lado de Alocação e Arquivos. Abraço.

Anônimo disse...

Ah tendi tudinho vcs estao me ensinando muito kkk vou bugar cupons do ddtank geral kkk

Anônimo disse...

Atual->prox" seria :atual(element)aponta Para o proximo element?(o proximo nó)?

Francieldo Noronha disse...

como faço com string ? com letras

Unknown disse...

Bom dia,

ha um erro no codigo, a primeiros funcao declarada apos a funcao opcao e:

int vazia (node *LISTA)

o correto seria:

int inicia (node *LISTA)

Gostou desse tutorial de C?
Sabia que o acervo do portal C Progressivo é o mesmo, ou maior que, de um livro ou curso presencial?
E o melhor: totalmente gratuito.

Mas para nosso projeto se manter é preciso divulgação.
Para isso, basta curtir nossa página no Facebook e/ou clicar no botão +1 do Google.
Contamos e precisamos de seu apoio.