Danh sách Liên Kết

#include 
#include 

using namespace std;

struct Node //Xay dung mot Node trong danh sach
{
	int Data; //Du lieu co kieu item
	Node *next; //Truong next la con tro, tro den 1 Node tiep theo
};
typedef Node *List;

void Init(List &L) {
	L = NULL;
}

Node *MakeNode(Node *p, int x) { // tao ra 1 node trong danh sach
	p = (Node *)malloc(sizeof(Node));
	p->next = NULL;
	p->Data = x;
	return p;
}

void Insert_first(List &L, int x)  //Chen x vao vi tri dau tien trong danh sach
{
	Node *k = NULL;
	k = MakeNode(k, x); //tao 1 Node P
	k->next = L; //Cho P tro den L
	L = k; //L tro ve P
}

int Lenght(List L) {
	int dem = 0;
	while (L != NULL)
	{
		L = L->next;
		dem++;

	}
	return dem;
}

void Insert_Last(List &L, int  x) {
	Node *m = NULL;
	m = L;

	if (Lenght(L) == 0)
	{
		Insert_first(L, x);
	}
	else
	{
		while (m->next != NULL) {
			m = m->next;
		}
		Node *p = NULL;
		p = MakeNode(p, x);
		m->next = p;
		p->next = NULL;

	}

}

void Delete_k(List &l, int  k) {
	Node * m = l;
	
	for (int i = 0; i < k - 1; k++) {
		m = m->next;
	}
	m->next = m->next->next;
}
void Delate_last(List &l) {
	Node *m = l;
	while (m->next->next != NULL) {
		m = m->next;
	}
	m->next = NULL;
}
void Insert_K(List &l, int x) {
	int k;
	cin >> k;
	Node *m;
	m = l;
	for (int i = 0; i < k - 1; i++) {
		m = m->next;
	}
	Node *p = NULL;
	p = MakeNode(p, x);
	p->next = m->next;
	m->next = p;
}
void Delete_First(List &l) {
	l = l->next;
}

bool check_empty(List l) {
	if (l == NULL)
	{
		return false;
	}
	else
	{
		return true;
	}
}

int Search_x(List l, int  x) {
	int dem = 0;
	if (!check_empty(l))
	{
		cout << "ham rong khong the tim X";
		return -1;
	}
	else
	{

		while (l != NULL)
		{
			if (x == l->Data)
			{
				return dem;
			}
			dem++;
			l = l->next;
		}
		return -1;
	}
}
void nhap(List &L) {
	int v;
	for (int i = 0; i < 3; i++) {
		cout << "nhap phan tu " << i <<" ";
		cin >> v;
		Insert_Last(L, v);
	}
	cout << endl;
}

void Xuat(List list) {
	while (list != NULL)
	{
		cout << list->Data << endl;
		list = list->next;
	}
}

int main() {
	List l; Init(l);
	int chon;
	
	cout << "1, Nhap" << endl;
	cout << "2, Xuat" << endl;
	cout << "3, Them dau" << endl;
	cout << "4, Them cuoi" << endl;
	cout << "5, Them vi tri K" << endl;
	cout << "6, Xoa dau" << endl;
	cout << "7, Xoa cuoi" << endl;
	cout << "8, Xoa o vi tri K" << endl;
	cout << "9, Tim vi tri cua so  n" << endl;
	
	while (true)
	{
		cout << "------------------------------------------" << endl << endl;
		cout << "Chon :  ";
		cin >> chon;
		cout << "------------------------------------------" << endl << endl;
		switch (chon)
		{
		default:
		case 1: {
			nhap(l);
			break;
		}
		case 2:
		{
			Xuat(l);
			break;
		}case 3: {
			cout << "tu dong nhap 3  vao dau  mang" << endl;
			Insert_first(l, 3);
			break;
		}case 4:
		{
			cout << "tu dong them 4 vao cuoi mang" << endl;
			Insert_Last(l, 4);
			break;
		}case 5: {
			cout << "tu dong them 5 vao vi tri K" << endl;
			Insert_K(l, 5);
			break;
		}case 6: {
			cout << "Xoa vi tri dau tien" << endl;
			Delete_First(l);
			break;
		}case 7: {
			cout << "xoa vi tri cuoi cung" << endl;
			Delate_last(l);
			break;
		}case 8: {
			int k;
			cin >> k;
			cout << "xoa o vi tri thu K";
			Delete_k(l, k);
			break;
		}case 9: {
			int  x;
			cout << "tim X co trong List hay khong ? ";
			cin >> x;
			if (Search_x(l, x) == -1)
			{
				cout << "khong co phan tu trong list" << endl;
			}
			else
			{
				cout << x << " o vi tri thu " << Search_x(l, x)  + 1 << endl;
			}
			break;
		}
		}
	}
	system("pause");
	return  0;
}