单项链接的接口问题
3.13 添加结点至任意位置前示意图
显然,只要获得某一结点的前驱,即可使用slist_add()函数添加结点至某一结点前面。为此,需要提供一个获得某一结点前驱的函数,其函数原型(slist.h)为:
slist_node_t *slist_prev_get (slist_head_t *p_head, slist_node_t *p_pos);
其中,p_head指向链表头结点,p_pos指向的结点表明查找结点的位置,返回值即为p_pos指向结点的前一个结点。由于在单向链表的结点中没有指向其上一个结点的指针,因此,只有从头结点开始遍历链表,当某一结点的p_next指向当前结点时,表明其为当前结点的上一个结点,函数实现详见程序清单3.25。
程序清单3.25 获取某一结点前驱的范例程序
1 slist_node_t *slist_prev_get (slist_head_t *p_head, slist_node_t *p_pos)
2 {
3 slist_node_t *p_tmp = p_head; // 指向头结点
4 while ((p_tmp != NULL) && (p_tmp->p_next != p_pos)) { // 找到p_pos指向的结点
5 p_tmp = p_tmp->p_next;
6 }
7 return p_tmp;
8 }由此可见,若p_pos的值为NULL,则当某一结点的p_next为NULL时就会返回,此时返回的结点实际上就是尾结点。为了便于用户理解,可以简单封装一个查找尾结点的函数,其函数原型为:
slist_node_t *slist_tail_get (slist_head_t *p_head) ;
其函数实现详见程序清单3.26。
程序清单3.26 查找尾结点
1 slist_node_t *slist_tail_get (slist_head_t *p_head)
2 {
3 return slist_prev_get(p_head, NULL);
4 }由于可以直接通过该函数得到尾结点,因此当需要将结添加点至链表尾部时,也就无需再自行查找尾结点了,修改slist_add_tail()函数的实现详见程序清单3.27。
程序清单3.27 查找尾结点
1 int slist_add_tail (slist_head_t *p_head, slist_node_t *p_node)
2 {
3 slist_node_t *p_tmp = slist_tail_get(p_head); // 找到尾结点
4 return slist_add(p_head, p_tmp, p_node); // 添加结点至尾结点之后
5 }与添加一个结点对应,也可以从链表中删除某一结点。假定链表中已经存在3个结点,现在要删除中间的结点,则删除前后的链表变化详见图3.14。
显然,删除一个结点也需要修改两个指针的值:既要修改其上一个结点的p_next,使其指向待删除结点的下一个结点,还要将删除结点的p_next设置为NULL。
删除结点的函数原型(slist.h)为:
int slist_del (slist_head_t *p_head, slist_node_t *p_node);
其中,p_head指向链表头结点,p_node为待删除的结点,slist_del()函数的实现详见程序清单3.28。
程序清单3.28 删除结点范例程序
1 int slist_del (slist_head_t *p_head, slist_node_t *p_node)
2 {
3 slist_node_t *p_prev = slist_prev_get(p_head, p_node);// 找到待删除结点的上一个结点
4 if (p_prev) {
5 p_prev->p_next = p_node->p_next;
6 p_node->p_next = NULL;
7
周立功 相关文章:
- 电源软启动的实用设计技巧(07-16)
- 周立功:动态分布内存——malloc()函数与calloc()函数(07-22)
- 周立功“程序设计与数据结构”:深度解剖动态分布内存的free()函数与realloc()函数(07-25)
- 周立功教你学程序设计技术:做好软件模块的分层设计,回调函数要这样写(07-30)
- 周立功教你学C语言编程:教你数组是如何保存指针的(07-31)
- 算法的泛化问题,这些坑你可能都经历过!|周立功教你学软件设计(08-01)