线性表应用

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

设函数f（L,x）是删除以L为首结点的单链表中所有值等于x的结点，f（L->next,x）的功 能是删除以L->next为首结点的单链表所有值等于x的结点。由此，推出递归模型。
终止条件：L为空表 f(L,x)不作操作
递归主体：L->data==x f(L,x)删除*L结点；f(L->next,x);
L->data!=x f(L,x)执行 f(L->next,x);

void delete(LinkList &L,ElemType x){
//递归实现单链表L中删除值为x的结点
	LNode *p;   //p用于指向待删除结点
	if(L==NULL)   //中止条件
		return;
	if(L->data==x){  //若L所指结点的值为x
		p=L;		 //	删除*L，并让L指向下一结点
		L=L->next;
		free(p);
		delete(L,x); //递归调用	
	}
	else					//若L所指结点的值不为x
		delete(L->next,x); //递归调用
}

方法一：用p从头至尾扫描单链表，pre指向*p结点的前驱。若p所指结点的值为x，则删除，并让p移向下一个结点，否则让pre，p指针同步后移一个结点。

void delete(Linklist &L,ElemType x){
	LNode *p=L->next,*pre=L,*q; //置p和pre的初始值
	while(p!=NULL){
		if(p->data==x){
			q=p;      //q指向待删除结点
			p=p->next;
			pre->next=p;//删除*q结点
			free(q);    //释放*q结点的空间	
		}
		else{			//不为x,pre和p同步后移
			pre=p;
			p=->next;
		}
	}
}