Thứ Tư, 28 Tháng Chín 2022
Trang chủLập trìnhCTDL & Thuật toánBài toán Quản lý sinh viên sử dụng cấu trúc dữ liệu...

Bài toán Quản lý sinh viên sử dụng cấu trúc dữ liệu Danh sách liên kết đơn

Trong bài viết hôm nay chúng ta sẽ xây dựng chương trình Quản lý sinh viên trên C/C++ sử dụng sanh sách liên kết đơn(Linked List).

Quản lý sinh viên sử dụng cấu trúc dữ liệu Linked List

Cụ thể trong bài này mình sẽ thực hiện viết chương trình quản lý sinh viên, mỗi sinh viên sẽ bao gồm các thông tin là mã sinh viên, họ tên, điểm trung bình. Và yêu cầu bài toán là cài đặt sử dụng danh sách liên kết đơn và chương trình sẽ có các chức năng là Nhập vào danh sinh viên, Hiển thị danh sách, xóa 1 sinh viên tại vị trí k nhập từ bàn phím.

Đầu tiên ta định nghĩa kiểu dữ liệu sinh viên gồm các trường là tên, mã sinh viên và điểm trung bình.

//Định nghĩa struc sinh vien
typedef struct SinhVien{
	char msv[100]; //Mã sinh viên
	char name[100]; //Tên
	float dtb;  //Điểm trung bình
}sinhvien_t;

Định nghĩa danh sách liên kết đơn.

//Mục đích 2 dòng này chỉ để mình có thể sử dụng khai báo là node ở  (**) bên dưới, vì để là ListSV trông khá xấu
struct ListSV;
typedef struct ListSV node;

//Định nghĩa danh sách liên kết đơn
struct ListSV{
	sinhvien_t sv;//Khai bao kiểu dữ liệu sinh viên
	node *next;  (**)    //Một node sẽ trỏ tới 1 node khác
};

typedef struct ListSV *root;//Định nghĩa kiểu dữ liệu nút gốc của list là root

Hàm khởi tạo

void init(root *A){
	*A=NULL; //Khởi tạo nút gốc là NULLL
}

Hàm kiểm tra danh sách rộng

bool isNull(root A){
	return A==NULL; //Nếu nút gốc mà bằng null thì hàm trả về 1, không null thì trả về 0 
}

Hàm tính độ dài danh sách

int length(root A){
	if(isNull(A)) return 0; //Nếu danh sách rộng thì độ dài là 0

//Khởi tạo biến độ dài là 0
	int len=0;

//Duyệt vòng lặp cho đến khi nút rỗng
	while(A!=NULL) {
		len++;//Cộng chiều dài lên 1
		A=A->next; //Gắn nút bằng nút theo (nút trỏ tới)
	}
	return len; //Trả về độ dài cho hàm
}

Hàm nhập thông tin 1 sinh viên và tạo nên 1 node mới

node *createNode()
{
	node *sv = (node*) malloc(sizeof(node)); //Khởi tạo node

//Nhập thông tin cho sv vào node
	printf("\n\nNhap ten sinh vien: ");
	fflush(stdin); gets((*sv).sv.name);
	printf("Nhap ma sinh vien: ");
	gets((*sv).sv.msv);
	
	printf("Nhap dtb sinh vien: ");     
   	scanf("%f",&(*sv).sv.dtb);

//Cho node này trỏ tới null
   	sv->next=NULL;
   	return sv; //trả về node
}

Hàm chèn 1 node vào cuối danh sách

void Insert_last(root *A, node *P){

//Nếu A đang null tức là danh sách đang rỗng thì ta gắn luôn nút gốc bằng nút P
	if(*A==NULL){
		 *A=P;
		 return;
	}
		
	node *B=*A; //Khai bao một node B gắn bằng nút gốc
	
//Sử dụng vòng lặp while lặp tới cuối danh sách (Nếu node đó trỏ tới null thì node đó là node cuối)
	while(B->next!=NULL){
		B=B->next;
	}
//Cho node cuối trỏ tới P
	B->next=P;
}

Hàm chèn 1 node vào đầu danh sách

void Insert_first (root *A, node *P)  {
 
//Nếu A null thì ta gắn luôn A = P
    if(*A==NULL){
		 *A=P;
		 return;//Dừng hàm này chương trình kg thực hiện xuống lệnh bên dưới
	}

//Ngược lại
    P->next = *A;  //Ta cho nút P trỏ tới nút gốc
    *A = P; //Gắn lại nút gốc bằng nút P
}

Hàm nhập danh sách sinh viên

void input(root *A)
{                    
	printf("Nhap so luong sinh vien: ");
	int n; scanf("%d",&n); //Nhập số lượng sinh viên
	int i;
	for(i=0;i<n;i++){
		node *b = createNode();
		Insert_first(A, b);
	}
}

Hàm xuất danh sách sinh viên

void output(root A){
	while(A!=NULL) 
	{
		printf("\n%s   %s  %f", A->sv.name, A->sv.msv, A->sv.dtb);
		A = A->next;
	}
}

Chương trình hoàn chỉnh

Từ tất cả các hàm ta đã cùng viết ở trên, chúng ta có thể ghép chúng lại thành 1 chương trình hoàn chỉnh như dưới đây.

Chương trình mẫu

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


typedef struct SinhVien{
	char msv[100];
	char name[100];
	float dtb;
}sinhvien_t;

struct ListSV;
typedef struct ListSV node;

struct ListSV{
	sinhvien_t sv;
	node *next;
};

typedef struct ListSV *root;


void init(root *A){
	*A=NULL;
}

bool isNull(root A){
	return A==NULL;
}
int length(root A){
	if(A==NULL) return 0;
	int len=0;
	while(A!=NULL) {
		len++;
		A=A->next;
	}
	return len;
}

node *createNode()
{
	node *sv = (node*) malloc(sizeof(node));
	printf("\n\nNhap ten sinh vien: ");
	fflush(stdin); gets((*sv).sv.name);
	printf("Nhap ma sinh vien: ");
	gets((*sv).sv.msv);
	
	printf("Nhap dtb sinh vien: ");     
   	scanf("%f",&(*sv).sv.dtb);
   	sv->next=NULL;
   	return sv;
}
void Insert_last(root *A, node *P){
	if(*A==NULL){
		 *A=P;
		 return;
	}
		
	node *B=*A;
	
	while(B->next!=NULL){
		B=B->next;
	}
	B->next=P;
}

void Insert_first (root *A, node *P)  {
      if(*A==NULL){
		 *A=P;
		 return;
	}
    P->next = *A; 
    *A = P;
}
void input(root *A)
{                    
	printf("Nhap so luong sinh vien: ");
	int n; scanf("%d",&n);
	int i;
	for(i=0;i<n;i++){
		node *b = createNode();
		Insert_first(A, b);
	}
}
void deletePhantuthuK(root *A){
	int n=length(*A)+1;
	printf("Nhap vi tri k can xoa phan tu: ");
	int k; scanf("%d", &k);
	if(k==0 || k>n){
		printf(" =>Vi tri xoa khong hop le");
		return;
	}
	if(k==1) *A=(*A)->next;
	else{
		int vt=2;
		node *B= *A;
		while(vt<k){
			B=B->next;
			vt++;
		}
		B->next = B->next->next;
	}
}
void output(root A){
	while(A!=NULL) 
	{
		printf("\n%s   %s  %f", A->sv.name, A->sv.msv, A->sv.dtb);
		A = A->next;
	}
}


int main()
{
	root A;
	init(&A);
	input(&A);
	printf("\n\n------------------XUAT--------\n");
	output(A);
	node * b;
	
	while(true){
		int chon;
		printf("\n\n\n\n--------CHON---------\n1.Nhap lai list\n2.Kiem tra xem list rong\n3.Do dai list\n4.Chen vao dau list\n5.Chen vao cuoi list\n6.Xoa phan tu\n");
		scanf("%d", &chon);
		switch(chon){
			case 1:
				init(&A);
				input(&A);
				output(A);
				break;
			case 2:
				if(isNull(A)) printf("List rong");
					else printf("List khong rong");
				break;
			case 3:
				printf("Do dai list: %d", length(A));
				break;
			case 4:
				b = createNode();
				Insert_first(&A, b);
				output(A);
				break;
			case 5:
				b = createNode();
				Insert_last(&A, b);
				output(A);
				break;
			case 6:
				deletePhantuthuK(&A);
				output(A);
				break;
		}
	}
}

[XEM THÊM NHIỀU BÀI VIẾT LẬP TRÌNH C/C++ TẠI ĐÂY]

ĐỌC THÊM
Tìm hiểu về Hàm đệ quy
Thuật toán tìm kiếm nhị
Tìm hiểu về thuật toán Sàng nguyên tố (sàng Eratosthenes)
Cách kiểm tra Số hoàn hảo trong Lập trình C/C++
0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x