当前位置：首页 > news >正文

创建全国文明城市建议简短优化网站

news 2025/7/19 10:23:45

创建全国文明城市建议简短,优化网站,wordpress视频页面模板,合肥市建设工程合同备案网站目录 1.链表的概念及结构 2.单链表功能的实现 2.1打印单链表 2.2创建节点 2.3单链表尾插 2.3单链表头插 2.5单链表尾删 2.6单链表头删 2.7单链表的查找 2.8在指定位置之前插入数据 2.9在指定位置之后插入数据 2.10删除pos节点 2.11删除pos之后的节点 2.12销毁链表…

1.链表的概念及结构

2.单链表功能的实现

2.1打印单链表

2.2创建节点

2.3单链表尾插

2.3单链表头插

2.5单链表尾删

2.6单链表头删

2.7单链表的查找

2.8在指定位置之前插入数据

2.9在指定位置之后插入数据

2.10删除pos节点

2.11删除pos之后的节点

2.12销毁链表

3.完整代码

SList.h

SList.c

1.链表的概念及结构

线性表的逻辑结构属于线性结构，采用顺序存储结构为顺序表，采用链式存储结构为线性链表。

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表的结构跟火车车厢相似，淡季时火车的车厢会相应减少，旺季时火车的车厢会额外增加几节。只需要将某节车厢去掉或者加上，不影响其他车厢，每节车厢都是独立存在的。

且每节车厢都有车门，假设每节车厢的车门都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带一把钥匙的情况下如何从车头走到车尾？ 最简单的做法：每节车厢里都放一把下一节车厢的钥匙。

在链表里，每节“车厢”是什么样的呢？

与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点/节点” ，节点的组成主要有两个部分：要保存的数据和下一个节点的地址（指针变量）。

图中指针变量 plist保存的是第一个节点的地址，我们称plist此时“指向”第一个节点，如果我们希望plist“指向”第二个节点时，只需要修改plist保存的内容为0x0012FFA0。

为什么还需要指针变量来保存下一个节点的位置？

链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），通过指针变量保存下一个节点位置才能从当前节点找到下一个节点。

注意：

链式结构在逻辑上是连续的，在物理结构上不一定连续。
节点一般是从堆上申请的。
从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续。

2.单链表功能的实现

2.1打印单链表

void SLPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur)//pcur!=NULL{printf("%d->", pcur->data);pcur = pcur->next; //将指针指向下一个节点}printf("NULL\n");
}

2.2创建节点

单链表每次插入都需要插入一个节点，所以我们最好写一个创建节点的函数方便后续调用。

SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL)  //申请失败{perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

2.3单链表尾插

尾插时需要找到最后一个节点的位置，再插入数值，但是要注意假如传进来一个空链表，ptail=NULL；那么对它进行找尾操作势必会造成ptail->next这句代码对空指针进行解引用，所以分成两种情况：

1.如果链表为空，直接插入即可。

2.如果链表不为空，需要找到尾节点再插入。

输出结果：

我们发现输出结果不是1，而是NULL，这是为什么呢？

SLTPushBack(plist, 1);

一级指针不能实现的原因：传参的时候另外创建一个一级指针phead接收plist传过来的值，它和plist指针一样指向NULL（这里属于传值调用，虽然plist变量存储的值是地址），尾插数据后，再让phaed指针指向newnode,在此期间plist仍然指向NULL，没有发生任何改变，因为形参的改变无法影响实参，调用链表打印函数，打印字符NULL。

当链表为空时，一开始plist指向空指针，然后需要plist指向newnode，需要改变plist的指向，这里用一级指针是实现不了的，需要用二级指针，二级指针才能改变一级指针plist的指向。若链表不为空，不需要改变plist的指向，程序依然可以正常运行。

小贴士

一级指针的作用 : 将普通变量的一级指针传入函数作为参数 ,可以在函数中访问该一级指针指向的普通变量, 并且可以修改该普通变量的值,但是该普通变量所在内存地址不能被修改。

传参的时候传一级指针变量的地址&plist，使用pphead二级指针来接收：

尾插代码

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);  //不能传空指针，不能对空指针进行解引用//空链表和非空链表SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL)    //*pphead是指向第一个节点的指针{*pphead = newnode;}else{//找尾SLTNode* ptail =*pphead;while (ptail->next)//ptail->next!=NULL{ptail = ptail->next;}//ptail指向的就是尾节点ptail->next = newnode;}	
}

2.3单链表头插

头插数据需要改变一级指针plist的指向，这里也需要二级指针改变一级指针plist的指向。

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead; //将newnode和头结点连接在一起*pphead = newnode;       //将链表头结点指向新的头
}

2.5单链表尾删

与单链表尾插类似，当链表只有一个头结点时需要将plist置为空，所以也需要二级指针。

void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);//链表不能为空//链表只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//链表有多个节点SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next)   //找尾节点{prev = ptail;ptail = ptail->next;}free(ptail);	//释放掉ptail指向的空间ptail = NULL;prev->next = NULL;//将ptail前一个节点next指针置为空，防止野指针}
}

2.6单链表头删

先创建一个指针next,保存第二个节点的位置，防止释放头结点导致找不到第二个节点。

void SLPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);//链表不能为空SLTNode* next = (*pphead)->next;//保存第二个节点free(*pphead);*pphead = next; //第二个节点作为链表新头，头指针走到新头的位置
}

2.7单链表的查找

查找数据不需要改变指针plist的指向，这里使用一级指针传参即可。如果找到就返回这个节点的地址，否则就返回空指针NULL。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;//再定义一个指针，phead指针可能后续还要用，不希望改变phead指针while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//pcur==NULL  没有找到！return NULL;
}