写在前面
链表真的很难吗？
缺陷1：空间经常会不够，需要扩容
缺陷2：插入或删除数据时需要挪动大量数据，效率低下
对于数据的插入和删除需要挪动大量的数据，因为时间复杂度的过高，导致效率的低下因为我们就应该对这两种缺陷做一个改进
对于链表这一块，如果C语言的指针和结构体这一块你没有很熟悉的话，学起来确实会比较困难，但这也不妨碍你看本文，我一定会慢慢地带你从浅到深，去领会链表该如何操作
typedef int SLTDataType;
typedef struct SListNode { //结构体大小：8B
SLTDataType data;
struct SListNode* next;
//SLTNode* next; 不可以这样定义，因为还没有到声明
}SLTNode;
typedef int SLTDataType;
struct SListNode { //结构体大小：8B
SLTDataType data;
struct SListNode* next;
};
typedef struct SListNode SLTNode；
明白了如何去定义一个结构体，接下去我们就用这个定义的结构体试着去创建一两个结点，然后对它们进行一个链接，我用了下面两种定义和链接方法，你觉得哪个更好呢？
第一种，指针类型【动态开辟】
SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
n1->next = n2;
第二种，变量类型【直接定义】
SLTNode n3, n4;
n3.next = &n4;
SLTNode* BuySLTNode(SLTDataType x)
{
//动态开辟
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
}
SLTNode* n1 = BuySLTNode(1);
SLTNode* n2 = BuySLTNode(2);
SLTNode* n3 = BuySLTNode(3);
SLTNode* n4 = BuySLTNode(4);
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;
结构体指针变量，既然是指针那就一定指向一块内存地址，也就是我们在Buy一个结点的时候为这个结点所申请的这块内存地址，而当你去解引用这个指针变量时，也就拿到了这块内存的地址值，这其实就可以解释了为什么n1->next = n2，是等于n2，而不是一个内存地址值，因为这个n2中存放的就是当前这个结点在堆区中申请的这块地址n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;
搞清楚了链表的各个结点直接是如何前后链接起来的，接下去我们正式地来玩一玩💷，申请多个结点将他们串起来
SLTNode* BuySLTNode(SLTDataType x)
{
//动态开辟
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
}
SLTNode* SListCreate(int n)
{
SLTNode* phead = NULL, * ptail = NULL;
for (int i = 0; i < n; ++i)
{
SLTNode* newnode = BuySLTNode(i);
if (phead == NULL)
phead = ptail = newnode;
else
{
ptail->next = newnode;
ptail = newnode;
}
}
return phead;
}
带头结点和不带头结点的类型，后面我会详细介绍。对于这个头结点指针phead，就是用来保存头结点的，对于这个ptail尾结点指针，就是用来链接数据的，将每一个待插入的结点链接到当前尾结点指针的后一个结点，也就是执行这句ptail->next = newnode;
ptail = newnode;
最后当你想要观看整个链表的结构时，去获取这个头结点即可，因为后面的结点都是链接在头结点之后的，所以头结点不可以变化，一旦变化了那么整个链表的结构就乱了😂，最后这是个函数，返回值类型是LSTNode*，因此返回phead，主函数中去接收一下即可SLTNode* SList = SListCreate(10);
void PrintList(SLTNode* phead)
{
SLTNode* cur = phead; //尽量不用头指针，定义变量存放
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
再定义一个结构体指针又需要消耗内存空间1M = 10W(byte)，1G = 10亿(byte)，对于一个cur结构体指针的大小，也就是8个B的大小，对于系统来说完全就是芝麻粒小的东西，所以有没有这个cur完全没有影响。此时美丽的链表就被形象地打印了出来📷
printf("[%d|%p]->", cur->data,cur->next);
对于Test函数和SListCreate函数都有它们自己单独的栈帧，栈帧内部就是函数体中定义的各种变量。因此在起初创建newnode的时候，phead和ptail均是指向这个链表的第一个结点，存了第一个结点的【地址】。phead是为了函数结束后返回，ptail则是为了链接free()
随着Create函数的结束，所建立的栈帧也将销毁，在函数内部创建的局部变量也跟着一起销毁，不复存在出了作用域就销毁了，但好在我们保存并返回了这个指向链表头的指针，这个指针中又保存着第一个结点的地址，此时SList便可以通过这个地址去访问这个链表
认真看完了上面两个模块，相信你对链表的整体框架和结构已经有了一个基本的认识，现在我们要真正地去实现一些有关链表操作的接口，以便观察链表这种数据结构在处理数据的时候与顺序表有何不同❓
void SListPushBack(SLTNode* phead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
SLTNode* ptail = phead;
// while(tail != NULL)
while (ptail) //一般写成这样
{
ptail = ptail->next;
}
ptail = newnode; //只是存放在局部变量中
}
void SListPushBack(SLTNode* phead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
SLTNode* ptail = phead;
while (ptail->next)
{
ptail = ptail->next;
}
ptail->next = newnode;
}
void SListPushBack(SLTNode* phead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
if (phead == NULL)
{
phead = newnode; //形参的改变不会影响实参
}
else
{
SLTNode* ptail = phead;
while (ptail->next)
{
ptail = ptail->next;
}
ptail->next = newnode;
}
}
发现每一次进入的都是第一个if，也就意味着这个SList一直就是为空的，但是进入函数内部却可以发现其实这个phead是指向了newnode所在的内存地址的，但是在外面看的时候，这个SList却始终都是空的，这是为什么呢？函数的返回值是void，因此外界根本无法从返回值来获取和指向这个首部的指针
本模块对于二级指针不太熟悉的同学先去看看二级指针有关的文章，我推荐这篇深入理解二级指针
void Swap1(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
int a = 2, b = 5;
printf("a = %d, b = %d\n", a, b);
Swap1(&a, &b);
printf("a = %d, b = %d\n", a, b);
可以看到，两个变量的值得到了交换，也就是很经典的通过指针接收地址去交换两个变量的值，我们先通过这个小案例带大家DeBug一下
可以看到，对于Swap1函数，我们传入了变量a和变量b的地址，然后在形参中，使用到两个指针变量去接收这两个地址，在函数体中，我们又可以通过【*p1和 *p2】解引的操作获取变量a和变量b的内容，引入第三方变量暂时存放一下，就可以实现一个交换了
指针的解引直接是访问这两块地址的内容，因而就发生了一个交换若是对上述这个传址的修改不了解，也可以看看我在函数章节中介绍的那个经典案例，讲得很细致清楚
int】型的变量，我们要交换改变它们的值需要对【int*】去传入地址，拓展一下int*】型的变量，我们要交换改变它们的值需要对【int**】去传入地址，传入什么地址呢，传入的就是【int*】的地址void Swap2(int** pp1, int** pp2)
{
int* tmp = *pp1;
*pp1 = *pp2;
*pp2 = tmp;
}
void test1()
{
int a = 2, b = 5;
int* p1 = &a, * p2 = &b;
printf("*p1 = %d, *p2 = %d\n", *p1, *p2);
Swap2(&p1, &p2);
printf("*p1 = %d, *p2 = %d\n", *p1, *p2);
}
*pp1 = p1】【 *pp2 = p2】，此时他们的指向都是相同的，存放的都是变量a和变量b的内存地址
函数调用结束内部变量随着栈帧的销毁而被释放，但是因为我传入的p1与p2的这两个一级指针的地址，所以函数内部就相当于获取到了这两个指针所指向的地址，实现了一个同一操作，因此函数内部的改变便带动了外界的p1和p2指向的改变，由下图便可看出但是我将这个二级指针有什么用呢？难道只是给你普及一下二级指针的知识吗，那当然不是，实际上就是为了通过这个二级指针接收以及结构体指针SList去真正地通过内部的修改改变外部的头结点指针，我们通过代码来看一下
//传二级指针
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
//通过二级指针的解引用改变头结点【从NULL->newnode】
}
else
{
SLTNode* pptail = *pphead;
while (pptail->next)
{
pptail = pptail->next;
//无需再使用二级指针，无需改变头结点，只需要做一个链接
//改变结构体的指向，使用结构体指针
}
pptail->next = newnode;
}
}
SLTNode* SList = NULL;
SListPushBack(&SList, 100);
SListPushBack(&SList, 200);
SListPushBack(&SList, 300);
PrintList(SList);
再来解释一下传参和链接的过程
一级指针类型的指针变量pptail去接收【 *pphead】，不断往后遍历，然后将两个结点通过【存放地址】的关系链接起来，就完成了我们的尾插操作二级指针接收一级指针的地址，以此使得函数内部和外部的指针都可以指向堆区中的同一块空间。而且对于函数的结构已经声明了是无法改变的，不能因为第一次需要改变头结点传入二级指针，但是在后面要无需用到二级指针就突然将这个pphead变为一级指针，这违背了编程的严谨性接下去一样再通过函数栈帧的形式来讲解一下，加深印象，帮助理解
*pphead = newnode】也让这个SList指向了100这个数据结点
对于尾插法，你学【废】会了吗😝
有尾插，那一定也有尾删，我们一起来探究一下🔍
void SListPopBack(SLTNode* phead)
{
SLTNode* ptail = phead;
while (ptail->next)
{
ptail = ptail->next;
}
free(ptail);
tail = NULL;
}
//way1
SLTNode* ptail = phead;
SLTNode* prev = NULL;
while (ptail->next != NULL)
{
prev = ptail;
ptail = ptail->next;
}
free(ptail);
prev->next = NULL;
//way2
SLTNode* ptail = phead;
while (ptail->next->next != NULL)
{
ptail = ptail->next;
}
free(ptail->next);
ptail->next = NULL;
void SListPopBack(SLTNode* phead)
{
if (phead->next == NULL)
{ //只有一个结点
free(phead);
phead = NULL;
}
else
{
SLTNode* ptail = phead;
while (ptail->next->next != NULL)
{
ptail = ptail->next;
}
free(ptail->next);
ptail->next = NULL;
}
}
二级指针👈
void SListPopBack(SLTNode** phead)
{
if ((*phead)->next == NULL)
{ //若只有一个结点，直接将其释放，传入二级指针便改变了链表的头结点
free(*phead);
*phead = NULL;
}
else
{
SLTNode* ptail = *phead;
while (ptail->next->next != NULL)
{
ptail = ptail->next;
}
free(ptail->next);
ptail->next = NULL;
}
}
void SListPopBack(SLTNode** phead)
{
assert(*phead);
if ((*phead)->next == NULL)
{ //若只有一个结点，直接将其释放，传入二级指针便改变了链表的头结点
free(*phead);
*phead = NULL;
}
else
{
SLTNode* ptail = *phead;
while (ptail->next->next != NULL)
{
ptail = ptail->next;
}
free(ptail->next);
ptail->next = NULL;
}
}
以上就是尾删法的最终版本，你又学【废】了吗😝
说完尾插和尾删，还有头插和头删，但是不要惊慌，对于头插和头删，没有你想象得那么复杂😵
一次*解引用即可。链接上后将这个新的头所存在的地址给到指向头结点的指针即可
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
newnode->next = (*pphead); //二级指针解引，变为一级指针
*pphead = newnode; //再让newnode变为新的头
}
void SListPopFront(SLTNode** pphead)
{
assert(*pphead); //删除都先断言一下，看看传进来的链表是否为空
SLTNode* nextNode = (*pphead)->next; //先保存当前首结点的下一个结点
free(*pphead);
(*pphead) = nextNode;
}
尾插、尾删、头插、头删。接下来我们要学习的是去链表中查找指定元素，先来看看接口定义SLTNode* SListFind(SLTNode* phead, SLTDataType x);
SLTNode* cur = phead;
//while (cur != NULL)
while (cur)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
//返回的是指向这个待查结点的指针，并不是位置
SLTNode* SList = NULL;
SListPushBack(&SList, 1);
SListPushBack(&SList, 2);
SListPushBack(&SList, 3);
SListPushBack(&SList, 4);
SListPushBack(&SList, 5);
PrintList(SList);
SLTNode* pos = SListFind(SList, 3);
if (pos != NULL) {
printf("找到了\n");
printf("pos = %d\n", pos->data);
}
else {
printf("没找到\n");
}
那有同学问，找到返回了这个值又能怎样呢，可以拿来做什么？那我告诉你这个用处可大了，后面我们将在找到的这个pos所指的结点之前、之后进行插入和删除相应的结点，都是要以这个Find接口作为前提
pos的next所指位置变化之后也就找不到4这个结点了，执行完第一条语句后pos的next就变成了newnode，这个时候再让newnode指向pos的next，也就是让newnode指向它自己，这也就不对了//pos的下一个位置就没了，相当于是newnode自己指向自己
pos->next = newnode;
newnode->next = pos->next;
newnode->next = pos->next;
pos->next = newnode;
SLTNode* pos = SListFind(SList, 88);
SListInsertAfter(pos, 9);
PrintList(SList);
放到一段程序的开头，而不是应该把它放在函数体的中间或者结尾，这点首先要明确；传入进来的某个参数变量，一般是去判断是否为空或者是否小于0。所以对于参数，你应该写入的是会报出错误的对立面，举个例子，当你想要检查a是否大于0，a小于0就会报错，因此应该写assert(a > 0)。若是去判断一个指针是否为空，就要这样写：assert(p != NULL)，或者直接简写成assert( p )，就像我们的while循环去判空是一个道理；assert的判断机制，就是当你所写的表达式不成立时，也就是当【p == NULL】时，就会出现警告，报出错误。在计算机中【0是假，非0才是真】，当【p = NULL】时，这个表达式就变为了假，非0一般指1，就是p != NULL，表明传进来的指针p不为空，那也就是不会满足条件
//0是假，非0才是真
assert(pos != NULL); //若不为空，则不会执行；若为空，则报出警告
//assert(pos);
哪个源文件的哪一行出了问题，也就是我们刚才写断言的地方，这个时候你立马可以进行【精确定位】然后排错，这个时候也就提高了程序的可维护性，所以作为我们程序员来说，学会使用断言是很重要的，但是断言并不是什么地方都可以随便加的，根据需求来加，也就是【因地制宜】，不然会出现麻烦，结尾总结的时候会说到📖
钱包是空的，于是这个时候就只能让你朋友付钱了【假设不支持手机支付】，那你说这个事情是不是很荒谬，assert断言其实就是在出门之前检查一下你有没有带钱，如果没有带那就会报出警告提醒你要带钱出门头插法，那既然是头插法，就需要去改变这个链表的头，所以又需要使用到二级指针void SListInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
if (*pphead == pos) {
//若pos位置就为原先的头结点，则使用头插法进行插入
SListPushFront(pphead,x);
}
else {
SLTNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
SLTNode* newnode = BuySLTNode(x);
//此处无需考虑前后错乱问题，直接链接即可
cur->next = newnode;
newnode->next = pos;
}
}
获取到外界SList这个头结点指针，然后去进行一个判断即可，若这个 *phead和pos相同，那表明所Find找到的pos就为链表的头结点。直接调用一下我们上面写过的头插法即可，实现了功能的复用，具体图示如下👇
要获取pos指针所指向的前一个位置，开头说到过，虽然单链表对于插入和删除很方便，但是访问结点并不方便，需要从头结点开始访问，于是还是一样的套路，定义一个cur指针首先获取到头结点指针的值，也就是把二级指针pphead解引用一下，然后一直去遍历即可，直到这个【cur->next = pos】为止停下来，表示当前cur所指向的结点所在的下一个位置便是pos，此时就可以做一个链接了，具体图示如下👇
看完了如何插入结点，接下去我们来说说如何在查找到的pos位置前后删除结点
void SListEraseAfter(SLTNode* pos)
pos->next】这块地址已经访问不到了，再去free的话也是徒劳pos->next = pos->next->next;
free(pos->next);
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
SLTNode* nextNode = pos->next;
if (nextNode == NULL){
return; //考虑到所查找到的结点为最后一个结点，后面无结点可删
}
else {
pos->next = nextNode->next;
free(nextNode);
}
}
free(pos->next);
pos->next = pos->next->next;
待删结点3的next域存放有结点4的地址，你讲它提前释放了，那pos怎么找得到呢❓此时【pos->next】就变成了一种我们都听说过的东西，叫做【野指针】，可能有小伙伴没听说过，也没关系，我们可以来了解一下👇不是确定的，而是随机的。通过阅读这篇文章，我也了解到了一些有关野指针的知识，但是这么理解起来比较晦涩难懂，因为还是按照我们的惯例，通过生活的一个小案例来帮助大家理解
没有登记入住但是却通过这把自己装配的钥匙进入了这个房间，又在里面住了一个晚上然后这个晚上刚好没什么客人，保洁阿姨也请假了，所以你又白嫖了一个晚上😊。于是你打算明天再来住一次，可是这一次，却有很大的祸患，晚上来了一个旅行团，于是很多房间都要重新打扫，然后就发现你还住在这里，就报警把你抓了起来👮通过这么一个案例，大家对野指针这一块应该有所了解了，所以不要轻易将指针乱指，可能那块地址就是随机的
free(pos->next);
pos->next = pos->next->next;
这个地址就不见了，而且数据值也变成了一个随机值，所以这个时候再去访问pos->next就是一个【野指针】了
所以大家在进行指针操作的时候一定要小心，可以一疏忽你的指针就变成了野指针🗡
void SListEraseBefore(SLTNode** pphead, SLTNode* pos)
第一种：pos就位于头结点位置
//当pos就为头结点时
if ((*pphead) == pos) {
return;
}
第二种：pos位于头结点的后一个位置，需要删除的便为头结点
else if ((*pphead)->next == pos) {
SListPopFront(pphead); //头删
}
第三种：正常情况，但是比较繁琐
要删除一个结点，就要找到它的前一个结点，因此这个时候我们需要定义一个结构体指针cur，刚开始指向【*pphead】，在不断往后遍历的时候当【cur->next->next == pos】时，定义一个指针指向当前cur的next，进行一个保存，接着执行【cur->next = delnode->next】，便可以进行一个删除void SListEraseBefore(SLTNode** pphead, SLTNode* pos)
{
assert(pos); //删除结点要断言
assert(*pphead);
//当pos就为头结点时
if ((*pphead) == pos) {
return;
} //当删除的结点为头结点时
else if ((*pphead)->next == pos) {
SListPopFront(pphead); //头删
}
else {
SLTNode* cur = *pphead;
while (cur->next->next != pos)
cur = cur->next;
SLTNode* delnode = cur->next;
cur->next = delnode->next;
free(delnode);
}
}
链表的每一个结点在堆内存中的空间是随机申请的。因此存储是不连续的，那对于释放来说，就需要从头结点开始，一一释放下去
void SLIstDestroy(SLTNode** pphead)
{
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* nextNode = cur->next;
free(cur);
cur = nextNode;
}
}
好，我们回归正题，既然这样会造成野指针，那应该怎么修改呢，那就是将和这个头结点指针置为NULL即可，这个时候再去打印的时候这个链表就是空的，也就不会出错了
SList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode { //结构体大小：8B
SLTDataType data;
struct SListNode* next;
//SLT* next; 不可以这样定义，因为还没有到声明
}SLTNode;
SLTNode* BuySLTNode(SLTDataType x);
SLTNode* SListCreate(int n);
void PrintList(SLTNode* phead);
void SListPushBack(SLTNode** phead, SLTDataType x);
void SListPopBack(SLTNode** phead);
void SListPushFront(SLTNode** pphead, SLTDataType x);
void SListPopFront(SLTNode** pphead);
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
void SListInsertAfter(SLTNode* pos, SLTDataType x);
void SListInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SListEraseAfter(SLTNode* pos);
void SListEraseBefore(SLTNode** pphead, SLTNode* pos);
void SLIstDestroy(SLTNode** pphead);
SList.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
//-----------------
/*动态开辟结点*/
SLTNode* BuySLTNode(SLTDataType x)
{
//动态开辟
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
}
//-----------------
/*建立链表*/
SLTNode* SListCreate(int n)
{
SLTNode* phead = NULL, * ptail = NULL;
for (int i = 0; i < n; ++i)
{
SLTNode* newnode = BuySLTNode(i);
if (phead == NULL)
phead = ptail = newnode;
else
{
ptail->next = newnode;
ptail = newnode;
}
}
return phead;
}
//-----------------
/*打印链表*/
void PrintList(SLTNode* phead)
{
//无需断言，链表为空，可以打印
SLTNode* cur = phead; //尽量不用头指针，定义变量存放【4 byte】
while (cur != NULL)
{
printf("%d->", cur->data);
//printf("[%d|%p]->", cur->data,cur->next);
cur = cur->next;
}
printf("NULL\n");
}
//-----------------
/*尾插*/
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
//无需断言，链表为空，可以尾插
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
//通过二级指针的解引用改变头结点【从NULL->newnode】
}
else
{
SLTNode* pptail = *pphead;
while (pptail->next)
{
pptail = pptail->next;
//无需再使用二级指针，无需改变头结点，只需要做一个链接
//改变结构体的指向，使用结构体指针
}
pptail->next = newnode;
}
}
//-----------------
/*尾删*/
void SListPopBack(SLTNode** phead)
{
assert(*phead); //必须断言，链表为空，不可尾删
if ((*phead)->next == NULL)
{ //若只有一个结点，直接将其释放，传入二级指针便改变了链表的头结点
free(*phead);
*phead = NULL;
}
else
{
SLTNode* ptail = *phead;
while (ptail->next->next != NULL)
{
ptail = ptail->next;
}
free(ptail->next);
ptail->next = NULL;
}
}
//-----------------
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
//无需断言，链表为空，可以头插
SLTNode* newnode = BuySLTNode(x);
newnode->next = (*pphead); //二级指针解引，变为一级指针
*pphead = newnode; //再让newnode变为新的头
}
//-----------------
//头删
void SListPopFront(SLTNode** pphead)
{
//必须断言，链表为空，不可头删
assert(*pphead); //删除都先断言一下，看看传进来的链表是否为空
SLTNode* next = (*pphead)->next; //先保存当前首结点的下一个结点
free(*pphead);
(*pphead) = next;
}
//-----------------
//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
//while (cur != NULL)
while (cur)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
//返回的是指向这个待查结点的指针，并不是位置
}
//-----------------
//在pos位置之后插入结点
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
//0是假，非0才是真
assert(pos != NULL); //若不为空，则不会执行；若为空，则报出警告
SLTNode* newnode = BuySLTNode(x);
//pos->next = newnode;
//newnode->next = pos->next;
//pos的下一个位置就没了，相当于是newnode自己指向自己
newnode->next = pos->next;
pos->next = newnode;
}
//-----------------
//在pos位置之前插入结点
void SListInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
if (*pphead == pos) {
//若pos位置就为原先的头结点，则使用头插法进行插入
SListPushFront(pphead,x);
}
else {
SLTNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
SLTNode* newnode = BuySLTNode(x);
//此处无需考虑前后错乱问题，直接链接即可
cur->next = newnode;
newnode->next = pos;
}
}
//-----------------
//删除pos位置之后的结点
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
SLTNode* nextNode = pos->next;
if (nextNode == NULL){
return; //考虑到所查找到的结点为最后一个结点，后面无结点可删
}
else {
//free(pos->next); //会产生野指针
//pos->next = pos->next->next;
pos->next = nextNode->next;
free(nextNode);
}
//-----------------
//删除pos位置之前的结点
void SListEraseBefore(SLTNode** pphead, SLTNode* pos)
{
assert(pos); //删除结点要断言
assert(*pphead);
//当pos就为头结点时
if ((*pphead) == pos) {
return;
} //当删除的结点为头结点时
else if ((*pphead)->next == pos) {
SListPopFront(pphead); //头删
}
else {
SLTNode* cur = *pphead;
while (cur->next->next != pos)
cur = cur->next;
SLTNode* delnode = cur->next;
cur->next = delnode->next;
free(delnode);
}
}
//-----------------
//释放链表
void SLIstDestroy(SLTNode** pphead)
{
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* nextNode = cur->next;
free(cur);
cur = nextNode;
}
*pphead = NULL;
}
test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <malloc.h>
#include "SList.h"
/* 顺序表缺陷
* 1.空间不够，需要扩容。扩容（尤其是异地扩容）是有一定代价的。其次还可能存在一定的空间浪费
* --》扩容都是扩2倍，扩得多了，一些不用空间的就会浪费
* --》扩得少了，插入一些数空间又不够了，又需要频繁的扩容
*
* 【吃米饭】一碗不够，吃两碗
* 吃一碗零20粒，频繁去锅里舀饭
*
* 2.头部或者中部插入删除，需要挪动数据，效率低下
*/
/* 优化方案
* 1.按需申请释放【要存储一个数据就开一块空间（结点）】
* 2.不要挪动数据【指针可以存放下一块空间的地址】
*/
/*
* 顺序表支持随机访问，可以根据下标快速访问到某个元素
* 链表不支持随机访问，只能通过头结点的next指针域一个个访问下去，最坏会到达O(N)
* 假设顺序表是货车，链表是公交车，都是不可替代的
*/
void TestSList1()
{
SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
n1->next = n2;
SListNode n3, n4;
n3.next = &n4;
}
void TestSList2()
{
/**/SLTNode* n1 = BuySLTNode(1);
SLTNode* n2 = BuySLTNode(2);
SLTNode* n3 = BuySLTNode(3);
SLTNode* n4 = BuySLTNode(4);
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;
SLTNode* SList = SListCreate(5);
PrintList(SList);
}
void Swap1(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void Swap2(int** pp1, int** pp2)
{
int* tmp = *pp1;
*pp1 = *pp2;
*pp2 = tmp;
}
void test1()
{
int a = 2, b = 5;
//printf("a = %d, b = %d\n", a, b);
//Swap1(&a, &b);
//printf("a = %d, b = %d\n", a, b);
int* p1 = &a, * p2 = &b;
printf("*p1 = %d, *p2 = %d\n", *p1, *p2);
Swap2(&p1, &p2);
printf("*p1 = %d, *p2 = %d\n", *p1, *p2);
printf("a = %d, b = %d\n", a, b);
}
//尾插
void TestSList3()
{
//SLTNode* SList = SListCreate(10);
//PrintList(SList);
//SListPushBack(SList, 100);
//SListPushBack(SList, 200);
//SListPushBack(SList, 300);
SLTNode* SList = NULL;
SListPushBack(&SList, 100);
SListPushBack(&SList, 200);
SListPushBack(&SList, 300);
PrintList(SList);
}
//尾删
void TestSList4()
{
SLTNode* SList = NULL;
SListPushBack(&SList, 100);
SListPushBack(&SList, 200);
SListPushBack(&SList, 300);
PrintList(SList);
SListPopBack(&SList);
PrintList(SList);
SListPopBack(&SList);
PrintList(SList);
SListPopBack(&SList);
PrintList(SList);
//再多删一次
SListPopBack(&SList); //访问越界
PrintList(SList);
}
//头插 — 头删
//void TestSList5()
//{
// SLTNode* SList = NULL;
// printf("尾插：");
// SListPushBack(&SList, 100);
// SListPushBack(&SList, 200);
// SListPushBack(&SList, 300);
// PrintList(SList);
//
// SLTNode* SList2 = NULL;
// printf("头插：");
// SListPushFront(&SList2, 100);
// SListPushFront(&SList2, 200);
// SListPushFront(&SList2, 300);
// SListPushFront(&SList2, 400);
// PrintList(SList2);
//
// printf("头删：\n");
// SListPopFront(&SList2);
// PrintList(SList2);
// SListPopFront(&SList2);
// PrintList(SList2);
// SListPopFront(&SList2);
// PrintList(SList2);
// SListPopFront(&SList2);
// PrintList(SList2);
//}
//查找与插入
void TestSList6()
{
SLTNode* SList = NULL;
SListPushBack(&SList, 1);
SListPushBack(&SList, 2);
SListPushBack(&SList, 3);
SListPushBack(&SList, 4);
SListPushBack(&SList, 5);
PrintList(SList);
//SLTNode* pos = SListFind(SList, 3);
//if (pos != NULL) {
// printf("找到了\n");
// printf("pos = %d\n", pos->data);
// SListInsertAfter(pos, 9);
// PrintList(SList);
//}
//else {
// printf("没找到\n");
//}
//SLTNode* pos = SListFind(SList, 88);
//SListInsertAfter(pos, 9);
//PrintList(SList);
//SLTNode* pos = SListFind(SList, 3);
//SListInsertAfter(pos, 9);
//PrintList(SList);
//SListInsertBefore(&SList, pos, 11);
//PrintList(SList);
SLTNode* pos = SListFind(SList, 1);
SListInsertBefore(&SList, pos, 8);
PrintList(SList);
}
//删除之后的结点
void TestSList7()
{
SLTNode* SList = NULL;
SListPushBack(&SList, 1);
SListPushBack(&SList, 2);
SListPushBack(&SList, 3);
SListPushBack(&SList, 4);
PrintList(SList);
SLTNode* pos = SListFind(SList, 2);
SListEraseAfter(pos);
PrintList(SList);
}
void TestSList8()
{
SLTNode* SList = NULL;
SListPushBack(&SList, 1);
SListPushBack(&SList, 2);
SListPushBack(&SList, 3);
SListPushBack(&SList, 4);
PrintList(SList);
//SLTNode* pos = SListFind(SList, 4);
SLTNode* pos = SListFind(SList, 2);
//SLTNode* pos = SListFind(SList, 1);
SListEraseBefore(&SList, pos);
PrintList(SList);
SLIstDestroy(&SList);
PrintList(SList);
}
void test()
{
int a = 'o';
printf("%d\n", a);
}
int main(void)
{
//TestSList2();
//test1();
//TestSList3();
//TestSList4();
//TestSList5();
//TestSList6();
//TestSList7();
TestSList8();
//test();
return 0;
}
不会修改头结点指针的，所以我们只需要以及指针就可以了一杯茶、一包烟、一个Bug改一天】，这个话其实不无道理，因为在一些大型项目中，若是出现了一个Bug，因为很多代码逻辑都是串联的，可能你修改了这个Bug，另一个地方又出了Bug，这个时候其实assert断言就可以帮助到我们很多，尤其是对于一些数组访问越界、野指针访问、空指针异常这些，若是你一步步去调试的话其实是很难找出来的，那用assert就很香了，马上就给你报出来，而且哪一个【.cpp】文件的哪一行都会告诉你，于是程序员们直呼：assert实在是太棒了删除算法的地方一般都会使用到assert，因为指针在不断前移或者后移的情况下可能造成越界访问，这个时候就会出现大问题了；pos】位置去删除其之前或之后的结点，对于这个传进来的【pos】指针可能是一个空指针，我们知道对空指针进行操作是很危险的一件事，所以也需要断言一下；二级指针接收的一级头结点指针吧，对于传进来的头结点指针我们也需要进行一个判断，尤其是在尾删或者头删链表的地方，若是这个链表本身就是空的，那么如何对其进行一个删除呢？这其实也是一种对空指针的违法操作。有关如何断言的操作我在前面已经讲过了，如还有不清楚的再去看看[对话框]去告诉他是否需要继续进行操作，再让他确认一下，这样显得其实是比较合理的，但若是你直接在这个地方给出一个断言，判断用户执行了这个操作就直接报错，那用户可能就会被你吓到了，影响用户的体验感以下题目请通过我另一个专栏【LeetCode算法题解】观看📺——题解更新中．<{=．．．．
最后，我们一起来回顾一下本文所学习的内容。除题解外，本文大概使用了
近四万字左右的篇幅详细讲解了单链表相关的知识点
尤其是头插和头删；对于【链表】，虽然在插入和删除这一块无需像顺序表那样，只要修改next指针域的指向即可，但是对于链表而言不支持随机访问，需要从头开始一一遍历才可访问到需访问元素OK，以上就是本文所要讲解的全部内容，非常感谢您的观看，如有问题请于评论区留言或者私信我🌺
我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i
有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳
给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最
我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_
无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD
本教程将在Unity3D中混合Optitrack与数据手套的数据流，在人体运动的基础上，添加双手手指部分的运动。双手手背的角度仍由Optitrack提供，数据手套提供双手手指的角度。 01 客户端软件分别安装MotiveBody与MotionVenus并校准人体与数据手套。MotiveBodyMotionVenus数据手套使用、校准流程参照：https://gitee.com/foheart_1/foheart-h1-data-summary.git02 数据转发打开MotiveBody软件的Streaming，开始向Unity3D广播数据；MotionVenus中设置->选项选择Unit
文章目录一、概述简介原理模块二、配置Mysql使用版本环境要求1.操作系统2.mysql要求三、配置canal-server离线下载在线下载上传解压修改配置单机配置集群配置分库分表配置1.修改全局配置2.实例配置垂直分库水平分库3.修改group-instance.xml4.启动监听四、配置canal-adapter1修改启动配置2配置映射文件3启动ES数据同步查询所有订阅同步数据同步开关启动4.验证五、配置canal-admin一、概述简介canal是Alibaba旗下的一款开源项目，Java开发。基于数据库增量日志解析，提供增量数据订阅&消费。Git地址：https://github.co
我正在尝试在Rails上安装ruby，到目前为止一切都已安装，但是当我尝试使用rakedb:create创建数据库时，我收到一个奇怪的错误:dyld:lazysymbolbindingfailed:Symbolnotfound:_mysql_get_client_infoReferencedfrom:/Library/Ruby/Gems/1.8/gems/mysql2-0.3.11/lib/mysql2/mysql2.bundleExpectedin:flatnamespacedyld:Symbolnotfound:_mysql_get_client_infoReferencedf
文章目录1.开发板选择*用到的资源2.串口通信（个人理解）3.代码分析（注释比较详细）1.主函数2.串口1配置3.串口2配置以及中断函数4.注意问题5.源码链接1.开发板选择我用的是STM32F103RCT6的板子，不过代码大概在F103系列的板子上都可以运行，我试过在野火103的霸道板上也可以，主要看一下串口对应的引脚一不一样就行了，不一样的就更改一下。*用到的资源keil5软件这里用到了两个串口资源，采集数据一个，串口通信一个，板子对应引脚如下：串口1，TX：PA9，RX：PA10串口2，TX：PA2，RX：PA32.串口通信（个人理解）我就从串口采集传感器数据这个过程说一下我自己的理解，