DANH SÁCH LIÊN KẾT - NGĂN XẾP VÀ HÀNG ĐỢI (tt)

Ngăn x p (Stack) là m t danh sách mà ta gi i h n vi c thế ộ ớ ạ ệ êmvào hoặc loại bỏ một phần tử chỉ thực hiện tại một đầu của danhsách, đầu này gọi là đỉnh (TOP) của ngăn xếp.
Nội dung trích xuất từ tài liệu:
DANH SÁCH LIÊN KẾT - NGĂN XẾP VÀ HÀNG ĐỢI (tt)CHƯƠNG I : TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ THUẬT GI ẢICHƯƠNG II : MỘT SỐ THUẬT TOÁN TÌM KIẾM VÀ SẮP XẾPCHƯƠNG III : DANH SÁCH LIÊN KẾT - NGĂN XẾP VÀ HÀNG ĐỢICHƯƠNG IV : CÂYI. NGĂN XẾP ( STACK )1. Giới Thiệu Top LIFO: Last In First Out - Vào Sau Ra Trước.I. NGĂN XẾP ( STACK )1. Định Nghĩa  Ngăn xếp (Stack) là một danh sách mà ta giới hạn việc thêm vào hoặc loại bỏ một phần tử chỉ thực hiện tại một đầu của danh sách, đầu này gọi là đỉnh (TOP) của ngăn xếp.  LIFO: Last In First Out - vào sau ra trước.  Các thao tác trong stack:  Push: chèn phần tử mới vào stack  Pop: lấy phần tử đầu stack ra khỏi stack  Top: kiểm tra phần tử đầu stackI. NGĂN XẾP ( STACK )2. Khai báo cấu trúc dữ liệu cho stack pFirst NULL 4 14 22 38 19 0 1 2 3 4 5 6 8 7I. NGĂN XẾP ( STACK )2. Khai báo cấu trúc dữ liệu cho stack Khai báo ngăn xếp dạng mảng Khai báo ngăn xếp dạng DSLK # define size 200 struct stack struct stack { { int info; int n; stack *pNext; e [size]; }; int Top_idx; //giữ vị trí đỉnh ngăn xếp };I. NGĂN XẾP ( STACK )2. Các phép toán trên ngăn xếp  Tạo một ngăn xếp rỗng.  Hàm trả về phần tử tại đỉnh ngăn xếp. Nếu ngăn xếp rỗng thì hàm không xác định.  Chương trình con xoá một phần tử tại đỉnh ngăn xếp.  Chương trình con thêm một phần tử x vào đầu ngăn xếp.  Hàm kiểm tra ngăn xếp rỗng. Hàm cho kết quả 1 (true) nếu ngăn xếp rỗng và 0 (false) trong trường hợp ngược lại.I. NGĂN XẾP ( STACK )2. Các phép toán trên ngăn xếp2.1 Cài đặt bằng DSLK  InitializeStack: Khởi động một Stack. Ban đầu Stack chưa có phần tử. void InitializeStack (stack* &Top) { Top = NULL; }  EmptyStack( ): Kiểm tra Stack rỗng. int EmptyStack (stack *Top) { return (Top == NULL ? 1 : 0); }I. NGĂN XẾP ( STACK )2. Các phép toán trên ngăn xếp2.1 Cài đặt bằng DSLK  Push( ): thêm một phần tử có nội dung x vào đầu Stack. void Push (stack* &Top, int x) { stack *p; p = new stack; p->info = x; p->pNext = Top; Top = p; }I. NGĂN XẾP ( STACK )2. Các phép toán trên ngăn xếp2.1 Cài đặt bằng DSLK  Pop( ): Lấy phần tử đầu danh sách. void Pop (stack* &Top) { stack *p; if (Empty (Top)) cout pNext; delete p; } }I. NGĂN XẾP ( STACK )2. Các phép toán trên ngăn xếp2.1 Cài đặt bằng DSLK GetTop( ): Lấy thông tin về phần tử đầu danh sách. int GetTop (stack* Top) { stack *p; p = Top; if (p != NULL ) return (p->info); else { cout I. NGĂN XẾP ( STACK )2. Các phép toán trên ngăn xếp2.1 Cài đặt bằng DSLK  DeleteAllStack( ): Xoá toàn bộ stack. void DeleteAllStack (stack* &Top) { stack *p; while (Top != NULL) // reach to end ? { p = Top; Top = p->pNext; delete p; } }I. NGĂN XẾP ( STACK )2. Các phép toán trên ngăn xếp2.2 Cài đặt bằng mảng 14 38 19 22 4 8 13 42 1 2 0 1 2 3 4 5 6 7 8# define size 200struct stack{ int n; e [size ]; int Top_idx; //giữ vị trí đỉnh ngăn xếp};I. NGĂN XẾP ( STACK )2. Các phép toán trên ngăn xếp2.2 Cài đặt bằng mảng Khởi tạo một Stack. Ban đầu Stack chưa có phần tử. void InitializeStack(stack &S) { S.Top_idx = size; } Kiểm tra Stack rỗng.  Kiểm tra Stack đầy. int EmptyStack (stack S) int FullStack (stack S) { { return S.Top_idx == size; return S.Top_idx == 0; } }I. NGĂN XẾP ( STACK )2. Các phép toán trên ngăn xếp2.2 Cài đặt bằng mảng  Thêm một phần tử có nội dung x vào đầu Stack. void PushStack(int X, stack &S) { if (FullStack(S)) cout I. NGĂN XẾP ( STACK )2. Các phép toán trên ngăn xếp2.2 Cài đặt bằng mảng  Lấy ra phần tử đầu Stack . void PopStack(stack &S) { if (!EmptyStack(S)) S.Top_idx = S.Top_idx + 1; else cout I. NGĂN XẾP ( STACK )2. Các phép toán trên ngăn xếp2.2 Cài đặt bằng mảng  Lấy giá trị phần tử đầu Stack. int TopStack(stack S) { if (!Empty_Stack(S)) return S.e[S.Top_idx]; else { cout I. NGĂN XẾP ( STACK )2. Các phép toán trên ngăn xếp2.2 Cài đặt bằng mảng  Xoá toàn bộ stack. Gọi Hàm khởi tạo vì dãy không cần phải xóa phần tửI. NGĂN XẾP ( STACK )3. Ứng dụng  Giải bài toán tháp HN Có ba cọc A,B,C. Khởi đầu cọc A có một số đĩa xếp theo thứ tự nhỏ dần lên trên đỉnh. Bài toán đặt ra là phải chuyển toàn bộ chồng đĩa từ A sang B. Mỗi lần thực hiện chuyển một đĩa từ một cọc sang một cọc khác và không được đặt đĩa lớn nằm trên đĩa nhỏI. NGĂN XẾP ( STACK )3. Ứng dụng void Move(int N, int A, int B, int C) //n: so dia, A,B,C: nguon , dich va trung gian { if (N == 1) cout I. NGĂN XẾP ( STACK ) ...