欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言实现单链表(不带头结点)的逆序打印

程序员文章站 2022-11-15 08:20:05
我在前面几篇博客中《C语言实现链表节点的插入》《C语言实现链表节点的删除》《C实现头插法和尾插法来构建链表》《C语言实现链表的基本操作》实现了单链表的很多增删改查操作。这里我们要来...

我在前面几篇博客中《C语言实现链表节点的插入》《C语言实现链表节点的删除》《C实现头插法和尾插法来构建链表》《C语言实现链表的基本操作》实现了单链表的很多增删改查操作。这里我们要来实现单链表的逆序打印,使用C来实现。代码上传至 https://github.com/chenyufeng1991/ReverseLinkedList。

基本算法是:

(1)使用尾插法构建原链表;

(2)依次遍历原链表;

(3)取出遍历中的节点使用头插法建立一个新链表;

(4)打印逆序后的新链表;

原理就是头插法每次插入的节点都是链表的第一个,第一个插入的会变成最后一个,最后一个插入的就成了第一个节点。所以就会造成逆序。

核心代码如下:

//声明逆序后的链表
Node *pReverseList;

//头插法建立逆序后的链表
void HeadInsert(Node *pInsert){
    if (pReverseList == NULL) {
        //这个是第一个节点
        pReverseList = pInsert;
    }else{
        //下面的是头插的语句
        pInsert->next = pReverseList;
        pReverseList = pInsert;
    }
}

//遍历链表并使用头插法构建新链表
void scanList(Node *pNode){
    //首先判断原链表是否为空;
    if (pNode == NULL) {
        printf("%s函数执行,原链表为空,无法逆序输出\n",__FUNCTION__);
    }else{

        Node *pMove;    //该节点用来在原链表中移动
        Node *pInsert;  //该节点为新建的插入节点
        pInsert = (Node *)malloc(sizeof(Node));
        memset(pInsert, 0, sizeof(Node));
        pInsert->next = NULL;

        pMove = pNode;
        while (pMove != NULL) {
            //遍历到每一个节点后,调用头插法函数插入新链表
            pInsert->element = pMove->element;
            HeadInsert(pInsert);

            //为插入的下一个节点分配空间
            pInsert = (Node *)malloc(sizeof(Node));
            memset(pInsert, 0, sizeof(Node));
            pInsert->next = NULL;
            pMove = pMove->next;
        }
        
        printf("%s函数执行,逆序链表完成\n",__FUNCTION__);
    }
}