www.pudn.com > Demo C.rar > set.c

#include  
#include "set.h" 
 
/*  
 * set.c from the Set of Integers example,  
 * Ch. 7, C: A Reference Manual 5/e 
 * Samuel P. Harbison III and Guy L. Steele Jr. 
 */ 
 
 
int cardinality(SET x) 
{	 
/* The following loop body is executed once for every 1-bit 
   in the set x.  Each iteration, the smallest remaining 
   element is removed and counted. The expression (x & -x) 
   is a set containing only the smallest element in x, in 
   twos-complement arithmetic. */ 
	int count = 0; 
	while (x != emptyset) { 
		x ^= (x & -x); 
		++count; 
	} 
	return count; 
} 
 
SET next_set_of_n_elements(SET x) 
{ 
/* This code exploits many unusual properties of unsigned 
   arithmetic.  As an illustration: 
     if x               == 001011001111000, then 
     smallest           == 000000000001000 
     ripple             == 001011010000000 
     new_smallest       == 000000010000000 
     ones               == 000000000000111 
     the returned value == 001011010000111  
   The overall idea is that you find the rightmost 
   contiguous group of 1-bits. Of that group, you slide the 
   leftmost 1-bit to the left one place, and slide all the 
   others back to the extreme right.  
   (This code was adapted from HAKMEM.) */ 
	SET smallest, ripple, new_smallest, ones; 
	if (x == emptyset) return x; 
	smallest     = (x & -x);  
	ripple       = x + smallest; 
	new_smallest = (ripple & -ripple); 
	ones         = ((new_smallest / smallest) >> 1) - 1; 
	return (ripple | ones); 
}  
 
void printset(SET z) 
{ 
	int first = 1; 
	int e; 
	forallelements(e, z) { 
		if (first) printf("{"); 
		else printf(", "); 
		printf("%d", e); 
		first = 0; 
	} 
	if (first) printf("{"); /* Take care of emptyset */ 
	printf("}");            /* Trailing punctuation */ 
} 
 
#define LINE_WIDTH 54 
void print_k_of_n(int k, int n) 
{ 
	int count = 0; 
	int printed_set_width = k * ((n > 10) ? 4 : 3) + 3; 
	int sets_per_line = LINE_WIDTH / printed_set_width; 
	SET z = first_set_of_n_elements(k); 
	printf("\nAll the size-%d subsets of ", k); 
	printset (first_set_of_n_elements(n)); 
	printf(":\n"); 
	do {			/* Enumerate all the sets. */ 
		printset(z); 
		if ((++count) % sets_per_line) printf (" "); 
		else printf("\n"); 
		z = next_set_of_n_elements(z); 
	}while ((z != emptyset) && !element(n, z)); 
	if ((count) % sets_per_line) printf ("\n"); 
	printf("The total number of such subsets is %d.\n", 
		count); 
}