Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
n1ckooo

Listas duplamente ligadas (Vector)

Recommended Posts

n1ckooo

Estou com algumas (muitas) duvidas como criar um vector de Listas usando as funções, malloc e realloc.

As listas serão as "Turmas" e os nós de cada lista será os "alunos".

A minha duvida é o seguinte como faço, para inserir uma turma nova Lista *L.

L =  (LISTA *) malloc ( zizeof(LISTA));

depois quero inserir outra turma (a 2ª), não é possível fazer algo como,

L = (LISTA *)realloc(L,2); ???

Em baixo deixo o código, para quem tiver paciência para ver, peço que apontem erros, algoritmos pouco eficientes, e principalmente que me ajudem nestas duvidas.

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

#define MAXNOME 80


typedef struct aluno
{
int num;
char nome[MAXNOME];
}ALUNO;



typedef struct NoLista *ApLista;

typedef struct NoLista
{
ALUNO elemento;
ApLista NoSeguinte,NoAnterior;

}No;

typedef struct lista //turmas
{
ApLista ApActual; 
int contador,PosActual;
int turma;
}LISTA;


// Inicializa a lista 
void CreateLista(LISTA *L)
{
(*L).ApActual = NULL;	
(*L).contador = 0;
(*L).PosActual =0;
//L -> cabeca = NULL;
//L -> contador = 0;

}

// define posisao
void SetPosition(int pos,LISTA *L)
{
int i;

if((pos<0) || (pos > (*L).contador-1))
	puts("Posicão fora da lista");
else
{
	// Se for diferente de P tem que mudar de node ate ser igual a Pos
	if((*L).PosActual < pos)
	{
		do
		{
			(*L).PosActual++;
			(*L).ApActual = L -> ApActual -> NoSeguinte;

		}while((*L).PosActual != pos);
	}
	else if((*L).PosActual > pos)
	{
		do
		{
			(*L).PosActual--;
			(*L).ApActual = L -> ApActual -> NoAnterior;

		}while((*L).PosActual != pos);

	}

}

}

// Adiciona Node
void InsertNode(int pos, ALUNO x, LISTA *L) {
ApLista NovoNo, ASeguir;
if((pos<0) || (pos > (*L).contador))
	printf("Erro : insercao numa posicao fora da lista");
else 
{
	NovoNo=(ApLista)malloc(sizeof(No));
	(*NovoNo).elemento=x;
	if(pos==0) 
	{
		(*NovoNo).NoAnterior = NULL;

		if((*L).contador ==0)
		{
			(*NovoNo).NoSeguinte = NULL;
		}
		else
		{
			SetPosition(0,L);
			(*NovoNo).NoSeguinte= (*L).ApActual;
			(*(*L).ApActual).NoAnterior = NovoNo;
		}

	}
	else 
	{
		SetPosition(pos-1, L);
		ASeguir=(*(*L).ApActual).NoSeguinte;
		(*NovoNo).NoSeguinte = ASeguir;
		(*NovoNo).NoAnterior = (*L).ApActual;
		(*(*L).ApActual).NoSeguinte=NovoNo;
		if(ASeguir!=NULL)
			(*ASeguir).NoAnterior = NovoNo;
	}
	(*L).ApActual=NovoNo;
	(*L).PosActual=pos;
	(*L).contador++;
}	
}

ALUNO DelNode(int pos,LISTA *L)
{
ApLista DelNode,ASeguir;
ALUNO x;
int i;
if((pos <0)|| (pos > (*L).contador-1))
	puts("Erro");
else
{
	if (pos ==0)
	{
		SetPosition(0,L);
		DelNode = (*L).ApActual;

		if ((*L).contador == 1)
		{
			(*L).ApActual = (*DelNode).NoAnterior;
		}
		else // Posicao = 0 E Contador > que 1;
		{
			/*puts("Pos =0 E Contador > que 1");
			getch();*/
			(*L).ApActual = DelNode -> NoSeguinte;
			(*(*L).ApActual).NoAnterior = NULL;

		}
	}
	else
	{
		SetPosition(pos-1,L); //1
		DelNode = L -> ApActual -> NoSeguinte;	//2
		ASeguir = DelNode -> NoSeguinte; 	//3
		L-> ApActual -> NoSeguinte = ASeguir; 	//4

		if(ASeguir!=NULL)
			ASeguir -> NoAnterior = (*L).ApActual; 	//5
	}
	(*L).contador--;
	x = (*DelNode).elemento;
	free(DelNode);
	return x;
}
}

void Traverse(LISTA *L)
{
int i =0;
SetPosition(0,L);
ApLista ApActual;
ApActual = (*L).ApActual;
while(ApActual != NULL)
{
	printf("%d - ",(*ApActual).elemento.num);
	puts((*ApActual).elemento.nome);
	ApActual = (*ApActual).NoSeguinte;
}

} 


main()
{
ALUNO x;
LISTA *L;

L = (LISTA *)malloc(sizeof(LISTA));
CreateLista(L);

int z;
int pos;
int op =0;
int nlista;
do
{ 
	op = Menu();
	switch(op)
	{
		case 1:
		//	nlista = EscolheLista();
			x = LerDados();
			InsertNode(0,x,L);
			system("cls");
			break;
		case 2:
			Traverse(L);
			getch();
			system("cls");
			break;
		case 3:
			if (ListEmpty(L) != 1)
			{
				pos = Posicao();
				x =DelNode(pos,L);
				puts("Os Seguintes dados foram eliminados");
				PrintAluno(x);	
			}
			else
				puts("Lista Nao Tem dados para apagar");
			getch();
			system("cls");
			break;
	case 4://Verifica vazia
			z = ListEmpty(L);
			if(z==1)
			{
				puts("Lista vazia");
			}
			getch();
			break;
		case 5: //Numero de elementos
			z = ListSize(L);
			printf("N elementos: %d",z);
			getch();
			break;
		case 6: //LIMPA LISTA
			ClearList(L);
			puts("Lista limpa");
			getch();
			break;
		case 7: 
			pos= Posicao();
			x = RetrieveList(pos,L);
			system("cls");
			PrintAluno(x);
			getch();
			break;
		case 8:
			x = LerDados();
			pos= Posicao();
			ReplaceList(pos,x,L);
			puts("SUBSTITUIDOS");
			getch();
			system("cls");
			break;
		case 0:
			break;
		default:
			puts("OPCAO INVALIDA");
	}
}
while (op!=0);


getch();


}

Share this post


Link to post
Share on other sites
_7_up_

Se no inicio so tens um elemento no array sugeriste bem:

L =  (LISTA *) malloc ( sizeof(LISTA));

Depois no realloc tens de indicar o novo tamanho do vector. Tens de guardar o numero de elementos(N) q o array já tem para indicares o novo tamanho com espaço para mais 1 elemento:

L =  (LISTA *) realloc (L, sizeof(LISTA) * (N+1));

Share this post


Link to post
Share on other sites
n1ckooo

Se no inicio so tens um elemento no array sugeriste bem:

L =  (LISTA *) malloc ( sizeof(LISTA));

Depois no realloc tens de indicar o novo tamanho do vector. Tens de guardar o numero de elementos(N) q o array já tem para indicares o novo tamanho com espaço para mais 1 elemento:

L =  (LISTA *) realloc (L, sizeof(LISTA) * (N+1));

Sim no inicio só terá um, depois conforme o utilizador quer criar mais uma turma(lista) uma função especifica ira fazer esse trabalho alocar mais um e assim sucessivamente. o problema é não encontrei a função ideal para criar o 1º e para realocar, amanha vou pensar melhor nisso, obrigado pela ajuda :D

Share this post


Link to post
Share on other sites
n1ckooo

Ainda com duvidas na função para criar uma nova lista.

Duvidas:

Se for a primeira lista então faço L = (LISTA *) malloc(sizeof(LISTA)); ?

depois contador = contador +1; ??

se não for a primeira lista ou seja se contador > 0 entao faco

L= (LISTA *) realloc(L,contador +1;

e depois incremento o contador...

Esta correcto esta ideia?

Share this post


Link to post
Share on other sites
_7_up_

Olha, cria logo com espaço para 500 turmas e acabou-se...

E se o contador >= 500 fazes realloc para 1000.....

Share this post


Link to post
Share on other sites
n1ckooo

Para isso isso não faz muita lógica o objectivo é fazer com que nao seja usado memoria desnecessária.

Share this post


Link to post
Share on other sites
_7_up_

O realloc pode ser muito eficiente no caso em que não é preciso copiar o conteudo do buffer para outra zona de memória, isto é, nos caso em que há memória livre nas posições de memória imediatamente asseguir ao buffer, suficientes para a nova quantidade de memória.

Noutros casos o realloc pode copiar vezes demais o buffer, o q é desperdício tb.

Agora é fazer as contas... o teu sizeof(LISTA) devolve ai quê? Ora quatro inteiros dá ai 4 x 32 bits = 128bits = 16 bytes.

Repara q se alocares logo:

64 posições são 64 x 16 bytes = 1024 bytes = 1KB

65536 posições são 65536 x 16 bytes = 1048576 bytes = 1MB

Isso mesmo! Espaço para 65536 turmas com apenas 1MB mas tu é q sabes da tua vida!!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.