【C++单链表实现】

功能如下：

//头插法建立单链表 （链表顺序和输入顺序相反）
LinkList List_HeadInsert(LinkList &L) 

//尾插法建立单链表（输入的顺序即为链表顺序）
LinkList List_TailInsert(LinkList& L)

//遍历此链表
void ShowLinkedList(LinkList &L) 

//按值查找指定节点，返回此节点，未找到返回原链表（以L->next为初始节点）
LinkList FindNode(LinkList &L,ElementType target) 

//按位序查找节点，并返回此节点，未找到返回原链表
LinkList FindBySequence(LinkList &L,ElementType location)
    
//删除指定位序的节点
void DeleteNode(LinkList &L,ElementType position)

//对某一节点进行前插 *** 作
void InsertNode(LinkList& L, ElementType position,ElementType data) 

定义单链表结构体：

//如果单链表存储的值不是int，修改一下下面语句的类型即可
typedef  int ElementType;

typedef struct LNode
{
	ElementType data;

	//此处不能用LNode *next,原因是在结构体建立没完成时，还没有LNode类型的结构体，编译器不认识它（和typedef有关）
	struct LNode *next;

}LNode,*LinkList;

//此处定义一个节点有两种方法了.如下：
//1. LNode *p;
//2. LinkList p;

头插法和尾插法：

//头插法建立单链表 （链表顺序和输入顺序相反）
LinkList List_HeadInsert(LinkList &L) {

	/*初始化链表L*/
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;

	/*创建临时节点*/
	LNode *temp;

	/*节点数据*/
	int outTag;

	//输入节点数据以及判断退出标志（ElementType类型）
	cout<<"请输入添加节点的数据，停止添加请键入999：" << endl;
	cin >> outTag;

	while (outTag !=999)
	{
		/*给临时节点分配空间以及数据*/
		temp = (LinkList)malloc(sizeof(LNode));
		temp->data = outTag;

		/*头插法添加节点*/
		temp->next = L->next;
		L->next = temp;

		/*决定退出还是继续输入添加节点*/
		cin >> outTag;
	}
	return L;
}

//尾插法建立单链表（输入的顺序即为链表顺序）
LinkList List_TailInsert(LinkList& L) {

	/*初始化链表L*/
	L = (LinkList)malloc(sizeof(LNode));

	/*定义临时指针和尾指针*/
	LinkList temp,rear=L;
	int outTag;

	//输入节点数据以及判断退出标志（ElementType类型）
	cout << "请输入添加节点的数据，停止添加请键入999：" << endl;
	cin >> outTag;

	while (outTag != 999)
	{
		temp = (LinkList)malloc(sizeof(LNode));
		temp->data = outTag;

		/*尾插法添加节点*/
		rear->next = temp;
		rear=temp;

		cin >> outTag;
	}
	/*置尾结点指向NULL*/
	rear->next = NULL;

	return L;
}

说明：头插法和尾插法实现方法不唯一，还可以通过先指定插入的次数，用for循环遍历。

按值查找和按位序查找：

//按值查找指定节点，返回此节点，未找到返回原链表（以L->next为初始节点）
LinkList FindNode(LinkList &L,ElementType target) {

	/*第一个节点指针赋给P*/
	LinkList P = L->next;

	if (P == NULL) {
		cout <<"链表为空"<< endl;
		return L;
	}

	/*位置，是否找到标志*/
	int position = 1;
	bool isFund = false;

	/*遍历该链表，直到找到匹配元素*/
	while (P != NULL)
	{
		if (P->data != target)
		{
			position++;
			P = P->next;
		}
		else 
		{
			isFund = true;
			break;
		}
			
	}

	if (!isFund) 
	{
		cout <<"查找说明：" << "该元素不存在" << endl;
		return L;
	}
	else 
		return P;

}

//按位序查找节点，并返回此节点，未找到返回原链表
LinkList FindBySequence(LinkList &L,ElementType location) {

	LinkList P = L->next;
	if (P==NULL)
	{
		cout <<"查找说明：" << "链表为空" << endl;
		return L;
	}

	int tag = 1;
	while (tag!=location)
	{
		P = P->next;
		tag++;
	}

	if (P == NULL) 
	{
		cout <<"查找说明：" << "链表中并不存在位序为" << location << "的节点" << endl;
		return L;
	}
	else 
		return P;
}

说明：代码方法不唯一

遍历单链表：

//遍历此链表
void ShowLinkedList(LinkList &L) {

	/*第一个节点指针赋值给P*/
	LinkList P = L->next;

	if (P == NULL)
	{
		cout <<"遍历说明：" << "链表为空表" << endl;
		return;
	}
	else 
	{
		cout <<"遍历说明：" << "链表如下：" << endl;
		while (P != NULL)
		{
			cout << P->data << " , ";
			P = P->next;
		}
		cout << endl;
	}
	cout << endl;
}

删除指定位序的节点：

//删除指定位序的节点
void	DeleteNode(LinkList &L,ElementType position) {
	cout << "执行删除 *** 作---------------------------------" <<"对"<<position <<"进行删除" << endl;

	if (position==1)
	{
		/*
		*position为1，说明删除的是起始节点，他没有前驱节点，单独进行 *** 作（这里第一个节点默认为L->next）
		*/
		L->next = L->next->next;
		return;
	}

	/*要删除的节点*/
	LinkList current = FindBySequence(L, position);

	/*找到要删除节点的前驱节点*/
	LinkList prior = FindBySequence(L, position - 1);

	/*删除current节点*/
	prior->next = current->next;
	free(current);
}

可以删去相邻接点，然后把删去节点的值给当前节点也可以达到目的,此处不再演示

对某一节点进行前插 *** 作：

//对某一节点进行前插 *** 作
void InsertNode(LinkList& L, ElementType position,ElementType data) {
	cout << "前插 *** 作-----------------------------------"<<"对"<<position<<"位置前进行插入" <<data << endl;

	/*1.找到要插入的节点的前驱节点*/
	LinkList prior = FindBySequence(L, position-1);

	/*新建要插入的节点*/
	LinkList Temp = (LinkList)malloc(sizeof(LNode));
	Temp->data = data;

	/*进行前插 *** 作*/
	Temp->next = prior->next;
	prior->next = Temp;
}

说明：可以在指定节点的后继节点新增节点，把指定节点和新增节点的值对调同样可以实现

演示如下：

void L_m() {

	//创建链表
	LinkList  k; 

	/*尾插法建立链表*/
	k = List_TailInsert(k);

	/*遍历此链表*/
	ShowLinkedList(k);

	/*插入节点*/
	//此处插入的值为999，但尾插法结束的标志也是999，两者互不影响
	InsertNode(k, 3,999);
	ShowLinkedList(k);

	/*删除节点*/
	DeleteNode(k,3);
	ShowLinkedList(k);

}

效果如下：

说明：将所有代码置于同一cpp文件下即可执行。