Поскольку вы делаете совсем немного неправильно я написал длинную критику. Если вы последуете за ним, вы также узнаете, почему ваша программа не работает на этом пути. Для начала:
- Вы используете связанный список, чтобы представить строку. Почему бы не использовать 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[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;
Опять же, свести к минимуму объем ваших переменных. «temp», в частности, может пойти туда, где он используется.
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.
{
Это сравнение, однако, нет. Опять же вы испытываете условие, которое вы уже знаете, должно быть правдой. Достаточно простого «еще». Дополнительный, если отнимает процессорные циклы и создает опасность технического обслуживания.
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;
}
Вы можете поделиться журналом сбоев и точным положением, в котором программа не работает? так что было бы легко проверить проблему для нас – ddb
'temp = topptr;' сразу же следует 'temp = topptr-> next;' предлагает вам не полностью понять алгоритм, который вы пытаетесь реализовать, или как его реализовать используя связанные списки.Алгоритм должен быть базовым. Создав связанный список символов, создайте * другой *, используя тот же алгоритм головок, который вы используете сейчас, но перечисляя первый связанный список в качестве исходного ввода. После этого запустите перечисление * обоих * списков с самого начала. Если они одинаковы на каждом узле, у вас есть палиндром (и технически вам нужно только перечислить * половину * для цикла сравнения). – WhozCraig
И '! IsPalindrome (head)' бесполезно, кстати. Простой 'else' достаточно, так как вы уже определили условие« нет ». – WhozCraig