›

Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 5: Danh sách liên kết kép

pdf 20 trang huongle 5530
Download
Bạn đang xem tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 5: Danh sách liên kết kép", để 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:

  • pdfgiao_trinh_cau_truc_du_lieu_va_giai_thuat_chuong_5_danh_sach.pdf

Nội dung text: Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 5: Danh sách liên kết kép

  1. Click To EditNỘI Master DUNG Title Style DANH SÁCH LIÊN KẾT kép Cấu trúc dữ liệu 1 vá giảivá 1 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 1
  2. ĐịnhClick Nghĩa To Edit Master Title Style • Mỗi phần tử liên kết với phần tử đứng trước và sau nó trong danh sách • Hình vẽ minh họa danh sách liên kết kép: A B C D Cấu trúc dữ liệu 1 vá giảivá 1 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
  3. CấuClick Trúc DữTo LiệuEdit Master Title Style • Cấu trúc dữ liệu 1 nút typedef struct tagDnode { Data Info; struct tagDnode *pPre; struct tagDnode *pNext; }DNode; • Cấu trúc List kép Typedef struct tagDList { DNode *pHead; DNode *pTail; }DList; Cấu trúc dữ liệu 1 vá giảivá 1 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 3
  4. CácClick Thao ToTác Edit Trên Master List Kép Title Style • Khởi tạo danh sách liên kết kép rỗng • Tạo 1 nút có thành phần dữ liệu = x • Chèn 1 phần tử vào danh sách – Chèn vào đầu – Chèn sau phần tử Q – Chèn vào trước phần tử Q – Chèn vào cuối danh sách • Huỷ 1 phần tử trong danh sách – Hủy phần tử đầu danh sách – Hủy phần tử cuối danh sách – Hủy 1 phần tử có khoá bằng x • Tìm 1 phần tử trong danh sách • Sắp xếp danh sách Cấu trúc dữ liệu 1 vá giảivá 1 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
  5. TạoClick 1 Danh To Sách Edit Rỗng Master Title Style void CreateDList(DList &l) { l.DHead=NULL; l.DTail=NULL; } Cấu trúc dữ liệu 1 vá giảivá 1 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
  6. TạoClick 1 Nút ToCó EditThành Master Phần Dữ Title Liệu Style = X DNode *CreateDNode(int x) { DNode *tam; tam=new DNode; if(tam==NULL) { printf("khong con du bo nho"); exit(1); } else { tam->Info=x; tam->pNext=NULL; tam->pPre=NULL; return tam; } Cấu trúc dữ liệu 1 vá giảivá 1 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
  7. ThêmClick 1 Nút To Vào Edit Đầu Master Danh SáchTitle Style • Minh họa hình vẽ pHead A B C D X pTail Cấu trúc dữ liệu 1 vá giảivá 1 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
  8. Cài ClickĐặt Thêm To Edit 1 Nút Master Vào Đầu Title Danh Style Sách void AddFirst(DList &l, DNode *tam) { if(l.pHead==NULL)//xau rong { l.pHead=tam; l.pTail=l.pHead; } else { tam->pNext=l.pHead; l.pHead->pPre=tam; l.pHead=tam; } Cấu trúc dữ liệu 1 vá giảivá 1 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
  9. ThêmClick Vào To Cuối Edit Danh Master Sách Title Style • Minh họa thêm 1 phần tử vào sau danh sách pTail pHead A B C D X Cấu trúc dữ liệu 1 vá giảivá 1 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
  10. Cài ClickĐặt Thêm To Edit 1 Nút Master Vào Cuối Title Danh Style Sách void AddEnd(DList &l,DNode *tam) { if(l.pHead==NULL) { l.pHead=tam; l.pTail=l.pHead; } else { tam->pPre=l.pTail; l.pTail->pNext=tam; tam=l.pTail; } Cấu trúc dữ liệu 1 vá giảivá 1 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
  11. ThêmClick Vào To Sau Edit Nút MasterQ Title Style • Minh họa thêm nút X vào sau nút q pHead q pTail A B C D X Cấu trúc dữ liệu 1 vá giảivá 1 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
  12. Cài ClickĐặt Thêm To Edit 1 Nút Master Vào Sau Title Nút QStyle void AddLastQ(DList &l,DNode *tam, DNode *q) { DNode *p; p=q->pNext; if(q!=NULL)//them vao duoc { tam->pNext=p; tam->pPre=q; q->pNext=tam; if(p!=NULL) p->pPre=tam; if(q==l.pTail) //them vao sau danh sach lien ket. l.pTail=tam; } else Cấu trúc dữ liệu 1 vá giảivá 1 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 AddFirst(l,tam); } 12
  13. ThêmClick 1 Nút To Vào Edit Trước Master Nút QTitle Style • Minh hoạ thêm 1 nút vào trước nút q pHead q pTail A B C D X Cấu trúc dữ liệu 1 vá giảivá 1 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
  14. Cài ClickĐặt Thêm To Edit 1 Nút Master Vào Trước Title Nút Style Q void AddBeforeQ(DList &l,DNode *tam,DNode *q) { DNode *p; p=q->pPre; if(q!=NULL) { tam->pNext=q; q->pPre=tam; tam->pPre=p; if(p!=NULL) p->pNext=tam; if(q==l.pHead) l.pHead = tam; } else AddEnd(l,tam); Cấu trúc dữ liệu 1 vá giảivá 1 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
  15. XoáClick Phần ToTử EditĐầu DanhMaster Sách Title Style void DeleteFirst(DList &l) { DNode *p; if(l.pHead!=NULL) { p=l.pHead; l.pHead=l.pHead->pNext; l.pHead->pPre=NULL; delete p; if(l.pHead==NULL) l.pTail=NULL; } } Cấu trúc dữ liệu 1 vá giảivá 1 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
  16. XoáClick 1 Phần To Tử Edit Cuối Master Danh Sách Title Style void DeleteEnd(DList &l ) { DNode *p; if(l.pHead!=NULL) //tuc xau co hon mot phan tu { p=l.pTail; l.pTail=l.pTail->Pre; l.pTail->pNext=NULL; delete p; if(l.pTail==NULL) l.pHead=NULL; } } Cấu trúc dữ liệu 1 vá giảivá 1 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
  17. HủyClick 1 Nút ToSau Edit Nút MasterQ Title Style void DeleteLastQ(DList &l,DNode *q) { DNode *p;//luu node dung sau node q if(q!=NULL) { p=q->pNext; if(p!=NULL) { q->pNext=p->pNext; if(p==l.pTail)//xoa dung nu't cuoi l.pTail=q; else //Nut xoa khong phai nut cuoi p->pNext->pPre=q; delete p; } } else DeleteFirst(l); } Cấu trúc dữ liệu 1 vá giảivá 1 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
  18. HuỷClick 1 Nút ToĐứng Edit Trước Master Nút QTitle Style void DeleteBeforeQ(DList &l,DNode *q) { DNode *p; if(q!=NULL) //tuc ton tai node q { p=q->pPre; if(p!=NULL) { q->pPre=p->pPre; if(p==l.pHead)//p la Node dau cua danh sach l.pHead=q; else //p khong phai la node dau p->pPre->pNext=q; delete p; } } else DeleteEnd(l); } Cấu trúc dữ liệu 1 vá giảivá 1 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
  19. XoáClick 1 Phần To Tử Edit Có MasterKhoá = X Title Style int DeleteX(DList &l,int x) { DNode *p; DNode *q; q=NULL; p=l.pHead; while(p!=NULL) { if(p->Info==x) break; q=p;//q la Node co truong Info = x p=p->pNext; } if(q==NULL) return 0;//khong tim thay Node nao co truong Info =x if(q!=NULL) DeleteLastQ(l,q); else DeleteFirst(l); return 1; Cấu trúc dữ liệu 1 vá giảivá 1 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
  20. SắpClick Xếp To Edit Master Title Style void DoiChoTrucTiep(DList &l) { DNode *p,*q; p=l.pHead; while(p!=l.pTail) { q=p->pNext; while(q!=NULL) { if(p->Info>q->Info) HV(p,q); q=q->pNext; } p=p->pNext; Cấu trúc dữ liệu 1 vá giảivá 1 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