Xem danh sách liên kết đơn.
Danhsách liên kết đơn được tạo bởi các ô nhớ chứa dữ liệu cần lưu trữ và được liên kết với nhau thành một danh sách. Mỗi phần tử của danh sách liên kết được chia làm 2 phần. Là phần dữ liệu lưu trữ (data) và phần liên kết(link).
Ø phần dữ liệu lưu trữ (data).
Phần này có thể chứa các số nguyên, số thực, hoặc tập hợp các số nguyên số thực và các xâu. Tùy thuộc vào mục đích sử dụng.
Ø phần liên kết(link).
Phần này chứa biến con trỏ. Để lưu trữ vị trí ô nhớ của phần tử tiếp theo cần tham chiếu.
Nhìn sơ qua hình trên ta thấy. Muốn xem danh sách liên kết đơn thì ta phải biết được địa chỉ của phần tử đầu tiên(ta thường hay dùng con trỏ f để lưu) . Sau đó lần theo phần link để đọc các phần tử tiếp theo cho đến khi gặp NULL (dấu hiệu kết thúc danh sách liên kết) thì kết thúc việc xem dslk đơn.
Vậy hàm xem chỉ thực hiện công việc xem đơn thuần nên ta sử dụng hàm kiểu void. Truyền vào hàm con trỏ fchứa địa chỉ ô nhớ phần tử đầu tiên của danh sách liên kết.
· void xem(node *f)
và việc xem danh sách liên kết đơn ta phải sử dụng một biến con trỏ trung gian để duyệt từ đầu đến cuối danh sách. ở đây chúng ta sử dụng con trỏ p. Sở dĩ phải dùng biến trung gian bở vì nếu sử dụng con trỏ f thì sẽ làm mất địa chỉ ô nhớ đầu tiên. Dẫn đến không thể dựa vào điểm nào để lần ra danh sách đồng nghĩa với việc mất danh sach liên kết.
· node *p=f;
Để duyệt từ vị trí đầu tiên đến (vị trí con trỏ f) vị trí cuối cùng ( phần tử có phần link bằng NULL)của danh sách liên kết ta sử dụng vòng lặp whilevới điều kiện dừng là (p!=NULL) và mỗi lần lặp thì con trỏ p trỏ lên 1 vùng nhớ của phần tử tiếp theo. (p=p->link;)
Sơ qua thì hàm xem chúng ta xây dựng như sau,
void xem(node *f)
{
node *p=f;
while(p!=NULL)
{
/*
phần đọc dữ liệu phần data.
*/
p=p->link;
}
}
Từ yêu cầu bài toán mà ta thay đổi phần đọc dữ liệu data sao cho phù hợp.
Ví dụ như phần data chưa mỗi biến info kiểu int.
typedef structnode
{
int info;
node *link;
};
// ham xem danh sach lien ket
void xem(node *f)
{
node *p=f;
while(p!=NULL)
{
printf("%5d",p->info);
p=p->link;
}
}
Ví dụ như phần data chưa mỗi biến info kiểu float.
typedef structnode
{
float info;
node *link;
};
// ham xem danh sach lien ket
void xem(node *f)
{
node *p=f;
while(p!=NULL)
{
printf("%5.2f",p->info);
p=p->link;
}
}
Các cách đọc dữ liệu cần linh hoạt. phù hợp với yêu cầu bài toán.
Gọi hàm chỉ làm thủ tục đơn giản là xem(f);
Code test thử hàm. c/c++
#include <stdio.h>
#include <conio.h>
typedef struct node
{
intinfo;
node *link;
};
// ham xem danh sach lien ket.
void xem(node *f)
{
node *p=f;
while(p!=NULL)
{
printf("%5d",p->info);
p=p->link;
}
}
//Nhap danh sach lien ket don LIFO.
node *nhaplifo(node *f,int n)
{
node *p;
for(int i=0;i<n;i++)
{
p=new(node);
printf("\nNhap phan tu: ");
scanf("%d",&p->info);
p->link=f;
f=p;
}
returnf;
}
int main()
{
node *f=NULL;
intn;
printf("\nNhap so phan tu cua dslk : ");
scanf("%d",&n);
f=nhaplifo(f,n);
printf("\nDanh sach vua nhap : ");
xem(f);
getch();
}
