数据结构考研分类复习真题 第二章 答案[32]

．[题目分析] 判断链表中数据是否中心对称通常使用栈将链表的前一半元素依次进栈在处理链表的后一半元素时当访问到链表的一个元素后就从栈中弹出一个元素两元素比较若相等则将链表中下一元素与栈中再弹出元素比较直至链表到尾这时若栈是空栈则得出链表中心对称的结论;否则当链表中一元素与栈中弹出元素不等时结论为链表非中心对称结束算法的执行

int dc(LinkedList hint n)∥h是带头结点的n个元素单链表链表中结点的数据域是字符本算法判断链表是否是中心对称

{char s[]; int i=;∥i记结点个数 s字符栈

p=h>next;∥p是链表的工作指针指向待处理的当前元素

for(i=;i<=n/;i++)∥链表前一半元素进栈

{s[i]=p>data;p=p>next;}

i;∥恢复最后的i值

if(n%==)p=p>next;}∥若n是奇数后移过中心结点

while(p!=null && s[i]==p>data){i;p=p>next;}∥测试是否中心对称

if(p==null)return();∥链表中心对称

else return();∥链表不中心对称

}∥算法结束

[算法讨论] 算法中先将链表的前一半元素(字符)进栈当n为偶数时前一半和后一半的个数相同;当n为奇数时链表中心结点字符不必比较移动链表指针到下一字符开始比较比较过程中遇到不相等时立即退出while循环不再进行比较

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []