BÀI TẬP VỀ DANH SÁCH LIÊN KẾT ĐƠN C++, BÀI TẬP DANH SÁCH LIÊN KẾT ĐƠN BẰNG C/C++

1. Định nghĩa một cấu trúc Sinh viên bao gồm các trường thông tin như sau: Mã sv (kiểu số nguyên), tên sv (kiểu chuỗi cam kết tự), lớp (kiểu chuỗi ký kết tự), điểm tổng kết (kiểu số thực), hạnh kiểm (Tốt, khá, trung bình, yếu).2. Cài đặt một cấu tạo danh sách liên kết 1-1 cho kiểu tài liệu Sinh viên, với những thao tác: 1) Khởi tạo danh sách; 2) kiểm tra rỗng 3) thêm bộ phận vào cuối (hoặc đầu) danh sách 4) search kiếm thành phần trong danh sách; 5) Xóa )phần tử sau cuối khỏi danh sách; 6) phê duyệt danh sách; 7) Sắp xếp danh sách3. Chương trình chính: Sử dụng cấu trúc danh sách liên kết đối chọi và các thao tác làm việc ở trên để:

– Nhập vào một trong những danh sách link đơn bao gồm n sv (n bất kỳ).

Bạn đang xem: Bài tập về danh sách liên kết đơn

– Hiển thị list đã nhập ra màn hình.

-Liệt kê ra màn hình danh sách tất cả những Sinh viên ở trong lớp “D13CNPM”.

– Sắp sếp danh sách sinh viên theo mã sinh viên tăng dần

– Xóa bộ phận cuối cùng khỏi danh sách.

Hiển thị lại danh sách sau thời điểm xóa ra màn hình.

2.Xây dựng chương trình theo yêu thương cầu đề bài

#include #include #include struct sinhvien int masv; char tensv<20>; char lop<20>; float dtk; char hk<15>;;typedef struct sinhvien SV;struct node SV data; node * next;;typedef struct node NODE;struct list NODE *p
Head; NODE *p
Tail;;typedef struct danh mục LIST;void Khoi
Tao(LIST &ds) ds.p
Head = NULL; ds.p
Tail = NULL;int Kiem
Tra
Rong(LIST ds) if (ds.p
Head == NULL) return 1; return 0;NODE* Tao
Node(SV x) NODE *p; p. = new NODE; if (p==NULL) printf ("KHONG DU BO NHO"); return NULL; p->data=x; p->next=NULL; return p;void Chen
Cuoi (LIST &ds, NODE *p) if (ds.p
Head==NULL) ds.p
Head=p; ds.p
Tail=p; else ds.p
Tail->next=p; ds.p
Tail=p; void Nhap(LIST &ds, int n) printf("NHAP THONG TIN SINH VIEN "); for(int i = 0; i next) printf("%d %s %s %f %s ", p->data.masv, p->data.tensv, p->data.lop, p->data.dtk, p->data.hk); void SVD13CNPM(LIST ds) for(NODE *p = ds.p
Head; p!= NULL; p=p->next) if(strcmp(p->data.lop, "D13CNPM")==0) printf("%d %s %s %f %s ", p->data.masv, p->data.tensv, p->data.lop, p->data.dtk, p->data.hk); void Sap
Xep(LIST &ds) NODE *p, *q; for(p = ds.p
Head; p != ds.p
Tail; p=p->next) for(q = p->next; q != NULL; q = q->next) if(p->data.masv > q->data.masv) SV x = p->data; p->data = q->data; q->data = x; Xuat(ds);void Xoa
Cuoi(LIST &ds) for(NODE *k = ds.p
Head; k != NULL; k = k ->next) if(k->next == ds.p
Tail) delete ds.p
Tail; k->next = NULL; ds.p
Tail = k; Xuat(ds);int main() list ds; int n; printf("NHAP N: "); scanf("%d",&n); Khoi
Tao(ds); Nhap(ds,n); printf("
DANH SACH SINH VIEN "); Xuat(ds); printf("
DANH SACH SINH VIEN D13CNPM "); SVD13CNPM(ds); printf("
DANH SACH SINH VIEN SAP XEP THEO MA "); Sap
Xep(ds); printf("
DANH SACH SINH VIEN domain authority XOA PHAN TU CUOI "); Xoa
Cuoi(ds);

Facebook Twitter
Linkedin#include%20#include%20struct%20sinhvien%20%20%20%20%20int%20masv;%20%20%20%20char%20tensv%5B20%5D;%20%20%20%20char%20lop%5B20%5D;%20%20%20%20float%20dtk;%20%20%20%20char%20hk%5B15%5D;;typedef%20struct%20sinhvien%20SV;struct%20node%20%20%20%20SV%20data;%20%20%20%20node%20*%20next;;typedef%20struct%20node%20NODE;struct%20list%20%20%20%20NODE%20*p
Head;%20%20%20%20NODE%20*p
Tail;;typedef%20struct%20list%20LIST;void%20Khoi
Tao(LIST%20&ds)%20%20%20%20ds.p
Head%20=%20NULL;%20%20%20%20ds.p
Tail%20=%20NULL;int%20Kiem
Tra
Rong(LIST%20ds)%20%20%20%20if%20(ds.p
Head%20==%20NULL)%20%20%20%20%20%20%20%20return%201;%20%20%20%20%20%20%20%20return%200;NODE*%20Tao
Node(SV%20x)%20%20%20%20%20NODE%20*p;%20%20%20%20p%20=%20new%20NODE;%20%20%20%20if%20(p==NULL)%20%20%20%20%20%20%20%20%20printf%20(KHONG%20DU%20BO%20NHO);%20%20%20%20%20%20%20%20return%20NULL;%20%20%20%20%20%20%20%20p->data=x;%20%20%20%20p->next=NULL;%20%20%20%20return%20p;void%20Chen
Cuoi%20(LIST%20&ds,%20NODE%20*p)%20%20%20%20if%20(ds.p
Head==NULL)%20%20%20%20%20%20%20%20%20ds.p
Head=p;%20%20%20%20%20%20%20%20ds.p
Tail=p;%20%20%20%20%20%20%20%20else%20%20%20%20%20%20%20%20%20ds.p
Tail->next=p;%20%20%20%20%20%20%20%20ds.p
Tail=p;%20%20%20%20void%20Nhap(LIST%20&ds,%20int%20n)%20%20%20%20printf(NHAP%20THONG%20TIN%20SINH%20VIENn);%20%20%20%20for(int%20i%20=%200;%20i%20next)%20%20%20%20%20%20%20%20printf(%dt%20%st%20%st%20%ft%20%sn,%20p->data.masv,%20p->data.tensv,%20p->data.lop,%20p->data.dtk,%20p->data.hk);%20%20%20%20void%20SVD13CNPM(LIST%20ds)%20%20%20%20for(NODE%20*p%20=%20ds.p
Head;%20p!=%20NULL;%20p=p->next)%20%20%20%20%20%20%20%20if(strcmp(p->data.lop,%20D13CNPM)==0)%20%20%20%20%20%20%20%20%20%20%20%20printf(%dt%20%st%20%st%20%ft%20%sn,%20p->data.masv,%20p->data.tensv,%20p->data.lop,%20p->data.dtk,%20p->data.hk);%20%20%20%20%20%20%20%20%20%20%20%20void%20Sap
Xep(LIST%20&ds)%20%20%20%20NODE%20*p,%20*q;%20%20%20%20for(p%20=%20ds.p
Head;%20p%20!=%20ds.p
Tail;%20p=p->next)%20%20%20%20%20%20%20%20for(q%20=%20p->next;%20q%20!=%20NULL;%20q%20=%20q->next)%20%20%20%20%20%20%20%20%20%20%20%20if(p->data.masv%20>%20q->data.masv)%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20SV%20x%20=%20p->data;%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20p->data%20=%20q->data;%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20q->data%20=%20x;%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Xuat(ds);void%20Xoa
Cuoi(LIST%20&ds)%20%20%20%20for(NODE%20*k%20=%20ds.p
Head;%20k%20!=%20NULL;%20k%20=%20k%20->next)%20%20%20%20%20%20%20%20%20%20%20%20if(k->next%20==%20ds.p
Tail)%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20delete%20ds.p
Tail;%20%20%20%20%20%20%20%20%20%20%20%20k->next%20=%20NULL;%20%20%20%20%20%20%20%20%20%20%20%20ds.p
Tail%20=%20k;%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Xuat(ds);int%20main()%20%20%20%20LIST%20ds;%20%20%20%20int%20n;%20%20%20%20printf(NHAP%20N:%20);%20%20%20%20scanf(%d,&n);%20%20%20%20Khoi
Tao(ds);%20%20%20%20Nhap(ds,n);%20%20%20%20printf(n
DANH%20SACH%20SINH%20VIENn);%20%20%20%20Xuat(ds);%20%20%20%20printf(n
DANH%20SACH%20SINH%20VIEN%20D13CNPMn);%20%20%20%20SVD13CNPM(ds);%20%20%20%20printf(n
DANH%20SACH%20SINH%20VIEN%20SAP%20XEP%20THEO%20MAn);%20%20%20%20Sap
Xep(ds);%20%20%20%20printf(n
DANH%20SACH%20SINH%20VIEN%20DA%20XOA%20PHAN%20TU%20CUOIn);%20%20%20%20Xoa
Cuoi(ds);/pre" target="_blank">Pinterest

Danh sách links đơn(Single linked list) là ví dụ cực tốt và đơn giản dễ dàng nhất về kết cấu dữ liệu động sử dụng con trỏ để download đặt. Vị đó, kỹ năng con trỏ là cực kì quan trọng nhằm hiểu biện pháp danh sách links hoạt động, vị vậy ví như bạn chưa có kiến thức về con trỏ thì chúng ta nên học về bé trỏ trước. Bạn cũng cần hiểu một chút ít về cung cấp phát bộ lưu trữ động. Để đơn giản dễ dàng và dễ hiểu, phần nội dung thiết lập danh sách liên kết của bài viết này đang chỉ trình bày về danh sách links đơn.

Danh Mục bài xích Viết

VI. Cài Đặt Danh Sách link Đơn C++VII. Code Danh Sách links Đơn sv C++VIII. Xóa phần tử Trong Danh Sách links Đơn C++IX. Bài bác Tập Danh Sách link Đơn C++

I. Danh Sách links Đơn C++

Danh sách links đơn (Single Linked List) là một kết cấu dữ liệu động, nó là một trong danh sách nhưng mà mỗi phần tử đều link với phần tử đúng sau nó trong danh sách. Mỗi thành phần (được gọi là một trong những node hay nút) vào danh sách links đơn là một cấu trúc có nhì thành phần:

Thành phần dữ liệu: lưu thông tin về phiên bản thân phần tử đó.Thành phần liên kết: lưu add phần tử đứng sau trong danh sách, trả dụ thành phần đó là bộ phận cuối cùng thì thành phần này bằng NULL.

Đặc điểm của danh sách links đơn

Do danh sách links đơn là 1 cấu tạo dữ liệu động, được tạo nên nhờ việc cấp phép động nên nó có một số điểm sáng sau đây:

Được cung cấp phát bộ nhớ lưu trữ khi chạy chương trình
Có thể thay đổi kích thước qua bài toán thêm, xóa phần tử
Kích thước về tối đa phụ thuộc vào vào bộ nhớ lưu trữ khả dụng của RAMCác thành phần được lưu trữ ngẫu nhiên (không liên tiếp) trong RAM

Và vị tính links của thành phần đầu và thành phần đứng sau nó trong danh sách links đơn, nó đem những điểm lưu ý sau:

Chỉ cần nắm được thành phần đầu với cuối là bao gồm thể cai quản được danh sách
Truy cập tới bộ phận ngẫu nhiên cần duyệt từ trên đầu đến địa chỉ đó
Chỉ rất có thể tìm kiếm tuyến tính một trong những phần tửDanh Sách link Đơn C++

II. Nối 2 Danh Sách liên kết Đơn C++

Bài tập C: Nối nhị danh sách link đơn

Bài tập C này khiến cho bạn làm quen dần với biện pháp tạo danh sách link đơn và phương pháp nối hai danh sách links đơn trong C. Để giải bài xích tập này, bản thân sử dụng cấu trúc struct trong C.

Chương trình C

Dưới đây là chương trình C để giải bài xích tập nối nhị danh sách liên kết đơn vào C:

#include #include struct node int data; struct node *next;;struct node *even = NULL;struct node *odd = NULL;struct node *list = NULL;//tao danh sach lien ketvoid insert(int data) // cap phat bo nho mang đến node moi; struct node *link = (struct node*) malloc(sizeof(struct node)); struct node *current; link->data = data; link->next = NULL; if(data%2 == 0) if(even == NULL) even = link; return; else current = even; while(current->next != NULL) current = current->next; // chen liên kết vao phan cuoi cua danh mục current->next = link; else if(odd == NULL) odd = link; return; else current = odd; while(current->next!=NULL) current = current->next; // chen liên kết vao phan cuoi cua list current->next = link; void display(struct node *head) struct node *ptr = head; printf(" =>"); while(ptr != NULL) printf(" %d =>",ptr->data); ptr = ptr->next; printf(" ");void combine() struct node *link; danh mục = even; link = list; while(link->next!= NULL) link = link->next; link->next = odd;int main() int i; for(i=1; i
Biên dịch công tác C bên trên sẽ cho kết quả:

Nối 2 Danh Sách liên kết Đơn C++

III. Đảo Ngược Danh Sách link Đơn C++

Đảo ngược list liên kết

Với vận động này, bạn cần phải cẩn thận. Họ cần tạo nên nút đầu (head) trỏ tới nút cuối cùng và đảo ngược toàn bộ danh sách liên kết.

Đảo Ngược Danh Sách link Đơn C++

Đầu tiên, bọn họ duyệt cho tới phần cuối của danh sách. Nút này đang trỏ tới NULL. Bây giờ điều phải làm là tạo cho nút cuối này trỏ tới nút phía đằng trước của nó.

Đảo Ngược Danh Sách links Đơn C++

Chúng ta phải bảo đảm an toàn rằng nút sau cùng này sẽ không trở nên thất lạc, do đó họ sẽ sử dụng một trong những nút lâm thời (temp node – hệt như các biến chuyển tạm trung gian để cất giữ giá trị). Tiếp theo, họ sẽ khiến cho từng nút phía trái sẽ trỏ tới nút trái của chúng.

Đảo Ngược Danh Sách liên kết Đơn C++

Sau đó, nút trước tiên sau nút head vẫn trỏ tới NULL.

Đảo Ngược Danh Sách links Đơn C++

Chúng ta sẽ khiến cho nút head trỏ cho tới nút thứ nhất mới vì sử dụng những nút tạm.

Đảo Ngược Danh Sách links Đơn C++

Bây giờ danh sách liên kết đã bị đảo ngược.

Chương trình minh họa Danh sách liên kết (Linked List) vào C

#include #include #include #include struct node int data; int key; struct node *next;;struct node *head = NULL;struct node *current = NULL;//hien thi danh sachvoid print
List() struct node *ptr = head; printf(" < "); //bat dau tu phan dau danh sach while(ptr != NULL) printf("(%d,%d) ",ptr->key,ptr->data); ptr = ptr->next; printf(" >");//chen links tai vi tri dau tienvoid insert
First(int key, int data) //tao mot links struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; //tro links nay toi first node cu link->next = head; //tro first toi first node moi head = link;//xoa phan tu dau tienstruct node* delete
First() //luu tham chieu toi first liên kết struct node *temp
Link = head; //danh dau next toi first links la first head = head->next; //tra ve liên kết bi xoa return temp
Link;//kiem tra danh sách co trong giỏi khongbool is
Empty() return head == NULL;int length() int length = 0; struct node *current; for(current = head; current != NULL; current = current->next) length++; return length;//tim mot link voi key domain authority chostruct node* find(int key) //bat dau tim tu first liên kết struct node* current = head; //neu menu la vào if(head == NULL) return NULL; //duyet qua menu while(current->key != key) //neu day la last node if(current->next == NULL) return NULL; else //di chuyen toi next liên kết current = current->next; //neu tim cầm du lieu, tra ve links hien tai return current;//xoa mot liên kết voi key da chostruct node* delete
Key(int key) //bat dau tu first liên kết struct node* current = head; struct node* previous = NULL; //neu menu la trong if(head == NULL) return NULL; //duyet qua danh sách while(current->key != key) //neu day la last node if(current->next == NULL) return NULL; else //luu tham chieu toi link hien tai previous = current; //di chuyen toi next liên kết current = current->next; //cap nhat links if(current == head) //thay doi first de tro toi next link head = head->next; else //bo qua link hien tai previous->next = current->next; return current;// đắm đuối sap xepvoid sort() int i, j, k, temp
Key, temp
Data ; struct node *current; struct node *next; int kích cỡ = length(); k = kích thước ; for ( i = 0 ; i next ; for ( j = 1 ; j data > next->data ) temp
Data = current->data ; current->data = next->data; next->data = temp
Data ; temp
Key = current->key; current->key = next->key; next->key = temp
Key; current = current->next; next = next->next; }// mê mệt dao nguoc listvoid reverse(struct node** head_ref) struct node* prev = NULL; struct node* current = *head_ref; struct node* next; while (current != NULL) next = current->next; current->next = prev; prev = current; current = next; *head_ref = prev;main() insert
First(1,10); insert
First(2,20); insert
First(3,30); insert
First(4,1); insert
First(5,40); insert
First(6,56); printf("Danh sach ban dau: "); //in danh sach print
List(); while(!is
Empty()) struct node *temp = delete
First(); printf("
Gia tri bi xoa:"); printf("(%d,%d) ",temp->key,temp->data); printf("
Danh sach sau thời điểm da xoa gia tri: "); print
List(); insert
First(1,10); insert
First(2,20); insert
First(3,30); insert
First(4,1); insert
First(5,40); insert
First(6,56); printf("
Phuc hoi danh sach: "); print
List(); printf(" "); struct node *found
Link = find(4); if(found
Link != NULL) printf("Tim thay phan tu: "); printf("(%d,%d) ",found
Link->key,found
Link->data); printf(" "); else printf("Khong tim gắng phan tu."); delete
Key(4); printf("Danh sach, sau thời điểm xoa mot phan tu: "); print
List(); printf(" "); found
Link = find(4); if(found
Link != NULL) printf("Tim cầm cố phan tu: "); printf("(%d,%d) ",found
Link->key,found
Link->data); printf(" "); else printf("Khong tim núm phan tu."); printf(" "); sort(); printf("Danh sach sau thời điểm duoc sap xep: "); print
List(); reverse(&head); printf("
Danh sach sau thời điểm bi dao nguoc: "); print
List();Kết quả

Biên dịch và chạy chương trình C bên trên sẽ mang đến kết quả:

Đảo Ngược Danh Sách liên kết Đơn C++

IV. Nhập Xuất Danh Sách links Đơn C++

Tùy theo phong cách 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 gồm phần đơn giản hơn

Mình đang nhập vào phần tử cho danh sách links đơn bởi con trỏ. Nếu như nhập vào bằng 0 thì vẫn dừng nhập. Thêm bộ phận vào danh sách mình thực hiện hàm chèn cuối Insert_Last

// Hàm nhập list số nguyên từ keyboard void Input(List &L) Init(L); tòa tháp x; int i=1; do cout>x; if (x!=0) Insert_Last(L,x); i++; while (x!=0); // giả dụ nhập x = 0 thì giới hạn nhập //Ban teo the dung cach khac

V. Bố trí Danh Sách link Đơn C++

Ở phần sắp xếp phần tử trong danh sách liên kết đơn, mình sẽ tiến hành sắp xếp bằng cách so sánh và thay đổi giá trị data chứ không đổi khác Node. Có nghĩa là chỉ so sánh các giá trị data rồi sắp tới xếp, những Node vẫn không thay đổi không dịch chuyển.

Sắp Xếp Danh Sách link Đơn C++

Thao tác thu xếp trong list về căn bạn dạng tương tự tựa như những thuật toán thu xếp khác, dễ dàng và đơn giản chỉ là ưng chuẩn từng thành phần rồi so sánh với nhau, sau ấy hoán đổi địa điểm của chúng.

Đầu tiên ta có một vòng lặp For thực hiện biến p
Tmp để lặp từng phần tử trong danh sách, vòng lặp For đồ vật hai sử dụng biến p
Tmp2 để lặp từng thành phần trong danh sách.

Nếu p
Tmp > p
Tmp2 thì hoán đổi địa điểm giữa chúng, nếu p
Tmp p
Next) //for loop sản phẩm hai for(Node *p
Tmp2=p
Tmp->p
Next;p
Tmp2!=NULL;p
Tmp2=p
Tmp2->p
Next) if(p
Tmp->data>p
Tmp2->data) // nếu giá trị trước > quý hiếm sau thì hoán thay đổi hai địa điểm int tmp=p
Tmp->data; p
Tmp->data=p
Tmp2->data; p
Tmp2->data=tmp;

VI. Cài Đặt Danh Sách link Đơn C++

Trước dịp đi vào thiết lập danh sách links đơn, hãy chắc chắn rằng rằng chúng ta đã nắm rõ phần con trỏ và cấp phép động vào C++. Bởi vì danh sách links đơn là một cấu tạo dữ liệu động, nếu như khách hàng không nắm rõ con trỏ và cấp phép động sẽ tương đối khó để bạn hiểu được nội dung bài viết này. Nếu bạn cảm thấy không tự tin, hãy dành riêng ít thời gian để xem nội dung bài viết này của mình. Còn bây chừ thì bước đầu thôi!

Tạo node

Danh sách links đơn được tạo thành thành từ nhiều node, vì chưng đó, chúng ta sẽ thuộc đi từ bỏ node trước. Một node bao gồm hai yếu tắc là thành phần tài liệu và yếu tắc liên kết. Yếu tắc dữ liệu hoàn toàn có thể là kiểu dữ liệu có sẵn hoặc chúng ta tự khái niệm (struct hay class…), trong nội dung bài viết này để đơn giản mình sẽ dùng kiểu int bỏ phần dữ liệu. Thành phần liên kết là add đương nhiên sẽ là nhỏ trỏ, bé trỏ này trỏ đến node tiếp theo, vị đó, con trỏ này là nhỏ trỏ trỏ vào 1 node.

struct Node int data; Node* next;;Để tạo ra một node mới, ta thực hiện cấp phạt động mang đến node mới, khởi sản xuất giá trị lúc đầu và trả về địa chỉ của node mới được cấp cho phát.

Tạo danh sách links đơn

Ta đã sở hữu được thành phần tạo nên danh sách liên kết đơn là node, tiếp theo họ cần làm chủ chúng bằng phương pháp biết được thành phần đầu và cuối. Vị mỗi bộ phận đều links với phần tử kế vậy bắt buộc tả chỉ cần biết bộ phận đầu và cuối là gồm thể cai quản được list này. Vậy dễ dàng ta phải tạo 1 kết cấu lưu trữ showroom phần tử đầu (head) và thành phần cuối (hay phần tử đuôi tail).

struct Linked
List Node* head; Node* tail;;Khi bắt đầu tạo danh sách, danh sách sẽ không còn có bộ phận nào, do đó head và tail không trỏ vào đâu cả, ta vẫn gán chúng bởi NULL. Ta xây dựng hàm tạo danh sách như sau:

void Create
List(Linked
List& l) l.head = NULL; l.tail = NULL;Bây tiếng để tạo một danh sách, ta làm như sau:

Linked
List list;Create
List(list); // Gán head với tail bởi NULL

Thêm bộ phận vào danh sách

Thêm vào đầu

Để thêm node vào đầu danh sách, trước hết ta đề nghị kiếm tra xem list đó tất cả rỗng tuyệt không, nếu danh sách rỗng, ta chỉ cần gán head và tail của list bằng node đó. Trái lại nếu list không rỗng, ta triển khai trỏ thành phần links vào head, tiếp nối gán lại head bằng node mới.

Thêm phần tử vào đầu danh sách links đơn

Như vào hình trên, họ thêm node gồm data bởi 0 vào danh sách. Ta thực hiện trỏ next của node đó vào head của list (chính là node đầu tiên của danh sách có data bởi 1), tiếp nối ta trỏ head vào node gồm data 0 vừa được thêm. Vậy là bộ phận đó đã nằm tại vị trí đầu list rồi.

Thêm vào cuối

Tương tự, để thêm node vào cuối danh sách, thứ nhất ta review xem danh sách rỗng xuất xắc không, trống rỗng thì gán head và tail đều bằng node mới. Còn nếu như không rỗng, ta triển khai trỏ tail->next vào node mới, kế tiếp gán lại tail bởi node mới (vì hiện giờ node mới thêm đó là tail).

Thêm phần tử vào cuối danh sách links đơn

Trong hình trên, bọn họ thực hiện nay thêm node bao gồm data bởi 6 vào danh sách. Tail hiện tại là node gồm data 5, triển khai gán tail->next bằng node mới để nối thêm nó vào đuôi danh sách, hôm nay node bắt đầu trở thành thành phần cuối list nên ta gán tail lại bởi node mới.

Thêm vào sau cùng node bất kỳ

Để thêm một node p vào sau node q bất kỳ, thứ nhất ta cần kiếm tra xem node q gồm NULL xuất xắc không, nếu như node q là NULL tức là danh sách rỗng, vậy thì ta sẽ phân phối đầu danh sách. Trường hợp node q ko NULL, có nghĩa là tồn tại trong danh sách, ta tiến hành trỏ p->next = q->next, tiếp nối q->next = phường Tiếp theo họ kiểm tra xem node q trước đó liệu có phải là node cuối hay không, trường hợp node q là node cuối thì thêm p vào, p. Sẽ thành node cuối nên ta gán lại tail = p.

Thêm thành phần vào sau nút Q vào danh sách liên kết đơn

Trong hình trên, ta thêm node tất cả data bởi 4 (node p) vào sau node bao gồm data bởi 3 (node q). Ta trỏ next của node p. Vào next của node q có nghĩa là node bao gồm data bởi 5, sau đó trỏ next của node q vào node p vậy là node phường đã được tiếp tế danh sách.

Xóa thành phần khỏi danh sách

Xóa nghỉ ngơi đầu

Để xóa thành phần ở đầu danh sách, ta đánh giá xem list đó có rỗng xuất xắc không, nếu rỗng, ta không đề nghị xóa, trả về kết quả là 0. Nếu list không rỗng, ta triển khai lưu node head lại, tiếp nối gán head bằng next của node head, tiếp nối xóa node head đi. Tiếp sau ta yêu cầu kiểm tra xem danh sách vừa bị xóa đi node head có rỗng tuyệt không, trường hợp rỗng ta gán lại tail bằng NULL luôn kế tiếp trả về kết quả 1.

Lưu ý trước khi xóa node head đi, ta dùng vươn lên là tham chiếu x để lưu trữ lại giá trị của node bị hủy nhằm sử dụng.

Xóa thành phần đầu danh sách link đơn

Trong hình trên, mình thực hiện xóa node trước tiên có data bởi 0. Bản thân trỏ head mang lại next của node 0 (hiện vẫn là head), thì head hôm nay sẽ là node 1, kế tiếp mình hủy đi node 0 là được.

Xóa sống sau node bất kỳ

Để xóa một node phường sau node q bất kỳ, ta kiểm tra xem node q gồm NULL hay không, trường hợp node q NULL thì ko tồn trên trong danh sách, cho nên trả về 0, không xóa. Giả dụ node q không giống NULL tuy vậy next của q là NULL, tức là p bằng NULL thì không xóa, trả về 0 (do sau q không có node như thế nào cả, q là tail). Nếu node p. Tồn tại, ta triển khai kiểm tra xem node p. Có đề xuất là tail tốt không, giả dụ node phường là tail thì gán lại tail là q, tức là node trước đó để xóa node phường đi.

Trong hình trên, ta triển khai xóa node gồm data 3 (node p) sau node tất cả data 2 (node q). Ta trỏ next của node q vào next của node p có nghĩa là node có data 4, tiếp nối xóa node p đi là xong.

Duyệt danh sách và in

Sau khi bao gồm các thao tác làm việc thêm, xóa, bạn cũng có thể in ra danh sách để chất vấn xem có vận động đúng xuất xắc không. Để in danh sách, ta duyệt từ đầu đến cuối list và in ra trong lúc duyệt. Ta gán một node bằng head, sau đó kiểm tra xem node đó gồm NULL hay không, không thì in ra data của node đó, tiếp đến gán tiếp node đó bởi next của chính nó tức node đó hiện giờ là node tiếp theo, cứ như vậy cho đến hết.

Lấy giá trị node bất kỳ

Để lấy giá trị phần tử trong danh sách, ta tiến hành duyệt tương tự như như khi in phần tử. Ta sẽ tạo một trở thành đếm để hiểu vị trí hiện tại tại, để mắt qua những node cho đến khi node bằng NULL hoặc trở nên đếm bởi với địa chỉ node nên lấy. Kiểm tra xem nếu như node khác NULL và thay đổi đếm bằng vị trí đề xuất lấy, ta đã trả về add của node đó, ngược lại trả về NULL (danh sách rỗng hoặc là vị trí bắt buộc lấy nằm bên cạnh phạm vi của danh sách).

Tìm kiếm phần tử trong danh sách

Ý tưởng tìm kiếm thành phần cũng là coi xét danh sách, nếu như chưa tìm thấy thì liên tiếp duyệt. Sau khi hoàn thành duyệt, ta chỉ cần kiểm tra xem node chú tâm có bằng NULL tốt không, nếu không tức là đã search thấy, ta vẫn trả về showroom của node đó.

Đếm số bộ phận của danh sách

Đếm số bộ phận thì cũng tương tự, ta vận dụng duyệt từ trên đầu đếm cuối với đếm số node.

Xóa danh sách

Để xóa danh sách, ta nên hủy toàn bộ các node tức là duyệt và hủy từng node. Ở phía trên mình sẽ cần sử dụng lại hàm Remove
Head. Đầu tiên, ta gán một node bằng head, khám nghiệm nếu node kia khác NULL thì điện thoại tư vấn Remove
Head cùng gán lại node bởi head tiếp, cứ lặp như vậy cho đến khi node đó NULL thì thôi. Sau khi xóa hết tất cả thành phần thì gán lại tail bằng NULL.

VII. Code Danh Sách links Đơn sv C++

Đề bài: gây ra chương trình làm chủ sinh viên bởi DSLK đơn

Cho 1 sinh viên bao gồm cấu trúc: mã (int), tên (char *). Cần sử dụng danh sách liên kết đơn với nhỏ trỏ phead để thao tác:

Khởi tạo menu dạng bé trỏ
Thêm node vào cuối danh sách
Sắp xếp theo mã
Xóa node

Chương trình làm chủ sinh viên áp dụng DSLK đơn

Chúng ta đang lần lượt tạo cấu trúc sinh viên, kết cấu danh sách links đơn và các thao tác làm việc liên quan.

Đầu tiên họ buộc phải khởi tạo một cấu trúc sinh viên cùng với mã số sv ma cùng tên sinh viên ten.

//tao cau truc sinh vienstruct Sinh
Vien int ma; char ten<150>;;Tiếp mang lại tạo cấu trúc dữ liệu của danh sách links đơn với mức giá trị data và con trỏ p
Next. Khởi sinh sản giá trị cho p
Head cùng p
Tail bằng NULL.

//tao cau truc danh sach lien ket donstruct Node Sinh
Vien *data; Node *p
Next;;struct Single
List Node *p
Head;;//khoi tao danh sach lien ket donvoid Initialize(Single
List *&list) list=new Single
List; list->p
Head=NULL;Tạo 1 hàm Nhap
Sinh
Vien() dùng kết cấu Sinh
Vien để nhập những tin tức của sv như: MSSV cùng tên sinh viên

Sinh
Vien *Nhap
Sinh
Vien() Sinh
Vien *sv=new Sinh
Vien; cout>sv->ma; cin.ignore(); coutten); return sv;Bây giờ bọn chúng ta bước đầu tạo Node với các thông tin của kết cấu Sinh
Vien, sau đó thêm Node vào thời điểm cuối danh sách.

//tao node sinh vien
Node *Create
Node(Sinh
Vien *sv) Node *p
Node=new Node; if(p
Node!=NULL) p
Node->data=sv; p
Node->p
Next=NULL; else coutp
Head==NULL) list->p
Head=p
Node; else Node *p
Tmp=list->p
Head; while(p
Tmp->p
Next!=NULL) p
Tmp=p
Tmp->p
Next; p
Tmp->p
Next=p
Node; Sau dịp thêm Node vào danh sách ta triển khai những làm việc theo kiến nghị của đề bài. Đầu tiên là vấn đề sắp xếp các sinh viên theo MSSV.

Ở bài tìm tìm và sắp xếp trong danh sách liên kết đơn tôi đã giới thiệu các bạn thao tác chuẩn bị xếp. Nhờ vào đó ta chỉ cần đổi khác một chút sẽ có được ngay hàm sắp xếp Sort
List() theo MSSV.

void Sort
List(Single
List *&list) for(Node *p
Tmp=list->p
Head;p
Tmp!=NULL;p
Tmp=p
Tmp->p
Next) for(Node *p
Tmp2=p
Tmp->p
Next;p
Tmp2!=NULL;p
Tmp2=p
Tmp2->p
Next) Sinh
Vien *sv
Tmp=p
Tmp->data; Sinh
Vien *sv
Tmp2=p
Tmp2->data; if(sv
Tmp2->mama) int ma=sv
Tmp->ma; char ten<150>; strcpy(ten,sv
Tmp->ten); sv
Tmp->ma=sv
Tmp2->ma; strcpy(sv
Tmp->ten,sv
Tmp2->ten); sv
Tmp2->ma=ma; strcpy(sv
Tmp2->ten,ten); Tương tự như hàm chuẩn bị xếp, nhằm xóa một sinh viên nhờ vào tên ta triển khai vòng lặp while lặp từng bộ phận trong danh sách. Nếu phần tử đó trùng với bộ phận được nhập vào từ keyboard ta triển khai delete thành phần đó ra khỏi danh sách.

void Remove
Node(Single
List *&list,int ma) Node *p
Del=list->p
Head; if(p
Del==NULL) coutdata; if(sv->ma==ma) break; p
Pre=p
Del; p
Del=p
Del->p
Next; if(p
Del==NULL) coutp
Head) list->p
Head=list->p
Head->p
Next; p
Del->p
Next=NULL; delete p
Del; p
Del=NULL; else p
Pre->p
Next=p
Del->p
Next; p
Del->p
Next=NULL; delete p
Del; p
Del=NULL; Sau khi thực hiện tạo các thao tác, ta chỉ cần tạo hàm main() và gọi các thao tác đó ra để sử dụng.

int main(int argc, char** argv) Single
List *list; Initialize(list); Sinh
Vien *teo=Nhap
Sinh
Vien(); Insert
Last(list,teo); Sinh
Vien *ty=Nhap
Sinh
Vien(); Insert
Last(list,ty); Sinh
Vien *bin=Nhap
Sinh
Vien(); Insert
Last(list,bin); Print
List(list); Sort
List(list); cout>ma; Remove
Node(list,ma); coutFull code:

#include #include #include using namespace std;//tao cau truc sinh vienstruct Sinh
Vien int ma; char ten<150>;;//tao cau truc danh sach lien ket donstruct Node Sinh
Vien *data; Node *p
Next;;struct Single
List Node *p
Head;;//khoi tao danh sach lien ket donvoid Initialize(Single
List *&list) list=new Single
List; list->p
Head=NULL;//nhap thong tin sinh vien
Sinh
Vien *Nhap
Sinh
Vien() Sinh
Vien *sv=new Sinh
Vien; cout>sv->ma; cin.ignore(); coutten); return sv;//tao node sinh vien
Node *Create
Node(Sinh
Vien *sv) Node *p
Node=new Node; if(p
Node!=NULL) p
Node->data=sv; p
Node->p
Next=NULL; else coutp
Head==NULL) list->p
Head=p
Node; else Node *p
Tmp=list->p
Head; while(p
Tmp->p
Next!=NULL) p
Tmp=p
Tmp->p
Next; p
Tmp->p
Next=p
Node; //hien thi danh sachvoid Print
List(Single
List *list) Node *p
Tmp=list->p
Head; if(p
Tmp==NULL) coutdata; coutmatenp
Next; //sap xepvoid Sort
List(Single
List *&list) for(Node *p
Tmp=list->p
Head;p
Tmp!=NULL;p
Tmp=p
Tmp->p
Next) for(Node *p
Tmp2=p
Tmp->p
Next;p
Tmp2!=NULL;p
Tmp2=p
Tmp2->p
Next) Sinh
Vien *sv
Tmp=p
Tmp->data; Sinh
Vien *sv
Tmp2=p
Tmp2->data; if(sv
Tmp2->mama) int ma=sv
Tmp->ma; char ten<150>; strcpy(ten,sv
Tmp->ten); sv
Tmp->ma=sv
Tmp2->ma; strcpy(sv
Tmp->ten,sv
Tmp2->ten); sv
Tmp2->ma=ma; strcpy(sv
Tmp2->ten,ten); //xoavoid Remove
Node(Single
List *&list,int ma) Node *p
Del=list->p
Head; if(p
Del==NULL) coutdata; if(sv->ma==ma) break; p
Pre=p
Del; p
Del=p
Del->p
Next; if(p
Del==NULL) coutp
Head) list->p
Head=list->p
Head->p
Next; p
Del->p
Next=NULL; delete p
Del; p
Del=NULL; else p
Pre->p
Next=p
Del->p
Next; p
Del->p
Next=NULL; delete p
Del; p
Del=NULL; int main(int argc, char** argv) Single
List *list; Initialize(list); Sinh
Vien *teo=Nhap
Sinh
Vien(); Insert
Last(list,teo); Sinh
Vien *ty=Nhap
Sinh
Vien(); Insert
Last(list,ty); Sinh
Vien *bin=Nhap
Sinh
Vien(); Insert
Last(list,bin); Print
List(list); Sort
List(list); cout>ma; Remove
Node(list,ma); coutKết quả:

Code Danh Sách liên kết Đơn sinh viên C++

VIII. Xóa phần tử Trong Danh Sách links Đơn C++

Trong chỉ dẫn này bản thân sẽ reviews tới các bạn cách xóa Node trong danh sách link đơn.

Chúng ta sẽ thuộc nhau tò mò 3 ví dụ lúc xóa 1 Node khỏi danh sách liên kết đơn:

Xóa Node sống đầu danh sách link đơn.Xóa Node nghỉ ngơi cuối danh sách links đơn.Xóa Node trung tâm danh sách link đơn.

+ Xóa Node ngơi nghỉ đầu danh sách liên kết đơn

Trong ngôi trường hợp họ muốn xóa một Node, nhưng Node này lại nằm sinh hoạt đầu danh sách. Đây là 1 trường hợp sệt biệt, chúng ta hãy xem quá trình thực hiện nay sau đây:

Giả sử bọn họ có một Node p
Del là Node yêu cầu xóa với một danh sách link đơn.

Xóa Node sinh sống đầu danh sách links đơn

Bước 1: vì Node phải xóa sống đầu danh sách, có nghĩa là ngay node p
Head. Bởi vậy bọn họ cần dịch chuyển p
Head từ p
Del lịch sự Node kế tiếp: list.p
Head = list.p
Head -> p
Next

Xóa Node nghỉ ngơi đầu danh sách liên kết đơn

Bước 2: Sau khi di chuyển p
Head quý phái Node kế tiếp, họ sẽ ngắt mối links giữa p
Del với Node phía sau nó: p
Del -> p
Next = Null.

Xóa Node sinh sống đầu danh sách liên kết đơn

Bước 3: bây chừ p
Del không hề liên kết với bất cứ Node như thế nào trong danh sách nữa, bọn họ đã rất có thể xóa Node này. Delete p
Del

Xóa thành phần Trong Danh Sách liên kết Đơn C++

// nếu như p
Del == list.p
Head, có nghĩa là số nên xóa sống đầu danh sách if(p
Del == list.p
Head) list.p
Head = list.p
Head -> p
Next; p
Del -> p
Next = NULL; delete p
Del; p
Del = NULL;

+ Xóa Node sinh hoạt cuối danh sách link đơn.

Trong trường hợp Node hy vọng xóa lại nằm tại cuối danh sách, tương tự như vấn đề xóa sinh hoạt đầu danh sách. Ta chỉ cần di gửi p
Tail về Node trước đó (p
Pre) và biến đổi p
Next = NULL.

Xóa Node ngơi nghỉ cuối danh sách liên kết đơn

Sau khi di chuyển p
Tail về Node trước đó cùng ngắt mối liên kết giữa p
Pre cùng với p
Del, ta thực hiện xóa Node p
Del: delete p
Del

//Nếu p
Del == list.p
Tail, có nghĩa là số buộc phải xóa sinh sống cuối list if(p
Del -> p
Next == NULL) list.p
Tail = p
Pre; p
Pre -> p
Next = NULL; delete p
Del; p
Del = NULL;

+ Xóa Node trung tâm danh sách links đơn.

Và trường thích hợp cuối cùng, lúc xóa Node cơ mà Node đó không ở đầu cũng ko nằm cuối danh sách, ta thực hiện các bước như sau:

Khi ta muốn xóa một Node ở giữa danh sách, thứ nhất ta cần xác định Node yêu cầu xóa p
Del và Node đứng trước nó p
Pre.

Xóa Node trọng điểm danh sách liên kết đơn.

Sau khi khẳng định được p
Del với p
Pre, ta biến hóa mối liên kết giữa p
Pre đến p
Tail (p
Pre -> p
Next = p
Del -> p
Next) và đến p
Del -> p
Next == NULL. Các bạn có thể xem phía mũi tên để hiểu được các bước thực hiện của nó.

Xóa Node ở giữa danh sách links đơn.

Ta có thể xóa Node p
Del khi sẽ ngắt mối link giữa nó với những Node khác: delete p
Del

// với trường hợp cuối cùng số hy vọng xóa nằm ở vị trí giữa list else p
Pre -> p
Next = p
Del -> p
Next; p
Del -> p
Next = NULL; delete p
Del; p
Del = NULL;

+ lấy một ví dụ xóa Node trong danh sách links đơn

Chúng ta vẫn sử dụng dữ liệu ở lấy ví dụ trước để thực hiện xóa cho ví dụ này, vừa có thể ôn lại kiến thức cũ vừa áp dụng kỹ năng và kiến thức mới.

#include using namespace std;/* Khai báo giá trị data và con trỏ p
Next trỏ tới phần tử kế tiếp */struct Node int data;// cực hiếm data của node Node *p
Next;// con trỏ p
Next; /* Khai báo Node đầu p
Head và Node cuối p
Tail*/struct Single
List Node *p
Head; //Node đầu p
Head Node *p
Tail; // Node cuối p
Tail; /* khởi chế tạo giá trị mang lại Node đầu cùng Node cuối */void Initialize(Single
List &list) list.p
Head=list.p
Tail=NULL;// khởi chế tạo giá trị mang đến Node đầu cùng Node cuối là Null /* Đếm số phần tử trong danh sách */ int Size
OfList(Single
List list) Node *p
Tmp=list.p
Head; int n
Size=0; while(p
Tmp!=NULL) p
Tmp=p
Tmp->p
Next; n
Size++; return n
Size; /* chế tạo Node vào danh sách links đơn */Node *Create
Node(int d) Node *p
Node=new Node; //sử dụng p
Node để tạo ra một Node new if(p
Node!=NULL) // giả dụ p
Node != Null, tức là p
Node có giá trị thì p
Node->data=d; // gán cực hiếm data mang đến d p
Node->p
Next=NULL;// cùng cho con trỏ p
Next trỏ tới quý hiếm Null else // nếu như p
Node == Null, tức là p
Node không có giá trị thì xuất thông tin coutp
Next=list.p
Head; list.p
Head=p
Node; /* chèn node vào thời điểm cuối danh sách */void Insert
Last(Single
List &list,int d) Node *p
Node=Create
Node(d); if(list.p
Tail==NULL) list.p
Head=list.p
Tail=p
Node; else list.p
Tail->p
Next=p
Node; list.p
Tail=p
Node; /* chèn node vào giữa list */void Insert
Mid(Single
List &list, int pos, int d) // ví như pos = Size
OfList(list)) coutp
Next; i++; //sau khi tìm được thì biến hóa con trỏ p
Next p
Pre ->p
Next=p
Node; p
Node->p
Next=p
Ins; /* xóa node ngoài danh sách links */void Remove
Node(Single
List &list, int d) Node *p
Del = list.p
Head; // tạo một node p
Del để xóa //Nếu p
Del == Null thì danh sách rỗng if(p
Del == NULL) cout data == d) break; p
Pre = p
Del; p
Del = p
Del -> p
Next; //Nếu p
Del == null có nghĩa là không tìm thấy số đề xuất xóa if(p
Del == NULL) cout p
Next; p
Del -> p
Next = NULL; delete p
Del; p
Del = NULL; //Nếu p
Del == list.p
Tail, tức là số yêu cầu xóa làm việc cuối list else if(p
Del -> p
Next == NULL) list.p
Tail = p
Pre; p
Pre -> p
Next = NULL; delete p
Del; p
Del = NULL; // với trường hợp cuối cùng số ý muốn xóa nằm ở vị trí giữa danh sách else p
Pre -> p
Next = p
Del -> p
Next; p
Del -> p
Next = NULL; delete p
Del; p
Del = NULL; } /* hàm xuất dữ liệu */void Print
List(Single
List list) Node *p
Tmp=list.p
Head; if(p
Tmp==NULL) coutdatap
Next; int main() { Single
List list; Initialize(list); //Thêm node đầu list Insert
First(list, 5); Insert
First(list, 7); Insert
First(list, 3); coutKết quả:

Ví dụ xóa Node vào danh sách liên kết đơn

IX. Bài Tập Danh Sách links Đơn C++

Bài tập danh sách link đơn dưới đó là 1 dạng bài xích tập tổng hợp giúp những chúng ta ôn luyện lại kỹ năng và kiến thức về danh sách link đơn cũng như các kiến thức và kỹ năng khác về thiết kế C. Sau bài học này, lân cận kiến thức về danh sách link đơn, bạn cũng trở thành nắm được:

Đọc ghi tệp trong ngôn từ CCách xử lý tài liệu văn bản trong C: bóc tách chuỗi, chuyển chuỗi về số, …Làm vấn đề với kiểu tài liệu tự có mang (structure)Và những kiến thức căn bản khác của thiết kế C

Đề bài tập danh sách link đơn

Viết công tác trong ngữ điệu C triển khai các nên sau:

Khai báo kết cấu dữ liệu để tổ chức triển khai danh sách liên kết đơn làm chủ các tỉnh/thành phố của Việt Nam. Tin tức của mỗi tỉnh/thành phố gồm những: Mã tỉnh, thương hiệu tỉnh, diện tích, dân số.Cài để các thao tác làm việc cơ phiên bản (thêm tại phần bất kỳ; sửa, xóa theo mã (code), phê duyệt danh sách).Tính tổng diện tích của toàn bộ các tỉnh thành.Tìm địa điểm của node của thức giấc có diện tích s lớn nhất.Tìm tỉnh/thành phố có dân số lớn nhất.Sắp xếp danh sách theo mã tỉnh/thành phố.Sắp xếp danh sách tăng đột biến theo diện tích.

Yêu cầu:

Viết chương trình ví dụ hóa những tính năng trên, người sử dụng rất có thể tương tác qua menu chất nhận được lựa chọn tính năng mà chúng ta muốn.Ban đầu, list tỉnh/thành phố được nhập tự động từ 1 tập tin (Text file .txt) mang đến trước có nội dung

Lời giải bài xích tập danh sách liên kết đơn

+ Xây dựng các kiểu dữ liệu cần thiết

Chúng ta yêu cầu định nghĩa kiểu tài liệu City theo yêu cầu của đề bài, bao gồm có các trường mã (code), thương hiệu (name), diện tích (area) và dân số (population).Chúng ta cũng cần được định nghĩa vẻ bên ngoài dữ liệu cho 1 Node của danh sách liên kết, mỗi Node sẽ gồm dữ liệu và bé trỏ next.Trong bài xích này, mình mang sử code (mã tỉnh,thành phố) là ko trùng lặp cần sẽ bỏ lỡ bước kiểm tra.

// Khai báo kiểu cấu trúc Citystruct city int code; char name<100>; float area; int population;;// Định nghĩa đến kiểu "struct City" 1 tên mới ngắn gọn gàng hơn, thay do khai báo đẳng cấp "struct City" thì ta chỉ việc dùng "City"typedef struct đô thị City; // Khai báo kiểu kết cấu Linked
Liststruct Linked
List thành phố city; struct Linked
List *next; ; // Định nghĩa mang đến kiểu "struct Linked
List" 1 tên bắt đầu ngắn gọn hơn, thay vị khai báo hình dạng "struct Linked
List" thì ta chỉ cần dùng "Node" typedef struct Linked
List *Node;+ Xây dựng các hàm khởi tạo

Với danh sách liên kết, họ cũng cần khởi chế tạo ra Node đầu tiên cho nó, vấn đề khởi sinh sản rất dễ dàng và đơn giản chỉ bằng cách gán Node đó bằng NULL, tức là chưa xuất hiện dữ liệu (chưa tất cả Node như thế nào cả)

// Hàm khởi tạo thành Node trước tiên của Linked
List
Node init
Head() Node head; head = NULL; return head;Chúng ta cũng trở nên cần hàm khởi sinh sản 1 Node khi đã có tài liệu của Node đó. Sau thời điểm khởi sản xuất thì chúng ta cũng có thể thêm nó vào danh sách. // Hàm tạo mới 1 Node trong Linked
List Node create
Node(City city) Node temp; // Khai báo 1 Node temp = (Node)malloc(sizeof(struct Linked
List)); // cấp phép vùng nhớ mang lại Node temp->next = NULL;// mang lại next trỏ tới NULL temp->city = city; // Gán giá bán trị mang đến Node return temp;Lưu ý: Ta buộc phải cho bé trỏ next của Node được khởi tạo bởi NULL, có nghĩa là chưa trỏ tới đâu. Tránh sự cố nó trỏ lộn xộn trong bộ nhớ.

Chúng ta cần phải có 1 hàm khởi chế tạo ra giá trị cho kiểu thành phố đã tư tưởng ở bên trên qua stdin (nhập tự console). Tại sao là vày chương trình của chúng ta có chức năng thêm, sửa dữ liệu của một Node. Lúc đó, ta sẽ call tới hàm này để sinh sản dữ liệu thông qua stdin.

City create
City() city new
City; printf("Nhap code: "); scanf("%d", &new
City.code); printf("Nhap ten: "); getchar(); // làm lơ " " trong bộ đệm fgets(new
City.name, 100, stdin); // Xóa sinh sống cuối chuỗi vừa nhập nếu có if ((p=strchr(new
City.name, " ")) != NULL) *p = ""; printf("Nhap dien tich: "); scanf("%f", &new
City.area); printf("Nhap dan so: "); scanf("%d", &new
City.population); return new
City;Lưu ý:

Chúng ta bắt buộc hàm getchar() nhằm xóa cỗ đệm, cụ thể là xóa khỏi ký từ ‘ ’ còn sót ngơi nghỉ lần nhập mã tỉnh/thành phố trước đó. Nếu không xóa, hàm nhập chuỗi sẽ nhận ra ‘ ’ trong cỗ đệm là hành động xong xuôi nhập chuỗi.Hàm fgets() đọc cả newline, buộc phải ta cần xóa đi còn nếu như không muốn trường name (tên) bao gồm ký từ này.

+ những hàm thao tác làm việc với danh sách liên kết

Trong việc này, bọn họ có các hành vi thêm, sửa, xóa Node. Do đó, họ cần xây dựng các hàm sau:

Hàm add
Head: Thêm Node vào đầu DSLKHàm add
Tail: Thêm Node vào thời điểm cuối DSLKHàm add
At: Thêm Node vào chỉ số bất kỳ, thừa kế sử dụng hàm add
Head cùng add
Tail
Hàm traverser: lưu ý danh sách
Hàm del
Head: Xóa Node đầu tiên của DSLKHàm del
Tail: Xóa Node cuối của DSLKHàm del
At: Xóa Node tại chỉ số bất kỳ, cũng trở thành kế quá hàm del
Head và del
Tail nghỉ ngơi trên
Hàm find
Index
ByCode: tra cứu chỉ số của Node trong list theo mã code (mã tỉnh/thành)

Các hàm này đa số là hàm cơ bạn dạng của DSLK đã được mình trình bày cụ thể tại bài xích danh sách links đơn. Do vậy, chúng ta nào không biết thì rất có thể quay lại đọc bài đó trước nha.

Các làm việc với danh sách, mình muốn để trong vòng lặp để tín đồ dùng có thể lặp lại làm việc đó nếu cần. Người tiêu dùng sẽ tất cả quyền chọn gồm thực hiện làm việc đó tiếp hay không ngay sau khi ngừng thao tác.

char option;while (TRUE) // thao tác ở đây scanf("%c", &option); if (option == "N" # Hàm phê chuẩn danh sách

void traverser(Node head) printf("Danh sach hien tai: "); printf("------------------------------------------------------------------------------------------------------------ "); printf("%10s%50s%20s%20s ", "Ma Tinh/TP", "Tinh thanh", "Dien tich", "Dan so"); for(Node phường = head; phường != NULL; phường = p->next) printf("%10d%50s%20f%20d ", p->city.code, p->city.name, p->city.area, p->city.population); printf("------------------------------------------------------------------------------------------------------------ ");Ở đây, ta đơn giản là bắt đầu từ Node thứ nhất (head) cho tới khi bắt buộc nhảy sang trọng Node tiếp theo.Chúng ta in ra dạng bảng bằng phương pháp sử dụng format vào hàm printf().# các hàm giao hàng thêm Node

// cung cấp cuối
Node add
Tail(Node head, city value) Node temp,p;// Khai báo 2 Node tạm thời temp và p. Temp = create
Node(value);//Gọi hàm create
Node để tạo Node temp tất cả next trỏ tới NULL và giá trị là value if(head == NULL) head = temp; //Nếu linked các mục đang trống thì Node temp là head luôn else phường = head;// Khởi tạo p trỏ cho tới head while(p->next != NULL) phường = p->next;//Duyệt danh sách liên kết đến cuối. Node cuối là Node bao gồm next = NULL p->next = temp;//Gán next của thằng cuối = temp. Lúc ấy temp đang là thằng cuối(temp->next = NULL mà) return head; // cấp dưỡng đầu
Node add
Head(Node head, thành phố value) Node temp = create
Node(value); // Khởi tạo thành Node temp với data = value if(head == NULL) head = temp; // //Nếu linked danh sách đang trống thì Node temp là head luôn luôn else temp->next = head; // Trỏ next của temp = head lúc này head = temp; // Đổi head hiện tại = temp(Vì temp hiện thời là head new mà) return head; // Thêm vào ở "chỉ số" (bắt đầu từ bỏ 0) bất kỳ, nếu muốn thêm theo "vị trí" (bắt đầu từ bỏ 1) thì sút position đi 1 solo vị
Node add
At(Node head, city value, int position) position = position - 1; // Thêm theo vị trí if(position == 0 Kết hợp với hàm khởi chế tác City (create
City) phía trên, bạn cũng có thể hoàn chỉnh thao tác làm việc thêm Node vào danh sách với hàm bên dưới đây:

Node del
Head(Node head) if(head == NULL) printf("
Cha teo gi de xoa het!"); else head = head->next; return head; Node del
Tail(Node head) head->next == NULL) return del
Head(head); Node p = head; while(p->next->next != NULL) p. = p->next; p->next = p->next->next; // cho next bởi NULL return head; // Xóa Node ở "chỉ số" (bắt đầu từ 0) bất kỳ
Node del
At(Node head, int position)Ở trên, bọn họ đã có hàm xóa nghỉ ngơi chỉ số bất kỳ, vậy nhằm xóa Node theo mã (code) cung cấp. Ta phải viết thêm 1 hàm tra cứu chỉ số của Node có dữ liệu thành phố mà mã code trùng với cái giá trị được cung cấp:

// Hàm tra cứu chỉ số của Node bao gồm dữ liệu tp mà mã code của nó trùng với cái giá trị cần tìmint find
Index
ByCode(Node head, int code) int index = -1; for(Node p. = head; p != NULL; p. = p->next) index++; if (p->city.code == code) return index; return -1; // không tìm thấyNhư vậy, để hoàn chỉnh thao tác xóa Node theo mã tỉnh/thành phố. Ta sẽ thêm 1 hàm sau:

Node remove
Node(Node head){ int code; char option; while (TRUE) { printf("========== Chon Node muon xoa =============== "); printf("Nhap ma tinh/thanh pho can xoa: "); scanf("%d", &code); int position = find
Index
ByCode(head, code); if (position Các công dụng thêm, xóa Node của danh sách đều có thể thay đổi Node head (Ex: xóa Node head). Bởi đó, các hàm này đều yêu cầu trả về quý giá là Node head mới sau khi đổi khác (có thể vẫn giữ nguyên).

# Hàm sửa cực hiếm Node vào DSLK

Hàm này chắc chắn không thể biến hóa Node head, vì đó bọn họ sẽ cần sử dụng kiểu voidĐơn giản là ta ưng chuẩn qua danh sách, giả dụ tìm thấy mã code tương ứng, sẽ cho những người dùng nhập dữ liệu mới mang đến Node đó.

void edit
Node(Node head) int code; char option; thành phố new
City; while (TRUE) # Hàm bố trí danh sách

void swap
City
Data(City *a, city *b) thành phố tmp = *a; *a = *b; *b = tmp; // Hàm bố trí // giả dụ sort theo code, thì by
Code = 1, by
Area = 0// giả dụ sort theo area, thì by
Code = 0, by
Area = 1// Nếu thu xếp tăng dần dần thì desc = 0, bớt dần thì desc = 1void sort
Cities(Node head, int by
Code, int by
Area, int desc) for(Node phường = head; p. != NULL; p. = p->next) for(Node q = p->next; q != NULL; q = q->next) if (desc) if (by
Code && p->city.code city.code) swap
City
Data(&p->city, &q->city); else if (by
Area && p->city.area city.area) swap
City
Data(&p->city, &q->city); else if (by
Code && p->city.code > q->city.code) swap
City
Data(&p->city, &q->city); else if (by
Area && p->city.area > q->city.area) swap
City
Data(&p->city, &q->city); Hàm swap bọn họ cần dùng con trỏ nhằm hàm sử dụng trực tiếp giá trị được truyền vào. Ta chỉ việc đổi giá trị của chúng đến nhau, chứ không cần đổi 2 Node (rắc rối lắm).Mình thay ý rút gọn code bằng phương pháp cho các option sắp xếp vào vào hàm sort
Cities. Mặc dù không tường minh lắm nhưng bóc ra thì dài quá.Hàm bố trí không chuyển đổi Node head, nên hàm cũng không đề nghị trả về cực hiếm như các hàm thêm xuất xắc xóa Node.# các hàm chức năng khác

Ngoài các hàm thêm, sửa, xóa trên, đề bài bác còn yêu thương cầu một vài hàm tính tổng diện tích, tra cứu tỉnh/thành phố gồm diện tích/dân số lớn nhất, với cả sắp xếp danh sách.

Về cơ bản, các hàm này chỉ việc dựa trên thao tác duyệt list (traveser) là tất cả thể chấm dứt rồi.

// Hàm tính tổng diện tích những thành phố vào DSLKfloat sum
Area(Node head) float sum = 0; for(Node phường = head; p. != NULL; phường = p->next) sum += p->city.area; return sum; // Hàm tìm chỉ số của Node có diện tích lớn tuyệt nhất (giả sử chỉ gồm 1)// nếu như dữ liệu có nhiều hơn 1, bọn họ tìm max rồi chăm bẵm lại 1 lần nữa để kiếm tìm ra các Node có mức giá trị = max đóint index
OfMax
Area(Node head) int max
Index = 0, index = 0; int max
Area = head->city.area; for(Node phường = head; p != NULL; p = p->next) if (p->city.area > max
Area) max
Area = p->city.area; max
Index = index; index++; return max
Index; // Hàm kiếm tìm Node có dân sinh lớn nhất
City max
ByPopulation(Node head) city city = head->city; for(Node p = head; p != NULL; phường = p->next) if (p->city.population > city.population) thành phố = p->city; return city;Thao tác đọc tài liệu từ tệp

Đề bài xích yêu cầu họ cần khởi tạo ra danh sách ban đầu bằng biện pháp đọc tài liệu từ tệp. Vì chưng đó, họ cần thêm một số hàm nhỏ nữa.

– Do dữ liệu tên tỉnh/thành phố bao gồm dấu cách bắt buộc mình chỉ biết cách đọc từng dòng vào xử lý. Vì chưng vậy, bản thân cần:

Hàm handle
Line
Data: tách dòng ra những thành phần con, rõ ràng là cho một dòng dữ liệu, đề xuất trả về cho doanh nghiệp 1 City. Mình cần sử dụng hàm strtok để gia công việc tách chuỗi.Hàm read
Data: Đọc tài liệu từ file, mỗi loại đọc được sẽ điện thoại tư vấn tới hàm handle
Line
Data phía trên. Sau thời điểm có City, ta thêm nó vào danh sách bằng phương pháp gọi cho tới add
Tail hoặc add
Head hoặc add
At

// Hàm tách các thành phần của 1 dòng trong file
City handle
Line
Data(char *line) đô thị city; city.code = INVALID_CITY_CODE; // Khởi sinh sản giá trị không hợp lệ. Sau này ta hoàn toàn có thể kiểm tra. Const char delimiter<> = " "; char *tmp; tmp = strtok(line, delimiter); if (tmp == NULL) printf("Du lieu khong dung dinh dang: %s", line); exit(EXIT_FAILURE); city.code = atoi(tmp); int index = 0; for (;;index++) tmp = strtok(NULL, delimiter); if (tmp == NULL) break; if (index == 0) strcpy(city.name, tmp); else if (index == 1) city.area = (float)atof(tmp); else if (index == 2) city.population = atoi(tmp); else printf("Du lieu khong dung dinh dang: %s", line); exit(EXIT_FAILURE); return city; // Hàm đọc dữ liệu từ tập tin
Node read
Data(Node head, const char* file
Name) FILE* tệp tin = fopen(file
Name, "r"); if(!file) printf("Co loi khi mo tệp tin : %s ", file
Name); exit(EXIT_FAILURE); char line<500>; while (fgets(line, sizeof(line), file)) thành phố city = handle
Line
Data(line); if (city.code != INVALID_CITY_CODE) head = add
Tail(head, city); fclose(file); return head;Như vậy là trả thiện, việc sót lại chỉ là đưa chúng nó vào hàm main theo 1 biệt lập tự do bọn họ quy định.

Xem thêm: Các Ngày Lễ Tinh Yeu Trong Năm, Có Mấy Ngày Valentine

Bài Tập Danh Sách liên kết Đơn C++

X. Danh Sách link Đơn quản lý Sinh Viên C++

Hôm nay bản thân định viết về phần tiếp theo sau của opencv xử lý hình ảnh nhưng còn bài tập môn cấu tạo dữ liệu chưa hoàn thành , sẵn tiện mình vừa làm vừa ra bài này luôn luôn .

Đề bài

Code

#include"iostream"#include"string"#include"stdlib.h"using namespace std;struct Sinh
Vien int mssv; string name; string diachi; string ngaysinh; string lop;;typedef struct Sinh
Vien sinhvien;struct node sinhvien *data; struct node* link;;typedef struct node Node;struct danh sách Node* p
Head; Node* p
Tail;;typedef struct các mục List;void Khoi
Tao
List(List &l) l.p
Head = l.p
Tail = NULL;void Input_Thong
Tin(sinhvien *sv) cin.ignore(); cout name); cout > sv->mssv; cin.ignore(); cout diachi); fflush(stdin); cout ngaysinh); fflush(stdin); cout lop);Node *Khoi
Tao
Node() { sinhvien* sv = new sinhvien; Input_Thong
Tin(sv); Node* p. = new Node; if (p == NULL) cout data = sv; p->link = NULL; return p;void Them
Vao
Dau
Mot
Sinh
Vien(List &l, Node *p) if (l.p
Head == NULL) l.p
Head = l.p
Tail= p; else p->link = l.p
Head; l.p
Head = p; void Show(List l) { for (Node* k = l.p
Head; k != NULL; k = k->link) cout data->mssvdata->name data->diachi data->ngaysinh data->lop data->mssv data->name data->diachi data->ngaysinh data->lop data->name) == 0 && l.p
Head->link ==NULL) l.p
Head = NULL; else for (Node* k = l.p
Head; k != NULL; k = k->link) if (del.compare(k->data->name) == 0) g->link = k->link; k = g; g = k; void search(List l ) int mssv; cout > mssv; for (Node* k = l.p
Head; k != NULL; k = k->link) if (k->data->mssv == mssv) show
Node(k); void upgrade(List& l) int mssv; cout > mssv; for (Node* k = l.p
Head; k != NULL; k = k->link) if (k->data->mssv == mssv) cout data); void Danh
Sach
Sinh
Vien
Chua
Xep
Lop(List l) { for (Node* k = l.p
Head; k != NULL; k = k->link) { if (k->data->lop == "") { cout Nhap 1 sinh vien moi . "; cout In danh sach sinh vien . "; cout Tim kiem sinh vien theo ma so . "; cout Sua thong tin sinh vien "; cout Xoa sinh vien khoi danh sach "; cout Lay danh sach