Bạn đã biết gì về danh sách liên kết đơn (Linked List) trong C++? Nó có đặc điểm gì? Cài đặt linked list C ++ cũng như những bài tập liên quan như thế nào. Hãy cùng Techacademy tìm hiểu trong bài viết này nhé!
I. Linked List C++ Là Gì
Một Danh sách liên kết (Linked List) là 1 dãy các cấu trúc dữ liệu được kết nối với nhau thông qua các liên kết (link). Hiểu một cách đơn thuần thì Danh sách liên kết là một cấu trúc dữ liệu bao gồm 1 nhóm những nút (node) tạo thành 1 chuỗi. Mỗi nút gồm dữ liệu ở nút ấy và tham chiếu đến nút kế tiếp trong chuỗi.
Danh sách liên kết là cấu trúc dữ liệu được sử dụng rộng rãi thứ hai sau mảng. Dưới đây là những định nghĩa cơ bản liên quan tới Danh sách liên kết:
Link (liên kết): mỗi link của một Danh sách liên kết có thể lưu giữ một dữ liệu được gọi là một phần tử.
Next: Mỗi liên kết của một Danh sách liên kết chứa một link tới next link được gọi là Next.
First: một Danh sách liên kết bao gồm các link kết nối tới first link được gọi là First.
II. Đặc Điểm Của Danh Sách Liên Kết Đơn
Do danh sách liên kết đơn là một cấu trúc dữ liệu động, được tạo nên nhờ việc cấp phát động nên nó mang một số đặc điểm sau đây:
- Được cấp phát bộ nhớ khi chạy chương trình
- Có thể đổi thay kích thước qua việc thêm, xóa phần tử
- Kích thước tối đa phụ thuộc vào bộ nhớ khả dụng của RAM
- Các phần tử được lưu trữ tự nhiên (không liên tiếp) trong RAM
Và do tính liên kết của phần tử đầu và phần tử đứng sau nó trong danh sách liên kết đơn, nó có những đặc điểm sau:
- Chỉ cần nắm được phần tử đầu và cuối là có thể quản lý được danh sách
- Truy cập tới phần tử ngẫu nhiên phải duyệt từ đầu tới vị trí đó
- Chỉ có thể tìm kiếm tuyến tính một phần tử
III. Cài Đặt Linked List C++
+ Khai báo linked list
Để đơn giản hóa, data của chúng ta sẽ là số nguyên(int). Bạn cũng có thể sử dụng các kiểu nguyên thủy khác(float, char,…) hay kiểu dữ liệu struct(SinhVien, CanBo,…) tự tạo.
struct LinkedList{
int data;
struct LinkedList *next;
};
Khai báo trên sẽ được sử dụng cho đa số Node trong linked list. Trường data sẽ lưu giữa giá trị và next sẽ là con trỏ để trỏ tới thằng kế tiếp của nó.
Tại sao next lại là kiểu LinkedList của chính nó? Bởi vì nó là con trỏ trỏ của chính bản thân nó, và nó trỏ tới một thằng Node kế tiếp cũng có kiểu LinkedList.
+ Tạo mới 1 Node
Hãy tạo 1 kiểu dữ liệu của struct LinkedList để code clear hơn:
typedef struct LinkedList *node; //Từ giờ dùng kiểu dữ liệu LinkedList có thể thay bằng node cho ngắn gọn
node CreateNode(int value){
node temp; // declare a node
temp = (node)malloc(sizeof(struct LinkedList)); // Cấp phát vùng nhớ dùng malloc()
temp->next = NULL;// Cho next trỏ tới NULL
temp->data = value; // Gán giá trị cho Node
return temp;//Trả về node mới đã có giá trị
}
Mỗi một Node lúc được khởi tạo, chúng ta cần cấp phát bộ nhớ cho nó, và mặc định cho con trỏ next trỏ tới NULL. Giá trị của Node sẽ được cung cấp khi thêm Node vào linked list.
- typedef được dùng để định nghĩa một kiểu dữ liệu trong C. VD: typeder long long LL;
- malloc là hàm cấp phát bộ nhớ của C. Với C++ chúng ta dùng new
- sizeof là hàm trả về kích thước của kiểu dữ liệu, dùng làm tham số cho hàm malloc
Lưu ý: Không giống với mảng, cần khai báo arr[size]. Trong linked list, vì mỗi Node sẽ có con trỏ liên kết đến Node tiếp theo. Do đó, với danh sách liên kết đơn, bạn chỉ cần lưu giữ Node đầu tiên(HEAD). Có head rồi bạn có thể đi tới bất cứ Node nào.
+ Thêm Node vào danh sách liên kết
Thêm vào đầu
Việc thêm vào đầu chính là việc cập nhật lại thằng head. Ta gọi Node mới(temp), ta có:
– Nếu head đang trỏ tới NULL, nghĩa là linked list đang trống, Node mới thêm vào sẽ làm head luôn
– Ngược lại, ta bắt buộc thay thế thằng head cũ bằng head mới. Việc này phải làm theo thứ tự như sau:
- Cho next của temp trỏ tới head hiện hành
- Đặt temp làm head mới
node AddHead(node head, int value){
node temp = CreateNode(value); // Khởi tạo node temp với data = value
if(head == NULL){
head = temp; // //Nếu linked list đang trống thì Node temp là head luôn
}else{
temp->next = head; // Trỏ next của temp = head hiện tại
head = temp; // Đổi head hiện tại = temp(Vì temp bây giờ là head mới mà)
}
return head;
}
Thêm vào cuối
Chúng ta sẽ cần Node đầu tiên, và giá trị muốn thêm. Khi đó, ta sẽ:
- Tạo một Node mới với giá trị value
- Nếu head = NULL, tức là danh sách liên kết đang trống. Khi đó Node mới(temp) sẽ là head luôn.
- Ngược lại, ta sẽ duyệt tới Node cuối cùng(Node có next = NULL), và trỏ next của thằng cuối tới Node mới(temp).
node AddTail(node head, int value){
node temp,p;// Khai báo 2 node tạm temp và p
temp = CreateNode(value);//Gọi hàm createNode để khởi tạo node temp có next trỏ tới NULL và giá trị là value
if(head == NULL){
head = temp; //Nếu linked list đang trống thì Node temp là head luôn
}
else{
p = head;// Khởi tạo p trỏ tới head
while(p->next != NULL){
p = p->next;//Duyệt danh sách liên kết đến cuối. Node cuối là node có next = NULL
}
p->next = temp;//Gán next của thằng cuối = temp. Khi đó temp sẽ là thằng cuối(temp->next = NULL mà)
}
return head;
}
Tổng quan hơn, chúng ta sẽ sẽ viết hàm thêm một Node vào vị trí bất kỳ nhé.
Thêm vào vị trí bất kỳ
Để làm được việc này, ta cần duyệt từ đầu để tìm tới vị trí của Node cần chèn, giả sử là Node Q, lúc đó ta cần làm theo thứ tự sau:
- Cho next của Node mới trỏ tới Node mà Q đang trỏ tới
- Cho Node Q trỏ tới Node mới
Lưu ý: Chỉ số chèn bắt đầu từ chỉ số 0 nhé các bạn
node AddAt(node head, int value, int position){
if(position == 0 || head == NULL){
head = AddHead(head, value); // Nếu vị trí chèn là 0, tức là thêm vào đầu
}else{
// Bắt đầu tìm vị trí cần chèn. Ta sẽ dùng k để đếm cho vị trí
int k = 1;
node p = head;
while(p != NULL && k != position){
p = p->next;
++k;
}
if(k != position){
// Nếu duyệt hết danh sách lk rồi mà vẫn chưa đến vị trí cần chèn, ta sẽ mặc định chèn cuối
// Nếu bạn không muốn chèn, hãy thông báo vị trí chèn không hợp lệ
head = AddTail(head, value);
// printf("Vi tri chen vuot qua vi tri cuoi cung!\n");
}else{
node temp = CreateNode(value);
temp->next = p->next;
p->next = temp;
}
}
return head;
}
Lưu ý: Bạn phải làm theo thứ tự trên, nếu bạn cho p->next = temp trước. Khi đó, bạn sẽ không thể lấy lại phần sau của danh sách liên kết nữa(Vì next chỉ được được lưu trong p->next mà thay đổi p->next rồi thì còn đâu giá trị cũ).
+ Xóa Node khỏi danh sách liên kết
Xóa đầu
Xóa đầu đơn giản lắm, bây giờ chỉ cần cho thằng kế tiếp của head làm head là được thôi. Mà thằng kế tiếp của head chính là head->next.
node DelHead(node head){
if(head == NULL){
printf("\nCha co gi de xoa het!");
}else{
head = head->next;
}
return head;
}
Xóa cuối
Xóa cuối mới nhọc nè, nhọc ở chỗ phải duyệt đến thằng cuối – 1, cho next của cuối – 1 đó bằng NULL.
node DelTail(node head){
if (head == NULL || head->next == NULL){
return DelHead(head);
}
node p = head;
while(p->next->next != NULL){
p = p->next;
}
p->next = p->next->next; // Cho next bằng NULL
// Hoặc viết p->next = NULL cũng được
return head;
}
Thằng Node cuối – 1 là thằng có p->next->next = NULL. Bạn cho next của nó bằng NULL là xong.
Xóa ở vị trí bất kỳ
Việc xóa ở vị trí bất kỳ cũng khá giống xóa ở cuối kia. Đơn giản là chúng ta bỏ qua một phần tử, như ảnh sau:
Lưu ý: Chỉ số xóa bắt đầu từ 0 nhé các bạn. Việc tìm vị trí càn xóa chỉ duyệt tới Node gần cuối thôi(cuối – 1). Sau đây là code xóa Node ở vị trí bất kỳ
node DelAt(node head, int position){
if(position == 0 || head == NULL || head->next == NULL){
head = DelHead(head); // Nếu vị trí chèn là 0, tức là thêm vào đầu
}else{
// Bắt đầu tìm vị trí cần chèn. Ta sẽ dùng k để đếm cho vị trí
int k = 1;
node p = head;
while(p->next->next != NULL && k != position){
p = p->next;
++k;
}
if(k != position){
// Nếu duyệt hết danh sách lk rồi mà vẫn chưa đến vị trí cần chèn, ta sẽ mặc định xóa cuối
// Nếu bạn không muốn xóa, hãy thông báo vị trí xóa không hợp lệ
head = DelTail(head);
// printf("Vi tri xoa vuot qua vi tri cuoi cung!\n");
}else{
p->next = p->next->next;
}
}
return head;
}
+ Lấy giá trị ở vị trí bất kỳ
Chúng ta sẽ viết một hàm để truy xuất giá trị ở chỉ số bất kỳ nhé. Trong trường hợp chỉ số vượt quá chiều dài của linked list – 1, hàm này trả về vị trí cuối cùng. Do hạn chế là chúng ta không thể raise error khi chỉ số không hợp lệ. Tôi mặc định chỉ số bạn truyền vào phải là số nguyên không âm. Nếu bạn muốn kiểm tra chỉ số hợp lệ thì nên kiểm tra trước khi gọi hàm này.
int Get(node head, int index){
int k = 0;
node p = head;
while(p->next != NULL && k != index){
++k;
p = p->next;
}
return p->data;
}
Lý do dùng p->next != NULL là vì chúng ta chỉ muốn đi qua các phần tử có value.
+ Tìm kiếm trong danh sách liên kết
Hàm tìm kiếm này sẽ trả về chỉ số của Node đầu tiên có giá trị bằng với giá trị cần tìm. Nếu không tìm thấy, chúng ta trả về -1.
int Search(node head, int value){
int position = 0;
for(node p = head; p != NULL; p = p->next){
if(p->data == value){
return position;
}
++position;
}
return -1;
}
Chúng ta có thể sử dụng hàm này để xóa tất cả các Node trong danh sách liên kết có giá trị chỉ định như sau:
node DelByVal(node head, int value){
int position = Search(head, value);
while(position != -1){
DelAt(head, position);
position = Search(head, value);
}
return head;
}
+ Duyệt danh sách liên kết
Việc duyệt danh sách liên kết cực đơn giản. Khởi tạo từ Node head, bạn cứ thế đi theo con trỏ next cho tới trước khi Node đó NULL.
void Traverser(node head){
printf("\n");
for(node p = head; p != NULL; p = p->next){
printf("%5d", p->data);
}
}
+ Một số hàm bổ trợ khác
Hàm khởi tạo Node head
Đơn giản là cho con trỏ head = NULL thôi. Nếu bạn để ý, chúng ta vẫn check head = NULL để biết rằng danh sách liên kết chưa có phần tử nào ở các hàm phía trên.
node InitHead(){
node head;
head = NULL;
return head;
}
Hàm lấy số phần tử của DSLK
Duyệt và đếm chừng nào các Node chưa NULL. Sau cùng, trả về giá trị đếm được.
int Length(node head){
int length = 0;
for(node p = head; p != NULL; p = p->next){
++length;
}
return length;
}
Hàm nhập danh sách liên kết
node Input(){
node head = InitHead();
int n, value;
do{
printf("\nNhap so luong phan tu n = ");
scanf("%d", &n);
}while(n <= 0);
for(int i = 0; i < n; ++i){
printf("\nNhap gia tri can them: ");
scanf("%d", &value);
head = AddTail(head, value);
}
return head;
}
IV. Thư Viện Linkedlist Trong C
Một Danh sách liên kết (Linked List) là 1 dãy các cấu trúc dữ liệu được kết nối với nhau thông qua các liên kết (link). Hiểu một cách đơn thuần thì Danh sách liên kết là một cấu trúc dữ liệu bao gồm 1 nhóm những nút (node) tạo thành một chuỗi. Mỗi nút gồm dữ liệu ở nút ấy và tham chiếu tới nút kế tiếp trong chuỗi.
Chương trình minh họa Danh sách liên kết (Linked List) trong C
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node
{
int data;
int key;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
//hien thi danh sach
void printList()
{
struct node *ptr = head;
printf("\n[ ");
//bat dau tu phan dau danh sach
while(ptr != NULL)
{
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
//chen link tai vi tri dau tien
void insertFirst(int key, int data)
{
//tao mot link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
//tro link nay toi first node cu
link->next = head;
//tro first toi first node moi
head = link;
}
//xoa phan tu dau tien
struct node* deleteFirst()
{
//luu tham chieu toi first link
struct node *tempLink = head;
//danh dau next toi first link la first
head = head->next;
//tra ve link bi xoa
return tempLink;
}
//kiem tra list co trong hay khong
bool isEmpty()
{
return head == NULL;
}
int length()
{
int length = 0;
struct node *current;
for(current = head; current != NULL; current = current->next)
{
length++;
}
return length;
}
//tim mot link voi key da cho
struct node* find(int key){
//bat dau tim tu first link
struct node* current = head;
//neu list la trong
if(head == NULL)
{
return NULL;
}
//duyet qua list
while(current->key != key){
//neu day la last node
if(current->next == NULL){
return NULL;
}else {
//di chuyen toi next link
current = current->next;
}
}
//neu tim thay du lieu, tra ve link hien tai
return current;
}
//xoa mot link voi key da cho
struct node* deleteKey(int key){
//bat dau tu first link
struct node* current = head;
struct node* previous = NULL;
//neu list la trong
if(head == NULL){
return NULL;
}
//duyet qua list
while(current->key != key){
//neu day la last node
if(current->next == NULL){
return NULL;
}else {
//luu tham chieu toi link hien tai
previous = current;
//di chuyen toi next link
current = current->next;
}
}
//cap nhat link
if(current == head) {
//thay doi first de tro toi next link
head = head->next;
}else {
//bo qua link hien tai
previous->next = current->next;
}
return current;
}
// ham sap xep
void sort(){
int i, j, k, tempKey, tempData ;
struct node *current;
struct node *next;
int size = length();
k = size ;
for ( i = 0 ; i < size - 1 ; i++, k-- ) {
current = head ;
next = head->next ;
for ( j = 1 ; j < k ; j++ ) {
if ( current->data > next->data ) {
tempData = current->data ;
current->data = next->data;
next->data = tempData ;
tempKey = current->key;
current->key = next->key;
next->key = tempKey;
}
current = current->next;
next = next->next;
}
}
}
// ham dao nguoc list
void reverse(struct node** head_ref) {
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("Danh sach ban dau: ");
//in danh sach
printList();
while(!isEmpty()){
struct node *temp = deleteFirst();
printf("\nGia tri bi xoa:");
printf("(%d,%d) ",temp->key,temp->data);
}
printf("\nDanh sach sau khi da xoa gia tri: ");
printList();
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("\nPhuc hoi danh sach: ");
printList();
printf("\n");
struct node *foundLink = find(4);
if(foundLink != NULL){
printf("Tim thay phan tu: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
}else {
printf("Khong tim thay phan tu.");
}
deleteKey(4);
printf("Danh sach, sau khi xoa mot phan tu: ");
printList();
printf("\n");
foundLink = find(4);
if(foundLink != NULL){
printf("Tim thay phan tu: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
}else {
printf("Khong tim thay phan tu.");
}
printf("\n");
sort();
printf("Danh sach sau khi duoc sap xep: ");
printList();
reverse(&head);
printf("\nDanh sach sau khi bi dao nguoc: ");
printList();
}
Kết quả
Biên dịch và chạy chương trình C trên sẽ cho kết quả:
V. Bài Tập Linked List C++
Nhằm giúp ace nâng cao kỹ năng, kiến thức lập trình, dễ dàng ghi nhớ và hiểu sâu hơn lúc đã học lý thuyết về linked list tại series tự học cấu trúc dữ liệu và giải thuật của techacademy. Sau đây là những bài tập có full lời giải và hướng dẫn giải cực chi tiết cho ace trên nhiều ngôn ngữ lập trình khác nhau.
Bài 1: Remove những phần tử trùng lặp trong linked list đã được sắp xếp
Cho 1 linked list được sắp xếp theo thứ tự tăng dần, hãy viết 1 hàm loại bỏ bất kỳ nút trùng lặp nào khỏi danh sách bằng phương pháp duyệt qua danh sách chỉ 1 lần
Cho thí dụ là: {1, 2, 2, 2, 3, 4, 4, 5}
sau lúc thực hiện sẽ được kết quả là: {1, 2, 3, 4, 5}
Gợi ý: Vì danh sách được sắp xếp, chúng ta có thể tiến hành rút gọn danh sách và so sánh các nút liền kề. Khi các nút liền kề giống nhau, hãy loại bỏ nút thứ hai. Có một trường hợp phức tạp trong đó nút sau nút tiếp theo cần được lưu ý trước khi xóa.
Bài 2: Đảo ngược mọi nhóm k nút trong danh sách liên kết đã cho
Cho một danh sách liên kết, đảo ngược mọi nhóm k nút liền kề trong đó với k là số nguyên dương.
Ví dụ:
–>
Input: 1>2>3>4>5>6>7>8>null
k = 3
Output: 3>2>1>6>5>4>8>7>null
k=2
Output: 2>1>4>3>6>5>8>7>null
k = 8
Output: 8>7>6>5>4>3>2>1>null
Gợi ý:
Ý tưởng là xem xét mọi nhóm k nút và đảo ngược đệ quy từng nút một. Cần phải đặc biệt chú ý khi liên kết các nhóm đảo ngược với nhau.
Bài 3: Di chuyển nút cuối cùng lên phía trước trong Danh sách được liên kết nhất định
Cho một danh sách được liên kết, hãy di chuyển nút cuối cùng của nó lên phía trước.
Ví dụ: Input: 1,2,3,4
Output: 4,1,2,3
Gợi ý: Ý tưởng là làm cho danh sách được liên kết có hình tròn và sau đó ngắt chuỗi trước nút cuối cùng sau khi làm cho danh sách này hướng đến nút cuối cùng.
Bài 4: Xóa mọi N nút trong danh sách được liên kết sau khi bỏ qua M nút
Cho một danh sách được liên kết và hai số nguyên dương M và N, xóa mọi N nút trong đó sau khi bỏ qua M nút.
Ví dụ:
1>2>3>4>5>6>7>8>9>10>null
if M = 1, N = 3
Output: 1>5>9>null
if M=2, N=2
Output: 1>2>5>6>9>10>null
Gợ ý: Ý tưởng rất đơn giản. Chúng tôi duyệt qua danh sách đã cho và bỏ qua m nút đầu tiên và xóa n nút tiếp theo trong đó và lặp lại cho các nút còn lại. Giải pháp rất đơn giản nhưng chúng ta cần đảm bảo rằng tất cả các điều kiện biên được xử lý đúng cách trong code.
Bài 5: Hợp nhất hai danh sách liên kết đã sắp xếp thành một
Viết một hàm nhận hai danh sách, mỗi danh sách được sắp xếp theo thứ tự tăng dần và hợp nhất hai danh sách với nhau thành một danh sách theo thứ tự tăng dần và trả về.
Ví dụ:
Input: 1>7>5>4 và 2>6>3>9
Output: 1>2>3>4>5>6>7>9
Gợi ý: Vấn đề có thể được giải quyết bằng vòng lặp hoặc đệ quy. Có nhiều trường hợp cần giải quyết: hoặc ‘a’ hoặc ‘b’ có thể để trống, trong quá trình xử lý, ‘a’ hoặc ‘b’ có thể hết đầu tiên và cuối cùng là vấn đề khởi động danh sách kết quả trống và xây dựng nó lên trong khi đi qua ‘a’ và ‘b’.
Có khá nhiều các giải như sau:
- Sử dụng nút giả
Chiến lược ở đây sử dụng một nút giả tạm thời làm điểm bắt đầu của danh sách kết quả. Đuôi con trỏ luôn trỏ đến nút cuối cùng trong danh sách kết quả, vì vậy việc thêm các Nút mới rất dễ dàng. Nút giả cung cấp cho đuôi một cái gì đó để trỏ đến ban đầu khi danh sách kết quả trống. Nút giả này hiệu quả, vì nó chỉ là tạm thời và nó được cấp phát trong ngăn xếp. Vòng lặp tiếp tục, xóa một nút khỏi ‘a’ hoặc ‘b’ và thêm nó vào đuôi. Khi chúng ta hoàn tất, kết quả là dummy.next.
- Sử dụng Tham chiếu cục bộ
Giải pháp này có cấu trúc rất giống với giải pháp trên, nhưng nó tránh sử dụng một nút giả. Thay vào đó, nó duy trì một con trỏ struct node ** lastPtrRef , luôn trỏ đến con trỏ cuối cùng của danh sách kết quả. Điều này giải quyết trường hợp tương tự mà nút giả đã làm – xử lý danh sách kết quả khi nó trống. Nếu bạn đang cố gắng tạo một danh sách ở đuôi của nó, bạn có thể sử dụng chiến lược nút giả hoặc nút cấu trúc ** “tham chiếu”.
The post Linked List C++ first appeared on Techacademy.
source https://techacademy.edu.vn/linked-list-c/
Nhận xét
Đăng nhận xét