85
/ 100
Bài tập danh sách liên kết đơn dưới đây là một dạng bài tập tổng hợp giúp các bạn ôn luyện lại kiến thức về danh sách liên kết đơn cũng như các kiến thức khác về lập trình C. Sau bài học này, ngoài kiến thức về danh sách liên kết đơn, bạn cũng sẽ nắm được:
- Đọc ghi tệp trong ngôn ngữ C
- Cách xử lý dữ liệu văn bản trong C: tách chuỗi, chuyển chuỗi về số, …
- Làm việc với kiểu dữ liệu tự định nghĩa (structure)
- Và các kiến thức căn bản khác của lập trình C
Đề bài tập danh sách liên kết đơn
Viết chương trình trong ngôn ngữ C thực hiện các yêu cầu sau:
- Khai báo cấu trúc dữ liệu để tổ chức danh sách liên kết đơn quản lý các tỉnh/thành phố của Việt Nam. Thông tin của mỗi tỉnh/thành phố bao gồm: Mã tỉnh, tên tỉnh, diện tích, dân số.
- Cài đặt các thao tác cơ bản (thêm ở vị trí bất kỳ; sửa, xóa theo mã (code), duyệt danh sách).
- Tính tổng diện tích của tất cả các tỉnh 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ó 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 dần theo diện tích.
Yêu cầu:
- Viết chương trình cụ thể hóa các chức năng trên, người dùng có thể tương tác qua menu cho phép lựa chọn chức năng mà họ muốn.
- Ban đầu, danh sách tỉnh/thành phố được nhập tự động từ 1 tập tin (Text file .txt) cho trước có nội dung như dưới đây (hoặc download tại đây):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
1 Ha Noi 3358.9 8418883 2 Thanh pho Ho Chi Minh 2061 9411805 3 Hai Phong 1561.8 2069110 4 Da Nang 1284.9 1191381 5 Ha Giang 7929.5 883388 6 Cao Bang 6700.3 535098 7 Lai Chau 9068.8 480588 8 Lao Cai 6364 756083 9 Tuyen Quang 5867.9 797392 10 Lang Son 8310.2 791872 11 Bac Kan 4860 318083 12 Thai Nguyen 3536.4 1322235 13 Yen Bai 6887.7 838181 14 Son La 14123.5 1286068 15 Phu Tho 3534.6 1495116 16 Vinh Phuc 1235.2 1184074 17 Quang Ninh 6177.7 1358490 18 Bac Giang 3851.4 1858540 19 Bac Ninh 822.7 1450518 20 Hai Duong 1668.2 1932090 21 Hung Yen 930.2 1279308 22 Hoa Binh 4591 868623 23 Ha Nam 860.9 867258 24 Nam Dinh 1668 1771000 25 Thai Binh 1570.5 1876579 26 Ninh Binh 1387 1000093 27 Thanh Hoa 11114.7 3690022 28 Nghe An 16493.7 3417809 29 Ha Tinh 5990.7 1301601 30 Quang Binh 8065.3 905895 31 Quang Tri 4739.8 639414 32 Thua Thien Hue 5048.2 1137045 33 Quang Nam 10574.7 1510960 34 Quang Ngai 5135.2 1234704 35 Kon Tum 9674.2 565685 36 Binh Dinh 6066.2 1487009 37 Gia Lai 15510.8 1566882 38 Phu Yen 5023.4 875127 39 Dak Lak 13030.5 1897710 40 Khanh Hoa 5137.8 1246358 41 Lam Dong 9783.2 1319952 42 Binh Phuoc 6877 1020839 43 Binh Duong 2694.7 2678220 44 Ninh Thuan 3355.3 595698 45 Tay Ninh 4041.4 1190852 46 Binh Thuan 7812.8 1243977 47 Dong Nai 5905.7 3236248 48 Long An 4490.2 1744138 49 Dong Thap 3383.8 1586438 50 An Giang 3536.7 1864651 51 Ba Ria - Vung Tau 1980.8 1181302 52 Tien Giang 2510.5 1783165 53 Kien Giang 6348.8 1730117 54 Can Tho 1439.2 1244736 55 Ben Tre 2394.6 1295067 56 Vinh Long 1475 1022408 57 Tra Vinh 2358.2 1010404 58 Soc Trang 3311.8 1181835 59 Bac Lieu 2669 917734 60 Ca Mau 5294.8 1191999 61 Dien Bien 9541 623295 62 Dak Nong 6509.3 652766 63 Hau Giang 1621.8 728255 |
Lời giải bài tập danh sách liên kết đơn
Tham khảo thành quả trước khi chúng ta bắt đầu để có động lực hơn nha.
Mục này sẽ hướng dẫn các từng bước để giải quyết bài toán trên, hãy cùng bắt đầu nhé. Chương trình sẽ cần sử dụng một số thư viện dưới đây, và một số hằng số giúp code tường minh hơn:
|
1 2 3 4 5 6 |
#include <stdio.h> // Thư viện nhập xuất chuẩn #include <string.h> // Sử dụng các hàm thao tác với chuỗi như strlen, strcpy, ... #include <stdlib.h> // Hàm exit thoát chương trình, atoi, atof để chuyển chuỗi sang số #define TRUE 1 #define INVALID_CITY_CODE -1 |
Xây dựng các kiểu dữ liệu cần thiết
- Chúng ta cần định nghĩa kiểu dữ liệu City theo yêu cầu của đề bài, gồm có các trường mã (code), tên (name), diện tích (area) và dân số (population).
- Chúng ta cũng cần định nghĩa kiểu 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à con trỏ next.
- Trong bài này, mình giả sử code (mã tỉnh,thành phố) là không trùng lặp nên sẽ bỏ qua bước kiểm tra.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Khai báo kiểu cấu trúc City struct City { int code; char name[100]; float area; int population; }; // Định nghĩa cho kiểu "struct City" 1 tên mới ngắn gọn hơn, thay vì khai báo kiểu "struct City" thì ta chỉ cần dùng "City" typedef struct City City; // Khai báo kiểu cấu trúc LinkedList struct LinkedList{ City city; struct LinkedList *next; }; // Định nghĩa cho kiểu "struct LinkedList" 1 tên mới ngắn gọn hơn, thay vì khai báo kiểu "struct LinkedList" thì ta chỉ cần dùng "Node" typedef struct LinkedList *Node; |
Xây dựng các hàm khởi tạo
- Với danh sách liên kết, chúng ta cũng cần khởi tạo Node đầu tiên cho nó, việc khởi tạo rất đơn giản chỉ bằng cách gán Node đó bằng NULL, tức là chưa có dữ liệu (chưa có Node nào cả)
|
1 2 3 4 5 6 |
// Hàm khởi tạo Node đầu tiên của LinkedList Node initHead(){ Node head; head = NULL; return head; } |
- Chúng ta cũng sẽ cần hàm khởi tạo 1 Node khi đã có dữ liệu của Node đó. Sau khi khởi tạo thì chúng ta có thể thêm nó vào danh sách.
|
1 2 3 4 5 6 7 8 |
// Hàm tạo mới 1 Node trong LinkedList Node createNode(City city){ Node temp; // Khai báo 1 Node temp = (Node)malloc(sizeof(struct LinkedList)); // Cấp phát vùng nhớ cho Node temp->next = NULL;// Cho next trỏ tới NULL temp->city = city; // Gán giá trị cho Node return temp; } |
Lưu ý: Ta cần cho con trỏ next của Node được khởi tạo bằng NULL, tức là chưa trỏ tới đâu. Tránh trường hợp nó trỏ lung tung trong bộ nhớ.
- Chúng ta cần có 1 hàm khởi tạo giá trị cho kiểu City đã định nghĩa ở trên qua stdin (nhập từ console). Lý do là bởi chương trình của chúng ta có chức năng thêm, sửa dữ liệu của 1 Node. Khi đó, ta sẽ gọi tới hàm này để tạo dữ liệu thông qua stdin.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
City createCity(){ City newCity; printf("Nhap code: "); scanf("%d", &newCity.code); printf("Nhap ten: "); getchar(); // Bỏ qua '\n' trong bộ đệm fgets(newCity.name, 100, stdin); // Xóa \n ở cuối chuỗi vừa nhập nếu có if ((p=strchr(newCity.name, '\n')) != NULL){ *p = '\0'; } printf("Nhap dien tich: "); scanf("%f", &newCity.area); printf("Nhap dan so: "); scanf("%d", &newCity.population); return newCity; } |
Lưu ý:
- Chúng ta cần hàm getchar() để xóa bộ đệm, cụ thể là xóa bỏ ký tự ‘\n’ còn sót ở 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 biết ‘\n’ trong bộ đệm là hành động kết thúc nhập chuỗi.
- Hàm fgets() đọc cả newline, nên ta cần xóa đi nếu không muốn trường name (tên) có ký tự này.
Các hàm thao tác với danh sách liên kết
Trong bài toán này, chúng ta có các hành động thêm, sửa, xóa Node. Do đó, chúng ta cần xây dựng các hàm sau:
- Hàm addHead: Thêm Node vào đầu DSLK
- Hàm addTail: Thêm Node vào cuối DSLK
- Hàm addAt: Thêm Node vào chỉ số bất kỳ, kế thừa sử dụng hàm addHead và addTail
- Hàm traverser: Duyệt danh sách
- Hàm delHead: Xóa Node đầu tiên của DSLK
- Hàm delTail: Xóa Node cuối của DSLK
- Hàm delAt: Xóa Node tại chỉ số bất kỳ, cũng sẽ kế thừa hàm delHead và delTail ở trên
- Hàm findIndexByCode: Tì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 của DSLK đã được mình trình bày chi tiết tại bài danh sách liên kết đơn. Do vậy, bạn nào chưa hiểu thì có thể quay lại đọc bài đó trước nha.
- Các thao tác với danh sách, mình thích để trong vòng lặp để người dùng có thể lặp lại thao tác đó nếu cần. Người dùng sẽ có quyền chọn có thực hiện thao tác đó tiếp hay không ngay sau khi hoàn thành thao tác.
|
1 2 3 4 5 6 7 8 |
char option; while (TRUE) { // Thao tác ở đây scanf("%c", &option); if (option == 'N' || option == 'n'){ break; } } |
# Hàm duyệt danh sách
|
1 2 3 4 5 6 7 8 9 |
void traverser(Node head){ printf("Danh sach hien tai:\n"); printf("------------------------------------------------------------------------------------------------------------\n"); printf("%10s%50s%20s%20s\n", "Ma Tinh/TP", "Tinh thanh", "Dien tich", "Dan so"); for(Node p = head; p != NULL; p = p->next){ printf("%10d%50s%20f%20d\n", p->city.code, p->city.name, p->city.area, p->city.population); } printf("------------------------------------------------------------------------------------------------------------\n"); } |
- Ở đây, ta đơn giản là bắt đầu từ Node đầu tiên (head) cho tới khi không thể nhảy sang Node tiếp theo.
- Chúng ta in ra dạng bảng bằng cách sử dụng format trong hàm printf().
# Các hàm phục vụ thêm Node
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
// Thêm vào cuối Node addTail(Node head, City value){ Node temp,p;// Khai báo 2 Node tạm temp và p temp = createNode(value);//Gọi hàm createNode để khởi tạo Node temp có next trỏ tới NULL và giá trị là value if(head == NULL){ head = temp; //Nếu linked list đang trống thì Node temp là head luôn } else{ p = head;// Khởi tạo p trỏ tới head while(p->next != NULL){ p = p->next;//Duyệt danh sách liên kết đến cuối. Node cuối là Node có next = NULL } p->next = temp;//Gán next của thằng cuối = temp. Khi đó temp sẽ là thằng cuối(temp->next = NULL mà) } return head; } // Thêm vào đầu Node addHead(Node head, City value){ Node temp = createNode(value); // Khởi tạo Node temp với data = value if(head == NULL){ head = temp; // //Nếu linked list đang trống thì Node temp là head luôn }else{ temp->next = head; // Trỏ next của temp = head hiện tại head = temp; // Đổi head hiện tại = temp(Vì temp bây giờ là head mới mà) } return head; } // Thêm vào ở "chỉ số" (bắt đầu từ 0) bất kỳ, nếu muốn thêm theo "vị trí" (bắt đầu từ 1) thì giảm position đi 1 đơn vị Node addAt(Node head, City value, int position){ position = position - 1; // Thêm theo vị trí if(position == 0 || head == NULL){ head = addHead(head, value); // Nếu vị trí chèn là 0, tức là thêm vào đầu }else{ // Bắt đầu tìm vị trí cần chèn. Ta sẽ dùng k để đếm cho vị trí int k = 1; Node p = head; while(p != NULL && k != position){ p = p->next; ++k; } if(k != position){ // Nếu duyệt hết danh sách lk rồi mà vẫn chưa đến vị trí cần chèn, ta sẽ mặc định chèn cuối // Nếu bạn không muốn chèn, hãy thông báo vị trí chèn không hợp lệ head = addTail(head, value); // printf("Vi tri chen vuot qua vi tri cuoi cung!\n"); }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 City (createCity) phía trên, chúng ta có thể hoàn chỉnh thao tác thêm Node vào danh sách với hàm dưới đây:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
Node addNode(Node head){ City newCity; char option; int position; while (TRUE) { printf("========== Nhap du lieu can them ===============\n"); printf("Nhap vi tri muon them: "); scanf("%d", &position); newCity = createCity(); head = addAt(head, newCity, position); printf("Them thanh cong? Them tiep (Y/n)? "); getchar(); // Bỏ qua '\n' trong bộ đệm scanf("%c", &option); if (option == 'N' || option == 'n'){ break; } } return head; } |
# Các hàm phục vụ xóa Node
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
Node delHead(Node head){ if(head == NULL){ printf("\nCha co gi de xoa het!"); }else{ head = head->next; } return head; } Node delTail(Node head){ if (head == NULL || head->next == NULL){ return delHead(head); } Node p = head; while(p->next->next != NULL){ p = p->next; } p->next = p->next->next; // Cho next bằng NULL return head; } // Xóa Node ở "chỉ số" (bắt đầu từ 0) bất kỳ Node delAt(Node head, int position){ if(position == 0 || head == NULL || head->next == NULL){ head = delHead(head); // Nếu vị trí xóa là 0, tức là thêm vào đầu }else{ // Bắt đầu tìm vị trí cần xóa. Ta sẽ dùng k để đếm cho vị trí int k = 1; Node p = head; while(p->next->next != NULL && k != position){ p = p->next; ++k; } if(k != position){ // Nếu duyệt hết danh sách lk rồi mà vẫn chưa đến vị trí cần chèn, ta sẽ mặc định xóa cuối // Nếu bạn không muốn xóa, hãy thông báo vị trí xóa không hợp lệ head = delTail(head); // printf("Vi tri xoa vuot qua vi tri cuoi cung!\n"); }else{ p->next = p->next->next; } } return head; } |
Ở trên, chúng ta đã có hàm xóa ở chỉ số bất kỳ, vậy để xóa Node theo mã (code) cung cấp. Ta cần viết thêm 1 hàm tìm chỉ số của Node có dữ liệu thành phố mà mã code trùng với giá trị được cung cấp:
|
1 2 3 4 5 6 7 8 9 10 11 |
// Hàm tìm chỉ số của Node có dữ liệu thành phố mà mã code của nó trùng với giá trị cần tìm int 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 tìm thấy } |
Như 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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Node removeNode(Node head){ int code; char option; while (TRUE) { printf("========== Chon Node muon xoa ===============\n"); printf("Nhap ma tinh/thanh pho can xoa: "); scanf("%d", &code); int position = findIndexByCode(head, code); if (position < 0){ printf("Khong tim thay du lieu can xoa! Xoa tiep (Y/n)? "); }else { head = delAt(head, position); printf("Xoa thanh cong? Xoa tiep (Y/n)? "); } getchar(); // Bỏ qua '\n' trong bộ đệm scanf("%c", &option); if (option == 'N' || option == 'n'){ break; } } return head; } |
Các chức năng thêm, xóa Node của danh sách đều có thể thay đổi Node head (Ex: xóa Node head). Do đó, các hàm này đều cần trả về giá trị là Node head mới sau khi thay đổi (có thể vẫn giữ nguyên).
# Hàm sửa giá trị Node trong DSLK
- Hàm này chắc chắn không thể thay đổi Node head, do đó chúng ta sẽ dùng kiểu void
- Đơn giản là ta duyệt qua danh sách, nếu tìm thấy mã code tương ứng, sẽ cho người dùng nhập dữ liệu mới cho Node đó.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
void editNode(Node head){ int code; char option; City newCity; while (TRUE) { printf("========== Chon Node muon sua ===============\n"); printf("Nhap ma tinh/thanh pho can sua: "); scanf("%d", &code); int found = 0; for(Node p = head; p != NULL; p = p->next){ if (p->city.code == code){ found = 1; newCity = createCity(); p->city = newCity; break; } } if (found) { printf("Sua thanh cong! Sua tiep (Y/n)? "); }else { printf("Khong tim thay du lieu! Sua tiep (Y/n)? "); } getchar(); // Bỏ qua '\n' trong bộ đệm scanf("%c", &option); if (option == 'N' || option == 'n'){ break; } } } |
# Hàm sắp xếp danh sách
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
void swapCityData(City *a, City *b){ City tmp = *a; *a = *b; *b = tmp; } // Hàm sắp xếp // Nếu sort theo code, thì byCode = 1, byArea = 0 // Nếu sort theo area, thì byCode = 0, byArea = 1 // Nếu sắp xếp tăng dần thì desc = 0, giảm dần thì desc = 1 void sortCities(Node head, int byCode, int byArea, int desc){ for(Node p = head; p != NULL; p = p->next){ for(Node q = p->next; q != NULL; q = q->next){ if (desc){ 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); } }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 chúng ta cần dùng con trỏ để hàm sử dụng trực tiếp giá trị được truyền vào. Ta chỉ cần đổi giá trị của chúng cho nhau, chứ không cần đổi 2 Node (rắc rối lắm).
- Mình cố ý rút gọn code bằng cách cho các option sắp xếp vào trong hàm sortCities. Mặc dù không tường minh lắm nhưng tách ra thì dài quá.
- Hàm sắp xếp không thay đổi Node head, nên hàm cũng không cần trả về giá trị như các hàm thêm hay 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 còn yêu cầu một số hàm tính tổng diện tích, tìm tỉnh/thành phố có diện tích/dân số lớn nhất, và cả sắp xếp danh sách.
Về cơ bản, các hàm này chỉ cần dựa trên thao tác duyệt danh sách (traveser) là có thể hoàn thành rồi.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
// Hàm tính tổng diện tích các thành phố trong DSLK float sumArea(Node head){ float sum = 0; for(Node p = head; p != NULL; p = p->next){ sum += p->city.area; } return sum; } // Hàm tìm chỉ số của Node có diện tích lớn nhất (giả sử chỉ có 1) // Nếu dữ liệu có nhiều hơn 1, chúng ta tìm max rồi duyệt lại 1 lần nữa để tìm ra các Node 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 số lớn nhất City maxByPopulation(Node head){ City city = head->city; for(Node p = head; p != NULL; p = p->next){ if (p->city.population > city.population){ city = p->city; } } return city; } |
Thao tác đọc dữ liệu từ tệp
Đề bài yêu cầu chúng ta cần khởi tạo danh sách ban đầu bằng cách đọc dữ liệu từ tệp. Do đó, chúng ta cần thêm 1 số hàm con nữa.
- Do dữ liệu tên tỉnh/thành phố có dấu cách nên mình chỉ biết cách đọc từng dòng vào xử lý. Do vậy, mình cần:
- Hàm handleLineData: Tách dòng ra các thành phần con, cụ thể là cho 1 dòng dữ liệu, phải trả về cho mình 1 City. Mình dùng hàm
strtokđể làm việc tách chuỗi. - Hàm readData: Đọc dữ liệu từ file, mỗi dòng đọ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 cách gọi tới addTail hoặc addHead hoặc addAt
- Hàm handleLineData: Tách dòng ra các thành phần con, cụ thể là cho 1 dòng dữ liệu, phải trả về cho mình 1 City. Mình dùng hàm
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
// Hàm tách các thành phần của 1 dòng trong file City handleLineData(char *line){ City city; city.code = INVALID_CITY_CODE; // Khởi tạo giá trị không hợp lệ. Về sau ta có thể kiểm tra. const char delimiter[] = "\t"; 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 readData(Node head, const char* fileName){ FILE* file = fopen(fileName, "r"); if(!file){ printf("Co loi khi mo file : %s\n", fileName); exit(EXIT_FAILURE); } char line[500]; while (fgets(line, sizeof(line), file)) { City 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 lại chỉ là đưa chúng vào hàm main theo 1 trật tự do chúng ta quy định.
Source code hoàn chỉnh tham khảo
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 |
#include <stdio.h> #include <string.h> #include <stdlib.h> #define TRUE 1 #define INVALID_CITY_CODE -1 // Khai báo kiểu cấu trúc City struct City { int code; char name[100]; float area; int population; }; // Định nghĩa cho kiểu "struct City" 1 tên mới ngắn gọn hơn, thay vì khai báo kiểu "struct City" thì ta chỉ cần dùng "City" typedef struct City City; // Khai báo kiểu cấu trúc LinkedList struct LinkedList{ City city; struct LinkedList *next; }; // Định nghĩa cho kiểu "struct LinkedList" 1 tên mới ngắn gọn hơn, thay vì khai báo kiểu "struct LinkedList" thì ta chỉ cần dùng "Node" typedef struct LinkedList *Node; // Hàm tạo mới 1 Node trong LinkedList Node createNode(City city){ Node temp; // Khai báo 1 Node temp = (Node)malloc(sizeof(struct LinkedList)); // Cấp phát vùng nhớ cho Node temp->next = NULL;// Cho next trỏ tới NULL temp->city = city; // Gán giá trị cho Node return temp; } // Thêm vào cuối Node addTail(Node head, City value){ Node temp,p;// Khai báo 2 Node tạm temp và p temp = createNode(value);//Gọi hàm createNode để khởi tạo Node temp có next trỏ tới NULL và giá trị là value if(head == NULL){ head = temp; //Nếu linked list đang trống thì Node temp là head luôn } else{ p = head;// Khởi tạo p trỏ tới head while(p->next != NULL){ p = p->next;//Duyệt danh sách liên kết đến cuối. Node cuối là Node có next = NULL } p->next = temp;//Gán next của thằng cuối = temp. Khi đó temp sẽ là thằng cuối(temp->next = NULL mà) } return head; } // Thêm vào đầu Node addHead(Node head, City value){ Node temp = createNode(value); // Khởi tạo Node temp với data = value if(head == NULL){ head = temp; // //Nếu linked list đang trống thì Node temp là head luôn }else{ temp->next = head; // Trỏ next của temp = head hiện tại head = temp; // Đổi head hiện tại = temp(Vì temp bây giờ là head mới mà) } return head; } // Thêm vào ở "chỉ số" (bắt đầu từ 0) bất kỳ, nếu muốn thêm theo "vị trí" (bắt đầu từ 1) thì giảm position đi 1 đơn vị Node addAt(Node head, City value, int position){ position = position - 1; // Thêm theo vị trí if(position == 0 || head == NULL){ head = addHead(head, value); // Nếu vị trí chèn là 0, tức là thêm vào đầu }else{ // Bắt đầu tìm vị trí cần chèn. Ta sẽ dùng k để đếm cho vị trí int k = 1; Node p = head; while(p != NULL && k != position){ p = p->next; ++k; } if(k != position){ // Nếu duyệt hết danh sách lk rồi mà vẫn chưa đến vị trí cần chèn, ta sẽ mặc định chèn cuối // Nếu bạn không muốn chèn, hãy thông báo vị trí chèn không hợp lệ head = addTail(head, value); // printf("Vi tri chen vuot qua vi tri cuoi cung!\n"); }else{ Node temp = createNode(value); temp->next = p->next; p->next = temp; } } return head; } Node delHead(Node head){ if(head == NULL){ printf("\nCha co gi de xoa het!"); }else{ head = head->next; } return head; } Node delTail(Node head){ if (head == NULL || head->next == NULL){ return delHead(head); } Node p = head; while(p->next->next != NULL){ p = p->next; } p->next = p->next->next; // Cho next bằng NULL return head; } // Xóa Node ở "chỉ số" (bắt đầu từ 0) bất kỳ Node delAt(Node head, int position){ if(position == 0 || head == NULL || head->next == NULL){ head = delHead(head); // Nếu vị trí xóa là 0, tức là thêm vào đầu }else{ // Bắt đầu tìm vị trí cần xóa. Ta sẽ dùng k để đếm cho vị trí int k = 1; Node p = head; while(p->next->next != NULL && k != position){ p = p->next; ++k; } if(k != position){ // Nếu duyệt hết danh sách lk rồi mà vẫn chưa đến vị trí cần chèn, ta sẽ mặc định xóa cuối // Nếu bạn không muốn xóa, hãy thông báo vị trí xóa không hợp lệ head = delTail(head); // printf("Vi tri xoa vuot qua vi tri cuoi cung!\n"); }else{ p->next = p->next->next; } } return head; } void traverser(Node head){ printf("Danh sach hien tai:\n"); printf("------------------------------------------------------------------------------------------------------------\n"); printf("%10s%50s%20s%20s\n", "Ma Tinh/TP", "Tinh thanh", "Dien tich", "Dan so"); for(Node p = head; p != NULL; p = p->next){ printf("%10d%50s%20f%20d\n", p->city.code, p->city.name, p->city.area, p->city.population); } printf("------------------------------------------------------------------------------------------------------------\n"); } // Hàm khởi tạo Node đầu tiên của LinkedList Node initHead(){ Node head; head = NULL; return head; } // Hàm tách các thành phần của 1 dòng trong file City handleLineData(char *line){ City city; city.code = INVALID_CITY_CODE; // Khởi tạo giá trị không hợp lệ. Về sau ta có thể kiểm tra. const char delimiter[] = "\t"; 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 readData(Node head, const char* fileName){ FILE* file = fopen(fileName, "r"); if(!file){ printf("Co loi khi mo file : %s\n", fileName); exit(EXIT_FAILURE); } char line[500]; while (fgets(line, sizeof(line), file)) { City city = handleLineData(line); if (city.code != INVALID_CITY_CODE) { head = addTail(head, city); } } fclose(file); return head; } City createCity(){ City newCity; char *p; printf("Nhap code: "); scanf("%d", &newCity.code); printf("Nhap ten: "); getchar(); fgets(newCity.name, 100, stdin); // Xóa \n ở cuối chuỗi vừa nhập nếu có if ((p=strchr(newCity.name, '\n')) != NULL){ *p = '\0'; } printf("Nhap dien tich: "); scanf("%f", &newCity.area); printf("Nhap dan so: "); scanf("%d", &newCity.population); return newCity; } Node addNode(Node head){ City newCity; char option; int position; while (TRUE) { printf("========== Nhap du lieu can them ===============\n"); printf("Nhap vi tri muon them: "); scanf("%d", &position); newCity = createCity(); head = addAt(head, newCity, position); printf("Them thanh cong? Them tiep (Y/n)? "); getchar(); // Bỏ qua '\n' trong bộ đệm scanf("%c", &option); if (option == 'N' || option == 'n'){ break; } } return head; } // Hàm tìm chỉ số của Node có dữ liệu thành phố mà mã code của nó trùng với giá trị cần tìm int 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 tìm thấy } void editNode(Node head){ int code; char option; City newCity; while (TRUE) { printf("========== Chon Node muon sua ===============\n"); printf("Nhap ma tinh/thanh pho can sua: "); scanf("%d", &code); int found = 0; for(Node p = head; p != NULL; p = p->next){ if (p->city.code == code){ found = 1; newCity = createCity(); p->city = newCity; break; } } if (found) { printf("Sua thanh cong! Sua tiep (Y/n)? "); }else { printf("Khong tim thay du lieu! Sua tiep (Y/n)? "); } getchar(); // Bỏ qua '\n' trong bộ đệm scanf("%c", &option); if (option == 'N' || option == 'n'){ break; } } } Node removeNode(Node head){ int code; char option; while (TRUE) { printf("========== Chon Node muon xoa ===============\n"); printf("Nhap ma tinh/thanh pho can xoa: "); scanf("%d", &code); int position = findIndexByCode(head, code); if (position < 0){ printf("Khong tim thay du lieu can xoa! Xoa tiep (Y/n)? "); }else { head = delAt(head, position); printf("Xoa thanh cong? Xoa tiep (Y/n)? "); } getchar(); // Bỏ qua '\n' trong bộ đệm scanf("%c", &option); if (option == 'N' || option == 'n'){ break; } } return head; } // Hàm tính tổng diện tích các thành phố trong DSLK float sumArea(Node head){ float sum = 0; for(Node p = head; p != NULL; p = p->next){ sum += p->city.area; } return sum; } // Hàm tìm chỉ số của Node có diện tích lớn nhất (giả sử chỉ có 1) // Nếu dữ liệu có nhiều hơn 1, chúng ta tìm max rồi duyệt lại 1 lần nữa để tìm ra các Node 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 số lớn nhất City maxByPopulation(Node head){ City city = head->city; for(Node p = head; p != NULL; p = p->next){ if (p->city.population > city.population){ city = p->city; } } return city; } void swapCityData(City *a, City *b){ City tmp = *a; *a = *b; *b = tmp; } // Hàm sắp xếp // Nếu sort theo code, thì byCode = 1, byArea = 0 // Nếu sort theo area, thì byCode = 0, byArea = 1 // Nếu sắp xếp tăng dần thì desc = 0, giảm dần thì desc = 1 void sortCities(Node head, int byCode, int byArea, int desc){ for(Node p = head; p != NULL; p = p->next){ for(Node q = p->next; q != NULL; q = q->next){ if (desc){ 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); } }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); } } } } } void printMenu(){ printf("================== MENU ====================\n"); printf("1. Duyet danh sach\n"); printf("2. Them du lieu (them Node)\n"); printf("3. Sua du lieu (sua Node)\n"); printf("4. Xoa du lieu (xoa Node)\n"); printf("5. Tinh tong dien tich\n"); printf("6. Tim dia chi cua Node co dien tich lon nhat\n"); printf("7. Tim tinh co dan so lon nhat\n"); printf("8. Sap xep danh sach theo ma tinh\n"); printf("9. Sap xep danh sach theo dien tich\n"); printf("10. Thoat chuong trinh\n"); printf("============================================\n"); } int main(){ Node head = initHead(); head = readData(head, "DS_CAC_TINH.txt"); traverser(head); int option; City result; while (TRUE) { printMenu(); printf("Nhap lua chon cua ban (1-10): "); scanf("%d", &option); switch(option) { case 1: traverser(head); break; case 2: head = addNode(head); break; case 3: editNode(head); break; case 4: head = removeNode(head); break; case 5: printf("Tong dien tich: %f\n", sumArea(head)); break; case 6: printf("Tinh co dien tich lon nhat o vi tri: %d\n", indexOfMaxArea(head) + 1); // vị trí = chỉ số + 1 break; case 7: result = maxByPopulation(head); printf("%s la noi co dien tich lon nhat voi %d nguoi!\n", result.name, result.population); break; case 8: sortCities(head, 1, 0, 0); traverser(head); break; case 9: sortCities(head, 0, 1, 0); traverser(head); break; case 10: printf("Ket thuc chuong trinh!...\n"); exit(EXIT_SUCCESS); default: printf("Lua chon khong dung, vui long nhap lai!\n"); break; } } } |
Như vậy, bài tập danh sách liên kết đơn tổng hợp tới đây đã hoàn chỉnh. Thực ra chưa hoàn chỉnh lắm, các bạn có thể cải tiến một số vấn đề dưới đây:
- Trường mã tỉnh/thành phố (code) có thể bị trùng, chúng ta nên có chức năng kiểm tra trùng này.
- Hàm sắp xếp chưa nhanh, độ phức tạp O(n^2)
- Chưa có chức năng lưu thay đổi vào file, thêm mỏi tay xong tắt chương trình là mất ^^.
