Báo Cáo: Danh Sách Liên Kết

Trang chủ Tìm kiếm Trang chủ Tìm kiếm Báo cáo: Danh sách liên kết pdf 34 290 KB 1 21 4.7 ( 9 lượt) Xem tài liệu Nhấn vào bên dưới để tải tài liệu Tải về Đang chuẩn bị: 60 Bắt đầu tải xuống Đang xem trước 10 trên tổng 34 trang, để tải xuống xem đầy đủ hãy nhấn vào bên trên Chủ đề liên quan tài liệu về danh sách liên kết Cơ sở dữ liệu phát động bộ nhớ danh sách liên kết đơn danh sách liên kết vòng tròn

Nội dung

Danh Sách Liên Kết Nguyễn Thanh Hiên Danh Sách Liên Kết (Linked List) • Gồm nhiều phần tử (gọi mỗi phần tử là một node) • Các phần tử nối kết với nhau thông qua vùng liên kết • Các phần tử được try xuất tuần tự và bao gồm: vùng dữ liệu và các vùng liên kết Ai A node in a linked list A header node A tail node 1 Các loại danh sách liên kết • DSLK đơn A1 A2 A3 AN • DSLK kép A1 A2 A3 AN • DSLK vòng A1 A2 A3 AN Các Tác Vụ • • • • • • • • Khởi tạo (init) Kiểm tra DSLK rỗng (IsEmpty) Xác định kích thước (Size) Chèn (Insert) Xóa (Remove) Tìm kiếm (Retrieve) Thay thế (Replace) Duyệt (Traverse) 2 DSLK Đơn- Cấu trúc dữ liệu • typedef struct node{ T info; // T là kiểu đã định nghĩa trước struct node* link; // con trỏ chỉ đến cấu trúc node }NODE; • T là kiểu dữ liệu cơ bản hoặc kiểu dữ liệu tự định nghĩa DSLK Đơn- Cấu trúc dữ liệu • typedef struct node { int info; struct node* link; }NODE; CTDL cho một phần tử của DS các số nguyên 3 DSLK Đơn- Cấu trúc dữ liệu • typedef struct SinhVien { char Ten[30]; int MaSV; }SV; • typedef struct svNode { SV info; struct svNode* link; }SVNODE; CTDL cho một phần tử của DS các sinh viên DSLK Đơn- Cấu trúc dữ liệu • typedef struct phanso { int tu; int mau; }PS; • typedef struct psNode { PS info; struct psNode* link; }PSNODE; CTDL cho một phần tử của DS các phân số 4 DSLK Đơn- Cấu trúc dữ liệu pTail A1 A2 A3 AN pHead • typedef struct { NODE* pHead; NODE* pTail; } LIST; DSLK Đơn- Các Tác Vụ • Khởi tạo DS void init (LIST &list){ list.pHead=NULL; list.pTail=NULL; } 5 DSLK Đơn- Các Tác Vụ • Tạo một Node mới cho DS NODE* getNode(T x){ NODE* p; p=new NODE; if (p==NULL) return NULL; p-> info = x; p-> link=NULL; return p; } x DSLK Đơn- Các Tác Vụ • Chèn một phần tử vào DS – Chèn vào đầu (insertHead) – Chèn vào cuối (insertTail) – Chèn sau phần tử q (insertMid) 6 DSLK Đơn- Các Tác Vụ • Chèn vào đầu (insertHead) pTail pHead A1 A2 A3 AN (1) (2) x newNode DSLK Đơn- Các Tác Vụ • Chèn vào đầu (insertHead) void insertHead(LIST &ds, NODE* newNode) { if (ds.pHead==NULL) //ds rỗng { ds.pHead = newNode; ds.pTail = ds.pHead; } else { newNode ->link = ds.pHead; ds.pHead = newNode; } } 7 DSLK Đơn- Các Tác Vụ • Chèn vào cuối (insertTail) pTail (2) x (1) A1 A2 A3 AN pHead DSLK Đơn- Các Tác Vụ • Chèn vào cuối (insertTail) void insertTail(LIST &ds, NODE *newNode) { if (ds.pHead==NULL) { ds.pHead = newNode; ds.pTail = ds.pHead; } else { ds.pTail->link = newNode; ds.pTail = newNode; } } 8 DSLK Đơn- Các Tác Vụ • Chèn sau phần tử q (insertMid) q A1 pTail A2 A3 AN pHead (2) (1) x DSLK Đơn- Các Tác Vụ • Chèn sau phần tử q (insertMid) void insertMid(LIST &ds,NODE *q, NODE* newNode) { if ( q!=NULL) { newNode ->link = q-> link; q-> link = newNode; if(q == ds.pTail) ds.pTail = newNode; } else //chèn vào đầu danh sách insertHead(ds, newNode); } 9 DSLK Đơn- Các Tác Vụ • Tìm một phần tử trong DS NODE * Retrieve(LIST ds, Data k) { NODE *p; p = ds.pHead; while((p!= NULL)&&(p->info != x)) p = p->link; return p; } DSLK Đơn- Các Tác Vụ • Duyệt DS void * Traverse(LIST ds) { NODE *p; p = ds.pHead; while(p!= NULL){ process(p); p = p->link; } } 10 This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

Tìm kiếm

Chủ đề

Thực hành Excel Hóa học 11 Đồ án tốt nghiệp Mẫu sơ yếu lý lịch Giải phẫu sinh lý Trắc nghiệm Sinh 12 Đơn xin việc Tài chính hành vi Đề thi mẫu TOEIC Atlat Địa lí Việt Nam Lý thuyết Dow Bài tiểu luận mẫu adblock ​ Bạn đang sử dụng trình chặn quảng cáo?

Nếu không có thu nhập từ quảng cáo, chúng tôi không thể tiếp tục tài trợ cho việc tạo nội dung cho bạn.

Tôi hiểu và đã tắt chặn quảng cáo cho trang web này