Bài giảng chương 2: Danh sách

1DANH SÁCH Chương 2 2Mục tiêu z Cung cấp cách cài đặt một số cấu trúc dữ liệu thường sử dụng như danh sách, danh sách liên kết, stack, queue, … z Minh họa bằng hình vẽ và mã lệnh tương ứng của các cấu trúc dữ liệu đã cài đặt z Ứng dụng của những cấu trúc dữ liệu này z So sánh ưu/nhược điểm của các cấu trúc dữ liệu với nhau 3Nội dung 1. Danh sách 2. Các biến thể của danh sách liên kết 3. Ngăn xếp 4. Hàng đợi 41. Danh Sách (list) z Định nghĩa z Các phép toán trên danh sách z Cài đặt danh sách 5Định nghĩa z ĐN: Danh sách là một tập hợp gồm nhiều phần tử a1, a2, …, an mà cấu trúc của nó là mối quan hệ giữa các phần tử với nhau z Như vậy, danh sách là cấu trúc dữ liệu tuyến tính, được tạo nên từ các phần tử dữ liệu theo một thứ tự xác định z Danh sách là một cấu trúc đặc biệt linh động bởi vì nó có thể co giản được (p.37 - Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, Data Structures and Algorithms - [4]) 6Định nghĩa z Danh sách thường được biển diễn với các phần tử được phân cách bằng dấu phẩy: a1, a2 ,…, an z a1 là phần tử đầu tiên, an là phần tử cuối cùng của danh sách z Số phần tử n (≥ 0) được gọi là chiều dài của danh sách z Ví dụ, sau đây là danh sách các số nguyên: 3, 5, 5, 0, 7, 5 7Định nghĩa z Không có hạn chế nào trên kiểu dữ liệu của các phần tử trong danh sách z Tuy nhiên, trong môn học này chúng ta chỉ xét các phần tử trong danh sách có cùng kiểu dữ liệu z Cần lưu ý là danh sách có thể được biểu diễn ở hai dạng: Danh sách đặc (condensed list) và danh sách liên kết (linked list). Trong danh sách đặc các phần tử được lưu trữ liên tục nhau trong bộ nhớ, còn trong danh sách liên kết các phần tử được lưu trữ ở những địa chỉ bất kỳ 8Các phép toán trên danh sách z Không giống như ngăn xếp (stack) hay hàng đợi (queue) là thao tác tuần tự trên những phần tử liên tiếp nhau, danh sách cho phép thao tác trên các phần tử tùy ý z Các phần tử trong danh sách có thể được truy xuất, chèn, xóa ở bất kỳ vị trí nào trên danh sách z Danh sách cũng có thể được kết nối với nhau hay cắt ra thành các danh sách con 9Danh sách đặc ([4] p.38, 41) z Để cài đặt danh sách đặc chúng ta có thể sử dụng mảng 10 Danh sách đặc z Trong trường hợp tổng quát, mỗi phần tử trong danh sách được xem là một struct và danh sách là một mảng các phần tử này. Ngoài ra, khai báo có sử dụng biến n để chứa chiều dài danh sách: const int MAX = 100; struct Element // Phần tử danh sách{ int key;};typedef Element List[MAX]; int n; // chiều dài danh sách 11 Danh sách đặc z Trường hợp tổng quát hơn nữa là cho Element và n vào một struct khác, đó là toàn bộ cấu trúc của danh sách. Tuy nhiên, việc truy xuất các phần tử trong danh sách sẽ trở nên rườm rà hơn z Khởi tạo danh sách: Cho số phần tử (chiều dài) n của danh sách bằng 0: void init(){ n = 0; } 12 Danh sách đặc z Hàm insert(x, p, L): Chèn x tại vị trí (chỉ số) p trong danh sách L, di chuyển các phần tử từ vị trí p đến cuối danh sách về hướng cuối danh sách một đơn vị. Nếu L là a1, a2, …, an thì L sẽ thành a1, a2, …,ap-1, x, ap, …, an 13 Danh sách đặc z Điều kiện: p phải là vị trí nào đó trong L (hoặc p là vị trí kế sau phần tử cuối cùng trong danh sách) và chiều dài n trước khi chèn phải nhỏ hơn MAX z Hàm locate(x, L): Hàm này trả về vị trí (chỉ số) của phần tử có trị là x trong danh sách L. Nếu có nhiều phần tử có trị x trong L thì vị trí x được tìm thấy đầu tiên được trả về. Nếu x không tồn tại trong L thì giá trị n được trả về (vì nếu L có n phần tử thì các phần tử có chỉ số từ 0 đến n-1, giá trị n được trả về cho thấy không tồn tại chỉ số này trong L) 14 Danh sách đặc z Ví dụ: z Hàm retrieve(p, L): Hàm này trả về phần tử tại vị trí p trong danh sách L. Nếu vị trí p không có trong L thì phần tử có giá trị là INT_MAX được trả về. Ví dụ, nếu p = 2 thì trả về L[2], tức phần tử có giá trị key là 8) 15 Danh sách đặc z Hàm delList(p, L): Xóa phần tử tại vị trí p trong danh sách L, di chuyển các phần tử từ sau vị trí p đến cuối danh sách về hướng đầu danh sách một đơn vị. Nếu L là a1, a2, …, an thì L sẽ thành a1, a2, …,ap-1, ap+1, …, an Điều kiện: p phải là vị trí nào đó trong L 16 Danh sách đặc z Lưu ý là trong ví dụ trên, mặc dù phần tử có giá trị 6 ở cuối danh sách vẫn còn trong bộ nhớ nhưng nó không còn trong danh sách vì chiều dài danh sách bây giờ là n = 4 (gồm các phần tử có giá trị là 5, 3, 8, 6) z Chương trình ví dụ, Figure 2.1 17 Ưu/nhược điểm của danh sách đặc z Ưu điểm: – Dễ dàng truy xuất phần tử L[i] trong danh sách L z Nhược điểm: – Do cài đặt bằng mảng tĩnh nên sử dụng bộ nhớ không hiệu quả (hoặc thiếu/thừa trong thời gian thực thi) – Không phù hợp với các phép toán chèn và loại bỏ phần tử. Bởi vì phải di chuyển tất cả phần tử sau đó về cuối hoặc về đầu danh sách 18 Danh sách liên kết ([1] p.204) z Danh sách liên kết là cấu trúc dữ liệu mà các đối tượng của nó cũng được sắp xếp theo thứ tự tuyến tính (linear order) z Tuy nhiên, không giống như mảng có thứ tự tuyến tính được xác định bởi chỉ số, thứ tự tuyến tính trong danh sách liên kết được xác định bởi con trỏ (pointer) trong mỗi đối tượng z Danh sách liên kết cung cấp sự biểu diễn mềm dẻo và đơn giản cho các dữ liệu động, hỗ trợ các thao tác như tìm kiếm, chèn, xóa, vv… 19 Danh sách liên kết đơn ([4] p.44) z Danh sách liên kết có thể được biểu diễn ở một số dạng (các biến thể) như: Danh sách liên kết đơn, kép, vòng, có thứ tự, … z Ví dụ danh sách liên kết đơn: 20 Danh sách liên kết đơn z Mỗi phần tử của danh sách liên kết đơn gồm hai vùng: Vùng chứa dữ liệu của phần tử đó (ai – để đơn giản, giả sử vùng này chỉ chứa số nguyên gọi là key) và vùng chứa địa chỉ của phần tử tiếp sau (vùng liên kết - next) z Vùng liên kết của an là nil (NULL) z Ngoài ra, cần phải có một biến con trỏ (head) để chứa địa chỉ (trỏ đến) của phần tử đầu tiên trong danh sách z Nếu danh sách rỗng thì head trỏ đến nil 21 Danh sách liên kết đơn z Khai báo danh sách: struct Node{ int key;Node *next; }; Node *head; z Khởi tạo danh sách: Để khởi tạo danh sách rỗng, gán head bằng NULL: void init(){ head = NULL;} 22 Danh sách liên kết đơn z Thêm phần tử p vào đầu danh sách: Cho vùng liên kết của p trỏ vào head, sau đó cho head trỏ vào p: z Figure 2.2 23 Danh sách liên kết đơn z Thêm phần tử p vào giữa hay cuối danh sách (nghĩa là sau phần tử q nào đó): Ta cho vùng liên kết của p trỏ vào liên kết của q, sau đó cho vùng liên kết của q trỏ vào p Figure 2.2 24 Danh sách liên kết đơn z Thêm phần tử p vào danh sách liên kết đã có thứ tự (tăng dần): Tìm phần tử q đứng ngay trước và phần r đứng ngay sau phần tử cần thêm p, chèn p vào giữa hai phần tử này Figure 2.2 25 Danh sách liên kết đơn z Tìm phần tử trong danh sách chưa có thứ tự: – Giả sử cần tìm phần tử có vùng key là x. Ta đi từ phần tử đầu tiên rồi tuần tự theo vùng liên kết đến cuối danh sách. Quá trình tìm kiếm sẽ kết thúc khi tìm thấy hoặc khi hết danh sách – Nếu tìm thấy thì hàm trả về địa chỉ của phần tử đầu tiên tìm được hoặc trả về NULL nếu không tìm thấy Figure 2.2 26 Danh sách liên kết đơn z Tìm phần tử trong danh sách đã có thứ tự: Vì danh sách đã có thứ tự, nên chỉ cần tìm x cho đến khi tìm thấy hoặc đến khi giá trị của phần tử hiện tại lớn hơn x (không cần phải tìm đến cuối danh sách) z Figure 2.2 27 Danh sách liên kết đơn z Loại bỏ phần tử q khỏi danh sách: – Nếu q là phần tử đầu tiên: Cho con trỏ head trỏ vào liên kết của q và giải phóng q khỏi bộ nhớ z Figure 2.2 28 Danh sách liên kết đơn – Nếu q là phần tử giữa hay cuối: Giả sử cần loại bỏ phần tử q sau phần tử p. Ta cho vùng liên kết của p trỏ vào liên kết của q và giải phóng q khỏi bộ nhớ Figure 2.2 29 Danh sách liên kết đơn – Loại bỏ phần tử q có nội dung là x: Quét từ đầu danh sách để tìm phần tử x, nếu tìm thấy thì gán phần tử này vào biến q. Lưu ý là cần phải lưu lại phần tử p đứng ngay trước q, nếu không có phần tử này thì không thể thực hiện thao tác xóa. Sau đó, xét xem q là head hay là phần tử khác để thực hiện thao tác xóa thích hợp. 30 Danh sách liên kết đơn – Figure 2.2 31 Ưu/nhược điểm của DSLK zƯu điểm: – Hiệu suất sử dụng bộ nhớ 100% – Thích hợp cho phép toán thêm vào và loại bỏ z Nhược điểm: – Tốn thêm vùng nhớ cho phần liên kết – Trong phép tìm kiếm chỉ có thể là tìm kiếm tuần tự 32 Các biến thể của DSLK z Danh sách liên kết đơn có các biến thể như: – Danh sách liên kết vòng (circularly linked list) – Danh sáck liên kết kép (double linked list) 33 Danh sách liên kết vòng ([3] p.108) z Liên kết của phần tử cuối (an) trỏ vào phần tử đầu tiên trong danh sách z Với danh sách này ta có thể truy cập mọi nút trong danh sách bắt đầu từ nút nào đó (không nhất thiết phài là nút đầu tiên). Tuy nhiên, điều này có thể tạo thành chu trình không kết thúc vì không biết chỗ kết thúc của danh sách 34 Danh sách liên kết vòng z Để khắc phục nhược điểm này, đưa thêm nút đặc biệt vào đầu danh sách z Nút head không chứa dữ liệu, chỉ có vùng next trỏ vào phần tử đầu của danh sách 35 Danh sách liên kết vòng z Một ưu điểm của danh sách liên kết vòng là trong phép loại bỏ, chỉ cần biết nút cần loại bỏ là đủ, không cần biết nút đứng trước, vì nút này có thể xác định được z Khởi tạo: void init(){ head = new Node;head->next = head;} 36 Danh sách liên kết vòng z Thêm một phần tử vào đầu danh sách: void insertFirst(int x) {Node *p;p = new Node;p->key = x;p->next = head->next;head->next = p; } 37 Danh sách liên kết kép ([1] p.204) z Trong danh sách liên kết đơn, khi loại bỏ phần tử q, ta phải xác định phần tử p đứng ngay trước q z Điều này dẫn đến là phải tìm p từ đầu danh sách z Để xác định ngay phần tử p mà không phải tìm kiếm, cấu trúc dữ liệu danh sách liên kết kép được sử dụng cho yêu cầu này 38 Danh sách liên kết kép z Ví dụ danh sách liên kết kép: z Mỗi phần tử của danh sách liên kết kép có ba trường: 39 Danh sách liên kết kép – Trường prev (previous): Là con trỏ, trỏ đến phần tử đứng ngay trước nó – Trường key: Chứa giá trị của phần tử – Trường next: Là con trỏ, trỏ đến phần tử đứng ngay sau nó z Trường prev của phần tử đầu tiên và trường next của phần tử cuối cùng trỏ đến nil z Con trỏ head và tail lần lượt trỏ vào phần tử đầu tiên và cuối cùng của danh sách. Thực chất tail chỉ có tác dụng khi truy suất danh sách theo thứ tự ngược, vì không phải tốn thời gian lần tìm nút cuối cùng của danh sách 40 Danh sách liên kết kép z Khai báo danh sách: struct Node{ int key;Node *prev, *next;};Node *head, *tail; z Khởi tạo danh sách: Để khởi tạo danh sách rỗng, gán head và tail bằng NULL: void init() { head = tail = NULL; } 41 Danh sách liên kết kép z Thêm phần tử p vào đầu danh sách: Có hai khả năng xảy ra là thêm vào danh sách rỗng hoặc không rỗng z Ví dụ: Figure 2.3 42 Danh sách liên kết kép z Tìm phần tử có giá trị là x trong danh sách: Cũng giống như cách thực hiện tìm kiếm phần tử trong danh sách liên kết đơn không có thứ tự, chúng ta bắt đầu từ đầu danh sách và tìm tuần tự cho đến khi tìm thấy hoặc đến hết danh sách (không tìm thấy) z Figure 2.3 43 Danh sách liên kết kép z Loại bỏ phần tử q khỏi danh sách: Cần xác định q là phần tử đầu, giữa hay cuối danh sách z Ví dụ, xét các trường hợp có thể xảy ra đối với q: 44 Danh sách liên kết kép z Figure 2.3 45 Chồng/ngăn xếp (stack) z Định nghĩa: ([1] p.200, [4] p.53) Stack là một loại danh sách đặc biệt mà tất cả các phép thêm vào và loại bỏ được thực hiện ở một đầu, gọi là đỉnh stack (top) 46 Ngăn xếp z Trong stack, phần tử được lấy ra trước hết là phần tử được đưa vào sau hết (đưa vào cuối cùng). Điều này ngược với hàng đợi z Stack còn được gọi là danh sách LIFO (last- in first-out list – vào sau ra trước) z Thao tác đưa một phần tử vào stack được gọi là push và thao tác lấy một phần tử khỏi stack được gọi là pop z Một ứng dụng điển hình của stack trong máy tính là quản lý quá trình gọi và thực thi chương trình con trong một chương trình 47 Ngăn xếp z Khai báo ngăn xếp: Chúng ta có thể cài đặt ngăn xếp bằng mảng và bằng danh sách liên kết đơn 1. Cài đặt bằng mảng: const int MAX = 100; struct Element { int key; }; Element stack[MAX]; int sp; 48 Ngăn xếp z Trong khai báo trên, biến nguyên sp được sử dụng làm con trỏ stack (stack pointer) để trỏ đến phần tử ở đỉnh stack (nơi mà phần tử này được lấy ra trước hết) z Khởi tạo ngăn xếp: Lúc đầu, con trỏ stack không trỏ đến phần tử nào void init(){ sp = -1;} 49 Ngăn xếp z Thêm phần tử vào ngăn xếp: – Ví dụ, ngăn xếp ban đầu: Có 4 phần tử, phần tử trên đỉnh ngăn xếp là 9 – Sau khi gọi hàm push() để thêm các phần tử lần lượt có giá trị là 17 và 3 50 Ngăn xếp – Gọi hàm pop() để lấy phần tử trên đỉnh stack, 3 được trả về – Lưu ý là giá trị 3 vẫn còn trong mảng nhưng nó không thể sử dụng trong stack, giá trị trên đỉnh stack bây giờ là 17 51 Ngăn xếp z Hàm push(): Có nhiều cách để định nghĩa hàm push() và pop() là chúng ở dạng trả trị hoặc không, sau đây là một trong các cách: void push(int x){ if(sp == MAX-1) cout << "Stack day!" << endl;elsestack[++sp].key = x;} 52 Ngăn xếp z Hàm pop(): Lấy phần tử ở đỉnh stack và gán cho tham số tham chiếu item: void pop(Element &item){ if(sp != -1)item = stack[sp--];else cout << "Stack rong!" << endl;} 53 Ngăn xếp 2. Cài đặt bằng danh sách liên kết: struct Node{ int key;Node *next;};Node *sp; z Khởi tạo ngăn xếp: void init(){ sp = NULL; } 54 Ngăn xếp z Thêm phần tử vào stack: Giống như phép toán thêm phần tử vào đầu danh sách liên kết đơn, con trỏ sp trỏ vào phần tử vừa thêm z Figure 2.4 55 Ngăn xếp z Lấy phần tử khỏi stack: Giống như phép toán loại bỏ phần tử ở đầu danh sách liên kết đơn, con trỏ sp trỏ vào phần tử kế tiếp z Figure 2.4 56 Ngăn xếp z Một vài ứng dụng của stack (xem bài tập) như: – Chuyển đổi cơ số – Xác định giá trị của một biểu thức số học theo ký pháp nghịch đã Ba Lan 57 Hàng đợi (queue) z Định nghĩa: ([1] p.201, [4] p.56) Hàng đợi là một loại danh sách đặc biệt mà các phép thêm vào được thực hiện ở một đầu (gọi là phía sau hàng – rear) và phép loại bỏ được thực hiện ở đầu còn lại (gọi là phía trước hàng – front) 58 Hàng đợi z Trong hàng, phần tử được lấy ra trước hết là phần tử được đưa vào trước hết và ngược lại z Hàng còn được gọi là danh sách FIFO (first-in first-out list – vào trước ra trước) z Thao tác đưa một phần tử vào hàng được gọi là enqueue và thao tác lấy một phần tử khỏi hàng được gọi là dequeue z Một ứng dụng điển hình của hàng đợi là quản lý và thực thi có trật tự các chương trình của hệ điều hành 59 Hàng đợi z Khai báo hàng đợi: Chúng ta có thể cài đặt hàng đợi bằng mảng và bằng danh sách liên kết đơn 1. Cài đặt bằng mảng: z Chúng ta có thể sử dụng mảng để cài đặt hàng đợi. Tuy nhiên, điều này không hiệu quả z Bởi vì trong thao tác dequeue để lấy phần tử khỏi hàng đợi thì các phần tử sau đó phải dịch chuyển lên một vị trí z Để tránh hao phí thời gian này, chúng ta phải có cách nhìn khác 60 Hàng đợi z Chẳng hạn, có thể xem mảng là một vòng tròn, tức là phần tử đầu tiên và phần tử cuối cùng nằm kế tiếp nhau z Để thêm phần tử vào hàng đợi, chúng ta phải di chuyển rear một vị trí theo chiều kim đồng hồ và thêm phần tử tại vị trí mới này 61 Hàng đợi z Để loại bỏ một phần tử khỏi hàng, lấy phần tử tại front và sau đó di chuyển front một vị trí theo chiều kim đồng hồ z Khai báo hàng đợi: const int MAX = 100;struct Element{ int key; }; Element queue[MAX];int front, rear; 62 Hàng đợi z Khởi tạo hàng đợi: void init(){ front = rear = -1;} z Thêm phần tử có trị x vào hàng: Figure 2.5 63 Hàng đợi z Loại bỏ phần tử khỏi hàng: z Figure 2.5 64 Hàng đợi z Cài đặt bằng DSLK: struct Node{ int key;Node *next;};Node *front, *rear; z Khởi tạo hàng đợi: void init(){ front = rear = NULL;} 65 Hàng đợi z Thêm phần tử vào hàng: Có hai trường hợp cần xét là lúc đầu hàng rỗng và khác rỗng z Figure 2.5 66 Hàng đợi z Lấy phần tử khỏi hàng: Nếu hàng không rỗng thi có hai trường hợp cần xét là hàng chỉ có một phần tử hoặc nhiều phần tử z Figure 2.5