Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Pascal]Динамическая_структура

Автор: camakob 1.4.2009, 06:30

Здравствуйте !
Дано задание:Используя очередь, решить следующую задачу. Содержимое текстового файла , разделенное на строки, переписать в текстовый файл g, перенося при этом в конец каждой строки все входящие в нее цифры (с сохранением исходного порядка как среди цифр, так и среди остальных литер строки).
Я сделал, но преподаватель требует, чтобы
"Очередь необходимо реализовать как динамическую структуру данных. Каждую операцию работы с очередью необходимо оформить отдельной процедурой или функцией".
Но в динамических структурах я полный ноль. Подскажите как выйти из положения.

Автор: volvo877 1.4.2009, 09:28

Вот тебе пример организации очереди как ДСД:

Код

type
  T = char;
  link = ^item;
  item = record
    data: T;
    next: link;
  end;

  queue = record
    head, tail: link
  end;

procedure initQueue(var q: queue);
begin
  q.head := nil; q.tail := nil;
end;

procedure putQueue(var q: queue; value: T);
var p: link;
begin
  new(p);
  p^.next := nil;
  p^.data := value;

  if q.head = nil then q.head := p
  else q.tail^.next := p;

  q.tail := p;
end;

function getQueue(var q: queue; var value: T): boolean;
var p: link;
begin
  if q.head = nil then getQueue := false
  else begin
    getQueue := true;
    value := q.head^.data;
    p := q.head;
    q.head := q.head^.next;
    dispose(p);
  end;
end;

var
  ch: char;
  q: queue;

begin
  initQueue(q);
  for ch := 'a' to 'k' do putQueue(q, ch);

  while getQueue(q, ch) do begin
    write(ch:3);
  end;
end.

Автор: camakob 1.4.2009, 11:02

Спасибо, будем разбираться.

Автор: camakob 1.4.2009, 12:12

Извините за назойливость, но как эти процедуры связать например с переменной типа string, т. е . как с их помощью из 'ab123987cd' получить 'abcd123987' ?

Автор: volvo877 1.4.2009, 12:39

Вот так, наверное:

Код

var
  i: integer;
  q_lett, q_dig: queue;
  s: string;
  ch: char;

begin
  initQueue(q_lett); initQueue(q_dig);

  s := 'ab123987cd';
  for i := 1 to length(s) do
    if s[i] in ['0' .. '9'] then putQueue(q_dig, s[i])
    else putQueue(q_lett, s[i]);

  s := '';
  while getQueue(q_lett, ch) do s := s + ch; { сначала берем все буквы }
  while getQueue(q_dig, ch) do s := s + ch; { а потом - цифры }

  writeln(s);
end.

Автор: camakob 1.4.2009, 13:33

Спасибо большое, сейчас думаю разберусь.

Автор: camakob 1.4.2009, 14:30

Все, программа работает. Для полного счастья объясните пожалуйста, что делают процедуры initQueue, putQueue, getQueue. И самый последний вопрос: порекомендуйте самую лучшую книгу по динамическим структурам данных.

Автор: volvo877 1.4.2009, 15:19

Цитата(camakob @ 1.4.2009, 13:30

)

что делают процедуры initQueue, putQueue, getQueue

initQueue инициализирует очередь (т.е., присваивает нулевые значения указателям на ее начало /head/ и конец /tail/). Если этого не сделать, то при работе с очередью возможны глюки.

А остальные... Ну, значит, так. Для очереди вообще-то определены только 2 операции: Put (добавить элемент в конец очереди) и Get (взять элемент из начала очереди). Вот это и делают putQueue и getQueue...

Цитата(camakob @ 1.4.2009, 13:30

)

порекомендуйте самую лучшую книгу по динамическим структурам данных

А зачем тебе книга? Что ты хочешь, чтоб там было написано? Назначение структур? Их реализации на каких-то языках? Преимущества/недостатки? Что именно ты ждешь от книги?

Автор: camakob 1.4.2009, 15:58

Спасибо за объяснения. Я жду от этой книги, чтобы там были примеры программ с объяснениями, именно на Паскале.