Danh sách liên kết đơn C++ cài đặt bằng con trỏ. Hướng dẫn code tạo một danh sách, sắp xếp, xóa phần tử đầu, cuối, giữa trong danh sách. Cùng với bài tập ví dụ chi tiết.

Đang xem: Nhập xuất danh sách liên kết đơn

1.Danh sách liên kết là gì?

Danh sách liên kết là một kiểu dữ liệu có cấu trúc. Là một mô hình dữ liệu chứa tập hợp hữu hạn biến động các phần tử thuộc cùng một lớp đối tượng nào đó. Nó được dùng để liên kết các phần tử lại với nhau, sử dụng cho nhiều mục đích riêng.

Các kiểu danh sách liên kết:

Danh sách liên kết đơn – Single Linked ListDanh sách liên kết đôi – Double Linked ListDanh sách liên kết vòng – Crircular Linked ListĐa liên kết

2. Danh sách liên kết đơn

Danh sách liên kết đơn gồm nhiều phần tử liên kết lại với nhau. Mỗi phần tử là một ô nhớ có cấu trúc 2 ngăng như sau:

M ngăn chứa dữ liệu – DataMột ngăn là con trỏ, trỏ tới địa chỉ của ô nhớ tiếp theo là ô nhớ đứng ngay sau nó trong danh sách.

Để hiểu được phần này. Bạn cần phải nắm được vững kiến thức về con trỏ. Biết các câu lệnh truy xuất, cấp vùng nhớ cho con trỏ.

Dưới đây là một ví dụ về danh sách, các thành phần của chúng đều móc nối với nhau.

*

2.1 Cài đặt danh sách liên kết đơn bằng con trỏ

Bài viết này mình viết hoàn toàn bằng code C++, bạn nào code C thì chỉ cần đổi câu lệnh nhập xuất, cấp phát bộ nhớ và khai báo lại thư viện là được.Bài toán của mình là quản lý một danh sách đơn các số nguyên.Nếu bạn cần xem quản lý sinh viên thì có thể tham khảo tại bài viết này!

Đây là hàm khai báo, định nghĩa một danh sách liên kết đơn. Chúng ta phải khai báo đúng cấu trúc của một ô nhớ như sau:

typedef int item; // Từ giờ khai báo item sẽ là kiểu inttypedef struct node{item Data;node *Next; //Tro den phan tu tiep theo};typedef node *List; //Tu gio khai bao List là khai bao danh sach cac nodeList L; //Khai bao danh sach L gom cac node
Trong đó con trỏ next sẻ trỏ đến một ” node ” tiếp theo trong ds, nên bắt buộc phải để kiểu ” node ” .

Nếu bạn gặp bài toán quản lý danh sách sinh viên, cán bộ . . . bằng danh sách liên kết đơn thì chỉ thay kiểu int thành kiểu dữ liệu có cấu trúc là được.

2.2 Hàm tạo danh sách rỗng

Chúng ta cần phải tạo ra một danh sách rỗng trước khi truyền vào đó dữ liệu đúng không nào! Điều này giúp loại bỏ hoàn toàn dữ liệu rác ở bộ nhớ. Đôi khi có thể bị lỗi nếu không có hàm này!

Ở đây bạn chỉ cần cho con trỏ danh sách L = NULL là xong!

Chú ý: Lỗi hiển thị mã nguồn, dấu & chuyển thành & amp ;

*

2.3 Các hàm kiểm tra độ dài List

Những hàm này dùng trong việc kiểm tra độ dài danh sách. Hàm này không hoàn toàn bắt buộc. Tùy vào thuật toán của bạn mà cân nhắc có cần nó hay không!

//Kiem tra do dai Listint Len(List L){node *P = L;int i=0;while (P!=NULL){ //Khi chưa đếm tới phần tử cuối cùng thì tiếp tụci++;P=P->Next;}return i;}

2.4 Hàm tạo một node

Hàm tạo một node: dùng để khởi tạo và gán giá trị cho node. Hàm này dùng khi bạn chèn thêm phần từ vào một danh sách.

//Tao mot Nodenode *Make_node(node *P,item x){P = new node; // Cấp phát bộ nhớ cho con trỏP->Data=x;P->Next= NULL;return P;}
Code này mình dùng C++. Nếu bạn dùng C thì chỉ cần đồi câu lệnh cấp phát bộ nhớ là được: (node*)malloc ( sizeof (node) )

2.5 Chèn phần tử vào danh sách

Hay còn gọi là thêm phần tử và danh sách liên kết.

Xem thêm: Top 20 Bảng Xếp Hạng Âm Nhạc Quốc Tế, Wikipedia:Bảng Xếp Hạng Âm Nhạc

Có 3 vị trí chúng ta cần phải viết hàm chèn :

Chèn đầuChèn giữa (vị trí k bất kỳ)Chèn cuốiHàm chèn đầu – Insert_first

Chèn thêm phần tử vào đầu danh sách liên kết đơn rất đơn giản. Bạn chỉ cần tạo một node mới. Cho node này trỏ đến vị trí phần tử đầu tiên của danh sách. Sau đó gán lại danh sách ban đầu.

//Ham chen vao vi tri dauvoid Insert_first(List &L, item x){node *P = Make_node(P,x);if(L == NULL)L=P;else{P->Next=L;// Cho node P trỏ tới đầu danh sáchL=P; /// Gán danh sách bằng con trỏ P}}
Hàm chèn vào vị trí k bất kìThêm một phần tử vào giữa danh sách liên kết đơn ở một vị trí k cụ thể nào đó. Có thể bài toàn của bạn làm yêu cầu khác đi một chút nhưng bản chất không thay đổi.

Thuật toán:

Tạo một con trỏ P đựng giá trị cần chèn, con trỏ Q dùng duyệt danh sáchDuyệt List L tới trước vị trí cần chèn một đơn vịGán P = Q->Next để nối P với phần sau của listSau đó gán Q -> Next = P

//Ham Chen vao vi tri Kvoid Insert_K(List & L, item x, int k){node *P, *Q=L; //Khoi tao con tro Q tro toi list L;int i=1;if(k Len(L))coutNext;i++;}P->Next=Q->Next;Q->Next=P;}}}
Hàm chèn vào cuối danh sách – Insert_LastChèn thêm phần tử vào cuối danh sách cũng là một yêu cầu của bài toán. Mình dùng hàm này trong việc thêm mới các phần tử vào danh sách.

Thuật toán cũng giống với chèn vào vị trí bất kì, nhưng ở đây mình duyệt tới cuối danh sách sau đó mới t

void Insert_Last(List & L, item x){node *P = L; // Khởi tạo node P trỏ tới Lnode * temp = Make_node(temp,x); if(L==NULL)L=temp;else{while(P->Next!=NULL){P=P->Next;}P->Next=temp;}}

2. 6 Hàm tìm kiếm phần tử trong danh sách – Search_x

Tìm kiếm vị trí của phần từ bất kì trong danh sách liên kết. Tham số truyền vào là giá trị cần tìm.

Ý tưởng:

Duyệt từ đầu danh sách tới cuối danh sách, nếu gặp vị trí đầu tiên của phần tử thì return. Ngược lại return 0;

//Tim kiem phan tuint Search_x(List L, item x){node *P=L; // Khai báo con trỏ P trỏ tới Lint i=1;while(P!=NULL && P->Data!=x){i++;P=P->Next;}if(P!=NULL) //Nếu danh sách khác rỗng thì trả về ireturn i;else // NẾu danh sách rỗng thì trả về 0;return 0;}

2.7 Xóa phần tử khỏi danh sách

Tương tự như thêm phần tử vào danh sách, xóa khỏi danh sách có 3;

Xóa phần tử ở đầuXóa phần tử ở vị trí bất kỳHàm xóa đầu – Del_first

Xóa phần tử đầu tiên khỏi danh sách rất đơn giản. Chỉ cần trỏ phần tử đầu tiên thành phần tử phía sau nó là được.

Hàm xóa vị trí bất kì – Del_kXóa phần tử khỏi danh sách liên kết đơn khi biết vị trí có vẻ sẽ khó hơn một chút. Nhưng về bản chất thì tương tự xóa đầu. Xóa phần tử ở cuối danh sách dùng hàm này cũng được nhé!

Ý tưởng: Chúng ta sẽ duyệt mảng tới vị trí k – 1. Sau đó gán con trỏ Next của phần tử k -1 thành phần tử sau vị trí k. Như vậy phần tử ở vị trí k sẽ bị bỏ khỏi danh sách liên kết đơn

// Hàm xóa vị trí bất kìvoid Del_k(List &L, int k){node *P=L; // Khai báo con trỏ P trỏ tới Lint i=1;if(k Len(L) )coutNext;i++;}P->Next=P->Next->Next; // Xóa đi phần tử k}}

2.8 Nhập danh sách – Input List

Tùy theo kiểu danh sách bạn là gì mà cách nhập xuất khác nhau. Bài viết này mình nhập xuất số nguyên nên có phần đơn giản hơn

Mình sẽ nhập vào phần tử cho danh sách liên kết đơn bằng con trỏ. Nếu nhập vào bằng 0 thì sẽ dừng nhập. Thêm phần tử vào danh sách mình sử dụng hàm chèn cuối Insert_Last

// Hàm nhập danh sách số nguyên từ bàn phím void Input(List &L){Init(L);item x;int i=1;do{cout>x;if (x!=0){Insert_Last(L,x);i++;}}while (x!=0);// Nếu nhập x = 0 thì dừng nhập//Ban co the dung cach khac}

2. 9 Hàm xuất danh sách – Output List

Xuất danh sách thì đơn giản rồi. Bạn duyệt danh sách tử đầu đến cuối rồi in ra màn hình lần lượt các phần tử là được

// Hàm xuất danh sách void Output(List L){node *P= L; // Khai báo con trỏ P trỏ tới coutData; // ỉn ra màn hình giá trịP=P->Next;}}

3. Chương trình hoàn chỉnh

Tổng hợp các hàm bên trên lại, mình giải quyết được bài toàn như tiêu đề bài viết. Một bài toán ứng dụng rất nhiều trong việc lập trình sau này.

Xem thêm: Kinh Nghiệm Viết Stt Quay Lại Với Người Yêu Cũ Hiệu Quả, Status Cảm Động Níu Kéo Người Yêu Cũ

Bạn có thể xem toàn bộ bài code này của mình trên Github. Tải về file và tránh bị lỗi hiển thị. Tại đây

Code hoàn chỉnh:

// Code by phanmemcntt.com with love#include //using namespace std;typedef int item;typedef struct node{item Data;node *Next;}node;typedef node *List;//Tao list rongvoid Init(List & L){L=NULL;}//check nullint Isempy(List L){return (L==NULL);}//Do dai Listint Len(List L){node *P = L;int i=0;while (P!=NULL){i++;P=P->Next;}return i;}//Tao mot Nodenode *Make_node(node *P, item x){P = new node;P->Data=x;P->Next= NULL;return P;}//Chen vao dau danh sachvoid Insert_first(List &L, item x){node *P = Make_node(P,x);if(L == NULL)L=P;else{P->Next=L;L=P;}}//Chen vao vi tri cuoi cungvoid Insert_Last(List & L, item x){node *P = L;node * temp = Make_node(temp,x);if(L==NULL)L=temp;else{while(P->Next!=NULL){P=P->Next;}P->Next=temp;}}//Chen vao vi tri Kvoid Insert_K(List & L, item x, int k){node *P, *Q=L;int i=1;if(k Len(L))coutNext;i++;}P->Next=Q->Next;Q->Next=P;}}}//Tim kiem phan tuint Search_x(List L, item x){node *P=L;int i=1;while(P!=NULL && P->Data!=x){i++;P=P->Next;}if(P!=NULL) //Neu danh sach khac rong tra ve ireturn i;else // Danh sach bang rong thi vi tri bang 0;return 0;}//Xoa dau danh sachvoid Del_first(List &L){if(L==NULL)coutNext;}//Xoa vi tri bat kyvoid Del_k(List &L, int k){node *P=L;int i=1;if(k Len(L) )coutNext;i++;}P->Next=P->Next->Next;}}//Nhap ds;void Input(List &L){Init(L);item x;int i=1;do{cout>x;if (x!=0){Insert_Last(L,x);i++;}}while (x!=0);//Neu nhap x = 0 thi dung nhap//Ban co the dung cach khac}void Output(List L){node *P= L;coutData;P=P->Next;}}int main(){List L;Input(L);cout

4. Lời kết

Mong rằng sau khi tham khảo xong bài viết này của mình bạn sẽ có thể hiểu bản chất, biết cách sử dụng và tương tác với danh sách liên kết đơn với C++. Từ đó ứng dụng vào việc lập trình sau này!

Có thể bạn chưa biết cách làm tròn số thực, số thập phân trong C++. Tham khảo bài viết này của mình nhé!

Leave a Reply

Your email address will not be published. Required fields are marked *