IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Закавыристая процедура, работа с деревьями
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 37
Пол: Мужской

Репутация: -  0  +


Вот тут написал программу. Она создает деверо общего вида, добавляет к нему элементы, печатает его. Но вот главная процедура мне что-то не хочет даваться. Задача ее состоит в том, чтобы подсчитать число вершин дерева, степень которых совпадает со значением их элементов. Причем элементы типа Char. Я знаю есть такая функция ord, но как это вообще реализовать я не могу. Вот прога, помоги те если не трудно
Код
program lab22(input,output);
type tree = ^node;
   node      = record
           inf    : char;
           brat,son    : tree;
        end;    
var t            : tree;
   q,data,kuda,shto        : char;
   c,i            : integer;
b            : boolean;
procedure dop(var t : tree);
begin
   if t^.brat=nil then
   begin
      new(t^.brat);
      writeln('vvedi element');
      readln(t^.brat^.inf);
      t^.brat^.brat:=nil;
      t^.brat^.son:=nil;
   end
   else dop(t^.brat);
end;
procedure sozd(var t:tree;var data:char);
begin
   writeln('vvedite element');
   readln(data);
   new(t);
   t^.inf:=data;
   t^.brat:=nil;
   t^.son:=nil;
end;
procedure add(var t : tree; data:char);
begin
   if t^.inf<>kuda then
   begin
      if t^.son<>nil then add(t^.son,kuda);
      if t^.brat<>nil then add(t^.brat,kuda);
   end
   else
   begin
      if t^.son=nil then
      begin
     new(t^.son);
     write('vvedite element:');
     readln(t^.son^.inf);
     t^.son^.son:=nil;
     t^.son^.brat:=nil;
      end
      else dop(t^.son);
   end;
end;
procedure dobavlenie;
begin
   write('kuda postavit element?:');
   readln(kuda);
   add(t,kuda);
end;
procedure print(t:tree; var i:integer);
var j : integer;
begin
   write('':i,t^.inf);
   if t^.brat<>nil then
   begin
      print(t^.brat,i);
   end;
   if t^.son<>nil then
   begin
      writeln;
      print(t^.son,i);
   end;
   i:=i+1;
end;
begin
   while b<>true do
   begin
      writeln('      1 - Sozdanie');
      writeln('      2 - Dobavlenie elementa');
      writeln('      3 - Print');
      writeln('      4 - Udalenie');
      writeln('      5 - Exit');
      writeln('      6 - Active');
write('vvedite punkt menu:');
      readln(c);
      if c=1 then sozd(t,data);
      if c=2 then dobavlenie;
      if c=3 then print(t,i);
      writeln;
      writeln('hotite prodoljit?y/n');
      readln(q);
      if q='y' then b:=false;
      if q='n' then b:=true;
      if (q<>'y') and (q<>'n') then
      begin
     writeln('Tolko "n" ili "y"!');
     readln(q);
      end;
   end;
end.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Цитата
подсчитать число вершин дерева, степень которых совпадает со значением их элементов.
Если ты имеешь в виду УРОВЕНЬ расположения элемента в дереве, то:
Procedure CountLevel(Level: integer; Root: Tree; Var n: integer);
Begin
if Root <> Nil then begin
if Ord(Root^.inf) = Level then Inc(n);
CountLevel(Succ(Level), Root^.brat, n);
CountLevel(Succ(Level), Root^.son, n);
end;
End;
...
{ Вызов: }
n := 0;
CountLevel(0, t, n);
...


?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 37
Пол: Мужской

Репутация: -  0  +


Ну, насколько я знаю, степенью вершины называется число исходящих из нее ветвей. То есть если число ветвей 5 и ord возвращает 5, то такая вершина засчитывается
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Цитата
Определение 2. Степенью вершины дерева называется число дуг, исходящих из нее.
У тебя по определению в бинарном дереве не может быть степени, равной 5, т. к. число исходящих дуг ограничено двумя.
Следовательно:
...
if
Ord(Root^.inf) =
Byte(Root^.Brat <> nil) + Byte(Root^.Son <> nil) then Inc(n);
...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 37
Пол: Мужской

Репутация: -  0  +


Но у меня дерево не бинарное, а общего вида
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Это твое определение дерева?
type
tree = ^node;
node = record
inf : char;
brat, son: tree; // Это - общего вида?
end;
У тебя в приведенном фрагменте сколько может быть потомков МАКСИМУМ у вершины? Два, не так ли? Значит, бинарное дерево.

Дерево общего вида (с произвольным количеством потомков у каждой вершины) описывается по другому...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 37
Пол: Мужской

Репутация: -  0  +


То есть в записи node задавать больше вершин? Ну а если мне понадобится десять вершин или двадцать, как это тогда описать?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






Ясно. Я понял твою логику. У тебя Brat - это указатель НЕ на потомка, а на следующего потомка родителя, а вот Son - именно указатель на список потомков, так? Я просто всегда описываю поля так:
type
ptree = ^tree;

tree = record
inf: char;
next: ptree; // Соответствует твоему Brat
child: ptree; // Соответствует твоему Son
end;


Тогда нужная тебе процедура будет выглядеть приблизительно так:
procedure Count(root: ptree; var n: integer);
var
p: ptree;
X: integer;
begin
if root <> nil then begin
p := root^.child; // Будем работать с потомками данного узла

X := 0; // Посчитаем их число
while p <> nil do begin
inc(X); p := p^.next;
end;

// Если условие выполняется - увеличить n
if ord(root^.inf) = X then Inc(n);

p := root.next; // А теперь запустим рекурсию для всех "братьев" ...
while p <> nil do begin
Count(p, n); p := p^.next;
end;
p := root.child; // ... и для всех потомков ТЕКУЩЕГО узла ...
while p <> nil do begin
Count(p, n); p := p^.next;
end;

end;
end;

// Пример вызова:
var
root: ptree;
n: integer;
begin
root := nil;
// ...
// Заполнение дерева

Count(root, n);
end.
Я надеюсь, ничего не перепутал, ибо лениво заполнять список и проверять правильность работы процедуры...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 37
Пол: Мужской

Репутация: -  0  +


Странно, подогнал процедуру под свою прогу, но он мне ошибку выдает
Цитата
Stack overflow error


Код

program lab22(input,output);
type tree = ^node;
   node      = record
           inf    : char;
           brat,son    : tree;
        end;
procedure Count(t: tree; var n: integer);
var
  p: tree;
  X: integer;
begin
  if t <> nil then begin
    p := t^.son;
    X := 0;
    while p <> nil do begin
      inc(X); p := p^.brat;
    end;
    if ord(t^.inf) = X then Inc(n);
    p :=t;
    while p <> nil do begin
      Count(p, n); p := p^.brat;
    end;
    p := t^.son;
    while p <> nil do begin
      Count(p, n); p := p^.brat;
    end;
   end;
end;
\\ ну и вызов соответственно
begin
       Count(t, n);
       writeln('kol-vo takih vershin:',n);
       end;


Сообщение отредактировано: Clon -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






Внимательно:
Код
    p :=t.brat; { <--- Здесь !!! }
    while p <> nil do begin
      Count(p, n); p := p^.brat;
    end;
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 37
Пол: Мужской

Репутация: -  0  +


Все, огромное спасибо, заработало.
Кстати, а где можно посмотреть процеруду удаление элемента? Я глянул в FAQ, но там только для двоичных деревьев.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






Цитата(Clon @ 19.05.2006 19:03)
Кстати, а где можно посмотреть процеруду удаление элемента? Я глянул в FAQ, но там только для двоичных деревьев.

Вот процедура удаления дерева общего вида:
{ Описание типа Tree }
type
T = char;

tree = ^node;
node = record
inf: T;
brat, son: tree;
end;
...
{ Процедура добавления осталась твоя... }

{ Удаление: }
procedure destroy(t: tree);
var p, pt: tree;
begin
if t <> nil then begin
p := t;
while p <> nil do begin
destroy(p^.son); pt := p;
p := p^.brat;
dispose(pt);
end;
end;
end;

...
{ Проверяем работу: }

{ В самом начале программы делаем : }
WriteLn(MemAvail); { Количество свободной памяти, запомни его !!! }
...
write('vvedite punkt menu: '); readln©;
case c of
...
5: begin
b := true;
destroy(root^.son); dispose(root); { Удаляем все дерево и сам корень }
writeln(memavail); { А вот это число должно совпадать с первым выведенным }
end;
end;
...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 37
Пол: Мужской

Репутация: -  0  +


Ошибка. Указывает на

Код
dispose(pt);


и пишет
Цитата
Invalid pointer operation


Сообщение отредактировано: Clon -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Гость






Ну, не знаю. Я скопировал сюда из только что отработавшей программы... Никаких ошибок не показывает, все нормально работает... Хочешь - присоединю свой файл...

P.S. Проверяй... А мне надоело. Все время что-то у кого-то не работает, где-то сбоит... Теперь буду чисто теоретически отвечать, никакого кода больше не будет. nea.gif

Сообщение отредактировано: volvo -


Прикрепленные файлы
Прикрепленный файл  DEREVO.PAS ( 2.4 килобайт ) Кол-во скачиваний: 98
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 37
Пол: Мужской

Репутация: -  0  +


Ладно, все равно спасибо. Вот только процедура эта, она удаляет все дерево или только указанный элемент? просто у меня она удаляет все кроме первого элемента.

Сообщение отредактировано: Clon -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 18.12.2017 11:57
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"