DSLK

#include<iostream>
using namespace std;

struct node
{
    int data;
    node *pNext;
};

struct list
{
    node *pHead;
    node *pTail;
};
void KhoiTao(list &l)
{
    l.pHead = l.pTail = NULL;
}

node* KhoiTaonode(int x)
{
    node *p = new node;
    if (p==NULL)
    {
        return NULL;
    }
    else
    {
        p->data = x;
        p->pNext = NULL;
    }
    return p;
}

void AddHead(list &l, node *p)
{
    if (l.pHead==NULL)
    {
        l.pHead = l.pTail = p;
    }
    else
    {
        p->pNext = l.pHead;
        l.pHead = p;
    }
}

void AddTail(list &l, node *p)
{
    if (l.pHead==NULL)
    {
        l.pHead = l.pTail = p;
    }
    else
    {
        l.pTail->pNext = p;
        l.pTail = p;
    }
}
void Xuat(list l)
{
    for (node *k=l.pHead ; k!=NULL; k=k->pNext)
    {
        cout << "  " << k->data;
    }
}
void themsauQ(list &l,node *p)
{
    int x;
    cout << "Nhap gia tri node q";
    cin >> x;
    node *q = KhoiTaonode(x);
    //neu danh sach chi co 1 phan tu va phan tu do cung chinh la node q =>bai toan tro thanh  add tail
    if (q->data==l.pHead->data&&l.pHead->pNext==NULL)
    {
        AddTail(l, p);
    }
    else
    {
        for (node *k=l.pHead;k!=NULL;k=k->pNext)
        {
            if (q->data == k->data)
            {
                node *h = KhoiTaonode(p->data);//Phải thêm qua 1 node trung gian
                node *g = k->pNext;//Phải thêm qua 1 node trung gian
                h->pNext = g;
                k->pNext = h;
            }
        }
    }
}
void ThemtruocQ(list &l,node *p)
{
    int x;
    cout << "\nNhap gia tri node q";
    cin >> x;
    node *q = KhoiTaonode(x);
    node *t = new node;
    if (q->data==l.pHead->data&&l.pHead->pNext==NULL)
    {
        AddHead(l, p);
    }
    else
    {
        for (node *k = l.pHead; k != NULL; k = k->pNext)
        {
            if (k->data==q->data)
            {
                node *g = KhoiTaonode(p->data);
                g->pNext = k;
                t->pNext = g;
            }
            t = k;
        }
    }
}
void addvaovtbatky(list &l, node *p, int vt)
{
    //lay so luong node trong ds
    int n = 0;
    for ( node *k=l.pHead;k!=NULL;k=k->pNext)
    {
        n++;
    }
    //danh sach rong
    if (l.pHead==NULL||vt==1)
    {
        AddHead(l, p);
    }
    else if (vt == n + 1)
    {
        AddTail(l, p);
    }
    else
    {

        //int x;
        ///*cout << "\nNhap gia tri node q";*/
        //cin >> x;
    /*  node *q = KhoiTaonode(x);*/
        node *t = new node;
            int dem = 0;
            for (node *k = l.pHead; k != NULL; k = k->pNext)
            {
                dem++;
                if (vt==dem)
                {
                    node *g = KhoiTaonode(p->data);
                    g->pNext = k;
                    t->pNext = g;
                    break;
                }
                t = k;
            }

    }
}
void XoaDau(list &l)
{
    if (l.pHead==NULL)
    {
        return;
    }
    else
    {
        node *p = l.pHead;
        l.pHead = l.pHead->pNext;
        delete p;
    }
}

void XoaCuoi(list &l)
{
    if (l.pHead==NULL)
    {
        return;
    }
    else
    {
        for (node *k=l.pHead;k!=NULL;k=k->pNext)
        {
            if (k->pNext==l.pTail)
            {
                delete l.pTail;
                k->pNext = NULL;
                l.pTail = k;
            }
        }
    }
}

void xoasaonodeq(list &l, node *q)
{
    /*int x;
    cout << "\Nhap gia tri node q can xoa";
    cin >> x;
    node *q = KhoiTaonode(x);*/
    for (node *k=l.pHead;k!=NULL;k=k->pNext)
    {
        if (q->data == k->data)
        {
            node*p = k->pNext;
            k->pNext = p->pNext;
            delete p;
        }
    }
}
//void xoa1nodep(list &l, node *p)
//{
//  node *t;
//  if (p->pNext!=NULL)
//  {
//      t = p->pNext;
//      p->pNext = t->pNext;
//      free(t);
//  }
//}
void XoaNodeKhoakBatky(list &l, int x)
{
    node *g = new node;
    if (l.pHead->data==x)
    {
        XoaDau(l);
    }
    else if (l.pTail->data == x)
    {
        XoaCuoi(l);
    }
    else
    {
        for (node *k = l.pHead; k != NULL; k = k->pNext)
        {
            if (k->data==x)
            {
                g->pNext = k->pNext;
                delete k;
                return;
            }
            g = k;
        }
    }
}

void XoaTrungnhau(list &l)
{
    for (node *k=l.pHead;k!=l.pTail;k=k->pNext)
    {
        for (node *g = k->pNext; g != NULL;g=g->pNext)
        {
            if (k->data==g->data)
            {
                XoaNodeKhoakBatky(l, g->data);
            }
            g = g->pNext;
        }
    }

}
void Menu(list &l)
{
    while(69)
    {
    system("cls");
    int luachon;
    cout << "\n\n\t\t====== Menu ======";
    cout << "\n\t1. Nhap node vao danh sach";
    cout << "\n\t2. Xuat danh sach lien ket don";
    cout << "\n\t3. Them sau node q";
    cout << "\n\t4. Them truoc node q";
    cout << "\n\t5. Them vao vi tri bat ki";
    cout << "\n\t6. Xoa dau";
    cout << "\n\t7. Xoa cuoi";
    cout << "\n\t8. Xoa sao node q";
    cout << "\n\t9. Xoa phan tu bat ky";
    cout << "\n\t10. Xoa phan tu trung nhau";
    cout << "\n\t11. Thoat" << endl;
    cin >> luachon;
        if (luachon == 1)
        {
            int x;
            cout << "\nNhap gia tri so nguyen: ";
            cin >> x;
            node *p = KhoiTaonode(x);
            AddTail(l, p);
        }
        else if (luachon == 2)
        {
            Xuat(l);
            system("pause");
        }
        else if (luachon == 3)
        {
            int a;
            cout << "\nNhap gia tri p can them";
            cin >> a;
            node *p = KhoiTaonode(a);
            themsauQ(l, p);
        }
        else if (luachon==4)
        {
            int a;
            cout << "\nNhap gia tri p can them";
            cin >> a;
            node *p = KhoiTaonode(a);
            ThemtruocQ(l, p);
        }
        else if (luachon == 5)
        {
            int a;
            cout << "\nNhap gia tri node p";
            cin >> a;
            node *p = KhoiTaonode(a);
            int vt;
            cout << "\nNhap vi tri: ";
            cin >> vt;
            addvaovtbatky(l, p, vt);
        }
        else if (luachon == 6)
        {
            XoaDau(l);
        }
        else if (luachon == 7)
        {
            XoaCuoi(l);
        }
        else if (luachon == 8)
        {
            int x;
            cout << "\Nhap gia tri node q can xoa";
            cin >> x;
            node *q = KhoiTaonode(x);
            xoasaonodeq(l, q);
        }
        else if (luachon == 9)
        {
            int x;
            cout << "\nNhap gia tri can xoa ";
            cin >> x;
            XoaNodeKhoakBatky(l, x);
        }
        else if(luachon==10)
        {
            XoaTrungnhau(l);
        }
        else
        {
            break;
        }
    }
}

int main()
{
    list l;
    KhoiTao(l);
    Menu(l);
    system("pause");
    return 0;
}