Code danh sách liên kết đơn C++
Danh Sách liên kết đơn Single Linked List Code C/C++By Như Quỳnh- 0 6636 Facebook Twitter Pinterest Email 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. Show
Mục lục bài viế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:
2. Danh sách liên kết đơnDanh 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:
Để 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. Đâ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ỗngChú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 ListNhữ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 nodeHà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áchHay 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 :
Hàm chèn đầu Insert_firstChè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:
//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"< 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 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_xTì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áchTương tự như thêm phần tử vào danh sách, xóa khỏi danh sách có 3;
Hàm xóa đầu Del_firstXó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_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 L
int i=1;
if(k < 1 || k>Len(L) )
cout<<"\nVi tri xoa khong hop le"< 2.8 Nhập danh sách Input ListTù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 "< 2. 9 Hàm xuất danh sách Output ListXuấ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<<" "< 3. Chương trình hoàn chỉnhTổ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 4. Lời kếtMong 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é!
Facebook Twitter Pinterest Email Previous articleSố nguyên tố trong Python Cách viết hàm kiểm tra Next articleHướng dẫn cách xác minh danh tính Google Adsense 100% thành công |
