Cài đặt danh sách liên kết đơn trong C
|

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:

Đề 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 ^^.

Similar Posts

Subscribe
Notify of
guest
0 Bình luận
Inline Feedbacks
View all comments