Loại danh sách nào là tốt nhất để chọn cài đặt khi tìm kiếm phần tử thứ n trong danh sách
|
Stack là một vật chứa (container) các đối tượng làm việc theo cơ chế LIFO (Last In First Out) nghĩa là việc thêm một đối tượng vào stack hoặc lấy một đối tượng ra khỏi stack được thực hiện theo cơ chế "Vào sau ra trước". Các đối tượng có thể được thêm vào stack bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi stack. Thao tác thêm 1 đối tượng vào stack thường được gọi là "Push". Thao tác lấy 1 đối tượng ra khỏi stack gọi là "Pop". Trong tin học, CTDL 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 và quay lui, vét cạn, ứng dụng trong các bài toán tính toán biểu thức, .  Một hình ảnh một stack Ta có thể định nghĩa CTDL stack như sau: stack là một CTDL trừu tượng (ADT) tuyến tính hỗ trợ 2 thao tác chính: 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. Ngoài ra, stack cũng hỗ trợ một số thao tác khác: isEmpty(): Kiểm tra xem stack có rỗng không. Top(): Trả về giá trị của phần tử nằm ở đầu stack mà không hủy nó khỏi stack. Nếu stack rỗng thì lỗi sẽ xảy ra. Các thao tác thêm, trích và huỷ một phần tử chỉ được thực hiện ở cùng một phía của Stack do đó hoạt động của Stack được thực hiện theo nguyên tắc LIFO (Last In First Out - vào sau ra trước). Ðể biểu diễn Stack, ta có thể dùng mảng 1 chiều hoặc dùng danh sách liên kết.
Ta có thể tạo một stack bằng cách khai báo một mảng 1 chiều với kích thước tối đa là N (ví dụ, N có thể bằng 1000). Như vậy stack có thể chứa tối đa N phần tử đánh số từ 0 đến N -1. Phần tử nằm ở đầu stack sẽ có chỉ số t (lúc đó trong stack đang chứa t+1 phần tử) Ðể khai báo một stack, ta cần một mảng 1 chiều S, biến nguyên t cho biết chỉ số của đầu stack và hằng số N cho biết kích thước tối đa của stack. Tạo stack S và quản lý đỉnh stack bằng biến t: Data S [N]; int t; Việc cài đặt stack thông qua mảng một chiều đơn giản và khá hiệu quả. Tuy nhiên, hạn chế lớn nhất của phương án cài đặt này là giới hạn về kích thước của stack N. Giá trị của N có thể quá nhỏ so với nhu cầu thực tế hoặc quá lớn sẽ làm lãng phí bộ nhớ.
Ta có thể tạo một stack bằng cách sử dụng một danh sách liên kết đơn (DSLK). Có thể nói, DSLK có những đặc tính rất phù hợp để dùng làm stack vì mọi thao tác trên stack đều diễn ra ở đầu stack. Sau đây là các thao tác tương ứng cho list-stack: Tạo Stack S rỗng LIST * S; Lệnh S.pHead=l.pTail= NULL sẽ tạo ra một Stack S rỗng. Kiểm tra stack rỗng : char IsEmpty(LIST &S) { if (S.pHead == NULL) // stack rỗng return 1; else return 0; } Thêm một phần tử p vào stack S void Push(LIST &S, Data x) { InsertHead(S, x); } Trích huỷ phần tử ở đỉnh stack S Data Pop(LIST &S) { Data x; if(isEmpty(S)) return NULLDATA; x = RemoveFirst(S); return x; } Xem thông tin của phần tử ở đỉnh stack S Data Top(LIST &S) {if(isEmpty(S)) return NULLDATA; return l.Head->Info; } Ứng dụng của Stack Cấu trúc Stack thích hợp lưu trữ các loại dữ liệu mà trình tự truy xuất ngược với trình tự lưu trữ, do vậy một số ứng dụng sau thường cần đến stack : Trong trình biên dịch (thông dịch), khi thực hiện các thủ tục, Stack được sử dụng để lưu môi trường của các thủ tục. Trong một số bài toán của lý thuyết đồ thị (như tìm đường đi), Stack cũng thường được sử dụng để lưu dữ liệu khi giải các bài toán này. Ngoài ra, Stack cũng còn được sử dụng trong trường hợp khử đệ qui đuôi.
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) nghĩa là việc thêm một đối tượng vào hàng đợi hoặc lấy một đối tượng ra khỏi hàng đợi được thực hiện theo cơ chế "Vào trước ra trước". Các đối tượng có thể được thêm vào hàng đợi bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào đầu tiên mới được phép lấy ra khỏi hàng đợi. Thao tác thêm một đối tượng vào hàng đợi và lấy một đối tượng ra khỏi hàng đợi lần lượt được gọi là "enqueue" và "dequeue". Việc thêm một đối tượng vào hàng đợi luôn diễn ra ở cuối hàng đợi và một phần tử luôn được lấy ra từ đầu hàng đợi. Trong tin học, CTDL hàng đợi 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 rộng và quay lui, vét cạn, tổ chức quản lý và phân phối tiến trình trong các hệ điều hành, tổ chức bộ đệm bàn phím, . Ta có thể định nghĩa CTDL hàng đợi như sau: hàng đợi là một CTDL trừu tượng (ADT) tuyến tính. Tương tự như stack, hàng đợi hỗ trợ các thao tác: EnQueue(o): Thêm đối tượng o vào cuối hàng đợi DeQueue(): Lấy đối tượng ở đầu queue ra khỏi hàng đợi và trả về giá trị của nó. Nếu hàng đợi rỗng thì lỗi sẽ xảy ra. IsEmpty(): Kiểm tra xem hàng đợi có rỗng không. Front(): Trả về giá trị của phần tử nằm ở đầu hàng đợi mà không hủy nó. Nếu hàng đợi rỗng thì lỗi sẽ xảy ra. Các thao tác thêm, trích và huỷ một phần tử phải được thực hiện ở 2 phía khác nhau của hàng đợi do đó hoạt động của hàng đợi được thực hiện theo nguyên tắc FIFO (First In First Out - vào trước ra trước). Cũng như stack, ta có thể dùng cấu trúc mảng 1 chiều hoặc cấu trúc danh sách liên kết để biểu diễn cấu trúc hàng đợi.
Ta có thể tạo một hàng đợi bằng cách sử dụng một mảng 1 chiều với kích thước tối đa là N (ví dụ, N có thể bằng 1000) theo kiểu xoay vòng (coi phần tử an-1 kề với phần tử a0). Như vậy hàng đợi có thể chứa tối đa N phần tử. Phần tử nằm ở đầu hàng đợi (front element) sẽ có chỉ số f. Phần tử nằm ở cuối hàng đợi (rear element) sẽ có chỉ số r (xem hình). Ðể khai báo một hàng đợi, ta cần một mảng một chiều Q, hai biến nguyên f, r cho biết chỉ số của đầu và cuối của hàng đợi và hằng số N cho biết kích thước tối đa của hàng đợi. Ngoài ra, khi dùng mảng biểu diễn hàng đợi, ta cũng cần một giá trị đặc biệt để gán cho những ô còn trống trên hàng đợi. Giá trị này là một giá trị nằm ngoài miền xác định của dữ liệu lưu trong hàng đợi. Ta ký hiệu nó là NULLDATA như ở những phần trước. Trạng thái hàng đợi lúc bình thường: Trạng thái hàng đợi lúc xoay vòng: Câu hỏi đặt ra: khi giá trị f=r cho ta điều gì ? Ta thấy rằng, lúc này hàng đợi chỉ có thể ở một trong hai trạng thái là rỗng hoặc đầy. Coi như một bài tập các bạn hãy tự suy nghĩ tìm câu trả lời trước khi đọc tiếp để kiểm tra kết quả. Hàng đợi có thể được khai báo cụ thể như sau: Data Q[N] ; int f, r; Cũng như strack, do khi cài đặt bằng mảng một chiều, hàng đợi có ki�ch thước tối đa nên ta cần xây dựng thêm một thao tác phụ cho hàng đợi: IsFull(): Kiểm tra xem hàng đợi có đầy chưa.
Ta có thể tạo một hàng đợi bằng cách sử dụng một DSLK đơn.
Phần tử đầu DSKL (head) sẽ là phần tử đầu hàng đợi, phần tử cuối DSKL (tail) sẽ là phần tử cuối hàng đợi. Sau đây là các thao tác tương ứng cho array-queue: Lệnh Q.pHead = Q.pTail = NULL sẽ tạo ra một hàng đợi rỗng. char IsEmpty(LIST Q) { if (Q.pHead == NULL) // stack rỗng return 1; else return 0; } Thêm một phần tử p vào cuối hàng đợi void EnQueue(LIST Q, Data x) { InsertTail(Q, x); }
Data DeQueue(LIST Q) { Data x; if (IsEmpty(Q)) return NULLDATA; x = RemoveFirst(Q); return x; } Xem thông tin của phần tử ở đầu hàng đợi Data Front(LIST Q) { if (IsEmpty(Q)) return NULLDATA; return Q.pHead->Info; } Các thao tác trên đều làm việc với chi phí O(1). Lưu ý, nếu không quản lý phần tử cuối xâu, thao tác dequeue sẽ có độ phức tạp O(n).
Hàng đợi có thể được sử dụng trong một số bài toán: Bài toán �sản xuất và tiêu thụ� (ứng dụng trong các hệ điều hành song song). Bộ đệm (ví dụ: Nhấn phím -> Bộ đệm -> CPU xử lý). Xử lý các lệnh trong máy tính (ứng dụng trong HÐH, trình biên dịch), hàng đượi các tiến trình chờ được xử lý, ..
Hàng đợi hai đầu (gọi tắt là Deque) là một vật chứa các đối tượng mà việc thêm hoặc hủy một đối tượng được thực hiện ở cả 2 đầu của nó. Ta có thể định nghĩa CTDL deque như sau: deque là một CTDL trừu tượng (ADT) hỗ trợ các thao tác chính sau: InsertFirst(e): Thêm đối tượng e vào đầu deque InsertLast(e): Thêm đối tượng e vào cuối deque RemoveFirst(): Lấy đối tượng ở đầu deque ra khỏi deque và trả về giá trị của nó. RemoveLast(): Lấy đối tượng ở cuối deque ra khỏi deque và trả về giá trị của nó. Ngoài ra, deque cũng hỗ trợ các thao tác sau: IsEmpty(): Kiểm tra xem deque có rỗng không. First(): Trả về giá trị của phần tử nằm ở đầu deque mà không hủy nó. Last(): Trả về giá trị của phần tử nằm ở cuối deque mà không hủy nó.
Ta có thể dùng deque để biểu diễn stack. Khi đó ta có các thao tác tương ứng như sau:
Tương tự, ta có thể dùng deque để biểu diễn queue. Khi đó ta có các thao tác tương ứng như sau:
Do đặc tính truy xuất hai đầu của deque, việc xây dựng CTDL biểu diễn nó phải phù hợp. Ta có thể cài đặt CTDL deque bằng danh sách liên kết đơn. Tuy nhiên, khi đó thao tác RemoveLast hủy phần tử ở cuối deque sẽ tốn chi phí O(n). Ðiều này làm giảm hiệu quả của CTDL. Thích hợp nhất để cài đặt deque là dùng danh sách liên kết kép. Tất cả các thao tác trên deque khi đó sẽ chỉ tốn chi phí O(1).
Danh sách liên kết có thứ tự (gọi tắt là OList) là một vật chứa các đối tượng theo một trình tự nhất định. Trình tự này thường là một khóa sắp xếp nào đó. Việc thêm một đối tượng vào OList phải bảo đảm tôn trọng thứ tự này. Ta có thể cài đặt OList bằng DSLK đơn hoặc DSLK đôi với việc định nghĩa lại duy nhất một phép thêm phần tử: thêm bảo toàn thứ tự. Nghĩa là trên OList chỉ cho phép một thao tác thêm phần tử sao cho thứ tự định nghĩa trên OList phải bảo toàn. Ví dụ, khi cài đặt OList bằng xâu đơn, hàm thêm một phần tử có thể được xây dựng như sau: NODE* InsertNode(LIST & l, Data X) { Node* q = NULL, *p = l.pHead; if(IsEmpty(l)) return InsertHead(l, X); while(p) { if(p->Info >= X) break; q = p; p = q->pNext; } Node*pT = new(Node); pT->Info = X; pT->pNext= p; if(q) q->pNext = pT; else l.pHead = pT; if(q == l->pTail) l.pTail = pT; return pT; } Khi đó, hàm tìm kiếm một phần tử được viết lại như sau: NODE* SearchNode(LIST l, Data X) { Node*p = l.pHead; while(p) { if(p->Info == X) break; else if(p->Info > X) return NULL; p = p->pNext; } return p;} Ta có thể dùng OList để cài đặt CTDL hàng đợi có độ ưu tiên. Trong hàng đợi có độ ưu tiên, mỗi phần tử được gán cho một độ ưu tiên. Hàng đợi có độ ưu tiên cũng giống như hàng đợi bình thường ở thao tác lấy một phần tử khỏi hàng đợi (lấy ở đầu queue) nhưng khác ở thao tác thêm vào. Thay vì thêm vào ở cuối queue, việc thêm vào trong hàng đợi có độ ưu tiên phải bảo đảm phần tử có độ ưu tiên cao đứng trước, phần tử có độ ưu tiên thấp đứng sau. Hàng đợi có độ ưu tiên có nhiều ứng dụng. Ví dụ, CTDL này có thể dùng để quản lý hàng đợi các tiến trình chờ được xử lý trong các hệ điều hành đa nhiệm.
Danh sách liên kếtkép là danh sách mà mỗi phần tử trong danh sách có kết nối với 1 phần tử đứng trước và 1 phần tử đứng sau nó.
Các khai báo sau định nghiã một danh sách liên kết kép đơn giản trong đó ta dùng hai con trỏ: pPrev liên kết với phần tử đứng trước và pNext như thường lệ, liên kết với phần tử đứng sau: typedef struct tagDNode { Data Info; struct tagDNode* pPre; // trỏ đến phần tử đứng trước struct tagDNode* pNext; // trỏ đến phần tử đứng sau }DNODE; typedef struct tagDList { DNODE* pHead; // trỏ đến phần tử đầu danh sách DNODE* pTail; // trỏ đến phần tử cuối danh sách }DLIST; khi đó, thủ tục khởi tạo một phần tử cho danh sách liên kết kép được viết lại như sau : DNODE* GetNode(Data x) { DNODE *p; // Cấp phát vùng nhớ cho phần tử p = new DNODE; if ( p==NULL) { printf("Không đủ bộ nhớ"); exit(1); } // Gán thông tin cho phần tử p p ->Info = x; p->pPrev = NULL; p->pNext = NULL; return p; } Tương tự danh sách liên kết đơn, ta có thể xây dựng các thao tác cơ bản trên danh sách liên kết kép (xâu kép). Một số thao tác không khác gì trên xâu đơn. Dưới đây là một số thao tác đặc trưng của xâu kép:
Có 4 loại thao tác chèn new_ele vào danh sách:
Cài đặt : void AddFirst(DLIST &l, DNODE* new_ele) { if (l.pHead==NULL) //Xâu rỗng { l.pHead = new_ele; l.pTail = l.pHead; } else { new_ele->pNext = l.pHead; // (1) l.pHead ->pPrev = new_ele; // (2) l.pHead = new_ele; // (3) } } NODE* InsertHead(DLIST &l, Data x) { NODE* new_ele = GetNode(x); if (new_ele ==NULL) return NULL; if (l.pHead==NULL) { l.pHead = new_ele; l.pTail = l.pHead; } else { new_ele->pNext = l.pHead; // (1) l.pHead ->pPrev = new_ele; // (2) l.pHead = new_ele; // (3) } return new_ele; }
Cài đặt : void AddTail(DLIST &l, DNODE *new_ele) { if (l.pHead==NULL) { l.pHead = new_ele; l.pTail = l.pHead; } else { l.pTail->Next = new_ele; // (1) new_ele ->pPrev = l.pTail; // (2) l.pTail = new_ele; // (3) } } NODE* InsertTail(DLIST &l, Data x) { NODE* new_ele = GetNode(x); if (new_ele ==NULL) return NULL; if (l.pHead==NULL) { l.pHead = new_ele; l.pTail = l.pHead; } else { l.pTail->Next = new_ele; // (1) new_ele ->pPrev = l.pTail; // (2) l.pTail = new_ele; // (3) } return new_ele; }
Cài đặt : void AddAfter(DLIST &l, DNODE* q,DNODE* new_ele) { DNODE* p = q->pNext; if ( q!=NULL) { new_ele->pNext = p; //(1) new_ele->pPrev = q; //(2) q->pNext = new_ele; //(3) if(p != NULL) p->pPrev = new_ele; //(4) if(q == l.pTail) l.pTail = new_ele; } else //chèn vào đầu danh sách AddFirst(l, new_ele); } void InsertAfter(DLIST &l, DNODE *q, Data x) { DNODE* p = q->pNext; NODE* new_ele = GetNode(x); if (new_ele ==NULL) return NULL; if ( q!=NULL) { new_ele->pNext = p; //(1) new_ele->pPrev = q; //(2) q->pNext = new_ele; //(3) if(p != NULL) p->pPrev = new_ele; //(4) if(q == l.pTail) l.pTail = new_ele; } else //chèn vào đầu danh sách AddFirst(l, new_ele); }
Cài đặt : void AddBefore(DLIST &l, DNODE q, DNODE* new_ele) { DNODE* p = q->pPrev; if ( q!=NULL) { new_ele->pNext = q; //(1) new_ele->pPrev = p; //(2) q->pPrev = new_ele; //(3) if(p != NULL) p->pNext = new_ele; //(4) if(q == l.pHead) l.pHead = new_ele; } else //chèn vào đầu danh sách AddTail(l, new_ele); } void InsertBefore(DLIST &l, DNODE q, Data x) { DNODE* p = q->pPrev; NODE* new_ele = GetNode(x); if (new_ele ==NULL) return NULL; if ( q!=NULL) { new_ele->pNext = q; //(1) new_ele->pPrev = p; //(2) q->pPrev = new_ele; //(3) if(p != NULL) p->pNext = new_ele; //(4) if(q == l.pHead) l.pHead = new_ele; } else //chèn vào đầu danh sách AddTail(l, new_ele); }
Có 5 loại thao tác thông dụng hủy một phần tử ra khỏi xâu. Chúng ta sẽ lần lượt khảo sát chúng. Data RemoveHead(DLIST &l) { DNODE *p; Data x = NULLDATA; if ( l.pHead != NULL) { p = l.pHead; x = p->Info; l.pHead = l.pHead->pNext; l.pHead->pPrev = NULL; delete p; if(l.pHead == NULL) l.pTail = NULL; else l.pHead->pPrev = NULL; } return x; } Data RemoveTail(DLIST &l) { DNODE *p; Data x = NULLDATA; if ( l.pTail != NULL) { p = l.pTail; x = p->Info; l.pTail = l.pTail->pPrev; l.pTail->pNext = NULL; delete p; if(l.pHead == NULL) l.pTail = NULL; else l.pHead->pPrev = NULL; } return x; } Hủy một phần tử đứng sau phần tử q void RemoveAfter (DLIST &l, DNODE *q) { DNODE *p; if ( q != NULL) { p = q ->pNext ; if ( p != NULL) { q->pNext = p->pNext; if(p == l.pTail) l.pTail = q; else p->pNext->pPrev = q; delete p; } } else RemoveHead(l); } Hủy một phần tử đứng trước phần tử q void RemoveAfter (DLIST &l, DNODE *q) { DNODE *p; if ( q != NULL) { p = q ->pPrev; if ( p != NULL) { q->pPrev = p->pPrev; if(p == l.pHead) l.pHead = q; else p->pPrev->pNext = q; delete p; } } else RemoveTail(l); } Hủy 1 phần tử có khoá k int RemoveNode(DLIST &l, Data k) { DNODE *p = l.pHead; NODE *q; while( p != NULL) { if(p->Info == k) break; p = p->pNext; } if(p == NULL) return 0; //Không tìm thấy k q = p->pPrev; if ( q != NULL) { p = q ->pNext ; if ( p != NULL) { q->pNext = p->pNext; if(p == l.pTail) l.pTail = q; else p->pNext->pPrev = q; } } else //p là phần tử đầu xâu { l.pHead = p->pNext; if(l.pHead == NULL) l.pTail = NULL; else l.pHead->pPrev = NULL; } delete p; return 1; }
Xâu kép về mặt cơ bản có tính chất giống như xâu đơn. Tuy nhiên nó có một số tính chất khác xâu đơn như sau: Xâu kép có mối liên kết hai chiều nên từ một phần tử bất kỳ có thể truy xuất một phần tử bất kỳ khác. Trong khi trên xâu đơn ta chỉ có thể truy xuất đến các phần tử đứng sau một phần tử cho trước. Ðiều này dẫn đến việc ta có thể dễ dàng hủy phần tử cuối xâu kép, còn trên xâu đơn thao tác này tồn chi phí O(n). Bù lại, xâu kép tốn chi phí gấp đôi so với xâu đơn cho việc lưu trữ các mối liên kết. Ðiều này khiến việc cập nhật cũng nặng nề hơn trong một số trường hợp. Như vậy ta cần cân nhắc lựa chọn CTDL hợp lý khi cài đặt cho một ứng dụng cụ thể.
Danh sách liên kết vòng (xâu vòng) là một danh sách đơn (hoặc kép) mà phần tử cuối danh sách thay vì mang giá trị NULL, trỏ tới phần tử đầu danh sách. Ðể biểu diễn, ta có thể xử dụng các kỹ thuật biểu diễn như danh sách đơn (hoặc kép).
Ta có thể khai báo xâu vòng như khai báo xâu đơn (hoặc kép). Trên danh sách vòng ta có các thao tác thường gặp sau:
Danh sách vòng không có phần tử đầu danh sách rõ rệt, nhưng ta có thể đánh dấu một phần tử bất kỳ trên danh sách xem như phân tử đầu xâu để kiểm tra việc duyệt đã qua hết các phần tử của danh sách hay chưa. NODE* Search(LIST &l, Data x) { NODE *p; p = l.pHead; do { if ( p->Info == x) return p; p = p->pNext; }while (p != l.pHead); // chưa đi giáp vòng return p; } Thêm phần tử đầu xâu void AddHead(LIST &l, NODE *new_ele) { if(l.pHead == NULL) //Xâu rỗng { l.pHead = l.pTail = new_ele; l.pTail->pNext = l.pHead; } else { new_ele->pNext = l.pHead; l.pTail->pNext = new_ele; l.pHead = new_ele; } }
void AddTail(LIST &l, NODE *new_ele) { if(l.pHead == NULL) //Xâu rỗng { l.pHead = l.pTail = new_ele; l.pTail->pNext = l.pHead; } else { new_ele->pNext = l.pHead; l.pTail->pNext = new_ele; l.pTail = new_ele; } }
void AddAfter(LIST &l, NODE *q, NODE *new_ele) { if(l.pHead == NULL) //Xâu rỗng { l.pHead = l.pTail = new_ele; l.pTail->pNext = l.pHead; } else { new_ele->pNext = q->pNext; q->pNext = new_ele; if(q == l.pTail) l.pTail = new_ele; } }
void RemoveHead(LIST &l) { NODE *p = l.pHead; if(p == NULL) return; if (l.pHead = l.pTail) l.pHead = l.pTail = NULL; else { l.pHead = p->Next; if(p == l.pTail) l.pTail->pNext = l.pHead; } delete p; }
void RemoveAfter(LIST &l, NODE *q) { NODE *p; if(q != NULL) { p = q ->Next ; if ( p == q) l.pHead = l.pTail = NULL; else { q->Next = p->Next; if(p == l.pTail) l.pTail = q; } delete p; } }
Ðối với danh sách vòng, có thể xuất phát từ một phần tử bất kỳ để duyệt toàn bộ danh sách
Danh sách có nhiều mối liên kết là danh sách mà mỗi phần tử có nhiều khoá và chúng được liên kết với nhau theo từng loại khoá. Danh sách có nhiều mối liên kết thường được xử dụng trong các ứng dụng quản lý một cơ sở dữ liệu lớn với những nhu cầu tìm kiếm dữ liệu theo những khoá khác nhau. Ví du: Ðể quản lý danh mục điện thoại thuận tiện cho việc in danh mục theo những trình tự khác nhau : tên khách tăng dần, theo số điện thoại tăng dần, thời gian lắp đặt giảm dần, ta có thể tổ chức dữ liệu như hình trên: một danh sách vơí 3 mối liên kết:
một cho họ tên khách hàng, một cho số điện thoại và một cho thời gian lắp đặt. Các thao tác trên một danh sách nhiều mối liên kết được tiến hành tương tự như trên danh sách đơn nhưng được thực hiện làm nhiều lần và mỗi lần cho một liên kết.
Danh sách tổng quát là một danh sách mà mỗi phần tử của nó có thể lại là một danh sách khác. Các ví dụ sau minh hoạ các cấu trúc danh sách tổng quát. Các thao tác trên một danh sách được xây dựng dựa trên cơ sở các thao tác trên danh sách liên kết chúng ta đã khảo sát. Ví dụ 1: typedef struct tagNode { DATA Info; struct tagNode *pNext; void *Sublist; }NODE; typedef NODE *PNODE; Ví dụ 2: typedef struct tagNguoi { char Ten[35]; char GioiTinh; int NamSinh; struct tagNguoi *Cha, *Me; struct tagNguoi *Anh, *Chi, *Em; }NGUOI; typedef NGUOI *PNGUOI; |
