Bài tập danh sách liên kết đơn tổng hợp
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
NỘI DUNG BÀI VIẾT
Đề 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 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:
#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.
// 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ả)
// 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.
// 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.
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.
char option;
while (TRUE) {
// Thao tác ở đây
scanf("%c", &option);
if (option == 'N' || option == 'n'){
break;
}
}
# Hàm duyệt danh sách
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
// 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:
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
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:
// 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:
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 đó.
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
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.
// 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 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
#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 ^^.
