C++ Pointer Probleme?

Michael Smith

Guten Tag!
Ich hänge schon einige Tage an einer verketteten Liste, die mithilfe eines Selection Sorts eine Zahlenmenge richtig sortieren soll. Problem ist nun, dass mir vier Funktionen in der Ausführung nicht gefallen und ich nicht weiß, ob diese so korrekt ausgeführt sind. Die dazu verkettete Liste wurde uns zur Verfügung gestellt.

Die erste Funktion soll die Summe der Zahlen in der Liste bestimmen:

int sum(const LinkedList& list){
    int i,summe = 0;
    if(isEmpty())
        return 0;
    else
        while(list_at(i)!=nullptr){
            summe += list_at(i);
            i++;
        }
    return summe;
}

Eine Methode size(), die die Anzahl der Elemente in der verketteten Liste zurückliefert:

int LinkedList::list_size(struct LinkedList* head) const{
    if (head == NULL)
        return 0;
    return 1 + list_size(head->next);
}

Eine Methode at(), die als Parameter einen Index erhält und eine Kopie des Wertes an der entsprechende Stelle der verketteten Liste an den Aufrufer zurückgibt:

int LinkedList::list_at(int i) const{
    int counter = 0;
    ListElement* p=head;
        while ( i != counter){
            p=p->next;
            counter++;
        }
    return p;
}

und eine Methode sort(), die die Liste mit dem Sortieren durch den Selection Sort aufsteigend sortiert:

void LinkedList::list_sort(LinkedList *l){
    LinkedList **curElPtr =&(l->first);
    LinkedList *smallest = Null:
    while(*curElPtr){
        smallest -> next =*curElPtr;
        *curElPtr = smallest;
        curElPtr =&(smallest->next);
    }
    l->last = smallest;
}

Am unsichersten bin ich mir dabei in der letzten Funktion, da ich noch Probleme mit den Pointern habe.

Vielen Dank euch !
Mfg. Michael

Zhavok

Sollst du das von der Uni/Schule aus so machen oder willst du C++ lernen?

mgaeckler

Die freie Funktion sum verwendet Ihren Parameter nicht. Wie sollen also die freien Funktionen isEmpty und list_at ein vernünftiges Ergebnis lieferen?

Durch eine verkettete List über einen Index zu iterieren, ist ein Performanzkiller und nicht Zweck einer Liste. Dafür gibt es Arrays und Vektoren.

LinkedList::list_size mag zwar rekursiv funktionieren, ist aber ebenfalls Performanzmässig ein Graus. Auch könnte bei großen Listen der Stack zu klein werden. Implementiere es iterativ.

LinkedList::list_at sollte eigentlich nicht notwendig sein, außerdem sollte das schon Dein Compiler ablehnen.

LinkedList::list_sort habe ich mir jetzt nicht angeschaut. Sieht auf dem ersten Blick aber schräg aus.

VG Martin

Jockelx

@mgaeckler sagte in C++ Pointer Probleme?:

LinkedList::list_sort habe ich mir jetzt nicht angeschaut. Sieht auf dem ersten Blick aber schräg aus.

Jupp, Sortierfunktion ohne irgendwo einen Vergleich zu machen ist in der Tat schräg.
@Michael-Smith Wo siehst du da einen selection-sort?

wob

@mgaeckler sagte in C++ Pointer Probleme?:

LinkedList::list_size mag zwar rekursiv funktionieren, ist aber ebenfalls Performanzmässig ein Graus. Auch könnte bei großen Listen der Stack zu klein werden. Implementiere es iterativ.

Noch dazu: warum wird hier eine LinkedList* übergeben? Die Liste sollte doch selbst wissen, wie groß sie ist? Und wieso ist "head" hier eine LinkedList und nicht ein ListElement?

Außerdem wäre spannend zu wissen, was die dir zur Verfügung gestellte Liste denn so alles kann.

Fragen über Fragen.

Michael Smith

@mgaeckler Alles klar, vielen Dank schonmal! Ich habe die Funktionen erstmal abgeändert und die at Funktionen weggelassen

Zu dem Sotieralgorithmus habe ich mir jetzt folgendes zusammengestellt:

struct node
{
 int data;
 struct node *next;
};

struct node *head,*head1;

void Selection_sort()
 {
  struct node *t,*t1,*t2,*t3;
  t1 = head;
  head1 = head;
  if(head == NULL)
    cout << "Die Liste ist leer" ;
  else
  {
    while( (t2 = t1 -> next)  !=  NULL)
    {
      while(t2 != NULL)
      {
        t3 = t2 -> next;
        if( t1 -> data   >   t2 -> data)
        {
          t2 -> next = t1;
          for(t = t1; t -> next != t2;t = t -> next);
          t -> next = t3;
          t1 = t2; 
          t2 = t3; 
        } 
        else
        {
          t2 = t3;
        }
      } 

      if(head == head1) 
      {               
       head = t1;
       head1 = t1 -> next;
      }  
      else
      {
        for(t = head;t -> next != head1; t = t -> next);
        t -> next = t1;
        head1 = t1 -> next;
      } 
      t1 = t1 -> next;
    } 
  }
}

Oder verwechsele ich das gerade mit einem anderen Sortieralgorithmus?

Michael Smith

@wob Ah ja, das ist mein Fehler!
Die implementierten Methoden sind: ausgeben, erstes Element löschen, finden, anhängen, und isEmpty.