intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Báo cáo: Danh sách liên kết

Chia sẻ: Van Vo Han | Ngày: | Loại File: PDF | Số trang:34

Thêm vào BST
Báo xấu
263
lượt xem 74
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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...

Chủ đề:

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

Lưu

Nội dung Text: Báo cáo: Danh sách liên kết

  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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Tài Chính Ngân Hàng
172 tài liệu
841 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2