单链表的实现
首先创建头文件
#pragma
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//定义数据类型
typedef int SLDataType;
//创建单链表
typedef struct SLinkListNode
{
SLDataType data;
struct SLinkListNode* next;
}SLNode;
以下是所需要实现的函数接口
//不会改变头指针,传一级指针
//可能改变头指针,传二级指针
// //创建结点
SLNode* BuySLNode(SLDataType x);
//打印
void SListPrint(SLNode* phead);
//尾插
void SListPushBack(SLNode** pphead, SLDataType x);
//头插
void SListPushFront(SLNode** pphead, SLDataType x);
//尾删
void SListPopBack(SLNode** pphead);
//头删
void SListPopFront(SLNode** pphead);
//在pos前插入x
void SListInsert(SLNode** pphead, SLNode* pos, SLDataType x);
//找到x的位置并返回
SLNode* SListfind(SLNode* phead, SLDataType x);
//删除pos位置的值
void SListErase(SLNode** pphead, SLNode* pos);
接下来是函数的实现
#include"SLinkList.h"
//创建新结点
SLNode* BuySLNode(SLDataType x)
{
SLNode* newnode = (SLDataType*)malloc(sizeof(SLDataType));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//打印
void SListPrint(SLNode* phead)
{
SLNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//尾插
void SListPushBack(SLNode** pphead, SLDataType x)
{
SLNode* newnode = BuySLNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
// 找尾节点的指针
SLNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
// 尾节点,链接新节点
tail->next = newnode;
}
}
//头插
void SListPushFront(SLNode** pphead, SLDataType x)
{
SLNode* newnode = BuySLNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//尾删
void SListPopBack(SLNode** pphead)
{
if (*pphead == NULL)
{
return;
}
else if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLNode* prev = NULL;
SLNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
//头删
void SListPopFront(SLNode** pphead)
{
SLNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
//在pos前插入x
void SListInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
if (pos == *pphead)
{
SListPushFront(pphead, x);
}
else
{
SLNode* newnode = BuySLNode(x);
SLNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
//找到x的位置并返回
SLNode* SListFind(SLNode* phead, SLDataType x)
{
SLNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//删除pos位置的值
void SListErase(SLNode** pphead, SLNode* pos)
{
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
SLNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}