Sap xep 2 danh sach lien ket
#include
#include
#include
#include
//using namespace std;???????????/
typedef struct tagNode{
int data;
tagNode *next;
} NODE;
typedef struct tagList{
NODE * head;
NODE * tail;
} LIST;
///
void Khoitao(LIST &l){
l.head = l.tail = NULL;
}
NODE*GetNode(int x){
NODE*t = new NODE;
t->data = x;
t->next = NULL;
return t;
}
/*Chen mot phan tu vao danh sach*/
// Chen dau
void AddFirst(LIST &l, int x)
{
NODE*add = GetNode(x);
if(l.head == NULL)
{
l.head = l.tail = NULL;
return;
}
else
{
add->next = l.head;
l.head = add;
}
}
//Chen cuoi
void AddEnd(LIST &l, int x)
{
NODE*add = GetNode(x);
if (l.tail == NULL)
{
l.head = l.tail = add;
return;
}
else
{
l.tail->next = add;
l.tail = add;
}
add->next = NULL;
}
//Chen sau q
void AddAfter(LIST &l, NODE*q, int x)
{
NODE*p = GetNode(x);
if(l.head == NULL)
{
AddFirst(l, x);//hoac AddEnd(l, x);
return;
}
if(q != NULL)
{
p->next = q->next;
q->next = p;
if(q == l.tail)
l.tail = p;
}
else
AddEnd(l, x);
}
//Chen tai
void AddAt(LIST &l, int x)
{
if(l.head == NULL || l.head->data == x)
AddFirst(l, x);
//Danh dau node truoc x
NODE*give = NULL;
for(NODE*p = l.head;
p != NULL && p->data == x;
p = p->next)
give = p;
if(p == NULL)
cout<<"
Khong tim thay phan tu "< else//Tai sao lai chen cuoi list ???
AddAfter(l, give, x);
}
//Xoa mot phan tu khoi danh sach*/
//Xoa dau
void RemoveHead(LIST &l)
{
NODE *xoa = l.head;
l.head = l.head->next;
delete xoa;
}
//Xoa cuoi
void RemoveTail(LIST &l)
{
NODE*t = l.tail;
//Xac dinh phan tu gan cuoi
NODE* p = l.head;
while(p->next->next != NULL)
p = p->next;
delete t;
//Gan tail la p
l.tail = p;
if(l.tail != NULL)
l.tail->next = NULL;
else
l.head = NULL;
}
//Xoa sau q
void RemoveAfter(LIST &l, NODE *q)
{
if(l.head == NULL) return;
NODE*p = q->next;
if(p == NULL && q == l.head)
RemoveHead(l);
else
{
q->next = p->next;
delete p;
if(q->next == NULL)
l.tail = q;
}
}
//Xoa tai
void RemoveAt(LIST &l, int x)
{
if(l.head == NULL) return;
if(l.head->data == x)
RemoveHead(l);
NODE*give = NULL;
for(NODE*p = l.head;
p != NULL && p->data == x;
p = p->next)
give = p;
if(p == NULL)
cout<<"
Khong tim thay phan tu "<< x;
else//Khong hoat dong ???
RemoveAfter(l,give);
}
void RemoveAll(LIST &l)
{
NODE *p;
while (l.head!= NULL)
{
p = l.head;
l.head = p->next;
delete p;
}
l.tail = NULL;
}
/*Duyet*/
//Duyet tuan tu
void Print_List(LIST l)
{
for(NODE*p = l.head; p != NULL; p = p->next)
cout<<"\t"<data;
}
//Duyet nguoc
void Print_Opposite(NODE*p)
{//Xuat tu trong xuat ra
if(p!=NULL)
{
Print_Opposite(p->next);
cout<data<<"\t";
}
}
/*Sap xep*/
// Quick Sort
void ListQSort(LIST &l)
{
NODE *p, *x;
LIST l1, l2;
if(l.head == l.tail) return; //da co thu tu
//khoi tao 2 day con
l1.head = l1.tail = NULL;
l2.head = l1.tail = NULL;
x = l.head;
l.head = x->next;
//tach l thanh l1, l2
while(l.head != NULL)
{
//tach p tu dau xau
p = l.head;
l.head = p->next;
p->next = NULL;
if(p->data <= x->data)
AddEnd(l1, p->data);
else
AddEnd(l2, p->data);
}
ListQSort(l1);
ListQSort(l2);
//Noi l1, x, l2 lai thanh l da sap xep
if(l.head != NULL)
{
l.head = l1.head;
l1.tail->next = x;
}
else
l.head = x;
x->next = l2.head;
if(l2.head != NULL)
l.tail = l2.tail;
else
l.tail = x;
}
//MergeSort
void DistributeList(LIST &l, LIST &l1, LIST &l2)
{
NODE *p;
//tach l thanh l1, l2
do{
p = l.head;
l.head = p->next;
p->next = NULL;
AddEnd(l1, p->data);
} while ((l.head) && (p->data <= l.head->data));
if(l.head)
DistributeList(l, l2, l1);
else
l.tail = NULL;
}
void MergeList(LIST& l,LIST& l1,LIST& l2)
{
NODE *p;
while((l1.head)&&(l2.head))
{
if(l1.head->data <= l2.head->data){
p = l1.head;
l1.head = p->next;
}
else {
p = l2.head;
l2.head = p->next;
}
p->next = NULL;
AddEnd(l, p->data);
};
//Noi phan tu con lai cua l1 vao cuoi l
if(l1.head){
l.tail->next = l1.head;
l.tail = l1.tail;
}
//Noi phan tu con lai cua l2 vao cuoi l
else if(l2.head){
l.tail->next = l2.head;
l.tail = l2.tail;
}
}
void ListMergeSort(LIST &l)
{
LIST l1, l2;
if(l.head == l.tail) return; //da co thu tu
//Khoi Tao
l1.head = l1.tail = NULL;
l2.head = l2.tail = NULL;
//Phan phoi l thanh l1, l2
DistributeList(l, l1, l2);
ListMergeSort(l1);
ListMergeSort(l2);
//Tron l1, l2 da co thu tu thanh l
MergeList(l, l1 ,l2);
}
/*Tim kiem*/
//Tim tuan tu
NODE *Search(LIST l, int x)
{
NODE *p = l.head;
while((p!= NULL)&&(p->data != x))
p = p->next;
return p;
}
//Tim nhi phan
NODE *SearchBinary(LIST l, int x)
{
NODE *p = l.head;
/////////???????????
return p;
}
char menuAdd()
{
system("cls");
cout<<"
1. Chen dau!";
cout<<"
2. Chen cuoi!";
cout<<"
3. Chen tai x!";
cout<<"
Chuc nang ban chon: "< fflush(stdin);
char ch=getch();
return ch;
}
char menuRemove()
{
system("cls");
cout<<"
1. Xoa dau!";
cout<<"
2. Xoa cuoi!";
cout<<"
3. Xoa tai x!";
cout<<"
4. Xoa het node!";
cout<<"
Chuc nang ban chon: "< fflush(stdin);
char ch=getch();
return ch;
}
char menuPrint()
{
system("cls");
cout<<"
1. Xuat!";
cout<<"
2. Xuat nguoc!";
cout<<"
Chuc nang ban chon: "< fflush(stdin);
char ch=getch();
return ch;
}
char menuSorting()
{
system("cls");
cout<<"
1. QuickSort!";
cout<<"
2. MergeSort!";
cout<<"
Chuc nang ban chon: "< fflush(stdin);
char ch=getch();
return ch;
}
char menu()
{
system("cls");
cout<<"
1. Chen!";
cout<<"
2. Xoa!";
cout<<"
3. Xem!";
cout<<"
4. Sap xep!";
cout<<"
5. Tim!";
cout<<"
Chuc nang ban chon: "< fflush(stdin);
char ch=getch();
return ch;
}
void main()
{
LIST l;
NODE *q = new NODE;
l.head = l.tail = NULL;
int n, x;
do{
cout<<"
Nhap so phan tu :\t";
cin>>n;
} while(n <= 0);
for(int i = 0; i < n; i++)
{
cout<<"\tNhap phan tu thu "< cin>>x;
AddEnd(l, x);
}
do{
char c = menu();
if(c == '1')
{
do {
cout<<"
Nhap tri can chen : ";
cin>>x;
char ch = menuAdd();
if (ch == '1') AddFirst(l, x);
if (ch == '2') AddEnd(l, x);
if (ch == '3') AddAt(l ,x);
cout<<"
Print ESC to exit"< } while (getch() != 27);
}
if(c == '2')
{
do {
char ch = menuRemove();
if (ch == '1') RemoveHead(l);
if (ch == '2') RemoveTail(l);
if (ch == '3')
{
cout<<"
Nhap tri can xoa : ";
cin>>x;
RemoveAt(l ,x);
}
if(ch == '4') RemoveAll(l);
cout<<"
Print ESC to exit"< } while (getch() != 27);
}
if(c == '3')
{
do {
char ch = menuPrint();
cout<<"
Danh sach moi : ";
if (ch == '1') Print_List(l);
if (ch == '2') Print_Opposite(l.head);
cout<<"
Print ESC to exit"< } while (getch() != 27);
}
if(c == '4')
{
do{
char ch = menuSorting();
if(ch == '1')
ListQSort(l);
if(ch == '2')
ListMergeSort(l);
cout<<"
Printf ESC to exit"< } while(getch() != 27);
}
if(c == '5')
{
cout<<"
Nhap phan tu can tim kiem:";
cin>>x;
Search(l, x);
}
cout<<"
Print ESC to exit"< }while(getch() != 27);
}
Bạn đang đọc truyện trên: AzTruyen.Top