实现不带头结点的单链表
程序员文章站
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;
}