Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 28.03.2015, 17:45   #1
7Sky
Новичок
Джуниор
 
Регистрация: 28.03.2015
Сообщений: 1
По умолчанию коментарии к коду С++

Может кто то помочь прокомментировать основные моменты в коде?
Реализация алгоритма Дейкстры.
Код:
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream>

#define word unsigned int

using namespace std;

int i, j, n, p, xn, xk;

int flag[11];

word c[11][11], l[11];

char s[80], path[80][11];

int min(int n)

{

int i, result;

for(i=0;i<n;i++)

if(!(flag[i])) result=i;

for(i=0;i<n;i++)

if((l[result]>l[i])&&(!flag[i])) result=i;

return result;

}

word minim(word x, word y)

{

if(x<y) return x;

return y;

}

int main()
{
cout << "Vvedite kolichestvo tochek: ";
cin>>n;
for(i=0;i<n;i++)
for(j=0;j<n;j++) c[i][j]=0;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)

{

cout<<"Vvedite rasstoyanie ot x"<<i+1<<" do x"<<j+1<<": ";

cin>>c[i][j];

}

cout<<" ";

for(i=0;i<n;i++) cout<<" X"<<i+1;

cout<<endl<<endl;

for(i=0;i<n;i++)

{

printf("X%d",i+1);

for(j=0;j<n;j++)

{

printf("%6d",c[i][j]);

c[j][i]=c[i][j];

}

printf("\n\n");

}

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(c[i][j]==0) c[i][j]=65535; //бесконечность

cout<<"Vvedite nachalnuy tochku: ";

cin>>xn;

cout<<"Vvedite konechnuy tochku: ";

cin>>xk;

xk--;

xn--;

if(xn==xk)

{

cout<<"Nachalnaya I konechnaya tochki sovpadayt."<<endl;

getch();

return 0;

}

for(i=0;i<n;i++)

{

flag[i]=0;

l[i]=65535;

}

l[xn]=0;

flag[xn]=1;

p=xn;

itoa(xn+1,s,10);

for(i=1;i<=n;i++)

{

strcpy(path[i],"X");

strcat(path[i],s);

}

do

{

for(i=0;i<n;i++)

if((c[p][i]!=65535)&&(!flag[i])&&(i!=p))

{

if(l[i]>l[p]+c[p][i])

{

itoa(i+1,s,10);

strcpy(path[i+1],path[p+1]);

strcat(path[i+1],"-X");

strcat(path[i+1],s);

}

l[i]=minim(l[i],l[p]+c[p][i]);

}

p=min(n);

flag[p]=1;

}

while(p!=xk);

if(l[p]!=65535)

{

cout<<"Put: "<<path[p+1]<<endl;

cout<<"Dlina puti: "<<l[p]<<endl;

}

else

cout<<"takogo puti ne syshestvuet!"<<endl;

getch();

}
7Sky вне форума Ответить с цитированием
Старый 28.03.2015, 17:55   #2
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,618
По умолчанию

В данном случае проще написать новый код по твоей задаче, чем разобраться в этом )
Глобальные переменные, магические числа, загадочные имена переменных все это обеспечивают.

Может быть в этом может разобраться автор кода (если писал недавно) - можно обратиться к нему.
Но можно озвучить условие задачи и начать ее решать самостоятельно, мы поможем советами.
rrrFer вне форума Ответить с цитированием
Старый 29.03.2015, 02:14   #3
challengerr
Участник клуба
 
Аватар для challengerr
 
Регистрация: 30.07.2008
Сообщений: 1,639
По умолчанию

Комментарии

Код:
// алгоритм поиска кратчайшего пути (алгоритм Дейкстры, 1959)

#include <string.h>
#include <stdio.h>
#include <locale.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream>

#define word unsigned int

using namespace std;

int i, j, // итераторы
n, // количество точек
p, 
xn, 
xk;
int flag[11];
word c[11][11], 
l[11];
char s[80], 
path[80][11];

// поиск и возврат минимального значения
int min(int n)
{
int i, result;
for(i = 0; i < n; i++) if( ! (flag[i]) ) result = i;
for(i = 0; i < n; i++) if( (l[result] > l[i]) && (! flag[i]) ) result = i;
return result;
}

// определяет минимальное из двух аргументов x,y
word minim(word x, word y) { if(x < y) return x; return y; }

int main()
{
setlocale(LC_ALL, "Russian");
cout << "Введите количество точек: "; cin >> n;
for(i = 0; i < n; i++) for(j = 0; j < n; j++) c[i][j] = 0; // обнуление массива

for(i = 0; i < n; i++) for(j = i + 1; j < n; j++) { cout<<"Введите расстояние от x[" << i+1 

<< "] до x[" << j + 1 << "]: "; cin >> c[i][j]; }  // ввод графа (списка вершин) как 

диагональной, верхней треугольной матрицы

cout<<" "; for(i = 0;i < n; i++) cout<<" X"<<i+1; cout<<endl<<endl; // вывод списка 

вершин

for( i = 0; i < n; i++) { printf("X%d", i + 1); //вывод названия вершины
for( j = 0; j < n; j++) { printf("%6d",c[i][j]); c[j][i] = c[i][j]; } // перенос из верхней 

треугольной матрицы в нижнюю треугольную матрицу графа
printf("\n\n"); } // вывод весов

for(i=0;i<n;i++) for(j=0;j<n;j++) if(c[i][j]==0) c[i][j]=65535; //бесконечность // если 

расстояние равно 0, то установить его в 65535

cout<<"Введите начальную точку: "; cin>>xn; xn--;
cout<<"Введите конечную точку: "; cin>>xk; xk--; 

if( xn == xk ) { cout<<"Начальная и конечная точки совпадают."<<endl; getch(); 

return 0; } // выход, т.к. задача не имеет смысла

for(i = 0; i < n; i++) { flag[i] = 0; l[i] = 65535; } // заполнение массивов flag и l

l[xn] = 0;
flag[xn] = 1; // флаг того, что посещена начальная вершина
p = xn;
itoa(xn+1,s,10); // запись xn+1 в строку s

for(i = 1; i <= n; i++) { strcpy(path[i],"X"); strcat(path[i],s); } // конкатенация 

наименования вершины к строке

// все вершины связаны друг с другом
// цикл алгоритма Дейкстры пока из начальной точки не попали в конечную
do
{

for(i = 0;i < n; i++) // перебор вершин графа
if( (c[p][i] != 65535) && (! flag[i]) && (i != p) ) // условие: если вершина еще не посещена, если начальная и конечная вершина не совпадают, если вершина не равна условной бесконечности
{
if ( l[i] > l[p] + c[p][i] ) { itoa(i+1,s,10); strcpy(path[i+1],path[p+1]); strcat(path[i+1],"-X"); 

strcat(path[i+1],s);} // конкатенация наименования вершины к строке, если она входит в путь
l[i] = minim( l[i], l[p]+c[p][i] ); // определение минимума из l[i] и l[p]+c[p][i]  и запись в l[i]
}

p = min(n); // переход в следующую вершину пути
flag[p] = 1; // указывает, что вершина рассмотрена
}
while(p != xk);
// окончание алгоритма

if( l[p] != 65535 ) { cout<<"Путь: "<<path[p+1]<<endl; cout<<"Длина пути: "<<l[p]

<<endl; } // вывлд пути
else cout<<"такого пути не существует!"<<endl; 
cout<<"нажмите любую клавишу"<<endl;  getch();
}
"SPACE.THE FINAL FRONTIER.This's a voyage of starship Enterprise. It's 5-year mission to explore strange new worlds,to seek out new life and civilizations,to boldly go where no man has gone before"
challengerr вне форума Ответить с цитированием
Старый 29.03.2015, 04:42   #4
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,618
По умолчанию

Цитата:
Комментарии
Плюсанул бы, но форум запрещает это делать слишком часто ((
rrrFer вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
коментарии к коду peredoz Помощь студентам 5 22.12.2012 22:39
коментарии к коду С++ dymych Помощь студентам 0 09.11.2010 16:35
коментарии parovoz121 Помощь студентам 0 18.06.2010 13:44
обьяснения (коментарии) к коду: Programmer20101 Общие вопросы Delphi 12 18.05.2010 18:36
C++. нужни коментарии к коду программы Myau Thai Помощь студентам 1 04.06.2009 19:32