//


#include <iostream>
#include <list>
#include <ctype.h>
#include "iostream"
#include "math.h"
#include <windows.h>
#include <conio.h>

using namespace std;

list<int> data;
list<int>::iterator iter;
void gotoxy(int x, int y)
{
	COORD pos = { x, y };
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
}
struct NODE
{
	int x;
	NODE *pNEXT;
};
struct LIST
{
	NODE *pHead, *pTail;
};
void CreatEmptyList(LIST &list)
{
	list.pHead = list.pTail = NULL;
}
int ListLen(LIST list)
{
	int dem = 0;
	NODE *p = list.pHead;
	p = p->pNEXT;
	while (p != NULL)
	{
		dem = dem + 1;
		p = p->pNEXT;
	}
	return dem;
}
bool IsEmptyList(LIST list)
{
	return(list.pHead == NULL && list.pTail == NULL);
}
void AddHead(LIST &list, NODE *pNew)
{
	pNew->pNEXT = list.pHead;
	list.pHead = pNew;
}
NODE *CreatNode(int x)
{
	NODE *p;
	p = new NODE;
	if (p == NULL)
		exit(0);
	p->x = x;
	p->pNEXT = NULL;
	return p;
}
void AddNode(LIST &list, NODE *pNew, int k)
{
	NODE *p = list.pHead;
	for (int i = 1; i < k; i++)
		p = p->pNEXT;
	pNew->pNEXT = p->pNEXT;
	p->pNEXT = pNew;
}
void Input(LIST &list)
{
	NODE *pNew;
	int x;
	char c[2];
	do
	{
		cout << "nhap gia tri nguyen (# de ket thuc): ";
		cin >> c;
		fflush(stdin);
		if (c[0] == '#') break;
		x = atoi(c);
		pNew = CreatNode(x);
		AddHead(list, pNew);
	} while (1);
}
void Output(LIST list)
{
	int x;
	NODE *pNew;
	pNew = list.pHead;
	while (pNew != NULL)
	{
		x = pNew->x;
		cout << x << endl;
		pNew = pNew->pNEXT;
	}
}
float Timchanduong(LIST list, int  &dem)
{
	int x, tong = 0;
	float tb;

	NODE *pNEW;
	pNEW = list.pHead;

	while (pNEW != NULL)
	{
		x = pNEW->x;
		if (x % 2 == 0 && x>0)
		{
			tong += x;
			dem++;
		}
		pNEW = pNEW->pNEXT;
	}
	return float(tong) / dem;
}
int GetInput()
{
	int choice;
	cin >> choice;
	return choice;
}
int cau5(LIST list)
{
	int dem = 0;
	float tbc;
	tbc = Timchanduong(list, dem);
	cout << "co " << dem << " so chan duong\ntrungbinh: " << tbc << endl;
	return 0;
}
int timk(LIST list, int k)
{
	NODE *p = list.pHead;
	p = p->pNEXT;
	int dem = 0;
	while (p != NULL)
	{
		if (p->x == k) dem = dem + 1;
		p = p->pNEXT;
	}
	return dem;
}
int timchanlientiep(LIST list, int &vitri)
{
	NODE *p = list.pHead;
	p = p->pNEXT;
	int dem = 0;
	vitri = 0;
	while (p != NULL && dem < 3)
	{
		vitri++;
		if (p->x % 2 == 0) dem++;
		else dem = 0;
		p = p->pNEXT;
	}
	if (dem == 3)
	{

		return 1;
	}
	else return 0;
}
void ChinhPhuong(LIST list)
{
	NODE *p = list.pHead;
	p = p->pNEXT;
	int a;
	while (p != NULL)
	{
		a = sqrt(float(p->x));
		if (p->x == a * a) cout << p->x << endl;
		p = p->pNEXT;
	}
}
int snt(int n)
{
	if (n < 2) return 0;
	if (n == 2) return 1;
	for (int i = 2; i <= sqrt(float(n)); i++)
		if (n % i == 0) return 0;
	return 1;
}
void delnode(LIST &list, NODE *pDel)
{
	NODE *p = list.pHead;
	if (list.pHead->pNEXT == pDel) list.pHead->pNEXT = pDel->pNEXT;
	else
	{
		while (p->pNEXT != pDel) p = p->pNEXT;
		p->pNEXT = pDel->pNEXT;
	}
}
void xoant(LIST &list)
{
	NODE *p = list.pHead;
	p = p->pNEXT;
	while (p != NULL)
	{
		if (snt(p->x) == 1) delnode(list, p);
		p = p->pNEXT;
	}
}
void xoatrung(LIST &list)
{
	NODE *p = list.pHead;
	p = p->pNEXT;
	NODE *q = new NODE;
	while (p != NULL)
	{
		q = p;
		while (q->pNEXT != NULL)
		{
			if (p->x == q->pNEXT->x)
			{
				NODE *t = new NODE;
				t->pNEXT = q->pNEXT->pNEXT;
				delete q->pNEXT;
				q->pNEXT = t;
			}
			q = q->pNEXT;
		}
		p = p->pNEXT;
	}
}
void KhungChuNhat(int a, int b, int c, int d)
{
	int i;
	for (i = a; i <= c; i++)
	{
		gotoxy(i, b);          printf("\xcd");
		gotoxy(i, d);          printf("\xcd");
	}
	for (i = b; i <= d; i++)
	{
		gotoxy(a, i);          printf("\xba");
		gotoxy(c, i);          printf("\xba");
	}
	gotoxy(a, b);			printf("\xc9");
	gotoxy(a, d);          printf("\xc8");
	gotoxy(c, b);          printf("\xbb");
	gotoxy(c, d);          printf("\xbc");
}
void DisplayMainMenu()
{
	system("cls");
	int i = 13;
	KhungChuNhat(12, 5, 70, 10);
	gotoxy(42, 7); cout << "BAI LAM NHOM";
	KhungChuNhat(12, 12, 70, 30);
	gotoxy(15, i++);  cout << "Lua chon cong viec\n";
	gotoxy(15, i++);  cout << "1 - Tao danh sach so\n";
	gotoxy(15, i++);  cout << "2 - Them mot phan tu vao danh sach\n";
	gotoxy(15, i++);  cout << "3 - Dem cac so k trong day va kiem";
	gotoxy(20, i); cout << "tra xem co chia het 3 khong\n";
	i++;
	gotoxy(15, i++);  cout << "4 - Kiem tra va xuat 3 so chan duong canh nhau (neu co)\n";
	gotoxy(15, i++);  cout << "5 - Dem so cac phan tu la so chan ";
	gotoxy(20, i); cout << "duong va xuat trung binh cong cac so\n";
	i++;
	gotoxy(15, i++);  cout << "6 - Sap xep va hien danh sach theo thu tu tang dan\n";
	gotoxy(15, i++);  cout << "7 - Liet ke cac so chinh phuong\n";
	gotoxy(15, i++);  cout << "8 - Xoa tat ca cac so nguyen to trong danh sach\n";
	gotoxy(15, i++);  cout << "9 - Xoa cac gia tri trung nhau trong danh sach\n";
	gotoxy(15, i++);  cout << "Lua chon: ";
}
void InterchangeSort_ListLinked(LIST &list)
{
	NODE *p = new NODE;
	NODE *q = new NODE;
	NODE *u = new NODE;
	NODE *v = new NODE;
	NODE *t = new NODE;
	for (u = list.pHead, p = list.pHead->pNEXT; p != NULL; u=u->pNEXT, p = p->pNEXT)
		for (v = u->pNEXT, q = p->pNEXT; q != NULL; v = v->pNEXT, q = q->pNEXT)
			if (p->x > q->x)
				if (p->pNEXT == q)
				{
					p->pNEXT = q->pNEXT;
					q->pNEXT = p;

					u->pNEXT = p;
				}
				else
				{
					t->pNEXT = q->pNEXT;
					q->pNEXT = p->pNEXT;
					p->pNEXT = t->pNEXT;
					u->pNEXT = q;
					v->pNEXT = p;
				}
	//delete t;
}
int main()
{
	LIST list;
	CreatEmptyList(list);
	do
	{
		DisplayMainMenu();
		switch (GetInput())
		{
		case 1:
			system("cls");
			Input(list);
			break;
		case 2:
			int giatri;
			int vitri;
			NODE *p;
			system("cls");
			do
			{
				cout << "Vi tri muon them: ";
				cin >> vitri;
			} while (vitri < 0 || vitri > ListLen(list));
			cout << "Gia tri muon them: ";
			cin >> giatri;
			p = CreatNode(giatri);
			AddNode(list, p, vitri);
			break;
		case 3:
			system("cls");
			int k, dem;
			do
			{
				cout << "Gia tri k: ";
				cin >> k;
			} while (k == 0);
			dem = timk(list, k);
			if (dem == 0) cout << "Khong co gia tri k";
			else
			{
				cout << "co gia tri " << k << "\n";
				if (dem % 3 == 0) cout << "chia het 3\n";
				else cout << "khong chia het 3";
			}
			_getch();
			break;
		case 4:
			int vitri1;
			system("cls");
			if (timchanlientiep(list, vitri1) == 1) cout << "co 3 so chan lien tiep, vi tri: " << vitri1;
			_getch();
			break;
		case 5:
			system("cls");
			cau5(list);
			_getch();
			break;
		case 6:
			system("cls");
			InterchangeSort_ListLinked(list);
			Output(list);
			_getch();
			break;
		case 7:
			ChinhPhuong(list);
			_getch();
			break;
		case 8:
			system("cls");
			xoant(list);
			Output(list);
			_getch();
			break;
		case 9:
			system("cls");
			xoatrung(list);
			Output(list);
			_getch();
			break;
		default:
			system("cls");
			Output(list);
			_getch();
			break;
		}

	} while (1);

}