数据结构 | 每日一练（54）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．设单链表的表头指针为 h，结点结构由 data 和 next 两个域构成，其中 data 域为字符型。写出算法dc(h,n),判断该链表的前 n 个字符是否中心对称。例如 xyx, xyyx 都是中心对称。

正确答案

ps：||代表注释

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

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

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

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

for（i=1；i<=n/2；i++）∥ 链表前一半元素进栈。

{s[i]=p->data；p=p->next；}

i--; ∥恢复最后的i值

if（n%2==1）p=p->next；} ∥若n是奇数，后移过中心结点。

while（p!=null && s[i]==p->data）{i--；p=p->next；} ∥测试是否中心对称。

if（p==null） return（1）；∥链表中心对称

else return（0）； ∥链表不中心对称

}∥算法结束。

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

转发朋友圈，点下“好看”就是对小编的最大帮助！

-end-