[数据结构与算法]单向链表的基本操作

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

链表的操作包括增删查改。

test.c

#include "SList.h"
void main()
{

	SListNode* pList = NULL;
	SListPushBack(&pList,1);
	SListPushBack(&pList,2);
	SListPushBack(&pList,3);
	SListPushBack(&pList,4);
	SListPrint(pList);
	SListPopBack(&pList);
	SListPrint(pList);
	SListPopBack(&pList);
	SListPrint(pList);
	SListPopBack(&pList);
	SListPrint(pList);
	SListPopBack(&pList);
	SListPrint(pList);
	SListPopBack(&pList);
	SListPrint(pList);
	SListPushFront(&pList,3);
	SListPushFront(&pList, 3);
	SListPushFront(&pList, 2);
	SListPushFront(&pList, 3);
	SListPrint(pList);
	SListPopFront(&pList);
	SListPrint(pList);
	SListNode* pos = SListFind(pList,3);
	if (pos)
	{
		pos->data = 30;
	}
	SListPrint(pList);
	SListInsertAfter(pList->next, 10);
	SListPrint(pList);
	SListErase(pList->next);
	SListPrint(pList);
	

}

SList.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SListDataType;
typedef struct SListNode
{
	SListDataType data;
	struct SListNode* next;
}SListNode;
void SListPushBack(SListNode** phead,SListDataType x);// 动态申请一个结点
void SListPopBack(SListNode** phead);//单链表尾删
void SListPushFront(SListNode** phead,SListDataType x);//单链表头插
void SListPopFront(SListNode** phead);//单链表头删
void SListPrint(SListNode* phead);//单链表打印
SListNode* BuySListNode(SListDataType x);// 动态申请一个结点
SListNode* SListFind(SListNode* phead, SListDataType x);//单链表查找
void SListInsertAfter(SListNode* pos, SListDataType x);//在pos位置后插入
void SListErase(SListNode* pos);//在pos位置后删除

SList.c

#include "SList.h"
SListNode* BuySListNode(SListDataType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
	{
		printf("申请内存失败");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while(cur != NULL)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("\n");
}
void SListPushBack(SListNode** phead,SListDataType x)
{
	SListNode* newNode = BuySListNode(x);
	if (*phead == NULL)
	{
		*phead = newNode;
	}
	else
	{
		SListNode* tail = *phead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newNode;
	}
}
void SListPopBack(SListNode** phead)
{
	//空链表
	if (*phead == NULL)
	{
		return;
	}
	//一个
	else if ((*phead)->next==NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	//大于1个
	else
	{
		SListNode* tail = *phead;
		SListNode* prev = NULL;
		while (tail->next!=NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}
//单链表查找
void SListPushFront(SListNode** phead, SListDataType x)
{
	SListNode* newNode = BuySListNode(x);
	newNode->next = *phead;
	*phead = newNode;
}
void SListPopFront(SListNode** phead)
{
	if (*phead==NULL)
	{
		return;
	}
	else
	{
		SListNode* next = (*phead)->next;
		free((*phead));
		*phead = next; 
	}
}
SListNode* SListFind(SListNode* phead, SListDataType x)
{
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void SListInsertAfter(SListNode* pos, SListDataType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SListErase(SListNode* pos)
{
	assert(pos);
	if (pos->next)
	{
		SListNode* next = pos->next;
		SListNode* nextnext = next->next;
		pos->next = next->next;
		free(next);
	}
}