dose chart 2d array overflows?

This is a discussion on dose chart 2d array overflows? within the C Programming forums, part of the General Programming Boards category; Code: #include <stdio.h> #include <stdlib.h> #define bool short #define true 1 #define false 0 #define maxP 10000 int set_relative(int relative[maxP][2], ...

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

    dose chart 2d array overflows?

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #define bool short
    #define true 1
    #define false 0
    #define maxP 10000
    
    int set_relative(int relative[maxP][2], int m, int n)
    {
    	int chart[maxP][maxP];
    	int i, j, r1, r2, max_contact;
    	bool group[maxP];
    	bool contact;
    	for (i = 0; i < m; i++)
    		for (j = 0; j < m; j++)
    			chart[i][j] = 0;
    	max_contact = 1;
    	chart[relative[0][0]-1][relative[0][1]-1] = 1;
    	chart[relative[0][1]-1][relative[0][0]-1] = 1;
    	for (i = 0; i < n; i++) {
    		contact = false;
    		r1 = relative[i][0]-1;
    		r2 = relative[i][1]-1;
    		for (j = 0; j < m; j++) {
    			if (chart[j][r1] != 0) {
    				chart[r1][r2] = chart[j][r1];
    				chart[r2][r1] = chart[j][r1];
    				contact = true;
    				break;
    			} else if (chart [r2][j] != 0) {
    				chart[r1][r2] = chart[r2][j];
    				chart[r2][r1] = chart[r2][j];
    				contact = true;
    				break;
    			} 
    		}
    		if (!contact) {
    			max_contact++;
    			chart[r1][r2] = max_contact;
    			chart[r2][r1] = max_contact;
    		}
    	}
    	for (i = 0; i < m; i++) {
    		group[relative[i][0]-1] = true;
    		group[relative[i][1]-1] = true;
    	}
    	for (i = 0; i < m; i++)
    		if (group[i] == false)
    			max_contact++;
    	return max_contact;
    }
    
    int main()
    {
    	FILE *fr, *fw;
    	int max_contact, m, n, i;
    	int relative[maxP][2];
    	fr = fopen("relative.dat", "rt");
    	fw = fopen("relative.out", "wt");
    	fscanf(fr, "%d %d", &m, &n);
    	for (i = 0; i < n; i++)
    		fscanf(fr, "%d %d", &relative[i][0], &relative[i][1]);
    	max_contact = set_relative(relative, m, n);
    	fprintf(fw, "%d", max_contact);
    	fclose(fr);
    	fclose(fw);
    	return 0;
    }
    relative.dat
    Code:
    8 6 
    1 2
    1 4
    2 3
    2 4
    5 6
    5 8
    Code:
    mathsniper:~# gcc -O2 -o relative relative.c
    mathsniper:~# ./relative
    Segmentation fault
    There has no compiling wrong message. during my debugging, I think the chart 2darray overflow. or appeal other problem?
    Last edited by Mathsniper; 10-31-2005 at 09:32 AM.

  2. #2
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    I think the program is having stack overflow problems. I tried to run it on MS-Windows using VC++ 6.0 and it wouldn't run. You need to allocate those huge arrays dynamically using malloc() or calloc().

  3. #3
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    This is asking for a lot of space on the stack.
    Code:
    #define maxP 10000
    
    int set_relative(int relative[maxP][2], int m, int n)
    {
    	int chart[maxP][maxP];
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  4. #4
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    yes, 10,000 * 10,000 * 4 = 400,000,000 bytes (or 400 Mg). just for chart array, then another 80,000 bytes for relative array. Even dynamic allocation will not be too helpful for that because unless the computer hardware has at least one GIG RAM the os will probably do a lot of disk swapping every time that array is accessed.
    Last edited by Ancient Dragon; 10-31-2005 at 10:07 AM.

  5. #5
    Registered User
    Join Date
    Apr 2005
    Posts
    77
    how can i create a 2d array by malloc?

  6. #6
    Registered User
    Join Date
    Apr 2005
    Posts
    77
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #define bool short
    #define true 1
    #define false 0
    #define maxP 1000
    
    int **make2darray(int x, int y)
    {
    	int **array;
    	int i;
    	array = malloc(x*sizeof(**array));
    	for (i = 0; i < y; i++)
    		array[i] = malloc(y*sizeof(*array));
    	return array;
    }
    
    int set_relative(int **relative, int m, int n)
    {
    	int i, j, r1, r2, max_contact;
    	int **chart;
    	bool *group;
    	bool contact;
    	chart = make2darray(m, m);
    	group = malloc(m*sizeof(*group));
    	for (i = 0; i < m; i++)
    		for (j = 0; j < m; j++)
    			chart[i][j] = 0;
    	max_contact = 1;
    	chart[relative[0][0]-1][relative[0][1]-1] = 1;
    	chart[relative[0][1]-1][relative[0][0]-1] = 1;
    	for (i = 0; i < n; i++) {
    		contact = false;
    		r1 = relative[i][0]-1;
    		r2 = relative[i][1]-1;
    		for (j = 0; j < m; j++) {
    			if (chart[j][r1] != 0) {
    				chart[r1][r2] = chart[j][r1];
    				chart[r2][r1] = chart[j][r1];
    				contact = true;
    				break;
    			} else if (chart [r2][j] != 0) {
    				chart[r1][r2] = chart[r2][j];
    				chart[r2][r1] = chart[r2][j];
    				contact = true;
    				break;
    			} 
    		}
    		if (!contact) {
    			max_contact++;
    			chart[r1][r2] = max_contact;
    			chart[r2][r1] = max_contact;
    		}
    	}
    	for (i = 0; i < m; i++) {
    		group[relative[i][0]-1] = true;
    		group[relative[i][1]-1] = true;
    	}
    	for (i = 0; i < m; i++)
    		if (group[i] == false)
    			max_contact++;
    	return max_contact;
    }
    
    int main()
    {
    	FILE *fr, *fw;
    	int max_contact, m, n, i;
    	int **relative;
    	fr = fopen("relative.dat", "rt");
    	fw = fopen("relative.out", "wt");
    	fscanf(fr, "%d %d", &m, &n);
    	relative = make2darray(m, 2);
    	for (i = 0; i < n; i++)
    		fscanf(fr, "%d %d", &relative[i][0], &relative[i][1]);
    	printf("asdf");
    	max_contact = set_relative(relative, m, n);
    	fprintf(fw, "%d", max_contact);
    	fclose(fr);
    	fclose(fw);
    	return 0;
    }
    I have edited a new one. But still have errors...(but compiling error), overflow?

  7. #7
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  8. #8
    Registered User
    Join Date
    Apr 2005
    Posts
    77
    During my debugging, the main problem is that, can't read data from *.dat
    Code:
    relative = make2darray(m, 2);
    	for (i = 0; i < n; i++)
    		fscanf(fr, "%d %d", &relative[i][0], &relative[i][1]);
    WRONG...

  9. #9
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    Code:
    	for (i = 0; i < m; i++) {
    		group[relative[i][0]-1] = true;
    		group[relative[i][1]-1] = true;
    	}
    the value of relative[i][0] is sometimes 0, so subtracting 1 makes index into group array a negative, and illegal, value. You need to make sure relative array contains values greater than 0 before executing the above loop.

    If you replace malloc() with calloc(), calloc() will set all elements to 0 for you. Also note the loop counter uses x, not y as you had in your original code.
    Code:
    int **make2darray(int x, int y)
    {
    	int **array;
    	int i;
    	array = calloc(x,sizeof(**array));
    	for (i = 0; i < x; i++)
    		array[i] = calloc(y,sizeof(*array));
    	return array;
    }
    Last edited by Ancient Dragon; 10-31-2005 at 11:26 AM.

  10. #10
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    Quote Originally Posted by Mathsniper
    During my debugging, the main problem is that, can't read data from *.dat
    Code:
    relative = make2darray(m, 2);
    	for (i = 0; i < n; i++)
    		fscanf(fr, "%d %d", &relative[i][0], &relative[i][1]);
    WRONG...
    I had that problem too, but figured out that I did not create the file before running the program.

  11. #11
    Registered User
    Join Date
    Apr 2005
    Posts
    77
    the relative[i][0] and relative[i][0] > 0 absolutely.... so I haven't add a new conditional to determine its value.
    could anyone tell me, why does the prog. terminate at
    Code:
    	for (i = 0; i < n; i++)
    		fscanf(fr, "%d %d", &relative[i][0], &relative[i][1]);
    ?????????

  12. #12
    Registered User
    Join Date
    Apr 2005
    Posts
    77
    HELP T_T~~~ why doesn't this loop terminate?!!! can't read from file as relative is dynamic 2d array?!

  13. #13
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    look at the data file. The program is reading the first line to determine the number of lines in the file. the first line has 8, so your program is expecting 8 more lines. The file doen't have that many lines. Your program works ok if you correct the data file.
    Last edited by Ancient Dragon; 10-31-2005 at 11:58 AM.

  14. #14
    Registered User
    Join Date
    Apr 2005
    Posts
    77
    But the data is correct. the program still doesn't run. we can malloc n*2 martix.
    Code:
    relative = make2darray(n, 2);
    for (i = 0; i < n; i++)
       fscanf(fr, "%d %d", &relative[i][0], &relative[i][1]);
    now, m = 8, n = 3. so it must work absolutely.
    Code:
    8 3
    1 2
    1 4
    5 8
    GET WRONG.
    ---------------------
    I have to sleep =.= actually, I live in macao(hosting 4th east asia game city ). and now it's 02:15. post later.
    Last edited by Mathsniper; 10-31-2005 at 12:17 PM.

  15. #15
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    As I said -- either add more lines to the data file or change the first set of numbers to indicate the number of rows in the file. For the file contents you posted, the first number should be 3 because there are only 3 more lines in the file. The second number is 2 because each row in the file has only 2 numbers.
    Code:
    3 2
    1 2
    1 4
    5 8
    Did you correct make2darray() function as I indicated? If not, why not?

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with mallocing a 2d array please?
    By Gatt9 in forum C Programming
    Replies: 5
    Last Post: 10-10-2008, 04:45 AM
  2. cannot print out my 2d array correctly! please help
    By dalearyous in forum C++ Programming
    Replies: 5
    Last Post: 04-10-2006, 03:07 AM
  3. how to pass 2D array into function..?
    By IngramGc in forum C++ Programming
    Replies: 2
    Last Post: 10-21-2001, 09:41 AM
  4. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 10:48 AM
  5. 2d Array access by other classes
    By deaths_seraphim in forum C++ Programming
    Replies: 1
    Last Post: 10-02-2001, 09:05 AM

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