【数据结构初阶】单链表的实现

//动态申请的内存是在堆空间上申请的
typedef int SLTDateType;

typedef struct SListNode//单链表结点
{
	SLTDateType data;
	struct SListNode* next;
}SLTNode;

void SListPrint(SLTNode* phead)
{
	
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	//这里一定要注意一点：在对结构体成员进行访问的时候，我们有两种方式，一种是结构体变量+点操作符，另一种是结构体变量指针->
	//这里要和指针区分开来，我们对结构体进行访问的时候，用的是成员选择操作符，对指针进行访问时，用的是解引用操作符
	//千万不要搞混了，分清成员选择和解引用这两种操作符

	printf("NULL\n");//每打印完一次链表我们就换一个行&&如果链表是空，正好我们打印NULL
}

SLTNode* BuyListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//1MB = 1024KB = 1024 * 1024 Byte
	//linux下栈有8MB,也就800多万字节，堆的字节数一般能上亿
	//32位系统，堆都有2G，大概是20几亿字节
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);//return结束的是当前这个函数，而exit终止的是整个程序
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

void SListPushBack(SLTNode** pphead, SLTDateType x)
{
	创造一个新结点,在堆区上开辟一个大小为结点大小的动态空间
	//SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	注意我们malloc函数的返回值是开辟的空间的首地址，所以我们得用指针去接收
	//newnode->data = x;
	//newnode->next = NULL;
	//if (phead == NULL)
	//{
	//	phead = newnode;	
	//}
	//else
	//{
	//	//找到尾节点
	//	SLTNode* tail = phead;
	//	while (tail->next != NULL)
	//	//这里tail是空地址，我们通过空指针去进行成员访问，这就会引发了异常: 读取访问权限冲突。因为tail是nullptr。
	//	{
	//		tail = tail->next;
	//	}
	//	//最后一步，将我们的新结点链接到这个单链表上去
	//	tail->next = newnode;
	//}
	

	//上面的代码我们看起来其实是没有什么问题的，但为什么程序运行结果什么都没有呢？
	//这其实也就引出了一个问题，我们对形参phead进行的改变，没有影响实参plist
	 
	 
	//创造一个新结点,在堆区上开辟一个大小为结点大小的动态空间
	/*SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));*/
	//注意我们malloc函数的返回值是开辟的空间的首地址，所以我们得用指针去接收
	/*newnode->data = x;
	newnode->next = NULL;*/

	assert(pphead);
	SLTNode* newnode = BuyListNode(x);//我们SListPushBack会接收一个参数x，我们这里把参数x传给创造结点的函数BuyListNode
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找到尾节点
		SLTNode* tail = *pphead;//要注意*pphead==phead==plist
		while (tail->next != NULL)
			//这里tail是空地址，我们通过空指针去进行成员访问，这就会引发了异常: 读取访问权限冲突。因为tail是nullptr。
		{
			tail = tail->next;
		}
		//最后一步，将我们的新结点链接到这个单链表上去
		tail->next = newnode;
	}
}

void SListPopBack(SLTNode** pphead)
{
	//正确写法
	assert(*pphead);//1.零个结点
	//2.一个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;//将plist置为NULL
	}
	else
	{
		//3.两个及两个以上的结点
		SLTNode* tail = *pphead;
		SLTNode* prev = NULL;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;

		prev->next = NULL;//一个结点就会出问题（对空指针指向的位置进行了访问）

		//或者这样写也可以
		//SLTNode* tail = *pphead;
		//while (tail->next->next != NULL)//一个结点就会出问题（对空指针指向的位置进行了访问）
		//{
		//	tail = tail->next;
		//}
		//free(tail->next);
		//tail->next = NULL;

	}


	/*SLTNode* tail = *pphead;
	SLTNode* prev = NULL;*///前驱指针,让我们的tail总是在prev的前面，让prev指向tail后边的结点
	//定义这个变量的原因就是，我们的tail在不断更新他指向的结点时，没人记得尾结点前面的结点了，
	//然而我们还需要让尾结点前面的结点中的next置空呢，但现在没人记得他了，所以我们需要一个prev指针
	//来替我们记住这倒数第二个的结点
	/*while (tail->next != NULL)
	{
		prev = tail;
		tail = tail->next;
	}
	free(tail);
	tail = NULL;*/

	/*prev->next = NULL;*///只有一个结点的时候，我们的prev是NULL，对NULL进行访问那就是非法访问
	//这样的代码会导致经典的野指针问题出现
	//我们将tail所在空间释放掉之后，相当于前一个结点中的next所指向的空间被释放掉，这就导致了野指针的出现

	//那么我们在SListPrint里面打印的时候，就会进行非法访问因为倒数第二个结点中的next指向的是一个被释放的空间


	//另一种写法
	/*SLTNode* tail = *pphead;
	while (tail->next->next!=NULL)
	{
		tail = tail->next;
	}
	free(tail->next);
	tail->next = NULL;*/

	//值得注意的是这两种写法状态下，程序都崩了
	//当我们删一个结点的时候，这样的写法是有问题的
}

void SListPushFront(SLTNode** pphead, SLTDateType x)//头插还是比较简单的，几句代码就搞定了
{
	assert(pphead);
//不要给这个函数传一个空指针过来，防止有些同学在写代码过程中不小心传了个空指针过来，这样我们就可以通过断言检查出我们传参
//出现了问题，帮助我们快速排查出问题
	SLTNode* newnode = BuyListNode(x);//将结点中的data改成我们预期值x
	newnode->next = *pphead;
	//如果链表刚开始是空链表的话，这里解引用只是找到了那个空指针，并没有对空指针解引用，所以是没问题的
	//将结点中的next改成我们的plist，因为plist是原链表的第一个结点的地址，我们把这个地址重新给到我们新开辟的结点中的next里
	*pphead = newnode;
	//我们重新将plist变为链表首结点的地址，首结点地址其实就是newnode
}

void SListPopFront(SLTNode** pphead)
{
	//assert(pphead);
	//如果只有一个结点的话，我们将第一个结点所在空间free掉之后，再将plist的指向改为空指针，以防别人用错plist
	//如果有两个及两个以上的结点的话，我们先释放掉plist的空间，因为plist现在指向的是第一个结点的空间
	//然后将plist的指向改为第一个结点中的next，这样我们的第一个结点就没有了
	//如果没有结点我们就将其进行断言处理，粗暴解决结点为0的情况
	assert(*pphead);
	
	SLTNode* next = (*pphead)->next;//->的运算符优先级要高于*解引用操作符的优先级
	free(*pphead);
	*pphead = next;
	//一个结点和多个结点的情况是一样的，这3条代码都可解决
}

SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
	assert(phead);
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	//如果没有找到，返回NULL
	return NULL;
}

//在pos的后面插入，这个更适合，也更简单
void SListInsertAfter(SLTNode*pos,SLTDateType x)//如果在pos位置的后面插入结点的话，我们根本不需要传头结点过来，只要有pos就可以
{
	assert(pos);//你在空结点后面插入，疯了？
	SLTNode* newnode = BuyListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	
	if (*pphead == pos)
	{
		SLTNode* newnode = BuyListNode(x);
		newnode->next = *pphead;//newnode中的next指向的是刚刚的头结点地址，也就是*pphead
		*pphead = newnode;//让头结点变成newnode
	}
	else
	{
		//我们需要在pos位置的前面先插入一个结点
		SLTNode* newnode = BuyListNode(x);//创造结点的函数只需要一个data的参数和结点地址的返回类型
		//找到pos的前一个位置
		SLTNode* posprev = *pphead;
		while (posprev->next != pos)
		{
			posprev = posprev->next;
		}
		//找到前一个位置之后，将新结点放入链表当中
		posprev->next = newnode;
		newnode->next = pos;
	}
	

}

if (*pphead==pos)
//将这里的判断条件改为pos和头结点地址是否相等的话，链表只有一个结点和为空这两种情况在一个if语句里都可以解决
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}

void SListErase(SLTNode** pphead, SLTNode* pos)//O(N)的算法
{
	assert(pphead);
	//如果要删中间和尾部的话，我们让pos的前一个结点next指向pos的下一个结点就好了，
	//但是要删头部的话，我们找不到pos的前一个结点了，所以这里要有一个分支结构
	if (*pphead == pos)
	{
		//删除头结点
		*pphead = pos->next;
		free(pos);//将头节点的空间内容给释放掉
		
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;//这句代码其实是没有意义的，因为你的pos只是外面实际pos结点地址的一个临时拷贝，修改形参并不会影响实参
		//但这句代码也可以体现出我们良好写代码的习惯
	}

	//所以我们的STL是实现SListEraseAfter,删除后面的结点的话就比较省事了

}
void SListEraseAfter(SLTNode* pos)
{
	assert(pos->next);//删空干毛线啊！	
	pos->next = pos->next->next;
	free(pos->next);
	pos->next = NULL;//置空不置空也是没有意义的
}

void SListDestroy(SLTNode** pphead)
{
	assert(pphead);
	
	while (*pphead)
	{
		SLTNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}

#define _CRT_SRCURE_NO_WARNINGS 1
#pragma  warning (disable:4996) 

#include "SList.h"

void TestList1()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
}
void TestList2()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPrint(plist);

	SLTNode* pos = SListFind(plist, 4);
	int i = 1;
	while (pos)
	{
		
		printf("第%d个结点:%p->%d\n", i++, pos, pos->data);
		pos->data = 40;
		pos = SListFind(pos->next, 4);//从pos后面的那个结点开始查找还有没有我目标的data的结点了
	}
	//我们既然能够找到，其实Find的另一个功能就是修改
	//我们现在把4修改为40
	SListPrint(plist);
	//我们现在在40的前面插入一个100
	pos = SListFind(plist, 40);
	SListInsert(&plist, pos, 100);
	pos = SListFind(pos->next, 40);
	SListInsert(&plist, pos, 100);
	SListPrint(plist);
}
void TestList3()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPrint(plist);

	SLTNode* pos = SListFind(plist, 3);
	SListEraseAfter(pos);
	SListErase(&plist, pos);
	SListPrint(plist);

	SListDestroy(&plist);

}
int main()
{
	TestList1();//测试过后,我们的头插，头删，尾插，尾删这些接口的功能就没有问题了
	//TestList2();//测试过后，我们的查找，任意位置插入，任意位置之后插入这些接口也没有问题了
	//TestList3();//测试过后，我们最后的任意位置删除元素接口也实现其功能了，到此我们的单链表也实现完了。
	return 0;
}