Вход на сайт
Программирование в С
976 просмотров
Перейти к просмотру всей ветки
в ответ lisenkalejka 29.05.15 18:48, Последний раз изменено 01.06.15 12:41 (BorisL0)
Я бы предложил следующий алгоритм, пока только для прочтения графа из файла.
В C неудобно создавать массивы (вершин, ребер) по ходу 1-го чтения файла,
т.к. неизвестно, каких размеров будет итоговый массив. Поэтому мне кажется, проще всего считать этот
файл дважды:
1-й раз: просто прочесть имя графа (GraphBezeichner) и количество ребер (строк с ->). После этого мы получаем это значение NKanten и закрываем файл командой fclose();
Создаем массивы (т.е. выделяем память командами malloc для ребер array_kanten (тип самого ребра я бы задал так struct Kante {int ausgangsKnote, eingangsKnote;}; ) размера NKanten и array_knoten вершин -- тут мы точного кол-ва пока не знаем (будет посчитано после 2-го прочтения файла), но можем взять по максимуму размера 2*NKanten. Тип элемента этого массива, например struct Knote{char name[257]; int ausgangsZahl, eingangsZahl;};)
2-й раз: каждое из ребер считываем командой n=scanf("%s%s%s", s1, s2, s3), где s1 и s3 -- массивы char размера 258 (под имена вершин), а s2 -- просто техническая ненужная вещь, куда сохраняется "стрелочка".
От s3 с конца нужно не забыть убрать лишний символ ";"
После прочтения каждого ребра нужно установить, встречались ли эти 2 вершины раньше (т.е. их имена сохранены в массиве array_knoten), или это новая/ые вершины, которые туда нужно сохранить (и при этом увеличить счетчик кол-ва вершин). В любом случае,
у нас получается соответствие между индексом(номером) вершины в массиве array_knoten и ее именем (которое сохраняется в поле name структуры Knote). Необходимо также для прочитанного ребра сохранить его
информацию, т.е. ausgangsKnote, eingangsKnote в соотв. элементе массива array_kanten.
Снова закрыть файл fclose();
После этого можно для каждой из сохраненных вершин в массиве array_knoten посчитать кол-во исходящих и входящих в нее ребер. Для этого просто пройти циклом по массиву ребер и проверить, где номер начальной
или конечной вершины совпадает с номером той, которую мы сейчас анализируем. Эти числа нужно сохранить в элемент массива array_knoten[ i ].ausgangsZahl и
array_knoten[ i ].eingangsZahl.
Уже сейчас можно вывести информацию, как первый Meilenstein, про кол-во ребер, вершин, и макс/мин исходящих/входящих ребер.
Пока все с этой частью алгоритма.
В C неудобно создавать массивы (вершин, ребер) по ходу 1-го чтения файла,
т.к. неизвестно, каких размеров будет итоговый массив. Поэтому мне кажется, проще всего считать этот
файл дважды:
1-й раз: просто прочесть имя графа (GraphBezeichner) и количество ребер (строк с ->). После этого мы получаем это значение NKanten и закрываем файл командой fclose();
Создаем массивы (т.е. выделяем память командами malloc для ребер array_kanten (тип самого ребра я бы задал так struct Kante {int ausgangsKnote, eingangsKnote;}; ) размера NKanten и array_knoten вершин -- тут мы точного кол-ва пока не знаем (будет посчитано после 2-го прочтения файла), но можем взять по максимуму размера 2*NKanten. Тип элемента этого массива, например struct Knote{char name[257]; int ausgangsZahl, eingangsZahl;};)
2-й раз: каждое из ребер считываем командой n=scanf("%s%s%s", s1, s2, s3), где s1 и s3 -- массивы char размера 258 (под имена вершин), а s2 -- просто техническая ненужная вещь, куда сохраняется "стрелочка".
От s3 с конца нужно не забыть убрать лишний символ ";"
После прочтения каждого ребра нужно установить, встречались ли эти 2 вершины раньше (т.е. их имена сохранены в массиве array_knoten), или это новая/ые вершины, которые туда нужно сохранить (и при этом увеличить счетчик кол-ва вершин). В любом случае,
у нас получается соответствие между индексом(номером) вершины в массиве array_knoten и ее именем (которое сохраняется в поле name структуры Knote). Необходимо также для прочитанного ребра сохранить его
информацию, т.е. ausgangsKnote, eingangsKnote в соотв. элементе массива array_kanten.
Снова закрыть файл fclose();
После этого можно для каждой из сохраненных вершин в массиве array_knoten посчитать кол-во исходящих и входящих в нее ребер. Для этого просто пройти циклом по массиву ребер и проверить, где номер начальной
или конечной вершины совпадает с номером той, которую мы сейчас анализируем. Эти числа нужно сохранить в элемент массива array_knoten[ i ].ausgangsZahl и
array_knoten[ i ].eingangsZahl.
Уже сейчас можно вывести информацию, как первый Meilenstein, про кол-во ребер, вершин, и макс/мин исходящих/входящих ребер.
Пока все с этой частью алгоритма.