Bài tập danh sách liên kết đôi C++

Tóm Tắt

Danh sách liên kết kép

Trongbài trước về danh sách liên kết đơn đã đề cập, nó có điểm yếu là chỉ có liên kết tới node kế tiếp mà không có liên kết tới node đứng trước. Do vậy ta luôn phải duyệt toàn bộ danh sách từ node gốc để tìm kiếm dữ liệu tai một vị trí bất kì.

Một node trong danh sách liên kết kép được cấu thành từ ba thành phần là dữ liệu và phần kết nối tới node kế tiếp và node trước nó.

Prev: Là con trỏ tới node trước.

Next: Là con trỏ tới node kế tiếp.

Xây dựng danh sách liên kết kép bởi liên kết các node với nhau.

Việc chèn dữ liệu trong danh sách liên kết kép

Giả sử trước khi chèn dữ liệu ta có một node riêng biệt và một danh sách liên kết kép.

Trường hợp ta muốn chèn vào vị trí giữa danh sách liên kết ở trên sẽ được mô tả như sau:

So sánh với danh sách liên kết đơn

Ưu điểm:

Ta có thể duyệt danh sách theo cả hai chiều bởi vì danh sách liên kết kép có con trỏ prev để truy cập node trước và con trỏ next để truy cập node sau. Nên khi muốn tìm kiếm dữ liệu trong danh sách ta không nhất thiết phải duyệt từ đầu danh sách như với danh sách liên kết đơn.

Nhược điểm:

Vì con trỏ prev được thêm vào mỗi node, như vậy sẽ tốn thêm không gian bộ nhớ.
Cách thức hoạt động của danh sách liên kết kép cũng vì vậy mà phức tạp hơn.

Xây dựng danh sách liên kết kép với C/C++

Các thành phần của danh sách liên kết kép bao gồm:

Các node: Mỗi node bao gồm phần dữ liệu, một con trỏ prev để trỏ đến node ngay trước nó và một con trỏ next để trỏ tới node ngay tiếp sau nó.

struct node {
int data; /* Phần dữ liệu của một node */
struct node* next; /* Con trỏ tới node kế tiếp */
struct node* prev; /* Con trỏ tới node trước nó */
};

Con trỏ head để trỏ tới vị trí đầu tiên của danh sách liên kết.

struct node * head; /* Con trỏ tới head node */

Các thao tác chính với danh sách liên kết kép:

Tạo một node mới và trả về con trỏ tới node đó

/* Tạo một node mới và trả về con trỏ tới node đó. */
struct node* NewNode(int x) {
struct node* new_node
= (struct node*)malloc(sizeof(struct node)); /* Cấp phát bộ nhớ cho node */
new_node->data = x;
new_node->next = NULL;
new_node->prev = NULL;
return new_node;
}
Chèn một node vào cuối danh sách

/* Chèn node vào vị trí cuối của danh sách liên kết */
void InsertAtEnd(int x) {
struct node* temp = head; /* Tạo ra một con trỏ tạm, tránh trực tiếp làm thay đổi vị trí trỏ của con trỏ head */
struct node* new_node = NewNode(x); /* Tạo ra một node mới với phần */
/* dữ liệu là tham số được truyền vào */
/* hàm NewNode đã được viết ở trên */
if(head == NULL) { /* Nếu danh sách rỗng, con trỏ head sẽ trỏ tới node được chèn vào danh sách */
head = new_node;
return;
}
while(temp->next != NULL) temp = temp->next; /* Đi tới vị trí cuối cùng của danh sách */
temp->next = new_node; /* Chèn node mới vào cuối danh sách */
new_node->prev = temp; /* Ghi lại địa chỉ node trước của node vừa chèn vào */
}
Chèn một node vào đầu danh sách

/* Chèn node vào vị trí cuối của danh sách liên kết */
void InsertHead(int x) {
struct node* new_node = NewNode(x); /* Tạo ra một node mới với phần */
/* dữ liệu là tham số được truyền vào */
/* hàm NewNode đã được viết ở trên */
if(head == NULL) { /* Nếu danh sách rỗng, con trỏ head sẽ trỏ tới node được chèn vào danh sách */
head = new_node;
return;
}
head->prev = new_node ;
new_node >next = head;
head = new_node ; /* Head lúc này là new_node vì new_node được chèn vào đầu danh sách */
}
Xóa một phần tử khỏi danh sách liên kết kép

Trong phần này ta có thể tách ra làm hai hàm riêng biệt.

Hàm deleteNode :

Dùng để xóa một node ra khỏi danh sách với điều kiện là ta đã biết địa chỉ của node cần xóa.

Có ba trường hợp cho việc xóa node là: xóa node ở vị trí đầu của danh sách, xóa node ở vị trí cuối của danh sách và xóa node ở vị trí giữa của dah sách.

Với việc xóa node ở vị trí đầu, ta chỉ việc chuyển con trỏ head để trỏ vào vị trí kế tiếp của node đầu tiên và giải phóng bộ nhớ đã cấp cho node đầu tiên đó.

Để xóa node ở vị trí cuối cùng của danh sách ta duyệt đến vị trí của node đứng ngay trước node cuối cùng, sau đó gán cho con trỏ next của node đó trỏ tới NULL và giải phóng bộ nhớ đã cấp cho node cuối cùng.

Việc xóa node ở giữa danh sách phức tạp hơn một chút bao gồm các bước:

Chuyển con trỏ next của node đứng ngay trước node cần xóa tới vị trí của node ngay sau node cần xóa đó.
Chuyển con trỏ prev của node đứng ngay sau node cần xóa về vị trí của node ngay trước node cần xóa đó.
Giải phóng bộ nhớ đã cấp cho node vừa xóa.

Hàm delNodeAtPos:

Hàm này được dùng để xóa một node ở một vị trí đã cho trong danh sách.

nhiệm vụ của hàm này là tìm ra địa chỉ của node tại vị trí đã cho, sau đó truyền địa chỉ đó vào hàm deleteNode ở trên.

Các công việc còn lại sẽ do hàm deleteNode đảm nhiệm.

/* Hàm dùng để xóa một node khỏi Doubly Linked List.
head_ref : Con trỏ tới head node.
del : Con trỏ tới node cần xóa */
void deleteNode(struct node** head_ref, struct node* del)
{
/* Điều kiện cơ sở, thoát khỏi hàm nếu danh sách rỗng hoặc địa chỉ của node cần xóa là NULL (không xóa node nào) */
if (*head_ref == NULL || del == NULL)
return;
/* Nếu node cần xóa là head node */
if (*head_ref == del)
*head_ref = del->next;
/* Thay đổi node kế tiếp chỉ khi node cần xóa không phải node cuối cùng trong danh sách */
if (del->next != NULL)
del->next->prev = del->prev;
/* Thay đổi node trước chỉ khi node cần xóa không phải node đầu tiên trong danh sách */
if (del->prev != NULL)
del->prev->next = del->next;
/* Cuối cùng, giải phóng bộ nhớ đã được chiếm giữ bởi del*/
free(del);
}
/* Hàm để xóa một node ở một vị trí đã cho (int n) trong doubly linked list */
void delNodeAtPos(struct node** head_ref, int n)
{
/* Thoát khỏi hàm nếu danh sách là rỗng hoặc vị trí truyền vào là không đúng (vị trí âm) */
if (*head_ref == NULL || n <= 0)
return;
struct node* current = *head_ref;
int i;
/* Duyệt danh sách từ node đầu tiên cho tới khi gặp node ở vị trí đã cho */
for (int i = 1; current != NULL && i < n; i++)
current = current->next;
/* Nếu vị trí đã cho lớn hớn số node tối đa của danh sách, ta thoát khỏi hàm */
if (current == NULL)
return;
/* Thực hiện việc xóa node mà ta đã tìm thấy tại vị trí đã cho */
deleteNode(head_ref, current);
}

/* Hàm dùng để xóa một node khỏi Doubly Linked List. head_ref : Con trỏ tới head node. del : Con trỏ tới node cần xóa */ void deleteNode(struct node** head_ref, struct node* del) { /* Điều kiện cơ sở, thoát khỏi hàm nếu danh sách rỗng hoặc địa chỉ của node cần xóa là NULL (không xóa node nào) */ if (*head_ref == NULL || del == NULL) return; /* Nếu node cần xóa là head node */ if (*head_ref == del) *head_ref = del->next; /* Thay đổi node kế tiếp chỉ khi node cần xóa không phải node cuối cùng trong danh sách */ if (del->next != NULL) del->next->prev = del->prev; /* Thay đổi node trước chỉ khi node cần xóa không phải node đầu tiên trong danh sách */ if (del->prev != NULL) del->prev->next = del->next; /* Cuối cùng, giải phóng bộ nhớ đã được chiếm giữ bởi del*/ free(del); } /* Hàm để xóa một node ở một vị trí đã cho (int n) trong doubly linked list */ void delNodeAtPos(struct node** head_ref, int n) { /* Thoát khỏi hàm nếu danh sách là rỗng hoặc vị trí truyền vào là không đúng (vị trí âm) */ if (*head_ref == NULL || n <= 0) return; struct node* current = *head_ref; int i; /* Duyệt danh sách từ node đầu tiên cho tới khi gặp node ở vị trí đã cho */ for (int i = 1; current != NULL && i < n; i++) current = current->next; /* Nếu vị trí đã cho lớn hớn số node tối đa của danh sách, ta thoát khỏi hàm */ if (current == NULL) return; /* Thực hiện việc xóa node mà ta đã tìm thấy tại vị trí đã cho */ deleteNode(head_ref, current); }

Hiển thị tất cả các node trong danh sách.

void Display() {
/* Ta sẽ duyệt từ đầu danh sách, và qua mỗi node ta sẽ in giá trị của node đó ra */
struct node* temp = head;
while(temp != NULL) {
printf(“%d “,temp->data);
temp = temp->next;
}
printf(“\n”);
}

Ứng dụng của danh sách liên kết kép trong thực tế

Ta có thể ứng dụng danh sách liên kết kép trong khá nhiều trường hợp, ví dụ:

Trong một phần mềm chơi nhạc có nút next và prev.
Trong bộ đệm của trình duyệt web cho bạn quay trở lại trang trước hoặc tới trang kế tiếp.
Các phần mềm sử dụng tính năng undo và redo ( MS word, các IDE).

Danh sách liên kết kép

Việc chèn dữ liệu trong danh sách liên kết kép

So sánh với danh sách liên kết đơn

Xây dựng danh sách liên kết kép với C/C++

Các thao tác chính với danh sách liên kết kép:

Tạo một node mới và trả về con trỏ tới node đó

Chèn một node vào cuối danh sách

Chèn một node vào đầu danh sách

Xóa một phần tử khỏi danh sách liên kết kép

Ứng dụng của danh sách liên kết kép trong thực tế

mtoplist