数据结构—＞单链表_代码007(未授权)

本文介绍: 链表是一种物理结构(储存结构)上不一定连续，不一定是顺序的存储结构，数据元素是通过链表中的指针链接次序实现的。

链表是一种物理结构(储存结构)上不一定连续，不一定是顺序的存储结构，数据元素是通过链表中的指针链接次序实现的

链表有很多种类两两匹配就一共有八种这里主要介绍一下单链表(单向不带头不循环)

图示：

链表中的结点一般都是在堆上申请的，从堆上申请的空间，按照一定的规则申请的，两次申请的空间也能相同也可能不相同。用一个指针就能找到下一个结点的空间地址了，从而形成线性关系

typedef int ElemType;
typedef struct SListNode
{
	ElemType data;
	struct SListNode* next;
}SLTNode;

typedef SLTNode* LinkList;//定义链表

定义一个数据域和指针域。数据域用来存放数据，指针域的指针指向下一个结点的空间地址

//创建新结点
SLTNode* NewSLTNode(ElemType x);
//尾插
void SLTPushBack(SLTNode** phead, ElemType x);
//头插
void SLTPushFront(SLTNode** phead, ElemType x);
//尾删
void SLTPopBack(SLTNode** phead);
//头删
void SLTPopFront(SLTNode** phead);
//单链表查找
SLTNode* SLTNodeFind(SLTNode* phead, ElemType x);
//在pos之前插入
void SLTInsert(SLTNode** phead, SLTNode* pos, ElemType x);
//在pos之后插入
void SLTInsertAfter(SLTNode* pos, ElemType x);
//删除pos位置
void SLTErase(SLTNode** phead, SLTNode* pos);
//删除pos位置后得
void SLTEraseAfter(SLTNode* pos);
//打印
void SLTNodePrintf(SLTNode* ps);

void SLTPushBack(SLTNode** phead, ElemType x)
{
	//申请结点
	SLTNode* newnode = NewSLTNode(x);
	//空链表
	if (*phead == NULL)
	{
		*phead = newnode;
	}
	//有一个以上的结点
	else
	{
		SLTNode* tail = *phead;
		//遍历找最后一个结点
		while (tail-&gt;next != NULL)
		{
			tail = tail-&gt;next;
		}
		//连接新结点
		tail-&gt;next = newnode;
	}
}

SLTNode* NewSLTNode(ElemType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if(newnode == NULL)
	{
		perror("malloc fail");
		eixt(-1);
	}
	newnode-&gt;data = x;
	newnode->next = NULL;
	return newnode;
}

void SLTPushFront(SLTNode** phead, ElemType x)
{
	//申请结点
	SLTNode* newnode = NewSLTNode(x);
	//空和非空链表都可处理
	newnode->next = *phead;
	*phead = newnode;
}

void SLTPopBack(SLTNode** phead)
{
	//空链表
	assert(*phead);
	//只有一个结点
	if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	//有两个结点以上的链表
	else
	{
		SLTNode* tail = *phead;
		SLTNode* tailprev = NULL;//记录最后一个的前一个
		while (tail->next != NULL)
		{
			tailprev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		tailprev->next = NULL;
	}
}

void SLTPopFront(SLTNode** phead)
{
	//空
	assert(*phead);
	//一个和多个结点处理逻辑一样
	SLTNode* newhead = (*phead)->next;
	free(*phead);
	*phead = newhead;
}

SLTNode* SLTNodeFind(SLTNode* phead, ElemType x)
{
	assert(phead);
	SLTNode* pos = phead;
	while (pos)
	{
		if (pos->data == x)
		{
			return pos;
		}
		pos = pos->next;
	}
	//没有该元素
	return NULL;
}

void SLTInsert(SLTNode** phead, SLTNode* pos, ElemType x)
{
	assert(*phead);
	assert(pos);
	
	if (pos == *phead)
	{
		SLTPushFront(phead, x);
	}
	else
	{
		//申请结点
		SLTNode* newnode = NewSLTNode(x);
		//找pos的前一个
		SLTNode* cur = *phead;
		SLTNode* posprev = NULL;
		while (cur != pos)
		{
			posprev = cur;
			cur = cur->next;
		}
		posprev->next = newnode;
		newnode->next = pos;
	}
}

void SLTInsertAfter( SLTNode* pos, ElemType x)
{
	assert(pos);
	//申请新结点
	SLTNode* newnode = NewSLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SLTErase(SLTNode** phead, SLTNode* pos)
{
       //空链表
	assert(*phead);
	// 指定位置不存在
	assert(pos); 
	//复用头删
	if (pos == *phead)
	{
		SLTPopFront(phead);
	}
	else
	{
		//找pos前一个
		SLTNode* cur = *phead;
		SLTNode* prevpos = NULL;
		while (cur != pos)
		{
			prevpos = cur;
			cur = cur->next;
		}
		prevpos->next = pos->next;
		free(pos);
	}
}

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* posnesxt = pos->next;
	pos->next = posnesxt->next;
	free(posnesxt);
	posnesxt = NULL;
}

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

void SLTNodeDestory(SLTNode** phead)
{
	assert(*phead);
	SLTNode* cur = *phead;
	SLTNode* curnext = NULL;
	while (cur != NULL)
	{
		curnext = cur->next;
		free(cur);
		cur = curnext;
	}
}

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，物理上不一定连续
随机访问	O(1)	O(n)
任意位置插入或删除	可能需要挪动数据，效率太低O(n)	只需要修改指针指向即可
插入元素	动态顺序表，空间不够时需要扩容	没有容量概念，用多少申请多少
应用场景	元素高效存储+频繁访问	频繁在任意位置插入和删除