本文共 1097 字,大约阅读时间需要 3 分钟。
题目:设计一个递归算法,删除不带头结点的单链表L中所有值为x的结点。
分析:递归算法,函数调用函数本身。
单链表,每个结点只有指针指向下一个结点。删除结点:找到这个结点,前一个结点指向它后一个结点,删除这个结点。
void Del_x_recursion(Linklist &L, int x) //&引用,指向链表L的地址 { if(L==NULL) return; //递归出口,函数类型void,不用返回值 if(L->data != x) //若L所指结点的值不为x { Del_x_recursion(L->next, x); //指针移到下一个位置,递归调用 return; } //if(L->data == x) 这里不用if语句,因为执行到这儿,肯定是这种情况 LNode *p; //定义一个单链表结点p p=L; //p也指向待删除结点,等下删除这个结点 L=L->next; //L指向链表的第一个元素,现在L指向下一个结点,就是不管这个结点了 delete p; //L和这个结点没关系了,还有p标记指向这个结点,现在删除这个结点 Delete_x_recursion(L,x); //L已经指向下个结点,这个结点也删除了,继续递归调用 }
解析:
这里为什么不用写代码,让当前删除结点的上一个结点指向当前删除结点的下一个结点?不会断链吗?
Del_x_recursion(L->next, x); //指针移到下一个位置,递归调用void Del_x_recursion(Linklist &L, int x) //&引用,指向链表L的地址
因为上一层结点L->next就是这一层的L。它们是完全一样的。
这一层的L指向哪儿,上一层的L->next就指向哪儿。不用写出来了。