数据结构之单链表-3. 单链表完整代码的实现

SList.h的实现

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int SLDataType;

typedef struct SinglyLinkedList
{
	SLDataType data;
	struct SinglyLinkedList* next;//存储下一个节点的地址
}SList;


//打印单链表
void DisplaySList(SList* phead);

//尾插
void SListPushBack(SList** pphead, SLDataType x);

//尾删
void SListPopBack(SList** pphead);

//头插
void SListPushFront(SList** pphead, SLDataType x);

//头删
void SListPopFront(SList** pphead);

//单链表查找
SList* SListFind(SList* phead, SLDataType x);

//从指定位置之后开始插入数据
void SListInsertAfter(SList** pphead, SList* pos, SLDataType x);

//从指定位置之前插入数据
void SListInsert(SList** pphead, SList* pos, SLDataType x);

//从指定位置删除数据
void SListErase(SList** pphead, SList* pos);

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

SList.c实现

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"

//打印单链表
void DisplaySList(SList* phead)
{
	SList* cur = phead;
	while (NULL != cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//创建新节点
SList* SListBuyNewNode(SList** pphead,SLDataType x)
{
	SList* newnode = (SList*)malloc(sizeof(SList));
	if (NULL == newnode)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//尾插
void SListPushBack(SList** pphead, SLDataType x)
{
	assert(pphead);
	/*SList* newnode = (SList*)malloc(sizeof(SList));
	if (NULL == newnode)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;*/
	SList* newnode = SListBuyNewNode(pphead, x);
	//单链表为空的情况
	if (NULL == *pphead)
	{
		*pphead = newnode;
	}
	else
	{
		SList* tail = *pphead;
		while (NULL != tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
 }

//尾删
void SListPopBack(SList** pphead)
{
	assert(pphead);
	//单链表为空的情况
	assert(*pphead);
	//单链表至少有一个节点
	if (NULL == (*pphead)->next)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SList* tail = *pphead;
		SList* prev = NULL;
		while (NULL != tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		prev->next = NULL;
		free(tail);
		tail = NULL;
	}
}

//头插
void SListPushFront(SList** pphead, SLDataType x)
{
	assert(pphead);
	/*SList* newnode = (SList*)malloc(sizeof(SList));
	if (NULL == newnode)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;*/
	SList* newnode = SListBuyNewNode(pphead, x);
	//至少有一个节点
	/*if (NULL == *pphead)
	{
		*pphead = newnode;
	}
	else
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}*/

	newnode->next = *pphead;
	*pphead = newnode;
}

//头删
void SListPopFront(SList** pphead)
{
	assert(pphead);
	//单链表为空的情况
	assert(*pphead);

	SList* cur = *pphead;
	*pphead = (*pphead)->next;
	free(cur);
	cur = NULL;
}

//单链表查找
SList* SListFind(SList* phead, SLDataType x)
{
	//单链表为空不查找
	assert(phead);

	SList* cur = phead;
	while (NULL != cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//从指定位置之后开始插入数据
void SListInsertAfter(SList** pphead, SList* pos, SLDataType x)
{
	assert(pphead);
	SList* newnode = SListBuyNewNode(pphead, x);
	if (NULL == *pphead)
	{
		*pphead = newnode;
	}
	else
	{
		SList* cur = *pphead;
		while (NULL != cur)
		{
			if (cur == pos)
			{
				newnode->next = cur->next;
				cur->next = newnode;
			}
			cur = cur->next;
		}
	}
}

//从指定位置之前插入数据
void SListInsert(SList** pphead, SList* pos, SLDataType x)
{
	assert(pphead);
	SList* newnode = SListBuyNewNode(pphead, x);
	if (NULL == *pphead)
	{
		*pphead = newnode;
	}
	else
	{
		SList* cur = *pphead;
		SList* prev = NULL;
		while (NULL != cur)
		{
			if (cur == pos)
			{
				newnode->next = prev->next;
				prev->next = newnode;
			}
			prev = cur;
			cur = cur->next;
		}
	}
}

//从指定位置删除数据
void SListErase(SList** pphead, SList* pos)
{
	assert(pphead);
	//单链表为空
	assert(*pphead);

	SList* cur = *pphead;
	while (NULL != cur->next)
	{
		if (cur->next == pos)
		{
			cur->next = pos->next;
			free(pos);
			pos = NULL;
		}
		cur = cur->next;
	}
}

//销毁链表
void SListDestroy(SList** pphead)
{
	assert(pphead);
	SList* cur = *pphead;
	while (NULL != cur)
	{
		SList* prev = cur;
		cur = cur->next;
		free(prev);
		prev = NULL;
	}
	*pphead=NULL;
}

test.c的实现

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"

void TestSList1()
{
	SList* plist = NULL;

	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);

	DisplaySList(plist);

	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);

	DisplaySList(plist);

}

void TestSList2()
{
	SList* plist = NULL;

	SListPushFront(&plist, 10);
	SListPushFront(&plist, 20);
	SListPushFront(&plist, 30);
	SListPushFront(&plist, 40);

	DisplaySList(plist);

	SListPopFront(&plist);

	DisplaySList(plist);

	SList* pos = SListFind(plist, 50);
	if (NULL != pos)
	{
		printf("%d\n", pos->data);
	}
	else
	{
		printf("找不到\n");
	}

}

void TestSList3()
{
	SList* plist = NULL;

	SListInsertAfter(&plist, NULL, 10);

	DisplaySList(plist);

	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);

	SList* pos = SListFind(plist, 4);

	SListInsertAfter(&plist, pos, 20);

	DisplaySList(plist);

	pos = SListFind(plist, 2);

	SListInsert(&plist, pos, 30);

	DisplaySList(plist);

	pos = SListFind(plist, 3);

	SListErase(&plist, pos);

	DisplaySList(plist);

	SListDestroy(&plist);

}

int main()
{
	//TestSList1();

	//TestSList2();

	TestSList3();

	return 0;
}