问题:
发现并修复下面C/C++函数中的缺陷,该函数是想从一个单向链表中删除头元素。
void removeHead(Node *head)
{
delete head;
head = head->next;
}
解答:缺陷发现策略:对于拿到的任何函数,考虑下面4个常见的问题:
1)检查数据是否正确地进入了该函数;
2)检查函数的每一行是否能正确工作;
3)检查该函数的输出数据是否正确;
4)检查常见的错误情况,如以指针为参数的函数在传入空指针时会失败。
函数释放了head之后,有对head进行引用,错误;我们试着将这两行颠倒位置,就会导致head之后的元素被删除,而不是head。因此正确的方法是利用一个临时变量:
void removeHead(Node *head)
{
Node *tmp = head->next;
delete head;
head = tmp;
}
现在我们进行上面策略的第三步,即确保函数返回正确的值,可以看出,这个函数尽管没有显式地返回值,但却有隐式的返回值。这个函数支持对head指针进行更新。在C语言中,所有参数都是按值传递的,所以函数会得到每一个参数的本地拷贝,而对本地拷贝的任何修改都不会对函数体之外产生影响。即上面代码第三行对head赋的任何新值都不会有效。要修复这个缺陷,我们需要一种能修改调用代码中head指针的方法。在C语言中,变量不能按引用传递,所以解决方案就是传递一个我们想修改的变量的指针,也就是head指针的指针,改动后,代码如下:
void removeHead(Node **head)
{
Node *tmp = (*head)->next;
delete *head;
*head = tmp;
}
接下来,我们检查边界条件。在只有1个元素的链表中,这个函数能正常工作,它删除了这个元素并将head指针设为了NULL。在0个元素的链表中,这个链表本身就是一个NULL指针,因此,head指针是NULL,上面代码中第一行错误地引用了NULL指针。因此,应该检查head指针是否为NULL,最终完善的函数如下:
void removeHead(Node **head)
{
Node *tmp;
if( !(*head) )
{
tmp = (*head)->next;
delete *head;
*head = tmp;
}
}
分享到:
相关推荐
Java算法实例-双向链表操作,封装性高,考试、学习都可使用
python算法-数组和链表 数组和链表.pdf
通过链表实现几种排序算法,并比较它们的优劣。
数据结构的双链表算法:双链表基本运算插入前插入后,循环双链表的基本运算。用C++语言写的控制台程序。
算法__链表的操作
数据结构-基本算法-孩子兄弟链表(学生时代源码,调试可运行)
c语言链表的排序算法-排序链表最快的算法是什么?.pdf
一个java实例,用来描述java算法中链表的使用。
设计算法判断单循环链表是否每个结点的值都是偶数,建立链表,判断,显示。 对任意输入的一组数据,建立一个递增有序的单链表。 将单链表L中的奇数项和偶数项结点分解开,并分别连成一个单链表。 用递增有序的链表A...
链表结点插入算法
算法学习:双向链表的创建和读取
逐字符读取键盘输入的合法字符串,并依次插入到双向链表中。具体的,对于当前读取的字符, 构造其对应的结点。 利用头插法(或尾插法)将该结点按照键盘输入的顺序插入到双向链表中。 3、判断双向链表中各节点...
算法-数据结构之链表合并算法.rar
这是一个关于链表算法的类,里面收集的算法还是比较全面的,当然,由于本人水平有限,可能在算法中存在一些错误,欢迎大家指正
算法笔记,有序链表转为二叉搜索树
C++经典算法 双向链表 采用了结构体,链表的知识。
5)查找操作:查找值为x的元素在单链表中出现的位置(是链表中的第几个元素)。 3、 为便于观察程序的运行结果,设计的输出函数能在输出设备上以图形或表格或其它直观的形式输出计算结果。例如可将链表输出成如下...
《数据结构与算法》-李春葆 实验报告-基于邻接链表存储的无向图形算法实践-邻接链表
代码主要实现了顺序表 链表 双链表的增删查改操作及链表逆置等常用线性表算法
这个问题的关键在于如何有效地遍历和比较链表中的元素,以实现最优的合并结果。 算法思路 针对这个问题,我们可以采用分治法的思路。首先将多个有序链表两两合并,然后再将这些合并后的链表进行一次合并,直到只剩下...