宁夏网站制作,wordpress后台缓慢,网站搭建与服务器配置,毕业设计微信小程序开发在顺序表中实现数据的增删的操作时#xff0c;都要把操作位置之后的数据全部移动一遍#xff0c;操作效率低下。其次是容量固定#xff08;静态顺序表#xff09;#xff0c;虽然在动态顺序表中容量可变#xff0c;但也会造成空间上的浪费。
单链表就完美解决了上述缺点…在顺序表中实现数据的增删的操作时都要把操作位置之后的数据全部移动一遍操作效率低下。其次是容量固定静态顺序表虽然在动态顺序表中容量可变但也会造成空间上的浪费。
单链表就完美解决了上述缺点。
这里要说明一点单链表与顺序表没有哪个比哪个更好只有哪个更适应场合。
介绍完上述后现在开始单链表的实现实现单链表需要用到结构体指针。
链表中的节点都是动态开辟的空间是在堆上的并不会出了作用域就销毁如果在链表中找到值为1的节点那就把这个节点的地址返回将体现在指定位置插入删除的操作解决了为什么没有传址而传值的疑惑
创建结构体 typedef int SLTDataType;typedef struct SListNode SLTNode; typedef struct SListNode { SLTDataType data; SLTNode* next; }SLTNode; 结构体指针SLTNode*储存下一个节点可以理解为一条链条或套娃。直到最后一个节点的next指向空NULL时
需要注意的是这里SLTNode我进行了前置声明因此可以直接用转换后的语句。
如果没有前置声明STLNode不会被识别出来这里需要说一下操作系统在找SLTNode时只会向上找不会向向下找这也就是为什么有许多代码中会有前置声明的函数或者像当先操作的转换一样。 能直观的看到前置声明的重要性。
创建一个头文件SListNode.h用来放需要实现的函数声明
#include stdio.h
#include stdlib.h
#include assert.h
typedef int SLTDataType;
typedef struct SListNode SLTNode;
typedef struct SListNode
{SLTDataType data;SLTNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);创建SListNode.c文件用来实现头文件的函数
首先是尾插 //尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode)); newnode-data x; newnode-next NULL; //不能直接这样用*pphead-next NULL;加括号(*pphead)-next, 优先级问题 //链表为空 if (*pphead NULL) { *pphead newnode; } //链表不为空,找尾节点 SLTNode* node *pphead; while (node-next) { node node-next; } node-next newnode; } 使用SLTNode** pphead接收传递的phead是SLTNode*类型而我们需要改变phead的内容因此要传址而非传值故用二级指针接收。
在这里我想用*pphead-next可是会报错这是为什么呢因为优先级-的优先级比*的优先级高pphead先与-结合因此报错。
首先创建 节点结构体指针newnode保存需要插入的值然后要判断两种情况一种是*pphead为空时直接让*pphead等于newnode。第二种*pphead不为空创建一个node等于*pphead循环向后找找到node-next为空时node-next newnode。
头插的实现 //头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode)); newnode-data x; if (*pphead NULL) { *pphead newnode; newnode-next NULL; } else { SLTNode* ret *pphead; newnode-next ret; *pphead newnode; } } 头插跟尾插一样需要判断两种情况当*pphead为空和不为空的两种情况。为空直接等于不为空创建临时的ret保存*pphead然后让*pphead头节点等于newnode。
尾删的实现 //尾删 void SLTPopBack(SLTNode** pphead) { assert(*pphead); assert(pphead); if ((*pphead)-next NULL) { free(*pphead); *pphead NULL; } else { SLTNode* node *pphead; SLTNode* ret node-next; while (ret-next) { node node-next; ret ret-next; } free(ret); ret NULL; node-next NULL; } } 删除涉及到空间的释放。因此要判断*ppead和ppead是否为空不能传递一个空值来删除释放吧所以要用assert断言。
也是要判断两种情况一种是只有一个节点时另一种是多个节点时。当为一个节点时直接释放后置空即可当为多个节点时需要遍历到最后一个节点后进行删除。
头删的实现 //头删 void SLTPopFront(SLTNode** pphead) { assert(*pphead); assert(pphead); if ((*pphead)-next NULL) { free(*pphead); *pphead NULL; } else { SLTNode* node (*pphead)-next; free(*pphead); *pphead node; } } 头删和尾删还是差不多需要判断两种情况是否是一个节点或多个节点。一个节点直接删除即可多个节点将头节点指向第二个节点。
查找的实现 //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { assert(phead); SLTNode* node phead; while (node) { if (node-data x) { return node; } node node-next; } return NULL; } void SLTfind(SLTNode* phead, SLTDataType x) { SLTNode* ret SLTFind(phead, x); if (ret) { printf(找到了%d\n, ret-data); } else { printf(没找到%d\n, x); } } 先创建SLTFind函数返回需要查找的节点在指定位置操作时需要用到因此将查找节点的操作分割出来后用SLTfind判断。
在指定位置之前插入的实现 //指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(*pphead); assert(pphead); assert(pos); SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode)); newnode-data x; newnode-next NULL; if (pos *pphead) { SLTNode* node (*pphead); *pphead newnode; (*pphead)-next node; return; } SLTNode* prev *pphead; while (prev-next ! pos) { prev prev-next; } prev-next newnode; newnode-next pos; } 链表中的节点都是动态开辟的空间是在堆上的并不会出了作用域就销毁如果在链表中找到值为1的节点那就把这个节点的地址返回
pos节点用SLTFind函数寻找需要断言 pos是否为空要判断*ppead和ppead是否为空。
判断两种情况当插入节点为头节点时和不为头节点时。当插入节点为头节点时将头节点指向newnode。当不为头节点时创建prev使用while循环当 prev-nextpos时退出让prev的下个节点指向newnodenewnode的下个节点指向pos。
pos节点删除的实现 //删除pos节点 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(*pphead); assert(pphead); assert(pos); if (pos *pphead) { SLTNode* ret *pphead; *pphead (*pphead)-next; free(ret); ret NULL; return; } SLTNode* prev *pphead; while (prev-next ! pos) { prev prev-next; } SLTNode* node pos-next; prev-next node; free(pos); pos NULL; } SLTFind函数寻找pos节点判断两种情况pos是否为头节点然后进行删除操作。
在指定位置之后插入的实现 //在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode)); newnode-data x; newnode-next NULL; SLTNode* prve pos-next; pos-next newnode; newnode-next prve; } 这个更简单。
删除pos之后的节点的实现 //删除pos之后的节点 void SLTEraseAfter(SLTNode* pos) { assert(pos); SLTNode* prve pos-next; SLTNode* node prve; while (node) { node prve-next; free(prve); prve node; } pos-next NULL; } 找到pos后循环释放。
销毁链表的实现 void SListDesTroy(SLTNode** pphead) { assert(*pphead); assert(pphead); SLTNode* prve (*pphead); while(prve) { prve prve-next; free(*pphead); *pphead NULL; *pphead prve; } } 一样的循环释放。
下面是SListNode.c代码
#include SListNode.h//打印
void SLTPrint(SLTNode* phead)
{while (phead){printf(%d-, phead-data);phead phead-next;}printf(NULL\n);
}//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));newnode-data x;newnode-next NULL;//不能直接这样用*pphead-next NULL;加括号(*pphead)-next, 优先级问题//链表为空if (*pphead NULL){*pphead newnode;}//链表不为空,找尾节点SLTNode* node *pphead;while (node-next){node node-next;}node-next newnode;
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));newnode-data x;if (*pphead NULL){*pphead newnode;newnode-next NULL;}else{SLTNode* ret *pphead;newnode-next ret;*pphead newnode;}
}//尾删
void SLTPopBack(SLTNode** pphead)
{assert(*pphead);assert(pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* node *pphead;SLTNode* ret node-next;while (ret-next){node node-next;ret ret-next;}free(ret);ret NULL;node-next NULL;}
}//头删
void SLTPopFront(SLTNode** pphead)
{assert(*pphead);assert(pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* node (*pphead)-next;free(*pphead);*pphead node;}
}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* node phead;while (node){if (node-data x){return node;}node node-next;}return NULL;
}void SLTfind(SLTNode* phead, SLTDataType x)
{SLTNode* ret SLTFind(phead, x);if (ret){printf(找到了%d\n, ret-data);}else{printf(没找到%d\n, x);}
}//指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(*pphead);assert(pphead);assert(pos);SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));newnode-data x;newnode-next NULL;if (pos *pphead){SLTNode* node (*pphead);*pphead newnode;(*pphead)-next node;return;}SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next newnode;newnode-next pos;
}//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(*pphead);assert(pphead);assert(pos);if (pos *pphead){SLTNode* ret *pphead;*pphead (*pphead)-next;free(ret);ret NULL;return;}SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* node pos-next;prev-next node;free(pos);pos NULL;
}//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));newnode-data x;newnode-next NULL;SLTNode* prve pos-next;pos-next newnode;newnode-next prve;
}//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);SLTNode* prve pos-next;SLTNode* node prve;while (node){node prve-next;free(prve);prve node;}pos-next NULL;
}//销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(*pphead);assert(pphead);SLTNode* prve (*pphead);while(prve){prve prve-next;free(*pphead);*pphead NULL;*pphead prve;}
}
