NGĂN XẾP STACK
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

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.

test php

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

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ư:

Bài viết này được đăng tại [free tuts .net]

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

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Tìm kiếm phần tử k trong danh sách liên kết đôi

Tìm kiếm phần tử k trong danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu cách tìm kiếm một phần tử k trong…

Top