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

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

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

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 17.05.2010, 04:27   #1
Romer
Новичок
Джуниор
 
Регистрация: 04.05.2010
Сообщений: 2
По умолчанию Блок схема...очень нужно...

Помогите сделать блок схему или структурную схему к следующему алгоритму.

Эйлеровым циклом называется цикл в графе, проходящий через все ребра графа ровно один раз. Для данного графа найти эйлеров цикл, если он существует.
#include <iostream.h>
#include <stdio.h>
struct Node{
int inf;
Node *next;
};
//============================Stack== ============================
Node *init(){ // Инициализация стека
return NULL;
}
void push(Node *&st,int dat){ // Загрузка числа в стек
Node *el = new Node;
el->inf = dat;
el->next = st;
st=el;
}
int pop(Node *&st){ // Извлечение из стека
int value = st->inf;
Node *temp = st;
st = st->next;
delete temp;
return value;
}
int peek(Node *st){ // Получение числа без его извлечения
return st->inf;
}
//=================================== ===========================
Node **graph; // Массив списков смежности
const int vertex = 1; // Первая вершина
FILE* fi = fopen("e_graph.txt","r"); //Файл с матрицей смежности
FILE* fo = fopen("e_cycle.txt","w"); // Результирующий файл
void add(Node*& list,int data){ //Добавление смежной вершины
if(!list){list=new Node;list->inf=data;list->next=0;return;}
Node *temp=list;
while(temp->next)temp=temp->next;
Node *elem=new Node;
elem->inf=data;
elem->next=NULL;
temp->next=elem;
}
void del(Node* &l,int key){ // Удаление вершины key из списка
if(l->inf==key){Node *tmp=l; l=l->next; delete tmp;}
else{
Node *tmp=l;
while(tmp){
if(tmp->next) // есть следующая вершина
if(tmp->next->inf==key){ // и она искомая
Node *tmp2=tmp->next;
tmp->next=tmp->next->next;
delete tmp2;
}
tmp=tmp->next;
}
}
}
bool eiler(Node **gr,int num){ // Определение эйлеровости графа
int count;
for(int i=0;i<num;i++){ //проходим все вершины
count=0;
Node *tmp=gr[i];
while(tmp){ // считаем степень
count++;
tmp=tmp->next;
}
if(count%2==1)return 0; // степень нечетная
}
return 1; // все степени четные
}
void eiler_path(Node **gr){ //Построение цикла
Node *S = init();// Стек для пройденных вершин
int v=vertex;// 1я вершина (произвольная)
int u;
push(S,v); //сохраняем ее в стек
while(S){ //пока стек не пуст
v = peek(S); // текущая вершина
if(!gr[v]){ // если нет инцидентных ребер
v=pop(S); fprintf(fo,"%d\ ",v); //выводим вершину
}else {
u=gr[v]->inf; push(S,u); //проходим в следующую вершину
del(gr[v],u); del(gr[u],v); //удаляем пройденное ребро
}
}
}
int main(){
int n; // Количество вершин
int zn;// Текущее значение
fscanf(fi,"%d",&n); graph=new Node*[n];
for(int i=0;i<n;i++)graph[i]=NULL;
for(int i=0;i<n;i++) // заполняем массив списков
for(int j=0;j<n;j++){
fscanf(fi,"%d",&zn);
if(zn) add(graph[i],j);
}
if(eiler(graph,n))eiler_path(graph) ;
else fprintf(fo,"Граф не является эйлеровым.");
return(0);
}
Romer вне форума Ответить с цитированием
Ответ


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



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Очень срочно нужна блок схема :((( maximon Паскаль, Turbo Pascal, PascalABC.NET 12 17.06.2010 19:03
Pascal ! Нужно составить ! Алгоритм ! Блок схема ! valerka92 Помощь студентам 1 27.04.2010 10:04
Блок схема dimonpwnz Помощь студентам 0 12.02.2010 19:10
Блок схема алгоритма программы и схема взаимодействия модулей. Lazio Фриланс 3 02.12.2009 23:10
Нарисуйте пожалуйста блок-схему лёгкой задачки, не знаю как,очень нужно... prikolist Паскаль, Turbo Pascal, PascalABC.NET 2 28.11.2008 15:27