| ← Июль 2011 → | ||||||
|
1
|
2
|
|||||
|---|---|---|---|---|---|---|
|
5
|
7
|
8
|
9
|
10
|
||
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
|
18
|
19
|
20
|
21
|
22
|
23
|
24
|
|
25
|
26
|
27
|
28
|
29
|
30
|
31
|
За последние 60 дней ни разу не выходила
Сайт рассылки:
http://prog.rusfaq.ru/pascal
Открыта:
14-03-2002
Статистика
0 за неделю
RFpro.ru: Программирование на языке Pascal
Хостинг портала RFpro.ru: РАССЫЛКИ ПОРТАЛА RFPRO.RU
Лучшие эксперты данной рассылки
/ КОМПЬЮТЕРЫ И СОФТ / Программирование / Pascal (Паскаль)
Вопрос № 183675: Здравствуйте! Прошу помощи в следующем вопросе:По таблице ребер построить списки инцидентности неориентированного графа, удалить все рёбра, обе инцидентных вершин которого кратны 3!!! Среда Turbo Pascal!!! Пожалуйста, сделайте комментарий каждой с... Вопрос № 183675:
Здравствуйте! Прошу помощи в следующем вопросе:По таблице ребер построить списки инцидентности неориентированного графа, удалить все рёбра, обе инцидентных вершин которого кратны 3!!!
Отправлен: 20.06.2011, 19:00 Отвечает Сергей Бендер (Бакалавр) : Здравствуйте, Артем Воробьев! Комментарии в программе -- вроде всё ясно. Код :
{Максимальное количество вершин графа}
const nmax=30;
{По вашему тексту}
type ref = ^ Elem;
Elem = record
num: integer;
{ves: array [1 .. kv] of real;
Я категорически не понял, зачем тут понадобился массив.
Вроде бы одно ребро -- один вес}
ves:real;
pred, sled, ref_vi: ref;
end;
var mas_ref: array [1 .. nmax] of ref;
{Колчество зааднных вершин}
n:integer;
{Доюавление ребра}
procedure add(vi,vj:integer;v:real);
var i,j:integer;
pi,pj:ref;
begin
{Если vi или vj ещё не были добавлены -- увеличиваем n}
if vi>n
then n:=vi;
if vj>n
then n:=vj;
{Начинаем пробег по списку рёбер вершины vi}
pi:=mas_ref[vi];
{Если его ещё нет}
if pi=nil
then begin
{Создаём }
new(pi);
pi^.sled:=nil;
pi^.pred:=nil;
{и заносим в основной массив}
mas_ref[vi]:=pi;
end
else begin
{Иначе сдвигаемся до конца списка}
while pi^.sled<>nil do pi:=pi^.sled;
{создаём новый элемент в ссылке sled}
new(pi^.sled);
pi^.sled^.sled:=nil;
{привязываем его к текущему}
pi^.sled^.pred:=pi;
{и сдвигаемся на него}
pi:=pi^.sled;
end;
{Всё то же самое для vj}
pj:=mas_ref[vj];
if pj=nil
then begin
new(pj);
pj^.sled:=nil;
pj^.pred:=nil;
mas_ref[vj]:=pj;
end
else begin
while pj^.sled<>nil do pj:=pj^.sled;
new(pj^.sled);
pj^.sled^.sled:=nil;
pj^.sled^.pred:=pj;
pj:=pj^.sled;
end;
{Заполняем информационные поля (номер, вес) и ссылку на смежную вершину}
pi^.num:=vi;
pi^.ves:=v;
pi^.ref_vi:=pj;
{Всё то же самое для pj}
pj^.num:=vj;
pj^.ves:=v;
pj^.ref_vi:=pi;
end;
{Вычисление кратности вершины}
function kratnost(vi:integer):integer;
var k:integer;
pi:ref;
begin
{Начальное значение}
k:=0;
{Берем начало списка}
pi:=mas_ref[vi];
{Пока не достигли конца}
while pi<>nil do
begin
{Сдвигаемся на следующий и загибаем палец}
pi:=pi^.sled;
inc(k);
end;
kratnost:=k;
end;
{Поиск ребра, вершинами которого имеют кратность 3}
function findrebro:ref;
var vi,vj:integer;
pi,p:ref;
begin
vi:=1;
{Начальное значение: ребро не найдено}
p:=nil;
{Если не дошли до конца массива и у текущей вершины есть ребра и
нужное ребро не найдено}
while (vi<=n) and (mas_ref[vi]<>nil) and (p=nil) do
begin
{Если кратность первой вершины = 3}
if kratnost(vi)=3
then begin
{Сдвигаемся по списку ребер пока не дойдём до конца
или до смежной вершины с кратностью 3}
pi:=mas_ref[vi];
while (pi<>nil) and (kratnost(pi^.ref_vi^.num)<>3) do
pi:=pi^.sled;
{Результат поиска}
p:=pi;
end;
{Следующая вершина в массиве}
inc(vi);
end;
findrebro:=p;
end;
{Вывод на экран списка инцидентности}
procedure print;
var i:integer;
p:ref;
begin
{Всё понятно, наверно?}
for i:=1 to n do
if mas_ref[i]=nil
then writeln(i:2,': izolirovanny')
else begin
write(i:2,': ');
p:=mas_ref[i];
while p<>nil do
begin
write('(',i,',',p^.ref_vi^.num,';v=',p^.ves:0:2,') ');
p:=p^.sled;
end;
writeln;
end
end;
var i:integer;
p:ref;
begin
{Начальное значение массива}
for i:=1 to n do mas_ref[i]:=nil;
{Формируем граф}
add(1,2,3.4);
add(1,3,5.6);
add(1,4,6.7);
add(2,3,8.9);
add(2,4,9.1);
add(3,4,10.11);
add(3,5,11.12);
writeln('Ishodny graf');
print;
{Находим ребро с вершинами с кратностью 3 и начинаем цикл
пока ещё в графе находятся такие ребра}
p:=findrebro;
while p<>nil do
begin
{Если это не последний элемент списка}
if p^.sled<>nil
{следующий привязываем к предыдущему}
then p^.sled^.pred:=p^.pred;
{Если это не первый элемент списка}
if p^.pred<>nil
{предыдущий привязываем к следующему
(список двунаправленный)}
then p^.pred^.sled:=p^.sled
{иначе делаем следующий элемент первым в списке,
т.е. заносим в основной массив}
else mas_ref[p^.num]:=p^.sled;
{Всё то же самое для смежной вершины}
if p^.ref_vi^.sled<>nil
then p^.ref_vi^.sled^.pred:=p^.ref_vi^.pred;
if p^.ref_vi^.pred<>nil
then p^.ref_vi^.pred^.sled:=p^.ref_vi^.sled
else mas_ref[p^.ref_vi^.num]:=p^.ref_vi^.sled;
{Оба элемента корректно выведены из своих списков
можно удалять}
dispose(p^.ref_vi);
dispose(p);
{Ищем следующее ребро для удаления}
p:=findrebro;
end;
writeln('Udalenie reber s kratnotiyu vershin 3');
print;
readln;
end.
Ответ отправил: Сергей Бендер (Бакалавр)
Оценить выпуск »
Задать вопрос экспертам этой рассылки »Скажите "спасибо" эксперту, который помог Вам!Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТАна короткий номер 1151 (Россия) Номер ответа и конкретный текст СМС указан внизу каждого ответа.
* Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи.
(полный список тарифов) © 2001-2011, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про" Калашников О.А. | Гладенюк А.Г. Хостинг: Компания "Московский хостер" Версия системы: 2011.6.31 от 07.05.2011 |
| В избранное | ||
