Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - ThS. Trịnh Quốc Sơn (ĐH Công nghệ Thông tin)

Chia sẻ: May Trời Gio Bien | Ngày: | Loại File: PDF | Số trang:20

Thêm vào BST

Báo xấu

68
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 và giải thuật - Chương 5: Danh sách liên kết kép" cung cấp cho người học các kiến thức: Định nghĩa, cấu trúc dữ liệu, các thao tác trên List kép, tạo một danh sách rỗng,... Mời các bạn cùng tham khảo nội dung chi tiết.

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 và giải thuật: Chương 5 - ThS. Trịnh Quốc Sơn (ĐH Công nghệ Thông tin)

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Cấu trúc dữ liệu 1 vá thuật giải Click To Edit 1 NỘIMaster DANH SÁCH LIÊN KẾT kép DUNGTitle Style
Định Nghĩa Click 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: Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 A B C D 2
CấuClick Trúc Dữ To Liệu Edit Master Title Style • Cấu trúc dữ liệu 1 nút typedef struct tagDnode { Data Info; struct tagDnode *pPre; struct tagDnode *pNext; Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 }DNode; • Cấu trúc List kép Typedef struct tagDList { DNode *pHead; DNode *pTail; }DList; 3
CácClick Thao To TácEdit TrênMaster 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 Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 – 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 4
TạoClick 1 Danh ToSách EditRỗng Master Title Style void CreateDList(DList &l) { l.DHead=NULL; Cấu trúc dữ liệu 1 vá thuật giải l.DTail=NULL; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 } 5
TạoClick 1 Nút To Có Edit Thành Phần Dữ Master LiệuStyle Title =X DNode *CreateDNode(int x) { DNode *tam; tam=new DNode; if(tam==NULL) { printf("khong con du bo nho"); exit(1); Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 } else { tam->Info=x; tam->pNext=NULL; tam->pPre=NULL; return tam; } } 6
Thêm 1 Nút Click ToVào Đầu Edit Danh Sách Master Title Style • Minh họa hình vẽ pHead A B C D Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 X pTail 7
CàiClick Đặt Thêm 1 NútMaster To Edit Vào ĐầuTitle DanhStyle Sách void AddFirst(DList &l, DNode *tam) { if(l.pHead==NULL)//xau rong { l.pHead=tam; l.pTail=l.pHead; Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 } else { tam->pNext=l.pHead; l.pHead->pPre=tam; l.pHead=tam; } } 8
Thêm VàoTo Click Cuối Danh Edit Sách Master Title Style • Minh họa thêm 1 phần tử vào sau danh sách pTail pHead Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 A B C D X 9
CàiClick Đặt Thêm 1 NútMaster To Edit Vào Cuối Danh Title Sách Style void AddEnd(DList &l,DNode *tam) { if(l.pHead==NULL) { l.pHead=tam; l.pTail=l.pHead; Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 } else { tam->pPre=l.pTail; l.pTail->pNext=tam; tam=l.pTail; } } 10
Click Thêm VàoTo Edit Sau Nút Master Q Title Style • Minh họa thêm nút X vào sau nút q pHead q pTail Cấu trúc dữ liệu 1 vá thuật giải A B C D CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 X 11
CàiClick Đặt Thêm 1 NútMaster To Edit Vào SauTitle 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; Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 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 AddFirst(l,tam); 12
Thêm 1 Nút Click ToVào Trước Edit Nút Q Master Title Style • Minh hoạ thêm 1 nút vào trước nút q pHead q pTail Cấu trúc dữ liệu 1 vá thuật giải A B C D CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 X 13
CàiClick Đặt Thêm 1 NútMaster To Edit Vào Trước Nút Title Q Style void AddBeforeQ(DList &l,DNode *tam,DNode *q) { DNode *p; p=q->pPre; if(q!=NULL) { tam->pNext=q; q->pPre=tam; Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 tam->pPre=p; if(p!=NULL) p->pNext=tam; if(q==l.pHead) l.pHead = tam; } else AddEnd(l,tam); } 14
XoáClick Phần To Tử Edit Đầu Danh Sách Master Title Style void DeleteFirst(DList &l) { DNode *p; if(l.pHead!=NULL) { p=l.pHead; Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 l.pHead=l.pHead->pNext; l.pHead->pPre=NULL; delete p; if(l.pHead==NULL) l.pTail=NULL; } } 15
XoáClick 1 Phần ToTử Cuối Edit Danh Sách Master Title Style void DeleteEnd(DList &l ) { DNode *p; if(l.pHead!=NULL) //tuc xau co hon mot phan tu { p=l.pTail; Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 l.pTail=l.pTail->Pre; l.pTail->pNext=NULL; delete p; if(l.pTail==NULL) l.pHead=NULL; } } 16
HủyClick 1 NútTo SauEdit Nút Master Q 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) { Cấu trúc dữ liệu 1 vá thuật giải q->pNext=p->pNext; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 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); } 17
HuỷClick 1 NútTo Đứng Trước Edit Nút Q Master Title Style void DeleteBeforeQ(DList &l,DNode *q) { DNode *p; if(q!=NULL) //tuc ton tai node q { p=q->pPre; if(p!=NULL) { Cấu trúc dữ liệu 1 vá thuật giải q->pPre=p->pPre; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 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); } 18
XoáClick 1 Phần ToTử Có Master Edit Khoá = XTitle Style int DeleteX(DList &l,int x) { DNode *p; DNode *q; q=NULL; p=l.pHead; while(p!=NULL) { Cấu trúc dữ liệu 1 vá thuật giải if(p->Info==x) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 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; 19
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; Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 while(q!=NULL) { if(p->Info>q->Info) HV(p,q); q=q->pNext; } p=p->pNext; }} 20