Cài đặt ngăn xếp bằng danh sách liên kết
Ngăn xếp Stack Cài đặt ngăn xếp bằng mảng code C/C++By Như Quỳnh- 1 9618 Facebook Twitter Pinterest Email Ngăn xếp và hàng đợi là những cấu trúc dữ liệu quan trọng. Bài viết chia sẻ code ngăn xếp stack C/C++ cài đặt bằng mảng một chiều con trỏ. Cách ứng dụng của stack vào bài tập quản lý danh sách liên kết. Show
Mục lục bài viết
1. Ngăn xếp Stack là gì?Ngăn xếp ( Stack ) trong C ++ là một cấu trúc dữ liệu tương tự như danh sách liên kết đơn, hay Queue hàng đợi. Đặc điểm của ngăn xếp: Tuân theo quy luật vào trước ra sau hay là vào sau ra trước ( FILO First In Last Out hoặc LIFO Last In First OUT ) Ngoài ngôn ngữ lập trình C/C++, thì tất cả các ngôn ngữ khác như Python, C#, PHP, Java, Javascript . . . đều sử dụng tới cấu trúc này! Hình ảnh mô phòng ngăn xếp: 1.1 Các dạng biểu diễn của ngăn xếpThực chất stack là một danh sách liên kết , nên bạn có thể sử dụng một trong các dạng cài đặt sau:
Ở bài viết này mình sẽ sử dụng cách thứ 2 tức sử dụng mảng 1 chiều. 1.2 Các phép toán trên ngăn xếpĐối với cấu trúc dữ liệu stack, bạn chắc chắn sẽ phải sử dụng những phép toán sau:
Lưu ý rằng các tên hàm mình kể bên trên là do bạn tự định nghĩa. Vì code trong bài mình sẽ đặt têm hàm như vậy nên mình viết cho bạn đọc dễ hiểu thôi nhé! 2. Ngăn xếp cài đặt bằng mảngBài toán: Cài đặt ngăn xếp stack các số nguyên, viết hàm chèn phần tử vào vị trí bất kỳ! Mình sẽ sử dụng ngôn ngữ C++ để giải quyết bài toán nhé! Nếu như bạn đang tìm code C thì chỉ cần thay đổi câu lệnh nhập xuất cin, cout thành scanf, printf là được. Chú ý: Lỗi hiển thị, mình không biết tại sao nhưng tất cả dấu & trong bài viết đều chuyển thành & ; 2.1 Khai báo cài đặt ngăn xếpNgăn xếp stack cài đặt bằng mảng một chiều sẽ có một biến Top dùng đế lưu vị trí hiện tại, vị trí đỉnh của ngăn xếp. //
// Cai dat ngan xep
typedef int item; // Kieu cua ngan xep
#define Max 100 // So phan tu toi da cua Stack
struct Stack{
int Top;
item Data[Max];
};
Stack S; // Khai bao ngan xep S
2.2 Nhóm hàm khởi tạo và kiểm traHàm khởi tạo ngăn xếp: Chỉ cần cho giá trị của biến Top = 0 là xong. //Khoi tao ngan xep
void Init (Stack & S){
S.Top = 0;
}
//Kiem tra ngan xep rong
int Isempty( Stack S){
return (S.Top==0);
}
//Kiem tra ngan xem day
int Isfull(Stack S){
return (S.Top == Max);
}
2.3 Thêm phần tử vào đầu stack Hàm PushHàm Push dùng để thêm phần tử vào đầu ngăn xếp. Tăng biến Top lên một đơn vị rồi gán Data ở vị trí Top bằng x. Như vậy giá trị x đã được thêm vào đầu danh sách. //
//Ham Push them phan tu x vao dau ngan xep
void Push(Stack & S, item x){
if(Isfull(S))
cout<<"\nNgan xep day!"< 2.4 Hàm lấy phần tử đầu Pop StackHàm này bản chất tương tự hàm Push. Bạn cần khai báo một biến dùng để đựng giá trị của phần tử đầu stack. Sau đó giảm giá trị của biến Top, return về biến đã lưu. // Ham Pop lay phan tu khoi dau ngan xep
item Pop(Stack & S){
if(Isempty(S))
cout<<"\n Ngan xep rong! "< 2.5 Hàm chèn vào vị trí k bất kì trong ngăn xếpChèn vào vị trí bất kì sẽ phức tạp hơn rất nhiều hàm chèn đầu. Chính vì phải thao tác với stack theo đúng nguyên tắc Vào trước ra sau (Fisrt In Last Out) nên mới phức tạp. Minh sử dụng cả hàm Push và hàm Pop trong hàm này. Ý tưởng đưa ra là khai báo một Stack tạm thời dùng đế lưu trữ giá trị từ vị trí k đến vị trí Pop của danh sách cần chèn. Tức là bạn lấy giá trị ra khỏi ngăn xếp cho tới vị trí cần chèn , sau đó chèn phần tử cần chèn vào. Sau khi chèn thì lại thêm lại các phần tử vừa lấy ra. Xem code cho nhanh hiểu nào: //
// Chen phan tu x vao vi tri k
void Insert_k(Stack & S, item x, int k){
if(k<1 || k>S.Top)
cout<<"\nVi tri chen khong hop le! "< 2.6 Hàm nhập phần tử InputNhập như thế nào là tùy theo từng bài toán. Tùy theo cách bạn muốn nhập phần tử vào ngăn xếp. Ở đây mình quản lý ngăn xếp các số nguyên nên có thế khác vấn đề bạn cần tìm một chút. Tuy nhiên bạn chỉ cần sửa một chút phần nhập dữ liệu từ bàn phím là ok. Mình viết hàm nếu nhập giá trị là 0 thì sẽ ngừng nhập. Bạn tham khảo nhé! //
// Ham Nhap
void Input(Stack&S){
cout<<"\nNhap gia tri cho Stack \nNhap 0 de ket thuc "< 2.7 Hàm xuất Output StackXuất dữ liệu ra màn hình thì thật đơn giản. Dùng Pop đế lấy giá trị và in ra màn hình là ok rồi. //
//Ham xuat
void Output(Stack S){
while(S.Top!=0)
cout<<" "<
3. Chương trình hoàn chỉnhTham khảo toàn bộ bài code này trên Github của mình tại đây! Nếu bạn viết với ngôn ngữ C thì đổi chút khai báo thư viện, lệnh nhập xuất (cin, cout thành scantf, printf tương ứng là được nhé) Code Stack C++: // Ngan xep cai dat bang mang
/*
Cac ham can viet:
+ Them phan tu vao dinh Push
+ Xoa phan tu khoi dinh Pop
+ Nhap xuat du lieu
+ Them xoa o day phan tu
*/
#include Kết quả khi chạy chương trình trên
Facebook Twitter Pinterest Email Previous articleCách đổi tên đường dẫn link Facebook tới trang cá nhân, fan Page Next articleGoogle Adsense là gì? Có nên chọn kiếm tiền với Google Adsene? |