----------------解决方案--------------------------------------------------------
我写的归并算法，比较长，高手见笑
先用快速排序对输入的两个数组排序，然后归并
/*
The Symmetric Difference Of Two Sets
Question:
The symmetric difference of two sets is the set of elements belonging to one but not both of the two sets. For example, if we have two sets A = {1,2,3,4,5} and B = {3,4,5,6,7,8}, then the symmetric difference of A and B is the set {1,2,6,7,8}.
Given two sets of positive integers, display their symmetric difference.
Input
A positive integer will denote the number of cases. Both sets will be input from a single line. A zero (0) marks the end of each set. There will be no more than 20 numbers in each set, and no number within a set will be repeated. Each number in a set is a positive integer less than 65535.
Output
The set of integers making up the symmetric difference of the two sets. The numbers within a set may be sorted from smaller to bigger.
Sample Input
3
1 2 3 4 5 0 3 4 5 6 7 8 0
1 2 3 0 1 2 3 0
129 34 5 6 7 0 129 0
Sample Output
{1,2,6,7,8}
{}
{5,6,7,34}
*/
/*
Attention Please: this code can only solve the question in a very very simple way.
It could solve the question correctly and quickly, but there was no support
of input or output. So you need to change the code and recompiler it to change
the input numbers;
Write by Li_za
afternoon, 8.12.2007
*/
int isSorted(int *A, int N);
void quick_sort(int A[], int p, int r);
int partition(int A[], int p, int r);
int merge(int *A, int N_A,int *B, int N_B, int *C);
int isSorted(int *A, int N)
{
while(N > 1)
{
if (*(A+1) < *A)
return 0; /* not sorted */
N--;
}
return 1; /* is sorted*/
}
void quick_sort(int A[], int p, int r)
{
int q;
if(p < r)
{
q = partition(A, p, r);
quick_sort(A, p, q - 1);
quick_sort(A, q + 1, r);
}
}
int partition(int A[], int p, int r)
{
int x, i, j, temp;
x = A[r];
i = p - 1;
for( j = p; j < r; j++ )
{
if (A[j] <= x)
{
i++;
temp = A[j];
A[j] = A[i];
A[i] = temp;
}
}
i++;
temp = A[i];
A[i] = A[r];
A[r] = temp;
return i;
}
int merge(int *A, int N_A, int *B, int N_B, int *C)
{
int * rest;
int N_rest = 0;
int N_C = 0;
/* do once frist or the following loop will underflow */
if(*A > *B)
{
*C = *B;
B++;
N_B--;
}
else
{
*C = *A;
A++;
N_A--;
}
C++;
N_C++;
/* merge */
while((N_A > 0) && (N_B > 0))
{
if(*A > *B)
{
*C = *B;
B++;
N_B--;
}
else
{
*C = *A;
A++;
N_A--;
}
if(*C != *(C-1))
{
C++;
N_C++;
}
else
{
C--;
N_C--;
}
}
/* who is the survivor ? */
if(N_B == 0)
{
rest = A;
N_rest = N_A;
}
else
{
rest = B;
N_rest = N_B;
}
/* Consider the header of the rest elements */
if(*(C-1) == *rest)
{
rest++;
N_rest--;
C--;
N_C--;
}
/* put the rest of elements which belong to the survivor into the set C */
N_C += N_rest;
while(N_rest > 0)
{
*(C++) = *(rest++);
N_rest--;
}
return N_C; /* return the length of the set C */
}
int main()
{
#define N_A 5
#define N_B 1
int i;
int N_C;
int C[N_A + N_B];
int A[] = {129, 34, 5, 6, 7};
int B[] = {129};
if(! isSorted(A, N_A))
quick_sort(A, 0, N_A - 1);
if(! isSorted(B, N_B))
quick_sort(B, 0, N_B - 1);
N_C = merge(A, N_A, B, N_B, C);
printf("%d\n", N_C);
for(i = 0; i < N_C; i++)
{
printf( "%d ", C[i] );
}
return 0;
}
----------------解决方案--------------------------------------------------------