DSLK Don

// LinkList.cpp
#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;

/*Cau truc thong tin chung ve sinh vien*/
typedef struct
{
   string hoten;
   int msv;
}sinhvien;

/*Cau truc cua mot node trong danh sach lien ket don*/
typedef struct tagNode
{
    sinhvien info;
    struct tagNode* pNext;
}Node;

/*================================= */
typedef struct tagList
{
    Node *pHead;
    Node *pTail;
}LIST;

/*===========Check data=======*/
int checkdata(sinhvien a,sinhvien b)
{
    if((a.hoten==b.hoten)&&(a.msv==b.msv)) return 1;
    return 0;
}
/*==================Khoi dong danh sach lien ket don=============== */
void CreateList(LIST &l)
{
    l.pHead=NULL;
    l.pTail=NULL;
}

/*============Cap phat mien nho cho mot node cua danh sach lien ket don===========*/
Node* CreateNode(sinhvien x)
{
    Node *p;
    p=new Node;
    if(p==NULL) return NULL;
    p->info=x;
    p->pNext=NULL;
    return p;
}
/*==================Them mot node vao dau danh sach lien ket don============*/
void AddHead(LIST &l,Node *p)
{
    if(l.pHead==NULL)
    {
        l.pHead=p;
        l.pTail=l.pHead;
    }
    else
    {
        p->pNext=l.pHead;
        l.pHead=p;
    }
}
/*==================Them mot node vao cuoi danh sach lien ket don============*/
void AddTail(LIST &l,Node *p)
{
    if(l.pHead==NULL)
    {
        l.pHead=p;
        l.pTail=l.pHead;
    }
    else
    {
        l.pTail->pNext=p;
        l.pTail=p;
    }
}
/*==================Them mot node vao sau mot node trong danh sach lien ket don============*/
void AddAfterQ(LIST &l,Node *p,Node *q)
{
    if(q!=NULL)
    {
        q->pNext=p->pNext;
        q->pNext=p;
        if(l.pTail==q)
            l.pTail=p;
    }
    else
    {
        AddHead(l,p);
    }
}
/*==================Huy node dau tien trong DSLK============*/
int RemoveHead(LIST &l,sinhvien &x)
{
    Node *p;
    if(l.pHead!=NULL)
    {
        p=l.pHead;
        x=p->info;
        l.pHead=l.pHead->pNext;
        delete p;
        if(l.pHead==NULL)
            l.pTail=NULL;
        return 1;
    }
    return 0;
}
/*==================Huy node sau node q trong DSLK============*/
int RemoveAfterQ(LIST &l,Node *q, sinhvien &x)
{
    Node *p;
    if(q!=NULL)
    {
        p=q->pNext;
        if(p!=NULL)
        {
            if(p==l.pTail)
                l.pTail=q;
            q->pNext=p->pNext;
            x=p->info;
            delete p;
        }
        return 1;
    }
    else
        return 0;
}
/*==================Huy node co khoa X trong DSLK============*/
int RemoveByKey(LIST &l,sinhvien key)
{
    Node *p,*q=NULL;
    p=l.pHead;
    while((p!=NULL)&&(!checkdata(p->info,key)))
    {
        q=p;
        p=p->pNext;
    }
    if(p==NULL)
    {
        return 0;
    }
    if(q!=NULL)
    {
        RemoveAfterQ(l,q,key);
    }
    else
    {
        RemoveHead(l,key);
    }
            return 1;
}
/*============Tim kiem node chua Key============*/
Node* Search(LIST &l,sinhvien key)
{
    Node *p;
    p=l.pHead;
    while((p!=NULL)&&(!checkdata(p->info,key)))
    {
        p=p->pNext;
    }
    return p;
}
/*===========Huy danh sach==============*/
void RemoveList(LIST &l)
{
    Node *p;
    while(l.pHead!=NULL)
    {
        p=l.pHead;
        l.pHead=l.pHead->pNext;
        delete p;
    }
}
/*============Duyet danh sach=========*/
int PrintList(LIST l)
{
    Node *p;
    if(l.pHead==NULL) return 0;
    int index=1;
    p=l.pHead;
    while(p!=NULL)
    {
        cout<<"\t\tSinh vien thu "<<index++<<":"<<endl;
        cout<<"Ho va ten: "<<p->info.hoten<<endl;
        cout<<"Ma sinh vien: "<<p->info.msv<<endl<<endl;
        p=p->pNext;
    }
    return 1;
}
    /*===============Sap xep danh sach=========*/
/*====Theo ten====*/
void SortByName(LIST &l)
{
    Node *p,*q,*min;
    string temp;
    int tmp;
    p=l.pHead;
    while(p!=l.pTail)
    {
        min=p;
        q=p->pNext;
        while(q!=NULL)
        {
            if(q->info.hoten<min->info.hoten)
                min=q;
            q=q->pNext;
        }
        tmp = min->info.msv;
        temp = min->info.hoten;
        min->info.msv = p->info.msv;
        min->info.hoten = p->info.hoten;
        p->info.msv = tmp;
        p->info.hoten = temp;
        p=p->pNext;
    }
}
/*====Theo ma sinh vien====*/
void SortByMSV(LIST &l)
{
    int tmp;
    string temp;
    Node *p,*q,*min;
    p=l.pHead;
    while(p!=l.pTail)
    {
        min=p;
        q=p->pNext;
        while(q!=NULL)
        {
            if(q->info.msv<min->info.msv)
                min=q;
            q=q->pNext;
        }
        tmp = min->info.msv;
        temp = min->info.hoten;
        min->info.msv = p->info.msv;
        min->info.hoten = p->info.hoten;
        p->info.msv = tmp;
        p->info.hoten = temp;
        p=p->pNext;
    }
}
/*====Theo ten====*/
int QuickSortByName(LIST &l)
{
    LIST l1,l2;
    Node *p,*x;
    if(l.pHead==l.pTail) return 0;
    CreateList(l1);
    CreateList(l2);
    x=l.pHead;
    l.pHead=l.pHead->pNext;
    while(l.pHead!=NULL)
    {
        p=l.pHead;
        l.pHead=p->pNext;
        p->pNext=NULL;
        if(p->info.hoten<=x->info.hoten)
            AddTail(l1,p);
        else
            AddTail(l2,p);
    }
    QuickSortByName(l1);
    QuickSortByName(l2);
    if(l1.pHead!=NULL)
    {
        l.pHead=l1.pHead;
        l1.pTail->pNext=x;
    }
    else
        l.pHead=x;
    x->pNext=l2.pHead;
    if(l2.pHead!=NULL)
        l.pTail=l2.pTail;
    else
        l.pTail=x;
}
/*====Theo ma sinh vien====*/
int QuickSortByMSV(LIST &l)
{
    LIST l1,l2;
    Node *p,*x;
    if(l.pHead==l.pTail) return 0;
    CreateList(l1);
    CreateList(l2);
    x=l.pHead;
    l.pHead=l.pHead->pNext;
    while(l.pHead!=NULL)
    {
        p=l.pHead;
        l.pHead=p->pNext;
        p->pNext=NULL;
        if(p->info.msv<=x->info.msv)
            AddTail(l1,p);
        else
            AddTail(l2,p);
    }
    QuickSortByName(l1);
    QuickSortByName(l2);
    if(l1.pHead!=NULL)
    {
        l.pHead=l1.pHead;
        l1.pTail->pNext=x;
    }
    else
        l.pHead=x;
    x->pNext=l2.pHead;
    if(l2.pHead!=NULL)
        l.pTail=l2.pTail;
    else
        l.pTail=x;
}

int main()
{
    LIST l;
    sinhvien sv;
    Node *q;
    int select;
    CreateList(l);
    do
    {
        cout<<"\n\t THAO TAC VOI DANH SACH SINH VIEN ";
        cout<<"\n\t------------------------------------";
        cout<<"\n\t 1.Them sinh vien vao dau danh sach ";
        cout<<"\n\t 2.Them sinh vien vao cuoi danh sach ";
        cout<<"\n\t 3.Huy sinh vien dau danh sach ";
        cout<<"\n\t 4.Huy sinh vien trong danh sach ";
        cout<<"\n\t 5.Tim sinh vien ";
        cout<<"\n\t 6.Duyet danh sach";
        cout<<"\n\t 7.Sap xep danh sach theo ho ten";
        cout<<"\n\t 8.Sap xep danh sach theo ma sinh vien";
        cout<<"\n\t 9.QuickSort theo ho ten";
        cout<<"\n\t 10.QuickSort theo ma sinh vien";
        cout<<"\n\t 11.Xoa danh sach";
        cout<<"\n\t 0.Thoat ";
        cout<<"\n\n\t #chon (1->n or 0 de thoat): ";
        cin>>select;
        cin.ignore();
        switch(select)
        {
            case 1:
                cout<<"\nHo ten sinh vien: ";
                getline(cin,sv.hoten);
                cout<<"Ma sinh vien: ";
                cin>>sv.msv;
                q=CreateNode(sv);
                if(q!=NULL) AddHead(l,q);
                break;
            case 2:
                cout<<"\nHo ten sinh vien: ";
                getline(cin,sv.hoten);
                cout<<"Ma sinh vien: ";
                cin>>sv.msv;
                q=CreateNode(sv);
                if(q!=NULL) AddTail(l,q);
                break;
            case 3:
                if(RemoveHead(l,sv))
                {
                    cout<<"\nHo ten sinh vien da huy: "<<sv.hoten<<endl;
                    cout<<"Ma sinh vien da huy: "<<sv.msv<<endl;
                }
                else
                    cout<<"Danh sach rong"<<endl;
                break;
            case 4:
                cout<<"\nHo ten sinh vien: ";
                getline(cin,sv.hoten);
                cout<<"Ma sinh vien: ";
                cin>>sv.msv;
                if(!RemoveByKey(l,sv))   cout<<"Khong tim thay sinh vien nay"<<endl;
                else    cout<<"Xoa thanh cong"<<endl;
                break;
            case 5:
                cout<<"\nHo ten sinh vien: ";
                getline(cin,sv.hoten);
                cout<<"Ma sinh vien: ";
                cin>>sv.msv;
                if(Search(l,sv)==NULL)   cout<<"\nKet qua: Khong tim thay sinh vien nay"<<endl;
                else    cout<<"\nKet qua: Tim thay sinh vien trong danh sach"<<endl;
                break;
            case 6:
                if(!PrintList(l)) cout<<"Danh sach rong"<<endl;
                break;
            case 7:
                SortByName(l);
                break;
            case 8:
                SortByMSV(l);
                break;
            case 9:
                QuickSortByName(l);
                break;
            case 10:
                QuickSortByMSV(l);
                break;
            case 11:
                RemoveList(l);
                break;
        }
   // system("pause");
    }
    while(select!=0);
}