单链表的基本操作，包括头插法、 尾插法、求表长、判断空、输出表元素、按位置查找结点值、按值查找表结点、 插入结点、 删除结点、销毁链表等。

注：仅供参考，有错误欢迎留言指出！

/*
*	带头结点的单链表的基本操作
*	By Lalmon
*	09/18/2019
**/

#include<iostream>
using namespace std;

typedef struct LNode
{
	int data;	//数据域
	struct LNode* next;	//指针域
}LNode,*LinkList;

//头插法
LinkList List_HeadInsert(LinkList& L)
{
	LNode* s;
	int x;	//插入的值
	L = (LinkList)malloc(sizeof(LNode));	//创建头结点
	L->next = NULL;	//初始为空链表
	cin >> x;
	while (x<=5)
	{
		s = (LNode*)malloc(sizeof(LNode));	//创建新结点
		s->data = x;	//数据赋值
		s->next = L->next;	//顺序不能乱。先是让插入的节点的next指向头结点的next（保护了头结点next）
		L->next = s;	//再让头结点的next指向插入的结点，完成插入

		cin >> x;
	}
	return L;
}

//尾插法
LinkList List_TailInsert(LinkList& L)
{
	int x;	//设元素类型为整形
	L = (LinkList)malloc(sizeof(LNode));
	
	LNode* s, * r = L;	//r为表尾指针
	cin>>x;	//输入结点的值
	while (x!=5)
	{
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;	//r指向新的表尾结点
		cin>>x;
	}
	r->next = NULL;
	return L;
}

//输出每个结点数据
void getItem(LinkList L)
{
	//带头结点链表
	LinkList h = new LNode;
	h = L->next;
	while (h)
	{
		cout << h->data << " ";
		h = h->next;
	}
	cout << endl;
}

//按序号查找结点值（返回一个对象）
LinkList getElem(LinkList L, int i)
{
	//首先对i的范围进行判断
	int j = 1;	//j从1开始，记录位置
	LinkList p = L->next;	//从头结点开始
	if (i==0)
	{
		return L;	//i=0,返回头结点
	}
	if (i<1)
	{
		return NULL;	//若i无效，则返回NULL
	}
	while (p!=NULL && j<i)
	{
		p = p->next;
		j++;
	}
	return p;	//要是循环提前结束，则返回p；要是循环没找到，正常结束，则p肯定为NULL，也直接返回
}

//按值查找（返回对象）
LinkList LocateElem(LinkList L, int e)
{
	LinkList p = L->next;	//从头结点开始
	while (p!=NULL && p->data!=e)
	{
		p = p->next;
	}
	return p;
}

//在第i个位置插入一个结点，值为e
LinkList ListInsert(LinkList& L, int i,int e)
{
	LinkList p, s;
	p = getElem(L, i - 1);	//找到第i-1个位置，看是否存在

	if (p==NULL)
	{
		cout << "Insert fale!" << endl;
	}
	else
	{
		s = (LinkList)malloc(sizeof(LNode));
		s->data = e;
		s->next = p->next;
		p->next = s;
		return p;
	}
}

//删除第i个结点
LinkList DeleteElem(LinkList& L, int i)
{
	LinkList p ,q;
	p = getElem(L, i -1);
	if (p==NULL)
	{
		cout << "Delete fale!" << endl;
	}
	else
	{
		//先用q记录下p->next，然后更换指向，最后释放q结点的内存
		q = p->next;
		p->next = q->next;
		free(q);	
		return p;
	}
}

//返回表长
int ListLength(LinkList L)
{
	int i = 0;
	LinkList p = L->next;
	while (p!=NULL)
	{
		i++;
		p = p->next;
	}
	return i;
}

//判断表空
bool IsEmpty(LinkList L)
{
	LinkList p = L->next;
	if (p!=NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//摧毁链表
LinkList DestroyList(LinkList& L)
{
	/*
	*	区别摧毁和清空操作：
	*		清空是指保留头指针，但是链表依旧存在
	*		摧毁是把头结点一并摧毁
	*/
	LinkList p=(LinkList)malloc(sizeof(LNode));
	while (L!=NULL)
	{
		p = L->next;
		free(L);
		L = p;
	}
	return p;
}

int main()
{
	/*
	*	具体输入的结点个数请在两个插入函数中进行修改
	*	所有函数均经过测试
	**/
	LinkList L = (LinkList)malloc(sizeof(LNode));
	//List_HeadInsert(L);	//头插法
	//getItem(L);	
	//IsEmpty(L);	//判表空
	List_TailInsert(L);	//尾插法
	getItem(L);
	//cout << getElem(L, 2)->data << endl;	//按序号查找结点值
	//cout<< LocateElem(L,2)->data <<endl;	按值查找
	ListInsert(L, 2, 0);	//在第2个位置插入0
	getItem(L);
	DeleteElem(L,2);	//删除第2个位置的结点
	getItem(L);
	cout << "表长： " << ListLength(L) << endl;
	DestroyList(L);	//摧毁链表
}