tailieunhanh - 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. | 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 . Kiểu dữ liệu ngăn xếp và ứng dụng . Đị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 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 .