#include <iostream>
using namespace std;
///////////////////////////////
struct Node
{
int info;
Node *pNext;
};
struct NodeList
{
Node *pHead;
Node *pTail;
};
Node *newNode(int n)
{
Node *pNew = new Node;
pNew->pNext = NULL;
pNew->info = n;
return pNew;
}
void addToHead(NodeList &list, Node *node)
{
if (list.pHead == NULL)
{
list.pHead = list.pTail = node;
}
else
{
node->pNext = list.pHead;
list.pHead = node;
}
}
void addToTail(NodeList &list, Node *node)
{
if (list.pTail == NULL)
{
list.pHead = list.pTail = node;
}
else
{
list.pTail->pNext = node;
list.pTail = node;
}
}
void input(NodeList &list)
{
int n = 0;
cout << “Nhap vao du lieu: (se dung nhap khi du lieu la so am)” << endl;
while (n >= 0)
{
cin >> n;
addToTail(list, newNode(n));
}
}
void Display(NodeList &list)
{
Node *p = list.pHead;
while( p != NULL)
{
cout << p->info << endl;
p = p->pNext;
}
}
void SapXepTang(NodeList &list)
{
Node *p, *X;
NodeList list1, list2;
if (list.pHead == list.pTail)
{
return;
}
list1.pHead = list1.pTail = NULL;
list2.pHead = list2.pTail = NULL;
X = list.pHead;
list.pHead = X->pNext;
while (list.pHead != NULL)
{
p = list.pHead;
list.pHead = p->pNext;
p->pNext = NULL;
if (p->info <= X->info)
addToTail(list1, p);
else
addToTail(list2, p);
}
SapXepTang(list1);
SapXepTang(list2);
if (list1.pHead != NULL)
{
list.pHead = list1.pHead;
list1.pTail->pNext = X;
}
else
{
list.pHead = X;
}
X->pNext = list2.pHead;
if (list2.pHead != NULL)
{
list.pTail = list2.pTail;
}
else
{
list.pTail = X;
}
}
Node *getHead(NodeList &l)
{
Node *p;
if (l.pHead != NULL)
{
p = l.pHead;
l.pHead = l.pHead->pNext;
p->pNext = NULL;
if (l.pHead == NULL)
{
l.pTail = NULL;
}
}
else
{
return NULL;
}
return p;
}
void Partition(NodeList &l1, NodeList &l2, NodeList &l)
{
Node *p = l.pHead->pNext;
Node* a;
int x;
if (p != NULL)
{
cout << “Nhap vao x bat ki: “;
cin >> x;
while (p != NULL)
{
a = getHead(l);
if(a->info >= x)
{
addToTail(l1, a);
p = p->pNext;
}
else
{
addToTail(l2, a);
p = p->pNext;
}
}
}
}
int main()
{
NodeList list, L1, L2;
list.pHead = NULL;
list.pTail = NULL;
L1.pHead = NULL;
L1.pTail = NULL;
L2.pHead = NULL;
L2.pTail = NULL;
input(list);
cout << “————-Du lieu da nhap————-” << endl;
Display(list);
SapXepTang(list);
cout << “———Du lieu sau khi sap xep———” << endl;
Display(list);
Partition(L1
, L2, list);
cout << “L1 (danh sach nhung du lieu >= x) la: ” << endl;
Display(L1);
cout << “L2 (danh sach nhung du lieu < x) la: ” << endl;
Display(L2);
system(“pause”);
return 0;
}
Mộ Dung Hoa 