链表的操作最重要的就是插入和删除，注意两者细节，尤其是while的循环条件

# include <iostream>
using namespace std;

typedef struct LNode {
	int data; //结点的数据域
	struct LNode* next; //结点的指针域
}LNode, * LinkList; //LinkList为指向结构体LNode的指针类型
//typedef: struct LNode == LNode; struct LNode* == LinkList 

//链表的初始化
LinkList InitList() {
	LNode* L = new LNode; //生成新节点作为头结点,用头指针L指向头结点
	L->next = NULL; //头结点的指针域置空
	return L;
}

//创建链表：头插法
void CreateList_H(LinkList& L, int n) {
	//逆位序输入n个元素的值，建立带头结点的单链表L
	L = new LNode;
	L->next = NULL; //先建立一个带头结点的单链表
	for (int i = 0; i < n; i++) {
		LNode* p = new LNode; //生成新结点
		cin >> p->data; //输入元素值赋值给新结点的数据域
		p->next = L->next;
		L->next = p;
	}
}

//创建链表：尾插法
void CreateList_R(LinkList& L, int n) {
	//正位序输入n个元素的值，建立带头节点的单链表L
	L = new LNode;
	L->next = NULL; //先建立一个带头结点的空链表
	LNode* r = L; //尾指针初始时指向头结点
	for (int i = 0; i < n; i++) {
		LNode* p = new LNode; //生成新结点
		cin >> p->data; //输入元素值赋值给新结点的数据域
		p->next = NULL; //p是最后一个结点
		r->next = p;
		r = p;//r指向新的尾结点p
	}
}

//按序号查找结点的值
bool GetElem(LinkList L, int i, int& e) {
//在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素
	LNode* p = L->next; //p指向首元结点
	int j = 1; //j为计数器
	while (p && j < i) { //顺链域向后扫描,直到p指向第i个元素或者扫描完p为空
		p = p->next; //p指向下一个结点
		j++; //计数器j相应加1
	}
	if (!p || j > i) return false; //p为空 或者 i值不合法(例如：i > n 或者 i<= 0)
	e = p->data; //e保存第i个结点的数据域
	return true;
}

//按值查找链表结点
bool LocateElem(LinkList L, int e) {
	//在带头结点的单链表L中查找值为e的元素
	LNode* p = L->next;
	while (p && p->data != e) {//顺链域向后扫描，直到p为空或者p所指结点的数据域等于e
		p = p->next; //p指向下一个结点
	}
	if (!p) return false;
	return true;
}

//单链表的插入
/*
	和顺序表一样，如果表中有n个结点, 则插入操作中的合法位置有n + 1个
	即1<= i <= n+1. 当i = n + 1时，新节点则插在链表尾部
*/
bool InsertList(LinkList& L, int i, int e) {
	//在点头结点的单链表L中第i个位置插入值为e的新结点
	LNode* p = L; //为啥不能是LNode* p = L->next; int j = 1
	int j = 0;
	while (p && j < i - 1) { //查找第i-1个结点，p指向该结点
		p = p->next;
		j++;
	}
	if (!p || j > i - 1) return false; //i值不合法(例如：i > n + 1 或 i < 1）
	LNode* s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

//单链表的删除
/*
	删除算法中的循环条件(p->next && j < i - 1)和插入算法中的循环条件
	(p && j < i - 1)是有所区别的。因为插入操作中合法的插入位置有n+1个，而
	删除操作中删除的合法位置只有n个，如果使用与插入操作相同的循环条件，则
	会出现引入空指针的情况，使删除操作失败。
	插入时p指针最多指向第n个结点,此时判断条件为while(p && j < i - 1)
	删除时p指针最多指向第n-1个结点,此时判断条件为while(p->next && j < i - 1)
*/
bool DeleteList(LinkList& L, int i) {
	//在带头结点的单链表L中，删除第i个位置
	LNode* p = L, * q;
	int j = 0;
	while (p->next && j < i - 1) { //查找第i-1个结点,p指向该结点
		p = p->next;
		j++;
	}
	if (!(p->next) || j > i - 1)return false; //当i>n+1 或者i < 1时，删除位置不合理
	q = p->next; //临时保存被删结点的地址以备释放空间
	p->next = q->next; //改变删除结点前驱结点的指针域
	delete q; //释放被删除结点的空间
	return true;
}

//单链表的遍历输出
void ListPrint(LinkList L) {
	//顺序输出单链表
	LNode* p = L->next;
	while (p) {
		cout << p->data << "\t";
		p = p->next;
	}
	cout << endl;
}

int main() {
	int i, n, e, choose;
	LinkList L = InitList();
	cout << "1. 初始化\n";
	cout << "2. 创建单链表(头插法)\n";
	cout << "3. 创建单链表(尾插法)\n";
	cout << "4. 取值\n";
	cout << "5. 查找\n";
	cout << "6. 插入\n";
	cout << "7. 删除\n";
	cout << "8. 输出\n";
	cout << "0. 退出\n";
	choose = -1;
	while (choose != 0) {
		cout << "请输入数字进行操作: ";
		cin >> choose;
		switch (choose) {
			case 1: //初始化一个空的单链表
				L = InitList();
				if (L) {
					cout << "成功初始化一个空的单链表" << endl;
				}else{
					cout << "初始化一个空的单链表失败" << endl;
				}
				break;
			case 2:// 创建单链表(头插法)
				cout << "请输入想要创建链表元素个数：";
				cin >> n;
				cout << "请依次输入" << n << "个元素:";
				CreateList_H(L, n);
				cout << "头插法创建单链表输出结果：";
				ListPrint(L);
				break;
			case 3:// 创建单链表(尾插法)
				cout << "请输入想要创建链表元素个数：";
				cin >> n;
				cout << "请依次输入" << n << "个元素:";
				CreateList_R(L, n);
				cout << "尾插法创建单链表输出结果：";
				ListPrint(L);
				break;
			case 4: //取值
				cout << "请输入想查找的链表元素序号：";
				cin >> i;
				GetElem(L, i, e);
				cout << "第" << i << "个链表元素的数据域是:" << e << endl;
				break;
			case 5: //查找
				cout << "请输入想查找的链表元素的数据域:";
				cin >> e;
				if (LocateElem(L, e)) {
					cout << "查找成功" << endl;
				}
				else {
					cout << "查找失败" << endl;
				}
				break;
			case 6: //插入
				cout << "请输入插入的位置和数据(用空格隔开)：";
				cin >> i >> e;
				if (InsertList(L, i, e)) {
					cout << "插入成功" << endl;
				}
				else {
					cout << "插入失败" << endl;
				}
				break;
			case 7: //删除
				cout << "请输入删除的位置：";
				cin >> i;
				if (DeleteList(L, i)) {
					cout << "删除成功" << endl;
				}
				else {
					cout << "删除失败" << endl;
				}
				break;
			case 8: //遍历输出单链表
				ListPrint(L);
				break;
			case 0: //退出
				exit(-1);
		}
	}
	return 0;
}