Untitled

#include <iostream>
using namespace std;

struct Node {
	int data;
	Node* next;	
};

typedef struct Node* node;

//Cap phat dong mot node voi du lieu la mot so nguyen x
node makeNode(int x)
{
	node tmp = new Node();
	tmp->data = x;
	tmp->next = NULL;
	return tmp;
}

bool empty(node a)
{
	return  a == NULL;
}

int Size(node a)
{
	int count = 0;
	while (a != NULL)
	{
		count++;
		a = a->next;//gán địa chỉ của nốt tiếp theo cho nốt của hiện tại
		//cho node hiện tại nhảy sang một node tiếp theo
	}
	return count;
}

//them 1 phan tu vao dau danh sach lien ket
void insertFirst(node &a, int x)
{
	node tmp = makeNode(x);
	if (a == NULL)
	{
		a = tmp;
	}
	else {
		tmp->next = a;
		a = tmp;
	}
}
//them 1 phan tu vao cuoi danh sach lien ket
void insertLast(node& a, int x)
{
	node tmp = makeNode(x);
	if (a == NULL)
	{
		a = tmp;
	}
	else {
		node p = a;
		while (p->next != NULL)
		{
			p = p->next;
		}
		p->next = tmp;
	}	
}

//them 1 phan tu vao giua dslk
void insertMiddle(node& a, int x, int pos)
{
	int n = Size(a);
	if (pos <= 0 || pos > n + 1) {
		cout << "Invalid position!\n";
	}
	if (pos == 1)
	{
		insertFirst(a, x);
		return;
	}
	else if (pos == n + 1)
	{
		insertLast(a, x);
	}
	node p = a;
	for (int i = 1; i < pos - 1; i++)
	{
		p = p->next;
	}
	node tmp = makeNode(x);
	tmp->next = p->next;
	p->next = tmp;
}

//xoa 1 phan tu o dau
void deleteFirst(node& a)
{
	if (a == NULL){
		return;
	}
	a = a->next;
}

//xoa 1 phan tu o cuoi
void deleteLast(node& a)
{
	if (a == NULL) return;
	node truoc = NULL, sau = a;
	while (sau ->next != NULL) {
		truoc = sau; 
		sau = sau->next;
	}
	if (truoc == NULL)
	{
		a = NULL;
	}
	else 
	{
		truoc->next = NULL;
	}
}
/////
//xoa 1 phan tu o giua
void deleteMiddle(node& a, int pos)
{
	if (pos <= 0 || pos > Size(a)) return;
	node truoc = NULL, sau = a;
	for (int i = 1; i < pos; i++)
	{
		truoc = sau;
		sau = sau->next;
	}
	if (truoc == NULL)
	{
		a = a->next;
	}
	else {
		truoc->next = sau->next;
	}
}
void in(node a)
{
	cout << "-------------------------\n";
	while(a!=NULL)
	{ 
		cout << a->data << " ";
		a = a->next;
	}
	cout << "\n-------------------------\n";
		
}

void sapxep(node &a)
{
	for (node p = a; p->next != nullptr; p = p->next)
	{
		node min = p;
		for (node q = p->next; q != NULL; q = q->next)
		{
			if (q->data < min->data)
			{
				min = q;
			}
		}
		int tmp = min->data;
		min->data = p->data;
		p->data = min->data;
	}
}

int main()
{
	node head = NULL;
	while (1)
	{
		cout << "----------------MENU----------------\n";
		cout << "1. Chen phan tu vao dau danh sach\n";
		cout << "2. Chen phan tu vao cuoi danh sach\n";
		cout << "3. Chen phan tu vao giua danh sach\n";
		cout << "4. Xoa phan tu o dau danh sach\n";
		cout << "5. Xoa phan tu o cuoi danh sach\n";
		cout << "6. Xoa phan tu o giua danh sach\n";
		cout << "7. Duyet danh sach lien ket\n";
		cout << " 8. Sap xep cac phan tu trong dslk\n";
		cout << "------------------------------------\n";
		cout << "Nhap lua chon: ";
		int lc; cin >> lc;
		switch (lc) {
		case 1:
			cout << "Nhap gia tri can chen: ";
			int x; cin >> x;
			insertFirst(head, x);
			continue;
		case 2:
			cout << "Nhap gia tri can chen: ";
			cin >> x;
			insertLast(head, x);
			continue;
		case 3:
			cout << "Nhap gia tri can chen: ";
			cin >> x;
			cout << "\nNhap vi tri can chen: ";
			int pos; cin >> pos;
			insertMiddle(head, x, pos);
			continue;
		case 4:
			deleteFirst(head);
			continue;
		case 5:
			deleteLast(head);
			continue;
		case 6:
			cout << "Nhap vi tri can xoa: ";
			cin >> pos;
			deleteMiddle(head, pos);
			continue;
		case 7:
			in(head);
			continue;
		case 8:
			sapxep(head);
			continue;
		}
		
	}

}