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

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ơ số áp dụng Stack. Đây là một bài toán rất phổ biến trong lập trình, để làm được bài này các bạn cần nắm rõ quy tắc chuyển đổi giữa các cơ số.

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 thực hiện một chương trình đổi cơ số thập phân sang cơ số nhị phân (2), bát phân (8) và thập lục phân (16).

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

Để giải được bài toán, điều đầu tiên các bạn phải biết được số thập phân, nhị phân, bát phân, thập lục phân là gì? và cách chuyển đổi giữa các cơ chế này ra sao thì các bạn mới có thể làm được. Nếu các bạn chưa từng nghe các cơ số này thì có thể tham khảo trên google. Dưới đây mình sẽ hướng dẫn chi tiết cách chuyển đổi từ cơ số 10 sang cơ số 2, còn lại các cơ số khác tương tự nhé.

Hệ nhị phân là một hệ đếm dùng hai kí tự 0 và 1 để biểu đạt một số.

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

Ví dụ: ta có một số nguyên 10 là số thập phân, khi chuyển sang số nhị phân sẽ là 1010.

Vậy làm sao nó có thể chuyển được như vậy, đơn giản chỉ là lấy số thập phân đó và chia lấy dư cho 2, khi đó các con số phần dư được lấy ngược từ dưới lên chính là hệ nhị phân.

stack he nhi phan PNG

Như các bạn đã biết thì Stack hoạt động theo quy tắc LIFO (last in first out), vậy tại sao chúng ta không sử dụng Stack vào bài toán này, thay vì ta lưu các số này vào mảng ta chỉ cần lưu nó vào Stack rồi lấy nó ra theo quy tắc LIFO là xong.

Cứ mỗi lần chia lấy dư như vậy ta sẽ lưu vào Stack, cho đến khi số chia bằng 0 thì ta thực hiện lấy phần tử đầu (top) trong Stack ra, như vậy dãy số được lấy ra chính là dãy nhị phân.

Tương tự như vậy, để chuyển sang cơ số 8 và 16 ta cũng thực hiện chia lấy dư.

2. Ứng dụng Stack để chuyển đổi cơ số

Trước khi bắt đầu viết hàm chuyển đổi cơ số, ta cần khởi tạo các cấu trúc Node và Stack, trong bài toán này mình sẽ sử dụng 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;

/* 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;
}

Tiếp đến ta viết một hàm kiểm tra Stack rỗng, đây là điều kiện để có thể thêm phần tử hoặc xóa 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;
}

Để thêm được dữ liệu và Stack và lấy dữ liệu ra, ta cần có hàm push() và hàm pop().

/* 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 xong các hàm cơ bản bây giờ chúng ta sẽ tạo hàm Chuyen_Co_So() để chuyển cơ số thập phân sang các cơ số khác. Tham số truyền vào của hàm bao gồm một Stack, cơ số cần đổi và số hệ thập phân cần chuyển.

Ta sẽ dùng vòng lặp while để chia lấy dư số cần chuyển đến khi số đó bằng 0, sau mỗi lần chia như vậy sẽ thêm vào Stack.

/* Hàm đổi cơ số 10 sang các cơ số 2, 8, 16 */
void Chuyen_Co_So(STACK &s, int cosocandoi, int hethapphan)
{
	while (hethapphan != 0)
	{
		int x = hethapphan % cosocandoi;
    // thêm x vào node p
		NODE *p = KhoiTaoNode(x); 
    // thêm node p vào stack
		Push(s, p);
    //tiếp tục chia đến hết
		hethapphan /= cosocandoi;
	}
}

Sau khi chia xong chúng ta sẽ có một Stack bao gồm các số là phần dư. Nhiệm vụ của chúng ta bây giờ là tạo một hàm xuất các giá trị trong Stack ra theo cơ chế LIFO.

*Lưu ý: Ở hệ bát phân và thập lục phân, khi giá trị lớn hơn 9 sẽ được quy ước thành các chữ cái, cụ thể như sau: 10 <=> A, 11 <=> B, 12 <=> C, 13 <=> D, 14 <=> E và 15 <=> F.

Vì vậy khi xuất các giá trị trong Stack ra màn hình ta cần thêm điều kiện, nếu giá trị < 10 thì ta thực hiện in bình thường, nếu giá trị >= 10 thì ta sẽ xuất ra các chữ cái quy ước.

/* xuất danh sách stack */
void XuatStack(STACK &s)
{
	while (IsEmpty(s) == true)
	{
		int x;
		Pop(s, x);
    //nếu x < 10 thi xuất bình thường
		if (x < 10)
		{
			cout << x;
		}
    //nếu x >= 10 thì xuất chữ cái tương ứng
		else
		{
			if (x == 10)
			{
				cout << "A";
			}
			else if (x == 11)
			{
				cout << "B";
			}
			else if (x == 12)
			{
				cout << "C";
			}
			else if (x == 13)
			{
				cout << "D";
			}
			else if (x == 14)
			{
				cout << "E";
			}
			else if (x == 15)
			{
				cout << "F";
			}
		}
	}
}

Full Code:

#include<iostream>
using namespace std;

/*
Đổi 1 số nguyên sang cơ số 2 8 16
*/

/* 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 đổi cơ số 10 sang các cơ số 2, 8, 16 */
void Chuyen_Co_So(STACK &s, int cosocandoi, int hethapphan)
{
	while (hethapphan != 0)
	{
		int x = hethapphan % cosocandoi;
    // thêm x vào node p
		NODE *p = KhoiTaoNode(x); 
    // thêm node p vào stack
		Push(s, p);
    //tiếp tục chia đến hết
		hethapphan /= cosocandoi;
	}
}

/* xuất danh sách stack */
void XuatStack(STACK &s)
{
	while (IsEmpty(s) == true)
	{
		int x;
		Pop(s, x);
    //nếu x < 10 thi xuất bình thường
		if (x < 10)
		{
			cout << x;
		}
    //nếu x >= 10 thì xuất chữ cái tương ứng
		else
		{
			if (x == 10)
			{
				cout << "A";
			}
			else if (x == 11)
			{
				cout << "B";
			}
			else if (x == 12)
			{
				cout << "C";
			}
			else if (x == 13)
			{
				cout << "D";
			}
			else if (x == 14)
			{
				cout << "E";
			}
			else if (x == 15)
			{
				cout << "F";
			}
		}
	}
}

int main()
{
	STACK s;
	KhoiTaoStack(s);
	
	int hethapphan,cosocandoi;
	cout << "\nNhập giá trị thập phân cần chuyển: ";
	cin >> hethapphan;
  do{
    cout << "\nNhập cơ số cần chuyển (2, 8, 16):  ";
	  cin >> cosocandoi;
  }while(cosocandoi != 2 && cosocandoi != 8 && cosocandoi != 16);

	Chuyen_Co_So(s, cosocandoi, hethapphan);
	cout << "\nKết quả:\n";
	XuatStack(s);
	cout << endl;

  cout<<"\n-------------------------\n";
  cout<<"Chương trình này được đăng tại Freetuts.net";
}

Kết quả: Mình chỉ thực hiện chuyển số thập phân sang nhị phân, các hệ khác các bạn có thể test thử nhé.

stack chuyen doi co so 1 PNG

3. Kết luận

Như vậy là chúng ta đã thực hiện xong chương trình chuyển đổi cơ số thập phân sang cơ số nhị phân, bát phân, thập lục phân. Đây là một bài toán khá phổ biến trong các ngôn ngữ lập trình, vì vậy các bạn hãy nắm thật kỹ. Để có thể hiểu rõ hơn về Stack các bạn có thể luyện tập thêm nhiều bài toán khác áp dung Stack. 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 kiểm tra số nguyên tố bằng Stack

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

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…

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