线性表--链表--单链表（不带头单向不循环链表）

关于顺序表存在的问题：

1.中间/头部的插?删除，时间复杂度为O(N)
2.增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗
3.增容?般是呈2倍的增长，势必会有一定的空间浪费
要如何解决这些问题？用线性表的链表就能解决

什么是链表？

链表是一种物理存储结构非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，逻辑结构上呈线性。

就如火车车厢之间的关系，可以通过挂钩链接，不用是再断开链接。

?链表的分类

链表含有6种元素，

其中最常见的是不带头单向不循环链表和带头双向循环链表；

这章将介绍单链表（不带头单向不循环链表）及其实现；

单链表

每个个体称之为节点/结点，每个节点即为一个结构体，每个结构体存着数据和指向下一个节点的指针，使之成为一条链；

链式在逻辑上是连续的，在物理结构上不一定连续；节点一般从堆上申请，从堆上申请来的空间，是按照?定策略分配出来的，每次申请的空间可能连续，可能不连续。

单链表的实现

?先创建节点的基本结构，数据类型重定义便于替换；

在单链表基础上实现增删查改的功能。

申请空间，创造节点

?将申请的节点next（下一个指向）先置为NULL，便于后续使用节点。

头插和尾插

尾插：

头插：

?头删和尾删

尾删：

?头删：

?查找

?指定位置之前插入数据

?指定数据之后插入数据

?删除指定位置pos的数据

?

?删除指定位置pos后面的数据

改变链表数据

?销毁链表

打印检验

?单链表代码

//SList.h


#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;      //数据类型，重命名便于改变数据类型

typedef struct SListNode     //单链表节点结构
{
	SLTDataType data;         //数据类型，重命名便于改变数据类型
	struct SListNode* next;  //这里还不能使用SLTNode，顺序问题
}SLTNode;                    //重命名

//创造节点
SLTNode* SLTBuyNode(SLTDataType x);

//检验
void SLTPrint(SLTNode* phead);

//单链表头插/尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//单链表头删/尾删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);

//指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos后面的节点
void SLTEraseAfter(SLTNode* pos);

//改变链表数据
void SLTChange(SLTNode* pos, SLTDataType x);

//销毁链表
void SListDestroy(SLTNode** pphead);

//SList.c


#include "SList.h"


//检验
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;//pcur指向当前节点
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}


//创造节点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("MALLOC FAIL!\n");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}


//单链表头插/尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//链表为空;
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}
	//链表不为空
	//先遍历链表找到尾节点
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	ptail->next = newnode;
}

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//创造节点
	SLTNode* newnode = SLTBuyNode(x);
	//链表为空,创造节点 *pphead == NULL
	//链表不为空
	newnode->next = *pphead;
	*pphead = newnode;
}


//单链表头删/尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	//链表为空，不能删
	assert(*pphead);

	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		(*pphead) = NULL;
		return;
	}
	//多个节点
	//先遍历
	SLTNode* pcur = *pphead;
	while (pcur->next->next)
	{
		pcur = pcur->next;
	}
	//销毁
	free(pcur->next);
	pcur->next = NULL;
}

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	//链表为空，不能删
	assert(*pphead);
	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		(*pphead) = NULL;
		return;
	}
	//多个节点
	SLTNode* temp = *pphead;
	*pphead = (*pphead)->next;//注意优先级*比->小
	free(temp);
	temp = NULL;
}


//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x)
		{
		//	printf("找到了\n");
			return pcur;
		}
		pcur = pcur->next;
	}
	//找不到
//	printf("找不到\n");
	return NULL;
}


//指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	SLTNode* pcur = *pphead;
	//头插(包括了一个或者多个节点的情况)
	if (pos == *pphead)
	{
		newnode->next = pcur;
		*pphead = newnode;
		return;
	}
	//多个节点
	while (pcur->next != pos)
	{
		pcur = pcur->next;
	}
	pcur->next = newnode;
	newnode->next = pos;
}

//指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}


//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);//链表不能为空

	//删除头节点/只有一个节点
	if (pos == *pphead)
	{
		SLTNode* temp = (*pphead)->next;
		free(pos);
	    pos = NULL;
		*pphead = temp;
		return;
	}

	//多个节点
	SLTNode* pcur = *pphead;
	while (pcur->next != pos)
	{
		pcur = pcur->next;
	}
	pcur->next = pos->next;
	free(pos);
	pos = NULL;
}

//删除pos后面的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	//不存在后面的节点
	assert(pos->next);
	//正常情况
	SLTNode* pAfter = pos->next;
	pos->next = pAfter->next;
	free(pAfter);
	pAfter = NULL;
}


//改变链表数据
void SLTChange(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	pos->data = x;
}


//销毁链表
void SListDesTroy(SLTNode** pphead) 
{
	assert(pphead);
	assert(*pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
	pphead = NULL;
}

//Test.h


#include "SList.h"

void test1()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 1);
	SLTPushBack(&plist, 5);
	SLTPushBack(&plist, 6);
	SLTPushBack(&plist, 7);
	SLTPushBack(&plist, 8);
	SLTPrint(plist);
	//SLTInsert(&plist, SLTFind(&plist, 1), 999);
	//SLTInsertAfter(SLTFind(&plist, 8), 888);
	//SLTErase(&plist, SLTFind(&plist, 1));
	//SLTErase(&plist, SLTFind(&plist, 2));
	//SLTErase(&plist, SLTFind(&plist, 3));
	//SLTErase(&plist, SLTFind(&plist, 8));
	//SLTErase(&plist, SLTFind(&plist, 5));
	//SLTErase(&plist, SLTFind(&plist, 6));
	//SLTErase(&plist, SLTFind(&plist, 7));
	//SLTErase(&plist, SLTFind(&plist, 4));
	//SLTEraseAfter(SLTFind(&plist, 1));
	//SLTEraseAfter(SLTFind(&plist, 1));
	//SLTEraseAfter(SLTFind(&plist, 1));
	//SLTEraseAfter(SLTFind(&plist, 1));
	//SLTEraseAfter(SLTFind(&plist, 1));
	//SLTEraseAfter(SLTFind(&plist, 7));
	//SLTEraseAfter(SLTFind(&plist, 1));
	//SLTChange(SLTFind(&plist, 1), 999);
	//SLTChange(SLTFind(&plist, 5), 888);
	//SLTChange(SLTFind(&plist, 8), 777);
	//SListDesTroy(&plist);

	SLTPrint(plist);

}

int main()
{
	test1();


	return 0;
}