intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Cấu trúc dữ liệu: Chương 5 - Nguyễn Xuân Vinh

Chia sẻ: Xaydung K23 | Ngày: | Loại File: PPTX | Số trang:20

Thêm vào BST
Báo xấu
88
lượt xem 9
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cấu trúc dữ liệu - Chương 5: Danh sách liên kết trình bày về review arrays, linked list (Singly Linked List), pros and cons, non - linear linked list (Cấu trúc phi tuyến tính), classification of linked list, các phép toán trên linked list,...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu: Chương 5 - Nguyễn Xuân Vinh

  1. GV: NGUYỄN XUÂN VINH CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] DANH SÁCH LIÊN KẾT MÔN: CẤU TRÚC DỮ LIỆU (Linked List) Nguyễn Xuân Vinh nguyenxuanvinh@hcmuaf. 6/12/14 edu.vn /20 1
  2. GV: NGUYỄN XUÂN VINH Review Arrays • Pros – Access quickly via array index. – Easier to use. • Cons MÔN: CẤU TRÚC DỮ LIỆU – Fixed size: the size of the array is static. – One block allocation – Complex position-based insertion/removal 6/12/14 /20 2
  3. GV: NGUYỄN XUÂN VINH Linked List (Singly Linked List) • A data structure consisting of a group of nodes which together represent a sequence  a linear structure. • Each node is composed of a data and a reference(*). • Allows more efficient insertion or removal of elements MÔN: CẤU TRÚC DỮ LIỆU from any position in the sequence. • Reference of the last node point to null. • Only need to handle the first (head) element. 6/12/14 /20 (*) There might be two references, references can link to previous or next 3
  4. GV: NGUYỄN XUÂN VINH Pros and cons • Pros – Flexibility: insert/delete from any position in constant time. – No single allocation of memory needed – Dynamic allocation: the size is not required to be known in advance MÔN: CẤU TRÚC DỮ LIỆU q Cons – There is no index to query element directly  not allow random access to element – Complex to use and access. – No constant time access to the elements. Question: How to get the last element in the list? 6/12/14 /20 4
  5. GV: NGUYỄN XUÂN VINH Non-linear Linked List (Cấu trúc phi tuyến tính) • Normally, Linked List is a linear data structure. • However, the complex reference also be a non-linear structure such as Tree, Graph. MÔN: CẤU TRÚC DỮ LIỆU 6/12/14 /20 5
  6. GV: NGUYỄN XUÂN VINH Classification of Linked List • Danh sách liên kết đơn (Singly Linked List) • Danh sách liên kết kép (Doubly Linked List) MÔN: CẤU TRÚC DỮ LIỆU • Danh sách liên kết vòng (Circular Linked List) 6/12/14 /20 6
  7. GV: NGUYỄN XUÂN VINH Các phép toán trên Linked List public class Node { 1) Duyệt các phần tử private T data; 2) Chèn them phần tử private Node next; § Chèn vào đầu public Node(T data, § Chèn vào giữa Node next) { MÔN: CẤU TRÚC DỮ LIỆU 3) Xóa phần tử this.data = data; § Xóa phần tử đầu this.next = next; § Xóa phần tử giữa } public T getData() { return data; } 6/12/14 public void setData(T data) { /20 this.data = data; 7 }
  8. GV: NGUYỄN XUÂN VINH 1) Duyệt Node head = ...; Node current = head; while ((current = current.getNext()) != null) { System.out.println(current); MÔN: CẤU TRÚC DỮ LIỆU } 6/12/14 /20 8
  9. GV: NGUYỄN XUÂN VINH 2) Chèn phần tử Chèn vào đầu danh sách liên kết MÔN: CẤU TRÚC DỮ LIỆU Chèn vào giữa danh sách liên kết 6/12/14 /20 9
  10. GV: NGUYỄN XUÂN VINH 3) Xóa phần tử Xóa phần tử ở đầu danh sách MÔN: CẤU TRÚC DỮ LIỆU Xóa phần tử ở giữa danh sách 6/12/14 /20 10
  11. GV: NGUYỄN XUÂN VINH Danh sách liên kết kép (Doubly Linked List) • Trong danh sách liên kết mà mỗi nút có 2 liên kết trỏ, 1 tới nút liền trước, 1 tới nút liền sau. MÔN: CẤU TRÚC DỮ LIỆU • Ưu điểm: – Có thể duyệt theo cả hai chiều. 6/12/14 /20 11
  12. GV: NGUYỄN XUÂN VINH Danh sách liên kết vòng (Circular Linked List) danh sách liên kết đơn, nút cuối cùng của danh sách trỏ tới • Trong nút đầu tiên A B C D E MÔN: CẤU TRÚC DỮ LIỆU • Ưu điểm: – Bất kỳ nút nào cũng có thể coi là đầu danh sách • Nhược điểm: – Không biết lúc nào là kết thúc của danh sách 6/12/14 /20 12
  13. GV: NGUYỄN XUÂN VINH LinkedList Example 1. LinkedList 2. Node a) Node in different class b) Static inner class Node MÔN: CẤU TRÚC DỮ LIỆU c) Non-static inner class Node 6/12/14 /20 13
  14. GV: NGUYỄN XUÂN VINH 1. LinkedList public class LinkedList { private Node head; public LinkedList(Node head) { this.head = head; } public Node getHead() { return head; MÔN: CẤU TRÚC DỮ LIỆU } public void setHead(Node head) { this.head = head; } } 6/12/14 /20 14
  15. GV: NGUYỄN XUÂN VINH 2. a) Node public class Node { private T data; private Node next; public Node(T data, Node MÔN: CẤU TRÚC DỮ LIỆU next) { this.data = data; this.next = next; } public T getData() { return data; 6/12/14 } /20 public void setData(T data) { 15
  16. GV: NGUYỄN XUÂN VINH 2. b) Static inner class Node public class LinkedList { private Node head; public LinkedList(Node head) { this.head = head; } MÔN: CẤU TRÚC DỮ LIỆU public Node getHead() { return head; } public void setHead(Node head) { this.head = head; } 6/12/14 private static class Node { private T data; /20 private Node next; 16 public Node(T data, Node next) {
  17. GV: NGUYỄN XUÂN VINH 2. c) Non-static inner class Node public class LinkedList { private Node head; private String name; public LinkedList(Node head) { this.head = head; MÔN: CẤU TRÚC DỮ LIỆU } public Node getHead() { return head; } public void setHead(Node head) { this.head = head; 6/12/14 } private class Node { /20 private T data; 17
  18. GV: NGUYỄN XUÂN VINH Complexity: Array vs Linked List Operation Array Singly Linked List Indexing O(1) O(n) MÔN: CẤU TRÚC DỮ LIỆU Insert/Delete at beginning O(n) O(1) Insert/Delete at end O(1) O(n) Insert/Delete in middle O(1) search time + O(1) 6/12/14 /20 18
  19. GV: NGUYỄN XUÂN VINH Tóm tắt • Review Arrays • Introduce LinkedList • Pros and cons • Non-linear Linked List MÔN: CẤU TRÚC DỮ LIỆU • Classification of Linked List • Các phép toán trên Linked List • Danh sách liên kết kép • Danh sách liên kết vòng • Cài đặt LinkedList 6/12/14 /20 19
  20. 20 /20 6/12/14 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH HỎI ĐÁP
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2