Trong lập C/C++, danh sách liên kết đơn (singly linked list) có chức năng tương tự như mảng (array) nhưng có cấu trúc dữ liệu đệ quy. Một danh sách liên kết sẽ bao gồm các node, mỗi node gồm 2 thành phần là dữ liệu (data) và con trỏ (next) để trỏ tới node tiếp theo nhằm tạo mối liên kết. Nếu số liên kết của mỗi su_label type=”success”]node[/su_label] là một thì danh sách trên được gọi là danh dách liên kết đơn.
Bài viết này chia sẻ một chương trình C có chức năng tạo và in danh sách liên kết đơn do người dùng nhập vào, đặc biệt dữ liệu được lưu trong file txt nên có thể tái sử dụng cho lần chạy chương trình tiếp theo.
Khai báo thư viện, biến và hàm cơ bản
Các bước đầu tiên trong việc thiết lập liên kết đơn gần như tương tự nhau, chủ yếu là thay đổi kiểu dữ cho data của node mà thôi.
#include <stdio.h>
#include <stdlib.h>
typedef struct { //Khai bao kieu du lieu NHAN VIEN
char maNV[5]; //Ma so nhan vien
char tenNV[30]; //Ten nhan vien
int tuoiNV; //Tuoi nhan vien
} DataType; //Dat ten kieu du lieu nay la DataType
typedef struct Node* NodeType; //Khai bao kieu con tro
typedef NodeType Position;
typedef Position List;
struct Node { //Moi node gom 2 thanh phan
DataType data; //Du lieu cua node
NodeType next; //Dia chi cua node tiep theo
};
void MakeNullList(List *Header){ //Khoi tao danh sach rong~
(*Header) = (NodeType)malloc(sizeof(struct Node));
(*Header)->next = NULL;
}
Position EndList(List L){ //Tra ve vi tri cuoi trong danh sach
Position P;
P = L; //Vi tri mac dinh la vi tri dau
while (P->next != NULL){ //Neu vi tri tiep theo ton tai
P = P->next; //thi duyet qua vi tri tiep theo
}
return P; //Ket luan vi tri P
}
void InsertList(DataType X, Position P, List *L){ //Chen phan tu X vao vi tri P
Position T; //Tao node moi
T = (NodeType)malloc(sizeof(struct Node)); //Cap phat bo nho va gan dia chi cho bien T
T->data = X; //Data cua T la Data cua X
T->next = P->next; //T nhan dia chi cua node ke tiep
P->next = T; //P nhan dia chi cua node T
}
//Ham khoi tao va nhap lieu cho danh sach o day
//Ham in danh sach o day
void main(){
List L;
DataType X;
Position P;
ReadList(&L); //Nhap vao danh sach moi/Doc danh sach tu file NV.txt
PrintList(L); //In toan bo danh sach
}Khởi tạo và nhập liệu cho danh sách
Mục tiêu hướng tới của bài viết này là phải lưu được dữ liệu mà người dùng đã nhập vào, để tái sử dụng cho lần chạy chương trình tiếp theo. Nếu không thể dùng MySQL thì ta dùng tạm file text vậy.
void ReadList(List *L){ //Nhap phan tu vao cuoi danh sach
int i, n;
DataType X;
MakeNullList(L); //Tao danh sach rong~
printf("Nhap so phan tu cua danh sach: ");
scanf("%d", &n);
FILE* fOut = fopen("NV.txt", "a"); //Mo file NV.txt
for(i=1; i<=n; i++){
printf("Nhap thong tin nhan vien thu %d:\n", i);
getchar();
printf("Ma so nhan vien: ");
gets(X.maNV);
printf("Ten nhan vien: ");
gets(X.tenNV);
printf("Tuoi nhan vien: ");
scanf("%d", &X.tuoiNV);
InsertList(X, EndList(*L), L); //Chen X vao cuoi danh sach
fprintf(fOut, "%-8s %-20s %-5d\n", X.maNV, X.tenNV, X.tuoiNV);
}
fclose(fOut);
}Mình đã comment cho mấy dòng lệnh trong này, nên cũng lười giải thích thêm về cách thức vận hành. Tuy nhiên, nếu bạn đọc cảm thấy chưa rõ chỗ nào thì vui lòng comment bên dưới, để mình trao đổi thêm.
Xuất thành quả
Bình thường, ta hay dùng vòng lặp while để in ra dữ liệu của danh sách, kiểu như:
while (P->next != NULL){ //Khi node ke tiep ton tai
X = P->next->data; //Lay data cua node ke tiep
printf("%-8s %-20s %-5d\n", X.maNV, X.tenNV, X.tuoiNV);
P = P->next; //Nhay qua node ke tiep
}
Vì đã có dữ liệu lưu trong file text, kể cả dữ liệu vừa được người dùng nhập vào, nên ta sẽ trực tiếp in danh sách từ trong file text ra màn hình, cách làm như sau:
void PrintList(List L){ //In toan bo danh sach ra man hinh
Position P;
P = L;
DataType X;
printf("--------------------------------------------\n");
printf("%-8s %-20s %-5s\n", "Na NV", "Ten NV", "Tuoi NV");
printf("--------------------------------------------\n");
FILE* fOut = fopen("NV.txt", "r"); //Doc du lieu tu file text
if(fOut){
for(;;){ //In danh sach co san trong file NV.txt
DataType X;
fscanf(fOut, "%8s %20[^\n] %5d\n", &X.maNV, &X.tenNV, &X.tuoiNV);
printf("%-8s %-20s %-5d\n", X.maNV, X.tenNV, X.tuoiNV);
if(feof(fOut)){
break;
}
}
}
fclose(fOut);
printf("--------------------------------------------\n");
}Ok rồi đó, quý bạn đọc thử ráp các lệnh vào trong một chương trình hoàn chỉnh và chạy thử xem sao nhe. Nếu kết quả in ra màn hình được tương tự như dưới đây là xem như thành công!
