Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - ThS. Trịnh Quốc Sơn (ĐH Công nghệ Thông tin)
lượt xem 11
download
Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 4: Danh sách liên kết đơn (List)" cung cấp cho người học các kiến thức: Tổ chức của DSLK đơn, các thao tác cơ bản trên DSLK đơn, khởi tạo danh sách liên kết, hàm thêm 1 phần tử vào đầu List, thuật toán thêm vào cuối DSLK,... Mời các bạn cùng tham khảo nội dung chi tiết.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - ThS. Trịnh Quốc Sơn (ĐH Công nghệ Thông tin)
- NỘIMaster Click To Edit DUNGTitle Style DANH SÁCH LIÊN KẾT ĐƠN (LIST) Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
- Tổ Chức ClickCủa DSLKMaster To Edit Đơn Title Style x2 x0 x3 x1 Mỗi phần tử liên kết với phần tử đứng liền sau trong danh sách Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Mỗi phần tử trong danh sách liên kết đơn là một cấu trúc có hai thành phần Thành phần dữ liệu: Lưu trữ thông tin về bản thân phần tử Thành phần liên kết: Lưu địa chỉ phần tử đứng sau trong danh sách hoặc bằng NULL nếu là phần tử cuối danh sách.
- ClickCTDL To Editcủa DSLKTitle Master đơnStyle Cấu trúc dữ liệu của 1 nút trong List đơn typedef struct tagNode { Data Info; // Lưu thông tin bản thân struct tagNode *pNext; //Lưu địa chỉ của Node đứng sau }Node; Cấu trúc dữ liệu của DSLK đơn pNext Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 typedef struct tagList Info { Node *pHead;//Lưu địa chỉ Node đầu tiên trong List Node *pTail; //Lưu địa chỉ của Node cuối cùng trong List }LIST; // kiểu danh sách liên kết đơn
- Ví dụ tổ chức Click DSLKMaster To Edit đơn trong bộ nhớ Title Style pHead pTail 3f 4f 5f 4 4f 7 5f 6 NULL Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Trong ví dụ trên thành phần dữ liệu là 1 số nguyên
- CácClick thao tác To cơ bảnMaster Edit trên DSLK đơn Title Style Tạo 1 danh sách liên kết đơn rỗng Tạo 1 nút có trường Infor bằng x Tìm một phần tử có Info bằng x Thêm một phần tử có khóa x vào danh sách Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Hủy một phần tử trong danh sách Duyệt danh sách Sắp xếp danh sách liên kết đơn
- Khởi tạo danh Click sáchMaster To Edit liên kết Title Style Địa chỉ của nút đầu tiên, địa chỉ của nút cuối cùng đều không có void CreateList(List &l) { Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 l.pHead=NULL; l.pTail=NULL; }
- TạoClick 1 phần TotửEdit mới Master Title Style Hàm trả về địa chỉ phần tử mới tạo Node* CreateNode(Data x) { Node *p; p = new Node;//Cấp phát vùng nhớ cho phần tử if ( p==NULL) exit(1); Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 p ->Info = x; //gán dữa liệu cho nút p->pNext = NULL; return p; }
- Thêm 1 phần Click tử vàoMaster To Edit DSLK Title Style Nguyên tắc thêm: Khi thêm 1 phần tử vào List thì có làm cho pHead, pTail thay đổi? Các vị trí cần thêm 1 phần tử vào List: Thêm vào đầu List đơn Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Thêm vào cuối List Thêm vào sau 1 phần tử q trong list
- Thuật toánTo Click thêm 1 phần Edit tử vào Master đầuStyle Title DSLK Thêm nút p vào đầu danh sách liên kết đơn Bắt đầu: Nếu List rỗng thì + pHead = p; Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 + pTail = pHead; Ngược lại + p->pNext = pHead; + pHead = p
- Hàm thêmTo Click 1 phần Edittử vào đầuTitle Master List Style void AddHead(LIST &l, Node* p) { if (l.pHead==NULL) { l.pHead = p; l.pTail = l.pHead; Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 } else { p->pNext = l.pHead; l.pHead = p; } }
- Minh họa thuật Click toánMaster To Edit thêm vào đầu Style Title pHead 2f 3f 4f 3 3f 4 4f 8… 9f 10 2f Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 N pHead=P P->pNext=pHead P
- Thuật toán Click To thêm Edit vào Title Master cuối Style DSLK Ta cần thêm nút p vào cuối list đơn Bắt đầu: Nếu List rỗng thì + pHead = p; + pTail = pHead; Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Ngược lại + pTail->pNext=p; + pTail=p
- Hàm thêmTo Click 1 phần Edittử vào cuối Master DSLKD Title Style void AddTail(LIST &l, Node *p) { if (l.pHead==NULL) { l.pHead = p; l.pTail = l.pHead; Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 } else { l.pTail->Next = p; l.pTail = p; } }
- Minh họa thuật Click toánMaster To Edit thêm vào cuốiStyle Title pTail 3f 4f 5f 4 4f 8 5f 5N 9f pTail=P Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 pTail->pNext 9f 6N P
- Thuật Clicktoán Tothêm Editphần tử q vào Master sau phần Title Styletử q Ta cần thêm nút p vào sau nút q trong list đơn Bắt đầu: Nếu (q!=NULL) thì B1: p->pNext = q->pNext Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 B2: + q->pNext = p + nếu q = pTail thì pTail=p
- CàiClick đặt thuật To toán Edit Master Title Style void InsertAfterQ(List &l, Node *p, Node *q) { if(q!=NULL) { p->pNext=Q->Next; q->pNext=p; Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 if(l.pTail==q) l.Tail=q; } else AddHead(l,q);// thêm q vào đầu list }
- Click Minh họa To Edit thuật Title Master toánStyle 3f 4f q 5f 4 4f 8 5f 9f 5 .. 9f 7 N q->pNext=P Cấu trúc dữ liệu và thuật giải 5f CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 P->pNext=q->pNext P
- HủyClick phần To tử trong Edit DSLK đơnTitle Master Style Nguyên tắc: Phải cô lập phần tử cần hủy trước hủy. Các vị trị cần hủy Hủy phần tử đứng đầu List Hủy phần tử có khoá bằng x Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Huỷ phần tử đứng sau q trong danh sách liên kết đơn Ở phần trên, các phần tử trong DSLK đơn được cấp phát vùng nhớ động bằng hàm new, thì sẽ được giải phóng vùng nhớ bằng hàm delete.
- Thuật toánTo Click hủy phần Edit tử trongTitle Master DSLK Style Bắt đầu: Nếu (pHead!=NULL) thì B1: p=pHead B2: Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 + pHead = pHead->pNext + delete (p) B3: Nếu pHead==NULL thì pTail=NULL
- CàiClick đặt thuật To toán Edit Master Title Style Hủy được hàm trả về 1, ngược lại hàm trả về 0 int RemoveHead(List &l, int &x) { Node *p; if(l.pHead!=NULL) { p=l.pHead; x=p->Info; //lưu Data của nút cần hủy l.pHead=l.pHead->pNext; Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 delete p; if(l.pHead==NULL) l.pTail=NULL; return 1; } return 0; }
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p | 175 | 17
-
Bài giảng Cấu trúc dữ liệu 1: Chương 1 - Lương Trần Hy Hiến
7 p | 162 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp
28 p | 77 | 9
-
Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Cấu trúc dữ liệu tuyến tính
92 p | 116 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên
25 p | 81 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 17: Cấu trúc dữ liệu dạng cây
21 p | 77 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu
193 p | 58 | 7
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)
62 p | 94 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )
62 p | 159 | 6
-
Bài giảng Cấu trúc dữ liệu - Chương 3: Cấu trúc cây
65 p | 58 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AA - Bùi Tiến Lên
30 p | 35 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p | 106 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây - Bùi Tiến Lên
68 p | 40 | 4
-
Bài giảng Cấu trúc dữ liệu: Chương 1 - ThS. Thiều Quang Trung (2018)
44 p | 43 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AVL - Bùi Tiến Lên
38 p | 47 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Ngô Quang Thạch
24 p | 58 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung
41 p | 68 | 3
-
Bài giảng Cấu trúc dữ liệu giải thuật: Cấu trúc dữ liệu
17 p | 50 | 2
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