机票旅游网站开发,软件编程和网站开发差别,厂家免费招代理,jsp网站开发实例与发布回文串为首尾对称的字符串#xff1a;
如a#xff0c;aba#xff0c;abba等
单链表思路
1.将字符读入链表
2.找到链表中点
3.将链表从中点断开成2条#xff0c;将后半条反转
4.比较两条链表是否相等#xff08;比较次数以少的为准#xff08;长度为奇数时#xff…回文串为首尾对称的字符串
如aabaabba等
单链表思路
1.将字符读入链表
2.找到链表中点
3.将链表从中点断开成2条将后半条反转
4.比较两条链表是否相等比较次数以少的为准长度为奇数时
双向链表思路
1.将字符读入链表
2.找到链表尾节点
3.从首尾依次向中间比较
双向链表可以双向移动代码上更简洁见下面 单链表C代码实现
//
// Created by mingm on 2019/3/13.
//
#include iostream
#include math.h
using namespace std;
struct Node //节点
{char data;Node* next;Node():next(NULL){}Node(char ch):data(ch),next(NULL){}~Node(){}
};
class SLinkedList //链表
{Node* p_head;
public:SLinkedList() //构造函数{p_head new Node; //带头链表
// cout new 1 endl;}~SLinkedList(){ erase(); } //析构函数void erase(){Node *del_tempNode, *tempNode;del_tempNode p_head;while(del_tempNode ! NULL) {tempNode del_tempNode - next;delete del_tempNode;
// cout delete 1 endl;del_tempNode tempNode;}}void set_head(Node* p){p_head p;}Node* get_head(){return p_head;}size_t get_len() //求链表长度{size_t len 0;Node* p p_head;while(p){len;p p-next;}return len;}void delHeadSentinel() //删除链表表头哨兵{Node* del p_head;p_head p_head-next;delete del; //删除链表的表头哨兵
// cout delete head 1 endl;}Node* reverse() //链表反转{if(p_head NULL || p_head-next NULL)return NULL;else{Node *prevNode, *nextNode, *tempNode;prevNode p_head;nextNode prevNode-next;prevNode-next NULL;while(nextNode ! NULL){tempNode nextNode-next;nextNode-next prevNode;prevNode nextNode;nextNode tempNode;}p_head prevNode;return p_head;}}Node* findMiddle() //查找链表中点{size_t len get_len();Node* tempNode p_head;size_t n ceil(double(len)/2);for(size_t i 1; i n; i){tempNode tempNode-next;}return tempNode;}
};int main()
{while(true){cout ----------------------------------- endl;char ch;cin.clear();cout enter a word, is it a palindrome ? endl;if((ch cin.get()) ch \n){cout empty word ! endl;continue;}SLinkedList charList, backHalfOfList; //链表(前半部分链表)后半部分链表Node* tempNode charList.get_head();while(ch ! \n) //把单词存进链表charList{Node* newNode new Node(ch);
// cout new insert 1 endl;tempNode-next newNode;tempNode newNode;ch cin.get();}charList.delHeadSentinel(); //链表表头删除backHalfOfList.delHeadSentinel(); //把空表头哨兵节点删除Node* endOfFrontList charList.findMiddle(); //链表的中点是前一半的结束节点Node* backListHead endOfFrontList-next; //中点的下一个节点是后半部分的开始endOfFrontList-next NULL; //把前半部分链表断开backHalfOfList.set_head(backListHead); //把后半部分的链表表头地址设置好backHalfOfList.reverse(); //后半部分链表反转size_t n backHalfOfList.get_len(); //求后半部分链表长度Node *frontList charList.get_head(); //找到前半部分的开头Node *backList backHalfOfList.get_head(); //后半部分的开头反转后的bool answer false;if(backList NULL) //如果后半部分为空说明只有一个字符answer true;else{for(size_t i 0; i n; i) //比较数据是否相同{if(frontList-data ! backList-data){answer false;break;}else{answer true;frontList frontList-next;backList backList-next;}}}if(answer)cout the word is a palindrome. endl;elsecout the word is not a palindrome. endl;char conti;cout continue to check? (y/n) endl;cin conti;cin.get();if(conti y || conti Y){continue;}elsebreak;}return 0;
}
Valgrind检查结果 双向链表C代码实现
//
// Created by mingm on 2019/3/16.
//
#include iostream
#include math.h
using namespace std;
struct Node //节点
{char data;Node *prev, *next;Node():prev(NULL),next(NULL){}Node(char ch):data(ch),prev(NULL),next(NULL){}~Node(){}
};
class SLinkedList //链表
{Node* p_head;
public:SLinkedList() //构造函数{p_head new Node; //带头链表
// cout new 1 endl;}~SLinkedList(){ erase(); } //析构函数void erase(){Node *del_tempNode, *tempNode;del_tempNode p_head;while(del_tempNode ! NULL) {tempNode del_tempNode - next;delete del_tempNode;
// cout delete 1 endl;del_tempNode tempNode;}}void set_head(Node* p){p_head p;}Node* get_head(){return p_head;}Node* get_tail() //求链表尾节点{Node* p p_head;if(p_head NULL)return NULL;while(p-next){p p-next;}return p;}void delHeadSentinel() //删除链表表头哨兵{Node* del p_head;p_head p_head-next;p_head-prev NULL;delete del; //删除链表的表头哨兵
// cout delete head 1 endl;}
};int main()
{while(true){cout ----------------------------------- endl;char ch;cin.clear();cout enter a word, is it a palindrome ? endl;if((ch cin.get()) ch \n){cout empty word ! endl;continue;}SLinkedList charList; //链表Node* tempNode charList.get_head();while(ch ! \n) //把单词存进链表charList{Node* newNode new Node(ch);
// cout new insert 1 endl;tempNode-next newNode; //前面节点后指针指向后面newNode-prev tempNode; //后面节点前置指针指向前面tempNode newNode;ch cin.get();}charList.delHeadSentinel(); //链表空表头删除Node *front charList.get_head(); //定义一个从头开始的指针Node *back charList.get_tail(); //定义一个从尾部开始的指针bool answer false;if(front back) //说明只有一个字符answer true;else{while(front ! back) //比较数据是否相同{if(front-data ! back-data){answer false;break;}else{answer true;front front-next;back back-prev;}}}if(answer)cout the word is a palindrome. endl;elsecout the word is not a palindrome. endl;char conti;cout continue to check? (y/n) endl;cin conti;cin.get();if(conti y || conti Y){continue;}elsebreak;}return 0;
}
Valgrind检查结果
