第2章第1节练习题2 判断是否中心对称
最后更新于：2022-04-01 19:51:36
## 问题描述
> 试写一算法来判断单链表的前n个字符是否中心对称。
例如xyx，xyyx都是中心对称
## 算法思想
> 在[第1章第2节练习题19 判断循环双链表对称](http://blog.csdn.net/u013595419/article/details/50511050)中已经初次涉及到了判断链表中心对称的问题，但是因为单链表只能从前往后遍历，因此不能使用与其相同算法进行解决，那么借助栈来判断单链表中的数据是否中心对称。
> 将单链表的前一半元素依次入栈，遍历到单链表的后一半元素的第一个元素时，便从栈中弹出一个元素，对它们俩开始比较。
> - 若相等，则将链表中的下一个元素与栈中再次弹出的元素进行比较，直至单链表到末尾，而且如果此时栈也为空栈，则可得出此单链表是中心对称的结论；
> - 若不相等，则单链表不是中心对称。
## 算法描述
~~~
int JudgeSym(LNode* head,int n)
{
LNode *p=head->next;
char s[n/2];
int i;
for(i=0;idata;
p=p->next;
}
i--;
if(n%2){
p=p->next;
}
while(p&&p->data==s[i]){
p=p->next;
i--;
}
if(i==-1){
return 0;
}else{
return -1;
}
}
~~~
具体代码见附件。
## 附件
~~~
typedef char ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
LinkList CreatList(LNode*);
int JudgeSym(LNode*,int);
void Print(LNode*);
int main(int argc,char* argv[])
{
LNode *head;
head=(LNode*)malloc(sizeof(LNode));
head=CreatList(head);
Print(head);
int flag;
int n=5;
flag=JudgeSym(head,n);
if(flag){
printf("The link is not symmetery before %d charactor!\n",n);
}else{
printf("The link is symmetery before %d charachtor!\n",n);
}
return 0;
}
//尾插法建立单链表
LinkList CreatList(LNode* head)
{
LNode *L;
LNode *r=head;
ElemType x;
scanf("%c",&x);
while(x!='\n'){
L=(LNode*)malloc(sizeof(LNode));
L->data=x;
r->next=L;
r=L;
scanf("%c",&x);
}
return head;
}
//判断中心对称
int JudgeSym(LNode* head,int n)
{
LNode *p=head->next;
char s[n/2];
int i;
for(i=0;idata;
p=p->next;
}
i--;
if(n%2){
p=p->next;
}
while(p&&p->data==s[i]){
p=p->next;
i--;
}
if(i==-1){
return 0;
}else{
return -1;
}
}
//打印全部结点
void Print(LNode *head)
{
LNode *p=head->next;
while(p){
printf("%4c",p->data);
p=p->next;
}
printf("\n");
}
~~~
';