Представление трассы в виде двунаправленного списка.

Представить автотрассу в виде двунаправленного списка, элементы которого содержат информацию о названии населенных пунктов и расстоянии между ними. По заданным названиям двух населенных пунктов вычислить расстояние между ними. Лабораторная работа "Двунаправленные списики". Задача №11 (см. "Сборник задач для начинающего программиста")

Алгоритм:
1)считываем размер списка
2)создаем двунаправленный список, заданного размера, в каждом элементе которого храним название города и расстояние до следующего
3)пользователь запоняет список
4)пользователь вводит города, расстояине между которыми его интересует
5)проходим по списку, в поисках первого города, который ввел пользователь в 4-м пункте
как только нашли, начинаем складывать расстояние до тех пор пока не найдем второй
теперь наоборот, ищем второй город, и до нахождения первого складываем расстояния
6)выводим полученное в 5-м пукте число

#include <stdafx.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
 
struct Titem 
{																             // создаем структуру данных
 
		char c[ 50 ];        // здесь хранится название города
		int n;
		Titem *prev;	     // это указатель на следующий элемент в списке
 
}
*start,*last,*p,*p1;  
 
void CreateAvto( char *s, int dis )
{
 
	if ( start == NULL )	     // если элемент является первым в списке
	{
		start = new Titem;											
		strcpy( start -> c , s );	// заносим в него название города
		start -> n = dis;		// расстояние между соседними городами
		start -> prev = NULL;  
		start -> next = NULL;
		last = start;
	}
	else
	{
																	// если элемент не является первым в списке
 
		p = new Titem;												
		strcpy( p -> c , s );		// заносим название города
		p -> n = dis;			// заносим расстояние между соседними городами
		p -> next = NULL;											
		p -> prev = last;		// соединяем  вновь созданным элемент с предыдущим
		last -> next = p;		// соединяем предыдущий элемент с вновь созданным
		last = p;
	}
 
}
int DistanceResult ( char *s1, char *s2, int res )
{
 
	Titem *p, *p1;
	res = 0;
	p = start;
	p1 = start;
 
 
	while ( p != NULL )												
	{
 
		if ( strstr( s1, p -> c) )		// если нашли первый город
		{
			while ( !strstr ( s2, p -> c ) ) // до тех пор, пока не найдем второй город
			{
				res += p -> n;		// складываем расстояния
				p = p -> next;
			}
			return res;
		}
 
		if ( strstr( s2, p -> c ) )		// если нашли первый город
		{
			while ( !strstr(s1, p -> c) )	// до тех пор, пока не найдем первый город
			{
				res += p -> n;		// складываем расстояния
				p = p -> next;
			}
			return res;
		}
 
 
	 p = p -> next;
 
 	}
}
 
int main ()
{
 
	start = NULL;
	last = NULL;
 
	char city[ 50 ];
	char s1 [ 50 ], s2[ 50 ];
	int N = 0;
	int res = 0, dis = 0;
	int i = 0;
 
	printf ( "Kollichestvo gorodov \n");	// количество населенных пунктов
	scanf ( "%d", &N );
 
	for ( i = 0; i < N; i++ )		// заносим имена и расстояния в список
	{
		printf ( "Nazvanue gorodov \n" );							
		scanf ( "%s", city );
 
 
		if ( i != N - 1 ) 
		{															
 
			printf ( "Rasstoyznue mezdy gorodamu \n");	// введите расстояние между двумя соседними городами
			scanf ( "%d", &dis );
 
		}
		else
		{															                                     // если последний
			res=0;
		}
 
		CreateAvto( city, dis );
	}
 
	printf ( "vvedite nazvanuya interesyysix gorodov \n" );
	scanf ( "%s %s", s1, s2 );
	printf ( "%d ",DistanceResult ( s1, s2, res ) );
	getch();
	return 0;
}

Ключевые слова: 
двунаправленные списки, расстояние между городами
ВложениеРазмер
Desktop.rar9.78 кб