[Cấu trúc dữ liệu và giải thuật] – Bài tập danh sách liên kết

Bài tập: Viết chương trình dùng danh sách liên kết quản lý thư viện.

**Yêu cầu:

• Xây dựng kiểu dữ liệu thích hợp để lưu trữ thông tin sách.
• Viết hàm nhập xuất danh sách thông tin sách. ( Ứng dụng danh sách liên kết ).
• Viết hàm tìm kiếm không khóa ( tìm dựa trên tên sách người dùng nhập vào ) và tìm kiếm theo khóa ( tìm theo số thứ tự người dùng nhập vào ) .
• Viết hàm sắp xếp sách theo số thứ tự.

**SOURCE CODE:

//BT QUẢN LÝ THƯ VIỆN
#include "pch.h"
#include <string.h>
#include <conio.h>
#include <iostream>
#include <stdio.h>

using namespace std;

//Định nghĩa cấu trúc Sách
typedef struct
{
	int stt;
	char ten_sach[100];
	char ten_TG[50];
	int namXB;
	int so_ban;
}stype;

//Định nghĩa nút (node) = phần tử danh sách
typedef struct Node
{
	stype infor; /*phần thông tin*/
	struct Node *next; /*Phần con trỏ*/
}snodetype;

//định nghĩa ds liên kết quản lý thông tin sách
typedef struct
{
	snodetype *head;
	snodetype *tail;
}qls_llist;

//Nhập thông tin 1 quyển sách
void Nhap_Sach(stype &s)
{
	cout << "\nSTT: ";
	cin >> s.stt;

	cin.ignore();
	cout << "\nTen cuon sach: ";
	cin.getline(s.ten_sach, 100);

	cout << "\nTen tac gia: ";
	cin.getline(s.ten_TG, 50);

	cout << "\nNam xuat ban: ";
	cin >> s.namXB;

	cout << "\nSo ban: ";
	cin >> s.so_ban;
}

//Xuất thông tin 1 quyển sách
void Xuat_Sach(stype s)
{
	cout << "\nSTT: " << s.stt;
	cout << "\nTen cuon sach: " << s.ten_sach;
	cout << "\nTac gia: " << s.ten_TG;
	cout << "\nNam xuat ban: " << s.namXB;
	cout << "\nSo ban: " << s.so_ban;
}

//Tạo node từ ô bự đã nhập
snodetype* get_snode(stype x)
{
	snodetype *p;
	p = new snodetype;
	p->infor = x;
	p->next = NULL;
	return p;
}

//Tạo node từ phần thông tin tự nhập
snodetype* get_node2()
{
	/*Nhập phần thông tin của node*/
	stype x;
	Nhap_Sach(x);

	//Tạo node trống
	snodetype *p;
	p = new snodetype;

	//Xử lý phần thông tin và phần con trỏ của Node
	p->infor = x;
	p->next = NULL;

	return p;
}

//In Node ra màn hình
void Print_snode(snodetype *n)
{
	Xuat_Sach(n->infor);
}

//Khởi tạo ds
void Init_qls_llist(qls_llist *l)
{
	l->head = NULL;
	l->tail = NULL;
}

//thêm phần tử vào đầu ds
void Addfirst(qls_llist *l, snodetype *n)
{
	if (l->head == NULL)
	{
		l->head = n;
		l->tail = n;
	}
	else
	{
		n->next = l->head;
		l->head = n;
	}
}

//In dslk
void printlist(qls_llist *l)
{
	snodetype *p;
	p = l->head;
	while (p != NULL)
	{
		Xuat_Sach(p->infor);
		p = p->next;
	}
}

//Tim kiem theo khoa
snodetype* findlist(qls_llist *l, int x)
{
	snodetype *p;
	p = l->head;
	while (p != NULL && p->infor.stt != x)
	{
		p = p->next;
	}
	return p;
}

//Tim kiem khong khoa, xuat ket qua dau tien tim thay
snodetype* findlist_2a(qls_llist *l, char ts[])
{
	snodetype *p;
	p = l->head;
	while (p != NULL && strcmp(p->infor.ten_sach, ts) != 0)
	{
		p = p->next;
	}
	return p;
}

//Tim kiem khong khoa, ket hop xuat tat ca ket qua 
int findlist_2b(qls_llist *l, char tg[])
{
	int so_kq = 0;
	snodetype *p;
	p = l->head;
	while (p != NULL)
	{
		if (strcmp(p->infor.ten_TG, tg) == 0)
		{
			so_kq++;
			Print_snode(p);
		}
		p = p->next;
	}
	return so_kq;

}

//ctc hoan vi 2 o bu
void swap(stype &a, stype &b)
{
	stype t = a;
	a = b;
	b = t;
}

//sx dslk
void SelectionSortlist(qls_llist* list)
{
	snodetype *p, *q, *min;
	p = list->head;
	while (p != list->tail)
	{
		q = p->next;
		/*tim min*/
		min = p;
		while (q != NULL)
		{
			if (q->infor.stt < min->infor.stt)
				min = q;
			q = q->next;
		}
		swap(min->infor, p->infor);
		p = p->next;
	}
}
void main()
{
	/*Test nhập xuất thông tin sách*/
	stype s;
	Nhap_Sach(s);
	Xuat_Sach(s);


	//test tạo node-in node
	stype s;
	Nhap_Sach(s);
	snodetype *n;
	n = new snodetype;
	n = get_snode(s);
	Print_snode(n);


	//test nhap-xuat dslk
	qls_llist *ds;
	ds = new qls_llist;
	Init_qls_llist(ds);
	char t = 'c';
	while (t == 'c' || t == 'C')
	{
		snodetype *n;
		n = new snodetype;
		cout << "\nNhap thong tin sach: ";
		n = get_node2();
		Addfirst(ds, n);
		cout << "\nNhap tiep (C/K)?";
		cin >> t;
	}
	printlist(ds);

	//test tim kiem theo khoa
	int x;
	cout << "\nNhap stt sach can tim: "; cin >> x;
	snodetype *kq;
	kq = findlist(ds, x);
	if (kq == NULL)
		cout << "\nKhong tim thay ";
	else
		Print_snode(kq);

	//test tim kiem khong khoa
	char ts[100];
	cin.ignore();
	cout << "\nNhap ten sach can tim: ";

	snodetype *kq;
	kq = findlist_2a(ds, ts);
	if (kq == NULL)
		cout << "\n Khong tim thay ";
	else
		Print_snode(kq);

		//test tim kiem khong khoa
		//Nhap ten tac gia can tim
		/*char tg[100];
		cin.ignore();
		cout << "\nNhap ten tac gia can tim: "; 
		cin.getline(tg, 100);
		int kq;
		cout << "\nKet qua tim theo tac gia: ";
		kq = findlist_2b(ds, tg);
		cout << "\nTong cong co: " << kq << " ket qua duoc tim thay.\n";*/
       SelectionSortlist(ds);
       printlist(ds);
		system("pause");
}
//Chúc các bạn thành công

Tác giả: Lê Minh Nghĩa – 18DHT02 ( Khoa Công Nghệ Thông Tin )