杭州网站设计建设公司/大数据营销精准营销

1.用单链表存储用到的数据结构，线性表，但结点的数据域的类型是字符

typedef struct CNode{char ch;struct CNode *next;
}CNode,*LinkList;

2.回文串：是一个正读和反读都一样的字符串。

        思路：回文串是以中间为对称轴两边对称的一种特殊字符串，故将字符串分为两半，左边一半从右往左遍历，右边一半从左往右遍历，如果对应的字符都相等则对称，但字符串的长度是奇数函数偶数也要判断一下，因为如果是奇数的话，中间一个数就是对称轴，中间一个数不用比较，两边比较就行，如“abcba”，以’c‘为对称轴，比较’ab‘和’ba‘即可，但如果是偶数，对称轴是中间两个数的中间部分，故要比较整个链表，如“abccba”，要比较‘abc’和‘cba’，然后就可以发现要判断的字符串是回文串，则左半边的字符串倒过来就等于右半边的字符串！故要找到中间结点，将左半边逆序，然后比较即可。

3.如何找到链表的中间结点--快慢指针

        快指针每次走两步，慢指针每次走一步，这样在快指针走到链表最后的时候，慢指针走到中间结点，当结点个数是偶数的时候，慢指针指向中间两个节点左边的一个。可以画图模拟一下就清楚了，快慢指针用法很多，要掌握。

1.找到中间结点--快慢指针

2.在移动慢指针的同时，逆置单链表

3.用两个指针分别遍历左半边和右半边比较是否相等

代码实现C++:

#include<iostream>
using namespace std;
/*判断用单链表存储的字符串是不是回文串*/ 
typedef struct CNode{char ch;struct CNode *next;
}CNode,*LinkList;
void init(LinkList &L){//初始化有一个头结点单链表 L=new CNode();L->next=NULL;
} 
void insertTail(LinkList &L,char ch){//用尾插法 LinkList pr=new CNode();pr->ch=ch;pr->next=NULL;LinkList p=L;while(p->next){p=p->next;}p->next=pr;
}
void printLink(LinkList &L){//打印单链表 LinkList pr=L->next;while(pr){cout<<pr->ch<<"->";pr=pr->next;}cout<<"NULL"<<endl;
}
void judge(LinkList &L){//判断是不是回文串 LinkList slow=L->next,fast=L->next;//快慢指针 LinkList p,q=fast->next;//逆置时用来保存结点的临时变量 int cnt=1;//用来记录字符串的长度 LinkList r1,r2;//while结束的时候，用这两个指针来遍历前一半链表和后一半链表 while(fast->next!=NULL){fast=fast->next;cnt++;if(fast->next==NULL) break;fast=fast->next;cnt++;p=q;//逆置单链表 q=q->next;//q用来保存下一个结点的，因为逆置会改变q的next域 p->next=slow;slow=p;}if(cnt%2==0){//用来判断字符串长度是不是偶数，如果是偶数则此时左右各一半，slow就是左边一半的头结点 r1=slow;}else{r1=slow->next;//如果是偶数，则slow指向中间一个说明左边比右边多一个，从左边的第二个开始比较 }r2=q;//q就是右边的第一个结点 while(r2!=NULL){if(r1->ch!=r2->ch){cout<<"不是回文串！"<<endl;return;}r1=r1->next;r2=r2->next;}cout<<"是回文串！"<<endl;}
int main()
{LinkList L;init(L);char ch;cin>>ch;while(ch!='#'){insertTail(L,ch);cin>>ch;}printLink(L);judge(L);return 0;
}

1024程序员节快乐哦uu们~