单链表的实现
首先创建头文件
#pragma
#include
#include
#include
//定义数据类型
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;
}
}