›
›

Cơ sở dữ liệu - Chương 3: Cấu trúc dữ liệu động

ppt 80 trang vanle 3280
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cơ sở dữ liệu - Chương 3: Cấu trúc dữ liệu động", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptco_so_du_lieu_chuong_3_cau_truc_du_lieu_dong.ppt

Nội dung text: Cơ sở dữ liệu - Chương 3: Cấu trúc dữ liệu động

  1. Chương 3: CẤU TRÚC DỮ LIỆU ĐỘNG 3.1. Kiểu dữ liệu con trỏ 3.2. Danh sách liên kết (link list) 3.3. Danh sách liên kết đơn 3.4. Sắp xếp danh sách 3.5. Các cấu trúc đặc biệt của danh sách liên kết đơn 3.5.1. Stack 3.5.2. Hàng đợi (Queue) 3.6. Bài tập 1 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  2. 3.1. Kiểu Dữ Liệu Con Trỏ 3.1.1. Biến không động 3.1.2. Kiểu con trỏ 3.1.3. Biến động 2 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  3. 3.1.1. Biến không động Dùng đề lưu trữ những đối tượng dữ liệu được sử dụng không có nhu cầu thay đổi và kích thước, số lượng . . . • Được khai báo tường minh • Tồn tại trong phạm vi khái báo • Kích thước không thay đổi trong suốt quá trình sống Ví dụ: int a; char b[10]; 3 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  4. 3.1.2. Kiểu con trỏ üKiểu con trỏ là kiểu cơ sở dùng lưu địa chỉ của một đối tượng dữ liệu khác. üBiến thuộc kiểu con trỏ là biến mà giá trị của nó là địa chỉ một vùng nhớ của một biến hoặc là giá trị Null. Tùy vào loại con trỏ gần (near pointer) hay con trỏ xa (far pointer) mà kiểu dữ liệu con trỏ có các kích thước khác nhau: + Con trỏ gần: 2 bytes + Con trỏ xa: 4 bytes 4 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  5. Cú pháp định nghĩa một kiểu con trỏ typedef * ; Ví dụ: typedef int *intpointer; inpointer p; Hay int *p; Các thao tác: - Khi 1 biến con trỏ p lưu địa chỉ của đối tượng x, ta nói “p trỏ x” - Gán địa chỉ của biến cho con trỏ p: p=& -Truy xuất nội dung của đối tượng do p trỏ đến *p 5 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  6. c. Ví dụ: void main() { int a,b,*pa,*pb; a=2; b=3; cout<<"\nGia tri cua bien a="<<a; cout<<"\nGia tri cua bien b="<<b; pa=&a; pb=&b; cout<<"\nDia chi cua o nho con tro pa tro toi="<<pa; cout<<"\nDia chi cua o nho con tro pb tro toi="<<pb; cout<<"\nNoi dung cua o nho con tro pa tro toi="<<*pa; cout<<"\nNoi dung cua o nho con tro pb tro toi="<<*pb; *pa=20; /* Thay doi giá tr cua *pa*/ *pb=20; /* Thay doi giá tri cua *pb*/ cout<<"\nGia tri moi cua bien a="<<a; cout<<"\nGia tri moi cua bien b="<<b; } 6 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  7. 3.1.3. Biến động Trong trường hợp, tại thời điểm biên dịch không thể xác định trước kích thước chính xác của đối tượng dữ liệu(do chúng phụ thuộc vào ngữ cảnh). Các đối tượng dữ liệu này được khai báo như biến động. Biến động là những biến thỏa: ü Không được khai báo tường minh. ü Được cấp phát/giải phóng bộ nhớ khi yêu cầu. ü Các biến này không theo qui tắc phạm vi. ü Vùng nhớ của biến được cấp phát trong Heap. ü Kích thước thay đổi trong quá trình sống. 7 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  8. Các thao tác trên biến động: vTạo biến động và cho con trỏ p trỏ đến: Các hàm cấp phát bộ nhớ: void* malloc(size); // trả về con trỏ chỉ đến một vùng // nhớ size byte vừa được cấp phát. void* calloc(n,size);// trả về con trỏ chỉ đến một vùng // nhớ vừa được cấp phát gồm n //phần tử,mỗi phần tử có kích //thước size byte new // hàm cấp phát bộ nhớ trong C++ 8 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  9. vHủy một biến động do p chỉ đến: Hàm free(p): Huỷ vùng nhớ cấp phát bởi hàm malloc do p trỏ tới Hàm delete p: huỷ vùng nhớ cấp phát bởi hàm new do p trỏ tới 9 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  10. vVí dụ: //Trong C int* p1, p2; //Cấp phát vùng nhớ cho 1 biến động kiểu int p1 = (int*)malloc(sizeof(int)); //Đặt giá trị 5 cho biến động p1 p1* = 5; //Cấp phát biến động kiểu mảng 10 p.tử kiểu int p2 = (int*)calloc(10, sizeof(int)); //Đặt giá trị 0 cho phần tử thứ 4 của mảng p2 (p2+3)* = 0; free(p1); free(p2); //Trong C++ int* p; p=new int; 10 delete p; © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  11. 3.2. Danh Sách Liên Kết 3.2.1. Ðịnh nghĩa 3.2.2. Các hình thức tổ chức danh sách 11 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  12. 3.2.1. Ðịnh nghĩa Kiểu danh sách Tx gồm các phần tử thuộc kiểu T được định nghĩa là: Tx = trong đó: ü Vx = {tập hợp có thứ tự các phần tử kiểu T được móc nối với nhau theo trình tự tuyến tính}; ü Ox = {Tạo danh sách; Tìm 1 phần tử trong danh sách; Chèn một phần tử vào danh sách; Huỷ một phần tử khỏi danh sách ; Liệt kê danh sách, Sắp xếp danh sách } 12 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  13. Ví du: Hồ sơ các học sinh của một trường được tổ chức thành danh sách gồm nhiều hồ sơ của từng học sinh; số lượng học sinh trong trường có thể thay đổi do vậy cần có các thao tác thêm, hủy một hồ sơ; để phục vụ công tác giáo vụ cần thực hiện các thao tác tìm hồ sơ của một học sinh, in danh sách hồ sơ 13 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  14. 3.2.2. Các hình thức tổ chức danh sách v Mối liên hệ giữa các phần tử được thể hiện ngầm: ü Mỗi phần tử trong danh sách được đặc trưng bằng chỉ số. ü Cặp phần tử xi, xi+1 được xác định là kế cận ü Với hình thức tổ chức này, các phần tử của danh sách phải lưu trữ liên tiếp trong bộ nhớ, công thức xác định địa chỉ phần tử thứ I là. Cách biểu diễn này cho phép truy xuất ngẫu nhiên, đơn giản và nhanh chóng đến một phần tử bất kỳ trong danh sách, nhưng lại hạn chế về mặt sử dụng bộ nhớ bị lãng phí. 14 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  15. vMối liên hệ giữa các phần tử thể hiện tường minh: ü Mỗi phần tử ngoài các thông tin còn chứa một liên kết (địa chỉ) đến phần tử kế trong danh sách nên còn được gọi là danh sách móc nối. ü Với hình thức này các phần tử trong danh sách không cần phải lưu trữ kế cận trong bộ nhớ nên khắc phục được các khuyết điểm của hình thức tổ chức mảng, nhưng việc truy xuất đến một phần tử đòi hỏi phải thực hiện truy xuất qua một số phần tử khác. 15 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  16. Có các kiểu tổ chức liên kết giữa các phần tử. ü Danh sách liên kết đơn ü Danh sách liên kết kép ü Danh sách liên kết vòng 16 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  17. 3.3. Danh Sách Liên Kết Đơn 3.3.1. Tổ chức danh sách đơn theo cách cấp phát liên kết 3.3.2. Các thao tác cơ bản trên danh sách đơn 17 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  18. 3.3.1. Tổ chức danh sách đơn theo cách cấp phát liên kết Mỗi phần tử là một cấu trúc chứa 2 thông tin : - Thành phần dữ liệu: Lưu trữ các thông tin về bản thân phần tử . - Thành phần mối liên kết: lưu trữ địa chỉ của phần tử kế tiếp trong danh sách, hoặc lưu trữ giá trị NULL nếu là phần tử cuối danh s ách. Ta có định nghĩa tổng quát struct tNode { DataType key; tNode* pNext; }; 18 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  19. Ví dụ: Ðịnh nghĩa danh sách đơn lưu trữ hồ sơ SV struct tSinhVien { char Ten[30]; int MaSV; }; typedef struct tSinhVien Sinhvien; struct SinhvienNode { Sinhvien Info; SinhvienNode* pNext; }; typedef struct SinvienNode SVNode; 19 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  20. Nếu biết được địa chỉ của phần tử đầu tiên trong danh sách đơn thì có thể dựa vào thông tin pNext của nó để truy xuất đến phần tử thứ 2, thứ 3 Để quản lý một xâu đơn chỉ cần biết địa chỉ phần tử đầu xâu. Con trỏ Head dùng để lưu trữ địa chỉ phần tử đầu xâu Khai báo: NODE *pHead; Ðể tiện lợi, có thể sử dụng thêm một con trỏ pTail giữ địa chỉ phần tử cuối xâu. Khai báo: NODE *pTail; 20 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  21. 3.3.2. Các thao tác cơ bản trên danh sách đơn 21 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  22. Các định nghĩa, Khởi tạo danh sách LK Đơn: struct tNode{ struct tList{ int key; node *pHead; tNode *pnext; node *pTail; }; }; typedef struct tNode *Node; typedef struct tList List; void Khoitao(List &L){ L.pHead=L.pTail=NULL; } 22 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  23. Các hàm con tạo Nút và Huỷ nút : Node * Taonut(int x){ Node *p; p=new Node; p->key=x; p->pNext=NULL; return p; } void Huy(List &L){ Node *p; while(L.pHead) { p=L.pHead; L.pHead=L.pHead->pNext; delete p; } } 23 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường CĐ CNTT TP.HCM
  24. v Chèn một phần tử vào đầu danh sách Thuật toán : void Themdau(List &L, Node *p){ Bắt đầu: if(L.pHead==NULL) Nếu Danh sách rỗng Thì L.pHead=L.pTail=p; B11 : Head = new_elelment; else { B12 : Tail = Head; p->pNext=L.pHead; Ngược lại L.pHead=p; B21 : new_ele ->pNext = Head; } B22 : Head = new_ele ; } 24 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  25. void Nhap(List &L) { int x; Node *p; Khoitao(L); do { cout >x; if(x==0) break; p=Taonut(x); Themdau(L,p); }while(true); } 25 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  26. void Xuat(List L){ Node *p=L.pHead; while(p) { cout Key pNext; } } void main() { List L; Nhap(L); cout<<"\nDanh sach vua nhap: "; Xuat(l); Huy(L); } 26 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  27. v Chèn một phần tử vào cuối danh sách Thuật toán : void Themcuoi(List &L, Node *p){ Bắt đầu : if(L.pHead==NULL) Nếu Danh sách rỗng Thì L.pHead=L.pTail=p; B11 : Head = new_elelment; else { B12 : Tail = Head; L.pTail->pNext=p; Ngược lại L.pTail=p; B21 : Tail ->pNext = new_ele; } B22 : Tail = new_ele ; } 27 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  28. v Chèn một phần tử vào sau phần tử q Thuật toán : Bắt đầu : Nếu ( q != NULL) thì B1: new_ele -> pNext = q->pNext; B2: q->pNext = new_ele void Thempsauq(List &L, Node *p, Node *q){ if(q->pNext!=NULL) p->pNext=q->pNext; q->pNext=p; } 28 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  29. v Tìm một phần tử trong danh sách đơn Thuật toán : Áp dụng thuật toán tìm tuyến tính để xác định phần tử trong xâu có khoá k: Bước 1: p = Head; //Cho p trỏ đến phần tử đầu danh sách Bước 2: Trong khi (p != NULL) và (p->key != k ) p:=p->Next;// Cho p trỏ tới phần tử kế Bước 3: Nếu p != NULL thì p trỏ tới phần tử cần tìm Ngược lại không có phần tử cần tìm. Node *Search(LIST l, int k){ Node *p; p = l.pHead; while((p!= NULL)&&(p->key != k)) p = p->pNext; return p; } 29 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường CĐ CNTT TP.HCM
  30. NODE *Search(LIST l, Data k) { NODE *p; p = l.pHead; while((p!= NULL)&&(p->Info != x)) p = p->pNext; return p; } 30 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  31. v Hủy một phần tử đầu danh sách đơn Thuật toán : Bắt đầu: Nếu (Head != NULL) thì B1: p = Head; B2: B21 : Head = Head->pNext; // tách p ra khỏi xâu B22 : free(p); // Hủy biến động do p trỏ đến B3: Nếu Head=NULL thì Tail = NULL; //Xâu rỗng. 31 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  32. Data RemoveHead(LIST &l) { NODE *p; Data x = NULLDATA; if ( l.pHead != NULL) { p = l.pHead; x = p->Info; l.pHead = l.pHead->pNext; delete p; if(l.pHead == NULL) l.pTail = NULL; } return x; } 32 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  33. v Hủy một phần tử đứng sau phần tử q Thuật toán : Bắt đầu: Nếu (q!= NULL) thì B1: p = q->Next; // p là phần tử cần hủy B2: Nếu (p != NULL) thì // q không phải là cuối xâu B21 : q->Next = p->Next; // tách p ra khỏi xâu B22 : free(p); // Hủy biến động do p trỏ đến 33 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  34. void RemoveAfter (LIST &l, NODE *q) { NODE *p; if ( q != NULL) { p = q ->pNext ; if ( p != NULL) { if(p == l.pTail) l.pTail = q; q->pNext = p->pNext; delete p; } } else RemoveHead(l); } 34 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  35. v Hủy một phần tử có khóa k Thuật toán : Bước 1: Tìm phần tử p có khóa k và phần tử q đứng trước nó Bước 2: Nếu (p!= NULL) thì // tìm thấy k Hủy p ra khỏi xâu tương tự hủy phần tử sau q; Ngược lại Báo không có k; 35 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  36. int RemoveNode(LIST &l, Data k) { NODE *p = l.pHead; NODE *q = NULL; while( p != NULL) { if(p->Info == k) break; q = p; p = p->pNext; } if(p == NULL) return 0; //Không tìm thấy k if(q != NULL) { if(p == l.pTail) l.pTail = q; q->pNext = p->pNext; delete p; }else{ l.pHead = p->pNext; if(l.pHead == NULL) l.pTail = NULL; } return 1; } 36 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  37. v Duyệt danh sách Duyệt danh sách là thao tác thường được thực hiện khi có nhu cầu xử lý các phần tử của danh sách như: - Ðếm các phần tử của danh sách, - Tìm tất cả các phần tử thoả điều kiện, - Huỷ toàn bộ danh sách (và giải phóng bộ nhớ) Thuật toán : Bước 1: p = Head; //Cho p trỏ đến phần tử đầu DS Bước 2: Trong khi (Danh sách chưa hết) thực hiện B21 : Xử lý phần tử p; B22 : p:=p->pNext; // Cho p trỏ tới phần tử kế 37 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  38. void ProcessList (LIST &l) { NODE *p; p = l.pHead; while (p!= NULL) { ProcessNode(p); // xử lý cụ thể tùy ứng dụng p = p->pNext; } } 38 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  39. 3.4. Sắp Xếp Danh Sách 3.4.1. Các cách tiếp cận 3.4.2. Một số phương pháp sắp xếp trên danh sách 39 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  40. 3.4.1. Các cách tiếp cận DS có thứ tự là DS mà các phần tử được sắp xếp theo một thứ tự nào đó dựa trên trường khoá. Ðể sắp xếp một danh sách, có 2 phương án: Phương án 1: Hoán vị nội dung các phần tử trong danh sách ü Sử dụng các thuật toán sắp xếp như trên mảng, dựa trên việc hoán vị nội dung của các phần tử ü Phương pháp này đòi hỏi sử dụng vùng nhớ trung gian, số lần hoán vị có thể lên đến bậc n2. Làm cho thao tác sắp xếp chậm không tận dụng được các ưu điểm của DSLK . 40 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  41. Ví dụ : Cài đặt thuật toán sắp xếp Chọn trực tiếp void ListSelectionSort (LIST &l) { NODE *min,*p,*q; p = l.pHead; int tam; while(p != l.pTail) { q = p->pNext; min = p; while(q != NULL){ if(q->Key Key ) min = q; q= q->pNext; } tam=min->Key; min->Key=p->Key; p->Key=tam; p = p->pNext; } } 41 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  42. Phương án 2: Thay đổi các mối liên kết (trên vùng Next) üThay đổi trình tự móc nối của các phần tử sao cho tạo lập nên được thứ tự mong muốn, üTuy nhiên thao tác trên các mọc nối thường sẽ phức tạp hơn là thao tác trực tiếp trên dữ liệu. üBước1: Khởi tạo danh sách mới Result là rỗng; üBước2: Tìm trong danh sách cũ l phần tử nhỏ nhất; üBước3: Tách min khỏi danh sách l; üBước4: Chèn min vào cuối danh sách Result; üBước5: Lặp lại bước 2 khi chưa hết danh sách Head; 42 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  43. void ListSelectionSort2 (LIST &l){ LIST lRes; NODE *min; // chỉ đến phần tử có giá trị nhỏ nhất NODE *p,*q, minprev; lRes.pHead = lRes.pTail = NULL; // khởi tạo lRes while(l.pHead != NULL){ p = l.pHead; q = p->pNext; min = p; minprev = NULL; while(q != NULL){ if(q->Info Info ) { min = q; minprev = p } p = q; q = q->pNext; } if(minprev != NULL) minprev->pNext = min->pNext; else l.pHead = min->pNext; min->pNext = NULL; AddTail(lRes, min); } l = lRes; 43 } © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  44. 3.4.2. Một số phương pháp sắp xếp trên danh sách v Thuật toán Quick Sort üBước 1: Chọn X là phần tử đầu DS L làm phần tử cầm canh. Loại X ra khỏi L. üBước 2: Tách DS L ra làm 2 DS L1 (gồm các phần tử nhỏ hơn hay bằng X) và L2 (gồm các phần tử lớn hơn X). üBước 3: Nếu L1 != NULL thì Quick Sort (L1). üBước 4: Nếu L2 != NULL thì Quick Sort (L2). üBước 5: Nối L1, X, và L2 theo trình tự ta có DS L được sắp xếp. 44 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  45. Ví dụ Chọn X = 4 làm phần tử cầm canh và tách L thành L1, L2: Sắp xếp L1: 45 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  46. Sắp xếp L2: Chọn X = 6 làm phần tử cầm canh và tách L2 thanh L21, L22 Nối L12, X2, L22 thành L2: Nối L1, X, L2 thành L: 46 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  47. void ListQSort(LIST & l){ NODE *p, *X; // X chỉ đến phần tử cầm canh LIST l1, l2; if(l.pHead == l.pTail) return;//đã có thứ tự l1.pHead == l1.pTail = NULL; //khởi tạo l2.pHead == l2.pTail = NULL; X = l.pHead; l.pHead = X->pNext; while(l.pHead != NULL) //Tách l thành l1, l2;{ p = l.pHead; l.pHead = p->pNext; p->pNext = NULL; if (p->Info Info) AddTail(l1, p); else AddTail(l2, p); } ListQSort(l1); ListQSort(l2); //Gọi đệ qui để sorl1, sort l2 //Nối l1, X và l2 lại thành l đã sắp xếp. if(l1.pHead != NULL) { l.pHead = l1.pHead; l1.pTail->pNext = X; } else l.pHead = X; X->pNext = l2; if(l2.pHead != NULL) l.pTail = l2.pTail; else l.pTail = X; } 47 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  48. Ngoài ra còn một số thuật toán khác như Merge Sort, Radix Sort 48 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  49. 3.5. Các Cấu Trúc Đặc Biệt Của Danh Sách Liên Kết Đơn 3.5.1. Stack 3.5.2. Hàng đợi (Queue) 49 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  50. 3.5.1. Stack üStack là một vật chứa (container) làm việc theo cơ chế LIFO (Last In First Out) "Vào sau ra trước". üThao tác thêm 1 đối tượng vào stack gọi là "Push". Thao tác lấy 1 đối tượng ra khỏi stack gọi là "Pop". üStack có nhiều ứng dụng: khử đệ qui, tổ chức lưu vết các quá trình tìm kiếm theo chiều sâu, quay lui, vét cạn, ứng dụng trong tính toán biểu thức, đồ thị . . . Push Pop 50 Hình ảnh stack © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  51. CTDL Stack hỗ trợ các thao tác: ü Push(o): Thêm đối tượng o vào đầu stack ü Pop(): Lấy đối tượng ở đầu stack ra khỏi stack và trả về giá trị của nó. Nếu stack rỗng thì lỗi sẽ xảy ra. ü isEmpty(): Kiểm tra xem stack có rỗng không. ü isFull():Kiểm tra xem stack có đầy không. ü StackTop(): Trả về giá trị của phần tử nằm ở đầu stack. Nếu stack rỗng thì lỗi sẽ xảy ra. 51 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  52. Ðể biểu diễn Stack: Dùng mảng 1 chiều hoặc danh sách liên kết. Mảng 1 chiều Danh sách liên kết đơn - Viết chương trình dễ dàng, Phức tạp khi triển khai chương nhanh chóng trình - Bị hạn chế do số lượng phần tử Không bị cố định về số phần tử, cố định phụ thuộc vào bộ nhớ - Tốn chi phí tái cấp phát và sao chép vùng nhớ nếu sử dụng mảng động 52 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  53. Ngăn xếp sử dụng mảng // Giả sử Stack chứa các phần tử kiểu nguyên // Khai báo cấu trúc Stack typedef struct STACK { int* StkArray; // mảng chứa các phần tử int StkMax; // số phần tử tối đa int StkTop; // vị trí đỉnh Stack }; //Thao tác “Khởi tạo Stack rỗng” int InitStack(STACK& s, int MaxItems) { s.StkArray = new int[MaxItems]; if (s.StkArray == NULL) return 0; // Không cấp phát được bộ nhớ s.StkMax = MaxItems; s.StkTop = -1; // chưa có phần tử nào trong Stack return 1; // khởi tạo thành công 53 } © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  54. //Thao tác “Kiểm tra Stack rỗng” int IsEmpty(const STACK &s) { if (s.StkTop==-1) return 1; // Stack rỗng return 0; // Stack không rỗng } //Thao tác “Kiểm tra Stack đầy” int IsFull(const STACK &s) { if (s.StkTop==s.StkMax-1) return 1; // Stack đầy return 0; // Stack chưa đầy } 54 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  55. //Thao tác “Push”: thêm một phần tử vào đỉnh Stack int Push (STACK& s, int newitem) { if (IsFull(s)) return 0; // stack đầy, không thể thêm s.StkTop++; s.StkArray[s.StkTop] = newitem; return 1; // thêm thành công } //Thao tác “Pop”: lấy ra 1 phần tử từ đỉnh Stack int Pop(STACK& s, int& outitem) { if (IsEmpty(s)) return 0; // Stack rỗng, không lấy ra được outitem = s.StkArray[s.StkTop]; s.StkTop ; return 1; // lấy ra thành công } 55 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  56. //truy xuất 1 phần tử ở đỉnh Stack, không làm thay đổi Stack int StackTop(const STACK s, int& outitem) { if (IsEmpty(s)) return 0; // Stack rỗng, không lấy ra được outitem = s.StkArray[s.StkTop]; return 1; // lấy ra thành công } 56 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  57. Ngăn xếp sử dụng DSLK // Giả sử Stack chứa các phần tử kiểu nguyên // Khai báo cấu trúc một phần tử trong stack typedef struct tagSTACK_NODE { int Data; tagSTACK_NODE *pNext; } STACK_NODE; // Khai báo cấu trúc stack typedef struct STACK { int StkCount; STACK_NODE *StkTop; }; 57 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  58. //Thao tác “Khởi tạo stack rỗng”: void InitStack(STACK& s) { s.StkTop = NULL; s.StkCount = 0; } //Thao tác “Kiểm tra stack rỗng” int IsEmpty(const STACK& s) { if (s.StkTop == NULL) return 1; // stack rỗng return 0; // stack không rỗng } 58 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  59. //Thao tác “Kiểm tra stack đầy” int IsFull (const STACK s) { // thử tạo mới một phần tử STACK_NODE* temp = new STACK_NODE; // nếu không tạo được stack đầy if (temp == NULL) return 1; // stack đầy delete temp; return 0; // stack chưa đầy } 59 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  60. //Thao tác “Push”: thêm 1 phần tử vào đỉnh stack int Push(STACK &s, int newitem) { if (IsFull(s)) return 0; // Stack đầy, không thêm vào được STACK_NODE *pNew = new STACK_NODE; pNew->Data = newitem; pNew->pNext = s.StkTop; s.StkTop = pNew; s.StkCount++; return 1; // Thêm thành công } 60 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  61. //Thao tác “Pop”: lấy ra 1 phần tử từ đỉnh stack int Pop(STACK &s, int& outitem) { if (IsEmpty(s)) return 0; // Stack rỗng, không lấy ra được // lưu lại con trỏ đến ptử đầu STACK_NODE *temp = s.StkTop; outitem = s.StkTop->Data; s.StkTop = s.StkTop->pNext; delete temp; s.StkCount ; return 1; // Lấy ra thành công } 61 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  62. //Thao tác “StackTop”: truy xuất 1 phần tử ở đỉnh stack int StackTop(STACK &s, int& outitem) { if (IsEmpty(s)) return 0; // Stack rỗng, không lấy ra được outitem = s.StkTop->Data; return 1; // Lấy ra thành công } 62 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  63. 3.5.2. Hàng đợi (Queue) ü Hàng đợi là một vật chứa (container) các đối tượng ü Làm việc theo cơ chế FIFO (First In First Out) "Vào trước ra trước". Phòng vé Hình ảnh queue 63 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  64. CTDL Queue hỗ trợ các thao tác: üInitQueue: Khởi tạo hàng đợi rỗng üIsEmpty: Kiểm tra hàng đợi rỗng ? üIsFull: Kiểm tra hàng đợi đầy ? üEnQueue: Thêm 1 phần tử vào cuối hàng đợi, có thể làm hàng đợi đầy üDeQueue: Lấy ra 1 phần tử từ đầu Queue, có thể làm Queue rỗng üQueueFront: Kiểm tra phần tử đầu Queue ü QueueRear: Kiểm tra phần tử cuối Queue 64 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  65. Ðể biểu diễn Queue: Dùng mảng 1 chiều hoặc danh sách liên kết. Mảng 1 chiều Danh sách liên kết đơn - Viết chương trình dễ dàng, Phức tạp khi triển khai chương nhanh chóng trình - Bị hạn chế do số lượng phần tử Không bị cố định về số phần tử, cố định phụ thuộc vào bộ nhớ - Tốn chi phí tái cấp phát và sao chép vùng nhớ nếu sử dụng mảng động 65 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  66. Hàng đợi sử dụng mảng ü Mảng (QArray) để chứa các phần tử. ü Số nguyên (QMax)để lưu số phần tử tối đa ü 2 số nguyên (Qfront/QRear) để xác định vị trí đầu/cuối ü Số nguyên (QNumItems) để lưu số phần tử hiện có 0 1 2 3 4 5 6 Qarray 37 22 15 3 QMax = 7 QNumItems = 4 QFront = 1 QRear = 4 66 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  67. // Giả sử Queue chứa các phần tử kiểu nguyên (int) // Khai báo cấu trúc Queue typedef struct QUEUE { int* QArray; int QMax; int QNumItems; int QFront; int QRear; }; 67 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  68. Khi thêm nhiều phần tử sẽ xảy ra hiện tượng “tràn giả” 0 1 2 3 4 5 6 Qarray 37 22 15 3 7 9 QMax = 7 QNumItems = 4 QFront = 1 QRear = 7 Giải pháp? Nối dài mảng (mảng động) hay sử dụng một mảng vô cùng lớn? 68 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  69. //Thao tác “Khởi tạo Queue rỗng”: int InitQueue(QUEUE& q, int MaxItem) { q.QArray = new int[MaxItem]; if (q.QArray == NULL) return 0; // không đủ bộ nhớ q.QMax = MaxItem; q.QNumItems = 0; q.QFront = q.QRear = -1; return 1; // thành công } 69 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  70. //Thao tác “Kiểm tra Queue rỗng”: int IsEmpty(QUEUE q) { if (q.QNumItems == 0) return 1; // rỗng return 0; // không rỗng } //Thao tác “Kiểm tra Queue đầy”: int IsFull(QUEUE q) { if (q.QMax == q.QNumItems) return 1; // đầy return 0; // không đầy } 70 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  71. //Thao tác EnQueue: thêm 1 phần tử vào cuối Queue int EnQueue(QUEUE &q, int newitem) { if (IsFull(q)) return 0; // Queue đầy, không thêm vào được q.QRear++; if (q.QRear==q.QMax) // “tràn giả” q.QRear = 0; // Quay trở về đầu mảng q.QArray[q.QRear] = newitem; // thêm phần tử vào cuối Queue if (q.QNumItems==0) q.QFront = 0; q.QNumItems++; return 1; // Thêm thành công } 71 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  72. //Thao tác DeQueue: lấy ra 1 phần tử ở đầu Queue int DeQueue(QUEUE &q, int& itemout) { if (IsEmpty(q)) return 0; // Queue rỗng, không lấy ra được itemout = q.QArray[q.QFront]; // lấy phần tử đầu ra q.QFront++; q.QNumItems ; if (q.QFront==q.QMax) // nếu đi hết mảng q.QFront = 0; // quay trở về đầu mảng if (q.QNumItems==0) // nếu lấy ra phần tử cuối cùng q.QFront = q.QRear = -1; // khởi tạo lại Queue return 1; // Lấy ra thành công } 72 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  73. //Thao tác QueueFront: Kiểm tra phần tử ở đầu Queue int QueueFront(const QUEUE &q, int& itemout) { if (IsEmpty(q)) return 0; // Queue rỗng, không kiểm tra // lấy phần tử đầu ra itemout = q.QArray[q.QFront]; return 1; } //Thao tác QueueRear: Kiểm tra phần tử ở cuối Queue int QueueRear(const QUEUE &q, int& itemout) { if (IsEmpty(q)) return 0; // Queue rỗng, không kiểm tra // lấy phần tử cuối ra itemout = q.QArray[q.QRear]; return 1; 73 } © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  74. Hàng đợi sử dụng DSLK //Khai báo cấu trúc typedef struct tagNODE { int data; tagNODE* pNext; } NODE, *PNODE; typedef struct tagQUEUE { int NumItems; PNODE pFront, pRear; } QUEUE; 74 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  75. Các thao tác cơ bản üint InitQueue(QUEUE& q); üint IsEmpty(const QUEUE& q); üint IsFull(const QUEUE& q); üint EnQueue(QUEUE &q, int newitem); üint DeQueue(QUEUE &q, int& itemout); üint QueueFront(const QUEUE &q, int& itemout); üint QueueRear(const QUEUE &q, int& itemout); 75 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  76. //Khởi tạo Queue rỗng int InitQueue(QUEUE& q) { q.NumItems = 0; q.pFront = q.pRear = NULL; return 1; } 76 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  77. //Kiểm tra Queue rỗng int IsEmpty(const QUEUE& q) { return (q.NumItems==0); } //Kiểm tra Queue đầy int IsFull(const QUEUE& q) { PNODE tmp = new NODE; if (tmp==NULL) return 1; delete tmp; return 0; 77 } © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  78. //Thêm 1 phần tử vào cuối Queue int EnQueue(QUEUE &q, int newitem) { if (IsFull(q)==1) return 0; PNODE p = new NODE; p->data = newitem; p->pNext = NULL; if (q.pFront==NULL && q.pRear==NULL) q.pFront = q.pRear = p; else { q.pRear->pNext = p; q.pRear = p; } q.NumItems++; return 1; 78 } © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  79. //Lấy ra 1 phần tử ở đầu Queue int DeQueue(QUEUE &q, int& itemout) { if (IsEmpty(q)==1) return 0; PNODE p = q.pFront; q.pFront = p->pNext; itemout = p->data; q.NumItems ; delete p; if (q.NumItems==0) InitQueue(q); return 1; } 79 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  80. //Kiểm tra 1 phần tử ở đầu Queue int QueueFront(const QUEUE &q, int& itemout) { if (IsEmpty(q)==1) return 0; itemout = q.pFront->data; return 1; } //Kiểm tra 1 phần tử ở cuối Queue int QueueRear(const QUEUE &q, int& itemout) { if (IsEmpty(q)==1) return 0; itemout = q.pRear->data; return 1; } 80 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương