温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

C++如何自定义单向链表ListNode

发布时间:2022-03-23 11:22:35 来源:亿速云 阅读:320 作者:小新 栏目:开发技术

小编给大家分享一下C++如何自定义单向链表ListNode,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

 链表有两种:

  •  1、带头结点,头结点存放的是链表的长度,从第二个节点开始存放数据。

  •  2、不带头结点,没有存放链表长度的节点,从头结点开始就存放数据。

小编这里定义的链表是第二种。

直接上代码:

#include <iostream>
#include <assert.h>
#include <vector>
#include <algorithm>
using namespace std;

struct ListNode
{
    int val;   //当前节点的值
    ListNode *next;   //指向下一个节点的指针
    ListNode() : val(0), next(nullptr) {}   //初始化当前结点值为默认值0,指针为空
    ListNode(int x) : val(x), next(nullptr) {}    //初始化当前结点值为x,指针为空
    ListNode(int x, ListNode *next) : val(x), next(next) {}    //初始化当前结点值为x,下一个绩点为next
};


class Solution
{
public:
    //创建长度为len的单向链表
    void createList(ListNode *head,int len){
        for(int i=1;i<len;i++)   //len-1个节点,加上head节点共len个
        {
            ListNode *node=new ListNode;   //每次都需要实例化一个ListNode
            node->val=i*i;    //为节点赋值
            node->next=nullptr;
            head->next=node;   //head指向下一个节点(即当前节点)
            head=node;     //将当前节点设为head
        }
        cout<<"Create a new ListNode with len of "<<len<<" successfully."<<endl;
    }

    //打印链表(顺序)
    void printList(ListNode *head){
        if(head==nullptr)        
            cout<<"empty list."<<endl;
        else
            while(head!=nullptr)
            {
                cout<<head->val<<'\t';
                head=head->next;
            }
        cout<<endl;
    }

    //打印链表(逆序)
    void reversePrintList(ListNode *head){
        //因为ListNode只能根据next单向索引,无法逆向回溯,所以只能将节点数值存在vector中反向输出。
        //目前只想到了这种方法。
        if(head==nullptr)
        {
            cout<<"empty list."<<endl;
            exit(1);
        }
        else
        {
            vector<int> node;
            while(head!=nullptr)
            {
                node.push_back(head->val);
                head=head->next;
            }
            while(!node.empty())
            {
                //先输出node中的最后一个元素,再删除最后一个元素。而不是先对node做reverse再正向输出。
                cout<<node.back()<<'\t';
                node.pop_back();
            }
            cout<<endl;
        }
    }

    //在链表尾节点添加一个新节点
    void pushBack(ListNode *head,int val){
        ListNode *node=new ListNode(val,nullptr);   //要添加的新节点
        if(head==nullptr)
            head=node;
        else
        {
            while(head->next!=nullptr)    //while循环结束后head就是尾结点了
                head=head->next;
            head->next=node;
        }
    }

    //更改链表尾节点数值
    void changeBackValue(ListNode *head,int val){
        assert(head!=nullptr);
        while(head->next!=nullptr)    //while循环结束后head就是尾结点了
            head=head->next;
        head->val=val;
    }

    //删除链表尾节点
    void popBack(ListNode *head){
        assert(head!=nullptr);
        while(head->next->next!=nullptr)   //while循环结束后head是倒数第二个节点,其next指向尾节点
            head=head->next;
        head->next=nullptr;   //删除尾节点
        //注意不要直接delete尾结点,因为尾结点的next是nullptr,直接delete nullptr会输出很多乱码。
    }

    //删除链表中节点值等于指定值的节点(不包括头节点)
    void deleteNode(ListNode *head, int val) {
        assert(head != nullptr);
        ListNode *node = head;    //copy一份链表
        while (head->next != nullptr)
        {
            if (head->next->val == val)
                node->next=head->next->next;
            head=head->next;
            node=node->next;
        }
    }

    //清空列表
    void clearList(ListNode *head){
        head->next=nullptr;   //清楚头结点之后的所有节点
        //清空列表的功能一直不知道怎么实现,头结点不知道怎么删除。
    }
};


int main()
{
    Solution solution;
    ListNode *listnode=new ListNode(5,nullptr);   //初始化链表的head节点
    solution.printList(listnode);           // 5
    solution.createList(listnode,5);   
    solution.printList(listnode);           // 5       1       4       9       16
    solution.pushBack(listnode,30);
    solution.printList(listnode);           // 5       1       4       9       16      30
    solution.reversePrintList(listnode);    // 30      16      9       4       1       5
    solution.changeBackValue(listnode,88);
    solution.printList(listnode);           // 5       1       4       9       16      88
    solution.popBack(listnode);
    solution.printList(listnode);           // 5       1       4       9       16
    solution.pushBack(listnode,101);
    solution.printList(listnode);           // 5       1       4       9       16      101
    solution.deleteNode(listnode,9);
    solution.printList(listnode);           // 5       1       4       16      101
    solution.clearList(listnode);
    solution.printList(listnode);           // 5
    cout<<"END"<<endl;
    return 0;
}

程序输出:

5
Create a new ListNode with len of 5 successfully.
5       1       4       9       16
5       1       4       9       16      30
30      16      9       4       1       5
5       1       4       9       16      88
5       1       4       9       16
5       1       4       9       16      101
5       1       4       16      101
5
END

以上是“C++如何自定义单向链表ListNode”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c++
AI