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

Một số vấn đề cơ phiên bản về “danh sách link đơn”

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

Để làm cho quen cùng với các làm việc cơ phiên bản trên list liên kết, ta thực hiện trên một list đơn giản, sẽ là DANH SÁCH SỐ NGUYÊN (mỗi nút chỉ chứa một số nguyên). Bọn họ 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ới giải phóng vùng ghi 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: Bài tập danh sách liên kết đơn

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

Có nhiều cách để khai báo cấu tạo danh sách links đơn.

Cách 1. Struct đối chọi 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 struct 1-1 thuần (chứ chưa hẳn một kiểu), vị vậy mỗi khi khai báo thay đổi nào đó tất cả kiểu tương quan đến cấu trúc Nut thì phải tất cả từ khóa struct vùng phía đằng trước (ví dụ: struct Nut *p). Bí quyết 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 biện pháp khai báo này, tuy nhiên song với câu hỏi khai báo cấu trúc SoNguyen, ta còn định nghĩa thêm một “kiểu” (type) mới mang tên là Nut (chính là giao diện có kết cấu SoNguyen). Vị vậy, sau này mỗi một khi khai báo đổi mới nào đó có kiểu tương quan đến cấu tạo SoNguyen thì thay vì chưng khai báo struct SoNguyen *p ta khai báo đối kháng giả: Nut *p. Tức thị Nut được thực hiện như một kiểu, giống như như loại int tốt float. Một để ý là ngôi trường Tiep không thể khai báo Nut *Tiep vì lúc này C không biết Nut là 1 trong những kiểu, do thế 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 phương pháp khai báo này, mẫu mã TroNut là một trong những kiểu con trỏ trỏ mang lại 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: Mê Cung Tập 30: Fedora Thụ Án Tử, Khánh "Run Người" Khi Biết Mẹ Là Nạn Nhân Cuối?

Nắm vững biện pháp biểu diễn danh sách 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à trình diễn “ngắn gọn”. Để cầm rõ, ta đề xuất phân biệt nhì vùng nhớ: vùng nhớ TĨNH (kích thước nhỏ) và vùng lưu giữ ĐỘNG (thường điện thoại tư vấn là “heap”, kích cỡ lớn).

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

Vùng nhớ cồn chứa những “biến động”. Những biến hễ không có tên mà được cai quản bởi các biến nhỏ trỏ (pointer). Chú ý, biến bé trõ phía bên trong vùng lưu giữ tĩnh!

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

*

Và cũng để đối chọi giản, vào trường hợp có không ít con trỏ trỏ đến những nút, ta rất có thể biểu diễn như sau:

*

Nghĩa là bé trỏ dau trỏ đến nút thứ nhất của danh sách (nút có mức giá trị là 1), nhỏ trỏ phường trỏ đến nút có giá trị 5, và nhỏ trỏ cuoi trỏ mang lại nút sau cuối của danh sách (nút có giá trị là 9). Mặc dù nhiên, chính xác hơn đã là nạm này:

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

*

Sau khi cấp phát, nó trỏ mang lại một nút (biến động) sinh sống vùng nhớ cồn (heap):

*
Bài 1. Danh sách ĐIỂM SINH VIÊNNgười ta cai quản điểm của các sinh viên vào lớp bằng cách sử dụng một danh sách liên kết đơn (mà ta hotline là danh sách điểm) cùng với nút đầu được trỏ bởi con trỏ dau. Từng nút của danh sách điểm là một phiên bản ghi gồm 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à trường Tiep lưu add của nút tiếp theo.

Xây dựng công tác gồm những 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 ra ds với tin tức được nhập từ keyboard (dừng khi nhập chúng ta tên là 1 trong chuỗi rỗng).hienThiDS nhằm hiển thị list (cách trình bày như sinh sống ví dụ phía dưới).soSvThiLai để đếm xem trong list 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 nhằm tìm kiếm cùng hiển thị (các) sv theo tên.main nhằm thử nghiệm các hàm vừa xây đắp ở 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 chúng ta 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) bao gồm 2 sinh viên cần thi lại.Những sinh viên tất cả điểm tối đa (9 điểm):- Phan Cong Minh (9 diem)- Mai Tien Huan (9 diem) rất nhiều 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: