Danh Sách Liên Kết đơn - Single Linked List Code C/C++

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.

Mục lục bài viết

• 1.Danh sách liên kết là gì?
• 2. Danh sách liên kết đơn
  • 2.1 Cài đặt danh sách liên kết đơn bằng con trỏ
  • 2.2 Hàm tạo danh sách rỗng
  • 2.3 Các hàm kiểm tra độ dài List
  • 2.4 Hàm tạo một node
  • 2.5 Chèn phần tử vào danh sách
    • Hàm chèn đầu – Insert_first
    • Hàm chèn vào vị trí k bất kì
    • Hàm chèn vào cuối danh sách – Insert_Last
  • 2. 6 Hàm tìm kiếm phần tử trong danh sách – Search_x
  • 2.7 Xóa phần tử khỏi danh sách
    • Hàm xóa đầu – Del_first
    • Hàm xóa vị trí bất kì – Del_k
  • 2.8 Nhập danh sách – Input List
  • 2. 9 Hàm xuất danh sách – Output List
• 3. Chương trình hoàn chỉnh
• 4. Lời kết

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:

1. Danh sách liên kết đơn – Single Linked List
2. Danh sách liên kết đôi – Double Linked List
3. Danh sách liên kết vòng – Crircular Linked List
4. Đ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 – Data
• Mộ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 int typedef 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 node List 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 ” .

Giải thích thêm: Các tài liệu dạy lập trình thường gọi cấu trúc dữ liệu một ô nhớ như trên là một ” node “. Đây chỉ là một từ do lập trình viên tự định nghĩa, bạn có thể đặt tên tùy ý đều được.

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 ;

//Ham tao List rong void Init(List & L){ L=NULL; }

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 List int 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ục i++; 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 Node node *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.

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

• Chèn đầu
• Chèn giữa (vị trí k bất kỳ)
• Chèn cuối

Hà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 dau void 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ách L=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ách
• Duyệ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 list
• Sau đó gán Q -> Next = P

//Ham Chen vao vi tri K void 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<1 || k > Len(L)) cout<<"\nVi tri chen khong hop le"<<endl; else{ if(k==1) // Neu vi tri can chen trung voi 1 Insert_first(L,x); else{ P= Make_node(P,x); while (i!=k-1 && Q!=NULL){ Q=Q->Next; i++; } P->Next=Q->Next; Q->Next=P; } } }

Hàm chèn vào cuối danh sách – Insert_Last

Chè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 L node * 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 tu int Search_x(List L, item x){ node *P=L; // Khai báo con trỏ P trỏ tới L int 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ề i return 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ử ở đầu
• Xó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.

//Xoa dau danh sach void Del_first(List &L){ if(L==NULL) cout<<"\nKhong co gi de xoa!"; else L=L->Next; // L gán bằng phần tử phía sau }

Hàm xóa vị trí bất kì – Del_k

Xó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 L int i=1; if(k < 1 || k>Len(L) ) cout<<"\nVi tri xoa khong hop le"<<endl; else if(k==1) Del_first(L); // Nếu vị trí bằng 1 gọi Del_first else{ while (i!=k-1 && P!=NULL){ // Duyệt đến k - 1 P=P->Next; 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<<"\nNhap phan tu thu "<<i<<": "; cin>>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 cout<<"\n"; while (P!=NULL){ cout<<" "<<P->Data; // ỉ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.

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<bits/stdc++.h> // using namespace std; typedef int item; typedef struct node{ item Data; node *Next; }node; typedef node *List; //Tao list rong void Init(List & L){ L=NULL; } //check null int Isempy(List L){ return (L==NULL); } //Do dai List int Len(List L){ node *P = L; int i=0; while (P!=NULL){ i++; P=P->Next; } return i; } //Tao mot Node node *Make_node(node *P, item x){ P = new node; P->Data=x; P->Next= NULL; return P; } //Chen vao dau danh sach void 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 cung void 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 K void Insert_K(List & L, item x, int k){ node *P, *Q=L; int i=1; if(k<1 || k > Len(L)) cout<<"\nVi tri chen khong hop le"<<endl; else{ if(k==1) Insert_first(L,x); else{ P= Make_node(P,x); while (i!=k-1 && Q!=NULL){ Q=Q->Next; i++; } P->Next=Q->Next; Q->Next=P; } } } //Tim kiem phan tu int 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 i return i; else // Danh sach bang rong thi vi tri bang 0; return 0; } //Xoa dau danh sach void Del_first(List &L){ if(L==NULL) cout<<"\nKhong co gi de xoa!"; else L=L->Next; } //Xoa vi tri bat ky void Del_k(List &L, int k){ node *P=L; int i=1; if(k < 1 || k>Len(L) ) cout<<"\nVi tri xoa khong hop le"<<endl; else if(k==1) Del_first(L); else{ while (i!=k-1 && P!=NULL){ P=P->Next; i++; } P->Next=P->Next->Next; } } //Nhap ds; void Input(List &L){ Init(L); item x; int i=1; do{ cout<<"\nNhap phan tu thu "<<i<<": "; cin>>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; cout<<"\n"; while (P!=NULL){ cout<<" "<<P->Data; P=P->Next; } } int main(){ List L; Input(L); cout<<"\nDanh Sach: "; Output(L); item x = 100; cout<<"\nThem 100 vao vi tri 3: "; Insert_K(L,x,3); Output(L); // cout<<"\nVi tri x: "<<Search_x(L,x); cout<<"\nXoa phan tu 100 khoi danh sach: "; Del_k(L,Search_x(L,x)); //tim vi tri cua x sau do xoa tai vi tri nay Output(L); cout<<"\n Cam on ban da xem bai viet cua minh"; }

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é!