#include
using 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://chengdu.cdxwcx.cn/article/igsope.html