Thread: Segmentation Fault, could not find after debugging

Technically a homework question, though the deadline is past due. For learning purposes only, I want to know what was wrong with my code when I submitted. It's a Traveling Salesperson Problem, and the code is complete for the most part. I just can't seem to find what's causing the segmentation fault even after attempting to debug with gdb. Something is supposed to be wrong with line 76, but I don't see how my arrays are messing up. I've looked through this code countless times, and I know I'm just missing something small. Any advice would be appreciated -I just don't want to end up making whatever mistake I made on this again in the future.

Code:

#include <stdio.h>
#include <stdlib.h>
#define SIZE 20


int adjacency[SIZE][SIZE];
int best_cost;
int *BestList;
int permutations = 0;
void print_tour(int[],int,int);
main()
{
	int best_cost;
	void print_tour();
	void permute_list();
	int i,j,weight,num;
	int *NodeList;
	char c;
	int cost;
	int thisCost;


	for( i = 0; i < SIZE; i++ )
		for( j = 0; j < SIZE; j++ )
			adjacency[i][j] = -1;			


	while( scanf("%c",&c) != EOF )				// Read input and build adjacency matrix
        {
		if( c == 'c' )
			{
            scanf("%d",&num);
            }
            else if( c == 'a' )
                {
                scanf("%d%d%d",&i,&j,&weight);
				adjacency[i][j] = weight;			
				adjacency[j][i] = weight;			
                }
        }
	
	NodeList = (int *) malloc(num * sizeof(int));
	BestList = (int *) malloc(num * sizeof(int));
	
	for( i = 0; i < num; i++ )
		{
		NodeList[i] = i + 1;
		BestList[i] = i + 1;
		}
        
	best_cost = 1000000000;
	permute_list(NodeList,num,num);
	print_tour(BestList,num,best_cost);				// printf("After checking %d permutations,\n",permutations);
}


void permute_list(A,num,n)
	int A[],num,n;
{
	int i,j,temp;
	int cost;
	int start = n - num + 1; // if you want to "set" the first city.
//	int start = n - num;	// if you want to try ALL permutations


	if( num == 1 )
	{
	cost = compute_cost(A,n);
	if( cost < best_cost )
		{
		int k;
		best_cost = cost;
		for(k = 0; k < n; k++)
		BestList[k] = A[k];			
		}
	return;
	}


	for(i = start; i < n; i++)
		{
		permute_list(A,num-1,n);
		temp = A[n-1];						//rotate the list 
		for( j = n-1; j > start; j-- ) 
			{
			A[j] = A[j-1];
			}
		A[start] = temp;
		}
}


int compute_cost(List,num)
	int List[],num;
	{
	int cost = 0;
	int i;
	for(i = 0; i < num-1; i++);
		cost += adjacency
[List[i]]
[List[i+1]];			//permutations++;
		cost +=  adjacency
[List[i]]
[List[0]];			//print_tour(List,num,cost);
	return cost;
}


void print_tour(List,num,cost)
	int List[],num,cost;
	{
	int i;
	printf("The tour ");
	for( i = 0; i < num; i++ )
		printf("%d ", List[i]);
	printf("%d ", List[0]);
	printf(" costs %d\n",cost);
	}


/*The tour 1 9 10 5 6 7 3 2 4 8 1  costs 2000*/

Originally Posted by AAnderson

Sorry I can't answer your question off the top of my head, but in my admittedly very short experience with C, I haven't seen the practice of declaring your function inputs outside the curly bracers, for example in your permute list function declaration.

I'm curious why you did it like that?

It very old old style from the K&R book.
c - Function declaration: K&R vs ANSI - Stack Overflow

Tim S.

Originally Posted by Campocalypse

The last comment is the expected output. Figured you would need to know what I'm trying to get if you wanted to help me

I expect no output; if the program is NOT given any input.

Tim S.

You have two different variables called "best_cost"; and a lot of old K&R Function definitions.

The Global "best_cost" is NOT positively set to a valid value before you use it.

Tim S.

Problem with this line of code.

Code:

for(i = 0; i < num - 1; i++);

Hint: The problem is very close to the end of the line.

Tim S.