Bài viết này được đăng tại
freetuts.net
Bạn đang đọc: Ứng dụng Stack vào bài toán chuyển đổi cơ số
, không được copy dưới mọi hình thức.
Chúng ta sẽ cùng nhau triển khai 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 ) .
Tóm Tắt
1. Gợi ý cách thực hiện
Để giải được bài toán, điều tiên phong những 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 những chính sách này thế nào thì những bạn mới hoàn toàn có thể làm được. Nếu những bạn chưa từng nghe những cơ số này thì hoàn toàn có thể tìm hiểu thêm trên google. Dưới đây mình sẽ hướng dẫn cụ thể cách chuyển đổi từ cơ số 10 sang cơ số 2, còn lại những cơ số khác tương tự như nhé .
Hệ nhị phân là một hệ đếm dùng hai kí tự 0 và 1 để diễn đạt một số ít .
Ví dụ : ta có một số ít nguyên 10 là số thập phân, khi chuyển sang số nhị phân sẽ là 1010 .
Vậy làm thế nào nó hoàn toàn có thể chuyển được như vậy, đơn thuần chỉ là lấy số thập phân đó và chia lấy dư cho 2, khi đó những số lượng phần dư được lấy ngược từ dưới lên chính là hệ nhị phân .
Như những bạn đã biết thì Stack hoạt động giải trí theo quy tắc LIFO ( last in first out ), vậy tại sao tất cả chúng ta không sử dụng Stack vào bài toán này, thay vì ta lưu những 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 thi lấy thành phần đầ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 thi 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 kèm theo để hoàn toàn có thể thêm thành phần hoặc xóa thành phần .
/* 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 tất cả chúng ta sẽ có một Stack gồm có những số là phần dư. Nhiệm vụ của tất cả chúng ta giờ đây là tạo một hàm xuất những giá trị trong Stack ra theo chính sá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 những giá trị trong Stack ra màn hình hiển thị ta cần thêm điều kiện kèm theo, nếu giá trị < 10 thì ta thực thi in thông thường, nếu giá trị > = 10 thì ta sẽ xuất ra những vần âm 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:
#includeusing 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é.
3. Kết luận
Như vậy là tất cả chúng ta đã triển khai 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ổ cập trong những ngôn từ lập trình, thế cho nên những bạn hãy nắm thật kỹ. Để hoàn toàn có thể hiểu rõ hơn về Stack những bạn hoàn toàn có thể rèn luyện thêm nhiều bài toán khác áp dung Stack. Chúc những bạn thực thi thành công xuất sắc ! ! !
Source: https://final-blade.com
Category: Kiến thức Internet
