10/13/13

Ví dụ về cài đặt hàng đợi trong C++

Code:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <fstream>
#include <cassert>

using namespace std;

typedef struct Node* NodePtr;
struct Node
{
    int data;
    NodePtr next;
};

typedef struct Queue* QueuePtr;
struct Queue
{
    NodePtr front;
    NodePtr rear;
};

// Tao 1 hang doi moi tu tep
QueuePtr newQueue(const char* filename);

// In ra cac phan tu ben trong hang doi
void printQueue(QueuePtr q);

// Kiem tra xem hang doi co rong khong
bool isEmpty(QueuePtr q);

// Them 1 phan tu vao hang doi
void enqueue(QueuePtr q, int v);

// Lay gia tri cua phan tu dau hang doi va xoa no khoi hang doi
int dequeue(QueuePtr q);

// Tra ve gia tri phan tu o dau hang doi
int getHead(QueuePtr q);

int main(int argc, char const *argv[])
{
    cout << "//Tao mot hang doi moi tu tep" << endl;
    cout << "Hang doi sau khi khoi tao: " << endl;
    QueuePtr q = newQueue("queue.txt");
    printQueue(q);

    cout << "\n//Kiem tra ham enqueue" << endl;
    cout << "Nhap vao 1 so de them vao hang doi: ";
    int number;
    cin >> number;
    enqueue(q, number);
    cout << "Hang doi sau khi enqueue: " << endl;
    printQueue(q);

    cout << "\n//Kiem tra ham dequeue" << endl;
    number = dequeue(q);
    cout << "Phan tu lay ra la: \n" << number << endl;
    cout << "Hang doi sau khi dequeue: " << endl;
    printQueue(q);

    cout << "\n//Kiem tra ham getHead" << endl;
    cout << "Gia tri phan tu dau cua hang doi: \n"
         << getHead(q) << endl;
    cout << "Hang doi sau khi getHead: " << endl;
    printQueue(q);

    return 0;
}

QueuePtr newQueue(const char* filename)
{
    ifstream input(filename);
    QueuePtr q = new Queue();
    
    // Doc so tu file va them vao cuoi hang doi
    int data;
    while (input >> data)
        enqueue(q, data);

    input.close();

    return q;
}

void printQueue(QueuePtr q)
{
    if (isEmpty(q))
        cout << "Queue is empty!";
    else
    { 
        NodePtr tmp = q->front;
        while (tmp != NULL)
        {
            cout << tmp->data << " ";
            tmp = tmp->next;
        }
    }
    cout << endl;
}

bool isEmpty(QueuePtr q)
{
    return (q->front == NULL);
}

void enqueue(QueuePtr q, int v)
{
    NodePtr tmp = new Node();
    tmp->data = v;
    tmp->next = NULL;

    if (isEmpty(q))
    {
        q->front = q->rear = tmp;
    }
    else
    {
        q->rear->next = tmp;
        q->rear = tmp;
    }
}

int dequeue(QueuePtr q)
{
    // Khi hang doi rong, con tro q->front bang NULL,
    // thoat khoi chuong trinh va thong bao loi.
    assert(q->front != NULL);
    
    int tmp = q->front->data;
    q->front = q->front->next;
    return tmp;
}

int getHead(QueuePtr q)
{
    // Khi hang doi rong, con tro q->front bang NULL,
    // thoat khoi chuong trinh va thong bao loi.
    assert(q->front != NULL);
    
    return q->front->data;
}

No comments :

Post a Comment