Code danh sách liên kết đơn C++

Học Lập Trình
C/C++
Cấu trúc dữ liệu và thuật toán

Danh Sách liên kết đơn Single Linked List Code C/C++

Như Quỳnh

27/05/2020

6636

Facebook

Twitter

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:

Danh sách liên kết đơn Single Linked List
Danh sách liên kết đôi Double Linked List
Danh 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 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 Len[L]] coutNext=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] coutLen[L] ] coutNext; // 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{ coutData!=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] coutLen[L] ] coutNext; } } //Nhap ds; void Input[List &L]{ Init[L]; item x; int i=1; do{ cout