从链表中删除素数

小咪咪 2022-11-30 05:39 192阅读 0赞

## 从链表中删除素数 ##

【问题描述】  
以下程序中结点node定义了一个整数的信息，函数IsPrime的功能是判定一个整数是不是素数，是素数返回1否则返回0；函数create创建一个由10个整数构成的链表；函数del从链表中删除所有数据成员为素数的结点， 函数print输出头结点地址为head的链表信息。

【样例输入】（输入10个数从头插入链表）  
9 8 7 6 5 4 3 2 1 0  
【样例输出】  
Source list: 0 1 2 3 4 5 6 7 8 9  
After deleted: 0 1 4 6 8 9

#include "stdio.h"
    #include "stdlib.h"
    struct node
    { 
        int n;
        struct node *next;
    } NODE;
    int IsPrime(int n) /*判断整数n是不是素数*/
    { 
        int i;
        if(n<2)  return 0;
        for(i=2;i<n;i++)
            { if(n%i==0) return 0;}
        return 1;
    }
    struct node *create() /*创建由10个整数构成的链表*/
    { 
        int i,n;
        struct node *head=NULL,*p;
        for(i=0;i<10;i++)
        { 
            p=(struct node *)malloc(sizeof(struct node));
            scanf("%d",&p->n);
            p->next=head;
            head=p;
        }
        return head;
    }
    struct node *del(struct node *head) /*删除所有素数点*/
    { 
        struct node *p,*q;
        if(head==NULL){ return NULL;}
        for(p=head,q=p->next;q!=NULL;q=p->next)
        {    /* 删除从第2个结点开始的整数部分是素数的结点*/
            if(IsPrime(q->n))
            { 
                p->next=q->next;
                free(q);
            }
            else
                { p=p->next;}
        }
        if(IsPrime(head->n)) /*处理头结点整数部分是素数的情况*/
        { 
          p=head->next;
          free(head);
          head=p;
        }
        return head;
    }
    void print(struct node *head)
    { 
        struct node *p=head;
        if(p==NULL) printf(" nothing");
        while(p!=NULL)
        { 
            printf("%d ",p->n);
            p=p->next;
        }
    }
    int main()
    { 
        struct node *head;
        head=create();
        printf("Source list: ");
        print(head);
        printf("\n");
        head=del(head);
        printf("After deleted: ");
        print(head);
        printf("\n");
    }