数据结构学习 (三) -在单链表中删除结点

在单链表中删除指定结点的两种算法：

一般思想：

1. 扫描单链表，定位指定结点位置；
2. 由于删除此结点需运用到该结点与其前驱结点，需两个指针 q, p 分别指向它们；

算法一：在带表头的单链表中删除元素值为 e 的结点

int delete_withHead(Linklist head, ElemType e)
{
struct node *q, *p;
q = head;
p = head->next;				//  q,p 扫描
while(p && p->data!= e)		// 查找元素为 e 的结点
{
q = p;						// 记住前一个结点
p = p->next;				// 查找下一个结点
}

if(p)						// 元素有为 e 的结点
{
q->next = p->next;			// 删除该结点
free(p);					// 释放结点所占的空间
return YES;
}
else	return NO;
}

算法二：在带表头的单链表中删除指定位置的元素

int delete_withHead(Linklist &L, int i, ElemType &e)
{
p=L;
int j = 1;
while(p->next && j<i)		// 循环结束时p 不可能为空
{
p = p->next;				// p 后移，指向下一个结点
j++;
}
if(i<1 || p->next==NULL)	return ERROR;	// 删除错误
}