博客

p40 综合应用题

01.设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点。

问题分析：


（1）代码基础中我们删除结点使用的函数参数是头结点和x的值，因此想到递归实现本题时我们传递的参数应该是第一个元素结点和x的值，不断递归调用函数也就是传入的第一个元素节点值不断往后推进的过程，每次调用函数中在函数中处理第一个元素结点即可。

（2）再考虑递归函数，分为两部分：

第一部分是递归函数的终止条件。也就是说传入的第一个结点为NULL时递归停止，即传入链表为空。

第二部分是递归函数的主体，也就是对传入链表的处理。当传入的节点元素值为x，则删除改结点，将下一个结点传入函数进行下一层递归；当传入结点元素不等于x，则不需要对结点进行处理，直接用下一个结点作为参数进行下一层递归即可。


代码：

void delElemX(LNode *&L,ElemType x){
	LNode *p;//用于删除结点
	if (L==NULL)
		return;//若链表为空，递归终止
	if (L->data == x){
		p=L;
		L=L->next;
		free(p);//删除第一个元素结点
		delElemX(L,x);//下一层递归调用
	}else{
		delElemX(L->next,x);//不需要处理，直接进行下一层递归调用
	}
}

时间复杂度：

对每一个结点进行遍历一遍，递归层数等于结点数，时间复杂度为O(n)。

02.在带头结点的单链表L中，删除所有值为X的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。

问题分析：


本题是基础例题，只需要熟练掌握课程基础即可。对于插入删除结点的问题，如果需要用到遍历结点的前驱结点，初始化结点指针时通常设置初值为L，否则可以设置为L->next。


代码：

void delElemX(LNode *&L,ElemType x){
 LNode *p=L;//初始化结点
 while (p!=NULL){
 	if (p->next->data == x){
 		q = p->next;
 		p-next = p->next->next;
 		free(q);
 	}
 	p=p>next;
 }
}

时间复杂度：

对每一个结点进行遍历一遍，时间复杂度为O(n)。