graph.cpp

一些关于数据结构的C语言实现源码

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

struct node{
	int value;
	struct node * next;
};
struct indexnode{
	int value;
	struct node * list_head;
};

#define MAXPATHLENGTH	10	//we limit the path length to be less than 10!
struct path{
	int path_record[MAXPATHLENGTH];		//record the path
};
//IMPORTANT: use this as the parameter, 'cause if pure array is used as
//	a parameter only the pointer is transferred to the function!

#define	NODENUMBER 5

//--------------------------	golbal variables definition	--------------------------
struct indexnode index_array[NODENUMBER+1];	//the graph
int  required_distance;	//store the distance needed to be match
int  path_serialnumber = 0;	//the i-th path
//--------------------------	golbal variables definition	--------------------------
//--------------------------	routines about the graph	--------------------------
void list_add( int base, int value );
void initialize_graph( void )
{
  int i;
  for ( i=1; i<=NODENUMBER; i++ ){
	index_array[i].value = i;
	index_array[i].list_head = NULL;
  }
  //list of node 1
  list_add( 1, 2 );
  list_add( 1, 4 );
  list_add( 1, 5 );
  //list of node 2
  list_add( 2, 1 );
  list_add( 2, 4 );
  list_add( 2, 3 );
  //list of node 3
  list_add( 3, 2 );
  list_add( 3, 4 );
  //list of node 4
  list_add( 4, 2 );
  list_add( 4, 1 );
  list_add( 4, 5 );
  list_add( 4, 3 );
  //list of node 5
  list_add( 5, 1 );
  list_add( 5, 4 );
}
void list_add( int base, int value )
{
  struct node *p, *q;

  q = (struct node*) malloc( sizeof(struct node) );
  q -> value = value;
  q -> next = NULL;

  if (index_array[base].list_head == NULL)
	index_array[base].list_head = q;
  else{
	for( p = index_array[base].list_head; p->next!=NULL; p=p->next);
	p -> next = q;
  }
  return;
}
void free_graph()
{
  int i;
  struct node *p, *q;
  for ( i=1; i<=NODENUMBER; i++ ){
	for( p=index_array[i].list_head; p!=NULL; ){
		q = p;
		p = p->next;
		free( q );
	}
  }
}
//--------------------------	routines about the graph	--------------------------

//--------------------------	routines about the pathfinding	----------------------
//this routine is used to detect whether a node once appeared before in the
// whole path, if so return 1 else return 0
int is_appeared( int nodenumber, int currentpos, struct path *record )
{
   int i;
   if ( currentpos >= required_distance ) return 0; //meaningless!
   for ( i=required_distance; i>=currentpos; i-- ){
	if ( record->path_record[i] == nodenumber ) return 1;
   }
   return 0;
}

void show_path( struct path *record )
{
   int i;
   printf( "%d Path Found: OccuranceNumber\tNodeNumber\n", ++path_serialnumber );
   for( i=required_distance; i>=0; i-- ){
	printf( "\t\t%d\t\t%d\n", required_distance-i, record->path_record[i] );
   }
}

void deep_distance(int start, int dest, int distance, struct path path_param)
{
   struct node *p, *q;

   path_param.path_record[distance] = start;
   if ( (distance==0) && (start==dest) ){
	show_path( &path_param );
	return;
   }else if (distance==0){
	return;
   }

   p = index_array[start].list_head;
   distance--;
   while( p!= NULL ){
	if ( !is_appeared( p->value, distance+1, &path_param ) )
		deep_distance( p->value, dest, distance, path_param );
	p = p->next;
   }
}
//--------------------------	routines about the pathfinding	----------------------

void main()
{
   int start, dest, i;
   struct path	path_array;

   clrscr();
   printf( "Please input the start node numbe:" );
   scanf( "%d", &start );
   printf( "Please input the destination node numbe:" );
   scanf( "%d", &dest );
   printf( "Please input the required length:" );
   scanf( "%d", &required_distance );

   if ( required_distance >= MAXPATHLENGTH ){
	printf( "ERROR:The distance should be less than %d!\n", MAXPATHLENGTH );
	return;
   }

   for( i=0; i<MAXPATHLENGTH; i++ ) path_array.path_record[i] = 0;
   initialize_graph();
   deep_distance( start, dest, required_distance, path_array );
   free_graph();
   if ( path_serialnumber == 0 ) printf( "Sorry NO path is found!\n" );
}