Danh sách liên kết đơn (List)

Chia sẻ: Nguyen Thi Quynh Mai | Ngày: | Loại File: PPT | Số trang:83

Thêm vào BST

Báo xấu

614
lượt xem 155
download

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

CácC thliacok táTco c Eơ dbiảt nM traêns tDeSr LTKit đleơ 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 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

Chủ đề:

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

Lưu

Nội dung Text: Danh sách liên kết đơn (List)

NỘI DUNG Click To Edit Master Title 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 1
Tổ Chức Của Edit Master Click To DSLK Đơ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 1  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.
ClickCTDL của DSLK đơn To Edit Master Title 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; pNex  Cấu trúc dữ liệu của DSLK đơ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 1 t Info 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
Ví dClick To Edit Master Title nhớ ụ tổ chức DSLK đơn trong bộ Style pHead pTail 4f 3f 5f 4 4f 7 5f 6 NULL Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Trong ví dụ trên thành phần dữ liệu là 1 số nguyên
CácClicktác cEditn trên DSLK đơn thao To ơ bả Master Title 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 Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1  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
Khởi tạo danh Edit Master Click To sách 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 1 l.pHead=NULL; l.pTail=NULL; }
Tạo 1 phầTo Edit Click n tử mới Master Title Style  Hàm trả về địa chỉ phần tử mới tạo CreateNode(Data x) // trong bài học là int Node* { 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 1 p ->Info = x; //gán dữa liệu cho nút p->pNext = NULL; return p; }
Thêm 1 phTo tEdit Master Click ần ử vào 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 Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1  Thêm vào cuối List  Thêm vào sau 1 phần tử q trong list
ThuClick To Editphần tử vào đầu DSLK ật toán thêm 1 Master Title Style  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 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 + pTail = pHead; Ngược lại + p->pNext = pHead; + pHead = p
Hàm thêmTo Edittử vào đầu List Click 1 phần Master Title 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 1 } else { p->pNext = l.pHead; l.pHead = p; } }
Minh họa thuậEdit Master Title Style Click To t toán thêm vào đầu pHead 4f 2f 3f 3 3f 4 4f 8… 9f Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 10 2f N pHead=P P->pNext=pHead P
Thuật To Edit Master Titlei Style Click toán thêm vào cuố 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 1 Ngược lại + pTail->pNext=p; + pTail=p
Hàm thêmTo Edittử vào cuốTitle Style Click 1 phần Master i 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 1 } else { l.pTail->Next = p; l.pTail = p; } }
Minh họa thuậEdit Master Title iStyle Click To t toán thêm vào cuố pTail 4f 5f 3f 5 4 4f 8 5f Nf 9 pTail=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 1 9f pTail->pNext 6N P
Thuật toán phần tMaster Titlephần tử q Click To Edit ử q vào sau Style  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 1 B2: + q->pNext = p + nếu q = pTail thì pTail=p
Cài Click 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 1 if(l.pTail==q) l.Tail=q; } else AddHead(l,q);// thêm q vào đầu list }
Click Minh họMastertTitle Style To Edit a thuậ toán 4f q 5f 3f 5 .. 4 4f 8 5f 9f 9f q->pNext=P 7N Cấu trúc dữ liệu và thuật giải 5f CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 P->pNext=q->pNext P
Hủy phần Totrong DSLK đơn Click tử Edit Master 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 Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1  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.
ThuClick To y phầMaster Title Style ật toán hủ Edit n tử trong DSLK  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 1 + pHead = pHead->pNext + delete (p)  B3: Nếu pHead==NULL thì pTail=NULL
Cài Click 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 1 delete p; if(l.pHead==NULL) l.pTail=NULL; return 1; } return 0; }