Ngôn ngữ lập trình C - Chương 7 - Bài 2. Stack

Stack (ngăn xếp)- Là một cấu trúc dữ liệu mà cácthao tác xử lý chỉ được thực hiệnở phía đáy (cuối) của nó
Nội dung trích xuất từ tài liệu:
Ngôn ngữ lập trình C - Chương 7 - Bài 2. Stack 4/28/2010 Chương 7. Bài 2. Stack ĐỖ BÁ LÂM ViỆN CNTT&TT, TRƯỜNG ĐHBK HÀ NỘINội dung 1. Khái niệm stack 2. Xây dựng stack 2.1. Sử dụng mảng 2.2. Sử dụng danh sách liên kết 21. Khái niệm stack Stack (ngăn xếp)  Là một cấu trúc dữ liệu mà các thao tác xử lý chỉ được thực hiện ở phía đáy (cuối) của nó  Cấu trúc dạng LIFO (Last In First Out) – “Vào sau ra trước”  Thao tác xử lý • Đẩy vào PUSH • Lấy ra POP 3 1 4/28/2010 1. Khái niệm stack Đỉnh Đáy 1. Khái niệm stack Push(B) Pop() Pop()Push(A) A B A B B A A A Stack rỗng Stack có 1 phần tử: Stack có 2 phần tử: Stack còn 1 phần tử: Stack lại rỗng A AB A Ứng dụng của Stack  Lưu trữ các trang web đã từng được duyệt trên Web browser  Cài đặt thao tác Undo trong các phần mềm soạn thảo  Lưu danh sách các lời gọi hàm trong Java Virtual Machine 2 4/28/2010 Ghi nhớ Stack được hình dung như một ngăn xếp chứa các quyển sách với 2 thao tác đưa vào và lấy ra theo nguyên tắc:  Quyển sách nào được đưa vào sau sẽ lấy ra trước – LIFO (Last In First Out) Ví dụ - Bài toán chuyển cơ số  Nguyên tắc đổi một số nguyên từ thập phân sang nhị phân: Các số dư lấy ra sau được hiển thị trước Cơ chế sắp xếp của Stack Giải pháp  Dùng stack để lưu trữ số dư qua từng phép chia:  Khi thực hiện phép chia: Đưa số dư vào Stack  Khi hiển thị kết quả: Lấy chúng lần lượt từ Stack 3 4/28/2010 Giải pháp 1 1 1 PUSH 0 0 0 PUSH 0 0 0 0 1 1 0 0 1 1 1 POP 0 0 0 0 0 0 0 Giải thuật 1. Nhap N 2. while N != 0 R = N% 2; //Tính số dư trong phép chia N cho 2 PUSH (S, R); //Đẩy R vào đỉnh Stack S N=N/2; //Thay N bằng N/2 3. while S chưa rỗng POP(S,R); //Lấy phần tử từ stack đưa vào R Hien_thi R; 2. Xây dựng Stack Lưu trữ được các đối tượng dữ liệu (quyển sách) Xây dựng 2 thao tác Push và Pop theo nguyên tắc LIFO Có hai cách cài đặt stack  Sử dụng mảng  Sử dụng danh sách liên kết 4 4/28/20102.1. Sử dụng mảng Đáy Stack Mỗi phần tử của stack được lưu như một phần tử của mảng Đáy: phần tử có chỉ số 0 Đỉnh: phần tử được đưa vào cuối cùng, có chỉ số T Khởi tạo T=-1 Stack rỗng (empty) T = -1, stack đầy T = MAX-1 132.1. Sử dụng mảng #define MAX 100 //So phan tu lon nhat cua Stack //Khai bao Stack va T la 2 bien toan cuc ElemType Stack[MAX]; int T=-1; 142.1. Sử dụng mảng Stack được biểu diễn thông qua mảng S[MAX] int push(ElemType N){ if (T==MAX-1) return 0; else{ //mảng chưa đầy T++; S[T]=N; } return 1; } 5 4/28/20102.1. Sử dụng mảng int pop(ElemType *N){ if (T== -1) return 0; else{ *N = S[T--]; return 1; } }2.2. Sử dụng danh sách liên kết Head Stack là cấu trúc LIFO (Last In First Out) Thao tác Push, Pop? 172.2. Sử dụng danh sách liên kết Push  Thêm một nút vào đầu danh sách Pop  Lấy giá trị nút đầu tiên trong danh sách  Loại bỏ nút này khỏi danh sách 18 6 4/28/2010 2.2. Sử dụng danh sách liên kết struct node { ElemType data; ...