C语言实现单链表删除

C语言实现单链表删除所有与条件相符的结点

删除链表的结点指若某结点数据域的值满足给定的条件，则将该节点删除。

删除链表结点有两个原则：

（1）删除操作不应该破坏原链接关系。

（2）删除结点前，应该有一个删除位置的查找子过程。

在删除一个结点时可能遇到以下三种情况：

（1）链表为空。此时不用做任何操作，直接返回。

（2）链表头就是要删除的结点。这时先用一个指针

q

暂存此结点，再将链表头指向下一结点，最后将

q

结点释放。

q = head;
head = q->next;
free(q);
           

（3）要删除的结点不在链表头。这时，要查找该链表中是否有要删除的结点，如果没有则返回，如果有则删除。

如果找到要删除的结点，为了不破坏原链表的链接关系，要将该结点的上一个结点链接到该结点的下一个结点上，这时需要一个记录遍历过程中结点

q

的上一个结点的指针

p

。

用

q

从第二个结点开始扫描单链表，

p

指向

q

前一节点，若

q

所指节点值为

x

，则删除，并让

q

后移一个节点，否则

p

和

q

同步后移一个节点。

node * p, * q;
p = head;
q = p->next;
while(q != NULL)
{
    if(q->num == x)
    {
        p->next = q->next;
        free(q);
        q = p->next;
    }
    else
    {
        p = p->next;
        q = q->next;
  }
}
           

以前面建立的动态链表为例，编写一个删除链表中指定结点的函数

Delete

。

node * Delete(node * head, int x)
{
    if(head == NULL)
    {
        printf("链表为空");
        return NULL;
    }
    node * p, * q;
    p = head;
    q = p->next;
    while(q != NULL)
    {
        if(q->num == x)
        {
            p->next = q->next;
            free(q);
            q = p->next;
        }
        else
        {
            p = p->next;
            q = q->next;
        }
    }
    if(head != NULL && head->num == x)
    {
        q = head;
        head = q->next;
        free(q);
        return head;
    }

    return head;
}
           

完整程序运行：

#include<stdio.h>
#include<stdlib.h>

typedef struct _node
{
    int num;
    struct _node * next;
}node;

node * createlist(void);
void display(node * head);
node * Delete(node * head, int x);

int main(void)
{
    node *head;
    head = createlist();
    display(head);
    head = Delete(head, 0);
    display(head);
    return 0;
}

node * createlist(void)
{
    node * head = NULL, *p, *tail = NULL;
    int n;
    while(scanf("%d", &n) == 1)//当输入不为整数时结束
    {
        p = (node *)malloc(sizeof(node));
        
        if(head == NULL)
           head = p;
        else
           tail->next = p;
           
        p->num = n;
        p->next = NULL;
        tail = p;
    }
    return head;
}

void display(node * head)
{
    node * p;
    p = head;
    while(p != NULL)
    {
        printf("%d ",p->num);
        p = p->next;
    }
    printf("\n");
}

node * Delete(node * head, int x)
{
    if(head == NULL)
    {
        printf("链表为空");
        return NULL;
    }
    node * p, * q;
    p = head;
    q = p->next;
    while(q != NULL)
    {
        if(q->num == x)
        {
            p->next = q->next;
            free(q);
            q = p->next;
        }
        else
        {
            p = p->next;
            q = q->next;
        }
    }
    if(head != NULL && head->num == x)
    {
        q = head;
        head = q->next;
        free(q);
        return head;
    }

    return head;
}
           

输入：

0 0 1 2 3 0 0 1 q

输出：

0 0 1 2 3 0 0 1

1 2 3 1