## 問題描述 > 試寫一算法來判斷單鏈表的前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;i<n/2;i++){ s[i]=p->data; 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;i<n/2;i++){ s[i]=p->data; 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"); } ~~~