Trong cấu trúc dữ liệu, Danh sách liên kết (Linked List) là tập hợp tuyến tính các phần tử dữ liệu. Mỗi phần tử hoặc nút của danh sách bao gồm hai mục - dữ liệu và tham chiếu đến nút tiếp theo. Nút cuối cùng có tham chiếu đến null. Trong danh sách liên kết, điểm vào được gọi là đầu (head) của danh sách.
Trong Danh sách liên kết kép vòng (Circular Doubly Linked List), hai phần tử liên tiếp được liên kết bởi con trỏ previous và next, và nút cuối cùng trỏ đến nút đầu tiên bằng con trỏ next, nút đầu tiên cũng trỏ đến nút cuối cùng bằng con trỏ previous.
Thuật toán
Bắt đầu
Tạo lớp circulardoublylist với các hàm sau:
nod *create_node(int) = Cấp phát bộ nhớ cho nút động.
insert_begin() = Chèn phần tử ở đầu danh sách.
A) Nếu danh sách rỗng, chèn nút và đặt next/previous là NULL.
B) Nếu không rỗng, chèn dữ liệu và đặt/cập nhật next/previous.
insert_end() = Chèn phần tử ở cuối danh sách:
A) Nếu rỗng, tạo nút như circular doubly list.
B) Tìm nút cuối.
C) Tạo nút động.
D) Start sẽ là next của nút mới.
E) Làm nút mới thành previous node.
F) Làm last thành previous của nút mới.
G) Làm nút mới thành next của last cũ.
insert_pos() = Chèn phần tử tại vị trí chỉ định:
A) Chèn dữ liệu.
B) Nhập vị trí cần chèn.
C) Nếu rỗng, chèn nút ở đầu.
D) Nếu không rỗng, tìm nút có vị trí và nút tiếp theo.
E) Chèn nút giữa chúng.
delete_pos() = Xóa phần tử từ vị trí chỉ định:
A) Nếu rỗng, trả về.
B) Nhập vị trí nút cần xóa.
C) Nếu có một nút, xóa và cập nhật next/prev.
D) Nếu nhiều hơn một nút, xóa nút tại vị trí đó và cập nhật next/prev.
search() = Tìm kiếm phần tử trong danh sách:
A) Nếu rỗng, trả về.
B) Nhập giá trị cần tìm.
C) In vị trí tìm thấy.
D) Nếu không tìm thấy, in không tìm thấy.
update() = Cập nhật giá trị tại nút cụ thể:
A) Nếu rỗng, trả về.
B) Nhập vị trí nút cần cập nhật.
C) Nhập giá trị mới.
D) Cập nhật nút.
display() = Hiển thị danh sách.
reverse() = Đảo ngược danh sách.
Kết thúc
Mã ví dụ
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
struct nod {
int info;
struct nod *n;
struct nod *p;
}*start, *last;
int count = 0;
class circulardoublylist {
public:
nod *create_node(int);
void insert_begin();
void insert_end();
void insert_pos();
void delete_pos();
void search();
void update();
void display();
void reverse();
circulardoublylist() {
start = NULL;
last = NULL;
}
};
int main() {
int c;
circulardoublylist cdl;
while (1) {
cout << "1. Chèn ở đầu" << endl;
cout << "2. Chèn ở cuối" << endl;
cout << "3. Chèn tại vị trí" << endl;
cout << "4. Xóa tại vị trí" << endl;
cout << "5. Cập nhật nút" << endl;
cout << "6. Tìm kiếm phần tử" << endl;
cout << "7. Hiển thị danh sách" << endl;
cout << "8. Đảo ngược danh sách" << endl;
cout << "9. Thoát" << endl;
cout << "Nhập lựa chọn: ";
cin >> c;
switch(c) {
case 1:
cdl.insert_begin();
break;
case 2:
cdl.insert_end();
break;
case 3:
cdl.insert_pos();
break;
case 4:
cdl.delete_pos();
break;
case 5:
cdl.update();
break;
case 6:
cdl.search();
break;
case 7:
cdl.display();
break;
case 8:
cdl.reverse();
break;
case 9:
exit(1);
default:
cout << "Lựa chọn sai" << endl;
}
}
return 0;
}
nod* circulardoublylist::create_node(int v) {
count++;
struct nod *t;
t = new(struct nod);
t->info = v;
t->n = NULL;
t->p = NULL;
return t;
}
void circulardoublylist::insert_begin() {
int v;
cout << endl << "Nhập phần tử cần chèn: ";
cin >> v;
struct nod *t;
t = create_node(v);
if (start == last && start == NULL) {
cout << "Phần tử chèn vào danh sách rỗng" << endl;
start = last = t;
start->n = last->n = NULL;
start->p = last->p = NULL;
} else {
t->n = start;
start->p = t;
start = t;
start->p = last;
last->n = start;
cout << "Phần tử đã chèn" << endl;
}
}
void circulardoublylist::insert_end() {
int v;
cout << endl << "Nhập phần tử cần chèn: ";
cin >> v;
struct nod *t;
t = create_node(v);
if (start == last && start == NULL) {
cout << "Phần tử chèn vào danh sách rỗng" << endl;
start = last = t;
start->n = last->n = NULL;
start->p = last->p = NULL;
} else {
last->n = t;
t->p = last;
last = t;
start->p = last;
last->n = start;
}
}
void circulardoublylist::insert_pos() {
int v, pos, i;
cout << endl << "Nhập phần tử cần chèn: ";
cin >> v;
cout << endl << "Nhập vị trí chèn: ";
cin >> pos;
struct nod *t, *s, *ptr;
t = create_node(v);
if (start == last && start == NULL) {
if (pos == 1) {
start = last = t;
start->n = last->n = NULL;
start->p = last->p = NULL;
} else {
cout << "Vị trí ngoài phạm vi" << endl;
count--;
return;
}
} else {
if (count < pos) {
cout << "Vị trí ngoài phạm vi" << endl;
count--;
return;
}
s = start;
for (i = 1; i <= count; i++) {
ptr = s;
s = s->n;
if (i == pos - 1) {
ptr->n = t;
t->p = ptr;
t->n = s;
s->p = t;
cout << "Phần tử đã chèn" << endl;
break;
}
}
}
}
void circulardoublylist::delete_pos() {
int pos, i;
nod *ptr, *s;
if (start == last && start == NULL) {
cout << "Danh sách rỗng, không có gì để xóa" << endl;
return;
}
cout << endl << "Nhập vị trí phần tử cần xóa: ";
cin >> pos;
if (count < pos) {
cout << "Vị trí ngoài phạm vi" << endl;
return;
}
s = start;
if(pos == 1) {
count--;
last->n = s->n;
s->n->p = last;
start = s->n;
free(s);
cout << "Phần tử đã xóa" << endl;
return;
}
for (i = 0; i < pos - 1; i++) {
s = s->n;
ptr = s->p;
}
ptr->n = s->n;
s->n->p = ptr;
if (pos == count) {
last = ptr;
}
count--;
free(s);
cout << "Phần tử đã xóa" << endl;
}
void circulardoublylist::update() {
int v, i, pos;
if (start == last && start == NULL) {
cout << "Danh sách rỗng, không có gì để cập nhật" << endl;
return;
}
cout << endl << "Nhập vị trí nút cần cập nhật: ";
cin >> pos;
cout << "Nhập giá trị mới: ";
cin >> v;
struct nod *s;
if (count < pos) {
cout << "Vị trí ngoài phạm vi" << endl;
return;
}
s = start;
if (pos == 1) {
s->info = v;
cout << "Nút đã cập nhật" << endl;
return;
}
for (i = 0; i < pos - 1; i++) {
s = s->n;
}
s->info = v;
cout << "Nút đã cập nhật" << endl;
}
void circulardoublylist::search() {
int pos = 0, v, i;
bool flag = false;
struct nod *s;
if (start == last && start == NULL) {
cout << "Danh sách rỗng, không có gì để tìm kiếm" << endl;
return;
}
cout << endl << "Nhập giá trị cần tìm: ";
cin >> v;
s = start;
for (i = 0; i < count; i++) {
pos++;
if (s->info == v) {
cout << "Phần tử " << v << " tìm thấy tại vị trí: " << pos << endl;
flag = true;
}
s = s->n;
}
if (!flag)
cout << "Phần tử không tìm thấy trong danh sách" << endl;
}
void circulardoublylist::display() {
int i;
struct nod *s;
if (start == last && start == NULL) {
cout << "Danh sách rỗng, không có gì để hiển thị" << endl;
return;
}
s = start;
for (i = 0; i < count-1; i++) {
cout << s->info << "<->";
s = s->n;
}
cout << s->info << endl;
}
void circulardoublylist::reverse() {
if (start == last && start == NULL) {
cout << "Danh sách rỗng, không có gì để đảo ngược" << endl;
return;
}
struct nod *p1, *p2;
p1 = start;
p2 = p1->n;
p1->n = NULL;
p1->p = p2;
while (p2 != start) {
p2->p = p2->n;
p2->n = p1;
p1 = p2;
p2 = p2->p;
}
last = start;
start = p1;
cout << "Danh sách đã đảo ngược" << endl;
}
Kết quả đầu ra
1. Chèn ở đầu 2. Chèn ở cuối 3. Chèn tại vị trí 4. Xóa tại vị trí 5. Cập nhật nút 6. Tìm kiếm phần tử 7. Hiển thị danh sách 8. Đảo ngược danh sách 9. Thoát Nhập lựa chọn: 1 Nhập phần tử cần chèn: 7 Phần tử chèn vào danh sách rỗng 1. Chèn ở đầu 2. Chèn ở cuối 3. Chèn tại vị trí 4. Xóa tại vị trí 5. Cập nhật nút 6. Tìm kiếm phần tử 7. Hiển thị danh sách 8. Đảo ngược danh sách 9. Thoát Nhập lựa chọn: 1 Nhập phần tử cần chèn: 6 Phần tử đã chèn 1. Chèn ở đầu 2. Chèn ở cuối 3. Chèn tại vị trí 4. Xóa tại vị trí 5. Cập nhật nút 6. Tìm kiếm phần tử 7. Hiển thị danh sách 8. Đảo ngược danh sách 9. Thoát Nhập lựa chọn: 2 Nhập phần tử cần chèn: 4 1. Chèn ở đầu 2. Chèn ở cuối 3. Chèn tại vị trí 4. Xóa tại vị trí 5. Cập nhật nút 6. Tìm kiếm phần tử 7. Hiển thị danh sách 8. Đảo ngược danh sách 9. Thoát Nhập lựa chọn: 2 Nhập phần tử cần chèn: 5 1. Chèn ở đầu 2. Chèn ở cuối 3. Chèn tại vị trí 4. Xóa tại vị trí 5. Cập nhật nút 6. Tìm kiếm phần tử 7. Hiển thị danh sách 8. Đảo ngược danh sách 9. Thoát Nhập lựa chọn: 7 6<->7<->4<->5 1. Chèn ở đầu 2. Chèn ở cuối 3. Chèn tại vị trí 4. Xóa tại vị trí 5. Cập nhật nút 6. Tìm kiếm phần tử 7. Hiển thị danh sách 8. Đảo ngược danh sách 9. Thoát Nhập lựa chọn: 6 Nhập giá trị cần tìm: 7 Phần tử 7 tìm thấy tại vị trí: 2 1. Chèn ở đầu 2. Chèn ở cuối 3. Chèn tại vị trí 4. Xóa tại vị trí 5. Cập nhật nút 6. Tìm kiếm phần tử 7. Hiển thị danh sách 8. Đảo ngược danh sách 9. Thoát Nhập lựa chọn: 6 Nhập giá trị cần tìm: 2 Phần tử không tìm thấy trong danh sách 1. Chèn ở đầu 2. Chèn ở cuối 3. Chèn tại vị trí 4. Xóa tại vị trí 5. Cập nhật nút 6. Tìm kiếm phần tử 7. Hiển thị danh sách 8. Đảo ngược danh sách 9. Thoát Nhập lựa chọn: 4 Nhập vị trí phần tử cần xóa: 4 Phần tử đã xóa 1. Chèn ở đầu 2. Chèn ở cuối 3. Chèn tại vị trí 4. Xóa tại vị trí 5. Cập nhật nút 6. Tìm kiếm phần tử 7. Hiển thị danh sách 8. Đảo ngược danh sách 9. Thoát Nhập lựa chọn: 3 Nhập phần tử cần chèn: 5 Nhập vị trí chèn: 2 Phần tử đã chèn 1. Chèn ở đầu 2. Chèn ở cuối 3. Chèn tại vị trí 4. Xóa tại vị trí 5. Cập nhật nút 6. Tìm kiếm phần tử 7. Hiển thị danh sách 8. Đảo ngược danh sách 9. Thoát Nhập lựa chọn: 7 6<->5<->7<->4 1. Chèn ở đầu 2. Chèn ở cuối 3. Chèn tại vị trí 4. Xóa tại vị trí 5. Cập nhật nút 6. Tìm kiếm phần tử 7. Hiển thị danh sách 8. Đảo ngược danh sách 9. Thoát Nhập lựa chọn: 8 Danh sách đã đảo ngược 1. Chèn ở đầu 2. Chèn ở cuối 3. Chèn tại vị trí 4. Xóa tại vị trí 5. Cập nhật nút 6. Tìm kiếm phần tử 7. Hiển thị danh sách 8. Đảo ngược danh sách 9. Thoát Nhập lựa chọn: 7 4<->7<->5<->6 1. Chèn ở đầu 2. Chèn ở cuối 3. Chèn tại vị trí 4. Xóa tại vị trí 5. Cập nhật nút 6. Tìm kiếm phần tử 7. Hiển thị danh sách 8. Đảo ngược danh sách 9. Thoát Nhập lựa chọn: 9