【数据结构】链表

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
SListNode* next为C++中的语法 将其封装成了类
void SListPrint(SLTNode* phead);
void Destory(SLTNode** pphead);
void SListPushFront(SLTNode** pphead, SLTDataType x);
void SListPushBack(SLTNode** pphead, SLTDataType x);
void SListPopBack(SLTNode** pphead);
void SListPopFront(SLTNode** pphead);
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
在pos之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
在pos之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos);
删除pos后面位置
void SListEraseAfter(SLTNode* pos);

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

void Destory(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur != NULL)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void SListPopFront(SLTNode** pphead)
{
	assert(pphead);
	温柔的检查
	if (*pphead == NULL)
	{
		return;
	}
	暴力的检查
	//assert(*pphead != NULL);
	SLTNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);
	del = NULL;
}

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	1.链表是空
	2.链表非空
	链表为空 插入第一个结点 要改变的是SListNode* 用的是结构体指针的指针
	链表不为空 尾插要改变的是结构体SListNode的成员 用的是结构体指针
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void SListPopBack(SLTNode** pphead)
{
	assert(pphead);
	温柔的检查——为空不删
	if (*pphead == NULL)
	{
		return;
	}
	暴力的检查
	//assert(*pphead != NULL);
	1.一个结点 2.多个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		找尾
		SLTNode* prev = NULL;
		/*SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		prev->next == NULL;
		free(tail);
		tail = NULL;*/
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		prev->next = NULL;
		free(tail->next);
		tail->next = NULL;
	}
}

链表中的查找函数可以替代其修改函数
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
			pos不在链表中 pos不在链表中 prev为空还没有找到pos 说明pos传错了
			assert(prev);
		}
		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
			检查pos不是链表中结点 参数传错的情况
			assert(prev);
		}
		prev->next = pos->next;
		free(pos);
		//pos = NULL;此代码并不会改变pos 使用人在main函数将其置空
	}
}

void SListEraseAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* next = pos->next;
		pos->next = next->next;
		free(next);
	}
}
单链表:只适合头插头删——O(1)
任意位置高效插入删除——双向链表
进阶:删除pos位置 要求是O(1) 替换法删除
缺陷:pos不能是尾结点 解决方法:将链表改成循环链表
进阶:在pos位置之前插入 要求是O(1)
方法:在pos位置后创造结点+替换法
newnode = BuySListNode(pos->val); 
pos->val = x;