【数据结构】- 链表之单链表(下)
文章目录
- 前言
- 一、单链表(下)
-
- 1.1 查找+修改
- 1.2 在任意位置插入
-
- 1.2.1 在pos位置插入(也就是pos位置之前)
- 1.2.2 在pos位置之后插入
- 1.3 在任意位置删除
-
- 1.3.1 删除pos位置得值
- 1.3.2 删除pos位置后面的值
- 二、完整代码
- 总结
前言
未来藏在迷雾中 叫人看来胆怯 带你踏足其中 就会云开雾散
本章是关于数据结构中的链表之单链表(下)
提示:以下是本篇文章正文内容,下面案例可供参考
一、单链表(下)
1.1 查找+修改
//SList.h
SLTNode* STFind(SLTNode* phead, SLTDataType x);
//SList.c
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
//Test.c
void TestSList()
{SLTNode* plist = NULL;SLPushFornt(&plist, 1);SLPushFornt(&plist, 2);SLPushFornt(&plist, 3);SLPushFornt(&plist, 4);SLTPrint(plist);SLTNode* pos = STFind(plist, 3);if (pos)//判断是否为空{pos->data = 30;}SLTPrint(plist);
}
1.2 在任意位置插入
1.2.1 在pos位置插入(也就是pos位置之前)
//SList.h
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos之前插入
//SList.c
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (*pphead == pos){SLPushFornt(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuyTNode(x);prev->next = newnode;newnode->next = pos;}
}
//Test.c
void TestSList()
{SLTNode* plist = NULL;SLPushFornt(&plist, 1);SLPushFornt(&plist, 2);SLPushFornt(&plist, 3);SLPushFornt(&plist, 4);SLTPrint(plist);SLTNode* pos = STFind(plist, 3);if (pos)//判断是否为空{SLInsert(&plist, pos, 30);}
}
流程图
- 多个节点
- 一个节点
1.2.2 在pos位置之后插入
//SList.h
void SLInsertAfter(SLTNode* pos, SLTDataType x);//在pos之后插入
//SList.c
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuyTNode(x);newnode->next = pos->next;pos->next = newnode;
}
//Test.c
void TestSList()
{SLTNode* plist = NULL;SLPushFornt(&plist, 1);SLPushFornt(&plist, 2);SLPushFornt(&plist, 3);SLPushFornt(&plist, 4);SLTPrint(plist);SLTNode* pos = STFind(plist, 2);if (pos)//判断是否为空{SLInsertAfter(pos, 30);}SLTPrint(plist);
}
流程图:
注意:
下面这种写法就存在了问题newnode指向了它自己造成了错误
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuyTNode(x);pos->next=newnode;newnode->next=pos->next;
}
流程图:
1.3 在任意位置删除
1.3.1 删除pos位置得值
//SList.h
void SLErase(SLTNode** pphead, SLTNode* pos);
//SList.c
void SLErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (pos == *pphead){SLPopFornt(pphead);//头删}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}
//Test.c
void TestSList()
{SLTNode* plist = NULL;SLPushFornt(&plist, 1);SLPushFornt(&plist, 2);SLPushFornt(&plist, 3);SLPushFornt(&plist, 4);SLTPrint(plist);SLTNode* pos = STFind(plist, 3);if (pos)//判断是否为空{SLErase(&plist, pos);}SLTPrint(plist);
}
流程图:
1.3.2 删除pos位置后面的值
//SList.h
void SLEraseAfter(SLTNode* pos);
//SList.c
void SLEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* next = pos->next;pos->next = next->next;free(next);
}
//Test.c
void TestSList()
{SLTNode* plist = NULL;SLPushFornt(&plist, 1);SLPushFornt(&plist, 2);SLPushFornt(&plist, 3);SLPushFornt(&plist, 4);SLTPrint(plist);SLTNode* pos = STFind(plist, 3);if (pos)//判断是否为空{SLEraseAfter(pos);}SLTPrint(plist);
}
流程图:
二、完整代码
//SList.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);
void SLPushFornt(SLTNode** pphead, SLTDataType x);
void SLPushBack(SLTNode** pphead, SLTDataType x);void SLPopFornt(SLTNode** pphead);
void SLPopBack(SLTNode** pphead);SLTNode* STFind(SLTNode* phead, SLTDataType x);//任意位置插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos之前插入
void SLInsertAfter(SLTNode* pos, SLTDataType x);//在pos之后插入
void SLErase(SLTNode** pphead, SLTNode* pos);//删除pos位置的值
void SLEraseAfter(SLTNode* pos);//删除pos位置的值//SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\\n");
}SLTNode* BuyTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;return newnode;
}void SLPushFornt(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuyTNode(x);newnode->next = *pphead;*pphead = newnode;
}void SLPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuyTNode(x);//空链表if(*pphead==NULL){*pphead = newnode;}//非空链表else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}void SLPopFornt(SLTNode** pphead)
{//空链表assert(*pphead);//一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//多个节点:保存下一个节点,释放当前节点else{SLTNode* del = *pphead;*pphead = del->next;free(del);}
}void SLPopBack(SLTNode** pphead)
{//空链表assert(*pphead);//有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}有多个节点else{SLTNode* prev = NULL;SLTNode* tail = *pphead;//找尾while (tail->next == NULL)//或者写成while(tail->next){prev = tail;tail = tail->next;}free(tail);prev->next = NULL;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}SLTNode* STFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (*pphead == pos){SLPushFornt(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuyTNode(x);prev->next = newnode;newnode->next = pos;}
}//在pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuyTNode(x);newnode->next = pos->next;pos->next = newnode;
}//删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (pos == *pphead){SLPopFornt(pphead);//头删}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}//删除pos位置后面的值
void SLEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* next = pos->next;pos->next = next->next;free(next);
}//Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"void TestSList()
{SLTNode* plist = NULL;SLPushFornt(&plist, 1);SLPushFornt(&plist, 2);SLPushFornt(&plist, 3);SLPushFornt(&plist, 4);SLTPrint(plist);SLPushBack(&plist, 5);SLPopFornt(&plist);SLTPrint(plist);SLPopFornt(&plist);SLTPrint(plist);SLPopFornt(&plist);SLTPrint(plist);SLPopFornt(&plist);SLTPrint(plist);SLTNode* pos = STFind(plist, 3);if (pos)//判断是否为空{SLInsert(&plist, pos, 30);}SLTNode* pos = STFind(plist, 2);if (pos)//判断是否为空{SLInsertAfter(pos, 30);}SLTPrint(plist);SLTNode* pos = STFind(plist, 3);if (pos)//判断是否为空{SLErase(&plist, pos);}SLTPrint(plist);SLTNode* pos = STFind(plist, 3);if (pos)//判断是否为空{SLEraseAfter(pos);}SLTPrint(plist);
}int main()
{TestSList();return 0;
}
总结
Ending,今天的链表之单链表(下)的内容就到此结束啦~,如果后续想了解更多,就请关注我吧,一键三连哦 ~