необходимо разобраться с кодом

[tema65]

Здравствуйте, может кто-нибудь прокомментировать что каждая функция в этом коде означает? Здесь рассмотрен метода Прима для нахождения наикратчайшего пути

int wpchk(int w, int *wpts)
{
int i=0;
int flg=0;
while(wpts[i]!=-1)
{
if(wpts[i]==w){flg=1;}
i++;
}
 
if (flg==0) {return 0;} else return 1;
}
 
void main()
{
srand( (unsigned)time( NULL ) );
 
//int prices[10][10];
int waypoint[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1};
int way[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
int start=-1;
int end=-1;
int min;
int imin;
 
*/// 0 1 2 3 4 5 6 7 8 9
int prices[10][10]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //0
0, 0, 2, 9, 8, 0, 0, 0, 0, 0, //1
0, 2, 0, 3, 0, 20,0, 0, 0, 0, //2
0, 9, 3, 0, 7, 4, 0, 0, 0, 0, //3
0, 8, 0, 7, 0, 11,0, 0, 0, 0, //4
0, 0, 20,4, 11,0, 0, 0, 0, 0, //5
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //6
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //7
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //8
0, 0, 0, 0, 0, 0, 0, 0, 0, 0};//9
 
printf("Enter № of start location:");
scanf("%i",&start);
printf("Enter № of finish location:");
scanf("%i",&end);
waypoint[0]=start;
int n=0;
int w;
while(waypoint[n]!=end)
{
min=0;
w=waypoint[n];
for(int i=0;i<10;i++)
{
if(((min==0)||((prices[w][i]<min)&&(prices[w][i]>0)))&&wpchk(i,waypoint)==0) {min=prices[w][i];imin=i;}
}
n++;
waypoint[n]=imin;
}
 
printf("\nThe way is:\n");
int i=0;
while(waypoint[i]!=-1)
{
printf("%i ",waypoint[i]);
i++;
}
getchar();
getchar();
}

[БалаШагаЛ]

Надо было код хоть как-то разметить по-хорошему, чтоб красиво выглядел.
Алгоритма самого этого не знаю, но в коде разобраться попробовал. Вот что получилось:

int wpchk(int w, int *wpts)
{
int i=0;
int flg=0;
while(wpts[i]!=-1)//Пока мы не дошли до элемента со значением -1 (то есть ещё необработанного)
{
    if(wpts[i]==w)//Если он равен переданной точке
      flg=1;//То делаем возвращаемое значение один
    i++;
}
 if (flg==0) {return 0;} else return 1;
//Вывод:
//Функция проверяет, была ли переданная в первом аргументе точка уже включена в путь
//P. S.: А возвращаемое значение можно было бы и bool поставить
}

void main()//main - основная функция. Та функция, которая будет выполняться изначально при запуске программы
{
srand( (unsigned)time( NULL ) );
 
//int prices[10][10];
int waypoint[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1};//Если я правильно понял, то номера точек, через которые идёт путь
int way[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
int start=-1;//Номер старстовой позиции
int end=-1;//Номер конечной позиции
int min;
int imin;
 
//Как я понял, это массив точек. Только странно как-то составленный, лучше было бы массив POINT-ов сделать
//Номер точки с координатами (x;y) является элементами массива с номерами [y][x] и [x][y]
// 0 1 2 3 4 5 6 7 8 9
int prices[10][10]=
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //0
0, 0, 2, 9, 8, 0, 0, 0, 0, 0, //1
0, 2, 0, 3, 0, 20,0, 0, 0, 0, //2
0, 9, 3, 0, 7, 4, 0, 0, 0, 0, //3
0, 8, 0, 7, 0, 11,0, 0, 0, 0, //4
0, 0, 20,4, 11,0, 0, 0, 0, 0, //5
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //6
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //7
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //8
0, 0, 0, 0, 0, 0, 0, 0, 0, 0};//9
 
printf("Enter № of start location:");//Функция printf - форматированный вывод на экран
scanf("%i",&start);//Функция scanf - форматированный ввод с клаиатуры
printf("Enter № of finish location:");
scanf("%i",&end);
waypoint[0]=start;
int n=0;
int w;
while(waypoint[n]!=end)//Пока мы не пришли в конечную точку
{
min=0;//Обнуляем min
w=waypoint[n];//-1 практически, кроме последнего
for(int i=0;i<10;i++)
{
    if (((min==0)||
         ((prices[w][i]<min)&&(prices[w][i]>0)))&&
        wpchk(i,waypoint)==0)//Последнее условие означает, что точка ранее не была пройдена
                             //Кстати, красивее выглядело бы !wpchk(i,waypoint)
    {
        min=prices[w][i];
        imin=i;
    }
}
n++;
waypoint[n]=imin;
}
 
printf("\nThe way is:\n");
int i=0;
while(waypoint[i]!=-1)//Выводить только "активированные" точки
{
printf("%i ",waypoint[i]);//Вывод точки
i++;
}
getchar();//Функция getchar() (или getch()) возвращает код нажатой клавиши. Здесь используется её свойство ожидать нажатие клавиши
getchar();//Только непонятно, зачем эта функция используется здесь два раза
}

[tema65]

спасибо), здесь используется алгоритм Прима. дана матрица, значения которой есть расстояния между точками городами. Нужно определить минимальный путь, проходящий через все точки, с возвращением в начальную... берется точка, потом ищется минимальное ребро(расстояние до другой точки), после обнаружения данного ребра точки соединяют между собой , после чего опять ищется минимальное ребро и т.д. пока не вернемся в начальную точку и не построится минимальный остовной граф.

while(wpts[i]!=-1) \\а что выполняется в данной строке?

[Stilet]

В этой строке говорится что цикл будет крутиться пока wpts[i] равен -1-це

[tema65]

а что хранит переменная wpchk? (кол-во точек через которые идет путь?)

[Stilet]

wpchk это не переменная а функция.

[БалаШагаЛ]

Это алгоритм нахождения минимального пути? Аааа! Так вы ж меня спасли, мне ж как раз он и нужен. Спасибо вам большое!

[tema65]

Сообщение от Stilet

wpchk это не переменная а функция.

а для чего она используется?