Memory problem

This is a discussion on Memory problem within the C Programming forums, part of the General Programming Boards category; I have this program: Code: #include <stdio.h> #include <stdlib.h> #define MAX 1000 /* Array limit */ #define oo 1000000000 /* ...

  1. #1
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82

    Memory problem

    I have this program:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #define MAX 1000  /* Array limit */
    #define oo 1000000000 /* "infinite" */
    
    int adj[MAX][MAX];
    int percurso[MAX];
    int cara=0,coroa=0;
    int maxpeso=-1000000000; /* another infinite */
    int in;
    int ja_ta=0;
    int somei=0;
    void poe_na_fila(int x) 
    {
    	percurso[coroa]=x;
    	coroa++;
    }
    
    int somador(int percurso[],int nos)
    {
    	int i=0,soma=0;
    	somei=1;
    	for(i=0; i< coroa-1;i++)
    		soma += adj[percurso[i]][percurso[i+1]];
    	return soma;
    }
    		
    void max_peso(int source, int sink, int nodes, int j)
    {
        int num;
        int u = 0, n = 0;
        if ( ja_ta ) return;
        if (j > nodes && source == in) 
        {
            ja_ta = 1;
            return;
        }
        else
        {
            if (source == sink) {
                poe_na_fila(source);
            }
            else
            {
                if (j > nodes)
                {
                    percurso[coroa] = 0;
                    coroa -= 1;
                    max_peso(percurso[coroa], sink, nodes, source + 1);
                }
                else
                {
                    if (adj[source][j] == oo) {
                        max_peso(source, sink, nodes, j + 1);
                    }
                    else
                    {
                        poe_na_fila(source);
                        max_peso(j, sink, nodes, 0);
                    }
                }
            }
            if ( ja_ta ) return;
            else
            {
            n = somador(percurso, nodes);
            if (n > maxpeso)
                maxpeso = n;
            coroa = coroa - 1;
            percurso[coroa] = 0;
            coroa = coroa - 1;
            max_peso(percurso[coroa], sink, nodes, source + 1);
            }
        }
    }
    
    main (int argc, char *argv[])
    {
    	int noi,nof,peso,i,u,j,arcos,nos,inicio,fim;
    	inicio=fim=noi=nof=i=j=peso=arcos=nos=u=0;
    	FILE *fp;
    	fp=fopen(argv[1],"r");
    	if (fp==NULL)
    		printf("Impossível abrir o ficheiro %s", argv[1]);
    	else
    		{
    			fscanf(fp,"%d",&nos);
    			fscanf(fp,"%d",&arcos);
    			for(u=0;u<=nos;u++)
    			{
    				percurso[u]=0;
    			}
    			for(i=0; i<=nos;i++)
    			{
    				for(j=0;j<=nos;j++)
    					adj[i][j]=oo;
    			}
    			for(i=0;i<arcos;i++)
    			{
    				
    				fscanf(fp,"%d %d %d", &noi,&nof,&peso);
    				adj[noi][nof]=peso;
    			}
    			fscanf(fp,"%d %d", &inicio, &fim);
    			in=inicio;
    			max_peso(inicio,fim,nos,0);
    			if(somei)
    			printf("%d\n",maxpeso);
    			else
    			printf("NA\n");
    		}
    		
    
    }
    It works perfectly,but my teachers are a bit nuts and will put inputs with more than 15Mb!The problem is i have a limit for my arrays or matrices. For example, for the adj matrice i need 2000000 bytes and most of them (half) are not used. I saw an example with 16 millions(!) possible combinations, that would mean a 16 million * 16 million matrice!My question is simple:
    is there any way of using malloc or something like it,to alloc the necessary space for the adj and percurso arrays?16 million...

  2. #2
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    You better find a more efficient way to do it, because that would require almost an exobyte of memory (1 exobyte = 1 000 terabytes = 1 000 000 gigabytes).
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  3. #3
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    The problem is that i´m supposed to work with the matrices...Daam...Any other ideas would be helpful...

  4. #4
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Allocate an array dynamically, using the right dimensions. There's plenty of sample code on here for doing that...
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  5. #5
    Registered User
    Join Date
    Apr 2003
    Posts
    23
    Well, if you decided to move to C++ here's a dynamic array class that I've been using, you might interest in it.
    Attached Files Attached Files
    Last edited by Mercury_Linx; 04-21-2003 at 12:59 AM.
    Merc

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with atl memory cleaning
    By Mariam1989 in forum Windows Programming
    Replies: 1
    Last Post: 11-11-2008, 12:35 PM
  2. Pointer's
    By xlordt in forum C Programming
    Replies: 13
    Last Post: 10-14-2003, 03:15 PM
  3. Is it necessary to write a specific memory manager ?
    By Morglum in forum Game Programming
    Replies: 18
    Last Post: 07-01-2002, 02:41 PM
  4. memory allocation problem with 2 dimensional array
    By nano_nasa in forum C++ Programming
    Replies: 7
    Last Post: 06-13-2002, 12:34 PM
  5. Memory Problem - I think...
    By Unregistered in forum C Programming
    Replies: 4
    Last Post: 10-24-2001, 01:14 PM

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