試圖找出鏈表問題

Question

#include <iostream> 
using namespace std; 

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

bool isPalindrome(ListNode*); 

int main() 
{ 

    char pali[] = "abaaba";//array of chars 

    for (int i = 0; pali[i] != '\0'; i++) 
    { 
     newNode = new ListNode; 
     newNode -> data = pali[i]; //places chars into a linked list 
     newNode -> next = head; 
     head = newNode;// links list together 
     nodeptr = head; 


     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; 


    } 

    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; 

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

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

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

       temp = topptr; 
       temp = topptr-> next; 
       topptr = temp;//moves topptr down by one 
       temp = botptr; 
       botptr = topptr; //intializes botptr to the first in the next iteration 

       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 
} 

我很難找出這個程序的問題。每次運行它時，都會經歷第三次迭代，並且只是崩潰。出於某種原因，我無法獲得第二次迭代的返回錯誤比較。它循環一次它應該循環爲零，因爲topptr等於b，botptr等於a。

Answer 1

這行看起來非常可疑：

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是您用於多種用途（在topptr尤其是下一個值並按照botptr項目）臨時變量。使用這樣的變量進行內部範圍以外的比較是危險的。

我相信行應該是這樣的：

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

---

另外，我建議你在聲明在你需要它的範圍temp變量。換句話說，刪除行

ListNode* temp = NULL; 

，並更改下面else if(botptr -> data == topptr -> data)行至

ListNode* temp = topptr; 

Answer 2

既然你是做了不少錯事，但我已經寫了一個更長的批判。如果你遵循它，你也會發現爲什麼你的程序不能一直工作。開頭：

• 您使用鏈表來表示一個字符串。爲什麼不使用std :: string？它可以讓你以一種更簡單的方式實現這件事。
• 您以相反的順序存儲字符串。在技​​術上不是錯誤的，但你是我遇到的第一個將字符串存儲在反向單鏈表中的人。
• 你實現自己的鏈表而不是使用std :: list。
• 對於真正需要雙向迭代的算法，您使用單個鏈接列表。
• 您並未清理您的任何資源。這裏沒關係，但是當你編寫大型程序時，這是一個好習慣。

已經得到了這一點的方式，讓我們來看看源：

#include <iostream> 
using namespace std; 

這種說法是令人難以接受的：Why is "using namespace std" considered bad practice?

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

在這裏，您全局聲明三個變量，可以很很容易成爲主要的一部分。儘量減少每個聲明變量的範圍。

bool isPalindrome(ListNode*); 

int main() 
{ 
    char pali[] = "abaaba";//array of chars 

    for (int i = 0; pali[i] != '\0'; i++) 

測試pali的最終條件是這樣的，但是很麻煩。您可以輕鬆測試pali[i]。

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

因此，您的鏈表與您的輸入字符串相反。考慮到這個問題沒有錯，但它是存儲字符串的一種非常獨特的方式。

此外，您還會瀏覽添加到列表中的每個字符的整個算法（打印和所有內容）。我想這可能是故意用於調試目的。

 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; 

第二個測試是多餘的;只是完全刪除整個if(!isPalindrome(head))測試，並且只留下else。有些東西要麼是迴文，要麼沒有其他可能的結果。兩次運行算法'確保'只是浪費CPU週期。

} 

    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; 

再次，最小化變量的範圍。特別是，「溫度」可以下降到使用地點。

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

再一次，你讓測試比他們需要更繁瑣。只要測試if (headptr && headptr->next)，這就足夠了。

{ 

     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) 

該測試指定不正確; '||'應該是'& &'。

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

這個比較就好了。

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

但是，這種比較不是。你再次測試一個你已經知道的條件必須是真實的。一個簡單的'其他'就足夠了。額外的如果浪費CPU週期並形成維護危險。

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

對同一個變量的雙賦值應該總是看起來可疑。在這種情況下，兩項任務都是不必要的。你可以簡單地寫topptr = topptr->next;

此外，如果topptr和bottomptr指向之前的相鄰字符，它們現在將指向相同的字符。這將導致下一個while循環的結束條件永遠不會成立，導致程序崩潰。你需要一個附加條件：

   if (topptr == botptr) 
        return true; 

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

因爲你有一個單鏈表，你不能輕易移動botptr到下一個最低位置。您需要重新遍歷整個列表才能找到新的botptr。因此，算法的運行時成本爲O（n^2），這意味着算法的成本是其輸入大小的平方。在這種情況下，具有O（n）複雜度的算法是可能的，這是非常優選的。

   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 
} 

那麼使用std :: string的解決方案會是什麼樣子？這有點簡單：

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; 
}