dungnvhàm xem danh sách liên kết đơn.
Wednesday, January 21, 2015
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ỏ f
chứ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 while
vớ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 struct
node
{
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 struct
node
{
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
{
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;
}
}
//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;
}
return
f;
}
int main()
{
node *f=NULL;
int
n;
printf("\nNhap so phan tu cua dslk : ");
scanf("%d",&n);
f=nhaplifo(f,n);
printf("\nDanh sach vua nhap : ");
xem(f);
getch();
}
All comments [ 0 ]
Your comments