Buscar

Listas circulares e encadeadas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 10 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 10 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 10 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Apostila de C online e gratuita
C Progressivo.net
Índice Básico Teste e Laços Função Vetores Ponteiros Strings Structs Alocação
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.
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:
O que é e como funciona uma lista
Inserindo nós no início e no fim
Retirando nós no início e no fim
Como obter certificado de programador C
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.
Listas em C
Como criar uma lista completa em C
Alterações em nossa lista
+654   Recomende isto no Google
Linguagem C (Review)
Livro Recomendado
Gostou dos tutoriais?
Ajude a divulgar!
Seja o primeiro de seus
amigos a curtir isso.
C Progr
5,2 mil curtidas
…
Curtir Página
Conteúdo original -
Todos os direitos
reservados
Como fazer uma lista em C -Implementação co... http://www.cprogressivo.net/2013/10/Como-faze...
1 de 10 20/09/2016 16:00
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.
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++;
Como inserir nós em qualquer posição da lista
Visite também
Política de Privacidade
Como fazer uma lista em C -Implementação co... http://www.cprogressivo.net/2013/10/Como-faze...
2 de 10 20/09/2016 16:00
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.
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.
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");
Como retirar estruturas de uma lista
Códigocompleto de uma Lista em C
Como fazer uma lista em C -Implementação co... http://www.cprogressivo.net/2013/10/Como-faze...
3 de 10 20/09/2016 16:00
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;
Como fazer uma lista em C -Implementação co... http://www.cprogressivo.net/2013/10/Como-faze...
4 de 10 20/09/2016 16:00
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++;
}
Como fazer uma lista em C -Implementação co... http://www.cprogressivo.net/2013/10/Como-faze...
5 de 10 20/09/2016 16:00
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");
Como fazer uma lista em C -Implementação co... http://www.cprogressivo.net/2013/10/Como-faze...
6 de 10 20/09/2016 16:00
Tags: Alocação dinâmica de memória, Estrutura Dinâmica de Dados, Lista, Lista simplesmente
encadeada, Ponteiros
}
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;
}
}
Como fazer uma lista em C -Implementação co... http://www.cprogressivo.net/2013/10/Como-faze...
7 de 10 20/09/2016 16:00
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.
21 de junho de 2014 13:41
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
Como fazer uma lista em C -Implementação co... http://www.cprogressivo.net/2013/10/Como-faze...8 de 10 20/09/2016 16:00
Postagem mais recente Postagem mais antigaPágina inicial
Assinar: Postar comentários (Atom)
Postar um comentário
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.
21 de junho de 2014 13:46
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.
27 de agosto de 2014 11:08
Anônimo disse...
Ah tendi tudinho vcs estao me ensinando muito kkk vou bugar cupons do ddtank
geral kkk
3 de janeiro de 2016 05:31
Anônimo disse...
Atual->prox" seria :atual(element)aponta Para o proximo element?(o proximo nó)?
3 de janeiro de 2016 05:34
Francieldo Noronha disse...
como faço com string ? com letras
30 de janeiro de 2016 03:24
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)
29 de maio de 2016 05:33
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.
Como fazer uma lista em C -Implementação co... http://www.cprogressivo.net/2013/10/Como-faze...
9 de 10 20/09/2016 16:00
Publicidade
Melhor visualizado com Google Chrome e Mozilla Firefox
Como fazer uma lista em C -Implementação co... http://www.cprogressivo.net/2013/10/Como-faze...
10 de 10 20/09/2016 16:00

Outros materiais