Danh Sách Liên Kết Đơn — Giải Thuật Lập Trình

     

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

Bạn đang xem: Danh sách liên kết đơn — giải thuật lập trình


Danh Mục bài Viết

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

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

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

Thành phần dữ liệu: lưu tin tức về bản thân thành phần đó.Thành phần liên kết: lưu địa chỉ cửa hàng phần tử lép vế trong danh sách, trả dụ bộ phận đó là bộ phận cuối cùng thì nguyên tố này bởi NULL.

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

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

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

Và do tính links của bộ phận đầu và phần tử đứng sau nó vào danh sách link đơn, nó mang những điểm lưu ý sau:

Chỉ bắt buộc nắm được phần tử đầu cùng cuối là tất cả thể quản lý được danh sáchTruy cập tới bộ phận ngẫu nhiên đề nghị duyệt từ trên đầu đến địa chỉ đóChỉ rất có thể tìm kiếm tuyến đường tính một phần tử
*
Danh Sách links Đơn C++

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

Bài tập C: Nối hai danh sách links đơn

Bài tập C này khiến cho bạn làm quen dần với bí quyết tạo danh sách liên kết đơn và giải pháp nối nhị danh sách link đơn trong C. Để giải bài xích tập này, mình sử dụng kết cấu struct trong C.

Chương trình C

Dưới đây là chương trình C nhằm giải bài xích tập nối hai danh sách liên kết đơn trong 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 đế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 link 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 link vao phan cuoi cua danh sách 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 sách = even; liên kết = list; while(link->next!= NULL) liên kết = link->next; link->next = odd;int main() int i; for(i=1; iBiên dịch công tác C bên trên sẽ cho kết quả:

*
Nối 2 Danh Sách link Đơn C++

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

Đảo ngược danh sách liên kết

Với vận động này, bạn phải cẩn thận. Họ cần tạo cho nút đầu (head) trỏ cho tới nút ở đầu cuối 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, họ duyệt 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 bắt buộc làm là làm cho nút cuối này trỏ cho tới nút phía trước của nó.

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

Chúng ta phải đảm bảo rằng nút cuối cùng này sẽ không trở nên thất lạc, vì đó họ sẽ sử dụng một số trong những nút trợ thời (temp node – giống như các biến chuyển tạm trung gian để lưu 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 đầu tiên sau nút head đang trỏ tới NULL.

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

Chúng ta sẽ làm cho nút head trỏ cho tới nút trước tiên mới vì chưng sử dụng các nút tạm.

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

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

Chương trình minh họa Danh sách links (Linked List) trong 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 printList() 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 insertFirst(int key, int data) //tao mot links struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; //tro link nay toi first node cu link->next = head; //tro first toi first node moi head = link;//xoa phan tu dau tienstruct node* deleteFirst() //luu tham chieu toi first links struct node *tempLink = head; //danh dau next toi first liên kết la first head = head->next; //tra ve links bi xoa return tempLink;//kiem tra menu co trong giỏi khongbool isEmpty() return head == NULL;int length() int length = 0; struct node *current; for(current = head; current != NULL; current = current->next) length++; return length;//tim mot links voi key domain authority chostruct node* find(int key) //bat dau tim tu first liên kết struct node* current = head; //neu list la vào if(head == NULL) return NULL; //duyet qua danh mục 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 chũm du lieu, tra ve link hien tai return current;//xoa mot liên kết voi key da chostruct node* deleteKey(int key) //bat dau tu first link struct node* current = head; struct node* previous = NULL; //neu các mục la vào 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 liên kết hien tai previous = current; //di chuyen toi next link current = current->next; //cap nhat link if(current == head) //thay doi first de tro toi next liên kết head = head->next; else //bo qua liên kết hien tai previous->next = current->next; return current;// đắm đuối sap xepvoid sort() int i, j, k, tempKey, tempData ; struct node *current; struct node *next; int kích thước = length(); k = form size ; for ( i = 0 ; i next ; for ( j = 1 ; j data > next->data ) tempData = current->data ; current->data = next->data; next->data = tempData ; tempKey = current->key; current->key = next->key; next->key = tempKey; current = current->next; next = next->next; }// mê man 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() insertFirst(1,10); insertFirst(2,20); insertFirst(3,30); insertFirst(4,1); insertFirst(5,40); insertFirst(6,56); printf("Danh sach ban dau: "); //in danh sach printList(); while(!isEmpty()) struct node *temp = deleteFirst(); printf(" Gia tri bi xoa:"); printf("(%d,%d) ",temp->key,temp->data); printf(" Danh sach sau khi da xoa gia tri: "); printList(); insertFirst(1,10); insertFirst(2,20); insertFirst(3,30); insertFirst(4,1); insertFirst(5,40); insertFirst(6,56); printf(" Phuc hoi danh sach: "); printList(); printf(" "); struct node *foundLink = find(4); if(foundLink != NULL) printf("Tim cầm cố phan tu: "); printf("(%d,%d) ",foundLink->key,foundLink->data); printf(" "); else printf("Khong tim cầm phan tu."); deleteKey(4); printf("Danh sach, sau khoản thời gian xoa mot phan tu: "); printList(); printf(" "); foundLink = find(4); if(foundLink != NULL) printf("Tim núm phan tu: "); printf("(%d,%d) ",foundLink->key,foundLink->data); printf(" "); else printf("Khong tim gắng phan tu."); printf(" "); sort(); printf("Danh sach sau khi duoc sap xep: "); printList(); reverse(&head); printf(" Danh sach sau khoản thời gian bi dao nguoc: "); printList();Kết quả

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

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

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

Tùy theo kiểu danh sách chúng ta là gì mà bí quyết 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 dễ dàng hơn

Mình vẫn nhập vào phần tử cho danh sách liên kết đơn bởi con trỏ. Ví như nhập vào bằng 0 thì đang dừng nhập. Thêm bộ phận vào list mình sử dụng hàm chèn cuối Insert_Last

// Hàm nhập list số nguyên từ keyboard void Input(List &L) Init(L); chiến thắng x; int i=1; do cout>x; if (x!=0) Insert_Last(L,x); i++; while (x!=0); // nếu như nhập x = 0 thì dừng 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 link đơn, mình sẽ thực hiện sắp xếp bằng phương pháp so sánh và đổi thay giá trị data chứ không thay đổi Node. Có nghĩa là chỉ so sánh các giá trị data rồi sắp đến xếp, các Node vẫn không thay đổi không dịch chuyển.

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

Thao tác bố trí trong list về căn bản tương tự như những thuật toán bố trí khác, dễ dàng chỉ là coi sóc từng phần tử rồi so sánh với nhau, sau ấy hoán đổi vị trí của chúng.

Đầu tiên ta tất cả một vòng lặp For áp dụng biến pTmp nhằm lặp từng thành phần trong danh sách, vòng lặp For lắp thêm hai thực hiện biến pTmp2 để lặp từng bộ phận trong danh sách.

Nếu pTmp > pTmp2 thì hoán đổi vị trí giữa chúng, nếu pTmp pNext) //for loop lắp thêm hai for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext) if(pTmp->data>pTmp2->data) // nếu quý giá trước > quý giá sau thì hoán thay đổi hai địa chỉ int tmp=pTmp->data; pTmp->data=pTmp2->data; pTmp2->data=tmp;

VI. Thiết lập Đặt Danh Sách liên kết Đơn C++

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

Tạo node

Danh sách link đơn được tạo ra thành từ nhiều node, vày đó, chúng ta sẽ cùng đi tự node trước. Một node gồm hai yếu tắc là thành phần dữ liệu và nhân tố liên kết. Yếu tố dữ liệu có thể là kiểu dữ liệu có sẵn hoặc các bạn tự quan niệm (struct tuyệt class…), trong bài viết này để đơn giản mình sẽ dùng kiểu int cho chỗ dữ liệu. Thành phần liên kết là địa chỉ đương nhiên đang là bé trỏ, bé trỏ này trỏ đến node tiếp theo, vị đó, bé trỏ này là bé trỏ trỏ vào 1 node.

struct Node int data; Node* next;;Để chế tạo một node mới, ta triển khai cấp phát động cho node mới, khởi sản xuất giá trị thuở đầu và trả về địa chỉ cửa hàng của node new được cấp phát.

Tạo danh sách links đơn

Ta đã chiếm lĩnh được thành phần khiến cho danh sách link đơn là node, tiếp theo họ cần cai quản chúng bằng phương pháp biết được phần tử đầu cùng cuối. Vì chưng mỗi bộ phận đều link với phần tử kế vậy yêu cầu tả chỉ việc biết phần tử đầu với cuối là có thể thống trị được list này. Vậy đơn giản ta nên tạo 1 kết cấu lưu trữ showroom phần tử đầu (head) và thành phần cuối (hay bộ phận đuôi tail).

struct LinkedList Node* head; Node* tail;;Khi bắt đầu tạo danh sách, danh sách sẽ không có bộ phận nào, do đó head với 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 CreateList(LinkedList& l) l.head = NULL; l.tail = NULL;Bây giờ để chế tạo ra một danh sách, ta có tác dụng như sau:

LinkedList list;CreateList(list); // Gán head và tail bằng NULL

Thêm thành 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 nên kiếm tra xem list đó gồm rỗng tốt không, nếu list rỗng, ta chỉ việc gán head và tail của danh sách bằng node đó. Trái lại nếu danh sách không rỗng, ta thực hiện trỏ thành phần link vào head, kế tiếp gán lại head bằng node mới.

*
Thêm phần tử vào đầu danh sách liên kết đơn

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

Thêm vào cuối

Tương tự, để thêm node vào thời gian cuối danh sách, trước tiên ta review xem list rỗng tuyệt khô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 tiến hành trỏ tail->next vào node mới, sau đó gán lại tail bởi node mới (vì hiện nay node new thêm chính là tail).

*
Thêm bộ phận vào cuối danh sách links đơn

Trong hình trên, chúng ta thực hiện tại thêm node gồm data bằng 6 vào danh sách. Tail bây giờ là node có data 5, tiến hành gán tail->next bởi node new để nối thêm nó vào đuôi danh sách, hôm nay node new trở thành phần tử cuối danh sách 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 1 node p. Vào sau node q bất kỳ, thứ nhất ta đề xuất kiếm tra coi node q tất cả NULL tốt không, nếu như node q là NULL tức là danh sách rỗng, vậy thì ta sẽ tiếp tế đầu danh sách. Trường hợp node q ko NULL, có nghĩa là tồn trên trong danh sách, ta tiến hành trỏ p->next = q->next, kế tiếp q->next = phường Tiếp theo chúng ta kiểm tra coi node q trước đó có phải là node cuối tuyệt không, trường hợp node q là node cuối thì thêm phường vào, p. Sẽ thành node cuối đề nghị ta gán lại tail = p.

*
Thêm phần tử vào sau nút Q vào danh sách link đơn

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

Xóa bộ phận khỏi danh sách

Xóa sinh hoạt đầu

Để xóa bộ phận ở đầu danh sách, ta soát sổ xem danh sách đó có rỗng xuất xắc không, nếu như rỗng, ta không yêu cầu xóa, trả về tác dụng là 0. Nếu danh sách không rỗng, ta tiến hành lưu node head lại, tiếp nối gán head bởi next của node head, tiếp đến 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 bao gồm rỗng tuyệt không, giả dụ rỗng ta gán lại tail bởi NULL luôn tiếp nối trả về hiệu quả 1.

Lưu ý trước lúc xóa node head đi, ta dùng phát triển thành tham chiếu x để lưu trữ lại giá trị của node bị hủy để sử dụng.

*
Xóa bộ phận đầu danh sách links đơn

Trong hình trên, mình triển khai xóa node trước tiên có data bởi 0. Bản thân trỏ head cho next của node 0 (hiện vẫn là head), thì head bây giờ sẽ là node 1, sau đó mình hủy đi node 0 là được.

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

Để xóa một node p. Sau node q bất kỳ, ta khám nghiệm xem node q bao gồm NULL tuyệt không, giả dụ node q NULL thì ko tồn trên trong danh sách, vì thế trả về 0, ko xóa. Nếu như node q khác NULL dẫu vậy next của q là NULL, có nghĩa là p bởi 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 như node p. Tồn tại, ta thực hiện kiểm tra coi node p. Có phải là tail tốt không, ví như node p là tail thì gán lại tail là q, tức là node trước đó để xóa node p đi.

Trong hình trên, ta triển khai xóa node tất cả data 3 (node p) sau node gồm 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 phường đi là xong.

Duyệt list và in

Sau khi tất cả các thao tác thêm, xóa, bạn cũng có thể in ra list để kiểm soát xem có chuyển động đúng hay không. Để in danh sách, ta duyệt từ trên đầu đến cuối list và in ra trong khi duyệt. Ta gán một node bởi head, kế tiếp kiểm tra xem node đó có NULL tuyệt không, ko 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 nay là node tiếp theo, cứ như vậy cho tới hết.

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

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

Tìm kiếm thành phần trong danh sách

Ý tưởng tra cứu kiếm bộ phận cũng là chăm bẵm danh sách, trường hợp như không tìm thấy thì thường xuyên duyệt. Sau khi xong xuôi duyệt, ta chỉ việc kiểm tra coi node chú ý có bởi NULL xuất xắc không, nếu không có nghĩa là đã tìm kiếm thấy, ta đang trả về địa chỉ cửa hàng của node đó.

Đếm số thành phần của danh sách

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

Xóa danh sách

Để xóa danh sách, ta phải hủy tất cả các node có nghĩa là duyệt cùng hủy từng node. Ở trên đây mình sẽ dùng lại hàm RemoveHead. Đầu tiên, ta gán một node bởi head, soát sổ nếu node kia khác NULL thì call RemoveHead với gán lại node bằng head tiếp, cứ lặp như vậy cho tới khi node đó NULL thì thôi. Sau khoản thời gian xóa không còn tất cả thành phần thì gán lại tail bằng NULL.

VII. Code Danh Sách liên kết Đơn sv C++

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

Cho 1 sinh viên bao gồm cấu trúc: mã (int), tên (char *). Dùng danh sách link đơn với bé trỏ phead nhằm thao tác:

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

Chương trình quản lý sinh viên sử 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 link đơn với các thao tác liên quan.

Đầu tiên chúng ta buộc phải tạo lập một cấu trúc sinh viên cùng với mã số sv ma với tên sinh viên ten.

Xem thêm: Cách Phóng To Màn Hình Facebook Bị Phóng To, Màn Hình Facebook Bị Phóng To

//tao cau truc sinh vienstruct SinhVien int ma; char ten<150>;;Tiếp đến tạo cấu tạo dữ liệu của danh sách link đơn với cái giá trị data và bé trỏ pNext. Khởi sinh sản giá trị đến pHead cùng pTail bằng NULL.

//tao cau truc danh sach lien ket donstruct Node SinhVien *data; Node *pNext;;struct SingleList Node *pHead;;//khoi tao danh sach lien ket donvoid Initialize(SingleList *&list) list=new SingleList; list->pHead=NULL;Tạo 1 hàm NhapSinhVien() dùng kết cấu SinhVien để nhập những thông tin của sinh viên như: MSSV và tên sinh viên

SinhVien *NhapSinhVien() SinhVien *sv=new SinhVien; cout>sv->ma; cin.ignore(); coutten); return sv;Bây giờ bọn chúng ta bắt đầu tạo Node với những thông tin của cấu trúc SinhVien, tiếp đến thêm Node vào thời gian cuối danh sách.

//tao node sinh vienNode *CreateNode(SinhVien *sv) Node *pNode=new Node; if(pNode!=NULL) pNode->data=sv; pNode->pNext=NULL; else coutpHead==NULL) list->pHead=pNode; else Node *pTmp=list->pHead; while(pTmp->pNext!=NULL) pTmp=pTmp->pNext; pTmp->pNext=pNode; Sau dịp thêm Node vào list ta triển khai những thao tá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 bác tìm tìm và sắp xếp trong danh sách links đơn mình đã giới thiệu các bạn thao tác sắp đến xếp. Phụ thuộc đó ta chỉ cần biến đổi một chút sẽ sở hữu được ngay hàm bố trí SortList() theo MSSV.

void SortList(SingleList *&list) for(Node *pTmp=list->pHead;pTmp!=NULL;pTmp=pTmp->pNext) for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext) SinhVien *svTmp=pTmp->data; SinhVien *svTmp2=pTmp2->data; if(svTmp2->mama) int ma=svTmp->ma; char ten<150>; strcpy(ten,svTmp->ten); svTmp->ma=svTmp2->ma; strcpy(svTmp->ten,svTmp2->ten); svTmp2->ma=ma; strcpy(svTmp2->ten,ten); Tương từ như hàm chuẩn bị xếp, nhằm xóa một sinh viên dựa vào tên ta tiến hành vòng lặp while lặp từng thành phần trong danh sách. Nếu thành phần đó trùng với bộ phận được nhập vào từ keyboard ta tiến hành delete bộ phận đó ra khỏi danh sách.

void RemoveNode(SingleList *&list,int ma) Node *pDel=list->pHead; if(pDel==NULL) coutdata; if(sv->ma==ma) break; pPre=pDel; pDel=pDel->pNext; if(pDel==NULL) coutpHead) list->pHead=list->pHead->pNext; pDel->pNext=NULL; delete pDel; pDel=NULL; else pPre->pNext=pDel->pNext; pDel->pNext=NULL; delete pDel; pDel=NULL; Sau khi tiến hành tạo các thao tác, ta chỉ cần tạo hàm main() và hotline các làm việc đó ra để sử dụng.

int main(int argc, char** argv) SingleList *list; Initialize(list); SinhVien *teo=NhapSinhVien(); InsertLast(list,teo); SinhVien *ty=NhapSinhVien(); InsertLast(list,ty); SinhVien *bin=NhapSinhVien(); InsertLast(list,bin); PrintList(list); SortList(list); cout>ma; RemoveNode(list,ma); coutFull code:

#include #include #include using namespace std;//tao cau truc sinh vienstruct SinhVien int ma; char ten<150>;;//tao cau truc danh sach lien ket donstruct Node SinhVien *data; Node *pNext;;struct SingleList Node *pHead;;//khoi tao danh sach lien ket donvoid Initialize(SingleList *&list) list=new SingleList; list->pHead=NULL;//nhap thong tin sinh vienSinhVien *NhapSinhVien() SinhVien *sv=new SinhVien; cout>sv->ma; cin.ignore(); coutten); return sv;//tao node sinh vienNode *CreateNode(SinhVien *sv) Node *pNode=new Node; if(pNode!=NULL) pNode->data=sv; pNode->pNext=NULL; else coutpHead==NULL) list->pHead=pNode; else Node *pTmp=list->pHead; while(pTmp->pNext!=NULL) pTmp=pTmp->pNext; pTmp->pNext=pNode; //hien thi danh sachvoid PrintList(SingleList *list) Node *pTmp=list->pHead; if(pTmp==NULL) coutdata; coutmatenpNext; //sap xepvoid SortList(SingleList *&list) for(Node *pTmp=list->pHead;pTmp!=NULL;pTmp=pTmp->pNext) for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext) SinhVien *svTmp=pTmp->data; SinhVien *svTmp2=pTmp2->data; if(svTmp2->mama) int ma=svTmp->ma; char ten<150>; strcpy(ten,svTmp->ten); svTmp->ma=svTmp2->ma; strcpy(svTmp->ten,svTmp2->ten); svTmp2->ma=ma; strcpy(svTmp2->ten,ten); //xoavoid RemoveNode(SingleList *&list,int ma) Node *pDel=list->pHead; if(pDel==NULL) coutdata; if(sv->ma==ma) break; pPre=pDel; pDel=pDel->pNext; if(pDel==NULL) coutpHead) list->pHead=list->pHead->pNext; pDel->pNext=NULL; delete pDel; pDel=NULL; else pPre->pNext=pDel->pNext; pDel->pNext=NULL; delete pDel; pDel=NULL; int main(int argc, char** argv) SingleList *list; Initialize(list); SinhVien *teo=NhapSinhVien(); InsertLast(list,teo); SinhVien *ty=NhapSinhVien(); InsertLast(list,ty); SinhVien *bin=NhapSinhVien(); InsertLast(list,bin); PrintList(list); SortList(list); cout>ma; RemoveNode(list,ma); coutKết quả:

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

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

Trong hướng dẫn này bản thân sẽ reviews tới chúng ta cách xóa Node vào danh sách link đơn.

Chúng ta sẽ thuộc nhau khám phá 3 ví dụ thời điểm xóa 1 Node khỏi danh sách links đơn:

Xóa Node làm việc đầu danh sách links đơn.Xóa Node ngơi nghỉ cuối danh sách liên kết đơn.Xóa Node ở giữa danh sách liên kết đơn.

+ Xóa Node làm việc đầu danh sách link đơn

Trong trường hợp chúng ta muốn xóa một Node, cơ mà Node này lại nằm làm việc đầu danh sách. Đây là một trong 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 pDel là Node đề xuất xóa với một danh sách links đơn.

*
Xóa Node làm việc đầu danh sách links đơn

Bước 1: bởi vì Node đề xuất xóa nghỉ ngơi đầu danh sách, tức là ngay node pHead. Vì chưng vậy bọn họ cần dịch chuyển pHead tự pDel lịch sự Node kế tiếp: list.pHead = list.pHead -> pNext

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

Bước 2: Sau khi dịch chuyển pHead quý phái Node kế tiếp, chúng ta sẽ ngắt mối link giữa pDel với Node phía đằng sau nó: pDel -> pNext = Null.

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

Bước 3: hiện thời pDel không còn liên kết với bất kì Node làm sao trong danh sách nữa, chúng ta đã rất có thể xóa Node này. Delete pDel

*
Xóa bộ phận Trong Danh Sách link Đơn C++

// giả dụ pDel == list.pHead, tức là số buộc phải xóa nghỉ ngơi đầu danh sách if(pDel == list.pHead) list.pHead = list.pHead -> pNext; pDel -> pNext = NULL; delete pDel; pDel = NULL;

+ Xóa Node làm việc cuối danh sách link đơn.

Trong trường hòa hợp Node ý muốn xóa lại nằm tại cuối danh sách, tựa như như việc xóa ngơi nghỉ đầu danh sách. Ta chỉ việc di gửi pTail về Node trước kia (pPre) và biến đổi pNext = NULL.

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

Sau khi di chuyển pTail về Node trước đó với ngắt mối links giữa pPre cùng với pDel, ta triển khai xóa Node pDel: delete pDel

//Nếu pDel == list.pTail, tức là số đề xuất xóa sinh sống cuối list if(pDel -> pNext == NULL) list.pTail = pPre; pPre -> pNext = NULL; delete pDel; pDel = NULL;

+ Xóa Node trọng điểm danh sách link đơn.

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

Khi ta ước ao xóa một Node trọng tâm danh sách, trước tiên ta cần xác minh Node đề nghị xóa pDel cùng Node đứng trước nó pPre.

*
Xóa Node trọng tâm danh sách links đơn.

Sau khi xác minh được pDel cùng pPre, ta chuyển đổi mối liên kết giữa pPre cho pTail (pPre -> pNext = pDel -> pNext) và mang đến pDel -> pNext == NULL. Các chúng ta có thể xem phía mũi tên để biết được công việc thực hiện nay của nó.

*
Xóa Node trung tâm danh sách liên kết đơn.

Ta hoàn toàn có thể xóa Node pDel khi đang ngắt mối liên kết giữa nó với những Node khác: delete pDel

// với trường hợp sau cuối số muốn xóa nằm tại giữa danh sách else pPre -> pNext = pDel -> pNext; pDel -> pNext = NULL; delete pDel; pDel = NULL;

+ ví dụ xóa Node trong danh sách link đơn

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

#include using namespace std;/* Khai làm giá trị data và con trỏ pNext trỏ tới bộ phận kế tiếp */struct Node int data;// quý giá data của node Node *pNext;// bé trỏ pNext; /* Khai báo Node đầu pHead cùng Node cuối pTail*/struct SingleList Node *pHead; //Node đầu pHead Node *pTail; // Node cuối pTail; /* khởi chế tạo ra giá trị cho Node đầu với Node cuối */void Initialize(SingleList &list) list.pHead=list.pTail=NULL;// khởi sinh sản giá trị mang đến Node đầu cùng Node cuối là Null /* Đếm số thành phần trong list */ int SizeOfList(SingleList list) Node *pTmp=list.pHead; int nSize=0; while(pTmp!=NULL) pTmp=pTmp->pNext; nSize++; return nSize; /* tạo ra Node trong danh sách link đơn */Node *CreateNode(int d) Node *pNode=new Node; //sử dụng pNode để sinh sản một Node new if(pNode!=NULL) // nếu pNode != Null, có nghĩa là pNode có mức giá trị thì pNode->data=d; // gán giá trị data mang lại d pNode->pNext=NULL;// với cho bé trỏ pNext trỏ tới cực hiếm Null else // trường hợp pNode == Null, có nghĩa là pNode không tồn tại giá trị thì xuất thông tin coutpNext=list.pHead; list.pHead=pNode; /* chèn node vào thời gian cuối danh sách */void InsertLast(SingleList &list,int d) Node *pNode=CreateNode(d); if(list.pTail==NULL) list.pHead=list.pTail=pNode; else list.pTail->pNext=pNode; list.pTail=pNode; /* chèn node vào giữa list */void InsertMid(SingleList &list, int pos, int d) // nếu pos = SizeOfList(list)) coutpNext; i++; //sau khi kiếm được thì đổi khác con trỏ pNext pPre ->pNext=pNode; pNode->pNext=pIns; /* xóa node khỏi danh sách link */void RemoveNode(SingleList &list, int d) Node *pDel = list.pHead; // tạo thành một node pDel nhằm xóa //Nếu pDel == Null thì list rỗng if(pDel == NULL) cout data == d) break; pPre = pDel; pDel = pDel -> pNext; //Nếu pDel == null có nghĩa là không tìm thấy số cần xóa if(pDel == NULL) cout pNext; pDel -> pNext = NULL; delete pDel; pDel = NULL; //Nếu pDel == list.pTail, có nghĩa là số buộc phải xóa ở cuối danh sách else if(pDel -> pNext == NULL) list.pTail = pPre; pPre -> pNext = NULL; delete pDel; pDel = NULL; // cùng trường hợp sau cuối số ước ao xóa nằm tại vị trí giữa list else pPre -> pNext = pDel -> pNext; pDel -> pNext = NULL; delete pDel; pDel = NULL; } /* hàm xuất tài liệu */void PrintList(SingleList list) Node *pTmp=list.pHead; if(pTmp==NULL) coutdatapNext; int main() { SingleList list; Initialize(list); //Thêm node đầu danh sách InsertFirst(list, 5); InsertFirst(list, 7); InsertFirst(list, 3); coutKết quả:

*
Ví dụ xóa Node trong danh sách links đơn

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

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

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

Đề bài xích tập danh sách liên kết đơn

Viết chương trình trong ngôn từ C tiến hành các đề nghị sau:

Khai báo kết cấu dữ liệu để tổ chức 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 từng tỉnh/thành phố bao gồm: Mã tỉnh, thương hiệu tỉnh, diện tích, dân số.Cài để các thao tác cơ phiên bản (thêm ở chỗ bất kỳ; sửa, xóa theo mã (code), chăm bẵm danh sách).Tính tổng diện tích của tất cả các tỉnh giấc thành.Tìm vị trí của node của tỉnh có diện tích lớn nhất.Tìm tỉnh/thành phố có số lượng dân sinh lớn nhất.Sắp xếp list theo mã tỉnh/thành phố.Sắp xếp danh sách tăng mạnh theo diện tích.

Yêu cầu:

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

Lời giải bài bác tập danh sách link đơn

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

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

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

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

// Hàm khởi tạo Node thứ nhất của LinkedListNode initHead() Node head; head = NULL; return head;Chúng ta cũng biến thành cần hàm khởi sinh sản 1 Node khi đang có dữ liệu của Node đó. Sau khi khởi tạo thì bạn có thể thêm nó vào danh sách. // Hàm tạo mới 1 Node vào LinkedList Node createNode(City city) Node temp; // Khai báo 1 Node temp = (Node)malloc(sizeof(struct LinkedList)); // cấp phép vùng nhớ mang đến Node temp->next = NULL;// cho next trỏ tới NULL temp->city = city; // Gán giá chỉ trị đến Node return temp;Lưu ý: Ta đề nghị cho nhỏ trỏ next của Node được khởi tạo bởi NULL, có nghĩa là chưa trỏ cho tới đâu. Tránh vấn đề nó trỏ ltinh tinh trong cỗ nhớ.

Chúng ta cần phải có 1 hàm khởi tạo thành giá trị mang đến kiểu đô thị đã tư tưởng ở bên trên qua stdin (nhập từ bỏ console). Lý do là vì chưng chương trình của họ có tính 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 để chế tạo ra dữ liệu thông qua stdin.

City createCity() đô thị newCity; printf("Nhap code: "); scanf("%d", &newCity.code); printf("Nhap ten: "); getchar(); // bỏ qua " " trong cỗ đệm fgets(newCity.name, 100, stdin); // Xóa sống cuối chuỗi vừa nhập nếu gồm if ((p=strchr(newCity.name, " ")) != NULL) *p = ""; printf("Nhap dien tich: "); scanf("%f", &newCity.area); printf("Nhap dan so: "); scanf("%d", &newCity.population); return newCity;Lưu ý:

Chúng ta phải hàm getchar() để xóa bộ đệm, rõ ràng là xóa sổ ký trường đoản cú ‘ ’ còn sót làm việc lần nhập mã tỉnh/thành phố trước đó. Còn nếu như không xóa, hàm nhập chuỗi sẽ nhận biết ‘ ’ trong bộ đệm là hành động ngừng nhập chuỗi.Hàm fgets() phát âm cả newline, buộc phải ta phải xóa đi còn nếu như không muốn ngôi trường name (tên) tất cả ký trường đoản cú này.

+ các 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. Bởi vì đó, chúng ta cần xây dựng các hàm sau:

Hàm addHead: Thêm Node vào đầu DSLKHàm addTail: Thêm Node vào thời gian cuối DSLKHàm addAt: Thêm Node vào chỉ số bất kỳ, thừa kế sử dụng hàm addHead và addTailHàm traverser: xem xét danh sáchHàm delHead: Xóa Node trước tiên của DSLKHàm delTail: Xóa Node cuối của DSLKHàm delAt: Xóa Node tại chỉ số bất kỳ, cũng trở nên kế quá hàm delHead cùng delTail sống trênHàm findIndexByCode: tìm kiếm chỉ số của Node trong danh sách theo mã code (mã tỉnh/thành)

Các hàm này đều là hàm cơ bạn dạng của DSLK đã có được mình trình bày cụ thể tại bài xích danh sách links đơn. Vị vậy, bạn nào chưa chắc chắn thì có thể quay lại đọc bài bác đó trước nha.

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

char option;while (TRUE) option == "n") break; # Hàm coi ngó 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 p. = 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 và dễ dàng là bắt đầu từ Node trước tiên (head) tính đến khi thiết yếu nhảy sang 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().# những hàm ship hàng thêm Node

// chế tạo cuốiNode addTail(Node head, đô thị value) Node temp,p;// Khai báo 2 Node nhất thời temp và phường temp = createNode(value);//Gọi hàm createNode để tạo Node temp bao gồm next trỏ tới NULL và cực hiếm là value if(head == NULL) head = temp; //Nếu linked danh mục đang trống thì Node temp là head luôn luôn else p. = head;// Khởi tạo phường trỏ tới head while(p->next != NULL) p. = p->next;//Duyệt danh sách link đến cuối. Node cuối là Node gồm next = NULL p->next = temp;//Gán next của thằng cuối = temp. Lúc ấy temp sẽ là thằng cuối(temp->next = NULL mà) return head; // thêm vào đầuNode addHead(Node head, đô thị value) Node temp = createNode(value); // Khởi tạo Node temp với data = value if(head == NULL) head = temp; // //Nếu linked danh mục đang trống thì Node temp là head luôn else temp->next = head; // Trỏ next của temp = head lúc này head = temp; // Đổi head bây giờ = temp(Vì temp hiện giờ là head new mà) return head; // Thêm vào ở "chỉ số" (bắt đầu trường đoản cú 0) bất kỳ, nếu muốn thêm theo "vị trí" (bắt đầu từ 1) thì giảm position đi 1 1-1 vịNode addAt(Node head, city value, int position) head == NULL) head = addHead(head, value); // Nếu địa chỉ chèn là 0, có nghĩa là thêm vào đầu else // bước đầu tìm vị trí đề nghị chèn. Ta sẽ sử dụng k nhằm đếm mang đến vị trí int k = 1; Node phường = head; while(p != NULL && k != position) phường = p->next; ++k; if(k != position) // Nếu trông nom hết list lk rồi mà lại vẫn không tới vị trí buộc phải chèn, ta vẫn mặc định chèn cuối // nếu khách hàng không ý muốn chèn, hãy thông báo vị trí chèn chưa phù hợp lệ head = addTail(head, value); // printf("Vi tri chen vuot qua vi tri cuoi cung! "); else Node temp = createNode(value); temp->next = p->next; p->next = temp; return head;Kết hợp với hàm khởi tạo nên City (createCity) phía trên, chúng ta 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 dưới đây:

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

// Hàm kiếm tìm chỉ số của Node gồm dữ liệu thành phố mà mã code của nó trùng với giá trị cần tìmint findIndexByCode(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 kiếm thấyNhư vậy, để hoàn hảo thao tác xóa Node theo mã tỉnh/thành phố. Ta sẽ thêm 1 hàm sau:

Node removeNode(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 = findIndexByCode(head, code); if (position Các tính năng thêm, xóa Node của danh sách đều có thể chuyển đổi Node head (Ex: xóa Node head). Vày đó, các hàm này đều buộc phải trả về giá trị là Node head bắt đầu sau khi thay đổi (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 là không thể thay đổi Node head, bởi vì đó họ sẽ dùng kiểu voidĐơn giản là ta chăm chú qua danh sách, ví như tìm thấy mã code tương ứng, sẽ cho tất cả những người dùng nhập dữ liệu mới mang đến Node đó.

void editNode(Node head) int code; char option; đô thị newCity; while (TRUE) # Hàm thu xếp danh sách

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

Ngoài các hàm thêm, sửa, xóa trên, đề bài còn yêu thương cầu một trong những hàm tính tổng diện tích, search tỉnh/thành phố tất cả diện tích/dân số khủng nhất, cùng cả sắp xếp danh sách.

Về cơ bản, những hàm này chỉ cần dựa trên làm việc duyệt danh sách (traveser) là gồm 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 sumArea(Node head) float sum = 0; for(Node phường = head; phường != NULL; phường = p->next) sum += p->city.area; return sum; // Hàm kiếm tìm chỉ số của Node có diện tích s lớn nhất (giả sử chỉ bao gồm 1)// nếu dữ liệu có khá nhiều hơn 1, bọn họ tìm max rồi phê chuẩn lại 1 đợt tiếp nhữa để tìm ra các Node có mức giá trị = max đóint indexOfMaxArea(Node head) int maxIndex = 0, index = 0; int maxArea = head->city.area; for(Node p = head; p != NULL; p. = p->next) if (p->city.area > maxArea) maxArea = p->city.area; maxIndex = index; index++; return maxIndex; // Hàm tìm Node có dân sinh lớn nhấtCity maxByPopulation(Node head) city city = head->city; for(Node p = head; phường != NULL; p = 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 sản xuất danh sách lúc đầu bằng phương pháp đọc tài liệu từ tệp. Bởi vì đó, chúng ta cần thêm một số hàm nhỏ nữa.

– Do tài liệu tên tỉnh/thành phố 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ị vậy, mình cần:

Hàm handleLineData: tách bóc dòng ra các thành phần con, rõ ràng là cho 1 dòng dữ liệu, bắt buộc trả về cho khách hàng 1 City. Mình dùng hàm strtok để làm việc bóc tách chuỗi.Hàm readData: Đọc tài liệu từ file, mỗi loại đọc được sẽ gọi tới hàm handleLineData phía trên. Sau khi có City, ta thêm nó vào danh sách bằng phương pháp gọi tới addTail hoặc addHead hoặc addAt

// Hàm bóc các thành phần của một dòng trong fileCity handleLineData(char *line) city city; city.code = INVALID_CITY_CODE; // Khởi sinh sản giá trị chưa phù hợp lệ. Trong tương lai 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 tinNode readData(Node head, const char* fileName) FILE* tệp tin = fopen(fileName, "r"); if(!file) printf("Co loi lúc mo file : %s ", fileName); exit(EXIT_FAILURE); char line<500>; while (fgets(line, sizeof(line), file)) thành phố city = handleLineData(line); if (city.code != INVALID_CITY_CODE) head = addTail(head, city); fclose(file); return head;Như vậy là hoàn thiện, việc còn sót lại chỉ là đưa chúng nó vào hàm main theo 1 biệt lập tự do họ quy định.

Xem thêm: Hướng Dẫn 11 Các Kiểu Gấp Khăn Ăn Trong Nhà Hàng Cực Dễ Chỉ Mất 5 Phút Thực Hiện

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

X. Danh Sách link Đơn thống trị Sinh Viên C++

Hôm nay bản thân định viết về phần tiếp sau của opencv xử lý ảnh nhưng còn bài xích tập môn kết cấu dữ liệu chưa kết thúc , 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 SinhVien int mssv; string name; string diachi; string ngaysinh; string lop;;typedef struct SinhVien sinhvien;struct node sinhvien *data; struct node* link;;typedef struct node Node;struct menu Node* pHead; Node* pTail;;typedef struct menu List;void KhoiTaoList(List &l) l.pHead = l.pTail = NULL;void Input_ThongTin(sinhvien *sv) cin.ignore(); cout name); cout > sv->mssv; cin.ignore(); cout diachi); fflush(stdin); cout ngaysinh); fflush(stdin); cout lop);Node *KhoiTaoNode() { sinhvien* sv = new sinhvien; Input_ThongTin(sv); Node* p. = new Node; if (p == NULL) cout data = sv; p->link = NULL; return p;void ThemVaoDauMotSinhVien(List &l, Node *p) if (l.pHead == NULL) l.pHead = l.pTail= p; else p->link = l.pHead; l.pHead = p; void Show(List l) { for (Node* k = l.pHead; 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.pHead->link ==NULL) l.pHead = NULL; else for (Node* k = l.pHead; 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.pHead; k != NULL; k = k->link) if (k->data->mssv == mssv) showNode(k); void upgrade(List& l) int mssv; cout > mssv; for (Node* k = l.pHead; k != NULL; k = k->link) if (k->data->mssv == mssv) cout data); void DanhSachSinhVienChuaXepLop(List l) { for (Node* k = l.pHead; 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 sinh vien chua xep lop "; cout Thoat chuong trinh "; while (1){ cout > n; if (n == 1) { cout

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