Bài tập kiểm tra số nguyên tố bằng Stack - Ngăn xếp Stack
Trong hướng dẫn này mình sẽ thực hiện một chương trình nhập một dãy các số nguyên vào Stack sau đó thực hiện xuất các số nguyên tố ra màn hình. Đây là một bài tập khá đơn giản nhưng rất phổ biến trong lập trình. Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết, sau đó thực hiện ...
Trong hướng dẫn này mình sẽ thực hiện một chương trình nhập một dãy các số nguyên vào Stack sau đó thực hiện xuất các số nguyên tố ra màn hình. Đây là một bài tập khá đơn giản nhưng rất phổ biến trong lập trình.
Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết, sau đó thực hiện xuất các số nguyên tố trong Stack ra màn hình.
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 << "
Khô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 << " ";
}
}
}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 << "
Khô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 << " ";
}
}
}
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 << "
Các số nguyên tố trong Stack là:
";
XuatSoNguyenTo(s);
cout << endl;
cout<<"
-------------------------
";
cout<<"Chương trình này được đăng tại Zaidap.com.net";
}Kết quả:
3. Kết luận
Như vậy là chúng ta đã thực hiện xong chương trình xuất các số là số nguyên tố trong Stack ra màn hình. Các bạn có thể luyện tập bằng cách xuất các số khác như số hoàn hảo, số chính phương, đây là một cách luyện tập rất hiệu quả cho thấy độ hiểu bài của các bạn. Chúc các bạn thực hiện thành công !!!
