一、题目

有些应用中允许线性表中存在有值相同的数据元素，设计一个算法，删除单链表中值为x的所有结点。

本题所使用的数据结构定义如下：typedef  int  ElemType ;

typedef  int  ElemType ;

单链表的数据结构定义：

typedef  struct  Lnode

{   ElemType  data;     /*  数据域，保存数据元素(结点的值)   */

struct   Lnode  *next;      /*  指针域  */

}LinkList;        /*  结点的类型   */

二、算法思路

1、定义指向首元结点的指针p，定义指向头结点的指针q，声明指针q为后续存放数据域与x相同的结点地址。

2、判断链表是否为空表，若为空表，则进行下一步操作。

3、若指针p不为空，则判断p->是否与x相等。

4、若p->与x相等，则将q指向要删除的结点，将指针p向后移动一个结点，改变pre指针域的指向，使q从链表中删除，释放q。

5、若p->与x不相等，将指针p向后移动一个结点，将指针pre向后移动一个结点。

6、重复345步骤，直到p为空为止。

三、程序实现

void Delete(LinkList* L, ElemType x) {
	// L为带头结点的链表
	LinkList* p = L->next, * pre = L, *q;
	if (p == NULL)
	{
		printf("链表为空！\n");
		return;
	}
	while (p) {
		if (p->data == x) {
			q = p;           // 让q指向p（要删除的结点）
			p = p->next;     // 将指针p向后移动一个结点
			pre->next = p;   // 改变pre指针域的指向，使q从链表中删除
			free(q);         // 释放q（要删除的结点）
		}
		else {
			pre = p;        // pre向下后移
			p = p->next;    // p与pre同步向后移，这两步不能调换顺序
		}
	}
}