目录
1.查找数据
2.指定位置插入和删除节点
2.1 指定位置之前插入节点
2.2 指定位置之后插入节点
2.3 删除指定位置节点
2.4 删除指定位置之后的节点
3.销毁链表
我们接着上一篇【数据结构】单链表(一)-CSDN博客 来继续实现单链表
1.查找数据
在SList.h中进行函数的声明
SLNode* SLfind(SLNode* pps, Type x);//查找
返回值是一个地址,如果找到,就返回这个数的地址,如果没找到,就返回NULL,参数就是链表首节点地址和要查找的数
在SList.c中进行函数的实现
首先我们可以再定义一个指针存放首节点地址,这样的话在后面的遍历链表时就不会改变pps的指向了
SLNode* SLfind(SLNode* pps, Type x)//查找
{
SLNode* pcur = pps;//新定义一个指针,指向首节点
}
然后就是循环遍历
SLNode* SLfind(SLNode* pps, Type x)//查找
{
SLNode* pcur = pps;//新定义一个指针,指向首节点
while (pcur)//pcur不能为空
{
if (pcur->data == x) //找到
return pcur;//直接返回地址
pcur = pcur->next;//没找到往后找
}
}
当跳出while循环时,证明没找到,此时pcur为空,我们直接返回NULL
SLNode* SLfind(SLNode* pps, Type x)//查找
{
SLNode* pcur = pps;//新定义一个指针,指向首节点
while (pcur)//pcur不能为空
{
if (pcur->data == x) //找到
return pcur;//直接返回地址
pcur = pcur->next;//没找到往后找
}
return NULL;//没找到
}
在test.c中测试一下
void SListtest3()
{
SLNode* plist = NULL;//空链表
SLPushBack(&plist, 1);//尾插
SLPushBack(&plist, 2);
SLPushHead(&plist, 6);//头插
SLPushHead(&plist, 7);
SLPrint(plist);//打印
SLNode* find = SLfind(plist, 2);
if (find == NULL)
printf("没找到\n");
else
printf("找到了\n");
}
int main()
{
//SListtest1();
//SListtest2();
SListtest3();
return 0;
}
自己测试的时候可以多测几次
2.指定位置插入和删除节点
上一篇我们说了头部尾部的插入和删除数据,现在我们来实现一下指定位置的插入和删除数据
2.1 指定位置之前插入节点
在SList.h中进行函数的声明
void SLInsert(SLNode** pps, SLNode* pos, Type x);//指定之前插
参数有三个:链表首节点的地址,指定的位置,要插入的数据
在SList.c中进行函数的实现
现在我们要在节点3前面插入一个节点,就要让节点2里面的next指向新节点,新节点里面的next指向节点3
我们先找pos的前一个结点 ,用循环遍历
void SLInsert(SLNode** pps, SLNode* pos, Type x)//指定之前插
{
assert(pps && *pps);
assert(pos);
SLNode* prev = *pps;//再定义一个指针变量初始指向首节点
while (prev->next != pos)
{
prev = prev->next;
}
}
跳出循环后此时prev指向pos前一个节点,然后让这些节点“手牵手”
void SLInsert(SLNode** pps, SLNode* pos, Type x)//指定之前插
{
assert(pps && *pps);
assert(pos);
SLNode* newnode = SLBuyNode(x);//插入的数据
SLNode* prev = *pps;//再定义一个指针变量初始指向首节点
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
代码写到这里我们在分析一下pos为1时可不可行
这种情况下prev会一直往后走,直到走到最后一个节点,上面的代码在次情况下行不通
我们再分析一下pos为最后一个节点时可不可行
依旧是让节点3里面的next指向新节点,新节点里面的next指向节点4
经分析,上面的代码在这种情况下可行,所以不可行的就是pos为1的情况,我们单独把这种情况列出来,其实pos为1时也就是头插的情况
void SLInsert(SLNode** pps, SLNode* pos, Type x)//指定之前插
{
assert(pps && *pps);
assert(pos);
SLNode* newnode = SLBuyNode(x);//插入的数据
if (pos == *pps)
{
SLPushHead(pps, x);//直接调用头插代码
}
else//其他位置
{
SLNode* prev = *pps;//再定义一个指针变量初始指向首节点
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}
这就是完整的代码
在test.c中测试一下
void SListtest3()
{
SLNode* plist = NULL;//空链表
SLPushBack(&plist, 1);//尾插
SLPushBack(&plist, 2);
SLPushHead(&plist, 6);//头插
SLPushHead(&plist, 7);
SLPrint(plist);//打印
SLNode* find = SLfind(plist, 2);//找2
SLInsert(&plist, find, 11);//直接插在2前面
SLPrint(plist);//打印
}
int main()
{
SListtest3();
return 0;
}
看结果
其他情况有疑惑的话一定要自己测试运行一下
2.2 指定位置之后插入节点
在SList.h中进行函数的声明
void SLAfter(SLNode* pos, Type x);//指定之后插
这里只有两个参数,一个是指定位置,一个是要插入的值,这里我们不需要知道头节点,因为可以通过pos找到下一个节点,在指定位置之前插入数据的函数需要头节点是因为我们不能通过pos找到pos的前一个节点
在SList.c中进行函数的实现
void SLAfter(SLNode* pos, Type x)//指定之后插
{
assert(pos);
SLNode* newnode = SLBuyNode(x);//插入的数据
newnode->next = pos->next;
pos->next = newnode;
}
注意: newnode->next = pos->next; pos->next = newnode;这两句代码的顺序不可以交换,交换后是错的
在test.c中测试一下
void SListtest3()
{
SLNode* plist = NULL;//空链表
SLPushBack(&plist, 1);//尾插
SLPushBack(&plist, 2);
SLPushHead(&plist, 6);//头插
SLPushHead(&plist, 7);
SLPrint(plist);//打印
SLNode* find = SLfind(plist, 2);//找2
SLInsert(&plist, find, 11);//直接插在2前面
SLPrint(plist);//打印
SLAfter(find, 5);//插在2后面
SLPrint(plist);//打印
}
int main()
{
SListtest3();
return 0;
}
代码没有问题
2.3 删除指定位置节点
在SList.h中进行函数的声明
void SLErase(SLNode** pps, SLNode* pos);//删除pos节点
参数是二级指针,接收首节点地址,还有一个参数是要删除的节点
在SList.c中进行函数的实现
我们要先让pos的前一个节点指向pos的后一个节点,然后把pos这个节点销毁
既然要找pos的前一个节点,我们依旧是定义一个指针prev,初始为*pps,往后一个一个找,直到找到pos前一个节点
void SLErase(SLNode** pps, SLNode* pos)//删除pos节点
{
assert(pps && *pps);
assert(pos);
SLNode* prev = *pps;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
如果此时链表只有一个节点,上面的代码可行吗?来分析一下
发现代码走不通,其实这种情况就是头删的情况,我们直接调用头删的代码就可以了
void SLErase(SLNode** pps, SLNode* pos)//删除pos节点
{
assert(pps && *pps);
assert(pos);
if (pos == *pps)//一个节点
{
SLPopHead(pps);
}
else//多个节点
{
SLNode* prev = *pps;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
在test.c中测试一下
void SListtest3()
{
SLNode* plist = NULL;//空链表
SLPushBack(&plist, 1);//尾插
SLPushBack(&plist, 2);
SLPushHead(&plist, 6);//头插
SLPushHead(&plist, 7);
SLPrint(plist);//打印
SLNode* find = SLfind(plist, 7);//找7
SLErase(&plist, find);//删除指定位置节点
SLPrint(plist);//打印
}
int main()
{
SListtest3();
return 0;
}
删除成功
2.4 删除指定位置之后的节点
在SList.h中进行函数的声明
void SLPushAfter(SLNode* pos);//删除pos之后的节点
pos的后一个节点我们可以直接通过pos找到,就不需要头节点地址,所以一个参数就好了
在SList.c中进行函数的实现
还是先让pos这个节点找到它的下下个节点,然后再销毁pos后面的节点
这里呢我们需要一个临时变量存放pos->next的地址,然后再连接节点
我们先写一下代码,让pos和pos下下个节点相连
void SLPushAfter(SLNode* pos)//删除pos之后的节点
{
assert(pos);
assert(pos->next);
SLNode* temp = pos->next;
pos->next = temp->next;
}
然后销毁pos下一个节点并置空
void SLPushAfter(SLNode* pos)//删除pos之后的节点
{
assert(pos);
assert(pos->next);
SLNode* temp = pos->next;//临时变量
pos->next = temp->next;//连接
free(temp);//销毁
temp = NULL;//置空
}
在test.c中测试一下
void SListtest3()
{
SLNode* plist = NULL;//空链表
SLPushBack(&plist, 1);//尾插
SLPushBack(&plist, 2);
SLPushHead(&plist, 6);//头插
SLPushHead(&plist, 7);
SLPrint(plist);//打印
SLNode* find = SLfind(plist, 7);//找7
SLPushAfter(find);//删除指定位置后一个节点
SLPrint(plist);//打印
}
int main()
{
SListtest3();
return 0;
}
3.销毁链表
跟顺序表一样,链表使用完之后也要销毁,链表由一个一个节点组成,所以也要一个一个销毁
在SList.h中进行函数的声明
void SLDestroy(SLNode** pps);//销毁
参数就是首节点地址
在SList.c中进行函数的实现
我们在销毁当前节点之前要把下一个节点的信息存起来
销毁空间
pcur后移到提前保存的next处
然后next后移,把当前的pcur销毁
就这样一直往后,直到pcur为空
代码来实现一下
void SLDestroy(SLNode** pps)//销毁
{
assert(*pps && pps);
SLNode* pcur = *pps;
while (pcur)
{
SLNode* next = pcur->next;//存下节点信息
free(pcur);//释放
pcur = next;//往后走
}
*pps = NULL;//不要忘了头节点此时没有置空,要置空
}
在test.c中测试一下
void SListtest3()
{
SLNode* plist = NULL;//空链表
SLPushBack(&plist, 1);//尾插
SLPushBack(&plist, 2);
SLPushHead(&plist, 6);//头插
SLPushHead(&plist, 7);
SLPrint(plist);//打印
SLDestroy(&plist);//销毁
SLPrint(plist);//打印
}
int main()
{
SListtest3();
return 0;
}
可以自己通过调试看结果,能看到更详细,打印出来看也可以
单链表实现就分享到这里,拜拜~