增加网站外链,注册网站时跳过验证码,wordpress搬家后图片不显示,怎么查工程项目信息这么可爱的猫猫不值得点个赞吗#x1f63d;#x1f63b; 目录
一.链表的概念和结构
二.单链表的逻辑结构和物理结构
1.逻辑结构 2.物理结构
三.结构体的定义
四.增加
1.尾插 SListpushback
2.头插 SListpushfront
五.删除
1.尾删 SListpopback
2.头删 SListpo… 这么可爱的猫猫不值得点个赞吗 目录
一.链表的概念和结构
二.单链表的逻辑结构和物理结构
1.逻辑结构 2.物理结构
三.结构体的定义
四.增加
1.尾插 SListpushback
2.头插 SListpushfront
五.删除
1.尾删 SListpopback
2.头删 SListpopfront
六.查找 插入 释放 打印
1.查找 SListfind
2.插入 SListinsert
3.释放 SListerase
4.打印 SListprint
七.源码
1.SList.h
2.SList.c
3.test.c 一.链表的概念和结构 链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 链表其实有很多种类 1.单向 双向 2.带头 不带头 3.循环 不循环 其中共能组合出8种形式的链表 这篇文章讲的是结构最简单的链表也就是单向不带头不循环链表即单链表。 单链表中的元素称为节点节点有一个数据data还有一个结构体指针next 存储下一个节点的地址最后一个节点的next是NULL。 二.单链表的逻辑结构和物理结构
1.逻辑结构 2.物理结构 三.结构体的定义
typedef int SLdatatype; //对数据类型重定义方便后续更改typedef struct SListNode
{SLdatatype data;struct SListNode* next;
}SLNode;
四.增加
1.尾插 SListpushback 想要实现尾插就要先找到尾节点但要注意当链表是空时就没有尾节点这个时候直接插入就行了 我们可以申请一个新的节点newnode然后插入链表中由于尾插和头插都需要申请新的节点所以我们可以将这封装成一个函数 注意不管是尾插还是头插最后都会使链表发生改变所以我们要传二级指针进去。 找尾节点时while里的循环条件要写成 tail-next !NULL 请看逻辑结构 申请新节点 BuySListNode
SLNode* BuySListNode(SLdatatype x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));assert(newnode);newnode-data x; //x是要插入的数据newnode-next NULL;return newnode;
}
尾插 SListpushback void SListpushback(SLNode** pphead,SLdatatype x) //注意传的是二级指针
{SLNode* newnode BuySListNode(x);if (*pphead NULL) //判断链表是否为空{*pphead newnode;}else{SLNode* tail *pphead; //寻找尾节点while (tail-next ! NULL) //注意这里不能写成 while(tail!NULL){tail tail-next;}tail-next newnode;}
}
2.头插 SListpushfront 头插时只需让新节点的 next 指向旧的头节点然后再把 newnode 赋给头节点使之成为新的头节点即使是空表也没关系newnode 会直接成为头节点。 void SListpushfront(SLNode** pphead, SLdatatype x)
{SLNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}
五.删除
1.尾删 SListpopback 尾删前我们需要判断 1.若为空表则直接结束函数 2.若链表中只有一个节点则直接 free 头节点然后置为NULL 3.寻找尾节点 tail 和尾节点的前一个节点 pre ,因为我们释放掉尾节点后pre就成为了新的尾节点而尾节点的 next 是 NULL 所以我们需要找到尾节点的前一个节点。 找尾的方法和之前的一样。 void SListpopback(SLNode** pphead)
{if (*pphead NULL){return;}else if ((*pphead)-next NULL) //注意这里因为优先级的问题*pphead 要打括号{free(*pphead);*pphead NULL;}else{SLNode* pre NULL;SLNode* tail *pphead;while (tail-next ! NULL){pre tail; //记录 tail 的前一个节点tail tail-next;}pre-next NULL; //next 置为NULL}
}
2.头删 SListpopfront 在头删前 1.判断是否为空表 2.定义一个 next 用来保存头节点中的 next 释放完后这个 next 就成为了新的头节点。 void SListpopfront(SLNode** pphead)
{if (*pphead NULL){return;}else{SLNode* next (*pphead)-next;free(*pphead);*pphead next;}
}
六.查找 插入 释放 打印
1.查找 SListfind 在插入和释放前都需要调用 find 函数来找到希望插入或是释放的位置。 SLNode* SListfind(SLNode* phead, SLdatatype x)
{SLNode* pos phead;while (pos){if (pos-data x){return pos;}pos pos-next;}
}
2.插入 SListinsert 如果是链表中只有一个节点就变成了头插只需要调用头插函数就行了如果是空表也不用担心可以设置成不调用函数 在插入前需要找到指定位置 pos 的前驱 pre 使pre-nextnewnode , newnode-nextpos 如图所示假设在3的前一个位置插入数据 void SListinsert(SLNode** pphead, SLNode* pos,SLdatatype x)
{SLNode* newnode BuySListNode(x);if (pos-next NULL){SListpushfront(pphead, x);}else{SLNode* pre *pphead;while (pre-next ! pos){pre pre-next;}pre-next newnode;newnode-next pos;}
}
3.释放 SListerase 释放前 1.如果只有一个节点则直接释放头节点再置为空即可 2.如果不止一个节点还需找到要释放的位置的前一个节点 pre 将 pre 的 next 指向 pos 的next然后再释放; 如图所示假设要释放掉3这个节点 void SListerase(SLNode** pphead, SLNode* pos, SLdatatype x)
{if (pos-next NULL){free(*pphead);*pphead NULL;}else{SLNode* pre *pphead;while (pre-next !pos){pre pre-next;}pre-next pos-next;free(pos);}
}
4.打印 SListprint 虽然可以直接用头节点 phead 遍历但博主还是推荐定义一个新的结构体指针 cur 把phead 的值赋给 cur 会显得更优雅 注意这里的 while 里的式子要写成 cur 如果 写成 cur-next 那么最终打印出来的结果会少一个节点的数据。 void SListprint(SLNode* phead)
{SLNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
} 七.源码
1.SList.h
#define _CRT_SECURE_NO_WARNINGS#include stdio.h
#include stdlib.h
#include assert.htypedef int SLdatatype;typedef struct SListNode
{SLdatatype data;struct SListNode* next;
}SLNode;void SListprint(SLNode* phead); //打印void SListpushback(SLNode** pphead,SLdatatype x); //尾插void SListpushfront(SLNode** pphead, SLdatatype x); //头插void SListpopfront(SLNode** pphead); //头删void SListpopback(SLNode** pphead); //尾删SLNode* SListfind(SLNode* phead,SLdatatype x); //查找void SListinsert(SLNode** pphead, SLNode* pos,SLdatatype x); //插入void SListerase(SLNode** pphead, SLNode* pos, SLdatatype x); //释放
2.SList.c
#define _CRT_SECURE_NO_WARNINGS#include SList.hvoid SListprint(SLNode* phead)
{SLNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}SLNode* BuySListNode(SLdatatype x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));assert(newnode);newnode-data x;newnode-next NULL;return newnode;
}void SListpushback(SLNode** pphead,SLdatatype x)
{SLNode* newnode BuySListNode(x);if (*pphead NULL){*pphead newnode;}else{SLNode* tail *pphead; //寻找尾节点while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}void SListpushfront(SLNode** pphead, SLdatatype x)
{SLNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}void SListpopfront(SLNode** pphead)
{if (*pphead NULL){return;}else{SLNode* next (*pphead)-next;free(*pphead);*pphead next;}
}void SListpopback(SLNode** pphead)
{if (*pphead NULL){return;}else if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLNode* pre NULL;SLNode* tail *pphead;while (tail-next ! NULL){pre tail;tail tail-next;}pre-next NULL;}
}SLNode* SListfind(SLNode* phead, SLdatatype x)
{SLNode* pos phead;while (pos){if (pos-data x){return pos;}pos pos-next;}
}void SListinsert(SLNode** pphead, SLNode* pos,SLdatatype x)
{SLNode* newnode BuySListNode(x);if (pos-next NULL){SListpushfront(pphead, x);}else{SLNode* pre *pphead;while (pre-next ! pos){pre pre-next;}pre-next newnode;newnode-next pos;}
}void SListerase(SLNode** pphead, SLNode* pos, SLdatatype x)
{if (pos-next NULL){free(*pphead);*pphead NULL;}else{SLNode* pre *pphead;while (pre-next !pos){pre pre-next;}pre-next pos-next;free(pos);}
}
3.test.c 博主写的主函数只是用来测试单链表的写起主函数来也不难大家可以自行编写。 #include SList.hvoid testSList1()
{SLNode* plist NULL;SListpushback(plist,1);SListpushback(plist,2);SListpushback(plist,3);SListpushback(plist,4);SListprint(plist);SListpushfront(plist, 0);SListprint(plist);SListpopfront(plist);SListpopfront(plist);SListpopfront(plist);SListprint(plist);SListpopback(plist);SListpopback(plist);SListpopback(plist);SListprint(plist);
}void testSList2()
{SLNode* plist NULL;SListpushback(plist, 1);SListpushback(plist, 2);SListpushback(plist, 3);SListpushback(plist, 4);SLNode* pos SListfind(plist, 3);if (pos){SListinsert(plist,pos, 20);SListprint(plist);}pos SListfind(plist, 2);if (pos){SListerase(plist,pos,2);SListprint(plist);}}int main()
{//testSList1();testSList2();return 0;
} 八.单链表的一些问题 在单链表中要想找到某一个数据就需要从头节点开始所以单链表是非随机存取的存储结构且要想对单链表进行一些操作总是要找到前驱节点有时还需判断一些特殊情况有什么办法能解决这些问题呢 博主将在下篇双向带头循环链表中讲解敬情期待~ 本篇文章到此就结束了如有错误或是建议欢迎小伙伴们提出~ 希望可以多多支持博主哦~ 谢谢你的阅读~
