Bài giảng Lập trình Java: Bài 12 - Bùi Trọng Tùng

Bài 12 giới thiệu một số cấu trúc dữ liệu trong Java. Nội dung chính trong bài này gồm có: Danh sách liên kết (Linked List), ngăn xếp (Stack), hàng đợi (Queue), cây (Tree). Mời các bạn cùng tham khảo để biết thêm các nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Lập trình Java: Bài 12 - Bùi Trọng Tùng 05/10/2014 BÀI 12. MỘT SỐ CẤU TRÚC DỮ LIỆU TRONG JAVA 1Nội dung• Danh sách liên kết (Linked List)• Ngăn xếp (Stack)• Hàng đợi (Queue)• Cây (Tree) 2 1 05/10/2014 1. DANH SÁCH LIÊN KẾT (LINKED-LIST) 3Mảng vs Danh sách liên kết(DSLK)• Hạn chế của mảng Unused spaces X A BThêm một phần tử. Xóa một phần tử. Y 4 2 05/10/2014Mảng vs Danh sách liên kết X A B I want to add Y after A. Y ? 5Ý tưởng xây dựng DSLK• Mỗi phần tử trong danh sách, gọi là một nút, chứa một tham chiếu trỏ đến nút tiếp theo• Các phần tử không nằm kế tiếp nhau trên bộ nhớ: • Mảng: Các phần tử nằm kế tiếp nhau trên bộ nhớ element next element next ai ai+1 … … và nút kế tiếp trong danh sách (nhưng Một nút trong không nhất thiết phải kế tiếp trong bộ nhớ) danh sách… element next ak Tham chiếu next là null: không có nút kế tiếp 6 3 05/10/2014Nhắc lại: Tham chiếu x 20 int x = 20; Integer y = new Integer(20); y 20 Integer ClassName myObject; new MyClass(); myObject = new MyClass(); Bộ Bộ nhớ myObject nhớ stack Đối tượng heap myObject là tham chiếu 7 Nhắc lại: Tham chiếu(tiếp) Integer y = new Integer(20); y 20 Integer w; Integer w = new Integer(20); if (w == y) System.out.println(1. w == y); w 20 w = y; Integer if (w == y) System.out.println(2. w == y); • Kết quả hiển thị là gì? 8 4 05/10/2014Nhắc lại (tham chiếu)• Mô tả nào là đúng về e trên bộ nhớclass Employee { private String name; Employee e = new Employee(Alan, 2000); private int salary;} (A) e (B) e Alan 2000 Alan 2000 (C) e (D) e 2000 Alan Alan 2000 9Xây dựng DSLK trên Java• Sử dụng kỹ thuật lập trình tổng quát• Giao diện IList định nghĩa các phương thức IList.javaimport java.util.*;public interface IList { public boolean isEmpty(); public int size(); public E getFirst() throws NoSuchElementException; public boolean contains(E item); public void addFirst(E item); public E removeFirst() throws NoSuchElementException; public void print();} ...