Dùng mảng một chiều để lưu trữ một lớp học có N sinh viên. Biết rằng mỗi sinh viên bao gồm các thông tin sau: Tên (chuỗi ký tự), Mã số sinh viên (chuỗi ký tự), Điểm trung bình. Hãy viết hàm thực hiện các yêu cầu sau:

1. In danh sách sinh viên ra màn hình
2. Liệt kê những sinh viên có điểm trung bình cao nhất trong lớp học.
3. Cho biết số sinh viên có điểm trung bình >=5. Nếu không có thì thông báo không có.
4. Tìm một sinh viên có tên X trong lớp học (X nhập từ bàn phím)
5. Xoá một sinh viên có mã số cho trước trong lớp học. Nếu không có thì thông báo không có.
6. Sắp xếp danh sách sinh viên tăng theo điểm trung bình bằng thuật toán sắp xếp mà các bạn đã học (Selection Sort, Interchange Sort, Binary Sort)
7. Chèn một sinh viên vào lớp học, biết ràng sau khi chèn danh sách sinh viên vẫn tăng dần theo điểm trung bình.

1

Chương 2. CÁC CẤU TRÚC DỮ LIỆU CƠ BẢN

2.1.Danh sách - LIST

Tóm tắt :

1. Khái niệm

2. Cài đặt danh sách tuyến tính bằng mảng

3. Danh sách liên kết đơn

2.1.1. Khái niệm danh sách - LIST

Danh sách là một dãy các phần tử, mỗi phần tử gọi là một nút (node).

Khi các nút chỉ lưu trữ các thông tin dữ liệu và được lưu trữ một cách tuần tự thì gọi là danh sách

thường hay tuyến tính, kiểu danh sách này được xử lý theo tuần tự, tuyến tính.

Khi các nút lưu trữ các thông tin dữ liệu và địa chỉ của nút kế tiếp thì gọi là danh sách liên kết

đơn.

Khi các nút lưu trữ thông tin dữ liệu và 2 địa chỉ liên kết với nút trước và nút sau nó thì gọi là

danh sách liên kết đôi.

Danh sách được tổ chức, cấu trúc theo kiểu dữ liệu có tên kiểu là list.

Kiểu dữ liệu list dùng cho danh sách là một trong các kiểu dữ liệu mà được hỗ trợ bởi thư viện

Standard Template Library (STL) trong C++, khi trong chương trình có dùng biến kiểu list thì

phải viết dòng khai báo

include vào phần đầu chương trình.

Cấu trúc dữ liệu list được hỗ trợ bởi STL là một danh sách liên kết đôi, khác với kiểu cấu trúc

Vector là kiểu mảng động (dynamic array), là mảng được cấp phát bộ nhớ động bằng

Allocator(đã học ở phần Con trỏ).

Trong thực tế, một danh sách thông thường sẽ dùng cấu trúc dữ liệu Vector, các thao tác xử lý

chủ yếu là thêm phần tử vào cuối mảng và truy cập phần tử theo theo ngẫu nhiên (địa chỉ) nên

nhanh và dễ. Tuy nhiên, việc thêm phần tử vào cuối mảng sẽ nhanh hơn việc chèn thêm phần tử

vào đầu hay giữa mảng do việc trước khi chèn vào một vị trí k, phải lùi các phần tử từ vị trí k đến

cuối mảng ra sau 1 vị trí.

Danh sách liên kết đôi chỉ nên dùng khi phải thực hiện nhiều lần các phép chèn/xóa phần tử vào

đầu hay giữa danh sách, ít phải truy nhập ngẫu nhiên tới các phần tử. Việc chèn/xóa phần tử

trong danh sách liên kết đôi chỉ đơn giản là thay đổi thông tin liên kết ở 2 bên trái-phải của nút.

Tuy nhiên, vì các nút không có địa chỉ index thực nên việc truy nhập các phần tử nút chậm, phải

duyệt danh sách cho đến khi gặp được phần tử cần thiết. Trong học phần này chỉ xét danh sách

liên kết đơn, sang học phần 2 mới xét danh sách liên kết đôi.

Những thao tác cơ bản đối với danh sách liên kết đơn :

1.Khai báo cấu trúc nút, cấu trúc danh sách liên kết đơn

2.Tạo một danh sách rỗng ban đầu, tạo một nút mới nhận dữ liệu

3 .Thêm nút mới vào danh sách liên kết đơn

4.Xoá một phần tử từ danh sách liên kết đơn

5.Duyệt, xử lý các phần tử danh sách liên kết đơn