›
›

Cấu trúc dữ liệu và giải thuật - Chương 4: Danh sách liên kết đơn (List)

pdf 78 trang phuongnguyen 6510
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cấu trúc dữ liệu và giải thuật - Chương 4: Danh sách liên kết đơn (List)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfcau_truc_du_lieu_va_giai_thuat_chuong_4_danh_sach_lien_ket_d.pdf

Nội dung text: Cấu trúc dữ liệu và giải thuật - Chương 4: Danh sách liên kết đơn (List)

  1. Click To EditNỘI Master DUNG Title Style DANH SÁCH LIÊN KẾT ĐƠN (LIST) Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  2. Tổ ChứcClick CủaTo EditDSLK Master Đơn Title Style x2 x0 x1 x3  Mỗi phần tử liên kết với phần tử đứng liền sau trong danh sách  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 Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU tử cuối danh sách.
  3. ClickCTDL To Edit của Master DSLK Title đơn Style  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 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 Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  4. Ví dụClick tổ chức To EditDSLK Master đơn trong Title bộ nhớStyle pHead pTail 3f 4f 5f 4 4f 7 5f 6 NULL Trong ví dụ trên thành phần dữ liệu là 1 số nguyên Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  5. CácClick thao tácTo cơEdit bản Master trên DSLK Title đơn 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  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 Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  6. KhởiClick tạo danh To Edit sách Master 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) { l.pHead=NULL; l.pTail=NULL; } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  7. TạoClick 1 phần To tử 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); p ->Info = x; //gán dữa liệu cho nút p->pNext = NULL; return p; } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  8. ThêmClick 1 phần To Edittử vào Master 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 . Thêm vào cuối List . Thêm vào sau 1 phần tử q trong list Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  9. ThuậtClick toán To thêm Edit 1 phầnMaster tử vào Title đầu Style 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; + pTail = pHead; Ngược lại + p->pNext = pHead; + pHead = p Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  10. HàmClick thêm To 1 phần Edit tửMaster vào đầu Title List Style void AddHead(LIST &l, Node* p) { if (l.pHead==NULL) { l.pHead = p; l.pTail = l.pHead; } else { p->pNext = l.pHead; l.pHead = p; } } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  11. MinhClick họa thuậtTo Edit toán Master thêm vào Title đầu Style pHead 2f 3f 4f 3 3f 4 4f 8 9f 10 2fN pHead=P P->pNext=pHead P Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  12. ThuậtClick Totoán Edit thêm Master vào Titlecuối StyleDSLK  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; Ngược lại + pTail->pNext=p; + pTail=p Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  13. HàmClick thêm To 1 phần Edit tửMaster vào cuối Title DSLKD Style void AddTail(LIST &l, Node *p) { if (l.pHead==NULL) { l.pHead = p; l.pTail = l.pHead; } else { l.pTail->Next = p; l.pTail = p; } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU }
  14. MinhClick họa thuậtTo Edit toán Master thêm vào Title cuối Style pTail 3f 4f 5f 4 4f 8 5f 5 9fN pTail=P pTail->pNext 9f 6 N P Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  15. ThuậtClick toán To thêm Edit phần Master tử q vào Title sau phầnStyle tử 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 B2: + q->pNext = p + nếu q = pTail thì pTail=p Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  16. Cài Clickđặt thuật To toánEdit Master Title Style void InsertAfterQ(List &l, Node *p, Node *q) { if(q!=NULL) { p->pNext=Q->Next; q->pNext=p; if(l.pTail==q) l.Tail=q; } else AddHead(l,q);// thêm q vào đầu list } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  17. Click MinhTo Edit họa Master thuật Titletoán Style 3f 4f q 5f 4 4f 8 5f9f 5 9f q->pNext=P 7 N5f P->pNext=q->pNext P Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  18. HủyClick phần Totử trongEdit DSLKMaster đơn Title 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 . 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. Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  19. ThuậtClick toán To hủy Edit phần Master tử trong Title DSLK Style  Bắt đầu: . Nếu (pHead!=NULL) thì . B1: p=pHead . B2: + pHead = pHead->pNext + delete (p) . B3: Nếu pHead==NULL thì pTail=NULL Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  20. Cài Clickđặt thuật To toánEdit 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; delete p; if(l.pHead==NULL) l.pTail=NULL; return 1; } return 0; Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU }
  21. MinhClick hoạ thuậtTo Edit toán Master Title Style pHead=pHead->pNext pHead 2f 3f 4f 1f 7 2f 6 3f 3 4f 8 P=pHead P Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  22. HủyClick phần Totử sauEdit phần Master tử q trong Title List Style  Bắt đầu Nếu (q!=NULL) thì //q tồn tại trong List . B1: p=q->pNext;// p là phần tử cần hủy . B2: Nếu (p!=NULL) thì // q không phải là phần tử cuối + q->pNext=p->pNext;// tách p ra khỏi xâu + nếu (p== pTail) // nút cần hủy là nút cuối pTail=q; + delete p;// hủy p Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  23. Cài Clickđặt thuật To toánEdit Master Title Style int RemoveAfterQ(List &l,Node *q, int &x) { Node *p; if(q!=NULL) { p=q->pNext; //p là nút cần xoá if(p!=NULL) // q không phài là nút cuối { if(p==l.pTail) //nút cần xoá là nút cuối cùng l.pTail=q;// cập nhật lạ pTail q->pNext=p->pNext; x=p->Info; delete p; } return 1; } else Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU return 0; }
  24. MinhClick họa thuậtTo Edit toán Master Title Style p-=q->pNext q p 2f pHead 1f 3f 4f 7 2f 6 3f4f 3 4f 8 q->pNext=p->pNext Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  25. ThuậtClick toán To hủy Edit phần Master tử có khoá Title x Style Bước 1: Tìm phần tử p có khoá bằng x, và q đứng trước p Bước 2: Nếu (p!=NULL) thì //tìm thấy phần tử có khoá bằng x Hủy p ra khỏi List bằng cách hủy phần tử đứng sau q Ngược lại Báo không tìm thấy phần tử có khoá Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  26. Cài Clickđặt thuật To toánEdit Master Title Style int RemoveX(List &l, int x) { Node *p,*q = NULL; p=l.Head; while((p!=NULL)&&(p->Info!=x)) //tìm { q=p; p=p->Next; } if(p==NULL) //không tìm thấy phần tử có khoá bằng x return 0; if(q!=NULL)//tìm thấy phần tử có khoá bằng x DeleteAfterQ(l,q,x); else //phần tử cần xoá nằm đầu List RemoveHead(l,x); return 1; Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU }
  27. TìmClick 1 phần To tử Edit trong Master DSLK đơn Title Style  Tìm tuần tự (hàm trả về), các bước của thuật toán tìm nút có Info bằng x trong list đơn Bước 1: p=pHead;// địa chỉ của phần tử đầu trong list đơn Bước 2: Trong khi p!=NULL và p->Info!=x p=p->pNext;// xét phần tử kế Bước 3: + Nếu p!=NULL thì p lưu địa chỉ của nút có Info = x + Ngược lại : Không có phần tử cần tìm Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  28. HàmClick tìm 1 To phần Edit tử Mastertrong DSLK Title đơn Style  Hàm tìm phần tử có Info = x, hàm trả về địa chỉ của nút có Info = x, ngược lại hàm trả về NULL Node *Search(LIST l, Data x) { Node *p; p = l.pHead; while((p!= NULL)&&(p->Info != x)) p = p->pNext; return p; } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  29. MinhClick họa thuậtTo Edit toán Master tìm phần Title tử trong Style DSLK pHead 1f 2f 3f 4f 5f 34 3 4 8 56 P X = 8 Tìm thấy, hàm trả về địa chỉ của nút tìm thấy là 4f Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  30. DuyệtClick danh To sách Edit Master Title Style Duyệt danh sách là thao tác thường được thực hiện khi có nhu cầu cần xử lý các phần tử trong danh sách như: . Đếm các phần tử trong danh sách . Tìm tất cả các phần tử trong danh sách thảo điều kiện . Hủy toàn bộ danh sách Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  31. ThuậtClick toán To duyệt Edit danh Master sách Title Style • Bước 1: p = pHead;// p lưu địa chỉ của phần tử đầu trong List • Bước 2: Trong khi (danh sách chưa hết) thực hiện + xử lý phần tử p + p=p->pNext;// qua phần tử kế Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  32. Cài Clickđặt in Tocác Editphần Master tử trong TitleList Style void PrintList(List l) { Node *p; p=l.pHead; while(p!=NULL) { printf(“%d ”, p->Info); p=p->pNext; } } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  33. HủyClick danh Tosách Edit liên Masterkết đơn Title Style . Bước 1: Trong khi (danh sách chưa hết) thực hiện • B11: p = pHead; pHead = pHead->pNext;// cập nhật pHead • B12: Hủy p . Bước 2: pTail = NULL;// bảo toàn tính nhất quán khi xâu rỗng Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  34. Cài Clickđặt thuật To toánEdit Master Title Style void RemoveList(List &l) { Node *p; while(l.pHead!=NULL)//còn phần tử trong List { p = l.pHead; l.pHead = p->pNext; delete p; } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  35. MinhClick họa thuậtTo Edit toán Master Title Style pHead pTail 2f 1f 3f 4f 5f 7 2f 6 3f 3 4f 8 5f 9 N p Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  36. SắpClick xếp danh To Edit sách Master Title Style  Có hai cách tiếp cận  Cách 1: Thay đổi thành phần Info pHead pTail 3f 4f 5f 4 4f 7 5f 6 N pHead pTail 3f 4f 5f 4 4f 6 5f 7 N Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  37. SắpClick xếp danh To Edit sách Master Title Style Cách 2: Thay đổi thành phần pNext (thay đổi trình tự móc nối của các phần tử sao cho tạo lập nên được thứ tự mong muốn) pHead pTail 3f 4f 5f 4 4f 7 5f 6 N pHead pTail 3f 4f 5f 4 5f 7 N 6 4f Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  38. Ưu,Click nhược To điểm Edit của Master 2 cách Titletiếp cận Style  Thay đổi thành phần Info (dữ liệu) . Ưu: Cài đặt đơn giản, tương tự như sắp xếp mảng . Nhược: • Đòi hỏi thêm vùng nhớ khi hoán vị nội dung của 2 phần tử -> chỉ phù hợp với những xâu có kích thước Info nhỏ • Khi kích thước Info (dữ liệu) lớn chi phí cho việc hoán vị thành phần Info lớn Làm cho thao tác sắp xếp chậm  Thay đổi thành phần pNext . Ưu: • Kích thước của trường này không thay đổi, do đó không phụ thuộc vào kích thước bản chất dữ liệu lưu tại mỗi nút. Thao tác sắp xếp nhanh Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU . Nhược: Cài đặt phức tạp
  39. DùngClick thuật Totoán Edit SX SelectionSort Master Title để SX Style List void SelectionSort(LIST &l) while(q!=NULL) { { Node *p,*q,*min; if(q->Info Info) p=l.pHead; min=q; while(p!=l.pTail) q=q->Next; { } min=p; HV(min->Info,p->Info); q=p->Next; p=p->Next; } } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  40. CácClick thuật Totoán Edit sắp Masterxếp hiệu Titlequả trên Style List  Các thuật toán sắp xếp xâu (List) bằng các thay đổi thành phần pNext (thành phần liên kết) có hiệu quả cao như: . Thuật toán sắp xếp Quick Sort . Thuật toán sắp xếp Merge Sort . Thuật toán sắp xếp Radix Sort Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  41. ThuậtClick toán To sắp Edit xếp Master Quick Sort Title Style • Bước 1: Chọn X là phần tử đầu xâu L làm phần tử cầm canh Loại X ra khỏi L • Bước 2: Tách xâu L ra làm 2 xâu L1(gồm các phần tử nhỏ hơn hoặc bằng x) và L2 (gồm các phần tử lớn hơn X) • Bước 3: Nếu (L1 !=NULL) thì QuickSort(L1) • Bước 4: Nếu (L2!=NULL) thì QuickSort(L2) • Bước 5: Nối L1, X, L2 lại theo thứ tự ta có xâu L đã được sắp xếp Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  42. MinhClick họa thuậtTo Edit toán Master Title Style Cho danh sách liên kết gồm các phần tử sau: pTail pHead 4 6 5 1 8 2 X = 4 pTail pHead L1 ( X) 1 2 pTail pHead L2 (>X) 6 5 8 Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  43. MinhClick họa thuậtTo Edit toán Master (tt) Title Style Sắp xếp L1 Sắp xếp L2 . Chọn x=6 cầm canh, và tách L2 thành L21 và L22 6 X2 = pTail pHead L21 ( X) 2 pTail pHead L22 (>X) 8 Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  44. MinhClick họa thuậtTo Edit toán Master (tt) Title Style  Nối L21, X2, L22 thành L2 pTail pHead L2 6 6 8 Nối L1, X, L2 thành L pTail pHead 1 2 4 5 6 8 Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  45. Cài Clickđặt thuật To toánEdit Master Title Style void QuickSort(List &l) { Node *p,*X;//X lưu địa chỉ của phần tử cầm canh List l1,l2; if(l.pHead==l.pTail) return;//đã có thứ tự CreateList(l1); CreateList(l2); X=l.pHead; l.pHead=X->pNext; while(l.pHead!=NULL)//tách L = L1 va L2 { p=l.pHead; l.pHead=p->pNext; p->pNext=NULL; if(p->Info Info) AddHead(l1,p); else AddHead(l2,p); Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU }
  46. Cài Clickđặt thuật To toánEdit (tt) Master Title Style QuickSort(l1);//Gọi đệ quy sắp xếp L1 QuickSort(l2);//Gọi đệ quy sắp xếp L2 if(l1.pHead!=NULL)//nối l1, l2 va X vao l { l.pHead=l1.pHead; l1.pTail->pNext=X;//nối X vào } else l.pHead=X; X->pNext=l2.pHead; if(l2.pHead!=NULL) //l2 có trên một phần tử l.pTail=l2.pTail; else //l2 không có phần tử nào l.pTail=X; Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU }
  47. ThuậtClick toán To sắp Edit xếp Master Merge Sort Title Style • Bước 1: Phân phối luân phiên từng đường chạy của xâu L vào 2 xâu con L1 và L2. • Bước 2: Nếu L1 != NULL thì Merge Sort (L1). • Bước 3: Nếu L2 != NULL thì Merge Sort (L2). • Bước 4: Trộn L1 và L2 đã sắp xếp lại ta có xâu L đã được sắp xếp. • Không tốn thêm không gian lưu trữ cho các dãy phụ Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  48. MinhClick họa Tothuật Edit toán Master Title Style Cho danh sách liên kết gồm các phần tử sau: pTail pHead 4 6 5 1 8 2 Phân phối các đường chạy của L1 vào L1, L2 pTail pHead L1 4 6 1 8 pTail pHead L2 5 2 Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  49. MinhClick họa thuậtTo Edit toán Master (tt) Title Style  Sắp xếp L1 . Phân phối các đường chạy L1 vào L11, L12 pTail pHead L11 4 6 pTail pHead L12 1 8 . Trộn L11 và L12 vào L1 pTail pHead L1 1 4 6 8 Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  50. MinhClick họa thuậtTo Edit toán(tt) Master Title Style  Sắp xếp L2 . Phân phối các đường chạy của L2 vào L21, L22 pTail pHead L21 5 pTail pHead L22 2 Trộn L21, L22 thành L2 pTail pHead L2 2 5 Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  51. MinhClick họa thuậtTo Edit toán Master (tt) Title Style  Trộn L1, L2 thành L pTail pHead 1 2 4 5 6 8 Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  52. Cài Clickđặt hàm To main() Edit Master Title Style  Yêu cầu: Viết chương trình thành lập 1 xâu đơn, trong đó thành phần dữ liệu của mỗi nút là 1 số nguyên dương. 1. Liệt kê tất thành phần dữ liệu của tất cả các nút trong xâu 2. Tìm 1 phần tử có khoá bằng x trong xâu. 3. Xoá 1 phần tử đầu xâu 4. Xoá 1 phần tử có khoá bằng x trong xâu 5. Sắp xếp xâu tăng dần theo thành phần dữ liệu (Info) 6. Chèn 1 phần tử vào xâu, sao cho sau khi chèn xâu vẫn tăng dần theo trường dữ liệu Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU vv
  53. CàiClick đặt hàm To main()Edit Master (tt) Title Style void main() { LIST l1; Node *p; int x; CreateList(l1); do{ printf(“nhap x=”); scanf(“%d”,&x); if(x>0) { p = CreateNode(x); AddHead(l1,x); } }while(x>0); printf(“Danh sách mới thành lập là\n”); PrintList(l1); printf(“nhập x cần tìm x=”); scanf(“%d”,&x); Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  54. Cài Clickđặt hàm To main() Edit Master(tt) Title Style p = Search(l1,x); if(p==NULL) printf(“không tìm thấy”); else printf(“tìm thấy”); RemoveHead(l1,x); printf(“danh sách sau khi xóa\n”); PrintList(l1); printf(“nhập khoá cần xoá\n”); scanf(“%d”,&x); RemoveX(l1,x); Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  55. Cài Clickđặt hàm To main() Edit Master(tt) Title Style printf(“danh sách sau khi xoá”); PrintfList(l1); SelectionSort(l1); printf(“Danh sách sau khi sắp xếp”); PrintfList(l1); RemoveList(l1); } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  56. Vài Clickứng dụng To Editdanh Mastersách liên Title kết đơn Style • Dùng xâu đơn để lưu trữ danh sách các học viên trong lớp học • Dùng xâu đơn để quản lý danh sách nhân viên trong một công ty, trong cơ quan • Dùng xâu đơn để quản lý danh sách các cuốn sách trong thư viện • Dùng xâu đơn để quản lý các băng đĩa trong tiệm cho thuê đĩa. • vv Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  57. DùngClick xâu Tođơn Edit để quản Master lý lớp Title học Style Yêu cầu: Thông tin của một sinh viên gồm, mã số sinh viên, tên sinh viên, điểm trung bình. 1. Hãy khai báo cấu trúc dữ liệu dạng danh sách liên kết để lưu danh sách sinh viên nói trên. 2. Nhập danh sách các sinh viên, và thêm từng sinh viên vào đầu danh sách (việc nhập kết thúc khi tên của một sinh viên bằng rỗng) 3. Tìm một sinh viên có trong lớp học hay không 4. Xoá một sinh viên có mã số bằng x (x nhập từ bàn phím) 5. Liệt kê thông tin của các sinh viên có điểm trung bình lớn hơn hay bằng 5. Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  58. DùngClick xâu Tođơn Edit để quản Master lý lớp Title học Style 6. Xếp loại và in ra thông tin của từng sinh viên, biết rằng cách xếp loại như sau: ĐTB =50 và ĐTB =6.5 và ĐTB =7.0 và ĐTB =8.0 và ĐTB =9.0 : Loại xuất sắc 7. Sắp xếp và in ra danh sách sinh viên tăng theo điểm trung bình. 8. Chèn một sinh viên vào danh sách sinh viên tăng theo điểm trung bình nói trên, sao cho sau khi chèn danh sách sinh viên vẫn tăng theo điểm trung bình vv Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  59. CấuClick trúc dữ To liệu Edit cho Master bài toán Title Style • Cấu trúc dữ liệu của một sinh viên typedef struct { char tên[40]; char Maso[40]; float ĐTB; }SV • Cấu trúc dữ liệu của 1 nút trong xâu typedef struct tagNode { SV Info; struct tagNode *pNext; }Node; Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  60. CácClick cấu trúc To đặcEdit biệt Master của danh Title sách Style đơn  Stack (ngăn xếp): Là 1 vật chứa các đối tượng làm việc theo cơ chế LIFO (Last In First Out), tức việc thêm 1 đối tượng vào Stack hoặc lấy 1 đối tượng ra khỏi Stack được thực hiện theo cơ chế “vào sau ra trước”  Queue (hàng đợi): Là 1 vật chứa các đối tượng làm việc theo cơ chế FIFO (First In First Out), tức việc thêm 1 đối tượng vào hàng đợi hay lấy 1 đối tượng ra khỏi hàng đợi thực hiện theo cơ chế “vào trước ra trước”. Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  61. ỨngClick dụng ToStack Edit và Master Queue Title Style Stack: . Trình biên dịch . Khử đệ qui đuôi . Lưu vết các quá trình quay lui, vét cạn Queue: . Tổ chức lưu vết các quá trình tìm kiếm theo chiều rộng, và quay lui vét cạn, . Tổ chức quản lý và phân phối tiến trình trong các hệ điều hành, . Tổ chức bộ đệm bàn phím, Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  62. CácClick thao tácTo trênEdit Stack Master Title Style • Push(o): Thêm đối tượng o vào Stack • Pop(): Lấy đối tượng từ Stack • isEmpty(): Kiểm tra Stack có rỗng hay không • Top(): Trả về giá trị của phần tử nằm đầu Stack mà không hủy nó khỏi Stack. Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  63. Cài Clickđặt Stack To Edit Master Title Style  Dùng mảng 1 chiều Data S [N]; int t;  Dùng danh sách liên kết đơn S 4 6 5 1 8 2 List S Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU  Thêm và hủy cùng phía
  64. Cài ClickStack Tobằng Edit mảng Master 1 chiều Title Style Cấu trúc dữ liệu của Stack typedef struct tagStack { int a[max]; int t; }Stack; Khởi tạo Stack: void CreateStack(Stack &s) { s.t=-1; } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  65. KiểmClick tra tính To rỗngEdit vàMaster đầy của Title Stack Style int IsEmpty(Stack s)//Stack có rỗng hay không { if(s.t==-1) return 1; else return 0; } int IsFull(Stack s) //Kiểm tra Stack có đầy hay không { if(s.t>=max) return 1; else return 0; Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU }
  66. ThêmClick 1 phần To Edittử vào Master Stack Title Style int Push(Stack &s, int x) { if(IsFull(s)==0) { s.t++; s.a[s.t]=x; return 1; } else return 0; } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  67. LấyClick 1 phần To tử Edit từ Stack Master Title Style int Pop(Stack &s, int &x) { if(IsEmpty(s)==0) { x=s.a[s.t]; s.t ; return 1; } else return 0; } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  68. Cài ClickStack Tobằng Edit danh Master sách liên Title kết Style • Kiểm tra tính rỗng của Stack int IsEmpty(List &s) { if(s.pHead==NULL)//Stack rong return 1; else return 0; } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  69. ThêmClick 1 phần To Edittử vào Master Stack Title Style void Push(List &s,Node *Tam) { if(s.pHead==NULL) { s.pHead=Tam; s.pTail=Tam; } else { Tam->pNext=s.pHead; s.pHead=Tam; } } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  70. LấyClick 1 phần To tử Edit từ Stack Master Title Style int Pop(List &s,int &trave) { Node *p; if(IsEmpty(s)!=1) { if(s.pHead!=NULL) { p=s.pHead; trave=p->Info; s.pHead=s.pHead->Next; if(s.pHead==NULL) s.Tail=NULL; return 1; delete p; } } return 0; } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  71. CácClick thao tácTo trênEdit Queue Master Title Style • EnQueue(O): Thêm đối tượng O vào cuối hàng đợi. • DeQueue(): Lấy đối tượng ở đầu hàng đợi • isEmpty(): Kiểm tra xem hàng đợi có rỗng hay không? • Front(): Trả về giá trị của phần tử nằm đầu hàng đợi mà không hủy nó. Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  72. CàiClick đặt Queue To Edit Master Title Style • Dùng mảng 1 chiều Data S [N]; int f,r; • Dùng danh sách liên kết đơn 4 6 5 1 8 2 List Q Head Tail Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU * Thêm và hủy Khác phía
  73. Cài Clickđặt Queue To Edit bằng Master mảng 1 Titlechiều Style • Cấu trúc dữ liệu: typedef struct tagQueue { int a[100]; int Front; //chỉ số của phần tử đầu trong Queue int Rear; //chỉ số của phầ tử cuối trong Queue }Queue; • Khởi tạo Queue rỗng void CreateQueue(Queue &q) { q.Front=-1; q.Rear=-1; } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  74. LấyClick 1 phần To tử Edit từ Queue Master Title Style int DeQueue(Queue &q,int &x) { if(q.Front!=-1) //queue khong rong { x=q.a[q.Front]; q.Front++; if(q.Front>q.Rear)//truong hop co mot phan tu { q.Front=-1; q.Rear=-1; } return 1; } else //queue trong { printf("Queue rong"); return 0; } } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  75. ThêmClick 1 phần To Edittử vào Master Queue Title Style void EnQueue(Queue &q,int x) { int i; int f,r; if(q.Rear-q.Front+1==N)//queue bi day khong the them vao duoc nua printf("queue day roi khong the them vao duoc nua"); else { if(q.Front==-1) { q.Front=0; q.Rear=-1; } if(q.Rear==N-1)//Queue đầy ảo { f=q.Front; r=q.Rear; for(i=f;i<=r;i++) q.a[i-f]=q.a[i]; q.Front=0; q.Rear=r-f; } q.Rear++; q.a[q.Rear]=x; } } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  76. Cài Clickđặt Queue To Edit bằng Master List Title Style • Kiểm tra Queue có rỗng? int IsEmpty(List &Q) { if(Q.pHead==NULL)//Queue rỗng return 1; else return 0; } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  77. ThêmClick 1 phần To Edittử vào Master Queue Title Style void EnQueue(List &Q, Node *Tam) { if(Q.pHead==NULL) { Q.pHead=Tam; Q.pTail=Tam; } else { Q.pTail->Next=tam; Q.pTail=tam; } } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU
  78. LấyClick 1 phần To tử Edit từ Queue Master Title Style int DeQueue(List &Q,int &trave) { Node *p; if(IsEmpty(Q)!=1) { if(Q.pHead!=NULL) { p=Q.pHead; trave=p->Info; Q.pHead=Q.pHead->Next; if(Q.pHead==NULL) Q.pTail=NULL; return 1; delete p; } } return 0; } Cấu trúc dữ liệu và giảivà thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU