字符串处理------回文判断

题目描述:

1.给定一个字符串,判断其是否为回文串.

2.判断一个单链表是否回文.

对于字符串,可以从两头想中间扫描,在扫描过程中如果头和尾的字符始终相同，则该字符串是回文串.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

bool isPalindrome(const char *s, int n);

int main()
{
    char *str = new char[];
    cout << "input a string(<100): " << endl;
    if(fgets(str, , stdin) == NULL)
    {
        cout << "error!" << endl;
        exit();
    }
    str[strlen(str) - ] = '\0';      //必须添加此句,因为fgets读取一行,会将'\n'也保留

    if(isPalindrome(str, strlen(str)))
        cout << "true" << endl;
    else
        cout << "false" << endl;

    return ;
}

bool isPalindrome(const char *str, int n)
{
    if(str == NULL || n < )
        return false;
    const char *front = NULL, *back = NULL;
    front = s;
    back = s + n - ;

    while(front < back)
    {
        if(*front != *back)
            return false;
        ++front;
        --back;
    }
    return true;
}
           

对于单链表回文串的判断(不改变链表结构): 先找到单链表的中点,将后半部分保存再与前半部分一一对比.

#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>
using namespace std;

struct Node 
{
    char ch;
    struct Node *next;
};

struct Node *findMid(struct Node *head);
bool isPalindrome(struct Node *head, struct Node *mid);

int main()
{
    string str;
    struct Node *head = NULL, *tmp = NULL;
    cout << "input a string: " << endl;
    cin >> str;

    for(int i = ; i < str.size(); i++)
    {
        struct Node *s = new Node ;
        s->ch = str[i];
        s->next = NULL;
        if(p == NULL)
        {
            head = s;
            p = s;
        }
        else
        {
            p->next = s;
            p = p->next;
        }
        s = NULL;
    }

    struct Node *mid = findMid(head);
    if(mid == NULL)
    {
        cout << "some wrong" << endl;
        exit();
    }
    if(isPalindrome(head, mid))
        cout << "true" << endl;
     else
         cout << "false" << endl;

    while(head != NULL)
    {
        struct Node *p = head;
        head = head->next;
        delete [] p;
        p = NULL;
    }

    return ;
}

struct Node *findMid(struct Node *head)
{
    if(head == NULL)
        return NULL;
    struct Node *p = head, *q = head;
    while(q->next != NULL && q->next->next != NULL)
    {
        p = p->next;
        q = q->next->next;
    }
    return p;
}

bool isPalindrome(struct Node *head, struct Node *mid)
{
    if(head == NULL || mid == NULL)
        return false;
    if(head == mid || head->next == NULL)
        return true;
    vector<char> str;
    struct Node *p = mid->next;
    while(p != NULL)
    {
        str.push_back(p->ch);
        p = p->next;
    }
    for(int i = ; i < str.size(); i++)
    {
        if(head->ch != str[str.size() - i - ])
            return false;
        head = head->next;
    }
    return true;
}