Bài tập kiểm tra số nguyên tố bằng 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 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 << "\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()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 Freetuts.net";
}

Kết quả:

stack so nguyen to PNG

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 !!!

Bạn đang tìm Hosting / VPS để chạy dự án?

Hiện nay, Tinohost là một trong những nhà cung cấp Hosting tốt nhất Việt Nam. Với đội ngũ hỗ trợ nhanh chóng, giá cả phù hợp, nhiều dịch vụ miễn phí kèm theo như:

  • Hỗ trợ di chuyển dữ liệu
  • Cho dùng thử 7 ngày miễn phí
  • Tự động backup cho khách hàng (cả VPS cũng đc backup)

Sử dụng mã TINO30_2020 để được giảm 30% nhé

VÀO TINOHOST NGAY