Bài giảng Các kĩ thuật lập trình: Phần 2

Bài giảng Các kĩ thuật lập trình: Phần 2 trình bày các nội dung chính sau: Ngăn xếp, hàng đợi và danh sách móc nối; Cây; Đồ thị và cuối cùng là Sắp xếp và tìm kiếm. Phần phụ lục là bài tập tổng hợp lại những kiến thức cơ bản nhất đã được đề cập trong bài giảng và được thể hiện bằng một chương trình. Mời các bạn cùng tham khảo để nắm nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Các kĩ thuật lập trình: Phần 2 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG -------------------- KHOA CÔNG NGHỆ THÔNG TIN BÀI GIẢNG CÁC KĨ THUẬT LẬP TRÌNH NGUYỄN DUY PHƯƠNG HàNội 2017 CHƢƠNG 4. NGĂN XẾP, HÀNG ĐỢI, DANH SÁCH LIÊN KẾT 4.1. Kiểu dữ liệu ngăn xếp và ứng dụng 4.1.1. Định nghĩa và khai báo Ngăn xếp (Stack) hay bộ xếp chồng là một kiểu danh sách tuyến tính đặc biệt mà phép bổ xung phần tử và loại bỏ phần tử luôn luôn đƣợc thực hiện ở một đầu gọi là đỉnh (top). Có thể hình dung stack nhƣ một chồng đĩa đƣợc xếp vào hộp hoặc một băng đạn đƣợc nạp vào khẩu súng liên thanh. Quá trình xếp đĩa hoặc nạp đạn chỉ đƣợc thực hiện ở một đầu, chiếc đĩa hoặc viên đạn cuối cùng lại chiếm vị trí ở đỉnh đầu tiên còn đĩa đầu hoặc viên đạn đầu lại ở đáy của hộp (bottom), khi lấy ra thì đĩa cuối cùng hoặc viên đạn cuối cùng lại đƣợc lấy ra trƣớc tiên. Nguyên tắc vào sau ra trƣớc của stack còn đƣợc gọi dƣới một tên khác LIFO (Last- in- First- Out). Stack có thể rỗng hoặc bao gồm một số phần tử. Có hai thao tác chính cho stack là thêm một nút vào đỉnh stack (push) và loại bỏ một nút tại đỉnh stack (pop). Nếu ta muốn thêm một nút vào đỉnh stack thì trƣớc đó ta phải kiểm tra xem stack đã đầy (full) hay chƣa, nếu ta muốn loại bỏ một nút của stack thì ta phải kiểm tra stack có rỗng hay không. Hình 4.1 minh họa sự thay đổi của stack thông qua các thao tác thêm và bớt đỉnh trong stack. Giả sử ta có một stack S lƣu trữ các kí tự. Trạng thái bắt đầu của stack đƣợc mô tả trong hình a. Khi đó thao tác: push(S,‟G‟) (hình b) push(S,‟H‟) (hình c) pop(S) (hình d) pop(S) (hình e) push(S,‟I‟) (hình f) H G G G I F F F F F F E E E E E E D D D D D D C C C C C C B B B B B B A A A A A A (hình a) (hình b) (hình c) (hình d) (hình e) (hình f) Có thể lƣu trữ stack dƣới dạng một vector S gồm n thành phần liên tiếp nhau. Nếu T là là địa chỉ của phần tử đỉnh stack thì T sẽ có giá trị biến đổi khi stack hoạt động. Ta 78 gọi phần tử đầu tiên của stack là phần tử thứ 0, nhƣ vậy stack rỗng khi T có giá trị nhỏ hơn 0 ta qui ƣớc là -1. Stack tràn khi T có giá trị là n-1. Mỗi khi một phần tử đƣợc thêm vào stack, giá trị của T đƣợc tăng lên 1 đơn vị, khi một phần tử bị loại bỏ khỏi stack giá trị của T sẽ giảm đi một đơn vị. TOP T BOOTTOM S1 S2 S3 ... ST ... Để khai báo một stack, chúng ta có thể dùng một mảng một chiều. Phần tử thứ 0 là đáy stack, phần tử cuối của mảng là đỉnh stack. Một stack tổng quát là một cấu trúc gồm hai trƣờng, trƣờng top là một số nguyên chỉ đỉnh stack. Trƣờng node: là một mảng một chiều gồm MAX phần tử trong đó mỗi phần tử là một nút của stack. Một nút của stack có thể là một biến đơn hoặc một cấu trúc phản ánh tập thông tin về nút hiện tại. Ví dụ, khai báo stack dùng để lƣu trữ các số nguyên. #define TRUE 1 #define FALSE 0 #define MAX 100 typedef struct { int top; int nodes[MAX]; } stack; 4.1.2. Các thao tác với stack Trong khi khai báo một stack dùng danh sách tuyến tính, chúng ta cần định nghĩa MAX đủ lớn để có thể lƣu trữ đƣợc mọi đỉnh của stack. Một stack đã bị tràn (TOP = MAX- 1) thì nó không thể thêm vào phần tử trong stack, một stack rỗng thì nó không thể đƣa ra phần tử. Vì vậy, chúng ta cần xây dựng thêm các thao tác kiểm tra stack có bị tràn hay không (full) và thao tác kiểm tra stack có rỗng hay không (empty). Thao tác Empty: Kiểm tra stack có rỗng hay không: int Empty(stack *ps) { if (ps ->top == -1) return(TRUE); return(FALSE); } Thao tác Push: Thêm nút mới x vào đỉnh stack và thay đổi đỉnh stack. void Push (stack *ps, int x) { 79 if ( ps ->top == -1) { printf(“\n stack full”); return; } ps -> top = ps ->top + 1; ps -> nodes[ps->top] = x; } Thao tác Pop : Loại bỏ nút tại đỉnh stack. int Pop ( stack *ps) { if (Empty(ps) { printf(“\n stack empty”); return(0); } return( ps -> nodes[ps->top --]); } 4.1.3. ứng dụng của stack Ví dụ 4.1. Chƣơng trình đảo ngƣợc xâu kí tự: quá trình đảo ngƣợc một xâu kí tự giống nhƣ việc đƣa vào (push) từng kí tự trong xâu vào stack, sau đó đƣa ra (pop) các kí tự trong stack ra cho tới khi stack rỗng ta đƣợc một xâu đảo ngƣợc. Chƣơng trình sau sẽ minh họa cơ chế LIFO đảo ngƣợc xâu kí tự sử dụng stack. #include #include #include #include #include #define MAX 100 #define TRUE 1 #define FALSE 0 typedef struct{ int top; char node[MAX]; } stack; /* nguyen mau cua ham*/ int Empty(stack *); void Push(stack *, char); char Pop(stack *); /* Mo ta ham */ int Empty(stack *ps){ ...