Listas

Happening · March 30, 2012 at 11:05 AM

Alguem me consegue explicar o que são e como funcionam as listas em c?

Tenho tentado trabablhar com elas mas como não as entendo é complicado...

Como é que consigo fazer alocação da memoria automatica, do género usando duas structs. Ouvi dizer que era possivel.

Agradeço desde já a quem me puder ajudar.

HappyHippyHippo · March 30, 2012 at 11:13 AM

struct XPTO {
  int a;
  int b;
};

...

  int lista_com_3_inteiros[3];
  XPTO lista_com_4_estruturas_XPTO[4];

  /*atribuição do valor dez à primeira posição da lista */
  lista_com_3_inteiros[0] = 10;
  /* atribuição do valor vinte à segunda posição da lista */
  lista_com_3_inteiros[1] = 20;
  /* atribuição do valor trinta à terceira posição da lista */
  lista_com_3_inteiros[2] = 30;

  /* atribuição ao parâmetro 'a' do primeiro elemento da lista com XPTO's o valor da terceira posição da lista de inteiros */
  lista_com_4_estruturas_XPTO[0].a = lista_com_3_inteiros[2];

  /* ERRO : a lista de inteiros so tem 3 elementos, mas o indice com o valor 3 é a quarta posição !!!!  */
  lista_com_3_inteiros[3] = 40;

pmg · March 30, 2012 at 11:24 AM

Alguem me consegue explicar o que são e como funcionam as listas em c?

Tenho tentado trabablhar com elas mas como não as entendo é complicado...

Uma lista é uma estrutura de dados composta por elementos em que cada elemento aponta para o elemento seguinte. Os elementos são sequenciais, isto é, a lista é ordenada, ou seja, os elementos têm número de ordem (o primeiro, o segundo, o quinquagésimo, ..., o último)

Vê o artigo na Wikipedia 😕

Em C, normalmente usa-se uma estrutura para representar cada elemento: essa estrutura tem (entre outras coisas) o apontador para o elemento seguinte.

struct elemento_da_lista {
    /* outras coisas */
    struct elemento_da_lista *next;
};

Como é que consigo fazer alocação da memoria automatica, do género usando duas structs. Ouvi dizer que era possivel.

Não. Em C não há nada automático!

Tens que fazer a alocação (e libertação) à pata mesmo.

Happening · March 30, 2012 at 07:30 PM

Boas, passo a explicar: sou estudante de engenharia e estou a estudar C.

Tenho tido algumas dificuldades e hoje na aula de programação na implementação de funçoes para mexer nas listas das mais variadas maneiras o professor disse que fazendo duas estruturas se podia criar (digamos assim) espaço para mais uma estrutura igual.

por exemplo:

typedef struct
{
    char nome[100];
    int idade;
} criança;

typedef struct item
{
    criança ca;
    struct item *proximo;
} listaItem;

depois de inicializar estas estruturas quando fosse para aumentar a lista ou seja criar lugar para mais uma criança podia-se fazer algo do género Mem=ca... (não me lembro do resto).

Eu sei que não é nada esclarecedor o que estou a dizer mas é porque eu estou mt confuso quanto a esta matéria... 😕

Edit: GeSHi adicionado e codigo reindentado (pmg)

pmg · March 30, 2012 at 07:38 PM

Alocacao manual!

Mem = calloc(1, sizeof *Mem);

Para libertar a memoria, nao te esquecas de

free(Mem);

Sugestao: nao uses caracteres esquisitos (especificamente o c com cedilha) no teu codigo. Principalmente nos nomes das varaiaveis ... ja para nao falar nos comentarios 😕

Happening · March 30, 2012 at 08:14 PM

O ca... era daquela variavel na struct xD

de qualquer maneira obrigado 😉

Tenho o livro de programação em C do Luis Damas ISBN 978-972-722-156-1 o livro até é bom mas não tem exercicios em que misture várias temáticas e não tem listas... Aconselham algum? 🙂

Já agora quando falamos de listas é o mesmo que falar de filas?? :0

bsccara · March 30, 2012 at 11:13 PM

A minha iniciação no C foi feita numas férias a ler o 'C - The Complete Reference' de Herbert Shildt, da Osborne McGraw-Hill, edição original em inglês. A edição actual está na Amazon (http://www.amazon.com/The-Complete-Reference-4th-Ed/dp/0072121246) mas essa não conheço.

Já agora quando falamos de listas é o mesmo que falar de filas?? :0

Não, podes fazer filas ('queues') com listas. É como árvores e cadeiras; podes fazer uma a partir da outra mas não o inverso. 😉

mundo · March 31, 2012 at 09:44 AM

Tem sim Happening, o teu professor não referiu listas ligadas como estruturas dinâmicas? lol

Happening · March 31, 2012 at 11:49 AM

Ahhnnnn tenho quase a certeza que não, acho que querem que saibamos as listas bem primeiro antes de iniciar as filas....

Deixem me ver se eu percebo a ideia por trás das 2 structs:

Na 1ª struct (criança) estamos a reservar um espaço para uma string e outro para um inteiro, (A string até devia ser nome[100+1], para ter 100 caracteres).

Na 2ª struct estamos a atribuir o tipo criança ao ca, e a criar um apontador para o próximo elemento. O ca parece-me que é o numero total de crianças???? Estou certo??

A partir daí a lista está criada e é só reallocar para o número total de crianças a o espaço na memória para a 1ª struct.

Estou certo? Corrijam-me por favor se eu estiver equivocado.

pmg · March 31, 2012 at 12:15 PM

typedef struct
{
    char nome[100];
    int idade;
} criança;

typedef struct item
{
    criança ca;
    struct item *proximo;
} listaItem;

Deixem me ver se eu percebo a ideia por trás das 2 structs:

Na 1ª struct (criança) estamos a reservar um espaço para uma string e outro para um inteiro, (A string até devia ser nome[100+1], para ter 100 caracteres).

Na 2ª struct estamos a atribuir o tipo criança ao ca, e a criar um apontador para o próximo elemento. O ca parece-me que é o numero total de crianças???? Estou certo??

A partir daí a lista está criada e é só reallocar para o número total de crianças a o espaço na memória para a 1ª struct.

Estou certo? Corrijam-me por favor se eu estiver equivocado.

Não, não é bem assim.

Primeiro tens de ter um objecto inicial fixo para o inicio da lista

struct item *inicio;

E como ao principio a lista está vazia, indicas isso mesmo pondo o inicio a apontar para NULL

inicio = NULL;

Quando tiveres um elemento pronto a fazer parte da lista

struct item *new;
new = malloc(sizeof *new);
/* falta verificação se o malloc retornou NULL */
strcpy(new->ca.nome, "nome da criança");
new->ca.idade = 42; /* esta criança já por cá anda há muito tempo  */

... adiciona essa nova criança à lista

struct item *temp;
temp = inicio;
inicio = new;
new->next = temp;

Não te esqueças de libertar a memória quando já não precisares dela.

Happening · March 31, 2012 at 12:25 PM

Eu peço desculpa, estou a ser chato mas...

Primeiro tens de ter um objecto inicial fixo para o inicio da lista
Código ©: [seleccione]

struct item *inicio;

estás a criar uma nova estrutura???

e depois quando metes lá *new (na estrutura) o que estás a fazer? ?

Estás a dar mais um nome à struct?

Deixa lá eu hei-de ser criança até à cova 😁

bsccara · March 31, 2012 at 01:54 PM

Eu peço desculpa, estou a ser chato mas...

estás a criar uma nova estrutura???

e depois quando metes lá *new (na estrutura) o que estás a fazer? ?

Estás a dar mais um nome à struct?

Não estás a perceber; considera a linha no código do pmg:

struct item *new;

Quando tens um tipo ('struct item') seguido dum nome ('new') estás a dizer ao compilador que queres reservar espaço em memória para uma variável do tipo indicado. O compilador vai arranjar um sítio para guardar essa variável mas não vai inicializa-la.

Quando entre o tipo e o nome tens um * estás a dizer ao compilador que queres reservar espaço para um ponteiro para uma variável do tipo indicado, que mais tarde irás inicializar (o ponteiro e a variável). Logo a variável 'new' é um ponteiro para uma variável (ainda não criada) do tipo 'struct item'.

A linha

new = malloc(sizeof *new);

vai reservar espaço na memória ('heap') para um bloco com o tamanho da variável apontada pelo ponteiro 'new' (é isso que significa o * antes de 'new'; sem ele iria ser reservado espaço para o ponteiro). O ponteiro para esse bloco alocado é gravado na variável 'new', permitindo o acesso à variável do tipo 'struct item', que agora existirá no bloco alocado, através do ponteiro 'new'.

Happening · March 31, 2012 at 03:21 PM

hmmm acho que já estou a perceber. Então o apontador que criamos dentro da estrutura item, que é para a próxima posição na lista não é o mesmo que o *new correcto?

O new vai apontar para a lista e o *proximo vai apontar para a proxima posição é isso? 😉

Alguem tem exercícios disto com ordem crescente de dificuldade para eu ir treinando?

pmg · March 31, 2012 at 04:40 PM

Alguem tem exercícios disto com ordem crescente de dificuldade para eu ir treinando?

Exercicio #1:

dada uma lista de números inteiros (de no máximo 4 digitos) separados por espaços e/ou newlines (a lista é apresentada ao programa no stdin) executar as operações:

quando o número for positivo: guardá-lo

quando o número for negativo: se estiver guardado, esquecê-lo (em caso de vários números iguais guardados, esquecer o que foi guardado mais recentemente); se o número não estiver guardado, apresentar uma linha com a mensagem "Numero XXX inexistente" com o XXX sendo esse numero mas positivo.

quando a lista terminar, mostrar os números ainda guardados por ordem do mais recentemente guardado ao mais antigo.

Exemplo:

para uma lista contendo

1 2 3 2 -4 -2 -1

apresentar o output

Numero 4 inexistente
3 2

Não deixar memory leaks.

Podes assumir que os dados de input correspondem ao enunciado.

Happening · March 31, 2012 at 04:43 PM

Se este exercicio é dos faceis vou chumbar a prog2 xD

Mas vou resolve-lo. 😉

pikax · March 31, 2012 at 05:08 PM

O ca... era daquela variavel na struct xD

de qualquer maneira obrigado 😉

Tenho o livro de programação em C do Luis Damas ISBN 978-972-722-156-1 o livro até é bom mas não tem exercicios em que misture várias temáticas e não tem listas... Aconselham algum? 🙂

Já agora quando falamos de listas é o mesmo que falar de filas?? :0

Se quiseres um livro em portugues sobre isto, ve o Estruturas de Dados e Algoritmos em C - António Adrego da Rocha[i/], nao e' um livro excelente, mas ja te da' uma nocao de estruturas de dados e algoritmos.

Happening · April 28, 2012 at 01:48 PM

ora bem cá está o exercicio meio resolvido, não percebo pq é que nao funciona...

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

typedef struct{

int algarismo;
int *proximo;

}lista;


int main(){

int num;
lista *pointer, *temp;

printf("Introduza um número: ");
scanf("%d",& num);

while (num!=NULL){

	if(num>0){

		while(pointer->proximo!=NULL)
			pointer->proximo++;

		pointer = ((lista*) malloc(1*sizeof(pointer)));
		temp=pointer;

	if(pointer==NULL) 
	{
	perror("Não há espaço suficiente no disco.\n");
	exit(1);
	}
	pointer->algarismo=num;
	pointer->proximo=NULL;

}
	else if(num<0){

		while(pointer->proximo!=NULL){
			pointer->proximo++;

	if(pointer->algarismo==num) break;
		}

	pointer = (lista*) malloc(1*sizeof(pointer));

	if(pointer==NULL) 
	{
	perror("Não há espaço suficiente no disco.\n");
	exit(1);
	}
	pointer->algarismo=num;
	pointer->proximo=NULL;
	printf("Elemento %d inexistente.\n", -num);
	}
}

while(pointer->proximo!=NULL){

	pointer->proximo++;
}

while(pointer!=temp){

printf("%d, ", pointer->algarismo);
pointer->proximo--;

}


system("pause");
	}

pmg · April 28, 2012 at 02:15 PM

não percebo pq é que nao funciona...
/* ... */
int main(){
lista *pointer;
/*  */
while(pointer->proximo!=NULL)

BANG!

A variavel pointer nao foi atribuida nenhum valor. Nao se pode aceder ao objecto para o qual ela aponta...

Happening · April 28, 2012 at 02:19 PM

Então é só por o pointer a apontar para um valor???

HappyHippyHippo · April 28, 2012 at 02:33 PM

        int num;
...
        while (num!=NULL){
        }

1º - apesar de o compilador comer (e queixar-se) de que estás a comparar um valor numérico a uma referência de memória, a comparação do while deveria ser a um inteiro (tipo de dados da variável num)

2º - não existe qualquer tipo de atribuição ao valor num dentro do ciclo ... logo nunca acaba se o valor de num for diferente de zero !!!!

Sign In

Listas

Recommended Posts

Happening

HappyHippyHippo

pmg

Happening

pmg

Happening

bsccara

mundo

Happening

pmg

Happening

bsccara

Happening

pmg

Happening

pikax

Happening

pmg

Happening

HappyHippyHippo

Create an account or sign in to comment

Create an account

Sign in

Home

Activity

Revista PROGRAMAR

Important Information