CS4343_lab5

// demo.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
stt 05 
ho va ten Le Van Phuc

#include <iostream>
#include<ctime>
using namespace std;
const int M = 7;
struct node
{
	int data;
	node* pNext;
};
struct  list
{
	node* pHead;
	node* pTail;
};

struct HASHTABLE
{
	list bucket[M];
};
node* CreateNode(int x)
{
	node* p = new node;
	p->data = x;
	p->pNext = NULL;
	return p;
}
void CreateList(list& l)
{
	l.pHead = l.pTail = NULL;
}

void InitBucket(HASHTABLE& h)
{
	for (int i = 0; i < M; i++)
	{
		CreateList(h.bucket[i]);
	}
}
void addTail(list& l, node* p)
{
	if (l.pHead == NULL)
		l.pHead = l.pTail = p;
	else
	{
		l.pTail->pNext = p;
		l.pTail = p;
	}

}
int hashfunct(int data)
{
	return data % M;
}
void insert(HASHTABLE& h, int data)
{
	int b = hashfunct(data);
	node* p = CreateNode(data);
	addTail(h.bucket[b], p);
}

void Input(HASHTABLE& h)
{
	int n;
	cout << "Nhap so luong phan tu: ";
	cin >> n;
	int x = 0;
	for (int i = 0; i < n; i++)
	{
		cout << "Nhap gia tri muon chen vo bang bam: ";
		cin >> x;
		insert(h, x);
	}
}
void InputFromArray(HASHTABLE& h, int a[], int n)
{
	int x = 0;
	for (int i = 0; i < n; i++)
	{
		x = a[i];
		insert(h, x);
	}
}
void InputAuto(HASHTABLE& h)
{
	srand(time(NULL));
	int n = (int)rand() % (95 - 45 + 1) + 45;
	int x = 0;
	for (int i = 0; i < n; i++)
	{
		//srand(time(NULL));
		x = (int)rand() % (988 - 856 + 1) + 856;
		insert(h, x);
	}
}

void print_BK(list l)
{
	for (node* p = l.pHead; p != NULL; p = p->pNext)
	{
		cout << p->data << "\t";
	}
	cout << endl;
}
void show_hash_table(HASHTABLE h)
{
	for (int i = 0; i < M; i++)
	{
		cout << "Bucket[" << i << "]: ";
		print_BK(h.bucket[i]);
	}
}
bool FindX(HASHTABLE h, int x)
{
	int b = hashfunct(x);
	list l = h.bucket[b];
	for (node* p = l.pHead; p != NULL; p = p->pNext)
	{
		if (p->data == x)
			return true;
	}
	return false;
}
int tong_le(HASHTABLE h)
{
	int tong = 0;
	for (int i = 0; i < M; i++)
	{

		for (node* p = h.bucket[i].pHead; p != NULL; p = p->pNext)
		{
			if ((p->data % 2) != 0)
			tong = tong + p->data;
		}
	}
	return tong;
}
bool ktNguyenTo(int n)
{
	if (n < 2)
		return false;
	if (n == 2)
		return true;
	if (n % 2 == 0)
		return false;
	for (int i = 3; i <= n / 2; i += 2)
		if (n % i == 0)
			return false;
	return true;
}
int tong_so_nguyen_to(HASHTABLE h)
{
	int tong = 0;
	for (int i = 0; i < M; i++)
	{

		for (node* p = h.bucket[i].pHead; p != NULL; p = p->pNext)
		{
			if (ktNguyenTo(p->data))
				tong = tong + p->data;
		}
	}
	return tong;
}
int dem_chan(HASHTABLE h)
{
	int dem = 0;
	for (int i = 0; i < M; i++)
	{
		for (node* p = h.bucket[i].pHead; p != NULL; p = p->pNext)
		{
			if (p->data % 2 == 0)
			dem++;
		}
	}
	return dem;
}
int dem_Am(HASHTABLE h)
{
	int dem = 0;
	for (int i = 0; i < M; i++)
	{

		for (node* p = h.bucket[i].pHead; p != NULL; p = p->pNext)
		{
			if (p->data < 0)
				dem++;
		}
	}
	return dem;
}
bool isEmpty(list l)
{
	if (l.pHead == NULL)
		return true;
	return false;
}
bool isEmpty(HASHTABLE h)
{
	for (int i = 0; i < M; i++)
	{
		if (isEmpty(h.bucket[i]) == false)
			return false;
	}
	return true;
}

void PrintMenu()
{
	cout << "\t\t1. Tao du lieu tu dong cho mang bam." << endl;
	cout << "\t\t2. Tao du lieu cho mang bam tu mang mot chieu." << endl;
	cout << "\t\t3. Tao du lieu thu cong tu ban phim." << endl;
	cout << "\t\t4. In gia chi co trong mang bam" << endl;
	cout << "\t\t5. Xoa gia tri cua mang bam." << endl;
	cout << "\t\t6. Tim gia tri trong mang bam." << endl;
	cout << "\t\t7. Tong cac gia tri le co trong mang bam." << endl;
	cout << "\t\t8. Kiem tra mang bam co rong hay khong" << endl;
	cout << "\t\t9. Tong so nguyen to co trong bang bam." << endl;
	cout << "\t\t10. Dem so am co trong bang bam." << endl;
	cout << "\t\t11. Dem so chan co trong bang bam." << endl;
	cout << "\t\t0. Thoat khoi chuong trinh." << endl;
	cout << "\t\tBan vui long chon chuc nang: ";
}

int main()
{
	HASHTABLE h;
	int a[] = { 12,6,76,8,9,45,5,3,5,6,7 };
	int x, TongLe, count, tong;
	InitBucket(h);
	int choice;

	do
	{
		PrintMenu();
		cin >> choice;
		switch (choice)
		{
		case 1:
			InputAuto(h);
			break;
		case 2:
			InputFromArray(h, a, sizeof(a) / 4);
			break;
		case 3:
			Input(h);
			break;
		case 4:
			show_hash_table(h);
			break;
		case 5:
			break;
		case 6:
			cout << "Nhap gia tri ban muon tim: ";
			cin >> x;
			if (FindX(h, x))
				cout << "Co gia tri " << x << "trong bang bam." << endl;
			else
				cout << "Khong Co gia tri " << x << " trong bang bam." << endl;
			break;
		case 7:
			TongLe = tong_le(h);
			cout << "Tong cac gia tri cua bang bam la: " << TongLe << endl;
			break;
		case 8:
			if (isEmpty(h))
				cout << "Bang bam rong." << endl;
			else
				cout << "Bang Bam khong rong." << endl;
			break;
		case 9:
			tong = tong_so_nguyen_to(h);
			cout << "Tong so nguyen to co trong bang bam la " << tong << endl;
			break;
		case 10:
			count = dem_Am(h);
			cout << "So luong so am co trong bang bam la " << count << endl;
			break;
		case 11:
			count = dem_chan(h);
			cout << "So luong so chan co trong bang bam la: " << count << endl;
			break;
		default:
			break;
		}
		system("pause");
		system("cls");
	} while (choice != 0);
	cout << "GoodBye!" << endl;
	return 0;
}