CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - CHƯƠNG 5: DANH SÁCH LIÊN KẾT KÉP

Chia sẻ: Lê Trinh Vàng | Ngày: | Loại File: PPT | Số trang:20

Thêm vào BST

Báo xấu

136
lượt xem 17
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mỗi phần tử liên kết với phần tử đứng trước và sau nó trong danh sách. 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;

Chủ đề:

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

Lưu

Nội dung Text: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - CHƯƠNG 5: DANH SÁCH LIÊN KẾT KÉP

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ỘMaster DANH SÁCH LIÊN KẾT kép I DUNGTitle Style
Click Định NghĩaTo 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 To Trúc D Edit ữ Liệu 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á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 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 ToSách 1 Danh EditRMaster ỗng 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 Edit Master Có Thành Title Phần Dữ LiệuStyle =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
Click Thêm ToVào 1 Nút Edit ĐầMaster Title u Danh Sách 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ài Click To Edit Đặt Thêm 1 NútMaster 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
Click Thêm VàoTo CuốEdit Master i Danh Sách 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ài Click To Edit Đặt Thêm 1 NútMaster Vào CuốTitle i DanhStyle Sách 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 SauEdit Master Nút 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ài Click To Edit Đặt Thêm 1 NútMaster 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
Click Thêm ToVào 1 Nút Edit Master Trướ c Nút QTitle 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ài Click To Edit Đặt Thêm 1 NútMaster Title Vào Trước NútStyle Q 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 Edit Tử Đ Master ầu Danh Title Sách 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ầTo n TửEdit CuốMaster Title i Danh Sách 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út To SauEdit Master Nút 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út To Edit Đứng Master Trướ c 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) { 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ầTo n TửEdit Master Có Khoá = X Title 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