我的小站——半生瓜のblog
单链表
- 结构体定义
- 打印
- 创建结点
- 尾插
- 头插
- 尾删
- 头删
- 查找
- 在指定位置前插入某个数据
- 删除指定位置数据
- 全部代码
结构体定义
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
打印
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur !=NULL)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
创建结点
SLTNode* SLTCreat(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}
尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
//创建新结点
SLTNode* newnode = SLTCreat(x);
//如果是空链表
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找到尾结点
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
//创建新结点
SLTNode* newnode = SLTCreat(x);
newnode->next = *pphead;
*pphead = newnode;
}
尾删
void SLTPopBack(SLTNode** pphead)
{
//空链表
if (*pphead == NULL)
{
return ;
}
//链表中只有一个结点
else if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//一个以上结点
else
{
//找到尾结点
SLTNode* tail = *pphead;
//找到尾结点的前一个结点
SLTNode* tailPrev = NULL;
while (tail->next != NULL)
{
tailPrev = tail;
tail = tail->next;
}
free(tail);
tailPrev->next = NULL;
}
}
头删
void SLTPopFront(SLTNode** pphead)
{
//如果直接free pphead就会找不到后面的结点了
//先保存下一个
SLTNode* ppheadNext = (*pphead)->next;//这里要加一个括号，因为*和->都是解引用，*是对任意的指针都可以解引用，取它指向的这个位置的数据，什么类型的指针就取几个字节，->是结构体的，这时候他们两个的优先级是一样的。
free(*pphead);
//这时候第一个数据就是之前第二个数据了
*pphead = ppheadNext;
}
查找
下面的删除和插入都要在先在链表中找到为前提。
SLTNode* SLTFind(SLTNode* phead,SLTDataType x)
{
SLTNode* pos = phead;
while (pos != NULL)
{
if (pos->data == x)
{
return pos;
}
pos = pos->next;
}
return NULL;
}
在指定位置前插入某个数据
void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x)
{
//如果在第一个结点前插入数据
//那就是头插，直接调用头插的函数
if (pos == *pphead)
{
SLTPushFront(pphead,x);
}
else
{
//创建一个新结点来存放新的数据
SLTNode* newnode = SLTCreat(x);
//要在pos前面插入newnode,就得先找到pos前面的内个结点
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
//链接起来
posPrev->next = newnode;
newnode->next = pos;
}
}
删除指定位置数据
void SLTErase(SLTNode** pphead, SLTNode*pos)
{
//当删除第一个结点的时候，无法找到他的前一个结点
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
//单链表每次老是要寻找前一个结点
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = pos->next;
free(pos);
}
}
全部代码
#include<stdio.h>
#include<stdlib.h>
//定义结构
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//改变头结点的传2级指针，不改变的传1级指针
//打印
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur !=NULL)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
//创建结点
SLTNode* SLTCreat(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
//创建新结点
SLTNode* newnode = SLTCreat(x);
//如果是空链表
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找到尾结点
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
//创建新结点
SLTNode* newnode = SLTCreat(x);
newnode->next = *pphead;
*pphead = newnode;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
//空链表
if (*pphead == NULL)
{
return ;
}
//链表中只有一个结点
else if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//一个以上结点
else
{
//找到尾结点
SLTNode* tail = *pphead;
//找到尾结点的前一个结点
SLTNode* tailPrev = NULL;
while (tail->next != NULL)
{
tailPrev = tail;
tail = tail->next;
}
free(tail);
tailPrev->next = NULL;
}
}
//头删
void SLTPopFront(SLTNode** pphead)
{
//如果直接free pphead就会找不到后面的结点了
//先保存下一个
SLTNode* ppheadNext = (*pphead)->next;//这里要加一个括号，因为*和->都是解引用，*是对任意的指针都可以解引用，取它指向的这个位置的数据，什么类型的指针就取几个字节，->是结构体的，这时候他们两个的优先级是一样的。
free(*pphead);
//这时候第一个数据就是之前第二个数据了
*pphead = ppheadNext;
}
//查找
SLTNode* SLTFind(SLTNode* phead,SLTDataType x)
{
SLTNode* pos = phead;
while (pos != NULL)
{
if (pos->data == x)
{
return pos;
}
pos = pos->next;
}
return NULL;
}
//在pos前插入某个数据
void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x)
{
//如果在第一个结点前插入数据
//那就是头插，直接调用头插的函数
if (pos == *pphead)
{
SLTPushFront(pphead,x);
}
else
{
//创建一个新结点来存放新的数据
SLTNode* newnode = SLTCreat(x);
//要在pos前面插入newnode,就得先找到pos前面的内个结点
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
//链接起来
posPrev->next = newnode;
newnode->next = pos;
}
}
//删除pos位置的数据
void SLTErase(SLTNode** pphead, SLTNode*pos)
{
//当删除第一个结点的时候，无法找到他的前一个结点
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
//单链表每次老是要寻找前一个结点
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = pos->next;
free(pos);
}
}
//测试
void Test1()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 0);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTNode* pos = SLTFind(plist, 0);
if (pos != NULL)
{
//说明找到了
SLTErase(&plist, pos);
}
SLTPrint(plist);
}
int main(void)
{
Test1();
return 0;
}