Danh sách liên kết đơn C++ setup bằng bé trỏ. Lí giải code chế tạo ra một danh sách, sắp tới xếp, xóa phần tử đầu, cuối, giữa trong danh sách. Thuộc với bài bác tập ví dụ đưa ra tiết.
Bạn đang xem: Nhập xuất danh sách liên kết đơn
1.Danh sách links là gì?
Danh sách liên kết là một trong kiểu dữ liệu có cấu trúc. Là một quy mô dữ liệu đựng tập phù hợp hữu hạn dịch chuyển các thành phần thuộc và một lớp đối tượng nào đó. Nó được dùng làm liên kết các thành phần lại cùng 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 link đơn – Single Linked ListDanh sách liên kết đôi – Double Linked ListDanh sách links vòng – Crircular Linked ListĐa liên kết2. Danh sách links đơn
Danh sách link đơn tất cả nhiều bộ phận liên đặc lại với nhau. Mỗi bộ phận là một ô ghi nhớ có cấu trúc 2 ngăng như sau:
M ngăn chứa tài liệu – DataMột chống là bé trỏ, trỏ tới địa chỉ của ô nhớ tiếp theo là ô ghi nhớ đứng ngay lập tức sau nó vào danh sách.Để hiểu được phần này. Bạn phải nắm được vững kiến thức về con trỏ. Biết những câu lệnh truy hỏi xuất, cấp vùng ghi nhớ cho bé trỏ.
Dưới đây là một ví dụ về danh sách, các thành phần của chúng phần đông móc nối cùng với nhau.
2.1 thiết đặ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++, chúng ta nào code C thì chỉ cần đổi câu lệnh nhập xuất, cung cấp phát bộ nhớ lưu trữ và khai báo lại thư viện là được.Bài toán của chính mình là thống trị một list đơn những số nguyên.Nếu bạn cần xem cai quản sinh viên thì hoàn toàn có thể tham khảo tại bài viết này!
Đây là hàm khai báo, khái niệm một danh sách link đơn. Chúng ta phải khai báo đúng cấu tạo của một ô nhớ như sau:
typedef int item; // Từ tiếng khai báo tòa tháp sẽ là mẫu mã inttypedef struct nodeitem 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ỏ mang đến một ” node ” tiếp theo sau trong ds, buộc phải bắt buộc phải đặt kiểu ” node ” .
Nếu bạn gặp mặt bài toán quản lý danh sách sinh viên, cán cỗ . . . Bởi danh sách link đơn thì chỉ nỗ lực kiểu int thành kiểu dữ liệu có cấu trúc là được.
2.2 Hàm tạo list rỗng
Chúng ta bắt buộc phải tạo nên một list rỗng trước lúc truyền vào đó dữ liệu đúng không nào nào! Điều này giúp thải trừ hoàn toàn dữ liệu rác ở bộ nhớ. Đôi khi rất có thể bị lỗi nếu không có hàm này!
Ở trên đây bạn chỉ cần cho nhỏ trỏ list L = NULL là xong!
Chú ý: Lỗi hiển thị mã nguồn, vệt & gửi thành & amp ;
2.3 các hàm kiểm soát độ lâu năm List
Những hàm này dùng trong vấn đề kiểm tra độ nhiều năm danh sách. Hàm này không hoàn toàn bắt buộc. Tùy thuộc vào thuật toán của bạn mà quan tâm đến có yêu cầu nó hay không!//Kiem tra vì chưng dai Listint Len(List L)node *P = L;int i=0;while (P!=NULL) //Khi không đếm tới thành phần cuối cùng thì tiếp tụci++;P=P->Next;return i;
2.4 Hàm tạo ra một node
Hàm tạo nên một node: dùng để làm khởi tạo ra và gán giá trị cho node. Hàm này dùng khi bạn chèn góp phần từ vào một danh sách.//Tao mot Nodenode *Make_node(node *P,item x)P = new node; // cấp cho phát bộ nhớ lưu trữ cho nhỏ trỏP->Data=x;P->Next= NULL;return P;
Code này mình cần sử dụng C++. Nếu như bạn dùng C thì chỉ việc đồi câu lệnh cấp cho phát bộ nhớ lưu trữ là được: (node*)malloc ( sizeof (node) )
2.5 Chèn phần tử vào danh sách
Hay còn được gọi là thêm phần tử và danh sách liên kết.
Có 3 vị trí bọn họ cần nên 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_firstChèn thêm phần tử vào đầu danh sách liên kết đơn rất solo giản. Bạn chỉ việc tạo một node mới. Mang đến node này trỏ mang đến vị trí thành phần đầu tiên của danh sách. Tiếp nối gán lại list ban đầu.
//Ham chen vao vi tri dauvoid Insert_first(List &L, cống phẩm x)node *P = Make_node(P,x);if(L == NULL)L=P;elseP->Next=L;// mang đến node phường trỏ tới đầu danh sáchL=P; /// Gán list bằng nhỏ trỏ P
Hàm chèn vào địa chỉ k bất kìThêm 1 phần tử vào thân danh sách liên kết đơn tại 1 vị trí k rõ ràng nào đó. Rất có thể bài toàn của bạn làm yêu cầu khác đi một ít nhưng thực chất không thay đổi.
Thuật toán:
Tạo một bé trỏ phường đựng giá chỉ trị buộc phải chèn, nhỏ trỏ Q dùng duyệt danh sáchDuyệt menu L tới trước vị trí buộc phải chèn một đối kháng vịGán phường = 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 và L, thành quả x, int k)node *P, *Q=L; //Khoi tao con tro Q tro toi menu 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 thành phần vào cuối list cũng là 1 trong những yêu cầu của bài toán. Mình cần sử dụng hàm này trong việc thêm bắt đầu các bộ phận vào danh sách.
Thuật toán cũng tương tự như với chèn vào địa chỉ bất kì, nhưng ở đây mình xem xét tới cuối danh sách tiếp nối mới t
void Insert_Last(List & L, nhà cửa x)node *P = L; // Khởi sản xuất node p trỏ cho tới Lnode * temp = Make_node(temp,x); if(L==NULL)L=temp;elsewhile(P->Next!=NULL)P=P->Next;P->Next=temp;
2. 6 Hàm tìm kiếm kiếm phần tử trong danh sách – Search_x
Tìm kiếm địa điểm của phần từ bất kể trong danh sách liên kết. Thông số truyền vào là giá chỉ trị đề nghị tìm.Ý tưởng:
Duyệt từ trên đầu danh sách cho tới cuối danh sách, nếu chạm chán vị trí thứ nhất của thành phần thì return. Ngược lại return 0;
//Tim kiem phan tuint Search_x(List L, thành phầm x)node *P=L; // Khai báo bé trỏ p. Trỏ tới Lint i=1;while(P!=NULL && P->Data!=x)i++;P=P->Next;if(P!=NULL) //Nếu list khác trống rỗng thì trả về ireturn i;else // NẾu list rỗng thì trả về 0;return 0;
2.7 Xóa bộ phận khỏi danh sách
Tương tự như thêm thành phần vào danh sách, xóa sổ danh sách bao gồm 3;Xóa thành phần ở đầuXóa phần tử ở địa chỉ bất kỳHàm xóa đầu – Del_firstXóa bộ phận đầu tiên khỏi danh sách rất đối chọi giản. Chỉ việc trỏ thành phần đầu tiên thành phần tử phía sau nó là được.
Hàm xóa vị trí bất cứ – Del_kXóa phần tử khỏi danh sách links đơn khi biết vị trí có vẻ như sẽ cực nhọc hơn một chút. Cơ mà về bản chất thì tựa như xóa đầu. Xóa bộ phận ở cuối list dùng hàm này cũng rất được nhé!
Ý tưởng: Chúng ta sẽ chú ý mảng tới vị trí k – 1. Tiếp đến gán bé trỏ Next của bộ phận k -1 thành thành phần sau địa chỉ k. Như vậy thành phần ở địa chỉ k sẽ ảnh hưởng bỏ khỏi danh sách links đơn
// Hàm xóa địa chỉ 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 thành phần k}}
2.8 Nhập danh sách – input List
Tùy theo kiểu danh sách các bạn là gì mà biện pháp nhập xuất khác nhau. Nội dung bài viết này bản thân nhập xuất số nguyên nên bao gồm phần đơn giản dễ dàng hơnMình sẽ nhập vào thành phần cho danh sách links đơn bởi con trỏ. Ví như nhập vào bằng 0 thì vẫn dừng nhập. Thêm phần tử vào list mình áp dụng hàm chèn cuối Insert_Last
// Hàm nhập danh sách số nguyên từ keyboard void Input(List &L)Init(L);item x;int i=1;docout>x;if (x!=0)Insert_Last(L,x);i++;while (x!=0);// giả dụ nhập x = 0 thì ngừng nhập//Ban co the dung cach khac
2. 9 Hàm xuất list – output đầu ra List
Xuất danh sách thì đơn giản dễ dàng rồi. Chúng ta duyệt list tử đầu mang lại cuối rồi in ra màn hình lần lượt các thành phần là được// Hàm xuất list void Output(List L)node *P= L; // Khai báo nhỏ trỏ phường trỏ cho tới coutData; // ỉn ra screen giá trịP=P->Next;}
3. Chương trình hoàn chỉnh
Tổng hợp những hàm trên lại, mình giải quyết được bài toàn như tiêu đề bài xích viết. Một câu hỏi ứng dụng tương đối 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 bản thân trên Github. Tải về file và tránh bị lỗi hiển thị. tại đây
Code trả chỉnh:
// Code by phanmemcntt.com with love#include //using namespace std;typedef int item;typedef struct nodeitem Data;node *Next;node;typedef node *List;//Tao danh sách 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, thành công x)P = new node;P->Data=x;P->Next= NULL;return P;//Chen vao dau danh sachvoid Insert_first(List &L, thắng lợi x)node *P = Make_node(P,x);if(L == NULL)L=P;elseP->Next=L;L=P;//Chen vao vi tri cuoi cungvoid Insert_Last(List & L, thành quả x)node *P = L;node * temp = Make_node(temp,x);if(L==NULL)L=temp;elsewhile(P->Next!=NULL)P=P->Next;P->Next=temp;//Chen vao vi tri Kvoid Insert_K(List & L, công trình 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, thành phầm 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 sầu 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;docout>x;if (x!=0)Insert_Last(L,x);i++;while (x!=0);//Neu nhap x = 0 thi dung nhap//Ban co the dung cach khacvoid 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 nội dung bài viết này của mình các bạn sẽ có thể hiểu bạn dạng chất, biết cách sử dụng và tương tác với danh sách link đơn cùng với C++. Tự đó áp dụng vào bài toán lập trình sau này!Có thể bạn chưa chắc chắn cách có tác dụng tròn số thực, số thập phân vào C++. Tham khảo nội dung bài viết này của mình nhé!
