Pagina 1 di 2 1 2 ultimoultimo
Visualizzazione dei risultati da 1 a 10 su 15
  1. #1
    Utente di HTML.it
    Registrato dal
    Apr 2010
    Messaggi
    99

    [C] unire 2 liste ordinate

    ciao a tutti, ho un problema con l'unire due liste ordinate in una sola lista ordinata
    dovrei farlo con una funzione merge che prenda in input i puntatori al primo nodo delle due liste e restituisca il puntatore al primo nodo della lista unita.
    Ho provato a farlo ma mi sono solo che incasinato con i puntatori, come un gatto si incasina con un filo di lana
    Qui vi posto la mia funzione merge, facendo il debugging esce la dove ho segnato in rosso, dice che non può accedere all'indirizzo di memoria :/
    qualcuno potrebbe darmi una mano o qualche spiegazione in merito perfavore? grazie in anticipo!
    codice:
    List1Ptr merge(List1Ptr *s1Ptr, List1Ptr *s2Ptr)
    {
    	List1Ptr firstPtr;
    	List1Ptr secPtr;
    	List1Ptr newPtr;
    	List1Ptr currPtr;
    	List1Ptr prevPtr;
    	newPtr=malloc(sizeof(List));
    	firstPtr=*s1Ptr;
    	secPtr=*s2Ptr;
    	currPtr=newPtr;
    	while(firstPtr!=NULL){
    		if(firstPtr->i > secPtr->i){
    			currPtr->i=secPtr->i;   
    			currPtr=currPtr->nextPtr;
    			currPtr->i=firstPtr->i;
    			secPtr=secPtr->nextPtr;
    			firstPtr=firstPtr->nextPtr;
    			currPtr=currPtr->nextPtr;
    		}
    		else{
    			currPtr->i=firstPtr->i;
    			currPtr=currPtr->nextPtr;
    			currPtr->i=secPtr->i; 
    			secPtr=secPtr->nextPtr;
    			firstPtr=firstPtr->nextPtr;
    			currPtr=currPtr->nextPtr;
    		}
    	}
    	return newPtr;
    }

  2. #2
    Utente di HTML.it
    Registrato dal
    Apr 2010
    Messaggi
    99
    nessuno proprio?

  3. #3
    Come è definito List1Ptr?
    Amaro C++, il gusto pieno dell'undefined behavior.

  4. #4
    Utente di HTML.it
    Registrato dal
    Apr 2010
    Messaggi
    99
    codice:
    #include<stdio.h>
    struct list{
    	int i;
    	struct list *nextPtr;
    };
    typedef struct list List;
    typedef List *List1Ptr;
    questa è la struttura,
    codice:
    int main(void)
    {
    	List1Ptr start1Ptr=NULL;
    	List1Ptr start2Ptr=NULL;
    	List1Ptr start3Ptr=NULL;
    	int i;
    	for(i=0;i<20;i++){
    		if(i%2==0){
    			insert(&start1Ptr,i);
    		}
    		else insert(&start2Ptr,i);
    	}
    	printL(start1Ptr);
    	printL(start2Ptr);
    	start3Ptr=merge(&start1Ptr,&start2Ptr);
    	printL(start3Ptr);
    	return 0;
    }
    questo invece è la main

  5. #5
    Nella merge non stai verificando se secPtr !=NULL, e anche il caso in cui firstPtr è uguale a NULL non è gestito correttamente.
    Devi modificare il codice per cui dal while si esce solo se entrambi i puntatori sono NULL, e la scelta del nodo da copiare valuta, prima ancora dell'ordine tra i due elementi, se uno dei due è NULL (ovvero, se è finita una delle due liste, necessariamente si prendono gli elementi dall'altra).
    Amaro C++, il gusto pieno dell'undefined behavior.

  6. #6
    Utente di HTML.it
    Registrato dal
    Apr 2010
    Messaggi
    99
    Originariamente inviato da MItaly
    Nella merge non stai verificando se secPtr !=NULL, e anche il caso in cui firstPtr è uguale a NULL non è gestito correttamente.
    Devi modificare il codice per cui dal while si esce solo se entrambi i puntatori sono NULL, e la scelta del nodo da copiare valuta, prima ancora dell'ordine tra i due elementi, se uno dei due è NULL (ovvero, se è finita una delle due liste, necessariamente si prendono gli elementi dall'altra).
    Come hai suggerito ho messo nella condizione del while anche che secPtr!=NULL e poi ho aggiunto i casi che una lista o l'altra sono vuote, ma il problema rimane sempre lì, dove ho segnato in rosso.
    Apparentemente secPtr non è NULL, e se inverto firstPtr con secPtr il problema sarà su firstPtr, quindi penso che si blocchi perchè currPtr non passa a currPtr->nextPtr

  7. #7
    Posta il codice modificato.
    Amaro C++, il gusto pieno dell'undefined behavior.

  8. #8
    Utente di HTML.it
    Registrato dal
    Apr 2010
    Messaggi
    99
    eccolo qua per intero:
    codice:
    #include<stdio.h>
    struct list{
    	int i;
    	struct list *nextPtr;
    };
    typedef struct list List;
    typedef List *List1Ptr;
    void insert(List1Ptr *sPtr, int val);
    void printL(List1Ptr currPtr);
    List1Ptr merge(List1Ptr *s1Ptr, List1Ptr *s2Ptr);
    int main(void)
    {
    	List1Ptr start1Ptr=NULL;
    	List1Ptr start2Ptr=NULL;
    	List1Ptr start3Ptr=NULL;
    	int i;
    	for(i=0;i<20;i++){
    		if(i%2==0){
    			insert(&start1Ptr,i);
    		}
    		else insert(&start2Ptr,i);
    	}
    	printL(start1Ptr);
    	printL(start2Ptr);
    	start3Ptr=merge(&start1Ptr,&start2Ptr);
    	printL(start3Ptr);
    	return 0;
    }
    void insert(List1Ptr *sPtr, int val)
    {
    	List1Ptr newPtr;
    	List1Ptr prevPtr;
    	List1Ptr currPtr;
    	newPtr=malloc(sizeof(List));
    	if(newPtr!=NULL){
    		newPtr->i=val;
    		newPtr->nextPtr=NULL;
    		prevPtr=NULL;
    		currPtr=*sPtr;
    		while(currPtr!=NULL&&val>currPtr->i){
    			prevPtr=currPtr;
    			currPtr=currPtr->nextPtr;
    		}
    		if(prevPtr==NULL){
    			newPtr->nextPtr=*sPtr;
    			*sPtr=newPtr;
    		}
    		else{
    			prevPtr->nextPtr=newPtr;
    			newPtr->nextPtr=currPtr;
    		}
    	}
    	else{
    		printf("%d not inserted. No memory available.\n",val);
    	}
    }
    void printL(List1Ptr currPtr)
    {
    	if(currPtr==NULL){
    		printf("List is empty!\n");
    	}
    	else{
    		printf("The list is: \n" );
    		while(currPtr!=NULL){
    			printf("%d--> ", currPtr->i);
    			currPtr=currPtr->nextPtr;
    		}
    		printf("NULL\n\n");
    	}
    }
    List1Ptr merge(List1Ptr *s1Ptr, List1Ptr *s2Ptr)
    {
    	List1Ptr firstPtr;
    	List1Ptr secPtr;
    	List1Ptr newPtr;
    	List1Ptr currPtr;
    	List1Ptr prevPtr;
    	newPtr=malloc(sizeof(List));
    	firstPtr=*s1Ptr;
    	secPtr=*s2Ptr;
    	currPtr=newPtr;
    	if(firstPtr!=NULL&&secPtr!=NULL){
    		if(firstPtr->i > secPtr->i){
    			currPtr->i=secPtr->i;   
    			currPtr=currPtr->nextPtr;
    			currPtr->i=firstPtr->i;
    			secPtr=secPtr->nextPtr;
    			firstPtr=firstPtr->nextPtr;
    			currPtr=currPtr->nextPtr;
    		}
    		else{
    			currPtr->i=firstPtr->i;
    			currPtr=currPtr->nextPtr;
    			currPtr->i=secPtr->i; 
    			secPtr=secPtr->nextPtr;
    			firstPtr=firstPtr->nextPtr;
    			currPtr=currPtr->nextPtr;
    		}
    		if(firstPtr==NULL&&secPtr!=NULL){
    			currPtr->i=secPtr->i;
    			currPtr=currPtr->nextPtr;
    			secPtr=secPtr->nextPtr;
    		}
    		if(secPtr==NULL&&firstPtr!=NULL){
    			currPtr->i=firstPtr->i;
    			currPtr=currPtr->nextPtr;
    			firstPtr=firstPtr->nextPtr;
    		}
    	}
    	return newPtr;
    }

  9. #9
    Non hai corretto come ti dicevo... in primis, non dovevi sostituire l'if con un while, e la condizione è sbagliata: devi continuare anche se uno solo dei due è diverso da NULL (ovvero, devi continuare il merge anche se una delle due liste è finita, copiando solo il contenuto dell'altra).
    Inoltre, se uno dei due puntatori è NULL, devi evitare di raggiungere il confronto tra firstPtr->i e secPtr->i, altrimenti siamo da capo.

    Io farei semplicemente:
    codice:
        List1Ptr merge(List1Ptr *s1Ptr, List1Ptr *s2Ptr)
        {
            List1Ptr firstPtr=*s1Ptr;
            List1Ptr secPtr=*s2Ptr;
            List l;
            List1Ptr currPtr=&l;
            while(firstPtr!=NULL || secPtr!=NULL)
            {
                if(secPtr==NULL || firstPtr->i < secPtr->i)
                {
                    currPtr->nextPtr=firstPtr;
                    currPtr=firstPtr;
                    firstPtr=firstPtr->nextPtr;
                    currPtr->nextPtr=NULL;
                }
                else
                {
                    currPtr->nextPtr=secPtr;
                    currPtr=secPtr;
                    secPtr=secPtr->nextPtr;
                    currPtr->nextPtr=NULL
                }
            }
            return l.nextPtr;
        }
    Amaro C++, il gusto pieno dell'undefined behavior.

  10. #10
    Utente di HTML.it
    Registrato dal
    Apr 2010
    Messaggi
    99
    Si il while lo avevo sostituito con l'if per fare una prova poi mi sono dimenticato di rimetterlo.

    Anche la funzione scritta da te non mi funziona, mi si blocca al primo if dove c'è firstPtr->i e dice "cannot access memory at address 0x0"
    cioè anche se non ci fossero i while e gli if, e la funzione semplicemente immettesse i valori nella lista non entrerebbero :/


    come non detto
    se tolgo tutti i while e dico solo di inserire i valori singolarmente li inserisce

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.