欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

实现不带头结点的单链表

程序员文章站 2024-03-21 13:06:04
...
SList.h
//不带头结点的单链表   
//不带头结点的话,那么链表表中的第一个节点一顶存储的是有效元素

#pragma once  //保证头文件不被重复包含


#include<assert.h>
#include<stdlib.h>
#include<stdio.h>
//如果想要对链表进行操作,那么首先需要一个结点的结构体

typedef int SDataType;

typedef struct SListNode
{
	SDataType data;
	struct SListNode* _pNext;
}Node;

//为了操作简单,在把链表的结构给出来
//如果想要找到一个链表,那么只需要知道链表的头节点就可以了
typedef struct SList
{
	Node* _pHead;
}SList;

//初始化
void SListInit(SList* pl);

//尾插
void SListPushBack(SList* pl,SDataType data);

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

//销毁
void SListDestroy(SList* pl);

//打印
void PrintSList(SList* pl);

//测试
void TestList();

//头插
void SListPushFront(SList* pl, SDataType data);

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

//任意位置的插入
void SListInsert(Node* pos, SDataType data);

//任意位置的删除
void SListErase(SList* pl,Node* pos);   //需要遍历去找到pos的前一个位置

//查找
Node* SListFind(SList* pl, SDataType data);

//个数
int SListSize(SList* pl);

//是否为空
int SListEmpty(SList* pl);

//返回第一个结点
Node* SListFront(SList* pl);

//返回最后一个结点
Node* SListBack(SList* pl);

SList.c
#include"单链表.h"

void SListInit(SList* pl)
{
	assert(pl);
	//初始化的时候,链表中一个结点都没有
	//所以让头节点指向空就可以了
	pl->_pHead = NULL;
}

Node* BuySListNode(SDataType data)
{
	Node* pNode = (Node*)malloc(sizeof(Node));
	//判断是否申请空间成功
	if (NULL == pNode)
	{
		assert(0);
		return NULL;
	}
	pNode->data = data;
	pNode->_pNext = NULL;
	return pNode;
}

void SListPushBack(SList* pl, SDataType data)
{
	//用来遍历的结点
	Node* pCur = NULL;
	//先需要构造出来一个结点
	//链表中的结点是从堆上new出来的
	Node* pNewNode = NULL;    //先将新的结点的赋值成空值
	//紧接着,判断链表是否存在,如果存在的话,我们给出结点
	assert(pl);    //保证链表是存在的 
	//给出结点
	pNewNode = BuySListNode(data);
	pCur = pl->_pHead;
	//空链表
	if (NULL == pl->_pHead)
		pl->_pHead = pNewNode;
	else
	{
		while (pCur->_pNext)
		{
			pCur = pCur->_pNext;
		}
		pCur->_pNext = pNewNode;
		pNewNode->_pNext = NULL;
	}
}

void PrintSList(SList* pl)
{
	Node* pCur = NULL;
	assert(pl);
	pCur = pl->_pHead;
	while (pCur)
	{
		printf("%d--->", pCur->data);
		pCur = pCur->_pNext;
	}
	printf("NULL\n");
}

void SListDestroy(SList* pl)
{
	Node* pCur = NULL;
	assert(pl);
	pCur = pl->_pHead;
	while (pCur)
	{
		pl->_pHead = pCur->_pNext;
		free(pCur);
		pCur = pl->_pHead;
	}
	pl->_pHead = NULL;
}

void SListPopBack(SList* pl)
{
	Node* pCur = NULL;
	//找链表中的倒数第二个结点    链表至少有两个结点
	assert(pl);
	if (NULL == pl->_pHead)
	{
		return;
	}
	else if (NULL == pl->_pHead->_pNext)
	{
		free(pl->_pHead);
		pl->_pHead = NULL;
	}
	else
	{
		//至少有两个节点
		Node* pTailNode = pl->_pHead;
		while (pTailNode->_pNext->_pNext)
		{
			pTailNode = pTailNode->_pNext;
		}
		free(pTailNode->_pNext);
		pTailNode->_pNext = NULL;
	}
}

void SListPushFront(SList* pl, SDataType data)
{
	Node* pNewNode = NULL;
	assert(pl);
	pNewNode = BuySListNode(data);
	pNewNode->_pNext = pl->_pHead;
	pl->_pHead = pNewNode;
}

void SListPopFront(SList* pl)
{
	assert(pl);
	if (NULL == pl->_pHead)
		return;
	else
	{
		Node* pDelNode = pl->_pHead;
		pl->_pHead = pDelNode->_pNext;
		free(pDelNode);
	}
}

void SListInsert(Node* pos, SDataType data)
{
	Node* pNewNode = NULL;
	//只能忘这个位置的后面插入
	if (NULL == pos)
		return;
	pNewNode = BuySListNode(data);
	pNewNode->_pNext = pos->_pNext;
	pos->_pNext = pNewNode;
}

void SListErase(SList* pl,Node* pos)
{
	Node* pPrePos = NULL;
	assert(pl);
	if (NULL == pl->_pHead || NULL == pos)
		return;
	if (pos == pl->_pHead)
	{
		pl->_pHead = pos->_pNext;
		free(pos);
		return;
	}
	pPrePos = pl->_pHead;
	while (pPrePos->_pNext != pos)
	{
		pPrePos = pPrePos->_pNext;
	}
	pPrePos->_pNext = pos->_pNext;
	free(pos);
}

Node* SListFind(SList* pl, SDataType data)
{
	Node* pCur = pl->_pHead;
	assert(pl);
	while (pCur)
	{
		if (pCur->data == data)
			return pCur;
		pCur = pCur->_pNext;
	}
	return NULL;
}

int SListSize(SList* pl)
{
	int count = 0;
	Node* pCur = NULL;
	assert(pl);
	pCur = pl->_pHead;
	while (pCur)
	{
		count++;
		pCur = pCur->_pNext;
	}
	return count;
}

int SListEmpty(SList* pl)
{
	assert(pl);
	retrun NULL == pl->_pHead;
}

Node* SListFront(SList* pl)
{
	assert(pl);
	return pl->_pHead;
}

//必须保证有结点才可以
Node* SListBack(SList* pl)
{
	Node* pCur = NULL;
	assert(pl);
	pCur = pl->_pHead;
	while (pCur->_pNext)
	{
		pCur = pCur->_pNext;
	}
	return pCur;
}
main.c
#include"单链表.h"

void TestList1()
{
	SList s;  //创建一个对象

	SListInit(&s);

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

	PrintSList(&s);

	SListPopBack(&s);

	PrintSList(&s);

	SListPushFront(&s, 10);
	SListPushFront(&s, 20);
	SListPushFront(&s, 30);
	SListPushFront(&s, 40);
	SListPushFront(&s, 50);

	PrintSList(&s);

	SListPopFront(&s);
	SListPopFront(&s);

	PrintSList(&s);

	SListInsert(SListFind(&s, 2),66);

	PrintSList(&s);

	SListErase(&s, SListFind(&s, 66));

	PrintSList(&s);

	SListDestroy(&s);
}

void TestList()
{
	TestList1();
}

int main()
{
	TestList();
	return 0;
}
相关标签: 数据结构