Hang Doi Mua Ve

// Hang Doi Mua Ve.cpp : Defines the entry point for the console application.
// So nguoi mua ve duoc bieu dien ban ky tu A B C D ...
// Nguoi dau tien la A, sau moi 1s thi ban  ve duoc 1 nguoi
#include "stdafx.h"                                                                                          
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<dos.h>
#include <windows.h>
// Ham gotoxy (lenh:gotoxy(x,y), thu vien:windows.h)
   void gotoxy(short x, short y)
   {
     HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE);
      COORD pos;
      pos.X=x-1;
     pos.Y=y-1;
    SetConsoleCursorPosition(hCon, pos);
  }
void sleep( clock_t wait )
{
clock_t goal;
goal = wait + clock();
while( goal > clock() )
;
}
//KHOI TAO DSLK QUEUE
struct tagnode{
        char Data;
        struct tagnode *next;
};
typedef tagnode *node;
typedef struct taglist{
        node head;
        node tail;
}linkedlist;
typedef linkedlist Queue;
void initQueue(Queue &q){
        q.head=q.tail=NULL;
}
int isempty(Queue q)   //kiem tra q rong hay khong
{
        return(q.head==NULL);
}
void enQueue(Queue &q,char x)   //them x vao cuoi q
{   node p= new tagnode;
        if(p==NULL) return;
        p->Data=x;
        p->next=NULL;
        if(isempty(q)){
                  q.head=q.tail=p;
                }
        else
                {        q.tail->next=p;
                  q.tail=p;
                }
}
void deQueue(Queue &q)  //xoa phan tu dau cua q
{   node p=q.head;
        if(isempty(q))
                return;
        q.head=p->next;
        if(q.head==NULL)
                q.tail=NULL;
        p->next=NULL;
        delete p;
}
void insertQueue(Queue &q,int n) //nhap phan tu cua q(nhap nguoi mua ve)
{   char j=65;
           initQueue(q);
           for(int i=0;i<n;i++)
                enQueue(q,j++);
}

void drawQueue(int x,int y)   //ve phong cho mua ve
{   int i,j;
           for(i=0;i<4;i++)
          if(i==0 || i==3)
                   for(j=0;j<16;j++)
                   {     gotoxy(x+j,y+i);
                         putchar(196);
                   }
          else
                   for(j=0;j<17;j+=3)
                   {     gotoxy(x+j,y+i);
                         putchar(221);
                   }
}
void putoutQueue(Queue q,int x,int y)   //in hang doi mua ve xem phim ra man hinh
{   node p=q.head;
        int i=1;    
        gotoxy(20,1);
        printf(" \n MO PHONG HANG DOI MUA VE XEM PHIM \n");
        drawQueue(x,y);
        if(isempty(q))
                return;
        else
                while(p)
                {          gotoxy(x+i,y+2);
                   putchar(p->Data);
                   p=p->next;
                   i+=3;
               }
}
void out_Queue(Queue q,int n) //quan ly so nguoi cho mua ve
{   int x=29,y=4;
           insertQueue(q,n);
           putoutQueue(q,x,y);
           gotoxy(25,10);
       
           sleep(4000);
           for(int i=0;i<n;i++)
           {     deQueue(q);
                 putoutQueue(q,x,y);
                 if(i!=(n-1))
                 {        gotoxy(25,10);
                  printf("\n Con %d nguoi cho mua ve",((n-1)-i));
                 }
                 else
                 {      gotoxy(33,10);
               
                 }
                sleep(2000);
           }
}
//HAM MAIN
void main()
{   Queue q;int n, m ,k;
   
        printf("\n Nhap so nguoi muon mua ve: ");
           scanf("%d",&m);
printf("\n Nhap so  ve: ");
scanf("%d",&k);
if(k<=m)
{
n=k;
printf("\n Ban het ve");
out_Queue(q,n);
   printf("\n Con %d nguoi chua co ve", m-k);
}
else
{
n=m;
printf("\n Tat ca deu co ve !");
out_Queue(q,n);
printf("\n Con thua %d ve :",k-m );
}
        getch();
}

Nhap Xuat Them Xoa Hang Doi

// HangDoi.cpp : Defines the entry point for the console application.
//


#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>
struct Queue
{
   int  info;
   struct Queue *next;
};
typedef struct Queue *QUEUE;

//Khai Bao Prototype
void InitializeQ (QUEUE *pfirst, QUEUE *plast);
int  EmptyQ (QUEUE *pfirst);
QUEUE GetQueue();
void PushQ (QUEUE *pfirst, QUEUE *plast, int x);
int  PopQ (QUEUE *pfirst, QUEUE *plast);
void TopQ (QUEUE *pfirst);
//==============================
void main()
{
   QUEUE pfirst, plast;
   int x, y, vt, chon, n, i;
   char ch;
   InitializeQ (&pfirst, &plast);
   do
   {
   
      printf("\n\n\t CHUONG TRINH DEMO HANG DOI THAO TAC TREN DAY NGUYEN !");
      printf("\n\t1  : Khoi Tao Hang Doi !");
      printf("\n\t2  : Kiem Tra Hang Doi Rong !");
      printf("\n\t3  : Tao Hang Doi !");
      printf("\n\t4  : Xuat Va Huy Hang Hoi  !");
      printf("\n\t5  : Them 1 Phan Tu Vao Hang Doi !");
      printf("\n\t6  : Xoa 1 PTu Ra Khoi hang Doi !");
      printf("\n\t7  : Truy Xuat Noi Dung O Dinh Hang Doi !");
      printf("\n\t0  : THOAT KHOI CHUONG TRINH !");
      printf("\n\tBan Chon Chuc Nang Nao ? ");
      scanf ("%d", &chon);
      switch (chon)
      {
         case 1:
         {
            InitializeQ (&pfirst, &plast);
            printf("\n\t Hang Doi Da Duoc Khoi Tao !");
            getch();
            break;
         }
         case 2:
         {
            printf("\n\t Kiem Tra Hang Doi Rong !");
            if (EmptyQ (&pfirst))
               printf("\n\t Hang Doi Rong !");
            else
               printf("\n\t Hang Doi Khong Rong !");
            getch();
            break;
         }
         case 3:
         {
            printf("\n\t Tao Hang Doi !");
            InitializeQ (&pfirst, &plast);
            printf("\n\t Nhap SPTu Trong Hang Doi !");
            scanf ("%d", &n);
            printf("\n\t Tao Hang Doi !");
            for (i = 1; i <= n; i++)
            {
               printf("\t\t\n Nhap PTu Thu %d  :  ", i);
               scanf("%d", &x);
               //Neu La Cau Truc : x = Nhap1PTu();
               PushQ(&pfirst, &plast, x);
            }
            getch();
            break;
         }
         case 4:
         {
            printf("\n\t Xuat Va Huy Hang Doi !");
            if (EmptyQ (&pfirst))
               printf("\n\t Hang Doi Rong  !");
            else
            {
               printf("\n\t Noi Dung Hang Doi Vua Nhap !");
               while(EmptyQ (&pfirst) == 0)
               {
                  TopQ (&pfirst);
                  y = PopQ (&pfirst, &plast);
               }
            }
            getch();
            break;
         }
         case 5:
         {
            printf("\n\t Them 1 PTu Vao Hang Doi !");
            printf("\n\t Nhap Noi Dung X Can Them :  ");
            scanf ("%d", &x);
            PushQ(&pfirst, &plast, x);
            getch();
            break;
         }
         case 6:
         {
            printf("\n\t Xoa PTu Dinh !");
            y = PopQ (&pfirst, &plast);
            getch();
            break;
         }
         case 7:
         {
            printf("\n\t Truy Xuat Noi Dung PTu Dinh !");
            TopQ (&pfirst);
            getch();
            break;
         }
      }//KT Switch
   }while (chon > 0);
   getch();
}//KThuc Ham Main
//==============================
//Cai Dat Cac Prototype
//======================================
void InitializeQ (QUEUE *pfirst, QUEUE *plast)
{
   *pfirst = *plast = NULL;
}
//========================================
int  EmptyQ (QUEUE *pfirst)
{
   if (*pfirst == NULL)
      return 1; //Rong
   return 0; //Khong Rong
}
//========================================
QUEUE Getnode()//Cap Phat Vung Nho
{
   QUEUE p;
   p = (QUEUE) malloc (sizeof (struct Queue));
   p -> next = NULL;
   return p;
}
//========================================
int  PopQ (QUEUE *pfirst, QUEUE *plast)
{
   QUEUE p;
   int x;
   if (EmptyQ(pfirst))
      printf("\n\t DS Rong, Khong Xoa Duoc !");
   else
   {
      p = *pfirst;
      x = p -> info;
      if (p -> next == NULL) //DS Co 1 Phan Tu
         *pfirst = *plast = NULL;
      else
         *pfirst = p -> next;
      return x;
   }
}
//========================================
void PushQ (QUEUE *pfirst, QUEUE *plast, int x)
{
   QUEUE p;
   p = Getnode();
   p -> info = x;
   p -> next = NULL;
   if (EmptyQ (pfirst))
   {
      *pfirst = p;
      *plast = *pfirst;
   }
   else
   {
      (*plast) -> next = p;
      *plast = p;
   }
}
//========================================
void TopQ (QUEUE *pfirst)
{
   if (EmptyQ (pfirst))
      printf("\n\t Hang Doi Rong !");
   else
   {
      printf("%5d", (*pfirst) -> info);
      //Neu La Cau Truc In1PTu
   }

}

Queue -Hang Doi

Hàng đợi :(tiếng Anh: queue) là một cấu trúc dữ liệu dùng để chứa các đối tượng làm việc theo cơ chế FIFO (viết tắt từ tiếng Anh:First In First Out), nghĩa là "vào trước ra trước
Trong hàng đợi, các đối tượng có thể được thêm vào hàng đợi bất kỳ lúc nào, nhưng chỉ có đối tượng thêm vào đầu tiên mới được phép lấy ra khỏi hàng đợi. Thao tác thêm vào và lấy một đối tượng ra khỏi hàng đợi được gọi lần lượt là "enqueue" và "dequeue". Việc thêm một đối tượng luôn diễn ra ở cuối hàng đợi và một phần tử luôn được lấy ra từ đầu hàng đợi.
Trong tin học, cấu trúc dữ liệu hàng đợi có nhiều ứng dụng: khử đệ qui, tổ chức lưu vết các quá trình tìm kiếm theo chiều rộng và quay lui, vét cạn, tổ chức quản lý và phân phối tiến trình trong các hệ điều hành, tổ chức bộ đệm bàn phím.
Cấu trúc dữ liệu hàng đợi có thể định nghĩa như sau: Hàng đợi là một cấu trúc dữ liệu trừu tượng (ADT) tuyến tính. Tương tự nhưngăn xếp, hàng đợi hỗ trợ các thao tác:
EnQueue(o): thêm đối tượng o vào cuối hàng đợi.
DeQueue(): lấy đối tượng ở đầu queue ra khỏi hàng đợi và trả về giá trị của nó. Nếu hàng đợi rỗng thì lỗi sẽ xảy ra.
IsEmpty(): kiểm tra xem hàng đợi có rỗng không.
Front(): trả về giá trị của phần tử nằm ở đầu hàng đợi mà không hủy nó. Nếu hàng đợi rỗng thì lỗi sẽ xảy ra.
Các thao tác thêm, trích và huỷ một phần tử phải được thực hiện ở hai phía khác nhau của hàng đợi, do đó hoạt động của hàng đợi được thực hiện theo nguyên tắc FIFO. Cũng như ngăn xếp, cấu trúc mảng một chiều hoặc cấu trúc danh sách liên kết có thể dùng để biểu diễn cấu trúc hàng đợi.

Có 2 cách cài đặt hàng đợi:

- Dùng mảng.

- Dùng danh sách liên kết.

1. Cài đặt hàng đợi sử dụng mảng (Implementation Queue using Array)

a) Mảng bình thường:

 #include <stdio.h>

 #include <stdlib.h>

 #define MAX 20

 typedef <Element's type> El_type;

 typedef struct Queue

 {

     El_type el[MAX];

     int front;

     int rear;

 } Queue;

Các thao tác: - Khởi tạo hàng đợi( Initialize Queue )

 Eltype *initQ( Queue *q )

 {

     q = (Queue *)malloc( sizeof( Queue ) );

     if( q != NULL ) 

     {

          q->front = -1;

          q->rear = -1;

     }

     return q;

 }

- Kiểm tra xem hàng đợi có rỗng không? ( Check if a queue is empty )

 int isEmpty( Queue *q )

 {

     return ( q->front == -1 );

 }

- Kiểm tra xem hàng đợi có đầy không? ( Check if a queue is full )

 int isFull( Queue q )

 {

     return ( q.rear-q.front+1 == MAX);

 }

- Đưa thêm một phần tử vào hàng đợi

 void enQ( El_type new_el, Queue *q )

 {

     if( !isFull( q ) )

     {

          if( isEmpty( q ) ) q->front = q->front+1;

          q->rear = q->rear+1;

          q->el[q->rear] = new_el;

     }

     else

          printf( "Queue is full.\n" );

 }

- Xóa một phần tử khỏi hàng đợi

 void deQ( Queue *q )

 {

     if( !isEmpty( q ) )    

         q->front = q->front+1;           

     else

         printf( "Queue is empty.\n" );

 }

Nhược điểm:

- Qua mỗi lần xóa (deQ): phần sử dụng được của mảng sẽ giảm đi (do front tăng lên ).

Cách khắc phục:

- Sử dụng mảng vòng (Circular Array).

Mảng vòng:

 tương ta có:

- Khởi tạo hàng đợi( Initialize Queue )

 Eltype *initQ( Queue *q )

 {

     q = (Queue *)malloc( sizeof( Queue ) );

     if( q != NULL ) 

     {

          q->front = -1;

          q->rear = -1;

     }

     return q;

 }

- Kiểm tra xem hàng đợi có rỗng không? ( Check if a queue is empty )

 int empty_queue(queue q)

 {

   return q.front==-1;

 }

- Kiểm tra xem hàng đợi có đầy không? ( Check if a queue is full )

 int full_queue(queue q)

 {

   return (q.rear-q.front+1)%maxlength==0;

 }

- Đưa thêm một phần tử vào hàng đợi

 void enqueue(elementtype x,queue *q)

 {

   if(!full_queue(*q))

   {

     if(empty_queue(*q))q->front=0;

     q->rear=(q->rear+1)%maxlength;

     q->data[q->rear]=x;                 

   }

   else printf("Hang Day!");

 }

- Xóa một phần tử khỏi hàng đợi

 void dequeue(queue *q)

 {

   if(!empty_queue(*q))

   {

     if(q->front==q->rear)makenull_queue(q);

     else q->front=(q->front+1)%maxlength;

   }

   else printf("Hang rong!");

 }

Nhược điểm:

- Mặc dù phương pháp sử dụng mảng vòng có thể tận dùng toàn bộ các mảng đã được cấp pháp ban đầu nhưng khi mảng đầy thì không thể thêm phần tử vào hàng được nữa. Cách khắc phục:

- Sử dụng Danh sách liên kết.

Cài Đặt Mảng Sử Dụng Danh Sách Liên Kết: (Implementation Queue using List Point)

Khai báo cài đặt hàng bằng con trỏ

 #include <stdio.h>

 #include <conio.h>

 #include <malloc.h>

 typedef int elementtype;

 typedef struct node{

   elementtype data;

   node* next;

 };

 typedef node* position;

 typedef struct queue{

   position front,rear;      

 };

Các thao tác:

- Khởi tạo hàng đợi( Initialize Queue )

 void makenull_queue(queue *q)

 {

   q->front=(node*)malloc(sizeof(node));

   q->front->next=NULL;

   q->rear=q->front;

 }

- Kiểm tra xem hàng đợi có rỗng không? ( Check if a queue is empty )

 int empty_queue(queue q)

 {

   return (q.front==q.rear);  

 }

- Kiểm tra hàng đợi có đầy không (ở đây không có hàm này vì danh sách liên kết làm sao đầy được ^^!)

- Đưa thêm một phần tử vào hàng đợi

 void enqueue(elementtype x, queue *q)

 {

   q->rear->next=(node*)malloc(sizeof(node));

   q->rear=q->rear->next;

   q->rear->data=x;

   q->rear->next=NULL;   

 }

- Xóa một phần tử khỏi hàng đợi

 void dequeue(queue *q)

 {

   position t;

   t=q->front;

   q->front=q->front->next;

   free(t);

 }

Ưu điểm: - khắc phục được tình trạng đầy của việc sử dụng mảng để cài đặt queue.

Chuyen Bieu Thuc Trung To Sang Hau To

Phương pháp chuyển đổi biểu thức inFix sang postFix như sau : (Trích sách Cấu trúc dữ liệu và thuật toán )
Nếu thành phần được đọc là toán hạng thì viết nó vào biểu thức postFix
Nếu thành phần được đọc là dấu mở ngoặc thì đẩy nó vào stack
Nếu thành phần được đọc là dấu đóng ngoặc thì lấy các phép toán trong stack ra và viết nó vào biểu thức postFix cho tới khi gặp dấu mở ngoặc.
Sau đó loại dấu mở ngoặc khỏi stack
Nếu thành phần là phép toán thì xét các trường hợp sau
Nếu stack không rỗng, hoặc phần tử ở đỉnh stack có độ ưu tiên cao hơn hay bằng phép toán hiện thời thì lấy phép toán đó ra khỏi stack và đưa vào postFix. Lặp lại bước này
Nếu stack rỗng, hoặc phần tử ở đỉnh stack có độ ưu tiên thấp hơn phép toán hiện thời thì phép toán hiện thời được đẩy vào stack
Sau khi toàn bộ biểu thức inFix đã được đọc thì lấy các phép toán trong ngăn xếp ra và viết vào postFix cho đến khi ngăn xếp rỗng
Dưới đây là code của mình viết theo thuật toán trên:



#include <iostream>
#include <string.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
#define  SIZE  100 
const int TOAN_TU = 1;
const int TOAN_HANG = 0; 
int LayDoUuTien(char toantu); // Ham tra ve do uu tien cua toan tu
//** Ham xu ly stack **//
char Top(char stack[]); //Tra ve phan tu dau tien trong stack nhung khong xoa khoi stack
void Push(char phantu, char stack[]); //Dat 1 phan tu vao stack
char Pop(char stack[]); //Lay phan tu dau tien ra khoi stack
/* Ham noi 1 ky tu vao cuoi chuoi.*/
void ConCat(char kytu, char array[]);
/*
* Ham kiem tra ky tu elem co phai la toan tu khong?
* Tra ve 1 neu elem la toan tu.
* Nguoc lai tra ve 0.
*/


int LoaiPhanTu(char elem);
/**
* Chuyen 1 chuoi infix sang chuoi postfix
*/
void InfixToPostFix(char infix[], char postfix[]);
/*
* Tinh gia tri postfix.
* @param postfix[]: chuoi chua postfix
*/


float TinhGiaTriBieuThuc(char postfix[]);
/**
* Tinh gia tri cua phep toan 2 ngoi
*/
float TinhGiaTri(char toantu, float val1, float val2);
int main() 
{
char infix[SIZE];


char postfix[SIZE];
//xoa vung nho chua postfix
strcpy(infix, "");
cout<<"note: \n";
cout<<" chi nhap toan tu tu 0 den 9\n";
cout << "nhap bieu thuc:";
cin >> infix; 
InfixToPostFix(infix, postfix);
cout << "Postfix: " << postfix <<endl;
cout <<"Gia tri: ";
cout <<TinhGiaTriBieuThuc(postfix);
getch();
return 0;


}

void InfixToPostFix(char infix[], char postfix[])
{
char stack[SIZE];
strcpy(postfix, "");
strcpy(stack, "");
int len = strlen(infix);
for (int i = 0; i < len; i++) 
{
char curChar = infix[i];
if (LoaiPhanTu(curChar) == TOAN_TU) 
{
int rank1 = LayDoUuTien(curChar);
int rank2 = LayDoUuTien(Top(stack));
if (rank1 > rank2) 
{


Push(curChar, stack);
} else
{


//Lay cac toan tu co do uu tien thap hon ra khoi stack
//va bo vao postfix
while (rank1 <= rank2)
{


if (Top(stack) == ' ')
break;
//lay phan tu tu` stack bo vao postfix


ConCat(Pop(stack), postfix);
//Kiem tra phan tu ke tiep trong stack


rank2 = LayDoUuTien(Top(stack));


}
Push(curChar, stack);


}
} else if (curChar == '(')
{


Push(curChar, stack);
} else if (curChar == ')') 
{


char temp = Pop(stack);


while (temp != '(')
{


ConCat(temp, postfix);


temp = Pop(stack);


}


} else //toan hang


{


ConCat(curChar, postfix);


}
}

//lay nhung phan tu con lai trong stack


while (Top(stack) != ' ') 
{


ConCat(Pop(stack), postfix);


}
}
int LoaiPhanTu(char elem)
 {
if (elem == '+' || elem == '-' || elem == '*' || elem == '/')
 {
return TOAN_TU;
}
return TOAN_HANG;
}
int LayDoUuTien(char toantu) 
{
int iRes = -1;
switch (toantu) 
{


case '*':


case '/':


iRes = 5;


break;


case '+':


case '-':


iRes = 4;


break;


default:


iRes = 0;


}
return iRes;


}
char Top(char stack[]) 
{


int len = strlen(stack);


if (len > 0) 
{
return stack[len-1];


}
return ' '; // neu stack rong, tra ve ky tu trong


}
char Pop(char stack[]) 
{
int len = strlen(stack);
if (len > 0)
{


char cRes = stack[len-1];


stack[len-1] = '\0';
return cRes;


}
return ' ';
}

void Push(char phantu, char stack[])
 {
int len = strlen(stack);
stack[len] = phantu;


stack[len+1] = '\0';


}
void ConCat(char kytu, char array[]) {


Push(kytu, array);
}
float TinhGiaTriBieuThuc(char postfix[]) {


float stackGiaTri[SIZE];


int dinh = -1; // vi tri di?nh cua stack
int len = strlen(postfix);
for (int i = 0; i < len; i++)
 {
char curChar = postfix[i];


if (LoaiPhanTu(curChar) == TOAN_HANG) {


char ss[2];


ss[0] = curChar;


ss[1] = '\0';


float val = atof(ss);


dinh++;


stackGiaTri[dinh] = val;
} 
else if (LoaiPhanTu(curChar) == TOAN_TU) {


float val2 = stackGiaTri[dinh];


dinh--;

if (dinh < 0) {


cout << "Bieu thuc co loi.";


exit(-1);


}
float val1 = stackGiaTri[dinh];


float val3 = TinhGiaTri(curChar, val1, val2);


stackGiaTri[dinh] = val3;


}
}
if (dinh > 0) 
{
cout << "Bieu thuc khong dung";


exit(-1);
}
return stackGiaTri[dinh];
}
float TinhGiaTri(char toantu, float val1, float val2)
{
float fRes = 0;

switch (toantu)
{


case '*':


fRes = val1 * val2; break;


case '/': 
{


if (val2 == 0) 
{


cout << "Loi chia cho 0"; exit(-2);


}
fRes = val1 / val2; break;
}
case '+':


fRes = val1 + val2; break;


case '-':


fRes = val1 - val2; break;


break;
}
return fRes;
}