Bài tập danh sách liên kết đơn tổng hợp

0
1248
Bài số 9 trong 10 bài của khóa học Cấu trúc dữ liệu

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):

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:

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.

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ả)

  • 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.

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.

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.

# Hàm duyệt danh sách

  • Ở đâ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

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:

# Các hàm phục vụ xóa Node

Ở 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:

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:

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 đó.

# Hàm sắp xếp danh sách

  • 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.

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

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

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 ^^.
Các bài viết trong khóa họcBài trước: Cây tìm kiếm nhị phân – Binary search treeBài sau: Danh sách kề (Adjacency list)
Sáng lập cộng đồng Lập Trình Không Khó với mong muốn giúp đỡ các bạn trẻ trên con đường trở thành những lập trình viên tương lai. Tất cả những gì tôi viết ra đây chỉ đơn giản là sở thích ghi lại các kiến thức mà tôi tích lũy được.
Subscribe
Notify of
guest
0 Bình luận
Inline Feedbacks
View all comments