Giải thuật và lập trình: §4. Cấu trúc dữ liệu biểu diễn danh sách


KHÁI NIỆM DANH SÁCH

Danh sách là một tập sắp thứ tự các phần tử cùng một kiểu. Đối với danh sách, người ta có một số thao tác: Tìm một phần tử trong danh sách, chèn một phần tử vào danh sách, xoá một phần tử khỏi danh sách, sắp xếp lại các phần tử trong danh sách theo một trật tự nào đó v.v…

BIỂU DIỄN DANH SÁCH TRONG MÁY TÍNH

Việc cài đặt một danh sách trong máy tính tức là tìm một cấu trúc dữ liệu cụ thể mà máy tính hiểu được để lưu các phần tử của danh sách đồng thời viết các đoạn chương trình con mô tả các thao tác cần thiết đối với danh sách.

Cài đặt bằng mảng một chiều

Khi cài đặt danh sách bằng một mảng, thì có một biến nguyên n lưu số phần tử hiện có trong danh sách. Nếu mảng được đánh số bắt đầu từ 1 thì các phần tử trong danh sách được cất giữ trong mảng bằng các phần tử được đánh số từ 1 tới n.

Chèn phần tử vào mảng:

Mảng ban đầu:

http://v1study.com/public/images/article/giai-thuat-lap-trinh-mang-ban-dau.png

Nếu muốn chèn một phần tử V vào mảng tại vị trí p, ta phải:

Dồn tất cả các phần tử từ vị trí p tới tới vị trí n về sau một vị trí:

http://v1study.com/public/images/article/giai-thuat-lap-trinh-don-tu-p-den-n.png

Đặt giá trị V vào vị trí p:

http://v1study.com/public/images/article/giai-thuat-lap-trinh-sau-khi-chen-v.png

Tăng n lên 1

Xoá phần tử khỏi mảng

Mảng ban đầu:

http://v1study.com/public/images/article/giai-thuat-lap-trinh-mang-ban-dau.png

Muốn xoá phần tử thứ p của mảng mà vẫn giữ nguyên thứ tự các phần tử còn lại, ta phải:

Dồn tất cả các phần tử từ vị trí p + 1 tới vị trí n lên trước một vị trí:

http://v1study.com/public/images/article/giai-thuat-lap-trinh-don-len-truoc.png

Giảm n đi 1

http://v1study.com/public/images/article/giai-thuat-lap-trinh-sau-khi-xoa.png

Trong trường hợp cần xóa một phần tử mà không cần duy trì thứ tự của các phần tử khác, ta chỉ cần đảo giá trị của phần tử cần xóa cho phần tử cuối cùng rồi giảm số phần tử của mảng (n) đi 1.

Cài đặt bằng danh sách nối đơn

Danh sách nối đơn gồm các nút được nối với nhau theo một chiều. Mỗi nút là một bản ghi (record) gồm hai trường:

Trường thứ nhất chứa giá trị lưu trong nút đó

Trường thứ hai chứa liên kết (con trỏ) tới nút kế tiếp, tức là chứa một thông tin đủ để biết nút kế tiếp nút đó trong danh sách là nút nào, trong trường hợp là nút cuối cùng (không có nút kế tiếp), trường liên kết này được gán một giá trị đặc biệt.

http://v1study.com/public/images/article/giai-thua-va-lap-trinh-cau-truc-cua-danh-sach-noi-don.png

Cấu trúc nút của danh sách nối đơn

Nút đầu tiên trong danh sách được gọi là chốt của danh sách nối đơn (Head). Để duyệt danh sách nối đơn, ta bắt đầu từ chốt, dựa vào trường liên kết để đi sang nút kế tiếp, đến khi gặp giá trị đặc biệt (duyệt qua nút cuối) thì dừng lại

http://v1study.com/public/images/article/giai-thua-va-lap-trinh-danh-sach-noi-don.png

Danh sách nối đơn

Chèn phần tử vào danh sách nối đơn:

Danh sách ban đầu:

http://v1study.com/public/images/article/giai-thua-va-lap-trinh-danh-sach-ban-dau.png

Muốn chèn thêm một nút chứa giá trị V vào vị trí của nút p, ta phải:

 

a. Tạo ra một nút mới NewNode chứa giá trị V:

http://v1study.com/public/images/article/giai-thua-va-lap-trinh-danh-nut-moi-newnode.png

b. Tìm nút q là nút đứng trước nút p trong danh sách (nút có liên kết tới p).

  b1) Nếu tìm thấy thì chỉnh lại liên kết: q liên kết tới NewNode, NewNode liên kết tới p

http://v1study.com/public/images/article/giai-thua-va-lap-trinh-q-lien-ket-toi-newnode.png

  b2) Nếu không có nút đứng trước nút p trong danh sách thì tức là p = Head, ta chỉnh lại liên kết: NewNode liên kết tới Head (cũ) và đặt lại Head = NewNode

Xoá phần tử khỏi danh sách nối đơn:

Danh sách ban đầu:

http://v1study.com/public/images/article/giai-thua-va-lap-trinh-danh-sach-ban-dau.png

Muốn huỷ nút p khỏi danh sách nối đơn, ta phải:

Tìm nút q là nút đứng liền trước nút p trong danh sách (nút có liên kết tới p)

Nếu tìm thấy thì chỉnh lại liên kết: q liên kết thẳng tới nút liền sau p, khi đó quá trình duyệt danh sách bắt đầu từ Head khi duyệt tới q sẽ nhảy qua không duyệt p nữa. Trên thực tế khi cài đặt bằng các biến động và con trỏ, ta nên có thao tác giải phóng bộ nhớ đã cấp cho nút p

http://v1study.com/public/images/article/giai-thua-va-lap-trinh-giai-phong-vung-nho.png

 

Nếu không có nút đứng trước nút p trong danh sách thì tức là p = Head, ta chỉ việc đặt lại Head bằng nút đứng kế tiếp Head (cũ) trong danh sách. Sau đó có thể giải phóng bộ nhớ cấp cho nút p (Head cũ)

Cài đặt bằng danh sách nối kép

Danh sách nối kép gồm các nút được nối với nhau theo hai chiều. Mỗi nút là một bản ghi (record) gồm ba trường:

  • Trường thứ nhất chứa giá trị lưu trong nút đó

  • Trường thứ hai (Next) chứa liên kết (con trỏ) tới nút kế tiếp, tức là chứa một thông tin đủ để biết nút kế tiếp nút đó là nút nào, trong trường hợp là nút cuối cùng (không có nút kế tiếp), trường liên kết này được gán một giá tị đặc biệt.

  • Trường thứ ba (Prev) chứa liên kết (con trỏ) tới nút liền trước, tức là chứa một thông tin đủ để biết nút đứng trước nút đó trong danh sách là nút nào, trong trường hợp là  nút đầu tiên (không có nút liền trước) trường này được gán một giá trị đặc biệt.

http://v1study.com/public/images/article/giai-thuat-va-lap-trinh-cau-truc-cua-danh-sach-noi-kep.png

Cấu trúc nút của danh sách nối kép

Khác với danh sách nối đơn, danh sách nối kép có hai chốt: Nút đầu tiên trong danh sách  được gọi là First, nút cuối cùng trong danh sách được gọi là Last. Để duyệt danh sách nối kép, ta có hai cách: Hoặc bắt đầu từ First, dựa vào liên kết Next để đi sang nút kế tiếp, đến khi gặp giá trị đặc biệt (duyệt qua nút cuối) thì dừng lại. Hoặc bắt đầu từ Last, dựa vào liên kết Prev để đi sang nút liền trước, đến khi gặp giá trị đặc biệt (duyệt qua nút đầu) thì dừng lại

http://v1study.com/public/images/article/giai-thuat-va-lap-trinh-danh-sach-noi-kep.png

Danh sách nối kép

Việc chèn / xoá vào danh sách nối kép cũng đơn giản chỉ là kỹ thuật chỉnh lại các mối liên kết giữa các nút cho hợp lý, ta coi như bài tập.

Cài đặt bằng danh sách nối vòng một hướng

Trong danh sách nối đơn, phần tử cuối cùng trong danh sách có trường liên kết được gán một giá trị đặc biệt (thường sử dụng nhất là giá trị nil). Nếu ta cho trường liên kết của phần tử cuối cùng trỏ thẳng về phần tử đầu tiên của danh sách thì ta sẽ được một kiểu danh sách mới gọi là danh sách nối vòng một hướng.

http://v1study.com/public/images/article/giai-thuat-va-lap-trinh-danh-sach-mot-huong.png

Danh sách nối vòng một hướng

Đối với danh sách nối vòng, ta chỉ cần biết một nút bất kỳ của danh sách là ta có thể duyệt được hết các nút trong danh sách bằng cách đi theo hướng của các liên kết. Chính vì lý do này, khi chèn xoá vào danh sách nối vòng, ta không phải xử lý các trường hợp riêng khi chèn xoá tại vị trí của chốt

Cài đặt bằng danh sách nối vòng hai hướng

Danh sách nối vòng một hướng chỉ cho ta duyệt các nút của danh sách theo một chiều, nếu cài đặt bằng danh sách nối vòng hai hướng thì ta có thể duyệt các nút của danh sách cả theo chiều ngược lại nữa. Danh sách nối vòng hai hướng có thể tạo thành từ danh sách nối kép nếu ta cho trường Prev của nút First trỏ thẳng tới nút Last còn trường Next của nút Last thì trỏ thẳng về nút First.

http://v1study.com/public/images/article/giai-thuat-va-lap-trinh-danh-sach-noi-vong-hai-huong.png

Danh sách nối vòng hai hướng

Bài tập

Bài 1

Lập chương trình quản lý danh sách học sinh, tuỳ chọn loại danh sách cho phù hợp, chương trình có những chức năng sau: (Hồ sơ một học sinh giả sử có: Tên, lớp, số điện thoại, điểm  TB …)

Cho phép nhập danh sách học sinh từ bàn phím hay từ file. Cho phép in ra danh sách học sinh gồm có tên và xếp loại Cho phép in ra danh sách học sinh gồm các thông tin đầy đủ

Cho phép nhập vào từ bàn phím một tên học sinh và một tên lớp, tìm xem có học sinh có tên nhập vào trong lớp đó không ?. Nếu có thì in ra số điện thoại của học sinh đó.

Cho phép vào một hồ sơ học sinh mới từ bàn phím, bổ sung học sinh đó vào danh sách học sinh, in ra danh sách mới.

Cho phép nhập vào từ bàn phím tên một lớp, loại bỏ tất cả các học sinh của lớp đó khỏi danh sách, in ra danh sách mới.

Có chức năng sắp xếp danh sách học sinh theo thứ tự giảm dần của điểm trung bình

Cho phép nhập vào hồ sơ một học sinh mới từ bàn phím, chèn học sinh đó vào danh sách mà không làm thay đổi thứ tự đã sắp xếp, in ra danh sách mới.

Cho phép lưu trữ lại trên đĩa danh sách học sinh khi đã thay đổi.

Bài 2

Có n người đánh số từ 1 tới n ngồi quanh một vòng tròn (n £ 10000), cùng chơi một trò chơi: Một người nào đó đếm 1, người kế tiếp, theo chiều kim đồng hồ đếm 2… cứ như vậy cho tới người đếm đến một số nguyên tố thì phải ra khỏi vòng tròn, người kế tiếp lại đếm bắt đầu từ 1: Hãy lập chương trình

Nhập vào 2 số n và S từ bàn phím

  • Cho biết nếu người thứ nhất là người đếm 1 thì người còn lại cuối cùng trong vòng  tròn là người thứ mấy

  • Cho biết nếu người còn lại cuối cùng trong vòng tròn là người thứ k thì người đếm 1 là người nào?.

Giải quyết hai yêu cầu trên trong trường hợp: đầu tiên trò chơi được đếm theo chiều kim đồng hồ, khi có một người bị ra khỏi cuộc chơi thì vẫn là người kế tiếp đếm 1 nhưng quá trình đếm ngược lại (tức là ngược chiều kim đồng hồ)

« Prev
Next »