设单链表的表头指针为h,链表中结点构造为(data,next),其中data域为字符型,链表长度为n。编写算法判断该链表的n个字符是否中心对称。(例如xyx,xyyx都是中心对称。)
参考答案:
int Centrosymmetric(LinkList h, int n){
char s[]; int i=; //i记结点个数,s字符栈
LNode * p=h->next; //p是链表的工作指针,指向待处理的当前元素
for(i=A; i<=n/B; i++){ //链表前一半元素进栈
s[i]=p->data;
p=p->next;
}
i- -; //恢复最后的i值
if(n%B= =A)p=p->next; //若n是奇数,后移过中心结点
while(p! =NULL && s[i] = =p->data){ //测试是否中心对称
i- -;
p=p->next;
}
if(p= =NULL)return A; //链表中心对称
else return 0; //链表非中心对称
}
算法中先将“链表的前一半”元素(字符)进栈。当n为偶数时,前一半和后一半的个数相同;当n为奇数时,链表中心结点字符不必比较,移动链表指针到下一字符开始比较。比较过程中遇到不相等时,立即退出while循环,不再进行比较。
解析: 判断链表中数据是否中心对称,通常使用栈。将链表的前一半元素依次进栈。在处理链表的后一半元素时,当访问到链表的一个元素后,就从栈中弹出一个元素,两元素比较,若相等,则将链表中下一元素与栈中再弹出元素比较,直至链表到尾。这时若栈是空栈,则得出链表中心对称的结论;否则,当链表中一元素与栈中弹出元素不等时,结论为链表非中心对称,结束算法的执行。