CÁC BÀI TẬP VỀ DANH SÁCH LIÊN KẾT ĐƠN

  -  
Một số vấn đề cơ bản về “danh sách liên kết đơn”

Tham khảo: http://agreenet.vn/baiviet/laptrinh/c/?eq=Ak7wytsN1FgZurlSBW9Flg==

Để làm quen với các thao tác cơ bản trên danh sách liên kết, ta thực hiện trên một danh sách đơn giản, đó là DANH SÁCH SỐ NGUYÊN (mỗi nút chỉ chứa một số nguyên). Chúng ta sẽ tìm hiểu các phần sau:

Khai báo danh sách (cấu trúc dữ liệu)Cấp phát và giải phóng vùng nhớ một nút.Thêm một nút vào đầu danh sách.Thêm một nút vào cuối danh sách.Duyệt danh sách.Xóa một nút trong danh sách.

Bạn đang xem: Các bài tập về danh sách liên kết đơn

Khai báo danh sách (cấu trúc dữ liệu)Trước tiên là khai báo các thư viện cần thiết:
#include //để sử dụng hàm: printf, scanf
#include //để sử dụng hàm: getch
#include //để sử dụng hàm: malloc (cấp phát vùng nhớ cho 1 nút)

Có nhiều cách để khai báo cấu trúc danh sách liên kết đơn.

Cách 1. Struct đơn thuần


struct Nut
{
int GiaTri;
struct Nut *Tiep;
};
struct Nut *dau, *cuoi;

Với cách khai báo trên, Nut chỉ là một struct đơn thuần (chứ không phải một kiểu), do vậy mỗi khi khai báo biến nào đó có kiểu liên quan đến cấu trúc Nut thì phải có từ khóa struct phía trước (ví dụ: struct Nut *p). Cách này ít khi được sử dụng.

Cách 2. Khai báo KIỂU MỚI (typedef)


typedef struct SoNguyen
{
int GiaTri;
struct SoNguyen *Tiep;
} Nut;
Nut *dau, *cuoi;

Với cách khai báo này, song song với việc khai báo cấu trúc SoNguyen, ta còn định nghĩa thêm một “kiểu” (type) mới có tên là Nut (chính là kiểu có cấu trúc SoNguyen). Do vậy, sau này mỗi khi khai báo biến nào đó có kiểu liên quan đến cấu trúc SoNguyen thì thay vì khai báo struct SoNguyen *p ta khai báo đơn giả: Nut *p. Nghĩa là Nut được sử dụng như một kiểu, tương tự như kiểu int hay float. Một chú ý là trường Tiep chưa thể khai báo Nut *Tiep vì lúc này C chưa biết Nut là một kiểu, do vậy phải khai báo là struct SoNguyen *Tiep.

Cách 3. TroNut


typedef struct SoNguyen
{
int GiaTri;
struct SoNguyen *Tiep;
} Nut;
typedef Nut *TroNut;
TroNut dau, cuoi;

Với cách khai báo này, kiểu TroNut là một kiểu con trỏ trỏ đến một nút trong danh sách. Nghĩa là, thay vì khai báo Nut *dau, *cuoi, ta khai báo TroNut dau, cuoi.

Xem thêm: Dọn Sạch Newsfeed Bằng Cách Ẩn Thông Báo Kết Bạn Trên Facebook

Nắm vững cách biểu diễn danh sách liên kếtTa có thể biểu diễn danh sách liên kết đơn như sau:

*

Tuy nhiên, hình ảnh trên chỉ là biểu diễn “ngắn gọn”. Để nắm rõ, ta cần phân biệt hai vùng nhớ: vùng nhớ TĨNH (kích thước nhỏ) và vùng nhớ ĐỘNG (thường gọi là “heap”, kích thước lớn).

Các biến khai báo toàn cục, trong chương trình con hay trong tham số của chương trình con là những biến tĩnh, nằm ở vùng nhớ tĩnh (ví dụ: int x; float y; char z; short *a;). Ở đây ta tạm “lơ” qua nội tình bên trong vùng nhớ tĩnh. Các biến tĩnh khi khai báo thì đã được cấp phát vùng nhớ.

Vùng nhớ động chứa các “biến động”. Các biến động không có tên mà được quản lý bởi các biến con trỏ (pointer). Chú ý, biến con trõ nằm trong vùng nhớ tĩnh!

Các “nút” trong danh sách là các “biến động” nằm trong HEAP, còn những con trỏ khai báo trong chương trình chính, ví dụ Nut *dau, *cuoi, *p là những “biến tĩnh”.

*

Và cũng để đơn giản, trong trường hợp có nhiều con trỏ trỏ đến các nút, ta có thể biểu diễn như sau:

*

Nghĩa là con trỏ dau trỏ đến nút đầu tiên của danh sách (nút có giá trị là 1), con trỏ p trỏ đến nút có giá trị 5, và con trỏ cuoi trỏ đến nút cuối cùng của danh sách (nút có giá trị là 9). Tuy nhiên, chính xác hơn sẽ là thế này:

*
Cấp phát vùng nhớ cho một nút
Ta có thể hình dung việc “cấp phát vùng nhớ cho p” như 2 hình dưới đây. Trước khi cấp phát, con trỏ p không trỏ đến nút nào:

*

Sau khi cấp phát, nó trỏ đến một nút (biến động) ở vùng nhớ động (heap):

*
Bài 1. Danh sách ĐIỂM SINH VIÊNNgười ta quản lý điểm của các sinh viên trong lớp bằng cách sử dụng một danh sách liên kết đơn (mà ta gọi là danh sách điểm) với nút đầu được trỏ bởi con trỏ dau. Mỗi nút của danh sách điểm là một bản ghi gồm 3 trường: trường HoTen để lưu họ tên sinh viên (là một chuỗi có tối đa 30 ký tự), trường Diemlưu điểm của sinh viên và trường Tiep lưu địa chỉ của nút tiếp theo.

Xem thêm: Cách Tải Facebook Messenger Trên Pc, Cách Tải Messenger Phiên Bản Mới Trên Pc

Xây dựng chương trình gồm các hàm sau:

themDau để thêm một nút vào đầu danh sách.themCuoi để thêm một nút vào cuối danh sách.taoDS để tạo ds với thông tin được nhập từ bàn phím (dừng khi nhập họ tên là một chuỗi rỗng).hienThiDS để hiển thị danh sách (cách trình bày như ở ví dụ phía dưới).soSvThiLai để đếm xem trong danh sách có bao nhiêu sinh viên thi lại (điểm ≤ 5).hienThiSvDiemMax để hiển thị (các) sinh viên có điểm cao nhấttimTheoTen để tìm kiếm và hiển thị (các) sinh viên theo tên.main để thử nghiệm các hàm vừa xây dựng ở trên.

Nhập họ tên sinh viên: Le Van HuanNhập điểm: 1Nhap ho ten sinh vien: Phan Cong MinhNhập điểm: 9Nhap ho ten sinh vien: Tran Thi LanhNhập điểm: 4Nhap ho ten sinh vien: Mai Tien HuanNhập điểm: 9Nhập họ tên sinh viên:Danh sách sinh viên vừa nhập:- Le Van Huan (1 diem)- Phan Cong Minh (9 diem)- Tran Thi Lanh (4 diem)- Mai Tien Huan (9 diem) Có 2 sinh viên phải thi lại.Những sinh viên có điểm tối đa (9 điểm):- Phan Cong Minh (9 diem)- Mai Tien Huan (9 diem) Những sinh viên có tên "Huan":- Le Van Huan (1 diem)- Mai Tien Huan (9 diem)Khai báo danh sách (cấu trúc dữ liệu)Khai báo thư viện cần thiết: