Bài giảng Cấu trúc dữ liệu và giải thuật - Danh sách liên kết đơn

Chia sẻ: Thanh Hoa | Ngày: | Loại File: PPT | Số trang:38

Thêm vào BST

Báo xấu

125
lượt xem 21
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 - Danh sách liên kết đơn" cung cấp cho người đọ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, minh họa thuật toán thêm vào đầu, minh họa thuật toán thêm vào cuối,... 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 - Danh sách liên kết đơn

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
Tổ Click To Edit Chức Của DSLKMaster Đơ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  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.
Click CTDL của To Edit 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; pNex Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Cấu trúc dữ liệu của DSLK đơn Info t typedef struct tagList { 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
Click Ví dụ To Edit tổ chức DSLKMaster Title đơn trong Style bộ nhớ 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à thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT nodes f elements
CácClick To cơ thao tác Edit bảnMaster Title trên DSLK đơnStyle  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  Hủy một phần tử trong danh sách CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Duyệt danh sách  Sắp xếp danh sách liên kết đơn
Click Khởi To Edit tạo danh sáchMaster 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 l.pHead=NULL; l.pTail=NULL; }
TạoClick TotửEdit 1 phần 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 p ->Info = x; //gán dữa liệu cho nút p->pNext = NULL; return p; }
Click Thêm To Edit 1 phần tử vàoMaster DSLK Title Style  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 Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Thêm vào sau 1 phần tử q trong list
Click Thuật toánTo Edit thêm Master 1 phần Title tử vào đầuStyle 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 + pTail = pHead; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ngược lại + p->pNext = pHead; + pHead = p
Click Hàm thêmTo EdittửMaster 1 phần vào đầuTitle 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 else { p->pNext = l.pHead; l.pHead = p; } }
Click Minh họa To thuậtEdit toánMaster Title thêm vào đầu Style pHead 4f 2f 3f 3 3f 4 4f 8 … 9f Cấu trúc dữ liệu và thuật giải 10 2f N CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 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 Ngược lại + pTail->pNext=p; + pTail=p
Click Hàm thêmTo EdittửMaster 1 phần Title vào cuối Style DSLKD 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 } else { l.pTail->Next = p; l.pTail = p; } }
Click Minh họa To thuậtEdit toánMaster Title thêm vào cuốiStyle pTail 3f 4f 5f 4 4f 8 5f 5 N 9f pTail=P Cấu trúc dữ liệu và thuật giải pTail->pNext 9f CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 6 N P
Click Thuật Tophần toán Edit tử Master p vào Title Styletử q sau phần  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 B2: + q->pNext = p + nếu q = pTail thì pTail=p
CàiClick To toán đặt thuật 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 if(l.pTail==q) l.Tail=q; } else AddHead(l,q);// thêm q vào đầu list }
Minh Click To họa Edit thuật Title Master toán Style 3f 4f q 5f 4 4f 8 5f 9f 5 .. 9f q->pNext=P 7 N 5f Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT P->pNext=q->pNext P
HủyClick phần To Edit DSLK tử trong Master đơnTitle 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  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.
Click Thuật toánTo Edit hủy Master phần tử trongTitle 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 + pHead = pHead->pNext + delete (p)  B3: Nếu pHead==NULL thì pTail=NULL
CàiClick To toán đặt thuật 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 delete p; if(l.pHead==NULL) l.pTail=NULL; return 1; } return 0; }