小编给大家分享一下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”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。