Một số vụ việc cơ bạn dạng về “danh sách links đơn”

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

Để có tác dụng quen với các làm việc cơ bạn dạng trên danh sách liên kết, ta triển khai trên một danh sách đơn giản, chính là DANH SÁCH SỐ NGUYÊN (mỗi nút chỉ chứa một số trong những nguyên). Chúng ta sẽ tò mò các phần sau:

Khai báo list (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 thời điểm cuối danh sách.Duyệt danh sách.Xóa một nút vào danh sách.

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

Bạn đang xem: bài bác tập danh sách link đơn gồm lời giải

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

Có nhiều phương pháp để khai báo cấu trúc danh sách links đơn.

Cách 1. Struct solo thuần

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

Với giải pháp khai báo trên, Nut chỉ là 1 trong những struct đơn thuần (chứ chưa hẳn một kiểu), vì vậy mọi khi khai báo biến đổi nào đó có kiểu tương quan đến kết cấu Nut thì phải gồm từ khóa struct phía đằng trước (ví dụ: struct Nut *p). Giải pháp này hiếm 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 câu hỏi khai báo kết cấu SoNguyen, ta còn quan niệm thêm một “kiểu” (type) mới mang tên là Nut (chính là loại có cấu tạo SoNguyen). Vì vậy, sau này mỗi khi khai báo phát triển thành nào đó gồm kiểu liên quan đến kết cấu SoNguyen thì thay vị khai báo struct SoNguyen *p ta khai báo 1-1 giả: Nut *p. Nghĩa là Nut được thực hiện như một kiểu, giống như như hình dáng int xuất xắc float. Một để ý là trường Tiep không thể khai báo Nut *Tiep vì bây giờ C chưa chắc chắn Nut là 1 trong những 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;Nắm vững giải pháp biểu diễn list liên kếtTa hoàn toàn có thể biểu diễn danh sách link đơn như sau:


*

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

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

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

Các “nút” trong list là những “biến động” phía trong HEAP, còn những nhỏ trỏ khai báo trong công tác chính, lấy một ví dụ Nut *dau, *cuoi, *p là đa số “biến tĩnh”.


*

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


*

Nghĩa là nhỏ trỏ dau trỏ mang lại nút trước tiên của danh sách (nút có giá trị là 1), nhỏ trỏ phường trỏ mang lại nút có mức giá trị 5, và nhỏ trỏ cuoi trỏ mang đến nút ở đầu cuối của danh sách (nút có giá trị là 9). Tuy nhiên, đúng chuẩn hơn sẽ là núm này:


*

Cấp phát vùng nhớ cho một nútTa hoàn toàn có thể hình dung câu hỏi “cấp phạt vùng nhớ đến 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:


*

Bài 1. List ĐIỂM SINH VIÊNNgười ta quản lý điểm của các sinh viên vào lớp bằng phương pháp sử dụng một danh sách links đơn (mà ta gọi là danh sách điểm) với nút đầu được trỏ bởi bé trỏ dau. Mỗi nút của danh sách điểm là một bản ghi tất cả 3 trường: ngôi trường HoTen để lưu bọn họ tên sinh viên (là một chuỗi tất cả tối nhiều 30 ký tự), trường Diemlưu điểm của sinh viên với trường Tiep lưu showroom của nút tiếp theo.

Xem thêm: Học Phí Đại Học Công Nghệ Sài Gòn, (Stu) Mới Nhất

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

themDau để thêm một nút vào đầu danh sách.themCuoi nhằm thêm một nút vào thời điểm cuối danh sách.taoDS để tạo ra 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 trong những chuỗi rỗng).hienThiDS để hiển thị list (cách trình diễn như ở ví dụ phía dưới).soSvThiLai để đếm coi trong danh sách có bao nhiêu sinh viên thi lại (điểm ≤ 5).hienThiSvDiemMax nhằm 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 những hàm vừa tạo ở trên.

Nhập chúng ta 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 chúng ta tên sinh viên:Danh sách sv 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 yêu cầu thi lại.Những sinh viên có điểm về tối đa (9 điểm):- Phan Cong Minh (9 diem)- Mai Tien Huan (9 diem) phần đông sinh viên có tên "Huan":- Le Van Huan (1 diem)- Mai Tien Huan (9 diem)Khai báo list (cấu trúc dữ liệu)Khai báo thư viện nên thiết: