集合的交并运算

喜欢ヅ旅行 2022-06-04 02:11 276阅读 0赞

**数据结构链表实现集合的交并运算**

//consts.h

#include<string.h>
    #include<malloc.h>
    #include<stdlib.h>
    #include<stdio.h>
    #include<limits.h>
    #include<io.h>
    #include<math.h>
    #include<process.h>
    
    #define TRUR 1
    #define FALSE 0
    #define OK 1
    #define ERROR -1
    #define INFEASIBLE -1

//linklist.h

#ifndef MY_H_FILE 
    #define MY_H_FILE 
    #include"consts.h"
    #endif 
    
    
    typedef char DataType;
    typedef struct node
    {
        DataType data;
        struct node *next;
    }LinkedList;
    
    
    
    void InitLlist(LinkedList *L)
    {
        L->next=NULL;
    }
    
    int GetLListLength(LinkedList *L)
    {
        LinkedList *p;
        int j;
        p=L->next;
        j=0;
        while(p!=NULL)
        {
            p=p->next;
            j++;
        }
        return j;
    }
    
    LinkedList *GetLListElem(LinkedList *L,int i)
    {
        int j;
        LinkedList *p;
        p=L;
        j=0;
        while((p->next!=NULL)&&(j<i))
        {
            p=p->next;
            j++;
        }
        if(i=j)
        {
            return p;
        }
        else
            return NULL;
    }
    
    LinkedList *LocateLListElem(LinkedList *L,DataType key)
    {
        LinkedList *p;
        p=L->next;
        while(p!=NULL)
        {
            if(p->data!=key)
            {
                p=p->next;
            }
            else
                break;
        }
        return p;
    }
    
    int InsertLList(LinkedList *L,int i,DataType x)
    {
        LinkedList *pre,*s;
        int k;
        pre=L;
        k=0;
        while(pre!=NULL && k<i-1)
        {
            pre=pre->next;
            k=k+1;
        }
        if(!pre)
        {
            printf("插入位置不合理");
            return ERROR;
        }
        s=(LinkedList*)malloc(sizeof(LinkedList));
        s->data=x;
        s->next=pre->next;
        pre->next=s;
        return OK;
    }
    
    int DeleteLList(LinkedList *L,int i,DataType *e)
    {
        LinkedList *pre,*r;
        int k;
        pre=L;
        k=0;
        while(pre->next!=NULL && k<i-1)
        {
            pre=pre->next;
            k++;
        }
        if(!(pre->next))
        {
            printf("删除的位置不合理");
            return ERROR;
        }
        r=pre->next;
        pre->next=pre->next->next;
        *e=r->data;
        free(r);
        printf("成功删除结点");
        return OK;
    }
    
    LinkedList *CreateLListR()
    {
        char ch;
        LinkedList *head,*s,*r;
        head=(LinkedList*)malloc(sizeof(LinkedList));
        r=head;
        ch=getchar();
        while(ch!='$')
        {
            s=(LinkedList*)malloc(sizeof(LinkedList));
            s->data=ch;
            r->next=s;
            r=s;
            ch=getchar();
        }
        r->next=NULL;
        return head;
    }
    
    void PrintLList(LinkedList *q)
    {
        LinkedList *p;
        p=q->next;
        printf("字符单链表结果是：\n");
        while(p!=NULL)
        {
            printf("%5c",p->data);
            p=p->next;
        }
        printf("\b\n");
    }

//main.h

#include"linklist.h"
    //求并集
    void UnionLinkCollection(LinkedList *a,LinkedList *b,LinkedList *c)
    {
        LinkedList *p,*q,*r,*s;
        int flag=0;
        r=c;
        for(p=a->next;p!=NULL;p=p->next)
        {
            s=(LinkedList*)malloc(sizeof(LinkedList));
            s->data=p->data;
            r->next=s;
            r=s;
            s->next=NULL;
        }
        for(p=b->next;p!=NULL;p=p->next)
        {
            for(q=a->next;q!=NULL;q=q->next)
            {
                if(p->data==q->data)
                {
                    flag=1;
                    break;
                }
            }
            if(flag==0)
            {
                s=(LinkedList*)malloc(sizeof(LinkedList));
                s->data=p->data;
                r->next=s;
                r=s;
                s->next=NULL;
            }
            flag=0;
        }
    }
    
    //求jiao集
    int InterLinkCollection(LinkedList *a,LinkedList *b,LinkedList *c)
    {
        int reg=0;
        LinkedList *p,*q,*r=c,*s;
        for(p=a->next;p!=NULL;p=p->next)
        {
            for(q=b->next;q!=NULL;q=q->next)
            {
                if(p->data==q->data)
                {
                    s=(LinkedList*)malloc(sizeof(LinkedList));
                    s->data=p->data;
                    r->next=s;
                    r=s;
                    s->next=NULL;
                    reg=1;
                }
            }
        }
        return reg;
    }
    
    int main()
    {
        LinkedList *a,*b,*jiao,*bing;
        printf("请输入表a的元素：（以$结束）\n");
        a=CreateLListR();
        getchar();
        printf("请输入表b的元素：（以$结束）\n");
        b=CreateLListR();
        printf("集合a中的元素为：");
        PrintLList(a);
        printf("集合b中的元素为：");
        PrintLList(b);
        jiao=(LinkedList*)malloc(sizeof(LinkedList));
        bing=(LinkedList*)malloc(sizeof(LinkedList));
        printf("a交b为：");
        InterLinkCollection(a,b,jiao);
        PrintLList(jiao);
        printf("a并b为：");
        UnionLinkCollection(a,b,bing);
        PrintLList(bing);
        return 0;
    }