Bài tập danh sách liên kết đơn có lời giải

     
Một số vấn đề cơ bạn dạng về “list liên kết đơn”

Tđắm say khảo: http://agreenet.vn/baiviet/laptrinh/c/?eq=Ak7wytsN1FgZurlSBW9Flg==

Để làm cho thân quen với các làm việc cơ phiên bản trên danh sách liên kết, ta triển khai bên trên một list đơn giản và dễ dàng, sẽ là DANH SÁCH SỐ NGUYÊN (từng nút chỉ đựng một trong những nguyên). Chúng ta đang mày mò các phần sau:

Khai báo danh sách (cấu trúc dữ liệu)Cấp vạc cùng giải pchờ vùng lưu giữ một nút ít.Thêm một nút ít vào đầu danh sách.Thêm một nút ít vào cuối danh sách.Duyệt list.Xóa một nút vào list.

Bạn đang xem: Bài tập danh sách liên kết đơn có lời giải

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

Có các phương pháp để khai báo cấu trúc danh sách link đối kháng.

Cách 1. Struct solo 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 trong những struct đơn thuần (chđọng chưa hẳn một kiểu), do thế mọi khi khai báo đổi mới như thế nào kia gồm hình dạng tương quan mang đến cấu trúc Nut thì nên tất cả trường đoản cú khóa struct phía đằng trước (ví dụ: struct Nut *p). Cách này ít khi được thực hiện.

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


typedef struct SoNguyen

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

Với cách knhị báo này, tuy vậy song cùng với việc khai báo kết cấu SoNguyen, ta còn định nghĩa thêm một “kiểu” (type) mới có tên là Nut (chính là hình dáng có kết cấu SoNguyen). Do vậy, trong tương lai mọi khi knhị báo biến đổi làm sao đó có thứ hạng liên quan mang đến cấu trúc SoNguyen thì núm vì chưng khai báo struct SoNguyen *p ta khai báo solo giả: Nut *p. Nghĩa là Nut được sử dụng nhỏng một đẳng cấp, tựa như nhỏng loại int hay float. Một để ý là ngôi trường Tiep chưa thể knhì báo Nut *Tiep vày lúc này C không biết Nut là một trong mẫu mã, do thế bắt buộc knhị 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, hình trạng TroNut là một trong kiểu con trỏ trỏ cho một nút ít trong list. Nghĩa là, cầm vày khai báo Nut *dau, *cuoi, ta knhị báo TroNut dau, cuoi.

Xem thêm: Hướng Dẫn Cách Chỉnh Đồng Hồ Casio Edifice, Cách Chỉnh Đồng Hồ Casio Edifice Nhanh Nhất

Nắm vững vàng bí quyết biểu diễn danh sách liên kếtTa rất có thể trình diễn danh sách liên kết đơn nlỗi sau:

*

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

Các thay đổi khai báo tổng thể, vào công tác bé hay trong tsay đắm số của lịch trình con là đa số biến chuyển 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;). Ở trên đây ta tạm “lơ” qua nội tình bên trong vùng nhớ tĩnh. Các biến chuyển tĩnh khi khai báo thì đã có được cấp phát vùng ghi nhớ.

Vùng ghi nhớ động cất các “trở nên động”. Các dịch chuyển ko mang tên mà lại được quản lý bởi các đổi mới bé trỏ (pointer). Chú ý, biến hóa nhỏ trõ bên trong vùng nhớ tĩnh!

Các “nút” trong danh sách là các “thay đổi động” bên trong HEAPhường., còn phần nhiều con trỏ khai báo vào công tác thiết yếu, ví dụ Nut *dau, *cuoi, *p là đông đảo “vươn lên là tĩnh”.

*

Và cũng nhằm đơn giản, vào trường thích hợp có tương đối nhiều bé trỏ trỏ mang đến những nút, ta hoàn toàn có thể biểu diễn nlỗi 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), con trỏ p trỏ mang lại nút có giá trị 5, và bé trỏ cuoi trỏ mang lại nút ở đầu cuối của danh sách (nút có giá trị là 9). Tuy nhiên, đúng mực rộng sẽ là gắng này:

*
Cấp phân phát vùng lưu giữ cho 1 nút
Ta có thể hình dung Việc “cấp phép vùng ghi nhớ mang đến p” như 2 hình dưới đây. Trước Lúc cấp phát, nhỏ trỏ p không trỏ mang đến nút nào:

*

Sau khi cấp phát, nó trỏ mang lại một nút ít (biến động) sinh hoạt vùng lưu giữ cồn (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 danh sách liên kết đơn (nhưng ta gọi là list điểm) cùng với nút đầu được trỏ vị con trỏ dau. Mỗi nút í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 nhằm lưu lại bọn họ tên sinch viên (là 1 chuỗi bao gồm về tối nhiều 30 ký kết tự), trường Diemlưu thế của sinh viên và trường Tiep lưu giữ tương tác của nút tiếp theo.

Xem thêm: Chương Trình Quay Số Trúng Thưởng, Và Các Hình Thức Tổ Chức

Xây dựng công tác có những hàm sau:

themDau để thêm 1 nút vào đầu list.themCuoi nhằm thêm một nút vào cuối list.taoDS để tạo ds cùng với biết tin được nhập từ bỏ bàn phím (dừng khi nhập bọn họ tên là một trong những chuỗi rỗng).hienThiDS nhằm hiển thị danh sách (phương pháp trình diễn nhỏng nghỉ ngơi ví dụ phía dưới).soSvThiLai nhằm đếm coi trong danh sách tất cả từng nào sinch viên thi lại (điểm ≤ 5).hienThiSvDiemMax để hiển thị (các) sinch viên bao gồm điểm trên cao nhấttimTheoTen để tra cứu tìm cùng hiển thị (các) sinch viên theo thương hiệu.main nhằm thể nghiệm những hàm vừa phát hành sinh hoạt trên.

Nhập chúng ta tên sinch viên: Le Van HuanNhập điểm: 1Nhap ho ten sinch vien: Phan Cong MinhNhập điểm: 9Nhap ho ten sinc vien: Tran Thi LanhNhập điểm: 4Nhap ho ten sinch 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 sinc viên phải thi lại.Những sinh viên bao gồm điểm tối đa (9 điểm):- Phan Cong Minch (9 diem)- Mai Tien Huan (9 diem) Những sinch viên mang tên "Huan":- Le Van Huan (1 diem)- Mai Tien Huan (9 diem)Khai báo list (kết cấu dữ liệu)Khai báo tlỗi viện bắt buộc thiết:


Chuyên mục: Công nghệ