前言: 刷题和面试兼顾还得看你啊-牛客网
近几年互联网受疫情影响,许多互联网都使用牛客网在线笔试招人
很多同学因为不熟悉牛客网的环境和使用,最后在线笔试面试中屡屡受挫
牛客网提供了语言巩固,算法提高等在线OJ题,更有面试真题,大厂内推!
链接附上点击链接注册牛客网
牛客网这么好用,但是下面几个关于牛客网的知识你了解过吗?
你知道你OJ过不了,牛客网几种经典的英文报错提示的含义吗?
你知道牛客网的OJ分为IO型和接口型吗?
你使用过牛客网的调试功能吗?
一.基本介绍:
1.链表的每一个结点都包含两个域:数据域和指针域
2.其实计算机中并没有指针的指向,箭头指向只是人为假象出来的,实际上指针域存储的是下一个结点的地址。
3.链表的种类:链表的种类从三对修饰词中每对修饰词中选出一个,例如我们今天讲的就是不带头单向不循环链表
4.左值和右值问题
拿这个曾经卡死你的那个插入结点的代码为例来讲解:
备注:这里要从没有标记的一端开始修改,也就是先执行s->next=p->next,
后执行p->next=s ,因为如果先执行p->next=s;就会找不到p原来后面的那个结点了,这和顺序表的从哪一端开始移动很像!
5.单链表较动态顺序表:
动态顺序表:
优点:只用通过数组下标访问的方式就可以随机访问某一个数组元素并进行操作,时间复杂度低;
缺点:当要删除或插入元素的时候不得不移动大量元素,时间复杂度高;
单链表(single list 常简写为 SLT)
优点:当要删除或插入元素的时候不用移动大量元素,时间复杂度低;
缺点:当要访问某一个结点并进行操作的时候要从头开始遍历,时间复杂度高;
6.要想学会单链表你得了解这些(上面没有讲到的下面会一一讲到)
🚗🚗🚗🚗🚗🚗🚗这里是正文接口分界线🚗🚗🚗🚗🚗🚗🚗🚗🚗
二.单链表基本操作
1.打印单链表
void SListPrint(SLTNode* plist) { SLTNode* cur = plist; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
备注;在对每一个接口进行测试的时候,通过打印结果来观察测试接口的正确与否
2.构造结点
每次插入前都要构造一个新结点,这一步模块化代码是不是和顺序表的插入前检查是否需要扩容很像!哈哈哈
SLTNode* BuySLTNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); newnode->data = x; newnode->next = NULL; return newnode; }
注意:返回类型是SLTNode*类型
3.尾插:在单链表尾部插入一个结点
关于哨兵位的头结点:(先给结论吧)
总结:如果带头结点的单链表在进行操作时,就可以使得每一个带数据元素的结点都有前驱结点,就可以统一操作这些带 数据元素的结点,就可以不用考虑一些特殊情况。
但是如果是不带头结点的单链表在进行操作时,第一个结点(也就是第一个带数据元素的结点)没有前驱结点,所以操作起来要对第一个结点特殊考虑。
一:(不带头结点的话)还是借一借排队的例子和你讲一讲,你在食堂排队打饭,你老老实实排队(尾插),会遇到两种情况:(一个不太恰当的例子)
1.一般情况,原队伍有人,那你(待插入的结点)就要通过“指针”和这原队伍最后一个学生(最后一个结点)关联起来
2:特殊情况:原队伍没人,那你通过指针关联起来的就不再是学生,而是“食堂阿姨”,对待长辈肯定会有所拘谨,那么这就会产生细微的区别,要特殊考虑。
二:(带头结点的话)但是下一篇博客就会提到,当我们用一个学生去代替食堂阿姨打饭的位置,无论原队伍没人还是原队伍有人打饭交接的内容就可以统一(排队的同学才是相当于带头结点中那些带有数据元素的结点,需要我们进行单链表的打印等操作,所以不必再考虑头结点和头指针的关联问题)。
void SListPushBack(SLTNode** pplist, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); if (*pplist == NULL) { *pplist = newnode; } else { SLTNode* tail = *pplist; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
命名:push 压入 pop弹出
back尾 front 头