CHƯƠNG VIII
DANH SÁCH MÓC N IỐ
Ta thương s d ng m ng c u trúc ử ụ ả ấ đ x lý ể ử
v i nhóm d li u. Đây là m t cách ti p c n ớ ữ ệ ộ ế ậ đúng
khi ta bi t trế ư c chính xác s các c u trúc c n có. ớ ố ấ ầ
Tuy nhiên, khi con s này không rõ ràng, mãng s ố ẽ
tr nên khá t n kém vì chúng ph i ở ố ả đưc c p phát ợ ấ
đ b nh ủ ộ ớ đ ho t ể ạ đng. B nh này ộ ố ớ đưc ợđăng ký
và s không dành cho nh ng tác v khác ngay c ẽ ứ ụ ả
khi ta ch dùng m t sô nh các ph n t m ng. ỉ ộ ỏ ầ ử ả
Phương hưng gi i quy t cho v n ớ ả ế ấ đ này là ề
cho phép c p phát b nh cho m t c u trúc m i khi ấ ộ ớ ộ ấ ớ
c n thi t.ầ ế
C cho phép ta th c hi n ự ệ đi u này thông qua cáhc ề
c p phát b nh ấ ộ ớ đng b ng:ộ ằ
malloc() và calloc()
Nhưng các c u trúc n u ấ ế đưc c p pháp xong s ợ ấ ẽ
không có đm báo nào r ng các c u trúc s ả ằ ấ ẽ đưc ợ
đt liên ti p nhau trong b nh . Do ặ ế ộ ớ đó đi u c n ề ầ
thi t là k thu t ế ỹ ậ đ n i k t t t c các c u trúc l i ể ố ế ấ ả ấ ạ
v i nhau.ớ
Phương cách thông d ng ụđ k t n i các ph n t ể ế ố ầ ử
đó l i là dùng danh sách liên k t (Linked list)ạ ế
I. Danh sách liên k t ếđơn:
1. Đnh nghĩaị
Cú pháp:
struct <Tên_ki u_c u_trúc> ể ấ
{
<Ki u c a ph n t > <Ph n t >;ể ủ ầ ử ầ ử
struct <Tên_ki u_c u_trúc> *<Tên ể ấ
pointer tr ỏđn ph n c u trúc ti p theo trong ế ầ ấ ế
Danh sách>
}
Ví d : Đnh nghĩa m t danh sách liên k t ụ ị ộ ế đ ể
ch a các s nguyên.ứ ố
struct Point
{
int info;
struct Point *Next;
};
2. Các phép toán trên danh sách liên k tế
a. C p phát bô nh cho bi n con tr m iấ ớ ế ỏ ớ
Cú pháp:
Point_New = (struct Point_Name *) malloc
(sizeof(struct Point_Name)
Ví d :ụ
typedef struct Point POINT;
POINT Head, Last, p;
CreatNode()
{
p=(POINT *) malloc (POINT)
if (Head==(POINT* ) NULL)
Head=Last=p;
else
{
Last=Head;