单链表及其所有操作（无哨兵位）

目录

一、单链表结构的定义

二、单链表结点的创建

三、单链表打印

四、单链表尾插

五、单链表头插

六、单链表尾删

七、单链表头删

九、单链表任意位置插入

十、单链表任意位置删除

十一、单链表任意位置后插入

十二、单链表任意位置后删除

十三、单链表任意位置插入（不提供链表头结点）

---

一、单链表结构的定义

//单链表结构的定义
typedef int SLNDataType;//数据类型
 
typedef struct SListNode {
	SLNDataType val;//结点数据域
	struct SListNode* next;//结点指针域
}SLNode;

二、单链表结点的创建

//单链表结点的创建
SLNode* CreateNode(SLNDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));//为新结点申请空间
	if (newnode == NULL)//申请失败
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;//新结点数据域
	newnode->next = NULL;//新结点指针域
	return newnode;
}

三、单链表打印

//单链表的打印
void SLTPrint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	if (cur == NULL)
		printf("NULL\n");
}

四、单链表尾插

//单链表的尾插
void SLTPushBack(SLNode** pphead, SLNDataType x)
{
    assert(pphead);
	SLNode* newnode = CreateNode(x);
	//链表为空
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else//链表不为空
	{
		SLNode* tail = *pphead;
		while (tail->next)//找尾结点
		{
			tail = tail->next;
		}
		tail->next = newnode;//尾插
	}
}

五、单链表头插

//单链表头插
void SLTPushFront(SLNode** pphead, SLNDataType x)
{
    assert(pphead);
	SLNode* newnode = CreateNode(x);
 
	newnode->next = *pphead;
	*pphead = newnode;
 
    //SLNode* newnode = CreateNode(x);
	链表为空
	//if (*pphead == NULL)
	//{
	//	*pphead = newnode;
	//}
	//else//链表不为空
	//{
	//	SLNode* tmp = *pphead;
	//	*pphead = newnode;
	//	(*pphead)->next = tmp;
	//}
}

六、单链表尾删

//单链表尾删
void SLTPopBack(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);//链表不能为空
	
	if ((*pphead)->next == NULL)//链表只有一个结点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//链表有多个结点
	{
		SLNode* tail = *pphead;
		SLNode* prev = NULL;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		prev->next = NULL;
		free(tail);
		tail = NULL;
	}
}

七、单链表头删

//单链表头删
void SLTPopFront(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	//SLNode* tmp = *pphead;
	//*pphead = (*pphead)->next;
	//free(tmp);
	//tmp = NULL;
	SLNode* tmp = (*pphead)->next;
	free(*pphead);
	*pphead = tmp;
}

八、单链表查找（返回找到的结点）

//单链表查找（返回找到的结点）
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{
	if (phead == NULL)
		return NULL;
	else
	{
		SLNode* cur = phead;
		while (cur)
		{
			if (cur->val == x)
				return cur;
			cur = cur->next;
		}
		return cur;//return NULL;
	}
}

九、单链表任意位置插入

//单链表任意位置插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
	assert(pphead);
	assert(pos);//必须在有效结点处插入
	assert(*pphead);//如果pos是有效结点，那么链表一定不为空
 
	SLNode* newnode = CreateNode(x);
	if (*pphead == pos)//插入位置在头结点处
	{
		//头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SLNode* cur = *pphead;
		while (cur->next != pos)//找插入位置的前一结点
		{
			cur = cur->next;
		}
		newnode->next = cur->next;
		cur->next = newnode;
	}
}

十、单链表任意位置删除

//单链表任意位置删除
void SLTErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(pos);//删除的必须是有效结点
	assert(*pphead);//链表不能为空
 
	if (*pphead == pos)//删除的结点是头结点
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		SLNode* cur = *pphead;
 
		while (cur->next != pos)//找删除结点的前一结点
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

十一、单链表任意位置后插入

//单链表任意位置后插入
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{
	assert(pos);//必须是有效结点
 
	SLNode* newnode = CreateNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

十二、单链表任意位置后删除

//单链表任意位置后删除
void SLTEraseAfter(SLNode* pos)
{
	assert(pos);//必须是有效结点
	assert(pos->next);//如果pos是最后一个结点，那么pos的后一位置为空
 
	SLNode* tmp = pos->next;
	pos->next = tmp->next;
	free(tmp);
	tmp = NULL;
}

十三、单链表任意位置插入（不提供链表头结点）

先进行任意位置后插入，再交换两个结点的值

//单链表任意位置插入（不提供链表头结点）
void SLTInsertNohead(SLNode* pos, SLNDataType x)
{
	assert(pos);
 
	SLTInsertAfter(pos, x);//先在pos位置后插入
 
	pos->next->val = pos->val;
	pos->val = x;
}