用单链表模拟有序集合，实现集合的加入一个元素、删除一个元素、集合的交、并、差运算。

Question

(1)用单链表存放集合中的元素，链表中的元素按大小存放;
(2)实现集合加入一个元素删除一个元素的元素操作;
(3)实现集合的交、并、差集合操作;

还要各函数之间的调用关系和总体设计图

Answer 1

    #include<stdio.h> 
#include<stdlib.h>
/*
插入一个数到集合指定位置
按值删除集合中的元素
按值在集合中进行查找
清空集合
求两个集合的交集
求两个集合的并集
求两个集合的差集
输出集合
*/



typedef struct Lnode{
    int data;
    struct Lnode *next;
}Lnode, *LinkList;
void menu()
{
    printf(    "0)输入表一表二数据\n" 
            "1)插入一个数到表一指定位置\n"
            "2)按值删除表一中的元素\n"
            "3)按值在表一中进行查找\n"
            "4)清空表一表二集合\n"
            "5)求两个集合的交集\n"
            "6)求两个集合的并集\n"
            "7)求两个集合的差集\n"
            "8)输出集合\n");
}
//实现创建一个头结点
void Init(LinkList *L)
{
    *L = (LinkList)malloc(sizeof(Lnode));
    if(!(*L))
    {
        printf("创建头节点失败\n");
        exit(1);
    }
    else
        (*L)->next = NULL;
    
 } 
//实现集合元素的输入
void Input(Lnode **L) //给集合输入数据采用单链表尾插法
{
    Lnode *p,*temp;
    p = (LinkList)malloc(sizeof(Lnode));
    if(p==NULL)
    {
        printf("内存分配失败\n");
        exit(1);
    }
    printf("请输入整数:\n");
    scanf("%d",&(p->data));

    if(*L != NULL)
    {
        temp = *L;
        //定位单链表的尾部位置
        while(temp->next != NULL)
        {
            temp = temp->next;
         } 
         //插入数据
         temp->next = p;
         p->next = NULL; 
    }
    else
    {
        *L=p;
        p->next=NULL;
    }
}


//实现任意位置插入
int Insert(LinkList L,int i)
{    
    LinkList p,q;
    if(i==0)
    {
        printf("位序不合法\n");
        return 0;
    }
    p=L->next;
    int j=0;
    while(p && j<i-1)
    {
        p=p->next;
        j++;
    }
    if(!p)
        return 0;
    else
    {
        q=(LinkList)malloc(sizeof(Lnode));
        if(q==NULL)
            return 0;
        printf("输入插入的内容:\n");
        scanf("%d",&(q->data));
        q->next = p->next;
        p->next = q;
    }
    
 } 


int Delete(LinkList L,int n)
{
    LinkList previous;
    LinkList target;
    previous=L;

    while(previous->next&&previous->next->data!=n)
    {
        previous=previous->next;
        
    }
     if(previous->next==NULL)
     {
         printf("未找到该元素\n");
         return ;
     }
    else
    {
        target = previous->next;
        previous->next = target->next;
        free(target);
    }    
}
void Output(Lnode *L)
{
    int i=1;
    Lnode *p;
    p=L->next;
    if(p==NULL)
    {
        printf("无数据\n");
    }
    while(p!=NULL)
    {        
        printf("[%d]:\t",i++);
        printf("%d\n",p->data);
        p=p->next; 
    }

}
//销毁单链表
void DestroyList(LinkList *L)
{
    LinkList q;
    while (*L)
    {
        q = (*L)->next;
        free(*L);  //释放头结点
        *L = q;   //L指向原首元节点，实现头结点
    }
}

//将单链表重置为空表
void ClearList(LinkList L)
{
    LinkList p = L->next; //p指向第一个结点
    L->next = NULL;   //头结点指针域为空
    DestroyList(&p);  //销毁p所指向的单链表

}


void SearchList(LinkList L,int target)
{    int i=1;
    Lnode *p;
    p=L->next;
    while(p)
    {    
        if(p->data==target)
        {    
            break;
        }
        p = p->next;
        i++;
    }
    if(p)
    {
        printf("您找的元素是:%d,查找的元素位序是%d,\n",target,i); 
    }
    else
    {
        printf("没有此元素\n");
    }
}


//求两个集合的交集
LinkList  Intersection(LinkList L1, LinkList L2,int i)
{    LinkList s;
    Init(&s);
    LinkList Lp,Lq;
    Lp=L1->next;
    while(Lp)
    {    Lq = L2->next;
        while(Lq)
        {
            if(Lp->data==Lq->data)
            {
                LinkList inter = (LinkList)malloc(sizeof(Lnode));//头插法插入 
                inter->data = Lp->data;
                inter->next = s->next;
                s->next = inter;    
            }
            Lq=Lq->next;
        }
        Lp=Lp->next;
    }
    if(i)
        Output(s);
    return s;
}

//求两个集合的并集
LinkList Union(LinkList L1,LinkList L2,int i)
{
    LinkList s;
    Init(&s);
    LinkList p1,p2;
    p1=L1->next;
    p2=L2->next;
    while(p1)
    {
        LinkList inter = (LinkList)malloc(sizeof(Lnode));//头插法插入 
        inter->data = p1->data;
        inter->next = s->next;
        s->next = inter;
        p1 = p1->next; 
    }
    while(p2)
    {
        p1 = s->next;
        while(p1)
        {
            if(p1->data != p2->data)
            {
                p1 = p1->next;
            }
            else
            {
                break;
             } 
            
        }
        if(!p1)
        {
            LinkList inter = (LinkList)malloc(sizeof(Lnode));//头插法插入 
            inter->data = p2->data;
            inter->next = s->next;
            s->next = inter;
        }
        p2 = p2->next;
    }
    if(i)
        Output(s);
    return s;
}


void DiffenceList(LinkList L1, LinkList L2)
{
    LinkList s1,s2,s,p,q;
    s1 = Union(L1,L2,0);
    s2 = Intersection(L1,L2,0);
    p=s1->next;
    while(p)
    {
        q=s2->next;
        while(q)
        {
            if(q->data != p->data)
                q=q->next;
            else
                break;
        }
        if(!q)
        {
            LinkList inter = (LinkList)malloc(sizeof(Lnode));//头插法插入 
            inter->data = p->data;
            inter->next = s->next;
            s->next = inter;
        }
        p=p->next;
    }
    Output(s);
}
void main()
{    int i=0;
    int input; 
    int flag;
    LinkList L1=NULL,Ltarget1;
    LinkList L2=NULL,Ltarget;
    Init(&L1);
    Init(&L2);
    int n;
    
    while(1)
    {    
        
    
        menu();
        printf("请输入功能数字:\n");
        scanf("%d",&flag);
        switch(flag)
        {    
            case 0:
                printf("表一\n");
                printf("输入元素个数\n"); 
                scanf("%d",&n);
                while(i<n)
                {
                    Input(&L1);
                    i++;
                }
                Output(L1);    
                
                printf("表二\n");
                printf("输入元素个数\n"); 
                scanf("%d",&n);
                i=0;
                while(i<n)
                {
                    Input(&L2);
                    i++;
                }
                Output(L2);    
                break; 
            case 1:
                //插入一个元素到表一指定位置
                printf("插入一个元素到表一指定位置\n"); 
                printf("请输入插入的位序:");
                scanf("%d",&n); 
                Insert(L1,n); 
                Output(L1);
                break; 
            case 2:
                //按值删除集合中的元素
                printf("删除表一中的元素\n");
                printf("请输入要删除的整数:");
                scanf("%d", &n);
                Delete(L1,n);
                Output(L1);    
                break; 
            case 3:
                
                //按值在集合中进行查找
                printf("请输入查找的元素:");
                scanf("%d",&input); 
                SearchList(L1,input);
                Output(L1);    
                break; 
            case 4:
                ClearList(L1);
                ClearList(L2); 
                break;
            case 5:
                //求两个集合的交集
                printf("两个集合的交集:\n");
                Intersection(L1,L2,1);
                break; 
            case 6:    
                //求两个集合的并集
                printf("两个集合的并集:\n");
                Union(L1,L2,1);
                break; 
            case 7:
                //求两个集合的差集
                printf("两个集合的差集:\n");
                DiffenceList(L1,L2);
                break;
            case 8: 
                //输出
                printf("输出完整表一/二(1 or 2):");
                scanf("%d",&input);
                if(input==1)
                    Output(L1);
                if(input==2)
                    Output(L2);
                break; 
        }
    }     
}