Listas em C |
- Leia este tutorial no seu computador ou celular: Apostila C Progressivo
Como criar uma lista completa em C
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
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; } }
13 comentários:
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.
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.
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.
Ah tendi tudinho vcs estao me ensinando muito kkk vou bugar cupons do ddtank geral kkk
Atual->prox" seria :atual(element)aponta Para o proximo element?(o proximo nó)?
como faço com string ? com letras
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)
Conseguiu de forma simples e rápida mostrar como manipular basicamente uma lista simplesmente encadeada. Ajudou muito, obrigado!
Muito bom as aula, são tão boas as aula que meu professor até copiou o código de vcs e passou pra turma implementar algumas funções, acho que compensa mais ler as apostilas que ir na aula dele hehehe
Fiz uma modificação na inserção de um elemento em qualquer posição da lista. Consegui usar apenas um ponteiro para isso, ao invés de dois. Segue abaixo.
Node *tmp = lista->nextNode;
int i;
for (i=2; inextNode;
}
novo->nextNode = tmp->nextNode;
tmp->nextNode = novo;
tam++;
Muito bom o código e a aula. Realmente melhor que na Faculdade que estudo....
Gostaria de saber como faço esta lista usando caracteres (char) ou strings no lugar de números, como se fosse um cadastro de livros, por exemplo.
Obrigado.
Testando
Muito Bom o código so fiz uma modificação para que não gerasse números aleatórios, mas sim numeros pedidos diretamente no input
Postar um comentário