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

Danh sách liên kết

Chia sẻ: Nguyễn Hữu Thiên Sơn | Ngày: | Loại File: PDF | Số trang:21

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

Tham khảo tài liệu 'danh sách liên kết', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: Danh sách liên kết

  1. Danh sách liên kết (Linked List) Giới thiệu cấu trúc “Danh sách p liên kết” p Các loại hình danh sách liên k ết Danh sách liên kết đơn p p Danh sách liên kết đôi p Danh sách liên kết vòng Cách xây dựng cấu trúc p Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 1 Nội dung trình bày Đặt vấn đề p p Danh sách liên kết là gì ? p Cấu tạo của nút p Cấu tạo của danh sách liên kết p Các loại danh sách liên kết p So sánh Mảng và Danh sách liên kết p Các thao tác trên danh sách liên kết đơn p Giới thiệu các loại danh sách liên k ết khác Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 2 1
  2. Đặt vấn đề p Nếu muốn thêm (Insert) 1 phần tử vào mảng, phải làm sao ? 10 5 13 11 6 12 9 ? 18 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 3 Đặt vấn đề p Phải di chuyển các phần tử về phía sau 1 vị trí ... 18 10 5 13 11 6 12 9 ? chèn phần tử mới vào p …và 10 5 13 11 6 12 9 18 p Vậy chi phí là O(n) Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 4 2
  3. Đặt vấn đề p Hỏi: muốn xóa (Delete) một phần tử trong mảng ? 10 5 13 11 6 12 9 ? Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 5 Đặt vấn đề sao có thể thêm (hay xoá) 1 phần tử p Làm mà không phải di chuyển các phần tử khác ? p Ta cần phải dùng một cấu trúc lưu trữ mới Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 6 3
  4. Đặt vấn đề tách rời các phần tử của mảng, và kết nối p Ta chúng lại với nhau bằng một “móc xích” 10 20 30 ? ? 18 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 7 Đặt vấn đề tác thêm phần tử chỉ cần thay đổi các p Thao mối liên kết tại chỗ 10 20 30 ? ? 18 phí thấp p Chi Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 8 4
  5. Danh sách liên kết là gì ? Một dãy tuần tự các nút (Node) p Giữa hai nút có con trỏ liên kết p Các nút không cần phải lưu trữ liên tiếp nhau trong bộ nhớ p Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung lượng bộ nhớ) p Thao tác Chèn/Xóa không cần phải dịch chuyển phần tử p Phần tử đầu là pHead p Có thể truy xuất đến các phần tử khác thông qua con trỏ p liên kết Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 9 Cấu tạo của nút p Tạo lập bằng cách cấp phát bộ nhớ động p Mỗi nút có 2 thông tin: p Dữ liệu (data) p Con trỏ liên kết đến phần tử kế tiếp trong danh sách (Next pointer link) p Phần tử cuối cùng trong danh sách có con trỏ Next = NULL Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 10 5
  6. Cấu tạo của nút typedef struct tagNODE { Nút có 1 field dữ liệu int number; tagNODE *pNext; } NODE; Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 11 Cấu tạo của nút typedef struct tagNODE { char name[30]; int id; float grdPts; Nút có nhiều tagNODE *pNext; field dữ liệu } NODE; Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 12 6
  7. Cấu tạo của nút typedef struct INFO { char name[30]; char address[50]; char phone[10]; } Nút có dữ typedef struct tagNODE { liệu là struct INFO data; tagNODE *pNext; } NODE; Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 13 Cấu tạo của danh sách liên kết p Quản lý toàn bộ danh sách liên kết thông qua con trỏ đầu pHead p pHead không ph ải là 1 nút, nó chỉ là “con trỏ chỉ đến nút” mà thôi p Ta cũng có thể quản lý danh sách bằng cách sử dụng thêm con trỏ cuối (pTail) p pTail không ph ải là 1 nút, nó chỉ là “con trỏ chỉ đến nút” mà thôi Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 14 7
  8. Cấu tạo của danh sách liên kết Danh sách liên kết đơn với phần tử đầu là pHead Danh sách “rỗng”, pHead = NULL Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 15 Cấu tạo của danh sách liên kết cần phải định nghĩa 2 cấu trúc lưu trữ: p Ta p Cấu trúc của phần đầu danh sách p Cấu trúc dùng cho các nút trong danh sách List Cấu trúc của Count phần đầu pHead End List Node Data Cấu trúc pNext của nút End Node Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 16 8
  9. Cấu tạo của danh sách liên kết Cấu trúc của phần đầu danh sách // Quản lý danh sách bằng con trỏ đầu typedef struct LINKED_LIST { NODE *pHead; Count; // số nút trong danh sách unsigned int } // Quản lý danh sách bằng con trỏ đầu và cuối typedef struct LINKED_LIST { NODE *pHead; NODE *pTail; Count; // số nút trong danh sách unsigned int } Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 17 Cấu tạo của danh sách liên kết Ví dụ minh họa Count pHead 2 Data pNext 15 Data pNext 99 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 18 9
  10. Các loại danh sách liên kết Danh sách liên kết đơn (Single-Linked list) p Mỗi nút chỉ có 1 con trỏ liên kết (pNext) p Danh sách liên kết đôi (Double-Linked list) p Mỗi nút có 2 con trỏ liên kết (pPrev, pNext) p Danh sách đa liên kết (Multi-Linked list) p Mỗi nút có nhiều hơn 2 con trỏ liên kết p Danh sách liên kết vòng (Circular-Linked list) p Liên kết ở nút cuối cùng của danh sách chỉ đến nút đầu p tiên trong danh sách Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 19 So sánh Mảng và Danh sách liên kết Mảng Danh sách liên kết Kích thước cố định Số phần tử thay đổi tùy ý Các phần tử lưu trữ tuần tự Các phần tử liên kết với nhau (địa chỉ tăng dần) trong bộ nhớ bằng con trỏ Phải tịnh tiến các phần tử khi Chỉ cần thay đổi con trỏ liên muốn Chèn/Xóa 1 phần tử kết khi muốn Chèn/Xóa 1 phần tử Truy xuất ngẫu nhiên Truy xuất tuần tự Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 20 10
  11. Các thao tác trên danh sách liên kết đơn p Tạo lập danh sách rỗng p Kiểm tra danh sách rỗng p Kiểm tra số phần tử trong danh sách p Thêm 1 nút vào danh sách p Xóa 1 nút p Duyệt danh sách p Tìm 1 phần tử Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 21 Các thao tác trên danh sách liên kết đơn Tạo lập danh sách rỗng Count pHead Count pHead ? ? list 0 list Trước khi tạo lập Sau khi tạo lập Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 22 11
  12. Các thao tác trên danh sách liên kết đơn Tạo lập danh sách rỗng void CreateEmptyList(LINKED_LIST &list) { list.Count = 0; list.pHead = NULL; } Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 23 Các thao tác trên danh sách liên kết đơn Tạo lập danh sách rỗng p L ưu ý quan trọng: luôn luôn khởi tạo danh sách rỗng trước khi sử dụng EMPTY LIST Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 24 12
  13. Các thao tác trên danh sách liên kết đơn Kiểm tra danh sách rỗng: p int IsEmptyList(const LINKED_LIST &list) { return (list.pHead == NULL); } Kiểm tra số phần tử trong danh sách: p int CountNode(const LINKED_LIST &list) { return list.Count; } Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 25 Các thao tác trên danh sách liên kết đơn Thêm 1 nút vào danh sách Trước khi thêm: pPrev == NULL Count pHead pNew 99 1 15 list pNew->pNext = list.pHead; Thêm vào đầu list.pHead = pNew; Sau khi thêm: Count pHead 15 2 99 list pNew Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 26 13
  14. Các thao tác trên danh sách liên kết đơn Thêm 1 nút vào danh sách Trước khi thêm: pNew pPrev Count pHead 50 99 2 15 list pNew->pNext = pPrev->pNext; Thêm vào giữa pPrev->pNext = pNew; Sau khi thêm: Count pHead 99 50 3 15 list pPrev pNew Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 27 Các thao tác trên danh sách liên kết đơn Thêm 1 nút vào danh sách int InsertNode(LINKED_LIST &list, NODE *pPrev, newdata) { // Tạo lập phần tử mới NODE *pNew = new NODE; if (pNew==NULL) return 0; // Lỗi không thể cấp phát phần tử mới pNew->Data = newdata; pNew->pNext = NULL; // Thêm vào đầu danh sách if (pPrev==NULL) { pNew->pNext = list.pHead; list.pHead = pNew; Còn tiếp… } Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 28 14
  15. Các thao tác trên danh sách liên kết đơn Thêm 1 nút vào danh sách else { // Thêm vào giữa danh sách, sau phần tử pPrev pNew->pNext = pPrev->pNext; pPrev->pNext = pNew; } list.Count++; return 1; // Thêm thành công } // end of InsertNode Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 29 Các thao tác trên danh sách liên kết đơn Xóa 1 nút trong danh sách Xóa nút đầu Count pHead Trước khi xóa: 2 15 99 list pCurr pPrev list.pHead = pCurr->pNext; Sau khi xoá: delete pCurr; Count pHead 1 99 list Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 30 15
  16. Các thao tác trên danh sách liên kết đơn Xóa 1 nút trong danh sách Xóa nút giữa Count pHead Trước khi xóa: 3 15 99 50 list pCurr pPrev pPrev->pNext = pCurr->pNext; delete pCurr; Sau khi xoá: Count pHead 2 15 50 list pPrev Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 31 Các thao tác trên danh sách liên kết đơn Xóa 1 nút trong danh sách int DeleteNode(LINKED_LIST &list, NODE *pPrev, NODE *pCurr) { // Xóa nút đầu if (pPrev==NULL) list.pHead = pCurr->pNext; else // Xóa nút giữa pPrev->pNext = pCurr->pNext; delete pCurr; list.Count--; return 1; // Xoá thành công } Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 32 16
  17. Các thao tác trên danh sách liên kết đơn Duyệt danh sách Count pHead 3 99 50 15 list pCurr Count pHead 3 99 50 15 list pCurr Count pHead 3 99 50 15 list pCurr pCurr Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 33 Các thao tác trên danh sách liên kết đơn Duyệt danh sách void TraverseList(const LINKED_LIST &list) { // bắt đầu từ đầu danh sách NODE *pCurr = list.pHead; while (pCurr!=NULL) { “Xử lý nút pCurr” pCurr = pCurr->pNext; // chuyển sang nút kế } } Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 34 17
  18. Các thao tác trên danh sách liên kết đơn Tìm 1 phần tử p Duyệt tuần tự từ đầu danh sách p Nếu gặp nút chứa khóa cần tìm à Stop ! Và thông báo tìm thấy p Nếu đi đến cuối danh sách à Stop ! Và thông báo không tìm th ấy p Chi phí O(n) Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 35 Các thao tác trên danh sách liên kết đơn Tìm 1 phần tử NODE * FindNode(const LINKED_LIST &list, key) { // bắt đầu từ đầu danh sách NODE *pCurr = list.pHead; while (pCurr!=NULL) { if (pCurr->Data==key) return pCurr; // Tìm thấy pCurr = pCurr->pNext; // chuyển sang nút kế } // Không tìm thấy return NULL; } Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 36 18
  19. Giới thiệu các loại danh sách liên kết khác Danh sách liên kết đôi (Double-Linked list) p Mỗi nút có 2 con trỏ liên kết: liên kết đến nút đứng trước p pPrev: p pNext: liên kết đến nút đứng sau xóa 1 nút, không cần phải duyệt danh p Khi sách để tìm phần tử đứng trước p Được sử dụng đối với các dữ liệu mà ta cần truy xuất theo cả 2 chiều: p Menu list p… Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 37 Giới thiệu các loại danh sách liên kết khác Danh sách liên kết đôi (Double-Linked list) Count pHead 3 15 50 90 list Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 38 19
  20. Giới thiệu các loại danh sách liên kết khác Danh sách liên kết đôi (Double-Linked list) p Định nghĩa các cấu trúc dữ liệu ? dựng thao tác “Thêm 1 nút vào danh p Xây sách” ? Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 39 Giới thiệu các loại danh sách liên kết khác Danh sách liên kết vòng (Circular-Linked list) trỏ liên kết pNext của nút cuối cùng trỏ p Con đến nút đầu tiên trong danh sách Count pHead 99 50 3 15 list Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 40 20
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