tailieunhanh - Bài giảng Cấu trúc dữ liệu 1: Chương 3D - Huỳnh Cao Thế Cường

Các nội dung chính được trình bày trong chương này gồm có: Ngăn xếp (stack), minh họa thao tác, cài đặt ngăn xếp bằng mảng, cài đặt ngăn xếp bằng con trỏ, hàng đợi (queue), cài đặt hàng bằng mảng theo phương pháp tịnh tiến, cài đặt hàng với mảng xoay vòng,. . | CẤU TRÚC DỮ LIỆU 1 Giảng viên phụ trách: HUỲNH CAO THẾ CƯỜNG Bộ môn Tin học email: hctcuong@ TRƯỜNG ĐẠI HỌC AN GIANG KHOA KỸ THUẬT- CÔNG NGHỆ - MÔI TRƯỜNG NGĂN XẾP (STACK) Ngăn xếp (Stack): là một danh sách mà 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. Stack là một cấu trúc có tính chất “vào sau - ra trước” hay “vào trước – ra sau“ (LIFO (last in - first out ) hay FILO (first in – last out)). NGĂN XẾP (STACK) Đỉnh ngăn xếp Push Pop Minh họa thao tác PUSH Data Top Minh họa thao tác POP Data Top Minh họa thao tác TOP Data Top ? ? NGĂN XẾP (STACK) Các phép toán trên ngăn xếp MAKENULL_STACK(S): tạo một ngăn xếp rỗng. TOP(S) hàm trả về phần tử tại đỉnh ngăn xếp. POP(S) xoá một phần tử tại đỉnh ngăn xếp. PUSH(x,S) thêm một phần tử x vào đầu ngăn xếp. EMPTY_STACK(S) kiểm tra ngăn xếp Cài đặt ngăn xếp bằng mảng Cài đặt ngăn xếp bằng mảng Khai báo ngăn xếp #define MaxLength . //độ dài của mảng typedef . ElementType; //kiểu các phần tử trong ngăn xếp typedef struct { ElementType Elements[MaxLength]; //Lưu nội dung của các phần tử int Top; //giữ vị trí đỉnh ngăn xếp } Stack; Cài đặt ngăn xếp bằng mảng Tạo ngăn xếp rỗng Ngăn xếp rỗng là ngăn xếp không chứa bất kỳ một phần tử nào, do đó đỉnh của ngăn xếp không được phép chỉ đến bất kỳ vị trí nào trong mảng. void Makenull_Stack(Stack *S) { S->Top=MaxLength; } Cài đặt ngăn xếp bằng mảng Kiểm tra ngăn xếp rỗng int IsEmpty_Stack(Stack S) { return ; } Kiểm tra ngăn xếp đầy int IsFull_Stack(Stack S) { return ; } Cài đặt ngăn xếp bằng mảng Lấy nội dung phần tử tại đỉnh của ngăn xếp ElementType Top(Stack S) { if (!IsEmpty_Stack(S)) return []; else printf("Loi! Ngan xep rong"); } Cài đặt ngăn xếp bằng mảng Chú ý Nếu ElementType không thể là kiểu kết quả trả về của một hàm thì ta có thể viết Hàm Top như sau: void Top2(Stack S, Elementtype *X) { //Trong đó x sẽ lưu trữ nội dung | CẤU TRÚC DỮ LIỆU 1 Giảng viên phụ trách: HUỲNH CAO THẾ CƯỜNG Bộ môn Tin học email: hctcuong@ TRƯỜNG ĐẠI HỌC AN GIANG KHOA KỸ THUẬT- CÔNG NGHỆ - MÔI TRƯỜNG NGĂN XẾP (STACK) Ngăn xếp (Stack): là một danh sách mà 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. Stack là một cấu trúc có tính chất “vào sau - ra trước” hay “vào trước – ra sau“ (LIFO (last in - first out ) hay FILO (first in – last out)). NGĂN XẾP (STACK) Đỉnh ngăn xếp Push Pop Minh họa thao tác PUSH Data Top Minh họa thao tác POP Data Top Minh họa thao tác TOP Data Top ? ? NGĂN XẾP (STACK) Các phép toán trên ngăn xếp MAKENULL_STACK(S): tạo một ngăn xếp rỗng. TOP(S) hàm trả về phần tử tại đỉnh ngăn xếp. POP(S) xoá một phần tử tại đỉnh ngăn xếp. PUSH(x,S) thêm một phần tử x vào đầu ngăn xếp. EMPTY_STACK(S) kiểm tra ngăn xếp Cài đặt ngăn xếp bằng mảng Cài đặt ngăn xếp bằng mảng Khai báo ngăn xếp #define MaxLength . //độ dài của