quan ly tau hoa

/*****************************************************************************
*                Chuong trinh quan ly va dieu hanh tuyen xe lua              *
*               Chuong trinh cai dat danh sach lien ket kep, moi nut         *
*                    cua danh sach duoc cap phat bang mot bien dong          *
* Nguoi viet chuong trinh: Trinh Van Chien                                   *
* SV lop TIN DIA CHAT K55  - MSSV 102 105 0008                               *
*****************************************************************************/

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <iomanip>
using namespace std;

#define TRUE 1
#define FALSE 0

// Khai bao cau truc cua mot doan xe lua
typedef struct doan
{
   char gatruoc[12];
   char gasau[12];
   int chieudai;   // km
   int thoigian;   // thoi gian xe lua chay tren doan, tinh theo gio
};

// Khai bao cau truc cua mot nut
struct node
{
   doan info;
   struct node *left, *right;
};
typedef struct node *NODEPTR;

// Tac vu getnode: cap phat mot nut cho danh sach lien ket kep
NODEPTR getnode(void)
{
   NODEPTR p;
   p = (NODEPTR)malloc(sizeof(struct node));
   return(p);
}

// Tac vu freenode: huy nut da cap phat
void freenode(NODEPTR p)
{
   free(p);
}

// Tac vu initialize: khoi dong danh sach lien ket kep
void initialize(NODEPTR *plist)
{
   *plist = NULL;
}

// Tac vu empty: kiem tra danh sach lien ket kep co bi rong khong
int empty(NODEPTR *plist)
{
   return((*plist == NULL) ? TRUE : FALSE);
}

// Tac vu listsize: xac dinh so nut co trong danh sach lien ket kep
int listsize(NODEPTR *plist)
{
   NODEPTR p;
   int n;
   p = *plist;  // p chi nut dau
   n = 0;
   while(p != NULL)
   {
      p = p->right;
      n++;
   }
   return(n);
}

/* Tac vu nodepointer: xac dinh con tro chi nut thu i (i=0,1,2,...) trong
   danh sach lien ket kep */
NODEPTR nodepointer(NODEPTR *plist, int i)
{
   NODEPTR p;
   int vitri;
   p = *plist;      // p chi nut dau dslk vong
   vitri = 0;
   while(p != NULL && vitri < i)
   {
      p = p->right;
      vitri++;
   }
   return(p);
}

// Tac vu position: xac dinh vi tri cua nut p trong danh sach lien ket kep
int position(NODEPTR *plist, NODEPTR p)
{
    int vitri;
    NODEPTR q;
    q = *plist;
    vitri = 0;
    while(q != NULL && q != p)
    {
        q = q->right;
        vitri++;
    }
    if(q == NULL)
        return(-1);
    return(vitri);
}

// Tac vu push: them nut vao dau danh sach lien ket
void push(NODEPTR *plist, doan x)
{
   NODEPTR p;
   p = getnode();
   p->info = x;
   if(*plist == NULL)  // truong hop danh sach rong
   {
      p->left = NULL;
      p->right = NULL;
      *plist = p;
   }
   else
   {
      // tao lien ket giua p va plist
      p->right = *plist;
      (*plist)->left = p;

      p->left = NULL;
      *plist = p;
   }
}

// Tac vu insertright: them nut moi sau nut p
void insertright(NODEPTR p, doan x)
{
   NODEPTR q, r;  // q la nut can them vao, p la nut truoc, r la nut sau
   if(p == NULL)
      cout<<"Nut p khong hien huu, khong them nut duoc"<<endl;
   else
   {
      q = getnode();
      q->info = x;
      r = p->right;
      // tao hai lien ket giua r va q
      if (r != NULL)
        r->left = q;
      q->right = r;
      // tao hai lien ket giua p va q
      q->left = p;
      p->right = q;
   }
}

// Tac vu insertleft: them nut moi truoc nut p
void insertleft(NODEPTR *plist, NODEPTR p, doan x)
{
   NODEPTR q, r;  // q la nut can them vao, p la nut sau, r la nut truoc
   if(p == NULL)
      cout<<"Nut p khong hien huu, khong them nut duoc"<<endl;
   else
   {
      if(p == *plist)  // them nut vao dau danh sach
         push(plist, x);
      else
      {
         q = getnode();
         q->info = x;
         r = p->left;
         // tao hai lien ket giua r va q
         r->right = q;
         q->left = r;
         // tao hai lien ket giua p va q
         q->right = p;
         p->left = q;
      }
   }
}

// Tac vu pop: xoa nut o dau danh sach lien ket
doan pop(NODEPTR *plist)
{
   NODEPTR p;
   doan x;
   if(empty(plist))  // truong hop danh sach rong
      cout<<"Danh sach rong, khong xoa nut duoc"<<endl;
   else
   {
      p = *plist;  // p la nut can xoa
      x = p->info;
      if((*plist)->right == NULL)  // truong hop danh sach co mot nut
         *plist = NULL;
      else
      {
         *plist = p->right;
         (*plist)->left = NULL;
      }
      freenode(p);
      return(x);
   }
}

// Tac vu delnode: xoa nut co con tro la p
doan delnode(NODEPTR *plist, NODEPTR p)
{
   NODEPTR q, r;
   doan x;
   if(p == NULL)
      cout<<"Nut p khong hien huu, khong xoa nut duoc"<<endl;
   else
   {
      if(*plist == NULL)  // truong hop danh sach rong
         cout<<"Danh sach rong, khong xoa nut duoc";
      else
      {
         if(p == *plist)  // truong hop xoa nut dau
            x = pop(plist);
         else
         {
            x = p->info;
            q = p->left;   // q la nut truoc
            r = p->right;  // r la nut sau
            // tao hai lien ket giua q va r
            r->left = q;
            q->right = r;
            freenode(p);
         }
         return(x);
      }
   }
}

// Tac vu righttraverse: duyet danh sach tu trai sang phai (duyet xuoi)
void righttraverse(NODEPTR *plist)
{
   NODEPTR p;
   int stt;
   if(empty(plist))
      cout<<endl<< "(khong co doan nao)";
   else
   {
      p = *plist;  // p chi nut dau
      stt = 0;
      while(p != NULL)
      {
         cout<<setw(5)<<stt++<<setw(12)<<p->info.gatruoc<<setw(12)<<p->info.gasau<<setw(12)<<p->info.chieudai<<setw(7)<<p->info.thoigian<<endl;
         p = p->right;
      }
   }
}

// Tac vu lefttraverse: duyet danh sach tu phai sang trai (duyet nguoc)
void lefttraverse(NODEPTR *plist)
{
   NODEPTR p;
   int stt;
   if(empty(plist))
      cout<<endl<< "(khong co doan nao)";
   else
   {
      stt = 0;
      p = nodepointer(plist, listsize(plist)-1);  // p chi nut cuoi
      while(p != NULL)
      {
         cout<<setw(5)<<stt++<<setw(12)<<p->info.gatruoc<<setw(12)<<p->info.gasau<<setw(12)<<p->info.chieudai<<setw(7)<<p->info.thoigian<<endl;
         p = p->left;
      }
   }
}

// Tac vu search1: tim ga truoc cua mot doan
NODEPTR search1(NODEPTR *plist, char x[])
{
   NODEPTR p;
   p = *plist;
   while(strcmp(p->info.gatruoc, x) != 0 && p != NULL)
      p = p->right;
   return(p);
}

// Tac vu search2: tim ga sau cua mot doan
NODEPTR search2(NODEPTR *plist, char x[])
{
   NODEPTR p;
   p = *plist;
   while(strcmp(p->info.gasau, x) != 0 && p != NULL)
      p = p->right;
   return(p);
}

// Tac vu clearlist: xoa toan bo danh sach lien ket kep
void clearlist(NODEPTR *plist)
{
   while(*plist != NULL)
      pop(plist);
}

void baolotrinh(NODEPTR *plist, char noidi[], char noiden[], char c)
{
   NODEPTR p, p1;
   int kc, tg;

   if(c == 'x')
   {
       p = search1(plist, noidi);
       if(p == NULL)
       {
         cout<<"Khong co noi di";
         return;
      }
      if(strcmp(noidi, noiden) == 0)
      {
         cout<<"Noi di trung noi den";
         return;
      }
       p1 = search2(plist, noiden);
       if(p1 == NULL)
       {
         cout<<"Khong co noi den";
         return;
      }

      if(position(plist, p) <= position(plist, p1))
      {
         kc = tg = 0;
         while(p != p1)
         {
            kc = kc + p->info.chieudai;
            tg = tg + p->info.thoigian;
            cout<<endl<<p->info.gatruoc<<" -> " <<p->info.gasau <<": " <<p->info.chieudai<<"Km " <<p->info.thoigian<<" gio";
            p = p->right;
         }
         kc = kc + p1->info.chieudai;
         tg = tg + p1->info.thoigian;
         cout<<endl<<p1->info.gatruoc<<" -> " <<p1->info.gasau <<": " <<p1->info.chieudai<<"Km " <<p1->info.thoigian<<" gio";
         cout<<endl<<"Tong chieu dai lo trinh: "<<kc<<" km. Tong thoi gian van chuyen "<<tg<<" gio";
      }
      else
         cout<<"Khong di xuoi duoc";
      return;
   }

   if(c == 'n')
   {
       p = search2(plist, noidi);
       if(p == NULL)
       {
         cout<<"Khong co noi di";
         return;
      }
      if(strcmp(noidi, noiden) == 0)
      {
         cout<<"Noi di trung noi den";
         return;
      }
       p1 = search1(plist, noiden);
       if(p1 == NULL)
       {
        cout<<"Khong co noi den";
         return;
      }

      if(position(plist, p) >= position(plist, p1))
      {
         kc = tg = 0;
         while(p != p1)
         {
            kc = kc + p->info.chieudai;
            tg = tg + p->info.thoigian;
            cout<<endl<<p->info.gatruoc<<" -> " <<p->info.gasau <<": " <<p->info.chieudai<<"Km " <<p->info.thoigian<<" gio";
            p = p->left;
         }
         kc = kc + p1->info.chieudai;
         tg = tg + p1->info.thoigian;
         cout<<endl<<p1->info.gasau<<" -> " <<p1->info.gatruoc <<": " <<p1->info.chieudai<<"Km " <<p1->info.thoigian<<" gio";

         cout<<endl<<"Tong chieu dai lo trinh: "<<kc<<" km. Tong thoi gian van chuyen "<<tg<<" gio";
      }
      else
         cout<<"Khong di nguoc duoc";
      return;
   }
}

// chuong trinh chinh
int main()
{
   NODEPTR plist, p, p1;
   doan ga;
   int vitri, chucnang;
   char c;
   char noidi[12], noiden[12];

   system("cls");

   // khoi dong danh sach lien ket kep
   initialize(&plist);

   do
   {
      // menu chinh cua chuong trinh
      cout<<endl<<endl<<"CHUONG TRINH QUAN LY VA DIEU HANH TAU THONG NHAT HA NOI - SAI GON"<<endl;
      cout<<"Sinh vien thuc hien : TRINH VAN CHIEN  Lop TIN DIA CHAT K55"<<endl;
      cout<<"\* * * * * * * * * * * * * * * * * * * * * * * * * * * * *  * * * * * "<<endl;
      cout<<"   1: Them mot doan"<<endl;
      cout<<"   2: Xoa mot doan"<<endl;
      cout<<"   3: Xem lo trinh 1 (lo trinh xuoi)"<<endl;
      cout<<"   4: Xem lo trinh 2 (lo trinh nguoc)"<<endl;
      cout<<"   5: Xem thong tin cua doan thu i"<<endl;
      cout<<"   6: Hieu chinh thong tin ve doan thu i"<<endl;
      cout<<"   7: Thong tin lo trinh"<<endl;
      cout<<"   0: Ket thuc chuong trinh"<<endl;
      cout<<"Chuc nang ban chon: "<<endl;
      cin>>chucnang;
      switch(chucnang)
      {
         case 1:
          {
             cout<<"\nVi tri (0,1,2,...): ";
             cin>>vitri;
             cout<<"Ten ga truoc: ";
             cin>>ga.gatruoc;
             cout<<"Ten ga sau: ";
             cin>>ga.gasau;
             cout<<"Chieu dai (km): ";
             cin>>ga.chieudai;
             cout<<"Thoi gian (gio): ";
             cin>>ga.thoigian;
             if(vitri == 0)
                push(&plist, ga);
             else
                insertright(nodepointer(&plist, vitri-1), ga);
             break;
          }
          case 2:
          {
             cout<<"\nVi tri (0,1,2,...): ";
             cin>>vitri;
            p = nodepointer(&plist, vitri);
            if(p == NULL)
               cout<<"Vi tri khong hop le";
            else
                if(vitri == 0)
                   pop(&plist);
                else
                   delnode(&plist, p);
             break;
          }
          case 3:
          {
             cout<<endl<<"Xem lo trinh 1 (duyet xuoi): ";
            cout<<endl<<"STT          TU         DEN         CD         TG"<<endl;
             righttraverse(&plist);
             break;
          }
          case 4:
          {
             cout<<endl<<"Xem lo trinh 1 (duyet nguoc): ";
            cout<<endl<<"STT          TU         DEN         CD         TG"<<endl;
             lefttraverse(&plist);
             break;
          }
          case 5:
          {
             cout<<"\nVi tri (0,1,2,...): ";
             cin>>vitri;
            p = nodepointer(&plist, vitri);
            if(p == NULL)
               cout<<"Vi tri khong hop le";
            else
               cout<<endl<<"Doan: "<<vitri<<" Tu: "<<p->info.gatruoc<<" Den:" <<p->info.gasau<<" Chieu dai: " <<p->info.chieudai<< " km  Thoi gian: "<<p->info.thoigian<<" gio";
             break;
          }
          case 6:
          {
             cout<<"\nVi tri: ";
             cin>>vitri;
            p = nodepointer(&plist, vitri);
            if(p == NULL)
               cout<<"Vi tri khong hop le";
            else
            {
                cout<<endl<<"Doan: "<<vitri<<" Tu: "<<p->info.gatruoc<<" Den:" <<p->info.gasau<<" Chieu dai: " <<p->info.chieudai<< " km  Thoi gian: "<<p->info.thoigian<<" gio";
                cout<<"Ten ga truoc: ";
                cin>>ga.gatruoc;
                cout<<"Ten ga sau: ";
                cin>>ga.gasau;
                cout<<"Chieu dai (km): ";
                cin>>ga.chieudai;
                cout<<"Thoi gian (gio): ";
                cin>>ga.thoigian;
                p->info = ga;
            }
             break;
          }
          case 7:
          {
            cout<<endl<<"Ban di xuoi hay nguoc (x/n): ";
            cin>>c;
             cout<<endl<<"Cho biet noi di: ";
             cin>>noidi;
             cout<<endl<<"Cho biet noi den: ";
             cin>>noiden;
            baolotrinh(&plist, noidi, noiden, c);
             break;
          }
      }
   } while(chucnang != 0);

   // Xoa toan bo cac nut tren danh sach lien ket
   clearlist(&plist);
}