51.png

    1. /*
    2.     设单链表的表头指针为h，节点结构由data和next两个域构成，其中data域为字符型。
    3.     试设计算法判断该链表的全部n个字符是否是中心对称，例如xyx，xyyx都是中心对称。
    5.     分析：
    6.         我们可以利用栈的先进后出的特性来搞定这道题，我们设置两个快慢指针，fast和slow
    7.         之前我们就用过这种方法，用以找到中间节点，之后将slow节点之后的节点依次入栈，
    8.         fast指针重新指向首节点，然后fast和栈内元素一一比较，若存在不同，则不对称。
    9. */
    10. struct Link {
    11.     union {
    12.         char letter;
    13.     }type;
    14.     struct Link *next;
    15. };
    16. struct Stack {
    17.     char *arr;
    18.     int len;
    19.     int top;
    20. };
    21. #define _CRT_SECURE_NO_WARNINGS
    22. #include <stdio.h>
    23. void isSymmetry(Link *h) {
    24.     int size;
    25.     struct Stack *s;
    26.     Stack *createStack(int);
    27.     bool push(Stack *,char);
    28.     bool empty(Stack *);
    29.     char *top(Stack *);
    30.     bool pop(Stack *);
    31.     void destory(Stack *);
    32.     printf("请输入要创建的栈的大小：size=");
    33.     scanf("%d",&size);
    34.     s = createStack(size);
    35.     struct Link *fast = h->next, *slow = h->next;
    36.     while (fast->next&&fast->next->next) {
    37.         fast = fast->next->next;
    38.         slow = slow->next;
    39.     }
    40.     fast = h->next;
    41.     while (slow->next) {//将中间元素的后面节点依次入栈
    42.         push(s,slow->next->type.letter);
    43.         slow = slow->next;//我总是忘记往下走
    44.     }
    45.     while (!empty(s)) {
    46.         if (fast->type.letter != *top(s) ) {
    47.             printf("该链表非中心对称");
    48.             break;
    49.         }
    50.         fast = fast->next;
    51.         pop(s);
    52.     }
    53.     if(empty(s))printf("该链表是中心对称的");
    54.     destory(s);//最后销毁栈
    55. }
    56. int main() {
    57.     struct Link *head;
    58.     Link *createLink(int);
    59.     head = createLink(1);
    60.     isSymmetry(head);
    61.     return 0;
    62. } 
    63. 一名谦虚的学生