Bài tập chuyển đổi cơ số bằng Stack - Ngăn xếp 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ố. 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ị ...
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ố.
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ố.
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.
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 << "
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;
}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 << "
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 đổ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 << "
Nhập giá trị thập phân cần chuyển: ";
cin >> hethapphan;
do{
cout << "
Nhậ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 << "
Kết quả:
";
XuatStack(s);
cout << endl;
cout<<"
-------------------------
";
cout<<"Chương trình này được đăng tại Zaidap.com.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é.
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 !!!
