DANH SÁCH LIÊN KẾT ĐƠN
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

Quản lý sinh viên sử dụng danh sách liên kết đơn

Trong hướng dẫn này mình sẽ thực hiện một chương trình quản lý sinh viên sử dụng danh sách liên kết đơn.

Chúng ta sẽ quản lý sinh viên với các thông tin cần thiết và các thao tác thêm, xóa và sắp xếp sinh viên.

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Đề bài: Xây dựng chương trình quản lý sinh viên bằng DSLK đơn

Cho một sinh viên có cấu trúc: mã (int), tên (char *). Dùng danh sách liên kết đơn với con trỏ phead để thao tác:

  • Khởi tạo list dạng con trỏ
  • Thêm node vào cuối danh sách
  • Sắp xếp theo mã
  • Xóa node

Chương trình quản lý sinh viên sử dụng DSLK đơn

Chúng ta sẽ lần lượt tạo cấu trúc sinh viên, cấu trúc danh sách liên kết đơn và các thao tác liên quan.

Đầu tiên chúng ta cần tạo một cấu trúc sinh viên với mã số sinh viên ma và tên sinh viên ten.

//tao cau truc sinh vien
struct SinhVien
{
	int ma;
	char ten[150];
};

Tiếp đến tạo cấu trúc dữ liệu của danh sách liên kết đơn với giá trị data và con trỏ pNext. Khởi tạo giá trị cho pHead và pTail bằng NULL.

//tao cau truc danh sach lien ket don
struct Node
{
	SinhVien *data;
	Node *pNext;
};
struct SingleList
{
	Node *pHead;
};
//khoi tao danh sach lien ket don
void Initialize(SingleList *&list)
{
	list=new SingleList;
	list->pHead=NULL;
}

Tạo một hàm NhapSinhVien() sử dụng cấu trúc SinhVien để nhập các thông tin của sinh viên như: MSSV và tên sinh viên

SinhVien *NhapSinhVien()
{
	SinhVien *sv=new SinhVien;
	cout<<"Nhap MSSV:";
	cin>>sv->ma;
	cin.ignore();
	cout<<"Nhap ho va ten:";
	gets(sv->ten);
	return sv;
}

Bây giờ chúng ta bắt đầu tạo Node với các thông tin của cấu trúc SinhVien, sau đó thêm Node vào cuối danh sách.

//tao node sinh vien
Node *CreateNode(SinhVien *sv)
{
	Node *pNode=new Node;
	if(pNode!=NULL)
	{
		pNode->data=sv;
		pNode->pNext=NULL;
	}
	else
	{
		cout<<"cap phat bo nho that bai!!!";
	}
	return pNode;
}
//them node vao cuoi danh sach
void InsertLast(SingleList *&list,SinhVien *sv)
{
	Node *pNode=CreateNode(sv);
	if(list->pHead==NULL)
	{
		list->pHead=pNode;
	}
	else
	{
		Node *pTmp=list->pHead;
		
		while(pTmp->pNext!=NULL)
		{
			pTmp=pTmp->pNext;
		}
		pTmp->pNext=pNode;
	}
}

Sau khi thêm Node vào danh sách ta thực hiện các thao tác theo yêu cầu của đề bài. Đầu tiên là việc sắp xếp các sinh viên theo MSSV.

Ở bài tìm kiếm và sắp xếp trong danh sách liên kết đơn mình đã giới thiệu các bạn thao tác sắp xếp. Dựa vào đó ta chỉ cần biến đổi một chút sẽ có ngay hàm sắp xếp SortList() theo MSSV.

void SortList(SingleList *&list)
{
	for(Node *pTmp=list->pHead;pTmp!=NULL;pTmp=pTmp->pNext)
	{
		for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext)
		{	
			SinhVien *svTmp=pTmp->data;
			SinhVien *svTmp2=pTmp2->data;
			if(svTmp2->ma<svTmp->ma)
			{
				int ma=svTmp->ma;
				char ten[150];
				strcpy(ten,svTmp->ten);
				
				svTmp->ma=svTmp2->ma;
				strcpy(svTmp->ten,svTmp2->ten);
				svTmp2->ma=ma;
				strcpy(svTmp2->ten,ten);				
			}
		}	
	}
}

Tương tự như hàm sắp xếp, để xóa một sinh viên dựa vào tên ta thực hiện vòng lặp while lặp từng phần tử trong danh sách. Nếu phần tử đó trùng với phần tử được nhập vào từ bàn phím ta thực hiện delete phần tử đó ra khỏi danh sách.

void RemoveNode(SingleList *&list,int ma)
{
	Node *pDel=list->pHead;
	if(pDel==NULL)
	{
		cout<<"Danh sach rong!";
	}
	else
	{
		Node *pPre=NULL;
		while(pDel!=NULL)
		{
			SinhVien *sv=pDel->data;
			if(sv->ma==ma)
				break;
			pPre=pDel;
			pDel=pDel->pNext;
		}
		if(pDel==NULL)
		{
			cout<<"khong tim thay MSSV: "<<ma;
		}
		else
		{
			if(pDel==list->pHead)
			{
				list->pHead=list->pHead->pNext;
				pDel->pNext=NULL;
				delete pDel;
				pDel=NULL;
			}
			else
			{
				pPre->pNext=pDel->pNext;
				pDel->pNext=NULL;
				delete pDel;
				pDel=NULL;
			}
		}
	}
}

Sau khi thực hiện tạo các thao tác, ta chỉ cần tạo hàm main() và gọi các thao tác đó ra để sử dụng.

int main(int argc, char** argv) {
	SingleList *list;
	Initialize(list);
	SinhVien *teo=NhapSinhVien();
	InsertLast(list,teo);
	SinhVien *ty=NhapSinhVien();
	InsertLast(list,ty);
	SinhVien *bin=NhapSinhVien();
	InsertLast(list,bin);
	PrintList(list);
	SortList(list);
	cout<<"\nSau khi sap xep:\n";
	PrintList(list);
	cout<<"\Ban muon xoa sinh vien co MSSV: ";
	int ma;
	cin>>ma;
	RemoveNode(list,ma);
	cout<<"\nSau khi xoa:\n";
	PrintList(list);
}

Full code:

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
//tao cau truc sinh vien
struct SinhVien
{
	int ma;
	char ten[150];
};
//tao cau truc danh sach lien ket don
struct Node
{
	SinhVien *data;
	Node *pNext;
};
struct SingleList
{
	Node *pHead;
};
//khoi tao danh sach lien ket don
void Initialize(SingleList *&list)
{
	list=new SingleList;
	list->pHead=NULL;
}
//nhap thong tin sinh vien
SinhVien *NhapSinhVien()
{
	SinhVien *sv=new SinhVien;
	cout<<"Nhap MSSV:";
	cin>>sv->ma;
	cin.ignore();
	cout<<"Nhap ho va ten:";
	gets(sv->ten);
	return sv;
}
//tao node sinh vien
Node *CreateNode(SinhVien *sv)
{
	Node *pNode=new Node;
	if(pNode!=NULL)
	{
		pNode->data=sv;
		pNode->pNext=NULL;
	}
	else
	{
		cout<<"cap phat bo nho that bai!!!";
	}
	return pNode;
}
//them node vao cuoi danh sach
void InsertLast(SingleList *&list,SinhVien *sv)
{
	Node *pNode=CreateNode(sv);
	if(list->pHead==NULL)
	{
		list->pHead=pNode;
	}
	else
	{
		Node *pTmp=list->pHead;
		
		while(pTmp->pNext!=NULL)
		{
			pTmp=pTmp->pNext;
		}
		pTmp->pNext=pNode;
	}
}
//hien thi danh sach
void PrintList(SingleList *list)
{
	Node *pTmp=list->pHead;
	if(pTmp==NULL)
	{
		cout<<"Danh sach rong";
		return;
	}
	while(pTmp!=NULL)
	{
		SinhVien *sv=pTmp->data;
		cout<<sv->ma<<"\t"<<sv->ten<<"\n";
		pTmp=pTmp->pNext;
	}
}
//sap xep
void SortList(SingleList *&list)
{
	for(Node *pTmp=list->pHead;pTmp!=NULL;pTmp=pTmp->pNext)
	{
		for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext)
		{	
			SinhVien *svTmp=pTmp->data;
			SinhVien *svTmp2=pTmp2->data;
			if(svTmp2->ma<svTmp->ma)
			{
				int ma=svTmp->ma;
				char ten[150];
				strcpy(ten,svTmp->ten);
				
				svTmp->ma=svTmp2->ma;
				strcpy(svTmp->ten,svTmp2->ten);
				svTmp2->ma=ma;
				strcpy(svTmp2->ten,ten);				
			}
		}	
	}
}
//xoa
void RemoveNode(SingleList *&list,int ma)
{
	Node *pDel=list->pHead;
	if(pDel==NULL)
	{
		cout<<"Danh sach rong!";
	}
	else
	{
		Node *pPre=NULL;
		while(pDel!=NULL)
		{
			SinhVien *sv=pDel->data;
			if(sv->ma==ma)
				break;
			pPre=pDel;
			pDel=pDel->pNext;
		}
		if(pDel==NULL)
		{
			cout<<"khong tim thay MSSV: "<<ma;
		}
		else
		{
			if(pDel==list->pHead)
			{
				list->pHead=list->pHead->pNext;
				pDel->pNext=NULL;
				delete pDel;
				pDel=NULL;
			}
			else
			{
				pPre->pNext=pDel->pNext;
				pDel->pNext=NULL;
				delete pDel;
				pDel=NULL;
			}
		}
	}
}
int main(int argc, char** argv) {
	SingleList *list;
	Initialize(list);
	SinhVien *teo=NhapSinhVien();
	InsertLast(list,teo);
	SinhVien *ty=NhapSinhVien();
	InsertLast(list,ty);
	SinhVien *bin=NhapSinhVien();
	InsertLast(list,bin);
	PrintList(list);
	SortList(list);
	cout<<"\nSau khi sap xep:\n";
	PrintList(list);
	cout<<"\Ban muon xoa sinh vien co MSSV: ";
	int ma;
	cin>>ma;
	RemoveNode(list,ma);
	cout<<"\nSau khi xoa:\n";
	PrintList(list);

  cout<<"\n---------------------------\n";
  cout<<"Chuong trinh nay duoc dang tai Freetuts.net";
}

Kết quả:

bai tap 1 PNG

Như vậy là chúng ta đã thực hiện xong chương trình quản lý sinh viên sử dụng danh sách liên kết đơn. Hãy luyện tập thật nhiều nhé, chúc các bạn thực hiện thành công!!!

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Top