牛骨文教育服务平台(让学习变的简单)

问题描述

在带头结点的单链表L中,删除所有值为x的结点,并释放其空间,假设值为x的结点不唯一,试编写算法实现以上的操作

算法思想

使用指针p指向数据域为x的结点,使用指针pre指向指针p所指结点的前驱结点,从前向后进行遍历。如果指针p指向的结点的数据域为x,则删除,如果指针p指向的结点的数据域不为x,继续向后遍历即可。

算法描述

void DelNodeX(LNode *head, ElemType x)
{
    LNode *pre=head;
    LNode *p=head->next;
    while(p!=NULL){
        if(p->data==x){
            pre->next=p->next;
            free(p);
            p=pre->next;
        }else{
            pre=p;
            p=p->next;
        }
    }
}

具体代码见附件。

附件

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;
LinkList CreatList(LNode*);
void DelNodeX(LNode*, ElemType);
void Print(LNode*);

int main(int argc,char* argv[])
{
    LNode *head;
    head=(LNode*)malloc(sizeof(LNode));
    head->next=NULL;
    head=CreatList(head);
    Print(head);
    DelNodeX(head,3);
    Print(head);
    return 0;
}
//头插法建立单链表
LinkList CreatList(LNode *head)
{
    LNode *L;
    ElemType x;
    scanf("%d",&x);

    while(x!=999){
        L=(LNode*)malloc(sizeof(LNode));
        L->data=x;

        L->next=head->next;
        head->next=L;

        scanf("%d",&x);
    }

    return head;
}
//删除值为x的结点
void DelNodeX(LNode *head, ElemType x)
{
    LNode *pre=head;
    LNode *p=head->next;
    while(p!=NULL){
        if(p->data==x){
            pre->next=p->next;
            free(p);
            p=pre->next;
        }else{
            pre=p;
            p=p->next;
        }
    }
}
//打印所有结点
void Print(LNode *head)
{
    LNode *p=head->next;
    while(p){
        printf("%4d",p->data);
        p=p->next;
    }
    printf("
");
}