#include <iostream>
#include <string> 
using namespace std;

// 定義結構體
typedef struct Node {
	int data;		// 數據域
	Node* next;		// 指針域
}Node, *LinkList; 


// 打印菜單
void printMenu() {
	string temp(10, '-');
	cout << temp + temp + temp << endl;
	cout << "\t單鏈表操作界面\n";
	cout << "\t 1.創建單鏈表\n";
	cout << "\t 2.打印單鏈表\n";
	cout << "\t 3.插入結點(指定位置)\n";
	cout << "\t 4.插入結點(頭插)\n";
	cout << "\t 5.插入結點(尾插)\n";
	cout << "\t 6.刪除結點(指定位置)\n";
	cout << "\t 7.刪除結點(頭刪)\n";
	cout << "\t 8.刪除結點(尾刪)\n";
	cout << "\t 9.統計鏈表長度\n";
	cout << temp + temp + temp << endl;
}

// 初始化鏈表
bool initLinkList(LinkList& L) {
	// 獲取要初始化的長度
	cout << "你要初始化的單鏈表長度:";
	int count;
	cin >> count;

	// 初始化頭結點 頭結點的數據域存放數據個數
	L = new Node;
	L->next = NULL;
	L->data = count;

	// 根據count 插入數據(尾插法)
	Node* p = L;
	Node* temp;
	for (int i = 0; i < count; i++) {
		temp = new Node;
		cout << "請輸入第" + to_string(i+1) + "個數據:";
		cin >> temp->data;
		temp->next = NULL;
		p->next = temp;
		p = p->next;
	}
	return true;
}

// 打印鏈表
bool printLinkList(LinkList& L) {
	// 判斷是否初始化
	if (L == NULL) {
		cout << "未初始化單鏈表"<<endl ;
		return  false;
	}
	
	// 從首元結點往下一一打印數據
	Node* temp = L->next;
	while (temp != NULL) {
		cout << to_string(temp->data) + " -> ";
		temp = temp->next;
	}

	// 補一個NULL
	cout << "NULL" << endl;
	return true;
}

// 指定位置插入(index范圍 1 - n)
bool locationInsert(LinkList& L) {
	// 判斷是否初始化
	if (L == NULL) {
		cout << "未初始化單鏈表" << endl;
		return  false;
	}

	// 獲取要插入的位置 范圍判斷->輸入到對為止
	int index;
	while (true) {
		cout << "輸入要插入的位置(1~n):";
		cin >> index;
		if (index <= L->data + 1 && index >= 1)break;
		cout << "輸入的位置有誤" <<endl;
	};

	// 新建節點 獲取數據存放到數據域
	Node* temp = new Node;
	cout << "輸入要插入的數據:";
	cin >> temp->data;
	
	// p指針向后移動 移動到要插入位置的前一個節點
	Node* p = L;
	for (int i = 1; i < index; i++) {
		p = p->next;
	}

	// 插入操作
	temp->next = p->next;
	p->next = temp;

	// 數據個數+1
	L->data += 1;
	return true;
}

// 頭插
bool headInsert(LinkList& L) {
	// 判斷是否初始化
	if (L == NULL) {
		cout << "未初始化單鏈表" << endl;
		return  false;
	}

	// 新建節點 獲取數據存放到數據域
	Node* temp = new Node;
	cout << "輸入要插入的數據:";
	cin >> temp->data;
	
	// 頭插操作
	temp->next = L->next;
	L->next = temp;

	// 數據個數+1
	L->data += 1;
	return true;
}



// 尾插
bool tailInsert(LinkList& L) {
	// 判斷是否初始化
	if (L == NULL) {
		cout << "未初始化單鏈表" << endl;
		return  false;
	}
	// 新建節點 獲取數據存放到數據域
	Node* temp = new Node;
	cout << "輸入要插入的數據:";
	cin >> temp->data;

	// p指針移動到最后一個節點
	Node* p = L->next;
	while (p->next != NULL){
		p = p->next;
	}

	// 尾插操作
	p->next = temp;
	temp->next = NULL;

	// 數據個數+1
	L->data += 1;
	return true;
}


// 頭刪
bool headDelete(LinkList& L) {
	// 判斷是否有元素
	if (L->data < 1) {
		cout << "單鏈表沒有元素" << endl;
		return  false;
	}

	// 頭刪操作
	if (L->data > 1) {	// 有多個數據節點
		Node* temp = L->next;
		L->next = L->next->next;
		delete temp;
	}else {				// 只有一個首元結點
		delete L->next;
		L->next = NULL;
	}

	// 數據個數-1
	L->data -= 1;
	return true;
}

// 尾刪
bool tailDelete(LinkList& L) {
	// 判斷是否有元素
	if (L->data < 1) {
		cout << "單鏈表沒有元素" << endl;
		return  false;
	}
	
	// 尾刪操作
	if (L->data > 1) {	// 有多個數據節點
		// 移動p指針到尾結點的前一個節點
		Node* p = L;
		for (int i = 0; i < L->data-1 ; i++) {
			p = p->next;
		}
		// 刪除操作
		delete p->next;
		p->next = NULL;
	}else {				// 只有一個首元結點
		delete L->next;
		L->next = NULL;
	}

	// 數據個數-1
	L->data -= 1;
	return true;
}

// 指定位置刪除(index范圍 1 - n)
bool locationDelete(LinkList& L) {
	// 判斷是否有元素
	if (L->data < 1) {
		cout << "單鏈表沒有元素" << endl;
		return  false;
	}
	// 獲取要刪除的位置 范圍判斷->輸入到對為止
	int index;
	while (true) {
		cout << "輸入要刪除的位置(1~n):";
		cin >> index;
		if (index <= L->data && index >= 1)break;
		cout << "輸入的位置有誤" << endl;
	};
	
	if (index == 1) {				// 頭刪
		headDelete(L);
	}else if (index == L->data) {	// 尾刪
		tailDelete(L);
	}else {							// 中間刪
		// 將p指針移動到要刪除節點的前一個節點
		Node* p = L;
		for (int i = 1; i < index; i++) {
			p = p->next;
		}
		// 刪除操作
		Node* temp = p->next;
		p->next = p->next->next;
		delete temp;
		// 數據個數-1
		L->data -= 1;
	}
	return true;
}

// 打印鏈表長度
bool printLength(LinkList& L) {
	// 判斷是否有元素
	if (L == NULL) {
		cout << "未初始化單鏈表" << endl;
		return  false;
	}
	// 打印頭結點的數據
	cout << "鏈表長度為[" + to_string(L->data) + "]" << endl;
	return true;
}

// 程序主入口
int main() {
	bool flag = true;	// 標記
	int option;			// 操作選項 [0 - 9]
	LinkList L = NULL;	// 初始化鏈表指針為NULL
	printMenu();		// 打印菜單
	while (flag) {
		cout << "請操作:";
		cin >> option;
		switch (option) {
			case 1: // 初始化
				initLinkList(L);
				printLinkList(L);
				break;
			case 2: // 打印菜單
				printLinkList(L);
				break;
			case 3:	// 指定位置插入
				locationInsert(L);
				printLinkList(L);
				break;
			case 4:	// 頭插
				headInsert(L);
				printLinkList(L);
				break;
			case 5:	// 尾插
				tailInsert(L);
				printLinkList(L);
				break;
			case 6:	// 指定位置刪除
				locationDelete(L);
				printLinkList(L);
				break;
			case 7:	// 頭刪
				headDelete(L);
				printLinkList(L);
				break;
			case 8:	// 尾刪
				tailDelete(L);
				printLinkList(L);
				break;
			case 9:	// 打印鏈表長度
				printLength(L); 
				printLinkList(L);
				break;
			case 0:	// 退出
				cout << "成功退出程序!" << endl;
				flag = false;
				break;
			default:// 其他情況
				cout << "操作有誤,重新輸入!" << endl;
		}
	}
	return 0;
}