Với yêu cầu nhập số N từ bàn phím chính là số lượng phần tử trong danh sách liên kết đơn. Để thực hiện được công việc nhập này bạn đọc hay đảm bảo rằng đã hiểu được các cách thêm phần tử vào đầu danh sách là hàm void ChenDau() và thêm phần tử vào cuối danh sách là hàm void ChenCuoi().
1.Nhập N phần tử vào danh sách liên kết đơn
Hàm void Nhap(LIST &ds, int n) dưới đây nhận LIST &ds làm danh sách cần được nhập phần từ và int n là số lượng phần tử cần thêm vào danh sách. Hàm này có chức năng tạo ra một Node p mới và nhận giá trị int x đưa vào Node p sau đó truyền vào hàm ChenDau() để thực hiện chèn vào đầu danh sách:
void Nhap(LIST &ds, int n){
//duyet N lan
for(int i = 0; i < n; i++){
//nhap du lieu la so nguyen int x
int x;
printf("Nhap vao so x: ");
scanf("%d",&x);
//tao node p
NODE *p = new NODE;
//dua du lieu vua nhap vao node p
p = TaoNode(x);
//dua node p vao ham chen dau
ChenDau(ds,p);
}
}
Chú ý:
- Các hàm TaoNode(), ChenDau() đã được nêu ra ở những bài trước vì thế nếu quên, bạn đọc vui lòng xem lại.
- Ví dụ trên thực hiện cho danh sách liên kết đơn lưu trữ dữ liệu kiểu số nguyên nên ta sử dụng int x, tùy vào trường hợp khác nhau mà ta sẽ sử dụng kiểu dữu liệu khác nhau như float, char….hay kiểu dữ liệu struct SinhVien mà ta tự định nghĩa!
Tương tự như chèn vào đầu danh sách, ta cũng có thể áp dụng hàm trên cho chèn cuối vào danh sách bằng cách thay đổi hàm:
ChenDau(ds,p);
Bằng hàm:
ChenCuoi(ds,p);
Chi tiết hàm nhập vào phần tử vào cuối danh sách liên kết đơn:
void Nhap(LIST &ds, int n){
//duyet N lan
for(int i = 0; i < n; i++){
//nhap du lieu la so nguyen int x
int x;
printf("Nhap vao so x: ");
scanf("%d",&x);
//tao node p
NODE *p = new NODE;
//dua du lieu vua nhap vao node p
p = TaoNode(x);
//dua node p vao ham chen cuoi
ChenCuoi(ds,p);
}
}
2.Xuất dữ liệu từ các node có trong danh sách liên kết đơn
Hàm void Xuat(LIST ds) dưới đây nhận LIST ds làm danh sách cần được duyệt qua tất cả phần tử. Hàm này có chức năng duyệt từ phần tử đầu tiên (ds.pHead) đến phần tử cuối cùng (ds.pTail) trong danh sách liên kết đơn. Có 2 cách để duyệt tất các các node trong danh sách liên kết đơn:
Cách 1: Duyệt bằng vòng lặp for
void Xuat(LIST ds){
//khoi tao mot node
NODE *p = new NODE;
//duyet tu dau danh sach den cuoi danh sach voi dieu kien p!=NULL
for(p = ds.pHead; p!= NULL; p=p->next){
//hien thi du lieu cua tung node
printf("%d\n",p->data);
}
}
Cách 2: Duyệt bằng vòng lặp while
void Xuat(LIST ds){
//tao node p
NODE *p;
p = ds.pHead;
//trong khi node p chua bang NULL (p chua la phan tu cuoi)
while (p!=NULL){
//hien thi du lieu
printf("%d\n",p->data);
//chuyen sang node tiep theo
p=p->next;
}
}
Chú ý:
- Ở trong vòng lặp for, tôi sử dụng p!= NULL nghĩa là điều kiện duyệt các phần tử chưa chạm đến phần NULL của danh sách (phần null là địa chỉ cuối của danh sách)
- p->data chính là việc lấy dữ liệu mà ta đã nhập vào các node có trong danh sách
3.Chương trình nhập xuất trong danh sách liên kết đơn hoàn chỉnh
#include <stdio.h>
#include <stdlib.h>
struct Node
{
//khai bao thanh phan du lieu co kieu int
int data;
//khai bao con tro next co kieu Node
Node *next;
};
typedef struct Node NODE;
struct list{
//thanh phan dau danh sach
NODE *pHead;
//thanh phan cuoi danh sach
NODE *pTail;
};
typedef struct list LIST;
void KhoiTao(LIST &ds){
//dat dia chi dau danh sach bang NULL
ds.pHead = NULL;
//dat dia chi cuoi danh sach bang NULL
ds.pTail = NULL;
}
int KiemTraRong(LIST ds){
//neu phan tu dau danh sach NULL
if (ds.pHead == NULL){
//tra ve 1 la co NULL
return 1;
}
//truong hop nguoc lai tra ve khong null
return 0;
}
NODE* TaoNode(int x) {
//tao mot node p moi
NODE *p;
p = new NODE;
//neu p==NULL thi khong du bo nho
if (p==NULL) {
printf ("KHONG DU BO NHO");
return NULL;
}
//gan thanh phan data = x
p->data=x;
//gan con tro next = NULL
p->next=NULL;
//tra ve node p da tao
return p;
}
void ChenDau(LIST &ds, NODE *p) {
//neu phan tu dau rong thi danh sach rong
if (ds.pHead==NULL){
//chen dau va cuoi deu bang node p
ds.pHead = p;
ds.pTail = p;
}
//nguoc lai danh sach khong rong
else {
//gan con tro next cua node p bang phan tu dang la dau tien cua danh sach
p->next = ds.pHead;
//gan pHead bang node p
ds.pHead = p;
}
}
void ChenCuoi (LIST &ds, NODE *p){
//neu phan tu dau rong thi danh sach rong
if (ds.pHead==NULL) {
//chen dau va cuoi deu bang node p
ds.pHead=p;
ds.pTail=p;
}
//nguoc lai danh sach khong rong
else {
//gan con tro cua phan tu cuoi trong danh sach bang node p
ds.pTail->next=p;
//gan pTail bang node p
ds.pTail=p;
}
}
void Nhap(LIST &ds, int n){
//duyet N lan
for(int i = 0; i < n; i++){
//nhap du lieu la so nguyen int x
int x;
printf("Nhap vao so x: ");
scanf("%d",&x);
//tao node p
NODE *p = new NODE;
//dua du lieu vua nhap vao node p
p = TaoNode(x);
//dua node p vao ham chen cuoi
ChenCuoi(ds,p);
}
}
void Xuat(LIST ds){
//khoi tao mot node
NODE *p = new NODE;
//duyet tu dau danh sach den cuoi danh sach voi dieu kien p!=NULL
for(p = ds.pHead; p!= NULL; p=p->next){
//hien thi du lieu cua tung node
printf("%d\n",p->data);
}
}
int main(){
//khai bao mot danh sach
LIST ds;
//nhap so luong N tu ban phim
int n;
printf("Nhap N: ");
scanf("%d",&n);
//khoi tao danh sach
KhoiTao(ds);
//goi ham nhap va truyen danh sach va so luong N vao
Nhap(ds,n);
//goi ham xuat du lieu
printf("\nDU LIEU TRONG DANH SACH LIEN KET DON\n");
Xuat(ds);
}
| Nhap N: 5
Nhap vao so x: 11 Nhap vao so x: 22 Nhap vao so x: 33 Nhap vao so x: 44 Nhap vao so x: 55 DU LIEU TRONG DANH SACH LIEN KET DON 11 22 33 44 55 |
Ở chương trình trên, trong hàm void Nhap(LIST &ds, int n) tôi sử dụng nhập node vào danh sách liên kết đơn theo cách chèn cuối vì vậy tôi gọi hàm void ChenCuoi(ds,p) và nhận được kết quả khi xuất dữ liệu ra màn hình theo thứ tự là: 11 22 33 44 55
Nếu tôi sử dụng hàm void ChenDau(ds,p) thay thế thì kết quả nhận được khi xuất dữ liệu ra màn hình sẽ theo thứ tự là: 55 44 33 22 11
