#include<iostream> using namespace std; #include<assert.h> template<class T> struct Node { int _data; Node* _next; Node(const T& x) :_data(x) , _next(NULL) {} }; template<class T> class PlinkList { public: PlinkList() :_head(NULL) {} void PushBack(const T& x) { if (_head == NULL) { _head = new Node<T>(x); _tail = _head; } else { Node<T>* tmp = new Node<T>(x); Node<T>* cur = _head; while (cur->_next) { cur = cur->_next; } tmp->_next = cur->_next; cur->_next = tmp; _tail = tmp; } } Node<T>* JosephusCycle(int k)//约瑟夫环问题 { assert(_head); _tail->_next = _head; Node<T>* begin = _head; while (1) { if (begin->_next == begin) break; int count = k - 1; while (count-- > 0) { //del = begin; begin = begin->_next; } Node<T>* del = begin->_next; //swap(begin->_data, begin->_next->_data); begin->_next = del->_next; begin = begin->_next; delete del; } return begin; } void Find_comm(Node<T>* one, Node<T>* two)//找两个已排好序链表的相同数 { assert(one && two); Node<T>* cur1 = one; Node<T>* cur2 = two; while (cur1 && cur2) { if (cur1->_data > cur2->_data) cur2 = cur2->_next; else if (cur1->_data < cur2->_data) cur1 = cur1->_next; else { cout << cur1->_data << " "; cur1 = cur1->_next; cur2 = cur2->_next; } } cout << "not comm data" << endl; } Node<T>* Find_CenterNode() //查找链表的中间节点 { assert(_head); Node<T>* slow = _head; Node<T>* fast = _head; while (fast && fast->_next) { slow = slow->_next; fast = fast->_next->_next; } return slow; } bool del_thelast_Knode(int pos)//删除倒数第Pos个节点 { int count = 0; Node<T>* cur = _head; while (cur) { cur = cur->_next; count++; } if (pos<0 || pos>count) return false; if (pos == count)//如果要删除的为头结点 { Node<T>* del = _head; _head = _head->_next; delete del; return true; } /*else //采用快慢指针让快指针先走pos步,慢指针再走 { Node<T>* slow = _head; Node<T>* fast = _head; Node<T>* prev = _head; int k = 0; while (fast) { if (k >= pos) { prev = slow; slow = slow->_next; } fast = fast->_next; k++; } Node<T>* del = slow; prev->_next = del->_next; delete del; return true; }*/ else //也可走count-pos步并记录该位置的前一个位置 { count = count - pos ; int num = 0; Node<T>* prev = _head; Node<T>* tmp = prev; cur = _head; while (cur->_next) { if (num + 1 == count) { tmp = cur; cur = cur->_next; break; } cur = cur->_next; //prev = prev->_next; num++; } Node<T>* del = cur; tmp->_next = del->_next; delete del; return true; } } Node<T>* reverse()//逆置单链表 { assert(_head); if (_head->_next == NULL) return _head; Node<T>* cur = _head; Node<T>* newHead = NULL; while (cur) { Node<T>* tmp = cur; cur = cur->_next; tmp->_next = newHead; newHead = tmp; } return newHead; } void PrintTailTohead(Node<T>* head)//从尾到头打印单链表 { if (head == NULL) return; else { PrintTailTohead(head->_next); cout << head->_data<<"->"; } } void Display() { assert(_head); Node<T>* cur = _head; while (cur) { cout << cur->_data << "->"; cur = cur->_next; } cout << "NULL" << endl; } void Bubble_sort()//链表的冒泡排序 { assert(_head); Node<T>* prev = _head; Node<T>* end = NULL; while (prev->_next) //控制排序次数 { Node<T>* tmp = _head; while (tmp->_next != end)//相邻两元素交换单趟排序 { if (tmp->_data > tmp->_next->_data) swap(tmp->_data, tmp->_next->_data); tmp = tmp->_next; } end = tmp; prev = prev->_next; } } Node<T>* Quicksort(Node<T>* begin, Node<T>* end) { Node<T>* prev = begin; Node<T>* cur = begin->_next; int key = begin->_data; while (cur != end) { if (cur && cur->_data < key) { prev = prev->_next; if (prev->_data != cur->_data) swap(prev->_data, cur->_data); } cur = cur->_next; } swap(begin->_data, prev->_data); return prev; } void Quick_sort(Node<T>* begin, Node<T>* end) { if (begin != end) { Node<T>* tmp = Quicksort(begin, end); Quick_sort(begin, tmp); Quick_sort(tmp->_next, end); } } ~PlinkList() { if (_head == NULL) return; Node<T>* cur = _head; while (cur) { Node<T>* del = cur; cur = cur->_next; delete del; } _head = NULL; } public: Node<T>* _head; Node<T>* _tail; }; //void Test() //{ // PlinkList<int> l; // l.PushBack(8); // l.PushBack(3); // l.PushBack(7); // l.PushBack(1); // l.PushBack(9); // l.PushBack(6); // l.PushBack(0); // l.PushBack(5); // //l.Display(); // //l.Quick_sort(l._head, NULL); // //l.Bubble_sort(); // //l._head=l.reverse(); // //l.del_thelast_Knode(8); // //cout << l.Find_CenterNode()->_data << endl; // //l.PrintTailTohead(l._head); // //cout << "NULL" << endl; // cout<<l.JosephusCycle(3)->_data<<endl; // //l.Display(); //}
文章名称:单链表的相关问题
本文网址:https://www.cdcxhl.com/article34/igsope.html
成都网站建设公司_创新互联,为您提供网页设计公司、、品牌网站建设、网站设计公司、网站制作、服务器托管
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联