Cai Dat Danh Sach Lien Ket Kep

// CaiDat_DSLK_Kep.cpp : Defines the entry point for the console application.
// DSLKK : o day la vi du ve doan tau, cac toa tau : hang khac va so ghe trong 1 toa

#include "stdafx.h"
#include <iostream>
#include <conio.h>

//Dinh nghia kieu toa tau
typedef struct {
    int number_of_seats;// Tong so ghe ngoi
    int number_of_passenger;// So hanh khach tren toa
} railroad_car;
typedef struct node{
    railroad_car infor;
    node *left;
    node *right;
} *dlist;

//KHoi tao DSLK
void init(dlist *l){
    *l= NULL;
}

//Nhap vao 1 toa tau
void inputRC(railroad_car &rc){
    printf("\n\n Nhap vao so ghe ngoi: ");
    scanf("%d",&rc.number_of_seats);
    printf("\n Nhap vao so hanh khach: ");
    scanf("%d",&rc.number_of_passenger);
    fflush(stdin);
}

//Hien thi 1 toa tau
void show(railroad_car rc, int i){
    printf("\n\n Toa thu %d: ",i);
    printf("\n So ghe ngoi:   %d",rc.number_of_seats);
    printf("\n So hanh khach: %d",rc.number_of_passenger);
}

//Duyet sang trai
void travel_left(dlist *l){
    dlist p= *l;
    int i= 1;
    while(p!= NULL){
        show(p->infor,i);
        i++;
        p= p->left;
    }
}
//Duyet sang phai
void travel_right(dlist *l){
    dlist p= *l;
    int i=1;
    //Chuyen p toi cuoi danh sach
    while(p->left!= NULL){
        p= p->left;
        i++;
    }
    while(p!= NULL){
        show(p->infor,i);
        i--;
        p= p->right;
    }
}
//=============== Them =================
//Them vao 1 node tren cung
void add_top(dlist *l){
    railroad_car rc;
    inputRC(rc);
    dlist p= *l;//p o dau danh sach
    dlist add = new node;//add la node can them vao
    add->infor= rc;
    add->left= p;
    if(p!= NULL)
        p->right= add;
    add->right= NULL;
    *l= add;//gan *l len dau danh sach
}
//Them 1 node vao cuoi
void add_bottom(dlist *l){
    railroad_car rc;
    inputRC(rc);//Nhap thong tin
    dlist p= *l;//p o dau danh sach
    dlist add = new node;//add la node can them vao
    add->infor = rc;
    //Neu danh sach rong
    if(p== NULL){
        add->left= NULL;
        add->right= NULL;
        *l= add;
    }
    else{
        //Duyet toi cuoi danh sach
        while(p->left!=NULL)
            p= p->left;
        //p dang o cuoi danh sach
        add->left= NULL;
        p->left= add;
        add->right= p;
    }
}
//Them 1 node vao giua
void add_before(dlist *l){
    int n,i=1;
    dlist p= *l;
    printf("\n Nhap vi tri ban muon them vao truoc: ");
    scanf("%d",&n);
    while(p!= NULL && i<n ){
        p= p->left;
        i++;
    }
    if(p== NULL || n<1){//Neu ko ton tai vi tri
        printf("\n Vi tri khong hop le ");
        getch();
        return;
    }
    //Neu ton tai vi tri do
    railroad_car rc;
    inputRC(rc);
    dlist add = new node;//add la node can them vao
    add->infor= rc;
        //neu vi tri do la cuoi cung
        if(p->left== NULL){
            add->left= NULL;
            add->right= p;
            p->left= add;
        }
        else{
            dlist q;
            q= p->left;
            //Can them vao giua p va q . p dang o truoc q
                //Noi p voi add
                p->left= add;
                add->right= p;
                //Noi add voi q
                add->left= q;
                q->right= add;
        }
}

//=================Xoa===========================
//Xoa o dau danh sach
void del_top(dlist *l){
    dlist p= *l;
    if(p== NULL){
        printf("\n Danh sach rong !");
        return;
    }
    else{
        if(p->left== NULL){
            delete(p);
            *l= NULL;
        }
        else{
            dlist q= p->left;//q o ben phai p
            delete(p);
            q->right= NULL;
            *l= q;
        }
    }
}

//Xoa o cuoi
void del_bottom(dlist *l){
    dlist p= *l;
    if(p== NULL){
        printf("\n Danh sach rong !");
        return;
    }
    else{
        if(p->left== NULL){
            delete(p);
            *l= NULL;
        }
        else{
            while((p->left)->left!= NULL)
                p= p->left;
            dlist q= p->left;
            delete(q);
            p->left= NULL;
        }
    }
}
//Xoa 1 node truoc 1 node
void del_before(dlist *l){
    int n,i=1;
    dlist p= *l;
    printf("\n Nhap vi tri node ");
    scanf("%d",&n);
    if(p== NULL){
        printf("\n Danh sach rong !");
        return;
    }
    while((p->left)->left!= NULL && i<n){
        p= p->left;
        i++;
    }
    //Neu chi co 1 node
    if(p->left== NULL || n<1){
        printf("\n Vi tri khong chinh xac ");
        return;
    }

    dlist del= p->left;//del la phan tu bi xoa
    //Neu node phai xoa la cuoi cung
    if(del->left== NULL){
        delete(del);
        p->left= NULL;
        return;
    }
    //Sau khi del bi xoa can noi p voi q
    p->left=del->left;printf("\n f gan ");
    (del->left)->right= p;printf("\n f bat dau xoa");
    delete(del);
}


void menu(){
    printf("\n\n============= Danh sach lien ket kep =================\n");
    printf("\n 1. Them vao dau danh sach");
    printf("\n 2. Them vao cuoi danh sach");
    printf("\n 3. Them vao truoc 1 node");
    printf("\n 4. xoa dau danh sach");
    printf("\n 5. Xoa cuoi danh sach");
    printf("\n 6. Xoa 1 node dang truoc 1 node");
    printf("\n 7. Duyet trai");
    printf("\n 8. Duyet phai");
    printf("\n 0. ----- Thoat -----\n");
}
// Ham thuc hien cac chuc nang
void execute(){
    dlist l;
    init(&l);
    char choice;
    do{
        menu();
printf("\n Chon 1 trong cac chuc nang tren \n");
        scanf("%c",&choice);
        if(choice== '0') exit(0);
        fflush(stdin);
            switch(choice){
                case '1':{
                    printf("\n 1. Them vao dau danh sach");
                    add_top(&l);
                    printf("\n      THEM THANH CONG    ");
                    getch();
                }break;

                case '2':{
                    printf("\n 2. Them vao cuoi danh sach");
                    add_bottom(&l);
                    printf("\n      THEM THANH CONG    ");
                    getch();
                }break;

                case '3':{
                    printf("\n 3. Them vao truoc 1 node");
                    add_before(&l);
                    printf("\n      THEM THANH CONG    ");
                    getch();
                }break;

                case '4':{
                    printf("\n 4. xoa dau danh sach");
                    del_top(&l);
                    printf("\n      XOA THANH CONG    ");
                    getch();
                }break;

                case '5':{
                    printf("\n 5. Xoa cuoi danh sach");
                    del_bottom(&l);
                    printf("\n      XOA THANH CONG    ");
                    getch();
                }break;

                case '6':{
                    printf("\n 6. Xoa 1 node");
                    del_before(&l);
                    printf("\n      XOA THANH CONG    ");
                    getch();
                }break;

                case '7':{
                    printf("\n     DUYET TRAI    ");
                    travel_left(&l);
                    getch();
                }break;

                case '8':{
                    printf("\n     DUYET PHAI    ");
                    travel_right(&l);
                    getch();
                }break;
            }
    }while(true);

}
int main(){
    execute();
    return (0);
}