Bài tập kiểm tra số nguyên tố bằng Stack

1. Gợi ý cách thực hiện

Trong chương trình này ta sẽ thực hiện nhập vào một dãy số nguyên sau đó lưu vào Stack, vậy nên việc đầu tiên ta cần tạo cấu trúc Stack. Trong hướng dẫn này mình sẽ sử dụng danh sách liên kết để cài đặt Stack, vì vậy ta cần tạo thêm cấu trúc Node.

Để có thể thêm, lấy các phần tử trong Stack thì ta cần tạo thêm các hàm cơ bản trong Stack như:

• Hàm isEmpty.
• Hàm Push.
• Hàm Pop.

Khi này ta sẽ bắt đầu thực hiện tạo các hàm liên quan đến việc xuất các số nguyên tố trong Stack ra màn hình:

• Hàm getData() lấy dữ liệu từ người dùng sau đó đưa nó vào Stack
• Hàm ktSoNT() để kiểm tra các số trong Stack có phải là số nguyên tố hay không.
• Hàm XuatSoNguyenTo() để xuất các số nguyên tố ra màn hình.

2. Chương trình xuất các số nguyên tố trong Stack

Ta sẽ dựa vào gợi ý ở trên rồi lần lượt thực hiện tạo các hàm cần thiết cho bài toán, đầu tiên ta sẽ tạo cấu trúc Stack và cấu trúc Node trong danh sách liên kết để cài đặt Stack.

/* khai báo Node */
struct node
{
    int data;
    struct node *pNext;
};
typedef struct node NODE;
 
/* khai báo cấu trúc của Stack */
struct stack
{
    NODE *pTop; // con trỏ quản lí đầu stack
};
typedef struct stack STACK;

 Sau đó ta sẽ viết hàm khởi tạo Stack và hàm khởi tạo Node.

/* hàm khởi tạo Stack */
void KhoiTaoStack(STACK &s)
{
    s.pTop = NULL;
}
 
/* hàm khởi tạo 1 cái node */
NODE *KhoiTaoNode(int x)
{
  //tạo mới một NODE
    NODE *p = new NODE();
    if (p == NULL)
    {
        cout << "\nKhông đủ bộ nhớ để cấp phát !";
        return NULL;
    }
  // đưa dữ liệu của biến x vào trong cái data của node p
    p->data = x; 
    p->pNext = NULL;
    return p;
}

Ta cần một hàm kiểm tra Stack có tồn tại phần tử hay không, đây là điều kiện để có thể thực hiện các thao tác khác trong Stack như thêm, lấy phần tử.

/* hàm kiểm tra Stack rỗng*/
bool IsEmpty(STACK s)
{
    // nếu stack rỗng
    if (s.pTop == NULL)
    {
        return false;
    }
    return true;
}

Và hai hàm cơ bản trong Stack đó chính là Push() và Pop(), đây là hai hàm không thể thiếu khi làm việc với Stack.

/* Thêm phần tử vào đầu Stack (top)*/
bool Push(STACK &s, NODE *p)
{
    // node p đang rỗng
    if (p == NULL)
    {
        return false;
    }
 
    // nếu danh sách rỗng
    if (IsEmpty(s) == false)
    {
    // node p cũng chính là node pTop <=>chính là node đầu stack
        s.pTop = p;
    }
    else
    {
    // B1: cho con trỏ của node p trỏ đến node pTop
        p->pNext = s.pTop; 
    // B2: cập nhật lại node đầu chính là node p
        s.pTop = p;
    }
  // thêm thành công
    return true;
}
 
/* Lấy phần tử đầu danh sách và hủy nó đi */
bool Pop(STACK &s, int &x) // x chính là giá trị cần lấy ra
{
    // nếu danh sách rỗng
    if (IsEmpty(s) == false)
    {
    // lấy thất bại <=> danh sách đang rỗng
        return false; 
    }
  // gán node đầu danh sách vào node p <=> node p chính là node mà tí nữa ta sẽ xóa nó
    NODE *p = s.pTop; 
   // cập nhật lại node đầu 
    s.pTop = s.pTop->pNext;
  // lấy giá trị của node đầu ra gán vào biến x
    x = p->data; 
  // lấy phần tử thành công
    return true; 
}

Sau khi tạo các hàm cơ bản trong Stack, bây giờ ta sẽ bắt đầu tạo các hàm liên quan đến xuất các số nguyên tố. Đầu tiên sẽ là hàm kiểm tra số nguyên tố, đây là một thuật toán rất phô biến, vì vậy các bạn có thể tìm hiểu trên google hoặc có thể tham khảo của mình dưới đây.

/* hàm kiểm tra số nguyên tố */
bool ktSoNT(int n)
{
    // Nếu n < 2 thì không phải là số nguyên tố
    if (n < 2){
        return false;
    }       
    // ngược lại nếu n >= 2 thì ta xét điều kiện số nguyên tố
    for (int i = 2; i < (n - 1); i++){
      //nếu n chia hết cho i thì không phải là số nguyên tố
        if (n % i == 0){
            return false;
        }   
    }
     //ngược lại là số nguyên tố
    return true;
}

Và cuối cùng là hàm xuất các số là số nguyên tố trong Stack ra màn hình bằng cách sử dụng hàm ktSoNT() và hàm Pop(). Đơn giản chỉ là ta sẽ xét điều kiện nếu x (số thêm vào trong Stack) là số nguyên tố thì ta sẽ xuất ra màn hình.

void XuatSoNguyenTo(STACK &s)
{
    while (IsEmpty(s) == true)
    {
        int x;
        Pop(s, x);
    //nếu x là số nguyên tố thì ta xuất ra màn hình
        if (ktSoNT(x))
        {
            cout << x << "\t";
        }
    }
}

Full Code:

#include<iostream>
using namespace std;
 
/* khai báo Node */
struct node
{
    int data;
    struct node *pNext;
};
typedef struct node NODE;
 
/* khai báo cấu trúc của Stack */
struct stack
{
    NODE *pTop; // con trỏ quản lí đầu stack
};
typedef struct stack STACK;
 
/* hàm khởi tạo Stack */
void KhoiTaoStack(STACK &s)
{
    s.pTop = NULL;
}
 
/* hàm khởi tạo 1 cái node */
NODE *KhoiTaoNode(int x)
{
  //tạo mới một NODE
    NODE *p = new NODE();
    if (p == NULL)
    {
        cout << "\nKhông đủ bộ nhớ để cấp phát !";
        return NULL;
    }
  // đưa dữ liệu của biến x vào trong cái data của node p
    p->data = x; 
    p->pNext = NULL;
    return p;
}
 
/* hàm kiểm tra Stack rỗng*/
bool IsEmpty(STACK s)
{
    // nếu stack rỗng
    if (s.pTop == NULL)
    {
        return false;
    }
    return true;
}
 
/* Thêm phần tử vào đầu Stack (top)*/
bool Push(STACK &s, NODE *p)
{
    // node p đang rỗng
    if (p == NULL)
    {
        return false;
    }
 
    // nếu danh sách rỗng
    if (IsEmpty(s) == false)
    {
    // node p cũng chính là node pTop <=>chính là node đầu stack
        s.pTop = p;
    }
    else
    {
    // B1: cho con trỏ của node p trỏ đến node pTop
        p->pNext = s.pTop; 
    // B2: cập nhật lại node đầu chính là node p
        s.pTop = p;
    }
  // thêm thành công
    return true;
}
 
/* Lấy phần tử đầu danh sách và hủy nó đi */
bool Pop(STACK &s, int &x) // x chính là giá trị cần lấy ra
{
    // nếu danh sách rỗng
    if (IsEmpty(s) == false)
    {
    // lấy thất bại <=> danh sách đang rỗng
        return false; 
    }
  // gán node đầu danh sách vào node p <=> node p chính là node mà tí nữa ta sẽ xóa nó
    NODE *p = s.pTop; 
   // cập nhật lại node đầu 
    s.pTop = s.pTop->pNext;
  // lấy giá trị của node đầu ra gán vào biến x
    x = p->data; 
  // lấy phần tử thành công
    return true; 
}
 
/* Xem thông tin của node đầu danh sách */
bool Top(STACK s, int &x) 
// x chính là giá trị cần xem
{
    // nếu danh sách rỗng
 
    if (IsEmpty(s) == false)
    {
        return false;
    }
    x = s.pTop->data;
    return true;
}
/* hàm thêm dữ liệu vào Stack */
void getData(STACK &s,int x)
{
    //tạo một node p để lưu giá trị của x vào
        NODE *p = KhoiTaoNode(x); 
    // thêm node p vào stack
        Push(s, p);
     
}
 
/* hàm kiểm tra số nguyên tố */
bool ktSoNT(int n)
{
    // Nếu n < 2 thì không phải là số nguyên tố
    if (n < 2){
        return false;
    }       
    // ngược lại nếu n >= 2 thì ta xét điều kiện số nguyên tố
    for (int i = 2; i < (n - 1); i++){
      //nếu n chia hết cho i thì không phải là số nguyên tố
        if (n % i == 0){
            return false;
        }   
    }
     //ngược lại là số nguyên tố
    return true;
}
/* hàm xuất các số nguyên tố ra màn hình */
void XuatSoNguyenTo(STACK &s)
{
    while (IsEmpty(s) == true)
    {
        int x;
        Pop(s, x);
    //nếu x là số nguyên tố thì ta xuất ra màn hình
        if (ktSoNT(x))
        {
            cout << x << "\t";
        }
    }
}
 
int main()
{
  STACK s;
  KhoiTaoStack(s);
     
  int x;
  while(1){
    cout<<"Nhập vào số bạn muốn thêm vào Stack, Nhập -1 để thoát !: ";
    cin >> x;
    getData(s, x);
    if(x == -1) break;
  }
   
  cout << "\nCác số nguyên tố trong Stack là: \n";
  XuatSoNguyenTo(s);
  cout << endl;
 
  cout<<"\n-------------------------\n";
  cout<<"Chương trình này được đăng tại hiepsiit.com";
}

Kết quả: