🚀write in front🚀
📝个人主页:认真写博客的夏目浅石.
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
📣系列专栏:C语言实现数据结构
💬总结:希望你看完之后,能对你有所帮助,不足请指正!共同学习交流 🖊
✉️如果无聊的话,就来逛逛我的博客栈吧stack-frame.cn
文章目录
- 前言
- 一、链表概念
- 二、链表的分类
- 1. 单向或者双向
- 2. 带头或者不带头
- 3. 循环或者非循环
- 三、链表的实现
- 函数接口汇总SList.h
- 函数接口实现SList.c
- 代码实践Test.c
- 代码汇总
- 总结
前言
这几天看了数据结构的单链表这一节,真的收获很大,第一次看没有动手敲代码就是感觉学了和没学一样,今天也是从新又看了一遍,并且边学边敲代码,终于算是非常理解单链表这个东西了,今天就把我所学到的知识给大家分享一下。
一、链表概念
链表
是一种物理存储结构
上非连续
、非顺序
的存储结构,数据元素的逻辑顺序
是通过链表中的指针
链
接次序实现的 。
二、链表的分类
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构
:
1.无头单向链表
2.双向循环链表
- 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。
三、链表的实现
函数接口汇总SList.h
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//打印
void SLTPrint(SLTNode* phead);
SLTNode* BuySLTNode(SLTDataType x);
//增
void SLTPushBack(SLTNode** pphead,SLTDataType x);
void SLTPushFront(SLTNode** pphead,SLTDataType x);
//删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* phead,SLTDataType x);
//任意位置插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除某个节点
void SListErase(SLTNode** pphead, SLTNode* pos);
//在后面插入一个节点
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos后面这一个节点
void SListEraseAfter(SLTNode* pos);
函数接口实现SList.c
//--------------------------手动分割线---------------------------
//打印
void SLTPrint(SLTNode* phead)
{
assert(phead);
SLTNode* cur=phead;
while(cur)
{
printf("%d ",cur->data);
cur=cur->next;
}
printf("NULL\n");
}
//--------------------------手动分割线-----------------------------
//创建新节点
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode=(SLTNode*)malloc(sizeof(SLTNode));
if(newnode==NULL)
{
printf("malloc fail\n");
return NULL;
}
newnode->data=x;
newnode->next=NULL;
return newnode;
}
//--------------------------手动分割线-----------------------------
//尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x)
{
assert(pphead);
SLTNode* newnode=BuySLTNode(x);
if(*pphead==NULL)
{
*pphead=newnode;
}
else
{
//找尾
SLTNode* cur=*pphead;
while(cur->next!=NULL)
{
cur=cur->next;
}
cur->next=newnode;
}
}
//--------------------------手动分割线-----------------------------
//前插
void SLTPushFront(SLTNode** pphead,SLTDataType x)
{
assert(pphead);
SLTNode* newnode=BuySLTNode(x);
newnode->next=*pphead;
*pphead=newnode;
}
//--------------------------手动分割线-----------------------------
//尾删
void SLTPopBack(SLTNode** pphead)
{
// 暴力检查
assert(pphead);
assert(*pphead);
SLTNode* cur=*pphead;
if(*pphead->next==NULL)
{
free(*pphead);
*pphead=NULL;
}
else
{
SLTNode* cur=*pphead;
while(cur->next->next!=NULL)
{
cur=cur->next;
}
SLTNode* tmp=cur->next;
free(tmp);
cur->next=NULL;
}
}
//--------------------------手动分割线-----------------------------
//前删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
if(*pphead->next==NULL)
{
free(*pphead);
*pphead=NULL;
}
else
{
SLTNode* tmp=*pphead;
free(tmp);
tmp=NULL;
*pphead=*pphead->next;
}
}
//--------------------------手动分割线-----------------------------
//查找
SLTNode* SListFind(SLTNode* phead,SLTDataType x)
{
SLTNode* cur=phead;
while(cur)
{
if(cur->data==x) return cur;
cur=cur->next;
}
return NULL;
}
//--------------------------手动分割线-----------------------------
//任意位置插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pos);
assert(pphead);
SLTNode* newnode=BuySLTNode(x);
if(*pphead==pos)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev=*pphead;
while(prev->next!=pos)
{
prev=prev->next;
}
prev->next=newnode;
newnode->next=pos;
}
}
//--------------------------手动分割线-----------------------------
//删除某个节点
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
SLTNode* cur=*pphead;
if(*pphead==pos)
{
SLTPopFront(pphead);
}
else
{
while(cur->next!=pos)
{
cur=cur->next;
}
cur->next=pos->next;
free(pos);
pos=NULL;
}
}
//--------------------------手动分割线-----------------------------
//在后面插入一个节点
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//--------------------------手动分割线-----------------------------
//删除pos后面这一个节点
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
//--------------------------手动分割线-----------------------------
代码实践Test.c
#include"SList.h"
void TestSList1()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
}
void TestSList2()
{
SLTNode* plist = NULL;
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
}
void TestSList3()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
}
int main()
{
TestSList3();
return 0;
}
代码汇总
#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)
{
assert(phead);
SLTNode* cur=phead;
while(cur)
{
printf("%d ",cur->data);
cur=cur->next;
}
printf("NULL\n");
}
//--------------------------手动分割线-----------------------------
//创建新节点
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode=(SLTNode*)malloc(sizeof(SLTNode));
if(newnode==NULL)
{
printf("malloc fail\n");
return NULL;
}
newnode->data=x;
newnode->next=NULL;
return newnode;
}
//--------------------------手动分割线-----------------------------
//尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x)
{
SLTNode* newnode=BuySLTNode(x);
if(*pphead==NULL)
{
*pphead=newnode;
}
else
{
//找尾
SLTNode* cur=*pphead;
while(cur->next!=NULL)
{
cur=cur->next;
}
cur->next=newnode;
}
}
//--------------------------手动分割线-----------------------------
//前插
void SLTPushFront(SLTNode** pphead,SLTDataType x)
{
SLTNode* newnode=BuySLTNode(x);
newnode->next=*pphead;
*pphead=newnode;
}
//--------------------------手动分割线-----------------------------
//尾删
void SLTPopBack(SLTNode** pphead)
{
//暴力检查
assert(*pphead);
SLTNode* cur=*pphead;
if(*pphead->next==NULL)
{
free(*pphead);
*pphead=NULL;
}
else
{
SLTNode* cur=*pphead;
while(cur->next->next!=NULL)
{
cur=cur->next;
}
SLTNode* tmp=cur->next;
free(tmp);
cur->next=NULL;
}
}
//--------------------------手动分割线-----------------------------
//前删
void SLTPopFront(SLTNode** pphead)
{
assert(*pphead);
if(*pphead->next==NULL)
{
free(*pphead);
*pphead=NULL;
}
else
{
SLTNode* tmp=*pphead;
free(tmp);
tmp=NULL;
*pphead=*pphead->next;
}
}
//--------------------------手动分割线-----------------------------
//查找
SLTNode* SListFind(SLTNode* phead,SLTDataType x)
{
SLTNode* cur=phead;
while(cur)
{
if(cur->data==x) return cur;
cur=cur->next;
}
return NULL;
}
//--------------------------手动分割线-----------------------------
//任意位置插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
SLTNode* newnode=BuySLTNode(x);
if(*pphead==pos)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev=*pphead;
while(prev->next!=pos)
{
prev=prev->next;
}
prev->next=newnode;
newnode->next=pos;
}
}
//--------------------------手动分割线-----------------------------
//删除某个节点
void SListErase(SLTNode** pphead, SLTNode* pos)
{
SLTNode* cur=*pphead;
if(*pphead==pos)
{
SLTPopFront(pphead);
}
else
{
while(cur->next!=pos)
{
cur=cur->next;
}
cur->next=pos->next;
free(pos);
pos=NULL;
}
}
//--------------------------手动分割线-----------------------------
//在后面插入一个节点
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//--------------------------手动分割线-----------------------------
//删除pos后面这一个节点
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
//--------------------------手动分割线-----------------------------
void TestSList1()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
}
void TestSList2()
{
SLTNode* plist = NULL;
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
}
void TestSList3()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
}
int main()
{
TestSList3();
return 0;
}
总结
今天学习了单链表的知识,初次写数据结构的知识,给我的感觉就是,学三遍不如手敲代码一遍来的实在,所以数据结构的学习我将多画图,多敲代码来学习
,希望大家吸取经验和我一起学习数据结构,为后面打比赛刷题打下坚实基础。
我是夏目浅石,希望和你一起学习进步,刷题无数!!!希望各位大佬
能一键三连支持一下博主
,hhhh~我们下期见喽
如果无聊的话,就来逛逛我的博客栈吧stack-frame.cn
✨ 原创不易,还希望各位大佬支持一下 \textcolor{blue}{原创不易,还希望各位大佬支持一下} 原创不易,还希望各位大佬支持一下
👍 点赞,你的认可是我创作的动力! \textcolor{9c81c1}{点赞,你的认可是我创作的动力!} 点赞,你的认可是我创作的动力!
⭐️ 收藏,你的青睐是我努力的方向! \textcolor{ed7976}{收藏,你的青睐是我努力的方向!} 收藏,你的青睐是我努力的方向!
✏️ 评论,你的意见是我进步的财富! \textcolor{98c091}{评论,你的意见是我进步的财富!} 评论,你的意见是我进步的财富!