Bài tập Linked list C++

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.

Linked List C++ Là Gì

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ử

Đặc Điểm Của Danh Sách Liên Kết Đơn

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ẽ:

1. Tạo một Node mới với giá trị value
2. 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.
3. 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 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ả:

Thư Viện Linkedlist Trong C

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ủatechacademy. 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.

Bài Tập Linked List C++