Merge λιστών

Re4cTiV3 · 6 Ιουνίου 2012

Θέλω να κάνω merge δυο ταξινομημένες λίστες και το αποτέλεσμα να βγαίνει σε μια τρίτη λίστα.Θέλω να γίνει αποκλειστικά με pointers και χωρίς να γίνει malloc() στην τρίτη.

Το μόνο που έχω καταφέρει είναι αυτό.

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

struct listNode{
      int data;
      struct listNode *nextPtr;
};

typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;

void insert(ListNodePtr *,int value);
void printList(ListNodePtr );
void mergeList(ListNodePtr *, ListNodePtr *, ListNodePtr *);

int main() {
   
   ListNodePtr list1 = NULL;
   ListNodePtr list2 = NULL;
   
   srand(time(NULL));
   int i;
   for(i=0;i<3;i++) {
       insert(&list1,rand()%10);
       insert(&list2,rand()%10);
   }
   insert(&list1,rand()%10);
   insert(&list1,rand()%10);
   printf("============ ARXIKES ==================\n");
   printList(list1);
   printList(list2);
   printf("========================================\n\n");
   ListNodePtr list3 = NULL;
   
   mergeList(&list1,&list2,&list3);
   
   printList(list1);
   printList(list2);
   printList(list3);
   
system("pause");
return 1;   
}

void insert(ListNodePtr *sPtr,int value)
{
   ListNodePtr previousPtr,currentPtr,newPtr;
   newPtr = (ListNodePtr)malloc(sizeof(ListNode));
   
   if(newPtr != NULL) 
   {
       newPtr->data = value;
       newPtr->nextPtr = NULL;
       previousPtr = NULL;
       currentPtr = *sPtr;
       
       while(currentPtr != NULL && value > currentPtr->data)
       {
           previousPtr = currentPtr;
           currentPtr = currentPtr->nextPtr;
       }
       
       if(previousPtr == NULL)
       {
           newPtr->nextPtr = *sPtr;
           *sPtr = newPtr;
       }
       else 
       {
           previousPtr->nextPtr = newPtr;
           newPtr->nextPtr = currentPtr;
       }
   }
}



void printList(ListNodePtr head) {
    while(head != NULL) {
               printf("%d-->",head->data);
               head = head->nextPtr;
    }
    printf("NULL\n\n");
}
                   
void mergeList(ListNodePtr *list1,ListNodePtr *list2,ListNodePtr *final)
{
    ListNodePtr cur = (ListNodePtr)malloc(sizeof(ListNode));
    ListNodePtr temp = cur;
    
    while(*list1 != NULL && *list2 != NULL)
    {

        if( (*list1)->data < (*list2)->data )
        {
            cur->nextPtr = *list1;
            *list1 = (*list1)->nextPtr;
        }
        else
        {
            cur->nextPtr = *list2;
            *list2 = (*list2)->nextPtr;
        }
        cur = cur->nextPtr;
    }

    
    if(*list2 == NULL) { cur->nextPtr = *list1; }
    if(*list1 == NULL) { cur->nextPtr = *list2; }
    
   // temp = temp->nextPtr;
    
    *final = temp;
}

Αυτό όμως λειτουργεί όμως έχει και memory leak μιας θέσης και οι δυο λίστες δεν γίνονται NULL. :/

Downloadpercent · 6 Ιουνίου 2012

Sorry, αλλά δεν μπορώ να σου δώσω τον κώδικα γιατί είναι θέμα σεβασμού ως προς τον καθηγητή, ουσιαστικά αυτός μας έδωσε αρκετή βοήθεια και αμα τον δώσω κατευθείαν θα είναι φουστιά.

μπορώ μόνο να δώσω τον σκελετό, και μερικές πληροφορίες.

>
void SLList_Merge(TSLList **L1, TSLList **L2)
{
TSLList *Prev, *Curr, *Temp;

if (*L1 == NULL) 
{
	*L1 = *L2;
	*L2 = NULL;
}
if (*L2 == NULL)
	return;

Prev = NULL;
Curr = *L1;
Temp = *L2;

while((Curr != NULL) && (Temp != NULL))
{
	while(Curr != NULL && Curr->Item < Temp->Item)
	{
		Prev = Curr;
		Curr = Curr->Next;
	}
	if (Prev == NULL)
		*L1 = Temp;
	else
		Prev->Next = Temp;
		
	// Here you must do linking, its easy to find it 		
	// There are only 4 lines

}
if (Curr == NULL) 
{
	Prev->Next = *L2;
	*L2 = NULL;
}

}

* Να ξεκαθαρίσω ότι ο κώδικας που είχα ανεβάσει ήταν ο σκελετός του προγράμματος με μερικά σχόλια για το πως θα υλοποιηθεί, πιστεύω ότι για κάποιον με ελάχιστες γνώσεις ήταν πολύ εύκολο να το καταλάβει και ουσιαστικά ήταν σαν να έδινα το πρόγραμμα απ' ευθείας.

*EDITET:Ο κορμός του κώδικα είναι ON, πραγματικά είναι ένας πολύ καλός κώδικας καλά μελετημένος, απλά θα πρέπει να το προσπαθήσετε λίγο και να το βγάλετε μόνη σας.

Επεξ/σία 8 Ιουνίου 2012 από Downloadpercent

Re4cTiV3 · 6 Ιουνίου 2012

Φαινεται πολυ πιο complicate με δυο while..Σε μια λιστα ειναι πιο ευκολο καθως κανεις συνεχεια next. σε αυτην και αν "τελειωσει" η λιστα κανεις link τον τελευταιο κομβο με το top της αλλης.

Αποστολή από το GT-I9000 με τη χρήση Insomnia App

Downloadpercent · 6 Ιουνίου 2012

Φαινεται πολυ πιο complicate με δυο while..Σε μια λιστα ειναι πιο ευκολο καθως κανεις συνεχεια next. σε αυτην και αν "τελειωσει" η λιστα κανεις link τον τελευταιο κομβο με το top της αλλης.

Αποστολή από το GT-I9000 με τη χρήση Insomnia App

Ουσιαστικά το 2ο while είναι για να μετακινήσεις τους δείκτες της 2ης λίστας.

Αν μιλάμε για ταξινομημένες λίστες τότε το ότι έχεις while σε while δεν σημαίνει ότι διπλασιάζετε η δουλειά-αγκαρία.

Επεξ/σία 6 Ιουνίου 2012 από Downloadpercent

defacer · 6 Ιουνίου 2012

Μπορεί να γίνει και πολύ απλούστερα

Ας πούμε να πηγαίνει κάπως ως εξής:

>if (!*L1 && !*L2) {
   return 0;
}
if (!*L2) {
   return L1; // προφανώς παραμένει sorted, η L2 είναι άδεια
}
if (!*L1) {
   return L2; // προφανώς παραμένει sorted, η L1 είναι άδεια
}

// επιλογή της λίστας με το μικρότερο πρώτο item σαν λίστας αποτελέσματος
TSLList **out = (*L1)->item < (*L2)->item ? L1 : L2;

while(*L1 || *L2) {
   TSLList **pick = (!*L2 || (*L1)->item < (*L2)->item) ? L1 : L2;

   if (pick == out) {
       // Το επόμενο μικρότερο item είναι στη λίστα την οποία έχουμε
       // επιλέξει ως out, οπότε δε χρειάζεται να κάνουμε τίποτα απολύτως.
       // Άφησα το if μόνο και μόνο για να φαίνεται η λογική.
   }
   if (pick != out) {
       // Φέρε το item από την *pick στην *out
       *out->next = *pick;
       // προχώρα τον *pick για να "καταναλωθεί" το item που επεξεργαστήκαμε
       *pick = *pick->next;
   }

   // Έχουμε ακόμα ένα ταξινομημένο node στη θέση του, προχώρα τον *out για να περάσουμε στο επόμενο
   *out = *out->next;
}

// Σ' αυτό το σημείο το *out είναι το τελευταίο node είτε από τη μία λίστα είτε από
// την άλλη, και στις 2 περιπτώσεις *out->next == null επειδή έτσι ήταν τα πράγματα
// όταν κλήθηκε η merge. Επομένως και πάλι δε χρειάζεται να κάνουμε απολύτως τίποτα.

// Αφού δεν έχουμε στάνταρ "λίστα αποτελέσματος" πρέπει να επιστρέψουμε αυτήν που
// επιλέξαμε. Κάτι που καλό είναι να κάνουμε ακόμα κι αν είχαμε επιλέξει a priori
// μία από τις δύο λίστες στην τύχη.
return out;

Μπορεί να έχω κάνει κάποιο λαθάκι αλλά όπως και να 'χει η ιδέα φαίνεται.

@Downloadpercent: Τώρα μπορείς να καταλάβεις πιστεύω πόση χάρη μπορεί να υπάρχει σ' ένα πρόγραμμα. Να ξέρεις ότι δεν πρόκειται να σου τη δείξει κανένας ακαδημαϊκός -- θα πρέπει να την ανακαλύψεις μόνος σου.

migf1 · 6 Ιουνίου 2012

@defacer:

Έχασα λίγο το σημείο που αντιγράφονται οι υπόλοιποι κόμβοι της άλλης λίστας όταν τελειώσουν οι κόμβοι της L1 ή της L2. Επίσης, για να λειτουργεί το loop δεν πρέπει να κάνεις increment και τους δείκτες των L1 και L2;

defacer · 6 Ιουνίου 2012

Το loop δεν τελειώνει όσο είτε η *L1 είτε η *L2 έχει ακόμα nodes. Όταν μία από τις δύο τελειώσει τότε σε κάθε iteration το *pick θα είναι ίσο με την άλλη, οπότε θα συνεχίσει να αντιγράφει όσα στοιχεία έχουν περισσέψει μέχρι να τελειώσει και η δεύτερη λίστα (ή να μην κάνει τίποτα βασικά αν η λίστα που δεν τελείωσε είναι αυτή που έχεις επιλέξει σαν out).

Με την ευκαιρία εδώ υπάρχει δυνατότητα optimization γιατί απαξ και τελειώσει η μία λίστα τότε μπορείς να ολοκληρώσεις τη διαδικασία είτε με μία μόνο μετακίνηση αν pick != out είτε με καμία απολύτως αν pick == out, και δε χρειάζεται να μείνεις άλλο μέσα στο while. Πάντως πέραν του ότι δεν ασχολήθηκα νομίζω ότι ένα τέτοιο optimization θα τραβούσε την προσοχή του αναγνώστη από τον ίδιο τον αλγόριθμο, οπότε καλύτερα που δεν υπάρχει εδώ.

Τα increment που λες είναι το *pick = *pick->next και αντίστοιχα για το *out. Απλώς θέλει προσοχή ούτως ώστε όταν pick == out να μην κάνεις increment δύο φορές.

Γενικά το πράγμα θέλει προσοχή γιατί δουλεύεις και με list* και με list** (τόση προσοχή που φαντάζομαι ότι έχω κάνει λάθος κάπου ).

migf1 · 6 Ιουνίου 2012

Σόρυ που άργησα, αλλά πάλευα με τις ρυθμίσεις του VS2010 που μόλις ξανάβαλα για να του δώσω ακόμα μια ευκαιρία (τελικά μόλις το έβαλα να κάνει και πάλι... uninstall )

Έχεις δίκιο, εκ παραδρομής διάβασα το || ως &&. Όμως στη συνθήκη του while συγκρίνει τους *L1, *L2 τους οποίους δεν βλέπω να τους κάνεις increase μέσα στο loop (βασικά η σωστή λέξη είναι η "advance").

Η αλήθεια όμως είναι πως δεν έχω κοιτάξει διεξοδικά τον κώδικα, μια ανάγνωση του έκανα μόνο.

πάω να κάνω το restart που ζητάει το uninstallation

Downloadpercent · 6 Ιουνίου 2012

Μια ερώτηση χωρίς κακία,

γιατί οταν κάνει κάποιος ένα ποστ αμέσως κάποιος να κάνει reply τον κώδικα του και "καλα διορθωμένο"

ο καθένας έχει μάθει διάφορους τρόπους, και το μεν και το δεν σωστό είναι ...

@Downloadpercent: Τώρα μπορείς να καταλάβεις πιστεύω πόση χάρη μπορεί να υπάρχει σ' ένα πρόγραμμα. Να ξέρεις ότι δεν πρόκειται να σου τη δείξει κανένας ακαδημαϊκός -- θα πρέπει να την ανακαλύψεις μόνος σου.

φυσικά, αλλά υπάρχουν άτομα που δεν κάνουν απλά τη δουλειά τους. προσωπικά ο τυπάς που έχω είναι μια χαρά-σπαθί...

migf1 · 6 Ιουνίου 2012

Μια ερώτηση χωρίς κακία,

γιατί οταν κάνει κάποιος ένα ποστ αμέσως κάποιος να κάνει reply τον κώδικα του και "καλα διορθωμένο"

ο καθένας έχει μάθει διάφορους τρόπους, και το μεν και το δεν σωστό είναι ...

Αφενός διότι στα φόρουμ είναι από θεμιτή έως ζητούμενη η ποικιλία, και αφετέρου διότι στα δημοφιλή φόρουμ συμμετέχουν άνθρωποι με διαφορετικό βαθμό εμπειρίας που συνήθως σημαίνει διαφορετικό επίπεδο στάνταρ στα οποία έχουν συνηθίσει να προγραμματίζουν.

Downloadpercent · 6 Ιουνίου 2012

Συμφωνώ απόλυτα στο να βοηθάνε άτομα με εμπειρία, άλλα ότι κάποιος κάνει κάτι post το οποίο προέρχεται από άτομο επαγγελματία(δεν είμαι εγώ αυτός) και είναι καλά ελεγμένο τότε γιατί να ποστράρει κάποιος άλλος το δικό του απλά αλλάζοντας το

if (!(List1 == NULL))

σε if (!List1)

τεσπα, αν μπορείς Migf δώσε μου ένα Link σχετικά με αυτό πού έλεγες χτες για το ότι έχει διαφορά στον compiler το if(xyz == 0) με το if(0 == xyz)

θα ήθελα μερικές πληροφορίες, Thanks.

migf1 · 6 Ιουνίου 2012

Συμφωνώ απόλυτα στο να βοηθάνε άτομα με εμπειρία, άλλα ότι κάποιος κάνει κάτι post το οποίο προέρχεται από άτομο επαγγελματία(δεν είμαι εγώ αυτός) και είναι καλά ελεγμένο τότε γιατί να ποστράρει κάποιος άλλος το δικό του απλά αλλάζοντας το

if (!(List1 == NULL))

σε if (!List1)

Που συνέβη αυτό; Δεν έχει πέσει κάτι τέτοιο στην αντίληψή μου.

defacer · 6 Ιουνίου 2012

ο καθένας έχει μάθει διάφορους τρόπους, και το μεν και το δεν σωστό είναι ...

αλλά υπάρχουν άτομα που δεν κάνουν απλά τη δουλειά τους. προσωπικά ο τυπάς που έχω είναι μια χαρά-σπαθί...

Σίγουρα, και νομίζω όλοι μας έχουμε γνωρίσει τέτοιους καθηγητές. Αυτό που προσπαθώ να πω είναι ότι συνήθως δεν πρόκειται να δεις μια πραγματικά όμορφη λύση** από ακαδημαϊκό γιατί α) η δουλειά του είναι να γίνει κατανοητός σε όλους, όχι μάστορας στα μάτια των λίγων που μπορούν να ακολουθήσουν και β) αν ζητήσεις το ίδιο πράγμα από έναν ακαδημαϊκό κι από ένα μηχανικό αυτά που θα σου ετοιμάσουν δε θα έχουν καμία σχέση μεταξύ τους, του μηχανικού θα είναι κλάσεις ανώτερο (και για να είμαι δίκαιος: ο μηχανικός δε θα μπορούσε να έχει γίνει μηχανικός αν δεν υπήρχε ο ακαδημαϊκός).

** "Perfection is achieved not when there is nothing left to add, but when there is nothing left to take away” –– Antoine de Saint-Exupery (ναι, ο γνωστός), "Terre des Hommes"

Συμφωνώ απόλυτα στο να βοηθάνε άτομα με εμπειρία, άλλα ότι κάποιος κάνει κάτι post το οποίο προέρχεται από άτομο επαγγελματία(δεν είμαι εγώ αυτός) και είναι καλά ελεγμένο τότε γιατί να ποστράρει κάποιος άλλος το δικό του απλά αλλάζοντας το if (!(List1 == NULL)) σε if (!List1)

Ούτε εγώ κατάλαβα σε τι αναφέρεσαι.

migf1 · 6 Ιουνίου 2012

...

τεσπα, αν μπορείς Migf δώσε μου ένα Link σχετικά με αυτό πού έλεγες χτες για το ότι έχει διαφορά στον compiler το if(xyz == 0) με το if(0 == xyz)

θα ήθελα μερικές πληροφορίες, Thanks.

Έχει ήδη δώσει ένα link ο defacer, αλλά να και κάνα-δυο ακόμα (άμα γκουγκλάρεις θα βρεις πολλά)...

http://users.ece.cmu...ard.html#ifthen

http://stackoverflow...iable-null-in-c

Πάντως δεν υπάρχουν άλλες πληροφορίες πέρα από αυτές που έχουμε ήδη σχολιάσει εδώ στο φόρουμ.

EDIT:

Btw, για να γυρίσουμε και λίγο on-topic, ρίξτε μια ματιά εδώ: http://stackoverflow...wo-sorted-lists

Περιέχει μερικές πολύ καλές υλοποιήσεις

Re4cTiV3 · 6 Ιουνίου 2012

Και μια υλοποίηση που έκανα εγώ είναι αυτή:

>ListNodePtr mergeList(ListNodePtr *list1,ListNodePtr *list2)
{
   ListNodePtr temp = NULL, curr;
   insert(&temp, 0);
   curr = temp;
   
   while( ( (*list1) != NULL ) && ( (*list2) != NULL ) )
   {
       if( (*list1)->data <= (*list2)->data )
       {
           curr->nextPtr = *list1;
           *list1 = (*list1)->nextPtr;
       }
       else
       {
           curr->nextPtr = *list2;
           *list2 = (*list2)->nextPtr;
       }
       curr = curr->nextPtr;
   }
   
   if (*list1)
   {
       curr->nextPtr = *list1;
       *list1 = NULL;
   }
   else
   {
       curr->nextPtr = *list2;
       *list2 = NULL;
   }
   
   curr = temp;
   temp = temp->nextPtr;
   free(curr);
   
   return temp;
}

Και μπορώ να πω πως είναι πολύ απλή, απλά μένει να βάλεις στην αρχή τα if-statements..

Σύνδεση

Merge λιστών

Προτεινόμενες αναρτήσεις

Re4cTiV3

Downloadpercent

Re4cTiV3

Downloadpercent

defacer

migf1

defacer

migf1

Downloadpercent

migf1

Downloadpercent

migf1

defacer

migf1

Re4cTiV3

Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε

Δημιουργία λογαριασμού

Σύνδεση

Σύνδεση