Viết chương trình tạo hàng đợi - queue (dùng danh sách liên kết đơn)

THỰC HÀNH 4

• YÊU CẦU 1 (cá nhân):

  Viết chương trình tạo hàng đợi - queue (dùng danh sách liên kết đơn), mỗi nút có thành phần dữ liệu là 1 số nguyên, hãy thực hiện 2 thao tác sau:

  1. Sắp xếp dãy số tăng dần theo thành phần dữ liệu;

  2. Chèn 1 số nguyên vào danh sách (nhập từ bàn phím) sao cho sau khi chèn thì danh sách vẫn tăng dần theo thành phần dữ liệu.
• 
  
  

Code cài đặt hàng đợi - queue:

/* HOANG KIM TUYEN | D18HT01 */
#include 
using namespace std;
struct node 
{
 int data;
 node *pNext; 
};
typedef struct node NODE;
struct list
{
 NODE *pHead;
 NODE *pTail;
};
typedef struct list LIST;
NODE *creatNODE(int x)
{
 NODE *p = new NODE;
 if(p==NULL)
 {
  cout<<"day bo nho "<data = x;
 p->pNext = NULL;
}
void creatLIST(LIST &l)
{
 l.pHead = NULL;
 l.pTail = NULL;
}
/* HOANG KIM TUYEN | D18HT01 */
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 delete_HEAD(LIST &l)
{
 NODE *temp = l.pHead->pNext;
 l.pHead = temp;
 delete temp;
}
void delete_TAIL(LIST &l)
{
 NODE *k = l.pHead;
 while(k != NULL)
 {
  if(k->pNext = l.pTail)
  {
   k->pNext = NULL;
   delete l.pTail;
   l.pTail = k;
  }
  k= k->pNext;
 }
}
void Push_to_list(LIST &l)
{
 int chucnang;
 do
 {
  cout<<"0. Dung nhap vao danh sach !"<>chucnang;
  system("cls");
  switch(chucnang)
  {
   case(1):
    {
     int x;
     cout<<"Nhap gia tri can them vao : ";
     cin>>x;
     NODE * p = creatNODE(x);
     addTail(l, p); // them vao cuoi queue
     system("cls");
    }
  }
 }
 while(chucnang!=0);
}
void Pop_list(LIST l)
{
 NODE *k = l.pHead;
 while(k != NULL) // lay ra dau queue
 {
  cout<data<<" ";
  k = k->pNext;
 }
}
void sort_list(LIST &l)
{
 NODE *k = l.pHead;
 while(k != NULL)
 {
  NODE *j = k->pNext; // Node j dung sau node k
  while(j != NULL)    // vong lap so sanh gia tri cua cac node voi node k
  {
   if(k->data > j->data)
   {
    // hoan doi gia tri giua node k va node j
    int temp = k->data; 
    k->data = j->data;
    j->data = temp;
   }
   j=j->pNext; // qua node tiep theo
  }
  k=k->pNext; // qua node tiep theo
 }
}
void insert_list(LIST &l)
{
 int x;
 cout<<"Nhap gia tri can chen vao danh sach : ";
 cin>>x;
 NODE *p = new NODE;
  p = creatNODE(x); // tao node p chua gia tri x
 // them p vao danh sach tang theo truong du lieu
 if(p->data == l.pHead->data)
 {
  addHead(l,p);
  return;
 }
 if(p->data == l.pTail->data)
 {
  addTail(l,p);
  return;
 }
 NODE *k = l.pHead;
 while(k!= NULL)
 {
  NODE *j = k->pNext; // node j la node dung sau node k
  // so sanh gia tri cua p voi node k va j
  if(p->data > k->data && p->data < j->data)
  {
   // chen p vao giua k va j -------- k->next = p, p->next = j
   k->pNext = p;
   p->pNext = j;
  }
  
  k = k->pNext;
 }
}

Hàm main:

int main()
{
LIST danhsach;
creatLIST(danhsach);
Push_to_list(danhsach);
cout<<"Danh sach vua nhap la : ";Pop_list(danhsach);cout<