VPF::Стек - Форум программистов

BaguK

Дата 3.11.2006, 17:58 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 3.11.2006

Репутация: нет
Всего: нет

Привет всем smile

! На лабораторной работе по САОДу дали лабу. В задании требуется отсортировать структуру чилел на четные и нечетные при помощи двух стеков. Организовать структуру с использованием динамической памяти. Используемая структура массив

Так вот мой вопрос? В книжке прочитал что стек можно представить в виде: списка и массива.
По условию задачи требуется организовать стек при помощи массива. Я спросил у преподавателя какой мне массив использовать статический или динамический. Он ответил что динамический!
Может мне кто-нибудь подсказать как организовать стек при помощи динамического сассива? smile

Nicholas_S

Дата 3.11.2006, 19:48 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 486
Регистрация: 12.10.2006
Где: Санкт-Петербург

Репутация: нет
Всего: 19

BaguK, "Организовать структуру с использованием динамической памяти", здесь как раз имеются ввиду списки с динамическим выделением памяти, с использованием указателей. Массив предполагает статический размер стека, ограниченный длинной массива. Возможно, преподаватель имел ввиду все-таки списки.
Если все таки он имел ввиду именно _динамический массив_, стандартная реализация которых не имеется в Паскале (если ничего не путаю, поддержка начинается только с версии Delphi 4), то это можно реализовать с использованием тех же самых указателей, например:

Код


{$R-}

{Создаем основные типы для реализации динамического массива}
type
    TArrayItem = Integer;
    TDynArray  = Array[1..1] of TArrayItem;  
    PDynArray  = ^TDynArray;

var
  DynArray: PDynArray; 
  len: Word;
  i, size: Word;

begin
  write('Число элементов массива: ');
  ReadLn(len);

  { Теперь нужно выделить память для массива }  
  size := len*SizeOf(TDynArray);
  GetMem(DynArray, size);

  {здесь пойдет обращение к массиву след. образом: DynArray^[index], где индекс - номер элемента массива }  

  {освобоить в конце работы программы память, выделенную под массив}

  FreeMem(DynArray, size);

end.

Это что касательно только динамических массивов.
Решение задачи оставляю другим. smile

Добавлено @ 19:49
Да, чуть не забыл. Параметр для компилятора в начале листинга программы {$R-} обязателен. Служит он для того, чтобы компилятор не ругался на уход за границы массива.

--------------------

...все в мире относительно

BaguK

Дата 3.11.2006, 20:20 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 3.11.2006

Репутация: нет
Всего: нет

Nicholas_S, спасибо!!!
Во всех книгах которые смотрел, реализация стека делается с помощью динамического списка и статического массива. Похоже препод специально сказал, что бы труднее было. Но может кто-нибудь покажит пример организации стека при помощи динамического массива. И может кто-нибудь знает ссылки на учебники по САОДу! Зарание спасибо smile

anwe

Дата 3.11.2006, 22:19 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 748
Регистрация: 2.9.2006

Репутация: нет
Всего: 23

Код


var
massiv:array[1..10]of Integer     //исходный массив (размер взял произвольно);
array_chet,array_nechet:array of Integer;       //динамические массивы
i,j,k:Word;
begin
j:=0;
k:=0;
for i:=1 to 10 do
    if massiv[i] mod 2=0 then
        begin
        inc(j);
        SetLength(array_chet,j);        //увеличение размера массива на 1
        array_chet[j-1]:=massiv[i];    //так как нумерация в динамик-массивах начинается с нуля
        end
    else
        begin
        inc(k);
        SetLength(array_nechet,k);
        array_chet[k-1]:=massiv[i];
        end;

Nicholas_S

Дата 3.11.2006, 22:29 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 486
Регистрация: 12.10.2006
Где: Санкт-Петербург

Репутация: нет
Всего: 19

anwe, не уверен, что код будет работать на Паскале smile

--------------------

...все в мире относительно

volvo877

Дата 4.11.2006, 03:01 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116

Цитата(Nicholas_S @ 3.11.2006, 21:29

)

не уверен, что код будет работать на Паскале

В том виде, в котором он приведен - не будет (Турбо Паскаль не работает с динамическими массивами), но это отнюдь не является непреодолимой преградой... Я о том, что написать свою функцию SetLength для массива, хранящего элементы определенного типа данных - не такая уж и большая проблема, достаточно описать тип массива как

Код

Type
  T = Integer; { <--- Это - наш тип данных }
  TArr = array[1 .. maxint div sizeof(T)] Of T;

, описать переменную

Код

Const
  arrSize: integer = 0;

и выделять в своей функции SetLength память для нового массива через GetMem, перемещая старый массив в новый функцией Move, и удаляя старый (немного неэффективно, конечно, но вполне даже работает)...

BaguK

Дата 4.11.2006, 11:53 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 3.11.2006

Репутация: нет
Всего: нет

Вообщем я тут нашел. Препод ошибылся все таки эту структуру надо организовывать при помощи статического массива smile

Цитата

Стек можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру – в виде линейного списка.
При реализации стека в виде статического массива необходимо резервировать массив, длина которого равна максимально возможной глубине стека, что приводит к неэффективному использованию памяти. Одновременно, работать с такой реализацией проще и быстрее.
При такой реализации дно стека будет располагаться в первом элементе массива, а рост стека будет осуществляться в сторону увеличения индексов. Одновременно, необходимо отдельно хранить значение индекса элемента массива, являющегося вершиной стека.
Можно обойтись без отдельного хранения индекса, если в качестве вершины стека всегда использовать первый элемент массива, но в этом случае, при записи или чтении из стека, необходимо будет осуществлять сдвиг всех остальных элементов, что приводит к дополнительным затратам вычислительных ресурсов.
Основные операции, производимые со стеком:
-   записать (положить в стек);
-   прочитать (снять со стека);
-   очистить стек;
-   проверка пустоты стека.

Кто может привести примеры smile

этих 4 операций для стека организованного ч/з статический массив

Nicholas_S

Дата 5.11.2006, 17:31 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 486
Регистрация: 12.10.2006
Где: Санкт-Петербург

Репутация: нет
Всего: 19

volvo877, оргинизацию именно _динамического_ массива на паскале в привел в самом начале топика.

--------------------

...все в мире относительно

BaguK

Дата 5.11.2006, 21:35 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 3.11.2006

Репутация: нет
Всего: нет

Цитата(anwe)

SetLength(array_chet,j)

На Паскале нет такой процедуры smile

Это сообщение отредактировал(а) BaguK - 5.11.2006, 21:35

Zero

Дата 5.11.2006, 22:36 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24

BaguK, прочитай ещё раз этот пост:
http://forum.vingrad.ru/index.php?showtopi...st&p=911351

volvo877

Дата 5.11.2006, 22:51 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116

Nicholas_S, то, что ты привел - это реализация массива, хранимого в "куче". Но размеры его ты не поменяешь... А я предложил именно динамический массив, с возможностью изменения его размеров. Поскольку изначально автор хотел реализовать стек, то твоя реализация так же не помогла бы ему, как и простой статический массив, ибо у нее жестко задан размер...

Читай внимательно...

Nicholas_S

Дата 6.11.2006, 13:42 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 486
Регистрация: 12.10.2006
Где: Санкт-Петербург

Репутация: нет
Всего: 19

volvo877, никто не мешает тебе добавить то же самое копирование памяти, которое ты предложил, написав свою SetLength().
Реализацию самой задачи я предоставил другим.

--------------------

...все в мире относительно

BaguK

Дата 7.11.2006, 20:58 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 3.11.2006

Репутация: нет
Всего: нет

Сделал лабу.

Код


program laboratornaya_rabota_2;
uses
 crt;
const
 max=100;
 ok=' Нажмите любую клавишу';
type
 t_array=array[1..max]of integer;

procedure add_random(var st:t_array; var n:integer);
var
 i:integer;
Begin
 clrscr;
 write('Введите количество чисел вашей структуры: ');
 readln(n);
 for i:=1 to n do
  st[i]:=random(99)+1;
End;

procedure add_hand(var st:t_array; var n:integer);
var
 i,v:integer;
Begin
 clrscr;
 write('Введите количество чисел вашей структуры: ');
 readln(n);
 for i:=1 to n do
  begin
   clrscr;
   write('Введите ',i,' число ');
   read(v);
   st[i]:=v;
  end;
End;

procedure add_fail(var st:t_array; var n:integer);
var
 i:integer;
 a:file of integer;
Begin
 {$i-}
 assign(a,'st-ra.baz');
 reset(a);
 {$i+}
 if IOresult = 0 then
  begin
   n:=filesize(a);
   for i := 1 to n do
    read(a,st[i]);
  end;
 close(a);
End;

procedure print_array(st:t_array;n:integer);
var
 i:integer;
Begin
 clrscr;
 for i:=1 to n do
  if st[i] mod 2 =0 then
   begin
    textcolor(green);
    write(st[i],' ');
    normvideo;
   end
  else
   begin
    textcolor(red);
    write(st[i],' ');
    normvideo;
   end;
 writeln;
 writeln('Вывод структуры закончен.',ok);
 readkey;
End;

procedure push(var stack:t_array; var k:integer; var tos:integer);
Begin
 stack[tos]:=k;
 tos:=tos+1;
End;

function pop(stack:t_array; var tos:integer):integer;
Begin
 tos := tos-1;
 if tos < 1 then
  begin
   Writeln('Stack underflow');
   tos:= tos+1;
   Pop:= 0;
  end
 else Pop := stack[tos];
End;

procedure sort_two_stack(var st:t_array; n:integer);
var
 tos1,tos2,b,j,l,i,k:integer;
 st2,st3,stack1,stack2:t_array;
Begin
 k:=0;
 tos1:=1;
 tos2:=1;
 l:=0;
 j:=0;
 b:=0;
 for i:=1 to n do
  if st[i] mod 2=0 then
   begin
    k:=st[i];
    j:=j+1;
    push(stack1,k,tos1);
   end
   else
    begin
     l:=l+1;
     st2[l]:=st[i];
    end;
 writeln;
 for i:=1 to j do
  begin
   b:=pop(stack1,tos1);
   st3[i]:=b;
  end;
 for i:=1 to j do
  begin
   b:=st3[i];
   push(stack2,b,tos2);
  end;
 for i:=l+1 to j+l do
  begin
   b:=pop(stack2,tos2);
   st2[i]:=b;
  end;
 for i:=1 to j+l do
  begin
   write(st2[i],' ');
   st[i]:=st2[i];
  end;
 readln;

End;

var
 endmenu:boolean;
 kol:integer;
 v:0..5;
 st_array:t_array;

BEGIN
 randomize;
 endmenu:=false;
 kol:=0;
 repeat
  clrscr;
  writeln('1. Заполнить структуру чисел случайным образом');
  writeln('2. Заполнить структуру чисел вручную');
  writeln('3. Заполнить структуру чисел из файла');
  writeln('4. Вывод структуры чисел');
  writeln('5. Рассортировать структуру чисел на четные и нечетные с помощью двух стеков');
  writeln('0. Окончание работы');
  readln(v);
  case v of
   1:begin
      add_random(st_array,kol);
      writeln('Структура заполнена.',ok);
      readkey;
     end;
   2:begin
      add_hand(st_array,kol);
      writeln('Структура заполнена.',ok);
      readkey;
     end;
   3:add_fail(st_array,kol);
   4:print_array(st_array,kol);
   5:sort_two_stack(st_array,kol);
   else
    EndMenu:=true;
   end;
   until EndMenu;
END.

Если есть какие-нибудь предложения по этой работе, то делитесь пожалуйста smile

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Object Pascal: кроссплатформенные технологии \| Следующая тема »