不带头结点的单链表

slist.h

#pragma once


typedef int SLDataType;
typedef struct SListNode
{
	struct SListNode* _pNext;   //next域
	SLDataType _data;           //数字域
}SListNode;


////////不带头节点的单链表 /////////////////
//
//链表初始化
void SListInit(SListNode** pHead);

//创建新结点
SListNode* SListNewNode(SLDataType data);

//打印链表
void SListPrint(SListNode* pHead);

//尾插
void SListPushBack(SListNode** pHead, SLDataType data);

//尾删
void SListPopBack(SListNode** pHead);

//头插
void SListPushFront(SListNode** pHead, SLDataType data);

//头删
void SListPopFront(SListNode** pHead);

//查找
SListNode* SListFind(SListNode** pHead, SLDataType data);

//任意位置插入
void SListInsert(SListNode** pHead, SListNode* pos, SLDataType data);

//任意位置删除
void SListErase(SListNode** pHead, SListNode* pos);

//销毁单链表
void SListDestroy(SListNode** pHead);

//链表大小
int SListSize(SListNode* pHead);

//判空
int SListEmpty(SListNode* pHead);

//首节点
SLDataType Front(SListNode* pHead);

//末节点
SLDataType Back(SListNode* pHead);

//删除第一个值为data的结点
void SListRemove(SListNode** pHead, SLDataType data);

//删除值为data的所有节点
void SListRemoveAll(SListNode** pHead, SLDataType data);

//冒泡排序
void SlistBubbleSort(SListNode** pHead);

slist.c

#include"Slist.h"
#include<assert.h>
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>



//初始化
void SListInit(SListNode** pHead){
	assert(pHead);
	*pHead = NULL;
}

//创建新结点
SListNode* SListNewNode(SLDataType data){
	SListNode* _pNew = (SListNode*)malloc(sizeof(SListNode));
	if (_pNew == NULL){
		exit(0);
	}
	else{
		_pNew->_data = data;
		_pNew->_pNext = NULL;
		return _pNew;
	}
}

//打印链表
void SListPrint(SListNode* pHead){
	SListNode* pCur = pHead;
	for (pCur; pCur != NULL; pCur = pCur->_pNext)
	{
		printf("%d--->", pCur->_data);
	}
	printf("NULL\n");
}


//尾插
void SListPushBack(SListNode** pHead, SLDataType data){
	assert(pHead);
	SListNode* NewNode = SListNewNode(data);
	//如果链表为空，则直接让头指针指向新申请的节点即可
	if (*pHead == NULL)
	{
		*pHead = NewNode;
		return;
	}
	//否则从头开始遍历链表，直到当前节点的指针域指向NULL，然后让当前节
	//点的指针域指向新申请的节点即可
	SListNode* pTail = *pHead;
	while (pTail->_pNext)
	{
		pTail = pTail->_pNext;
	}
	pTail->_pNext = NewNode;
}

//尾删
void SListPopBack(SListNode** pHead){
	assert(pHead);
	//三种情况分别对待
	if (NULL == *pHead)
	{
		return;
	}
	else if (NULL == (*pHead)->_pNext){
		free(*pHead);
		*pHead = NULL;
	}
	else{
		//链表中至少有两个节点
		SListNode* pCur = *pHead;
		while (pCur->_pNext->_pNext){
			pCur = pCur->_pNext;

		}
		free(pCur->_pNext->_pNext);
		pCur->_pNext = NULL;
	}
}


//头插元素
void SListPushFront(SListNode** pHead, SLDataType data)
{
	assert(pHead);
	SListNode* NewNode = SListNewNode(data);
	NewNode->_pNext = (*pHead);
	*pHead = NewNode;
}

//头删元素
void SListPopFront(SListNode** pHead)
{
	assert(pHead);
	SListNode* pDel = *pHead;
	//考虑链表为空情况
	if ((*pHead) == NULL)
	{
		printf("链表为空！无法删除！\n");
		return;
	}
	else{
		*pHead = pDel->_pNext;
		free(pDel);
	}
}

//查找元素
SListNode* SListFind(SListNode** pHead, SLDataType data){
	assert(pHead);
	//考虑链表为空的情况
	if (*pHead == NULL)
	{
		return NULL;
	}
	SListNode* pFind = *pHead;
	while(pFind){
		if (pFind->_data == data){
			return  pFind;
		}
			pFind = pFind->_pNext;
	}
	return NULL;
}


//任意位置的插入
void SListInsert(SListNode** pHead, SListNode* pos, SLDataType data)
{
	SListNode* _pNew = (SListNode*)SListNewNode(data);

	if (NULL == pos){
		return;
	}
	_pNew->_pNext = pos->_pNext;
	pos->_pNext = _pNew;
}

//任意位置的删除
void SListErase(SListNode** pHead, SListNode* pos)
{
	assert(pHead);
	assert(pos);
	if (pos == NULL || *pHead == NULL){
		return;
	}
	if (*pHead == pos){
		*pHead = pos->_pNext;
	}
	else{
		//找pos前一个结点
		SListNode * posPre = *pHead;
		while (posPre->_pNext != pos){
			posPre = posPre->_pNext;
		}
		posPre->_pNext = pos->_pNext;   //1		2		3		4		5
		free(pos);					   //	  pospre   pos
	}
}


//销毁单链表
void SListDestroy(SListNode** pHead){
	SListNode *pDel = *pHead;
	while (*pHead){
		pDel = *pHead;
		*pHead = pDel->_pNext;
		free(pDel);
	}
}

//链表大小
int SListSize(SListNode* pHead){
	SListNode * pCur = pHead;
		int length = 0;
		while (pCur) {
			++length;
			pCur = pCur->_pNext;
		}
		return length;
	}


//判空
int SListEmpty(SListNode* pHead){
	SListNode *pCur = pHead;
	if (pCur->_pNext != NULL){
		return 1;
	}
	return 0;
}

//首节点
SLDataType Front(SListNode* pHead){
	SListNode *pCur = pHead;
	return pCur->_data;
}

//末节点
SLDataType Back(SListNode* pHead){
	SListNode *pCur = pHead;
	while (pCur->_pNext){
		pCur = pCur->_pNext;	
	}
	return pCur->_data;
}

//删除第一个值为data的结点
//void SListRemove(SListNode** pHead, SLDataType data){
//	assert(pHead);
//	SListErase(pHead, SListFind(pHead, data));
//}

////删除指定的所有节点
//void SListRemoveAll(SListNode** pHead, SLDataType data){
//	assert(pHead);
//	SListNode *pCur = *pHead;
//	while (pCur){
//		SListRemove(pHead, data);
//		pCur = pCur->_pNext;
//	}	
//}



//冒泡排序
void SlistBubbleSort(SListNode** pHead){
	assert(pHead);
	SListNode *pCur = NULL;
	SListNode *pTail = NULL;
	int flag = 0;
	if (*pHead == NULL || (*pHead)->_pNext==NULL){
		return;
	}
	else{
		for (pCur = *pHead; pCur != NULL; pCur = pCur->_pNext){
			flag = 0;
			for (pTail = *pHead; pTail != NULL; pTail = pTail->_pNext){
				if ((pCur->_data) <(pTail->_data)){
					int a = pCur->_data;
					pCur->_data = pTail->_data;
					pTail->_data = a;
					flag = 1;
				}
			}
			if (flag == 0){
				return;
			}
		}
	}
}



//删除第一个值为data的元素
void SListRemove(SListNode** pHead, SLDataType data){
	assert(pHead);
	SListNode* pCur = *pHead;
	SListNode* pPre = *pHead;
	if (*pHead == NULL){
		return;
	}
	while (pCur){
		if (pCur->_data == data){
			if (pCur == *pHead){
				*pHead = pCur->_pNext;
			}
			else{
				pPre->_pNext = pCur->_pNext;
			}
			free(pCur);
			break;
		}
		pPre = pCur;
		pCur = pCur->_pNext;
	}
}



//删除指定的所有节点
void SListRemoveAll(SListNode** pHead, SLDataType data){
		assert(pHead);
		SListNode* pCur = *pHead;
		SListNode* pPre = *pHead;
		if (*pHead == NULL){
			return;
		}
		while (pCur){
			if (pCur->_data == data){
				if (pCur == *pHead){
					*pHead = pCur->_pNext;
				}
				else{
					pPre->_pNext = pCur->_pNext;
				}
				free(pCur);
				pCur = pPre->_pNext;
				continue;
			}
			pPre = pCur;
			pCur = pCur->_pNext;
		}
}

slist-test.c

#include "Slist.h"
#include<Windows.h>
#include<stdio.h>

void TestSListBack(){
	SListNode* p;
	SListInit(&p);
	SListPushBack(&p, 1);
	SListPushBack(&p, 2);
	SListPushBack(&p, 3);
	SListPushBack(&p, 4);
	SListPushBack(&p, 5);
	SListPrint(p);


	SListPopBack(&p);
	SListPrint(p);
	
	
	printf("链表大小:%d\n", SListSize(p));
	printf("首结点:%d\n", Front(p));
	printf("末节点:%d\n", Back(p));
	printf("判空<1.不空,0空>:%d\n", SListEmpty(p));
	printf("查找结点:%d\n", SListFind(&p, 10));

}

void TestSListFront(){
	SListNode* p;
	SListInit(&p);
	SListPushFront(&p, 3);
	SListPushFront(&p, 1);
	SListPushFront(&p, 8);
	SListPushFront(&p, 2);
	SListPushFront(&p, 3);
	SListPushFront(&p, 9);
	SListPushFront(&p, 7);
	SListPushFront(&p, 4);
	SListPrint(p);

	/*SListPopFront(&p);
	SListPrint(p);*/

	SListRemove(&p, 3);
	SListPrint(p);

	//SListRemoveAll(&p, 3);
	//SListPrint(p);

	SlistBubbleSort(&p);
	SListPrint(p);
}


void TestSList(){
	SListNode* p;
	SListInit(&p);
	SListPushBack(&p, 1);
	SListPushBack(&p, 2);
	SListPushBack(&p, 3);
	SListPushBack(&p, 4);
	SListPushBack(&p, 5);
	SListPrint(p);

	SListInsert(&p, SListFind(&p,3),7);
	SListPrint(p);

	SListErase(&p, SListFind(&p, 4));
	SListPrint(p);
}

TestSListDestroy(){
	SListNode* p;
	SListInit(&p);
	SListPushBack(&p, 1);
	SListPushBack(&p, 2);
	SListPushBack(&p, 3);
	SListPushBack(&p, 4);
	SListPushBack(&p, 5);
	SListPrint(p);

	SListDestroy(&p);
}



int main(){

	//TestSListBack();
	
	TestSListFront();

	//TestSList();

	//TestSListDestroy();

	system("pause");
	return 0;
}