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

     
Một số vụ việc cơ phiên bản về “list links đơn”

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

Để làm cho quen thuộc với các thao tác cơ phiên bản bên trên list link, ta thực hiện bên trên một list đơn giản dễ dàng, chính là DANH SÁCH SỐ NGUYÊN (mỗi nút ít chỉ chứa một số trong những nguyên). Chúng ta đang mày mò các phần sau:

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

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

Knhì báo danh sách (kết cấu dữ liệu)Đầu tiên là knhì báo các tlỗi viện đề xuất thiết:
#include //để sử dụng hàm: printf, scanf
#include //nhằm thực hiện hàm: getch
#include //nhằm thực hiện hàm: malloc (cấp phép vùng ghi nhớ cho 1 nút)

Có những cách để khai báo cấu tạo danh sách link 1-1.

Cách 1. Struct đối kháng thuần


struct Nut

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

Với phương pháp knhì báo bên trên, Nut chỉ là một trong những struct đối kháng thuần (chđọng không hẳn một kiểu), do vậy mọi khi khai báo thay đổi nào kia có vẻ bên ngoài liên quan cho kết cấu Nut thì nên có từ khóa struct phía trước (ví dụ: struct Nut *p). Cách này hiếm khi được thực hiện.

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 phương pháp knhì báo này, song tuy vậy với Việc khai báo kết cấu SoNguyen, ta còn tư tưởng thêm 1 “kiểu” (type) bắt đầu có tên là Nut (đó là hình dạng bao gồm cấu trúc SoNguyen). Do vậy, sau này mọi khi knhị báo đổi thay nào kia gồm hình dạng liên quan cho cấu trúc SoNguyen thì rứa bởi vì knhì báo struct SoNguyen *p ta knhị báo đơn giả: Nut *p. Nghĩa là Nut được áp dụng nhỏng một hình dạng, giống như nhỏng vẻ bên ngoài int hay float. Một để ý là trường Tiep không thể knhì báo Nut *Tiep vày từ bây giờ C chưa biết Nut là một trong những hình trạng, do vậy nên 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 bí quyết khai báo này, giao diện TroNut là 1 trong hình dáng con trỏ trỏ cho một nút vào danh sách. Nghĩa là, thế vày khai báo Nut *dau, *cuoi, ta knhì 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 vàng cách trình diễn list liên kếtTa có thể màn biểu diễn danh sách link đối chọi nhỏng sau:

*

Tuy nhiên, hình hình họa trên chỉ cần trình diễn “nđính thêm gọn”. Để nắm vững, ta bắt buộc biệt lập nhì vùng nhớ: vùng nhớ TĨNH (form size nhỏ) và vùng nhớ ĐỘNG (thường gọi là “heap”, form size lớn).

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

Vùng nhớ động chứa các “đổi mới động”. Các biến động không mang tên mà được thống trị bởi các thay đổi nhỏ trỏ (pointer). Chụ ý, phát triển thành nhỏ trõ bên trong vùng nhớ tĩnh!

Các “nút” vào danh sách là các “biến chuyển động” nằm trong HEAP, còn những con trỏ knhị báo trong chương trình chủ yếu, ví dụ Nut *dau, *cuoi, *p là gần như “phát triển thành tĩnh”.

*

Và cũng để dễ dàng, trong trường phù hợp có khá nhiều con trỏ trỏ cho các nút ít, ta hoàn toàn có thể màn biểu diễn nlỗi sau:

*

Nghĩa là bé trỏ dau trỏ mang đến nút ít trước tiên của danh sách (nút ít có giá trị là 1), bé trỏ p trỏ cho nút có giá trị 5, cùng con trỏ cuoi trỏ mang đến nút ít ở đầu cuối của list (nút có giá trị là 9). Tuy nhiên, chính xác rộng đã là ráng này:

*
Cấp phát vùng lưu giữ cho 1 nút
Ta hoàn toàn có thể hình dung Việc “cấp phép vùng lưu giữ đến p” nlỗi 2 hình sau đây. Trước lúc cấp phát, con trỏ p ko trỏ cho nút ít nào:

*

Sau Lúc cấp phát, nó trỏ mang đến một nút ít (phát triển thành động) ngơi nghỉ vùng ghi nhớ hễ (heap):

*
Bài 1. Danh sách ĐIỂM SINH VIÊNNgười ta cai quản điểm của những sinch viên vào lớp bằng phương pháp sử dụng một list links đối kháng (cơ mà ta điện thoại tư vấn là danh sách điểm) với nút đầu được trỏ vì chưng nhỏ trỏ dau. Mỗi nút của danh sách điểm là một trong những bạn dạng ghi có 3 trường: trường HoTen nhằm lưu bọn họ thương hiệu sinch viên (là một trong chuỗi tất cả về tối đa 30 cam kết tự), ngôi trường Diemlđiểm mạnh của sinh viên với trường Tiep lưu shop của nút tiếp sau.

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 những hàm sau:

themDau nhằm thêm một nút vào đầu danh sách.themCuoi để thêm 1 nút ít vào thời điểm cuối danh sách.taoDS nhằm tạo nên ds cùng với thông báo được nhập trường đoản cú keyboard (giới hạn lúc nhập bọn họ thương hiệu là một trong những chuỗi rỗng).hienThiDS để hiển thị danh sách (phương pháp trình bày như làm việc ví dụ phía dưới).soSvThiLai nhằm đếm coi vào danh sách có từng nào sinh viên thi lại (điểm ≤ 5).hienThiSvDiemMax nhằm hiển thị (các) sinch viên có điểm cao nhấttimTheoTen để tìm kiếm tìm với hiển thị (các) sinc viên theo thương hiệu.main nhằm thử nghiệm các hàm vừa kiến tạo làm việc trên.

Nhập bọn họ tên sinch viên: Le Van HuanNhập điểm: 1Nhap ho ten sinc vien: Phan Cong MinhNhập điểm: 9Nhap ho ten sinch vien: Tran Thi LanhNhập điểm: 4Nhap ho ten sinh vien: Mai Tien HuanNhập điểm: 9Nhập bọn họ thương hiệu sinh viên:Danh sách sinc viên vừa nhập:- Le Van Huan (1 diem)- Phan Cong Minch (9 diem)- Tran Thi Lanh (4 diem)- Mai Tien Huan (9 diem) Có 2 sinh viên đề nghị thi lại.Những sinh viên tất cả điểm buổi tối đa (9 điểm):- Phan Cong Minh (9 diem)- Mai Tien Huan (9 diem) Những sinh viên mang tên "Huan":- Le Van Huan (1 diem)- Mai Tien Huan (9 diem)Knhị báo danh sách (cấu tạo dữ liệu)Knhì báo tlỗi viện cần thiết:


Chuyên mục: Tổng hợp