1. Trang Chủ
  2. Công nghệ thông tin
  3. Báo cáo: Danh sách liên kết

Báo cáo: Danh sách 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... 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 A header node linked list A tail node 1 Các loại danh sách liên kết • DSLK đơn A2 A3 AN A1 • DSLK kép A1 A2 A3 AN • DSLK vòng A2 A3 AN A1 Các Tác

Thể loại Tài liệu miễn phí Công nghệ thông tin

Số trang 34

Ngày tạo 8/29/2018 8:49:33 PM +00:00

Loại tệp PDF

Kích thước

Tên tệp

Tải Báo cáo: Danh sách liên kết (.pdf)

Xem mẫu

  1. 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 A header node linked list A tail node 1
  2. Các loại danh sách liên kết • DSLK đơn A2 A3 AN A1 • DSLK kép A1 A2 A3 AN • DSLK vòng A2 A3 AN A1 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
  3. DSLK Đơn- Cấu trúc dữ liệu • typedef struct node{ info; // T là kiểu đã định nghĩa trước T 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; CTDL cho một }NODE; phần tử của DS các số nguyên 3
  4. DSLK Đơn- Cấu trúc dữ liệu • typedef struct SinhVien { char Ten[30]; int MaSV; }SV; • typedef struct svNode CTDL cho một phần tử của DS { các sinh viên SV info; struct svNode* link; }SVNODE; DSLK Đơn- Cấu trúc dữ liệu • typedef struct phanso { int tu; int mau; }PS; • typedef struct psNode CTDL cho một phần tử của DS { các phân số PS info; struct psNode* link; }PSNODE; 4
  5. DSLK Đơn- Cấu trúc dữ liệu pTail A2 A3 AN A1 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
  6. 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; x if (p==NULL) return NULL; p-> info = x; p-> link=NULL; return p; } 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
  7. DSLK Đơn- Các Tác Vụ • Chèn vào đầu (insertHead) pTail pHead A2 A3 AN A1 (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
  8. DSLK Đơn- Các Tác Vụ • Chèn vào cuối (insertTail) (2) x pTail (1) A2 A3 AN A1 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
  9. DSLK Đơn- Các Tác Vụ • Chèn sau phần tử q (insertMid) q pTail A2 A3 AN A1 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
  10. 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
  11. DSLK Đơn- Các Tác Vụ Xoá một phần tử • – Xoá phần tử đầu – Xoá phần tử sau phần tử q – Xoá phần tử có khoá k DSLK Đơn- Các Tác Vụ Xoá phần tử đầu • pTail pHead A2 A3 AN A1 11
  12. DSLK Đơn- Các Tác Vụ • Xoá phần tử đầu Data RemoveHead(LIST &ds) { NODE *p; Data x = NULLDATA; if ( ds.pHead != NULL) { p = ds.pHead; x = p->info; ds.pHead = ds.pHead->link; delete p; if(ds.pHead == NULL) ds.pTail = NULL; } return x; } DSLK Đơn- Các Tác Vụ • Xoá phân ftử sau phần tử q pTail q p pHead A2 A3 AN A1 12
  13. DSLK Đơn- Các Tác Vụ • Xoá phần tử sau phần tử q void RemoveAfter (LIST &ds, NODE *q) { NODE *p; if ( q != NULL) { p = q ->link ; if ( p != NULL) { if(p == ds.pTail) ds.pTail = q; q->link = p->link; delete p; } } else RemoveHead(ds); } DSLK Đơn- Các Tác Vụ • Xoá phần tử có khoá k if(q != NULL) int RemoveNode(LIST &ds, Data k) { { if(p == ds.pTail) NODE *p = ds.pHead; ds.pTail = q; NODE *q = NULL; q->link = p->link; while( p != NULL) delete p; { } if(p->info == k) break; else //p là phần tử đầu ds q = p; p = p->link; { } ds.pHead = p->link; if(p == NULL) return 0; if(ds.pHead == NULL) //Không tìm thấy k ds.pTail = NULL; } return 1; } 13
  14. DSLK Đơn- Hủy danh sách void ReamoveList(LIST &ds) { NODE *p; while (ds.pHead!= NULL) { p = ds.pHead; ds.pHead = p->link; delete p; } ds.pTail = NULL; } DSLK Kép- Cấu trúc dữ liệu typedef struct DNode { T info; struct DNode* pPre; struct DNode* pNext; }DNODE; 14
  15. DSLK Kép- Cấu trúc dữ liệu DNODE* GetNode(T x) { DNODE *p; p = new DNODE; if ( p==NULL) return NULL p ->Info = x; p->pPrev = NULL; p->pNext = NULL; return p; } DSLK Kép- Insert Chèn đầu • Chèn cuối • Chèn sau phần tử q • Chèn trước phần tử q • 15
  16. DSLK Kép- Insert DSLK Kép- Insert void Insert(DLIST &ds, DNODE* q, DNODE* newNode) { DNODE* p = q->pNext; if ( q!=NULL) { newNode->pNext = p; //(1) newNode->pPrev = q; //(2) q->pNext = newNode; //(3) if(p != NULL) p->pPrev = newNode; //(4) if(q == ds.pTail) ds.pTail = newNode; } else //chèn vào đầu danh sách InsertHead(ds, newNode); } 16
  17. DSLK Kép- Remove Xóa đầu • Xóa cuối • Xóa sau phần tử q • Xóa trước phần tử q • • Xóa có khóa k DSLK Kép- Remove sau q void Remove(DLIST &ds, DNODE *q) { DNODE *p; if ( q != NULL) { p = q ->pNext ; if ( p != NULL) { q->pNext = p->pNext; if(p == ds.pTail) ds.pTail = q; else p->pNext->pPrev = q; delete p; } } else RemoveHead(ds); } 17
  18. STACK Bottom_of_stack •Danh sách hạn chế 21 (this is where the 56 •Các phần tử được stack started) 31 thêm vào và lấy ra ở 29 đỉnh stack Direction 179 in which • Hiện thực dùng dslk top 52 stack grows hoặc array Empty/unfilled portion of stack Stack – Tác vụ typedef struct { • Init() T *theArray; • Push() int top; int size; • Pop() }STACK; • IsEmpty() void init (STACK &s, int size) { • IsFull() s.size = size; s.theArray = new T[size]; s.top = -1; } 18
  19. Stack- Push() void push(STACK &s, T x){ if (!isFull(s)){ s.top++; s.theArray[s.top]=x; } } bool isFull(STACK s) { if(s.top < s.size-1) return false; else return true; } Stack- Pop(), Top() T pop(STACK &s){ if (!isEmpty(s)) return s.theArray[s.top--]; } T top(STACK s){ return s.theArray[s.top]; } bool isEmpty(STACK s) { if(s.top == -1) return true; else return false; } 19
  20. Stack-Ví dụ 21 21 21 21 56 56 56 56 31 31 31 31 pop() push(2) top() 29 29 29 29 179 179 179 179 52 2 2 top top top Return 52 Return 2 Queue 12 31 79 5 63 front back empty portion of the queue Danh sách hạn chế • Chèn vào một đầu, lấy ra ở đầu kia • Hiện thực dùng dslk hoặc array • • Linear and Circular Queues 20
nguon tai.lieu . vn
Thạc sĩ - Tiến sĩ - Cao học Công nghệ thông tin Kinh tế - Thương mại Tài chính - Ngân hàng Kiến trúc - Xây dựng Điện-Điện tử-Viễn thông Cơ khí - Chế tạo máy Công nghệ - Môi trường Báo cáo khoa học Quản trị kinh doanh Khoa học xã hội Khoa học tự nhiên Nông - Lâm - Ngư Y khoa - Dược