做营销网站视频,中国建设教育协会的官方网站,小程序怎么做网站,淘宝pc端官网目录 1.单链表的物理结构 2.头文件的实现 3.SList.c文件的实现 3.1尾插、创建节点 3.2打印 3.3头插 3.4尾删 3.5头删 3.6查找 3.7指定位置之前插入数据 3.8指定位置之后插入数据 3.9删除指定位置节点 3.10删除pos之后的节点 3.11销毁链表 4 所有的代码 1.单链表的物理结构 众所… 目录 1.单链表的物理结构 2.头文件的实现 3.SList.c文件的实现 3.1尾插、创建节点 3.2打印 3.3头插 3.4尾删 3.5头删 3.6查找 3.7指定位置之前插入数据 3.8指定位置之后插入数据 3.9删除指定位置节点 3.10删除pos之后的节点 3.11销毁链表 4 所有的代码 1.单链表的物理结构 众所周知单链表是线性表的一种线性表是逻辑结构连续、物理结构不一定连续的结构我们的单链表就是逻辑上连续但物理结构上不一定连续的结构。 那么它的逻辑图长什么样呢如下图所示 上面的图片中我们展示的是一种无头单向不循环链表plist指针指向的就是单链表头节点的空间的地址。我们将每一个小方格称为节点每个节点的结构中包括数据值和指向下一个节点的地址。 上面的代码就是我们这无头单向不循环链表的结构我们重命名int型是为了以后改数据类型的时候不要改太多次只用在这一行把int换掉就可以了。然后我们把单链表结构体重命名也是为了我们书写方便。我们这里使用三个文件来实现无头单向不循环链表的内容。分别是test.c源文件用来测试代码的文件、SList.c源文件用来实现接口的文件、SList.h头文件用来进行接口的声明各种头文件的调用定义数据结构。最后我会把代码全部放上来那么我们开始来体会这个过程。 2.头文件的实现 #pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h//定义链表节点的结构
typedef int SLDataType;
typedef struct SListNode
{SLDataType data;//要保存的数据struct SListNode* next;
}SLNode;//创建几个节点组成一个链表并打印链表
void SLNPrint(SLNode* phead);
//尾插
void SLPushBack(SLNode** pphead, SLDataType x);
//头插
void SLPushFront(SLNode** pphead, SLDataType x);
//删除
void SLPopBack(SLNode** pphead);
void SLPopFront(SLNode** pphead);SLNode* SLFind(SLNode** pphead, SLDataType x);//指定位置的插入和删除//在指定位置之前插入数据
void SLInsert(SLNode** pphead,SLNode* pos,SLDataType x);
//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x);//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos);
//删除pos之后节点
void SLEraseAfter(SLNode* pos);
//销毁链表
void SListDesTroy(SLNode** pphead); 引用头文件我们就不多说了单链表的结构我们上面也讲过了接下来就来讲解一下声明这些接口的时候我们要注意的事项由于在test.c文件中我们定义的是SLNode*指针我们知道使用函数传参时形参是实参的一份临时拷贝所以为了修改我们的链表我们要传二级指针才能修改链表。 3.SList.c文件的实现 3.1尾插、创建节点 我们执行尾插前要先进行断言一下这是为了防止传进来一个空指针接下来就是创建节点 创建节点我们只需要传一个x值就可以了然后把返回值类型定位SLNode*型在这个接口中我们先用malloc开辟出一块空间然后再把x的值给到结构体中的data之后我们再把next指针置为NULL接下来就可以把节点指针返回了。 我们再回到上面创建好节点后我们还要看一看是否传进来的是空链表如果是的话我们把新的节点给头节点然后返回头节点如果不是空链表的话我们用pcur指针来遍历整个链表进行找尾操作找到尾指针之后我们把尾指针的next指向新的节点。 3.2打印 我们的尾插操作有没有成功可以通过两种方式一种是调试一种是打印出来看看粗略检查。 我们还是让pcur指针来进行遍历每遍历一个节点我们就打印一个节点最后打印一个NULL如果是空链表我们就会直接打印NULL。 这样我们就可以看出确实是尾插成功了。 3.3头插 头插的操作跟尾插差不多我们先断言指针是否为NULL不是的话我们创建一个新的节点这里我们注意一下顺序我们要先把新节点的next指向原来的头节点再把头节点指针指向新的节点倘若我们先进行把头节点指针指向新的节点我们就会发现我们找不到原来的头节点了这就是我们要注意的一个地方。 好让我们来看看效果 3.4尾删 尾删的操作我们不需要传入x值了只需要二级指针就行了第一步还是要进行断言我们这里我们还需要断言一下它的一级指针因为我们既然要进行删除操作我们的链表总不能是空链表吧接下来我们处理只有一个节点的情况只有一个节点的话我们直接把头节点空间释放地址指向空就可以了如果节点不只有一个我们就需要找尾节点和尾节点的前一个节点我们先创建一个ptail进行遍历ptail指向的是最后一个节点prev则是前一个节点我们把我们把将要成为尾节点的next指向原尾节点的next再把原尾节点的空间释放掉我们就完成了尾删的操作。 3.5头删 头删操作要简单的多它不需要考虑只有一个节点的情况跟尾删一样我们先断言两次然后创建一个del指针指向头节点然后将头节点指向新的头节点也就是原头节点的下一个节点然后把del释放掉我们再出于规范把这个野指针置为NULL。 3.6查找 这里我们查找的标准就定为查找是否有x这个元素然后我们的第一步还是断言之后创建一个pcur来遍历整个链表如果找到了就返回这个地址如果没有找到就返回NULL。 3.7指定位置之前插入数据 这里我们要多传一个参数pos因为pos就是我们的指定位置的节点。好我们开始断言断言之后我们创建新的节点然后处理只有一个节点的情况如果只有一个头节点我们就把新节点的next指向头节点然后再让头节点的指针指向新节点如果不只有一个节点那么我们就创建一个指针prev来找到pos节点的前一个然后把新节点的next指向pos再把原来的前一个节点的next指向新的节点。 3.8指定位置之后插入数据 这个操作我们就要简单的多我们先进行断言然后创建一个新的节点让新的节点的next指向pos节点的下一个节点再把pos的next指向新的节点。 3.9删除指定位置节点 老操作先进行断言如果我们删除的是头节点那么我们直接把头节点指向头节点的下一个节点然后释放pos返回无值就可以了如果不是头节点那么我们就要先创建一个prev指针来找pos的前一个节点把prev的next指向pos的下一个再释放掉pos就可以了我们也可以为了规范再把pos置为NULL。 3.10删除pos之后的节点 这个就要节点的多我们只需要断言一下pos和pos的下一个节点就行了然后我们再创建一个del指针指向pos的下一个节点然后把pos的next指向pos的下一个的下一个节点我们再释放掉del。 3.11销毁链表 我们进行一下断言再创建一个指针进行遍历每遍历一次就销毁一个节点。 4 所有的代码 //SList.h头文件#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h//定义链表节点的结构
typedef int SLDataType;
typedef struct SListNode
{SLDataType data;//要保存的数据struct SListNode* next;
}SLNode;//创建几个节点组成一个链表并打印链表
void SLNPrint(SLNode* phead);
//尾插
void SLPushBack(SLNode** pphead, SLDataType x);
//头插
void SLPushFront(SLNode** pphead, SLDataType x);
//删除
void SLPopBack(SLNode** pphead);
void SLPopFront(SLNode** pphead);SLNode* SLFind(SLNode** pphead, SLDataType x);//指定位置的插入和删除//在指定位置之前插入数据
void SLInsert(SLNode** pphead,SLNode* pos,SLDataType x);
//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x);//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos);
//删除pos之后节点
void SLEraseAfter(SLNode* pos);
//销毁链表
void SListDesTroy(SLNode** pphead); //SList.c源文件#define _CRT_SECURE_NO_WARNINGS 1
#include SList.hvoid SLNPrint(SLNode* phead)
{//循环打印SLNode* pcur phead;while (pcur){printf(%d -, pcur-data);pcur pcur-next;}printf(NULL\n);
}SLNode* SLBuyNode(SLDataType x)
{SLNode* node (SLNode*)malloc(sizeof(SLNode));node-data x;node-next NULL;return node;
}//尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* node SLBuyNode(x);if (*pphead NULL){*pphead node;return;}//说明链表不为空找尾SLNode* pcur *pphead;while (pcur-next){pcur pcur-next;}pcur-next node;
}
//头插
void SLPushFront(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* node SLBuyNode(x);//新节点跟头节点连接起来node-next *pphead;//让新的节点成为头节点*pphead node;
}
//删除
void SLPopBack(SLNode** pphead)
{assert(pphead);//第一个节点不能为空assert(*pphead);//只有一个节点的情况if ((*pphead)-nextNULL){//直接把头节点删除free(*pphead);*pphead NULL;}else{//找尾节点和尾节点的前一个节点SLNode* prev NULL;SLNode* ptail *pphead;while (ptail-next ! NULL){prev ptail;ptail ptail-next;}//prev的next指针不再指向ptail指向下一个节点prev-next ptail-next;free(ptail);ptail NULL;}}
void SLPopFront(SLNode** pphead)
{assert(pphead);assert(*pphead);SLNode* del *pphead;*pphead (*pphead)-next;free(del);del NULL;//出于代码规范
}SLNode* SLFind(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* pcur *pphead;while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{assert(pphead);//约定链表不为空pos也不能为空assert(pos);assert(*pphead);SLNode* node SLBuyNode(x);//处理只有一个节点pos指向第一个节点if (pos*pphead){node-next *pphead;*pphead node;return;}//找pos的前一个节点SLNode* prev *pphead;while(prev-next!pos){prev prev-next;}//prev node posnode-next pos;prev-next node;
}//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x)
{assert(pos);SLNode* node SLBuyNode(x);node-next pos-next;pos-next node;
}//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (pos *pphead){*pphead (*pphead)-next;free(pos);return;}//找pos的前一个节点SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;
}
//删除pos之后节点
void SLEraseAfter(SLNode* pos)
{assert(pospos-next);SLNode* del pos-next;pos-next del-next;free(del);
}//销毁链表
void SListDesTroy(SLNode** pphead)
{assert(pphead);SLNode* pcur *pphead;while (pcur){SLNode* next pcur-next;free(pcur);pcur next;}pcur NULL;
}
