Versucht, Probleme der verketteten Liste herauszufinden

Question

Ich habe eine harte Zeit versucht, Probleme mit diesem Programm herauszufinden. Jedes Mal, wenn ich es laufe, durchläuft es die dritte Iteration und stürzt einfach ab. Aus irgendeinem Grund kann ich den Rückgabevergleich nicht für die zweite Iteration durchführen. Die Schleife wird einmal durchlaufen, wenn die Schleife auf Null gesetzt wird, da topptr gleich b und botptr gleich a ist.

Answer 1

Diese Linie sieht sehr verdächtig:

while (topptr != temp || topptr -> next != temp) //reiterates until the list is the same as temp(empty) or if the next topptr(headptr) value is temp(singleton) 

temp eine temporäre Variable ist, die Sie für mehrere Zwecke verwenden (insbesondere nächsten Wert von topptr und das Element folgende botptr). Die Verwendung einer solchen Variablen für Vergleiche außerhalb des inneren Bereichs ist gefährlich.

Ich glaube, die Linie soll so sein:

while (topptr != botptr && botptr -> next != topptr) //iterates until topptr reaches botptr 

---

Außerdem schlage ich vor, dass Sie die temp Variable im Rahmen erklären, wo Sie es brauchen. Mit anderen Worten, entfernen Sie die Zeile

ListNode* temp = NULL; 

und ändern Sie die Zeile unter else if(botptr -> data == topptr -> data) zu

ListNode* temp = topptr; 

Answer 2

Da Sie ziemlich viel falsch zu machen ich eine längere Kritik geschrieben habe. Wenn Sie es befolgen, finden Sie auch, warum Ihr Programm nicht auf dem Weg funktioniert. Beginnen mit:

• Sie verwenden eine verkettete Liste, um eine Zeichenfolge darzustellen. Warum nicht std :: string verwenden? Es würde Ihnen erlauben, das Ganze viel einfacher zu implementieren.
• Sie speichern die Zeichenfolge in umgekehrter Reihenfolge. Nicht technisch falsch, aber Sie sind die erste Person, die ich traf, die Strings in umgekehrten Single-Linked-Listen speichert.
• Sie implementieren Ihre eigene verkettete Liste anstelle von std :: list.
• Sie verwenden eine einzelne verkettete Liste für einen Algorithmus, der wirklich bidirektionale Iteration benötigt.
• Sie bereinigen keine Ihrer Ressourcen. Es spielt hier keine Rolle, aber es ist eine gute Gewohnheit, wenn Sie größere Programme schreiben.

, dass aus dem Weg bekommen haben, die an der Quelle aussehen lassen:

#include <iostream> 
using namespace std; 

Diese Aussage ist verpönt: Why is "using namespace std" considered bad practice?

struct ListNode 
{ 
    char data; 
    ListNode *next; 
}*head = NULL, *nodeptr = NULL, *newNode = NULL; 

Hier global Sie drei Variablen erklären, dass konnte nur so leicht ein Teil von main sein. Versuchen Sie, den Gültigkeitsbereich jeder deklarierten Variablen zu minimieren.

Testen der Endbedingung für Pali wie dies ist richtig, aber umständlich. Sie könnten genauso gut für pali[i] testen.

{ 
     newNode = new ListNode; 
     newNode -> data = pali[i]; //places chars into a linked list 
     newNode -> next = head; 
     head = newNode;// links list together 
     nodeptr = head; 

So ist verknüpften Liste in umgekehrter Reihenfolge aus dem Eingabestring. Bei dem Problem nicht falsch, aber es ist eine ziemlich einzigartige Möglichkeit, eine Zeichenfolge zu speichern.

Sie gehen auch durch den gesamten Algorithmus (Drucken und alles) für jedes Zeichen, das der Liste hinzugefügt wird. Dies kann für Debug-Zwecke beabsichtigt sein, nehme ich an.

 while(nodeptr != NULL)// prints out the chars 
     { 
      cout << nodeptr -> data; 
      nodeptr = nodeptr ->next; 
     } 

     cout << endl; 

     if(isPalindrome(head)) //prints if function true 
      cout << "Is a Palindrome" << endl; 
     else if(!isPalindrome(head)) //prints if function false 
      cout << "Not a Palindrome" << endl; 

Der zweite Test ist redundant; Entfernen Sie einfach den gesamten if(!isPalindrome(head)) Test und lassen Sie nur die else. Etwas ist entweder ein Palindrom oder nicht, es gibt kein anderes mögliches Ergebnis. Wenn Sie den Algorithmus zweimal ausführen, um sicherzustellen, dass nur CPU-Zyklen verschwendet werden.

} 

    return 0; 
} 
//test if the list is a palindrome 
bool isPalindrome(ListNode* headptr) 
{ 
    ListNode* topptr = headptr;//intializes to first char 
    ListNode* botptr = headptr;//intializes to first char 
    ListNode* temp = NULL; 

Minimieren Sie erneut den Umfang Ihrer Variablen. Insbesondere "temp" kann dorthin gehen, wo es verwendet wird.

if(headptr != NULL && headptr -> next != NULL)//uses to initially test if the list is empty or a singleton 

Wieder machen Sie die Tests mühsamer als sie sein müssen. Testen Sie einfach if (headptr && headptr->next), das ist ausreichend.

{ 

     while(botptr->next != NULL)//places botptr at the last value pointing towards null 
     { 
      //cout << botptr ->data; 
      botptr = botptr -> next ; 
     } 


     while (topptr != temp || topptr -> next != temp) //reiterates until the list is the same as temp(empty) or if the next topptr(headptr) value is temp(singleton) 

Dieser Test wird falsch angegeben; das '||' sollte '& &' sein.

 { 
      if(topptr -> data != botptr -> data)//stops if two values dont equal. I feel like the main problem is with this comparison. 
      { 
       return false; 
      } 

Dieser Vergleich ist in Ordnung.

  else if(botptr -> data == topptr -> data)//if two values do equal move topptr and botptr towards the middle by one. 
      { 

Dieser Vergleich ist jedoch nicht. Wieder testen Sie eine Bedingung, von der Sie bereits wissen, dass sie wahr sein muss. Ein einfaches "anderes" würde genügen. Die zusätzliche if verschwendet CPU-Zyklen und bildet eine Wartungsgefahr.

   temp = topptr; 
       temp = topptr-> next; 
       topptr = temp;//moves topptr down by one 

Eine doppelte Zuweisung zu derselben Variablen sollte Ihnen immer suspekt erscheinen. In diesem Fall sind beide Zuweisungen unnötig; Sie können einfach schreiben topptr = topptr->next;

Darüber hinaus zeigen topptr und bottyptr auf benachbarte Zeichen vor, sie werden jetzt auf das gleiche Zeichen zeigen. Dies führt dazu, dass die Endbedingung der nächsten while-Schleife nie wahr ist, was zu einem Programmabsturz führt. Sie benötigen eine zusätzliche Bedingung:

   if (topptr == botptr) 
        return true; 

       temp = botptr; 
       botptr = topptr; //intializes botptr to the first in the next iteration 

Da Sie eine einfach verkettete Liste haben, können Sie nicht einfach botptr auf die nächstniedrigere Position bewegen. Sie müssen erneut über die gesamte Liste iterieren, um das neue botptr zu finden. Die Laufzeitkosten Ihres Algorithmus sind daher O (n^2), was bedeutet, dass die Kosten des Algorithmus das Quadrat seiner Eingabegröße sind. In diesem Fall ist ein Algorithmus mit O (n) -Komplexität möglich, was sehr bevorzugt ist.

   while(botptr -> next != temp) 
       { 
        botptr = botptr -> next;// move botptr up by one 
       }//places bottom pointer onto the last value pointer towards null or temp 
      } 
     } 
    } 
    return true; // returns true if only the list is empty or a singleton 
} 

Also, was würde eine Lösung mit std :: string aussehen? Es ist ein bisschen einfacher:

bool isPalindrome (const std::string &s) { 
    for (int b=0, e=s.size() - 1; b<e; b++, e--) 
     if (s [b] != s [e]) 
      return false; 

    return true; 
} 

int main() { 
    if (isPalindrome ("abaaba")) 
     cout << "Is a Palindrome" << endl; 
    else 
     cout << "Not a Palindrome" << endl; 

    return 0; 
}