Giải thuật và lập trình - C: IV. Danh sách liên kết kép (DOUBLE - LISTS)
Giải phóng thời gian, khai phóng năng lực
IV. DANH SÁCH LIÊN KẾT KÉP (DOUBLE - LISTS)
Một số ứng dụng đòi hỏi chúng ta phải duyệt danh sách theo cả hai chiều một cách hiệu quả. Chẳng hạn cho phần tử X cần biết ngay phần tử trước X và sau X một cách mau chóng. Trong trường hợp này ta phải dùng hai con trỏ, một con trỏ chỉ đến phần tử đứng sau (next), một con trỏ chỉ đến phần tử đứng trước (previous). Với cách tổ chức này ta có một danh sách liên kết kép. Dạng của một danh sách liên kép như sau:
Hình II.15 Hình ảnh một danh sách liên kết kép
Các khai báo cần thiết
typedef ... ElementType;
//kiểu nội dung của các phần tử trong danh sách
typedef struct Node{
ElementType Element; //lưu trữ nội dung phần tử
//Hai con trỏ trỏ tới phần tử trước và sau
Node* Prev;
Node* Next;
};
typedef Node* Position;
typedef Position DoubleList;
Để quản lí một danh sách liên kết kép ta có thể dùng một con trỏ trỏ đến một ô bất kỳ trong cấu trúc. Hoàn toàn tương tự như trong danh sách liên kết đơn đã trình bày trong phần trước, con trỏ để quản lí danh sách liên kết kép có thể là một con trỏ có kiểu giống như kiểu phần tử trong danh sách và nó có thể được cấp phát ô nhớ (tương tự như Header trong danh sách liên kết đơn) hoặc không được cấp phát ô nhớ. Ta cũng có thể xem danh sách liên kết kép như là danh sách liên kết đơn, với một bổ sung duy nhất là có con trỏ previous để nối kết các ô theo chiều ngược lại. Theo quan điểm này thì chúng ta có thể cài đặt các phép toán thêm (insert), xoá (delete) một phần tử hoàn toàn tương tự như trong danh sách liên kết đơn và con trỏ Header cũng cần thiết như trong danh sách liên kết đơn, vì nó chính là vị trí của phần tử đầu tiên trong danh sách.
Tuy nhiên, nếu tận dụng khả năng duyệt theo cả hai chiều thì ta không cần phải cấp phát bộ nhớ cho Header và vị trí (position) của một phần tử trong danh sách có thể định nghĩa như sau: Vị trí của phần tử ai là con trỏ trỏ tới ô chứa ai, tức là địa chỉ ô nhớ chứa ai. Nói nôm na, vị trí của ai là ô chứa ai. Theo định nghĩa vị trí như vậy các phép toán trên danh sách liên kết kép sẽ được cài đặt hơi khác với danh sách liên đơn. Trong cách cài đặt này, chúng ta không sử dụng ô đầu mục như danh sách liên kết đơn mà sẽ quản lý danh sách một các trực tiếp (header chỉ ngay đến ô đầu tiên trong danh sách).
Tạo danh sách liên kết kép rỗng
Giả sử DL là con trỏ quản lí danh sách liên kết kép thì khi khởi tạo danh sách rỗng ta cho con trỏ này trỏ NULL (không cấp phát ô nhớ cho DL), tức là gán DL=NULL.
void MakeNull_List (DoubleList *DL){
(*DL)= NULL;
}
Kiểm tra danh sách liên kết kép rỗng
Rõ ràng, danh sách liên kết kép rỗng khi và chỉ khi chỉ điểm đầu danh sách không trỏ tới một ô xác định nào cả. Do đó ta sẽ kiểm tra DL = NULL.
int Empty (DoubleList DL){
return (DL==NULL);
}
Xóa một phần tử ra khỏi danh sách liên kết kép
Để xoá một phần tử tại vị trí p trong danh sách liên kết kép được trỏ bởi DL, ta phải chú ý đến các trường hợp sau:
- Danh sách rỗng, tức là DL=NULL: chương trình con dừng.
- Trường hợp danh sách khác rỗng, tức là DL!=NULL, ta phải phân biệt hai trường hợp
Ô bị xoá không phải là ô được trỏ bởi DL, ta chỉ cần cập nhật lại các con trỏ để nối kết ô trước p với ô sau p, các thao tác cần thiết là (xem hình II.16):
Nếu (p->previous!=NULL) thì p->previous->next=p->next;
Nếu (p->next!=NULL) thì p->next->previous=p->previous;
Xoá ô đang được trỏ bởi DL, tức là p=DL: ngoài việc cập nhật lại các con trỏ để nối kết các ô trước và sau p ta còn phải cập nhật lại DL, ta có thể cho DL trỏ đến phần tử trước nó (DL = p->Previous) hoặc đến phần tử sau nó (DL = p->Next) tuỳ theo phần tử nào có mặt trong danh sách. Đặc biệt, nếu danh sách chỉ có một phần tử tức là p->Next=NULL và p->Previous=NULL thì DL=NULL.
p->Previous p p->Next
Hình II.16 Xóa phần tử tại vị trí p
void Delete_List (Position p, DoubleList *DL){
if (*DL == NULL) printf(”Danh sach rong”);
else{
if (p==*DL) (*DL)=(*DL)->Next;
//Xóa phần tử đầu tiên của danh sách nên phải thay đổi DL
else p->Previous->Next=p->Next;
if (p->Next!=NULL)
p->Next->Previous=p->Previous; free(p);
}
}
Thêm phần tử vào danh sách liên kết kép
Để thêm một phần tử x vào vị trí p trong danh sách liên kết kép được trỏ bởi DL, ta cũng cần phân biệt mấy trường hợp sau:
Danh sách rỗng, tức là DL = NULL: trong trường hợp này ta không quan tâm đến giá trị của p. Để thêm một phần tử, ta chỉ cần cấp phát ô nhớ cho nó, gán giá trị x vào trường Element của ô nhớ này và cho hai con trỏ previous, next trỏ tới NULL còn DL trỏ vào ô nhớ này, các thao tác trên có thể viết như sau:
DL=(Node*)malloc(sizeof(Node));
DL->Element = x;
DL->Previous=NULL;
DL->Next =NULL;
Nếu DL!=NULL, sau khi thêm phần tử x vào vị trí p ta có kết quả như hình II.18:
Hình II.17: Danh sách trước khi thêm phần tử x
Hình II.18: Danh sách sau khi thêm phần tử x vào tại vị trí p
(phần tử tại vị trí p cũ trở thành phần tử "sau" của x).
Lưu ý: các kí hiệu p, p->Next, p->Previous trong hình II.18 để chỉ các ô trước khi thêm phần tử x, tức là nó chỉ các ô trong hình II.17.
Trong trường hợp p=DL, ta có thể cập nhật lại DL để DL trỏ tới ô mới thêm vào hoặc để nó trỏ đến ô tại vị trí p cũ như nó đang trỏ cũng chỉ là sự lựa chọn trong chi tiết cài đặt.
void Insert_List (ElementType X,Position p, DoubleList *DL){
if (*DL == NULL){
(*DL)=(Node*)malloc(sizeof(Node));
(*DL)->Element = X;
(*DL)->Previous =NULL;
(*DL)->Next =NULL;
}
else{
Position temp;
temp=(Node*)malloc(sizeof(Node));
temp->Element=X;
temp->Next=p;
temp->Previous=p->Previous;
if (p->Previous!=NULL)
p->Previous->Next=temp;
p->Previous=temp;
}
}
TỔNG KẾT CHƯƠNG
Chương mô tả các cấu trúc dữ liệu trừu tượng và các giải thuật cài đặt các phép toán này. Tuy nhiên, tùy theo bài toán cụ thể và mức độ thay đổi của dữ liệu cũng mà ta lựa chọn các cấu trúc dữ liệu cho phù hợp. Trong chương này, phần cơ bản nhất là danh sách đặc và liên kết, còn các cấu trúc khác chỉ là sự biến tấu của cấu trúc này. Trong chương này cũng đề cập đến các ứng dụng cụ thể của từng cấu trúc dữ liệu trừu tượng bên ngoài thực tế. Cách cài đặt các cấu trúc dữ liệu trừu tượng khác nhau và có vận dụng cấu trúc đã có để mô tả cho một cấu trúc dữ liệu trừu tượng mới.
Giải phóng thời gian, khai phóng năng lực