Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Amsteri
0 / 0 / 0
Регистрация: 27.09.2013
Сообщений: 24
#1

помошите з ошыбками - C++

09.12.2013, 19:37. Просмотров 148. Ответов 0
Метки нет (Все метки)

//Знаходження відстані від джерела до всіх вершин в графі

//з ненегативними вагами (метод Дейкстри).

//Знаходження найкоротшого шляху з S в T.

# include <iostream.h>

# define MaxNodes 7

# define B 1000 //Машинний еквівалент нескінченності.

//Опис типу вузла стека.

typedef struct Zveno *svqz;

typedef struct Zveno {

int Element;

svqz Sled; };

//======================================================================

classSpisok {

private:

int A[MaxNodes][MaxNodes]; //Матриця вагів дуг.

int D[MaxNodes]; //Матриця відстаней від джерела до

//всіх вершин графа.

svqz Stack; //Вказівник на робочий стек.

void UDALENIE(svqz *, int *);

void W_S(svqz *, int);

int Pusto_Q( int *);

public:

Spisok() {Stack = NULL;}

void Vvod_Ves();

void Reshenie(); };

//======================================================================

void main() {

Spisok A;

A.Vvod_Ves();

A.Reshenie(); }

//======================================================================

int Spisok::Pusto_Q( int *Q) {

for( int i=0;i<MaxNodes;i++)

if( *(Q+i)!=0 ) return 0; //Брехня – не порожньо!

return 1; //Істина – порожньо!

}

//======================================================================

void Spisok::Reshenie() {

int S; //Початкова вершина шляху (джерело).

int T; //Кінцева вершина шляху.

int u,v,Min;

int i,j,k;

svqz UkZv;

int Q[MaxNodes];

cout<<"Введіть джерело: ";

cin>>S; S--;

//Ініціалізація.

for(i=0;i<MaxNodes;i++) { D[i]= A[S][i]; Q[i]= 0; }

D[S]= 0;

for(i=0;i<MaxNodes;i++) Q[i]= 1;

Q[S]= 0;

//Обчислення матриці відстаней від джерела до всіх вершин графа.

while(!Pusto_Q(&Q[0])) { //Поки Q не порожньо.

Min = B;

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

if(Q[i]==1 && D[i]<Min) { Min = D[i]; u = i; }

Q[u]= 0;

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

if(Q[i]== 1)

if( D[i]> D[u]+A[u][i] ) D[i]= D[u]+ A[u][i]; }

//Виведення матриці відстаней від джерела до всіх вершин графа.

cout<<"Матриця відстаней:\n";

for(i=0;i<MaxNodes;i++) cout<<D[i]<< " ";

cout<<endl;

// -----------------------------------------------------------------

//Знаходження найкоротшого шляху з S в T з використанням побудованої

//матриці відстаней.

// -----------------------------------------------------------------

cout<<"Введіть кінцеву вершину шляху: ";

cin>>T; T--;

W_S(&Stack,T);

v = T;

while( v!=S ) {

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

if( D[v]==D[i]+A[i][v] ) u = i;

W_S(&Stack,u);

v = u; }

//Виведення найкоротшого шляху на екран дисплея.

cout<<"Найкоротший шлях: ";

UkZv = Stack;

while( UkZv != NULL ) {

cout<<(UkZv->Element+1)<<" ";

UkZv = UkZv->Sled; }

cout<<endl; }

//======================================================================

void Spisok::Vvod_Ves() {

//Введення матриці вагів дуг заданого графа.

cout<<"Вводьте елементи матриці вагів дуг по стрічкам:\n";

for( int i=0;i<MaxNodes;i++)

for( int j=0;j<MaxNodes;j++) {

cout<<"Введіть A[" <<(i+1)<<"," <<(j+1)<<"]: ";

cin>>A[i][j];

if( A[i][j]==0 ) A[i][j]= B; } }

//======================================================================

voidSpisok::W_S(svqz *stk, int Elem) {

//Приміщення Elem в стек stk.

svqz q= new(Zveno);

(*q).Element = Elem;

(*q).Sled = *stk;

*stk = q; }

//======================================================================

voidSpisok::UDALENIE(svqz *stk, int *Klad) {

//Видалення ланки із стека, заданого вказівником *stk. Значення

//інформаційного поля ланки зберігається в параметрі Klad.

svqz q;

if( *stk == NULL ) cout<<"Спроба вибору з порожнього стека!\n";

else *Klad =(**stk).Element;

q = *stk;

*stk =(**stk).Sled;

delete q; } }
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru