Thread: 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?

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];

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.

http://www.eskimo.com/~scs/C-faq/q6.16.html

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;
}

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.

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.