您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
一般这样的题,链表肯定不会是一个双向链表还带个循环什么的,也就是只给一个单链表的头结点,然后从尾到头输出每个结点的值;
如果从前往后去找最后一个结点,那找到了输出然后就没办法往返回往头部访问了,因为只是个单链表;因此可以想到,用递归来实现:
#include <iostream> using namespace std; template <class T> //将链表的结点定义为模板类,实现代码的复用性 struct ListNode { T _data; ListNode<T>* _next; }; template <class T> ListNode<T>* buy_node(T data) //创建结点 { ListNode<T>* tmp = new ListNode<T>; tmp->_data = data; tmp->_next = NULL; return tmp; } template <class T> void init_list(ListNode<T>** node, T data) //链表的初始化 { *node = buy_node(data); } template <class T> void push_node(ListNode<T>*& head, T data) //向链表中插入结点 { if(head == NULL) { init_list(&head, data); return; } ListNode<T>* tmp = head; while(tmp->_next != NULL) { tmp = tmp->_next; } tmp->_next = buy_node(data); } template <class T> void destroy_list(ListNode<T>*& head) //销毁链表 { if(head != NULL) { ListNode<T>* cur = head; ListNode<T>* tmp = head; while(cur != NULL) { tmp = cur; cur = cur->_next; delete tmp; } head = NULL; } } template <class T> void print_list(ListNode<T>* head) //正序打印链表的数据 { while(head != NULL) { cout<<head->_data<<"->"; head = head->_next; } cout<<"NULL"<<endl; } template <class T> void ReversePrintList(ListNode<T>* head) //逆序打印链表,用递归 { if(head != NULL) { ReversePrintList(head->_next); cout<<head->_data<<"->"; } else cout<<"NULL->"; } int main() { ListNode<int>* list = NULL; push_node(list, 1); push_node(list, 2); push_node(list, 3); push_node(list, 4); push_node(list, 5); push_node(list, 6); push_node(list, 7); push_node(list, 8); push_node(list, 9); cout<<"print list: "; print_list(list); cout<<"reverse print list: "; ReversePrintList(list); cout<<endl; destroy_list(list); return 0; }
上面的栗子中只为了完成题目要求并没有实现链表的其他操作,比如pop数据以及查找删除插入等函数,运行程序可得如下结果:
从上面的程序可以知道,将链表逆序输出其实就是后插入的结点先输出,最开始放进去的结点最后输出,因此也就是后进先出的原则,可以用栈来实现,从头开始遍历链表,将结点一一push_back进栈里面,然后再从栈顶取出数据,取到的就是链表的最后一个结点,再不断地pop数据然后取栈顶;
上面的程序中用的是非类的变量,下面可以定义一个链表类来实现,而且当程序运行完后不用手动调用析构函数释放空间:
#include <iostream> #include <vector> using namespace std; template <class T> struct ListNode //链表结点结构体 { T _data; ListNode<T>* _next; ListNode(T data) :_data(data) ,_next(NULL) {} }; template <class T> class List //实现一个链表类 { public: List() //默认构造函数 :_head(NULL) {} List(T data) //带参的构造函数 :_head(new ListNode<T>(data)) {} ~List() //析构函数,释放链表结点空间 { if(_head != NULL) { ListNode<T>* tmp = _head; ListNode<T>* cur = _head; while(cur != NULL) { tmp = cur; cur = cur->_next; delete tmp; } _head = NULL; } } void _push(T data) //在链表尾部push数据 { if(_head == NULL) { _head = new ListNode<T>(data); return; } ListNode<T>* tmp = _head; while(tmp->_next != NULL) tmp = tmp->_next; tmp->_next = new ListNode<T>(data); } void print_list() //正序输出链表 { ListNode<T>* tmp = _head; while(tmp != NULL) { cout<<tmp->_data<<"->"; tmp = tmp->_next; } cout<<"NULL"<<endl; } void ReversePrintList() //逆序输出链表 { vector<T> list; ListNode<T>* tmp = _head; while(tmp != NULL) //将链表结点依次放入栈中 { list.push_back(tmp->_data); tmp = tmp->_next; } cout<<"reverse print list:"<<endl; while(!list.empty()) //不断地取栈顶元素,释放栈顶元素 { cout<<list.back()<<"->"; list.pop_back(); } cout<<"NULL"<<endl; } private: ListNode<T>* _head; }; int main() { List<int> list(1); list._push(2); list._push(3); list._push(4); list._push(5); list._push(6); list._push(7); list._push(8); list._push(9); list.print_list(); list.ReversePrintList(); return 0; }
运行程序可得如下结果:
《完》
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。