数据结构_最少需要收集的材料的个数之链表实现集合

题意关键句：搜集足够的材料确保两种制作方式都能满足.

1 3 1

3 3 1

编号1至少收集2个，编号3至少收集2个，才能同时满足两种方法。

因为不知道编号到底有多大，用位向量表示集合的无法判断需要开多少位。而有序链表恰恰弥补这个缺点。

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 typedef struct node *link;
  4 struct node 
  5 {
  6     int data;//数据域
  7     link next;
  8 }Node;
  9 typedef struct list *Set;
 10 struct list
 11 {
 12     link first;//头指针
 13 }List;
 14 int ans=0;
 15 Set SetInit()//创建一个空链表
 16 {
 17     Set S;
 18     S=(Set)malloc(sizeof(list));
 19     S->first=NULL;
 20     return S;
 21 }
 22 void SetInsert(int x,Set S)
 23 {
 24     link q,p,r;
 25     p=S->first;
 26     q=p;
 27     while(p&&p->data<x)
 28     {
 29         q=p;
 30         p=p->next;
 31     }
 32     r=(link)malloc(sizeof(Node));
 33     r->data=x;
 34     r->next=p;
 35     if(p==q)
 36         S->first=r;
 37     else
 38         q->next=r;
 39 }
 40 void SetSearch(Set A,Set B)
 41 {
 42     link a,b;
 43     int x1=1,x2=1;
 44     a=A->first;
 45     b=B->first;
 46     while(a&&b)
 47     {
 48         x1=x2=1;
 49         if(a->data==b->data)
 50         {
 51             while(a->next&&a->data==a->next->data)
 52             {
 53                 x1++;
 54                 a=a->next;
 55             }
 56             if(x1==1)
 57                 x1=0;//只有一个相同的元素
 58             while(b->next&&b->data==b->next->data)
 59             {
 60                 x2++;
 61                 b=b->next;
 62             }
 63             if(x1!=0||x2!=1)//不止只有一个相同元素
 64             {
 65                 if(x1>x2)
 66                     ans+=x1;
 67                 else
 68                     ans+=x2;
 69             }
 70             else
 71                 ans+=1;//只有一个相同元素
 72             a=a->next;
 73             b=b->next;
 74         }
 75         else if(a->data<b->data)
 76         {
 77             ans++;
 78             a=a->next;
 79         }
 80         else
 81         {
 82             ans++;
 83             b=b->next;
 84         }
 85     }
 86     while(a)
 87     {
 88         ans++;
 89         a=a->next;
 90     }
 91     while(b)
 92     {
 93         ans++;
 94         b=b->next;
 95     }
 96 }
 97 int main()
 98 {
 99     int n,m,i,x;
100     scanf("%d",&n);
101     Set L1,L2;    
102     L1=SetInit();
103     for(i=0;i<n;i++)
104     {
105         scanf("%d",&x);
106         SetInsert(x,L1);
107     }
108     scanf("%d",&m);
109     L2=SetInit();
110     for(i=0;i<m;i++)
111     {
112         scanf("%d",&x);
113         SetInsert(x,L2);
114     }
115     SetSearch(L1,L2);
116     printf("%d
",ans);
117     return 0;
118 }

View Code

算法基础定义：http://www.cnblogs.com/zeze/p/Bitsit.html