链表逆置和从尾到头打印单链表

曾经终败给现在 2022-05-25 12:41 178阅读 0赞

链表的逆置和链表从尾到头打印是两个不同的概念，链表的逆置就是将链表（a1,a2,a3…an）转化为（an，a（n-1),..a1），链表结构会发生改变；而从尾到头打印链表是将链表中的元素逆序打印，即从尾结点开始依次打印，链表的结构不发生改变。

--------------------

链表分为带头结点的单链表和不带头结点的单链表，所以链表逆置和从尾到头打印单链表可分为对带头结点的单链表和不带头结点的单链表的操作。

--------------------

**不带头结点的单链表**

从尾到头打印链表的算法思想：先找到链表的尾结点，将尾结点中的元素值打印出来，然后从头开始继续查找链表中的元素，打印尾节点的前一个结点中的元素值，循环操作，直到链表的头指针指向空为止。可以用下图描述这一过程。  
![这里写图片描述][70]

//从尾到头打印单链表
    
    void PrintFormTail(LinkList pHead)
    {
        Node* pCur = pHead;
        Node* Tail = NULL;
        while (pCur != Tail)
        {
            while (pCur->Next!= Tail)
            {
                pCur = pCur->Next;
            }
            printf("%-3d", pCur->Data);
            Tail = pCur;
            pCur = pHead;
        }
        printf("\n");
    }

不带头结点的链表的逆置，可以通过改变链表的指针方向来实现，链表的逆置是将链表（a1,a2,a3…an）转化为（an，a（n-1),..a1）的过程，假设原链表为`a1->a2->a3->a4->NULL`,只需将链表的结构变成`NULL←a1←a2←a3←a4`即完成了链表的逆置。为此，定义3个指针分别为pPre，pCur，pNext，使pPre开始时指向NULL，pCur指向头指针pHead，设置一个while循环，pNext指向pCur->Next,先使`pCur->Next = pPre;`即：使第一个结点指向空，然后依次将指针pPre和pNext后移一位，循环改变指针的指向，直到pCur==NULL，跳出循环，最后使头结点指向原链表的尾结点，即完成了链表的逆置。如下图：  
![这里写图片描述][70 1]

//*带头结点的链表逆置*
    
    /*由于最后要改变pHead的指向，即改变一级指针的指向， 所以参数pHead定义为二级指针*/
    void ReverseList(LinkList* pHead)
    {
        Node* pPre = NULL;
        Node* pNext = NULL;
    
        //如果链表为空，或者链表中只有一个元素，则不需要逆置
        if (*pHead == NULL || (*pHead)->Next == NULL)
        {
            return;
        }
        Node* pCur = *pHead;
        while (pCur)
        {
            pNext = pCur->Next;
            pCur->Next = pPre;
            pPre = pCur;
            pCur = pNext;
        }
        *pHead = pPre;
    }

**完整源代码：**

#include <stdio.h>
    #include <stdlib.h>
    #include <Windows.h>
    
    typedef int DataType;
    
    typedef struct Node
    {
        DataType Data;
        struct Node* Next;
    }Node, *LinkList;
    
    //初始化，将头指针pHead置空
    void InitList(LinkList* pHead)
    {
        *pHead = NULL;
    }
    
    //尾插，在表尾插入一个元素data
    
    void PushBack(LinkList* pHead, DataType data)
    {
        if (NULL == (*pHead))     //如果链表为空，则头插一个元素
        {
            *pHead = (LinkList)malloc(sizeof(Node));
            if (NULL == *pHead)
            {
                printf("申请空间失败!\n");
            }
            (*pHead)->Data = data;
            (*pHead)->Next = NULL;
            return;
        }
    
        Node* pCur = (*pHead);
        Node* pNewNode = (LinkList)malloc(sizeof(Node));
        if (pNewNode == NULL)
        {
            printf("申请空间失败!\n");
        }
        //跳出循环时pCur指向链表的尾结点
        while (pCur->Next != NULL)
        {
            pCur = pCur->Next;
        }
        pNewNode->Data = data;
        pCur->Next = pNewNode;
        pNewNode->Next = NULL;
    }
    
    
    
    //打印表中元素
    
    void PrintList(LinkList pHead)
    {
        Node* pCur = pHead;
        while (pCur)
        {
            printf("%-3d", pCur->Data);
            pCur = pCur->Next;
        }
        printf("\n");
    }
    
    //从尾到头打印单链表
    
    void PrintFormTail(LinkList pHead)
    {
        Node* pCur = pHead;
        Node* Tail = NULL;
        while (pCur != Tail)
        {
            while (pCur->Next!= Tail)
            {
                pCur = pCur->Next;
            }
            printf("%-3d", pCur->Data);
            Tail = pCur;
            pCur = pHead;
        }
        printf("\n");
    }
    
    //链表逆置
    
    /*由于最后要改变pHead的指向，即改变一级指针的指向， 所以参数pHead定义为二级指针*/
    void ReverseList(LinkList* pHead)
    {
        Node* pPre = NULL;
        Node* pNext = NULL;
    
        //如果链表为空，或者链表中只有一个元素，则不需要逆置
        if (*pHead == NULL || (*pHead)->Next == NULL)
        {
            return;
        }
        Node* pCur = *pHead;
        while (pCur)
        {
            pNext = pCur->Next;
            pCur->Next = pPre;
            pPre = pCur;
            pCur = pNext;
        }
        *pHead = pPre;
    }
    
    
    int main()
    {
        LinkList L;
        DataType data;
        //链表初始化
        InitList(&L);
        //循环输入链表中的元素值，采用尾插法，将其插入链表
        printf("请输入链表中的元素，以-1结束：");
        scanf("%d", &data);
        while (data != -1)
        {
            PushBack(&L, data);
            scanf("%d", &data);
        }
        //打印插入链表中的元素
        PrintList(L);
        //从尾到头打印链表
        PrintFormTail(L);
        //链表逆置
        ReverseList(&L);
        //打印逆置后链表中的元素
        PrintList(L);
        system("pause");
        return 0;
    }

--------------------

**带头结点的单链表**

带头结点的单链表的打印和不带头结点的链表的打印，基本思想是一样的，由于链表有头结点，（头结点中不存数据），头指针pHead 指向头节点，所以找要打印的结点元素值时应从pHead->Next 开始，指针pCur指向pHead->Next;然后使指针Tail指向要打印结点pCur的下一个节点，通过指针的移动依次打印出链表中的元素值。

//从尾到头打印链表
    
    void PrintFormTail(LinkList* pHead)
    {
        assert(pHead);
        Node* pCur = (*pHead)->Next;
        Node* Tail = NULL;
        while (pCur!= Tail)
        {
            while (pCur->Next != Tail)
            {
                pCur = pCur->Next;
            }
            printf("%-3d", pCur->Data);
            Tail = pCur;
            pCur = (*pHead)->Next;
        }
        printf("\n");
    }

带头结点的单链表的逆置相对比较好理解，算法思想：先将单链表的头结点与第一个结点断开,使头结点构成一个空链表，然后从第一个结点开始依次取下原来链表中的结点，将取下的结点依次插入到新链表的头部，循环这一过程直到所有的结点都插入到新链表，如下图所示。

![这里写图片描述][70 2]  
![这里写图片描述][70 3]  
![这里写图片描述][70 4]

//带头结点的链表逆置
    void Reverse(LinkList pHead)
    {
        //如果链表为空，或者链表中只有一个结点则不需要逆置
        if (pHead->Next == NULL || pHead->Next->Next == NULL)
        {
            return;
        }
        Node* pCur = pHead->Next;
        Node* pNext;
        //将头结点与链表断开，构成一个空链表
        pHead->Next = NULL;
        //当pCur！=NULL时依次取链表中的结点插入到头结点之后
        while (pCur)
        {
            pNext = pCur->Next;
            pCur->Next = pHead->Next;
            pHead->Next = pCur;
            pCur = pNext;
        }
    }

**完整源代码**

#include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <Windows.h>
    
    typedef int DataType;
    typedef struct Node
    {
        DataType Data;
        struct Node* Next;
    }Node,*LinkList;
    
    void InitList(LinkList* PHead)
    {
        if ((*PHead = (LinkList)malloc(sizeof(Node))) == NULL)
        {
            printf("内存申请失败!\n");
            return;
        }
        (*PHead)->Next = NULL;
    }
    
    //尾插法建表
    void CreatFormTail(LinkList PHead)
    {
        Node* s;
        Node* tail;
        DataType data;
        tail = PHead;
        scanf("%d", &data);
        while (data != -1)
        {
            s = (Node*)malloc(sizeof(Node));
            s->Data = data;
            s->Next = tail->Next;
            tail->Next = s;
            tail = s;   //tail始终指向表尾
            scanf("%d", &data);
        }
    }
    
    //打印表中元素
    void PrintList(LinkList PHead)
    {
        Node* p;
        p = PHead->Next;
        while (p)
        {
            printf("%-3d", p->Data);
            p = p->Next;
        }
        printf("\n");
    }
    
    //从尾到头打印链表
    
    void PrintFormTail(LinkList* pHead)
    {
        assert(pHead);
        Node* pCur = (*pHead)->Next;
        Node* Tail = NULL;
        while (pCur!= Tail)
        {
            while (pCur->Next != Tail)
            {
                pCur = pCur->Next;
            }
            printf("%-3d", pCur->Data);
            Tail = pCur;
            pCur = (*pHead)->Next;
        }
        printf("\n");
    }
    
    //带头结点的链表逆置
    void Reverse(LinkList pHead)
    {
        //如果链表为空，或者链表中只有一个结点则不需要逆置
        if (pHead->Next == NULL || pHead->Next->Next == NULL)
        {
            return;
        }
        Node* pCur = pHead->Next;
        Node* pNext;
        //将头结点与链表断开，构成一个空链表
        pHead->Next = NULL;
        //当pCur！=NULL时依次取链表中的结点插入到头结点之后
        while (pCur)
        {
            pNext = pCur->Next;
            pCur->Next = pHead->Next;
            pHead->Next = pCur;
            pCur = pNext;
        }
    }
    
    int main()
    {
        LinkList L;
        //初始化链表
        InitList(&L);
        //尾插法建表
        CreatFormTail(L);
        //打印表中元素
        PrintList(L);
        //从尾到头打印单链表
        PrintFormTail(&L);
        //链表逆置
        Reverse(L);
        //打印逆置后的链表中元素
        PrintList(L);
        system("pause");
    
        return 0;
    }

[70]: /images/20220525/22a938271acd4cd88d9c7677a8c7cd4c.png
[70 1]: /images/20220525/42d8fbe1ec3e400dab96cf9419412d08.png
[70 2]: /images/20220525/998aa8f3185c40f5945631bb107f00c5.png
[70 3]: /images/20220525/4ea4c5b50198458585afcb807a23eaa3.png
[70 4]: /images/20220525/9ac028f582f94f3ba42fdc4aa99b7500.png