Bài giảng Ngôn ngữ lập trình C - Chương VIII: Danh sách móc nối
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;
while (Last->Next!= (POINT*) NULL)
Last=Last->Next;
Last->Next=p;
Last=p;
}
printf(“\nInput information for Node”);
scanf(“%d”, p->.info);
Last->Next=(POINT *) NULL;
return;
}
b. Xoá một con trỏ:
Cú pháp:
free(Point_Variable)
Giải phóng vùng nhớ được trỏ bởi Point_Variable
c. Các phép toán thương dùng trong danh sách liên
kết
Tạo một phần tư của danh sách
Điều phải làm là cấp pháp bộ nhớ cho cấu trúc và
trả về con trỏ trỏ đến vùng nhớ này.
Ví dụ:
POINT *CreatNode()
{
POINT *p;
p = (POINT *) malloc (sizeof(POINT));
if (p==NULL)
{
printf(“Malloc falled.\n”);
exit(1);
}
printf(“Input data for Node info = ”);
scanf(“%d”, p->info);
p->Next = NULL
return p;
}
Bổ sung phần tư vào danh sách
Hàm CreatNode() chỉ cấp phát bộ nhớ nhưng nó
không nối phần tử này vào danh sách. Để làm điều này,
ta cần thêm một hàm nữa, gọi là hàm AddNode(). Được
định nghĩa như sau:
static POINT *Head;
void AddNode(POINT *e)
{
POINT *p;
if (Head ==NULL)
{
Head = e;
return;
}
for (p=Head; p->Next!=NULL; p=p->Next);
p->Next=e;
}
Chú ý:
Biến Head là con trỏ trỏ đến đầu danh sách, nên cần
được khai báo đầu chương trình.(Sau phần khai định
nghĩa kiểu con trỏ).
Chèn phần tư vào danh sách
Để chèn phần tử vào danh sách liên kết, ta phải
chỉ rỏ phần tử mới sẽ được chèn vào vị trí nào.Sau
đây là hàm sẽ thực hiện công việc trên.
void InsertNode(POINT *p, POINT *q)
{
if (p=NULL || q=NULL || p==q || q->Next ==p)
{ printf (“Cannot Insert \n”);
return;
}
p->Next =q->Next;
q->Next=p;
};
Xoá phần tư vào danh sách
Xoá một phần tử khỏi danh sách liên kết đơn, ta
cần phải tìm phần tử trước phần tử cần xoá để nhằm
mục đích nối lại với phần tử sau phần tử cần xoá. Ta
dùng hàm free() để giải phống bộ nhớ chiếm bởi
phần tử bị xoá.
Có thể xây dưng là:
void DeleteNode(POINT *goner)
{
POINT *p;
p=Head;
if (goner ==Head)
Head = goner->Next;
else
{ while (p!=NULL && p->Next!=goner)
p=p->Next;
if (p=NULL)
{
printf(“Cannot find Node \n”);
return;
}
p->Next=p->Next->Next;
};
free(goner)
};
Tìm phần tư vào danh sách
Thật khó tạo một hàm FindNode() tổng quát,
bởi vì khi tìm kiếm thì ta phải dựa vào một trong
những trường dữ liệu của cấu trúc, điều này phụ
thuộc vào cấu trúc dang sử dụng. Để viết hàm
FindNode() tổng quát ta phảisử dụng con trỏ trỏ
đến hàm.
Với cấu trúc trên ta xây dựng hàm FindNode()
như sau:
POINT *FindNode(int *n)
{
POINT *p;
for (p=Head; p!=NULL; p=p->Next)
if (p->Info=n)
return p;
return NULL;
};
II. Danh sách đa liên kết
Đị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>,<Tên pointer trỏ đến phần tử cấu trúc trước
đó 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,*Previous;
};
III. STACK và QUEUE
1. STACK
Là danh sách có móc nối đặc biệt. Mặc dầu ta có
thể thực hiệm nhiều phép toán trên danh sách
tổng quát, Stack vẫn có những tính chất riêng
biệt: chỉ cho phép thêm và xoá bỏ các phần tử ở
một vị trí duy nhất, tại đỉnh của Stack.
Với đặc trưng như vậy thì Stack có kiểu cấu trúc
dữ liệu là LIFO (Last In First Out)
a. Khởi tạo Stack
Sử dụng mảng:
int stack[100], p;
Stackinit()
{
p=0;
}
Sử dụng danh sách liên kết
struct Node {
int info;
struct Node *Next;
};
typedef struct Node NODE;
NODE *Head, *p, *q;
StackInit()
{
Head = (NODE *) malloc (sizeof *Head);
p=(NODE *) malloc (sizeof *p);
Head->Next=p;
Head->info=0;
p->Next=NULL;
return 0;
}
Tải về để xem bản đầy đủ
31 trang
13/04/2022
3880
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Ngôn ngữ lập trình C - Chương VIII: Danh sách móc nối", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_ngon_ngu_lap_trinh_c_chuong_viii_danh_sach_moc_noi.ppt
