Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

n1ckooo

Listas duplamente ligadas (Vector)

Mensagens Recomendadas

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();


}

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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));

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.