Listas encadeadas [RESOLVIDO]

ic0158040
(usa KUbuntu)

Enviado em 03/10/2008 - 18:14h

Galera, implementei um códio de teste para uma lista encadeada estática, mas está dando segmentation fault.
Aguém consegue descobrir o erro do meu código?


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

#define TAM 100



struct No{
char info[30] ;
int prox ;
}typedef No ;

struct Lista{
No Dados[TAM] ;
int Dispo ;
int Prim ;
}typedef Lista ;


void inicializaLista(Lista &L) {
int i=0 ;
for (i=0; i<TAM; i++) {
L.Dados[i].prox = i+1 ;
}
L.Prim = -1 ;
L.Dispo = 0 ;
L.Dados[TAM-1].prox = -1 ;
}


bool insereNo(Lista &L, char* palavra) {
int i = L.Prim;
int ant = -1 ;
int aux ;

if (L.Prim == -1){
L.Dispo = L.Prim ;
L.Dados[L.Prim].prox = (L.Dispo)+1 ;

strcpy(L.Dados[L.Dispo].info, palavra);
L.Dispo = L.Dados[L.Prim].prox ;
}

while ((L.Dados[i].prox!= -1)&&(strcmp(L.Dados[i].info, palavra) < 0)){
ant = i ;
i = L.Dados[i].prox ;
}
aux = L.Dados[L.Dispo].prox;
L.Dados[ant].prox = L.Dispo ;


strcpy(L.Dados[L.Dispo].info, palavra);
L.Dados[L.Dispo].prox = i ;
L.Dispo = aux ;
return true ;

if (L.Dados[i].prox == -1) return false ;
}

bool removeNo(Lista &L, char* pal) {
int i = L.Prim ;
int ant = -1;
if (L.Prim == -1) return false ;
while ((L.Dados[i].prox != -1)&&(strcmp(L.Dados[i].info, pal) != 0)) {
ant = i;
i = L.Dados[i].prox ;
}
if (L.Dados[i].prox != -1 ) {
L.Dados[ant].prox = L.Dados[i].prox ;
L.Dados[i].prox = L.Dispo ;
L.Dispo = i ;
return true ;
}
return false ;
}

bool imprimeLista (Lista &l) {
int i=l.Prim ;
int j = l.Dados[i].prox ;
if(i != -1) {
printf(l.Dados[i].info) ;
while(j!=-1 ){
printf(l.Dados[j].info) ;
}
}
return false;
}



int main() {
char*palavra;
palavra = (char*)malloc(30*sizeof(char));
Lista teste ;
inicializaLista(teste);
printf("\nDigite uma palavra para ser inserida na lista:\t") ;
gets(palavra) ;
insereNo(teste, palavra) ;
printf("\nDigite a palavra que deseja remover:\t") ;
gets(palavra) ;
removeNo(teste, palavra) ;
free(palavra) ;
return 0 ;
}


vlw!

gallois
(usa Debian)

Enviado em 03/10/2008 - 18:39h

sei que não é a pergunta mas vou dando algumas dicas ;)
NUNCA faça cast em malloc(), você suprime erros do compilador que podem te ajudar a debugar o código.

NUNCA, NUNCA, NUNCA use gets(), talvez o seu erro esteja aí! gets não te oferece oportunidade de tratar buffer overflows. prefira fgets() ou outra!

antes de usar free() em algum ponteiro, você deve conferir se ele está apontando para algum lugar, e é aconselhável apontá-lo para NULL sempre que liberar a memória dele

quanto à lista em si. tem muita coisa ali que não tá correta, tem tipos que não existem, sua inicialização da lista não está feita corretamente (de uma olhada em ponteiros, passagem de parâmetros, etc). o código nem compilou aqui. qual compilador você usou?

f_Candido
(usa Ubuntu)

Enviado em 03/10/2008 - 21:53h

Olá,
Nunca é uma palavra muito forte, principalmente em programação. Mesmo que ele não saiba, mas o cast se faz necessário para explicitar o tipo de retorno. Em seguida, você informa todo o seu código em C, mas encontramos palavras reservadas da linguagem C++: bool. Bom, por enquanto é só.


Abraços

ic0158040
(usa KUbuntu)

Enviado em 04/10/2008 - 08:40h

sim sim, o cast se faz necessário pois malloc, por padrão volta um ponteiro para void, diferentemente do new que já faz a conversão. o free também se faz necessário, pois quando dou malloc eu tiro a responsabilidade do compilador de liberar a memória, passando-a para mim. sem o free o programa irá ficar sugando memória do meu pc.

quanto a eu escrever todo o código em c, mas utilizar o tipo bool, nativo de c++ se resolveu quando eu salvei o código como .cpp. A linguagem c está incorporada na c++.

bem... a introdução da minha lista não está errada também não, creio eu.





já o lance do gets para mim é novidade. o próprio compilador (G++) já tinha me dado uma waring sobre isso, mas não entendo, a fundo, qual o problema.

caso vocês possam apontar os erros na minha lista, a gente pode discutir e tentar resolver.

tentarei o lance do gets();

valeu!

mslomp
(usa Slackware)

Enviado em 04/10/2008 - 13:25h

o problema aqui nem está no gets(). o problema é que ao passar para a função insereNo a variável palavra (que está na a heap por ter sido alocada através de malloc) como argumento e lá dentro realizar operações de ponteiro entre ela e alguma variável que não esteja na mesma seção (heap), você está tentando cruzar a fronteira entre as diferentes áreas de memória do seu processo, e isso é inválido. L.Dados[L.Dispo].info não está na heap, portanto você não pode utilizar funções de string diretamente entre ela e palavra. ao retornar, palavra terá tentado atravessar a fronteira e retornará apontando para null. e quando for reutilizá-la, já viu...
a solução para isso, além de resolver o problema, economizará uma chamada externa à libc:

troque essa linha (em insereNo):
strcpy(L.Dados[L.Dispo].info, palavra);
por:
*L.Dados[L.Dispo].info = *palavra;

as duas sentenças produzem o mesmo resultado, porém apesar de parecer que estamos então trocando seis por meia dúzia, internamente são operações diferentes. strcpy copiará por incremento de índice (operação não permitida nesse caso), e a cópia simples por pura cópia crua de bloco de dados, sem importar-se com bases, índices e ponteiros.

outra boa prática é passar cadeias de caracteres que não retornarão modificadas como "const char*". evita pequenos bugs difíceis de depurar.

quanto a gets(), use-a sim, justamente para compreender o porquê não se deve usá-la. se apenas disserem "nao use isso, não faça aquilo" e você apenas aceitar, estará desperdiçando uma ótima chance de aprender algo diferente.

ic0158040
(usa KUbuntu)

Enviado em 05/10/2008 - 10:28h

fiz isso que me disse. utilizei também a função gets, para ver o que acontecia.

de principio não adiantou nada.
mas me deu uma luz para descobrir onde estava o problema (não fiz a função imprimir, mas não dá mais falha de segmentação) acho que está tudo ok.

o que eu fiz foi não mais alocar palavra usando malloc, mas com a notação de vetor fiz palavra[30] ;
daí funfou.

quando eu faço *p = *q , o que acontece? eu não entendi direito. pensei que o ponteiro que apontava para a posição p passaria a apontar para a posição q, mas não é isso?

vlw abs.

gallois
(usa Debian)

Enviado em 05/10/2008 - 10:44h

cast em malloc DEVE ser evitado sim, C99 prevê o tipo de retorno do malloc como void * e já trata a conversão. fazer um cast suprime mensagens do compilador e deve, portanto, ser evitado.

o free É necessário, mas antes de usar, você deve conferir se o ponteiro aponta para algum lugar, senão, seg fault

if (ptr) {
free(ptr)
}

se você não usar, ao fechar o programa, o SO libera a memória. a não ser que seu programa vá rodar indefinidamente (ou por muito tempo), não há com o que se preocupar. mas de uma maneira ou de outra, você deve liberar toda memória que alocar. boas práticas.

quer saber mais sobre o porque não usar o gets?
info libc
procure por gets()
lá vai te dizer direitinho
use info libc para tudo. lá tem muita coisa importante.
lembre-se que o fgets nao elimina o newline character no final da string, você vai ter q tratar isso, implemente alguma função do tipo dump_line, referência?
http://www.drpaulcarter.com/cs/common-c-errors.php#4.3

ta ae!

ic0158040
(usa KUbuntu)

Enviado em 05/10/2008 - 11:10h

mas basta usar o malloc como se eu estivesse usando o new?

tipo...
ao invés de:

palavra = (char*)malloc(50*sizeof(char)) ;

eu fizer:

palavra = malloc(50*sizeof(char)) ;

???????

gallois
(usa Debian)

Enviado em 05/10/2008 - 11:27h

cara, não entendo NADA de c++, então não sei ao certo se é igual ao new...
mas fica desse jeito mesmo que você colocou =]

mslomp
(usa Slackware)

Enviado em 05/10/2008 - 12:21h

quanto ao cast, o problema é o seguinte. como disse o colega aí em cima, o c99 define uma extensão para o tratamento dos void* para C, mas isso não está presente no C++. como seu código está meio "híbrido", misturando C e C++ e precisa ser compilado como C++, vai receber um erro de conversão inválida. aí nesse caso, a menos que você ajeite o código para C, vai precisar desse cast.

quando você faz:
char palavra[30];
está criando estaticamente uma variável não inicializada de tamanho 30*sizeof(char), e o linker a colocará em .bss, que é um dos segmentos de dados do seu executável (elf nesse caso). então você acessa o seu ponteiro através de &palavra.

quando faz:
char* palavra = new char[30];
está criando a variável dinamicamente do mesmo modo que malloc faz, apenas usando uma abordagem diferente.
o linker colocará uma dword (usualmente 4 bytes) em .bss, que apenas conterá o endereço para o conteúdo de palavra e reservará 30 bytes na heap para o esse conteúdo.
a partir daí, quando você tenta, por exemplo, copiar o conteúdo de uma string para palavra, deve cuidar para não acabar copiando-a para aquela dword que citei acima, mas sim para o local para onde essa dword aponta.
e nesse caso, ao usar strcpy e derivados, acabará acontecendo essa tragédia.

diferença entre strcpy e *p=*q:
strcpy realiza uma operação byte a byte através dos endereços das cadeias de caracteres. algo mais ou menos assim:
aponta para o início (endereço) da 1a string;
aponta para o início (endereço) da 2a string;
copia 1 byte (conteúdo) da fonte para o destino;
incrementa o índice de ambas;
verifica se é o caractere nulo (\ 0);
se sim, o copia e retorna;
se não, copia o conteúdo;
incrementa os índices;
...
e assim vai, em loop.

quando você faz *p, está fazendo uma derreferência. a grosso modo, é como se trabalhasse com uma variável "normal", como char p, e não um ponteiro. sendo assim, *p = *q atribui ao conteúdo de p o conteúdo de q.
para *p = *q, sendo ambos uma cadeia de caracteres e sabendo-se que q tem tamanho 30, desconsiderando o alinhamento para fins práticos, serão copiados os 30 bytes (ou menos, caso haja um \ 0 no meio do caminho) do conteúdo de q para p, a partir da base de p. internamente isso também envolve os endereços das variáveis, mas há o cuidado de não se cruzar a fronteira (já que envolvem segmentos diferentes) de modo ilegal, tratando do conteúdo e não de seus endereços em si, que só entraram em jogo para localizá-las.

numa analogia boba, é como chegar do méxico para os eua através da alfândega ou do deserto. pela alfângdega, desde que esteja tudo ok, você entra. se for pelo deserto e te pegarem, por mais que não esteja mal intencionado, com certeza a polícia te dará um "segmentation fault".

gallois
(usa Debian)

Enviado em 05/10/2008 - 16:10h

"numa analogia boba, é como chegar do méxico para os eua através da alfândega ou do deserto. pela alfângdega, desde que esteja tudo ok, você entra. se for pelo deserto e te pegarem, por mais que não esteja mal intencionado, com certeza a polícia te dará um "segmentation fault"."

perfeita analogia!!! aeuhaeuhae

mslomp
(usa Slackware)

Enviado em 05/10/2008 - 19:51h

"... com certeza a polícia te dará um "segmentation fault""
eheheh... pior é que esse nem com gdb se resolve...