【单链表】单链表的删除

在有些应用中，允许线性表中存在值相同的数据元素。线性表的另一个删除操作listDeleteAll(SeqList *seqlist,dataType x)的功能是：删除线性表seqlist中所有等于x的数据元素。要求编写使用单链表实现上述功能的操作算法

题目分析：

题目很简单，我们只需要在遍历线性表seqlist的时候挨个和数据x比对，如果相同，删除当前结点就可以了，但恰恰在这里有一个小陷阱，废话不多说，直接上图

上图是我刚开始学数据结构时编写的代码，老老实实的逐个与数据x作比较，相同则删除

我们来看看效果吧

这没问题呀，最终结果是将15给删除了掉了，那我们接下来再看看有多个15的运行情况

这算法还是很OK，直接将单链表中3个连续的15给删除了，完全没问题

咱们再来看一个测试用例

现在bug就出来了，我们看到，3个15最终只删除了两个，还有一个15没有被删除，程序宣告失败！

那么问题到底出在哪里呢？？？

咱们来顺着错误代码分析一下

问题已经找到，在删除时将第二个15遗漏了，那怎么办呢？怎样才能不遗漏连续的相同数据，我能想到的一个办法就是，每当我们删除一个数据之后，就重头遍历单链表，这或许不是一个最好的办法，但这是我目前能想到解决这个问题的最好的方法，为什么说不是最好的方法，因为这种方法当在重复数据很多的时候，大大的加大了算法的时间复杂度，因此我觉得应该还有更好更快捷的程序来解决删除全部相同数据的方法，如果您有更好的方法，请留言，我们可以一起交流，嘻嘻

那么接下来请看我的代码

//删除链表中所有等于x的数据
void listDeleteAll(Node *head, dataType x)
{
    Node * p, *p1;
    p = head;
    while (p->next != NULL)
    {
        if (x == p->next->data)
        {
            p->next = p->next->next;
            p = head;            //又从头开始遍历，避免忽略掉连续数据相同的情况
            continue;
        }
        p = p->next;
    }
}

完整代码实现：

#include<stdio.h>
#include<stdlib.h>
typedef int dataType;    //数据类型为int

//结点结构体
typedef struct node
{
    dataType data;      //数据域
    struct node *next;  //指针域
}Node;

//初始化结点
void listInitiate(Node **head)            //双星指针，地址的地址，在初始化时，我们要使地址的值改变，所以使用双星作为参数传入
{
    *head = (Node*)malloc(sizeof(Node));  //为头结点分配位置空间（一个结点的大小）
    (*head)->next = NULL;                 //头结点指针域初始默认为空
}

/*尾插发建立单链表——得到的链表是顺序的
利用数组的前n个数建立一条单链表*/
void listBuildRear(Node *head, dataType arr[], int n)
{
    Node *p = head;                       //新增一个指针，用来代替head指针
    for (int i = 0; i < n; i++)              //循环n次，每次循环都在链表尾部追加一个结点
    {
        Node *q = (Node*)malloc(sizeof(Node));//新建立结点，并为之分配内存空间
        q->data = arr[i];                 //数据域赋值，将数组的第i+1个数字赋给新结点q
        q->next = NULL;                   //单链表最后一个结点的指针域都为空
        p->next = q;                      //将原始单链表最后一个结点指针域指向新结点q，从此q成为最后一个结点，原始最后一个结点变成倒数第二个结点
        p = q;                            //p又指向当前链表最后一个结点，为下一次尾部插入做准备
    }
}

//遍历输出函数
void listPrint(Node *head)
{
    printf("单链表：");
    Node *p = head;                       //新增一个指针，用来代替head指针
    while (p->next != NULL)
    {
        printf("%d   ", p->next->data);
        p = p->next;                      //这一句不要忘了，不然会死循环的，我总是忘掉这一句
    }
}

//删除链表中所有等于x的数据
void listDeleteAll(Node *head, dataType x)
{
    Node *p;
    p = head;
    for (;p->next != NULL ;)
    {
        if (x == p->next->data)
        {
                p->next = p->next->next;
                p = head;            //又从头开始遍历，避免忽略掉连续数据相同的情况
                continue;
        }
        p = p->next;
    }
}

int main()
{
    Node link1;
    Node *q;
    q = &link1;
    listInitiate(&q);
    int arr[50],n;
    printf("你要输入几个数：");
    scanf("%d",&n);
    for(int i = 0;i < n;i++)
       scanf("%d",&arr[i]);
    listBuildRear(q,arr,n);    //将数组arr的前n个数放进链表中
    listPrint(q);
    printf("请输入要删除的数据：");
    int x;
    scanf("%d",&x);
    listDeleteAll(q,x);        //删除链表中所有等于x的数据
    listPrint(q);
}

运行结果：

（1）如果链表中有一个x

（2）如果链表中有多个x，单不相邻

（3）如果链表中有多个x，并且相邻

代码编译器：Dev-C++
ok，完美解决