#includeusing namespace std; #include template struct Node { int _data; Node* _next; Node(const T& x) :_data(x) , _next(NULL) {} }; template class PlinkList { public: PlinkList() :_head(NULL) {} void PushBack(const T& x) { if (_head == NULL) { _head = new Node (x); _tail = _head; } else { Node * tmp = new Node (x); Node * cur = _head; while (cur->_next) { cur = cur->_next; } tmp->_next = cur->_next; cur->_next = tmp; _tail = tmp; } } Node * JosephusCycle(int k)//约瑟夫环问题 { assert(_head); _tail->_next = _head; Node * begin = _head; while (1) { if (begin->_next == begin) break; int count = k - 1; while (count-- > 0) { //del = begin; begin = begin->_next; } Node * del = begin->_next; //swap(begin->_data, begin->_next->_data); begin->_next = del->_next; begin = begin->_next; delete del; } return begin; } void Find_comm(Node * one, Node * two)//找两个已排好序链表的相同数 { assert(one && two); Node * cur1 = one; Node * 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 * Find_CenterNode() //查找链表的中间节点 { assert(_head); Node * slow = _head; Node * 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 * cur = _head; while (cur) { cur = cur->_next; count++; } if (pos<0 || pos>count) return false; if (pos == count)//如果要删除的为头结点 { Node * del = _head; _head = _head->_next; delete del; return true; } /*else //采用快慢指针让快指针先走pos步,慢指针再走 { Node * slow = _head; Node * fast = _head; Node * prev = _head; int k = 0; while (fast) { if (k >= pos) { prev = slow; slow = slow->_next; } fast = fast->_next; k++; } Node * del = slow; prev->_next = del->_next; delete del; return true; }*/ else //也可走count-pos步并记录该位置的前一个位置 { count = count - pos ; int num = 0; Node * prev = _head; Node * 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 * del = cur; tmp->_next = del->_next; delete del; return true; } } Node * reverse()//逆置单链表 { assert(_head); if (_head->_next == NULL) return _head; Node * cur = _head; Node * newHead = NULL; while (cur) { Node * tmp = cur; cur = cur->_next; tmp->_next = newHead; newHead = tmp; } return newHead; } void PrintTailTohead(Node * head)//从尾到头打印单链表 { if (head == NULL) return; else { PrintTailTohead(head->_next); cout << head->_data<<"->"; } } void Display() { assert(_head); Node * cur = _head; while (cur) { cout << cur->_data << "->"; cur = cur->_next; } cout << "NULL" << endl; } void Bubble_sort()//链表的冒泡排序 { assert(_head); Node * prev = _head; Node * end = NULL; while (prev->_next) //控制排序次数 { Node * 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 * Quicksort(Node * begin, Node * end) { Node * prev = begin; Node * 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 * begin, Node * end) { if (begin != end) { Node * tmp = Quicksort(begin, end); Quick_sort(begin, tmp); Quick_sort(tmp->_next, end); } } ~PlinkList() { if (_head == NULL) return; Node * cur = _head; while (cur) { Node * del = cur; cur = cur->_next; delete del; } _head = NULL; } public: Node * _head; Node * _tail; }; //void Test() //{ // PlinkList 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< _data<
分享题目:单链表的相关问题
网址分享:http://cdkjz.cn/article/igsope.html