TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 có nội dung trình bày về các cấu trúc dữ liệu cho các tập rời nhau, thao tác lên cấu trúc dữ liệu các tập rời nhau, ứng dụng của các tập rời nhau, biểu diễn các tập rời nhau dùng danh sách liên kết, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | Các Cấu Trúc Dữ Liệu cho các Tập Rời Nhau 1 Các thao tác lên cấu trúc dữ liệu các tập rời nhau ª Cấu trúc dữ liệu các tập rời nhau được định nghĩa bởi Một tập S của các tập động rời nhau S S1 S2 . Sk Mỗi tập Si được tượng trưng bởi một phần tử đại diện là một phần tử nào đó của nó. Các thao tác MAKE-SET x tạo một tập mới chỉ gồm x. Vì các tập là rời nhau nên x không được đang nằm trong một tập khác. UNION x y tạo tập hội của các tập động Sx và Sy lần lượt chứa x và y với điều kiện là Sx và Sy là rời nhau. FIND-SET x trả về một con trỏ chỉ đến phần tử đại diện của tập chứa x. ª Để cho gọn sẽ dùng các tập rời nhau để gọi cấu trúc dữ liệu các tập rời nhau . Chương 7 C ác cấu trúc dữ liệu cho 2 các tập rời nhau Các thao tác lên các tập rời nhau tiếp ª Phân tích thời gian chạy của các thao tác sẽ dựa trên hai tham số sau n số các thao tác MAKE-SET m số tổng cộng các thao tác MAKE-SET UNION và FIND-SET. ª Nhận xét Sau n 1 lần gọi UNION lên các tập rời nhau thì còn lại đúng một tập. m n. Chương 7 C ác cấu trúc dữ liệu cho 3 các tập rời nhau Một ứng dụng của các tập rời nhau ª Xác định các thành phần liên thông của một đồ thị vô hướng Thủ tục CONNECTED-COMPONENTS xác định các thành phần liên thông của một đồ thị vô hướng. V G là tập các đỉnh của đồ thị G E G là tập các cạnh của G. CONNECTED-COMPONENTS G 1 for mỗi đỉnh v V G 2 do MAKE-SET v 3 for mỗi cạnh u v E G 4 do if FIND-SET u FIND-SET v 5 then UNION u v Chương 7 C ác cấu trúc dữ liệu cho 4 các tập rời nhau Một ứng dụng của các tập rời nhau tiếp Thủ tục SAME-COMPONENT xác định hai đỉnh có cùng một thành phần liên thông hay không. SAME-COMPONENT u v 1 if FIND-SET u FIND-SET v 2 then return TRUE 3 else return FALSE Chương 7 C .

• Cơ sở dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu các tập rời nhau
• Biểu diễn tập rời nhau
• Biểu diễn tập bằng danh sách liên kết
• Biểu diễn tập bằng cây
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• tài liệu Cấu trúc dữ liệu và giải thuật
• giáo trình Cấu trúc dữ liệu và giải thuật
• bài tập Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu
• Ngôn ngữ diễn đạt giải thuật
• Thiết kế và phân tích giải thuật
• Giải thuật đệ quy
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu cơ bản
• Kiểu dữ liệu trừu tượng
• Tổng quan về giải thuật
• Kiểu dữ liệu
• Các tiêu chuẩn đánh giá dữ liệu
• Cách diễn đạt giải thuật
• Phân tích giải thuật
• phân tích thiết kế
• thiết kế hướng đối tượng
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm