dynamic union array doesn't work

This is a discussion on dynamic union array doesn't work within the C Programming forums, part of the General Programming Boards category; Code: #include <stdio.h> #include <stdlib.h> #include <time.h> #define w_max 50 #define c_max 200 typedef union wcStruct { float d; int ...

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    77

    dynamic union array doesn't work

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #define w_max 50
    #define c_max 200 
    
    typedef union wcStruct {
    	float d;
    	int index;
    }*wcType;
    
    void iexchange(int *a, int *b)
    {
    	int t = *a;
    	*a = *b;
    	*b = t;
    }
    
    void fexchange(float *a, float *b)
    {
    	float t = *a;
    	*a = *b;
    	*b = t;
    }
    
    int partition(wcType *a, int p, int r)
    {
    	float x = a[r]->d;
    	int i, j;
    	j = p-1;
    	for (i = p; i < r; i++) {
    		if (a[i]->d <= x) {
    			j++;
    			fexchange(&a[i]->d, &a[j]->d);
    			iexchange(&a[i]->index, &a[j]->index);
    		}
    	}
    	j++;
    	fexchange(&a[j]->d, &a[r]->d);
    	iexchange(&a[j]->index, &a[r]->index);
    	return j;	
    }
    
    void quick_sort(wcType *a, int p, int r)
    {
    	int q;
    	if (p < r) {
    		q = partition(a, p, r);
    		quick_sort(a, p, q-1);
    		quick_sort(a, p+1, r);
    	}
    }
    
    void knapsack_01(int *get, int *w, int *c, int m, int n)
    {
    	int sum, i;
    	wcType *r = (wcType*)malloc(n*sizeof(wcType));
    	for (i = 0; i < n; i++)
    		get[i] = 0;
    	for (i = 0; i < n; i++) {
    		r[i]->d = c[i]/w[i];
    		r[i]->index = i;
    		printf("r[i]->d = %f, r[i]->index = %d\n", r[i]->d, r[i]->index);
    		sum += w[i];
    	}
    	if (sum >= m) {
    		free(r);
    		return;
    	}
    	else {
    		sum = 0;
    		quick_sort(r, 0, n-1);
    		for (i = 0; i < n; i++) {
    			sum += w[r[i]->index];
    			if (sum > m) break;
    			get[i] = 1;
    		}
    	}
    	free(r);
    }
    
    void generation(FILE *pFile, int *w, int *c, int m, int n)
    {
    	int i;
    	srand(time(NULL));
    	fprintf(pFile, "%d\n%d\n", m, n);
    	for (i = 0; i < n; i++) {
    		w[i] = rand()%w_max+1;
    		c[i] = rand()%c_max+1;
    	}
    	for (i = 0; i < n; i++) {
    		if (i%10 == 0) 
    			fprintf(pFile, "\n");
    		fprintf(pFile, "%d ", w[i]);
    	}
    	fprintf(pFile, "\n");
    	for (i = 0; i < n; i++) {
    		if (i%10 == 0)
    			fprintf(pFile, "\n");
    		fprintf(pFile, "%d ", c[i]);
    	}
    }
    
    int main()
    {
    	int *w, *c, *get;  
    	// w = weight, c = cost, get = which items have been got(1 = got, 0 = no got)
    	int n, m, i;
    	char gen;
    	FILE *pFile;
    	pFile = fopen("knapsack.dat", "wt");
    	printf("m = ");
    	scanf("%d", &m);
    	printf("n = ");
    	scanf("%d", &n);
    	
    	if (pFile) {
    		w = (int*)malloc(n*sizeof(int));
    		c = (int*)malloc(n*sizeof(int));
    		get = (int*)malloc(n*sizeof(int));
    		generation(pFile, w, c, m, n);
    		fclose(pFile);
    	}
    	else {
    		printf("Can't open file.\n");
    		return;
    	}
    	knapsack_01(w, c, get, m, n);
    	for (i = 0; i < n; i++)
    		printf("%d ", get[i]);
    	/*
    	pFile = fopen("knapsack.out", "wt");
    	if (pFile) {
    	knapsack_01(w, c, d, n, size);
    	for (i = 0; i < size; i++)
    		fprintf(pFile, "%d ", w[d[i]]);
    	fclose(pFile);
    	}
    	*/
    	return 0;
    }
    wcType *r = (wcType*)malloc(n*sizeof(wcType)); , is it right?
    Code:
    		r[i]->d = c[i]/w[i];
    		r[i]->index = i;
    		printf("r[i]->d = %f, r[i]->index = %d\n", r[i]->d, r[i]->index);
    of r[i]->d is going to equal zero or infinite number, and i print r[i]->d and c[i]/w[i] data, the c[i]/w[i] is a zero value, what's matter? [notice: w[i] and c[i] have non-zero value, I have already tested.]
    Last edited by Mathsniper; 05-07-2005 at 10:14 PM.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,336
    > wcType *r = (wcType*)malloc(n*sizeof(wcType)); , is it right?
    Well it would look a lot better without the cast, since this is C (see the FAQ)
    Also, your typedef is already a pointer, so now you have TWO pointers (a ** variable in effect).
    Hiding pointers inside typedefs is a bad idea IMO, with the general exception of pointer to function types.

    Also,
    r[i]->d = c[i]/w[i];
    r[i]->index = i;
    Since you've declared a union (not a struct?), there is only ONE value stored here - and that's the last one.

    It seems to me you'd get a lot further with
    Code:
    typedef struct wcStruct {
    	float d;
    	int index;
    } wcType;
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Apr 2005
    Posts
    77
    Code:
    /******************
     *				  *
     *	date: 9/5/05      *
     *				  *
     ******************/
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #define w_max 50
    #define c_max 150 
    
    typedef struct wcStruct {
    	float d;
    	int index;
    }wcType;
    
    void iexchange(int *a, int *b)
    {
    	int t = *a;
    	*a = *b;
    	*b = t;
    }
    
    void fexchange(float *a, float *b)
    {
    	float t = *a;
    	*a = *b;
    	*b = t;
    }
    
    int partition(wcType *a, int p, int r)
    {
    	float x = a[r].d;
    	int i, j;
    	j = p-1;
    	for (i = p; i < r; i++) {
    		if (a[i].d >= x) {
    			j++;
    			fexchange(&a[i].d, &a[j].d);
    			iexchange(&a[i].index, &a[j].index);
    		}
    	}
    	j++;
    	fexchange(&a[j].d, &a[r].d);
    	iexchange(&a[j].index, &a[r].index);
    	return j;	
    }
    
    void quick_sort(wcType *a, int p, int r)
    {
    	int q;
    	if (p < r) {
    		q = partition(a, p, r);
    		quick_sort(a, p, q-1);
    		quick_sort(a, p+1, r);
    	}
    }
    
    int knapsack_01(int *get, int *w, int *c, int m, int n)
    {
    	int sum, i;
    	wcType *r = malloc(n*sizeof(wcType));
    	sum = 0;
    	for (i = 0; i < n; i++)
    		get[i] = 0;
    	for (i = 0; i < n; i++)
    		sum += w[i];
    	
    	if (sum <= m) {
    		for (i = 0; i < n; i++)
    			get[i] = 1;
    	}
    	else {
    		sum = 0;
    		for (i = 0; i < n; i++) {
    			r[i].d = (float)c[i]/w[i];
    			r[i].index = (int)i;
    		}
    		printf("work\n");
    		quick_sort(r, 0, n-1);
    		printf("quick\n");
    		for (i = 0; i < n; i++) {
    			sum += w[r[i].index];
    			get[r[i].index] = 1;
    			if (sum > m) {
    				sum -= w[r[i].index];
    				break;
    			}
    		}
    	}
    	free(r);
    	return sum;
    }
    
    void generation(FILE *pFile, int *w, int *c, int m, int n)
    {
    	int i;
    	srand(time(NULL));
    	fprintf(pFile, "%d\n%d\n", m, n);
    	for (i = 0; i < n; i++) {
    		w[i] = rand()%w_max+1;
    		c[i] = rand()%c_max+1;
    	}
    	for (i = 0; i < n; i++) {
    		if (i%10 == 0) 
    			fprintf(pFile, "\n");
    		fprintf(pFile, "%d ", w[i]);
    	}
    	fprintf(pFile, "\n");
    	for (i = 0; i < n; i++) {
    		if (i%10 == 0)
    			fprintf(pFile, "\n");
    		fprintf(pFile, "%d ", c[i]);
    	}
    }
    
    int main()
    {
    	int *w, *c, *get;  
    	// w = weight, c = cost, get = which items have been got(1 = got, 0 = no got)
    	int n, m, sum, i;
    	FILE *pFile;
    	pFile = fopen("knapsack.dat", "wt");
    	printf("m = ");
    	scanf("%d", &m);
    	printf("n = ");
    	scanf("%d", &n);
    	
    	if (pFile) {
    		w = (int*)malloc(n*sizeof(int));
    		c = (int*)malloc(n*sizeof(int));
    		get = (int*)malloc(n*sizeof(int));
    		generation(pFile, w, c, m, n);
    		fclose(pFile);
    	}
    	else {
    		printf("Can't open file.\n");
    		return;
    	}
    	sum = knapsack_01(get, w, c, m, n);
    	/*
    	for (i = 0; i < n; i++)
    		printf("%d ", get[i]);
    	*/
    	pFile = fopen("knapsack.out", "wt");
    	if (pFile) {
    		fprintf(pFile, "%d\n", sum);
    		for (i = 0; i < n; i++) {
    			if (get[i] == 1)
    			fprintf(pFile, "%d %d\n", w[i], c[i]);
    		}
    		fclose(pFile);
    	}
    	return 0;
    }
    The program is strange, when i quick sort a more than 30 number, it is very slow and it seems doesn't work.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dynamic Array
    By firetheGlazer in forum C Programming
    Replies: 4
    Last Post: 07-11-2008, 11:57 AM
  2. dynamic array of vectors
    By axr0284 in forum C++ Programming
    Replies: 8
    Last Post: 02-25-2006, 11:01 PM
  3. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  4. Dynamic 2d array
    By Mithoric in forum C++ Programming
    Replies: 8
    Last Post: 12-29-2003, 08:19 AM
  5. 2D array in dynamic memory
    By VanJay011379 in forum C++ Programming
    Replies: 3
    Last Post: 03-16-2003, 07:34 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21