数据结构实验之链表三：链表的逆置

﹏ヽ暗。殇╰゛Y 2022-05-30 04:45 156阅读 0赞

1.知识点：链表逆置  
2.题意：输入多个整数，以-1作为结束标志，顺序建立一个带头结点的单链表，之后对该单链表的数据进行逆置，并输出逆置后的单链表数据  
3.注意事项：游动指针的移动(指针域指向的变化)

代码：

#include <stdio.h>
    #include <stdlib.h>
    typedef struct st
    {
        int num;
        struct st * next;
    }str;
    int main()
    {
        int n;
        str *head, *tail, *p, *q;//定义str类型首指针head， 尾指针tail， 游动指针p， 游动指针q；
        head = (str *)malloc(sizeof(str));
        tail = head;//将head的数据域和指针域赋值给同类型的tail；
        head -> next = tail;
        tail -> next = NULL;
        while(scanf("%d", &n) && n != -1)
        {
            p = (str *)malloc(sizeof(str));//游动指针p动态申请空间
            p -> next = NULL;//顺序输入1;
            tail -> next = p;//顺序输入2;
            tail = p;//顺序输入3(将p的数据域和指针域赋值给同类型的tail(tail等同向下移动一个表,再度成为尾指针));
            p -> num = n;//给游动指针p的数据域中的num赋值
        }
        p = head -> next;
        head -> next = NULL;//将头指针作为新链表的头指针
        q = p -> next;
        while(p != NULL)
        {
            p -> next = head -> next;//将p所在的表插入到head新表中1；
            head -> next = p;//将p所在的表插入到head新表中2；
            p = q;//游动指针p重新获取原表中的新头表；
            if(q != NULL)
               q = q -> next;//游动指针p不断记录原表中的新头表；
        }
        p = head -> next;//游动指针p指向新表中的第一个实表;
        while(p != NULL)
        {
            printf("%d%c", p -> num, p -> next == NULL? '\n': ' ');
            p = p -> next;//游动指标p向下移动至新的实表;
        }
        return 0;
    }