单链表的排序(快排和冒泡实现)以及查找中间结点
//快排,冒泡链表排序 #include#include using namespace std; template struct LinkNode { T _data; LinkNode* _next; LinkNode(const T& x) :_data(x) , _next(NULL) {} }; template class ListNode { //为了安全性 private: ListNode(const ListNode& l) {} ListNode & operator=(ListNode l) {} public: //程序限制 LinkNode * _head; public: ListNode() :_head(NULL) {} ~ListNode() { while (_head) { PopBack(); } } void PushBack(const T& x) { LinkNode * tmp = new LinkNode (x); if (_head == NULL) _head = tmp; else { LinkNode * cur = _head; while (cur->_next) cur = cur->_next; cur->_next = tmp; } } void PopBack() { if (_head == NULL) return; if (_head->_next == NULL) { delete _head; _head = NULL; } else { LinkNode * cur = _head; while (cur->_next&&cur->_next->_next) { cur = cur->_next; } LinkNode * del = cur->_next; cur->_next = NULL; delete del; } } LinkNode * Search(const T& x) { if (_head == NULL) return NULL; LinkNode * cur = _head; while (cur->_data != x) cur = cur->_next; return cur; } void Print() { LinkNode * cur = _head; while (cur) { cout << cur->_data << " "; cur = cur->_next; } cout << endl; } }; template LinkNode * QuickPartion(LinkNode * begin,LinkNode * end)//前闭后开 { if (begin== end) return begin; LinkNode * prev,* cur; prev = begin; cur = begin->_next; int tmp = begin->_data; while (cur != end) { if(cur->_data < tmp) { prev = prev->_next; if (cur!=prev) swap(cur->_data, prev->_data); } cur = cur->_next; } swap(prev->_data, begin->_data); return prev; } template void QuickSort(LinkNode * head,LinkNode * tail) { if (head == NULL || head-== tail) return; LinkNode * mid = QuickPartion(head, tail); QuickSort(head, mid); QuickSort(mid->_next, tail); } template void BubbleSort(LinkNode * head) { if (head == NULL || head->_next == NULL) return; LinkNode * start = head; LinkNode * end = NULL; LinkNode * curBegin = NULL; int flag = 0; while (start->_next) { curBegin = start; flag = 0; while (curBegin->_next != end) { if (curBegin->_data > curBegin->_next->_data) { swap(curBegin->_data, curBegin->_next->_data); flag = 1; } curBegin = curBegin->_next; } if (flag == 0) break;//优化,若有序,直接跳出 end = curBegin; } } template LinkNode * SearchMidNode(LinkNode * head) { if (head == NULL || head->_next == NULL) return head; LinkNode * slow = head; LinkNode * fast = head; while (fast&&fast->_next)//偶数个数中间任意一个 //while (fast&&fast->_next&&fast->_next->_next)//偶数个数找到中间的第一个 { fast = fast->_next->_next; slow = slow->_next; } return slow; } void Test1() { ListNode l1; l1.PushBack(10); l1.PushBack(9); l1.PushBack(8); l1.PushBack(7); l1.PushBack(6); l1.PushBack(6); l1.PushBack(5); l1.PushBack(9); l1.PushBack(0); l1.PushBack(1); l1.PushBack(2); /*LinkNode * tail = NULL; QuickSort(l1._head,tail);*/ //BubbleSort(l1._head); cout << SearchMidNode(l1._head)->_data<< endl; l1.Print(); }
分享标题:单链表的排序(快排和冒泡实现)以及查找中间结点
网站路径:http://scyanting.com/article/peipic.html