Pascal

Активность

Pascal

19.01.2012 / 22:13	#134773 Скопировать ссылку Скопировать как BB-код Перейти к посту
XakepPRO Модератор форума Сейчас: Offline Регистрация: 20.06.2012	ptiCa, PascalABC.NET. Скачивай с инсталлятором .NET Framework 4.0, если последнего нет. Изменено Ксакеп* (18.11 / 07:09) (всего 1 раз)*

19.01.2012 / 22:14	#134775 Скопировать ссылку Скопировать как BB-код Перейти к посту
Pauk52 Пользователь Сейчас: Offline Имя: Володимир Откуда: Пески-радьковские Регистрация: 25.01.2011	abc

19.01.2012 / 22:23	#134782 Скопировать ссылку Скопировать как BB-код Перейти к посту
ptiCa Пользователь	Вот и мой вклад http://pas1.ru А какую ide для pascal посоветуете ?

19.01.2012 / 22:25	#134783 Скопировать ссылку Скопировать как BB-код Перейти к посту
Naik Пользователь Сейчас: Offline Имя: %name% Регистрация: 14.03.2010	PascalGUI - теперь можно программировать на Паскале и на Android. Использует компилятор freepascal и является полнофункциональным.

20.01.2012 / 13:53

XakepPRO

Модератор форума

Сейчас: Offline

Стеки

Стек (англ. stack — стопка) — структура данных с методом доступа к элементам LIFO (англ. Last In — First Out, «последним пришел — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно взять верхнюю.
Другими словами, стек - это упорядоченный набор элементов, в котором размещение новых элементов и удаление осуществляется только с одного конца.

Стек предназначен для хранения элементов, доступных естественным путем в вершине списка. Представим шампур, на который нанизаны нарезанные овощи, подготовленные для шашлыка. Пусть овощи расположены в следующем порядке: лук, грибочек, зеленый перец и лук. Перед приготовлением шашлыка гость сообщает, что он не ест грибов и их необходимо убрать. Эта просьба означает удалить лук, удалить грибочек и затем вновь нанизать лук. Если гость не любит зеленый перец или лук, это доставит повару больше проблем.

Рисунок 1

В структуре стека важнейшее место занимают операции, добавляющие и удаляющие элементы. Операция Push добавляет в вершину стек, а операция Pop извлекает элемент с вершины стека.

Рисунок 2
_______

Таким выглядит стек, состоящий из трех элементов:
Рисунок 3

Элемент стека описывается следующим образом:

type
  PNode=^TNode;
  TNode=record
    Data: integer;
    Next: PNode;
  end;

Т.е, каждый элемент стека содержит необходимые для хранения данные (Data) и ссылку на следующий элемент (Next). Связь таких элементов и есть стек.

Выкладываю самописную библиотеку для работы со стеками: скачать.
Основное её применение - решение задач, не прибегая к примитивам.

Открыть спойлер

[копировать] [скачать]
///Модуль для работы со стеками, только самое основное для решения задач
///Version: 0.1   Author: Xakep
 
unit Stack;
 
type
  ///Тип данных в узле
  TType = integer;
  /// Тип указателя на узел списка
  PNode = ^TNode;
  /// Тип узла списка
  TNode = record
    Data: TType;
    Next: PNode;
  end;    
 
//----------------------------------------------
////  Создание, удаление стека и его элементов
//----------------------------------------------
 
///Создание нового узла в списке
///P - Вершина, Data - значение
procedure AddNode(var P: PNode; Data: TType);
var
  P1: PNode;
begin
  New(P1);
  P1^.Data := Data; 
  P1^.Next := P;
  P := P1;
end;
 
///Удаление последнего узла в списке
procedure DelNode(var P: PNode);
var
  P1: PNode;
begin
  P1 := P; P := P^.Next;
  Dispose(P1);
end;
///Процедура удаления элемента по указателю
///P - вершина, tmp - указатель
procedure DelNode(var P: PNode; tmp: PNode);
var
  tmpi: PNode;
begin
  //Если стек пуст или указатель никуда не указывает, то выходим
  if (P = nil) or (tmp = nil) then exit;
 
  //Если tmp - указатель на вершину стека
  if tmp = P then 
  begin
    P := tmp^.Next; 
    Dispose(tmp);
  end
  else
  begin
    tmpi := P;
 
    //Доходим до элемента стоящего "перед" тем, который нам следует удалить
    while (tmpi^.Next <> nil) do
      if tmpi^.Next = tmp then
      begin
        //Указатель элемента переносим на следующий элемент за удаляемым
        tmpi^.Next := tmp^.Next;
        Dispose(tmp);
      end
      else tmpi := tmpi^.Next;    
  end;
end;
///Процедура удаления элемента по значению
///P - вершина, Data - значение
procedure DelNode(var P: PNode; Data: TType);
var
  tmp, tmpi: PNode;
begin
  //Если стек пуст, то выводим сообщение и выходим
  if P = nil then exit;
  tmp := P;
 
  //Просматриваем вершину
  if P^.Data = Data then 
  begin
    P := P^.Next;
    Dispose(tmp);
    exit;
  end;
 
  while tmp^.Next <> nil do
    if tmp^.Next^.Data = Data then 
    begin
      tmpi := tmp^.Next;
      tmp^.Next := tmp^.Next^.Next;
      Dispose(tmpi);
      break;
    end
    else tmp := tmp^.Next;
end;
///Удаление элемента по порядковому номеру
///P - вершина стека, Pos - номер позиции (вершина имеет номер 1)
procedure DelNodePos(var P: PNode; Pos: integer);
var
  i: integer;
  tmp, tmpi: PNode;
begin
  if (Pos <= 0) or (P = nil) then  exit;
  tmp := P;
 
  if Pos = 1 then begin P := P^.Next; Dispose(tmp); exit; end;
 
  i := 1;
  while (tmp^.Next <> nil) do
  begin
    Inc(i);
 
    if i = Pos then
    begin
      tmpi := tmp^.Next;
      tmp^.Next := tmpi^.Next;
      Dispose(tmpi); exit;
    end;
 
    tmp := tmp^.next;
  end;
end;
 
///Процедура полного удаления стека из памяти
procedure Free(var P: PNode);
var
  P1: PNode;
begin
  while P <> nil do
  begin
    P1 := P;
    P := P^.Next;
    Dispose(P1);
  end;
end;
 
//-----------------------------------------------
////  Сортировка, анализ стека и его элементов
//-----------------------------------------------
 
///Процедура инвертирования стека
procedure Invert(var P: PNode);
var
  Pl, Pr: PNode;
begin
  Pl := nil;
  while P <> nil do
  begin
    Pr := P^.Next;
    P^.Next := Pl;
    Pl := P; P := Pr;
  end;
  P := Pl;
end;
 
///Процедура сортировки "пузырьком" с изменением только данных
procedure SortBubl(P: PNode);
var
  tmp, rab: PNode;
  tmps: TType;
begin  
  rab := P;
  while rab <> nil do
  begin
    tmp := rab^.next;
    while tmp <> nil do
    begin
      if tmp^.data < rab^.data then
      begin
        //стандартная замена в 3 операции
        tmps := tmp^.data;
        tmp^.data := rab^.data;
        rab^.data := tmps;
      end;
      tmp := tmp^.next;
    end;
    rab := rab^.next;
  end
end;
///Процедура сортировки "пузырьком" с изменением только адресов
procedure SortBublLink(P: PNode);
//TODO Аццкий быдлокод. Ни в коем случае не использовать
{
var
  tmp,pered,pered1,pocle,rab: PNode; //все рабочие ссылки}
begin{
  rab:=P; //становимся на вершину стека
  while rab<>nil do//пока не конец стека делать
  begin
    tmp:=rab^.next; //переходим к следующему за сортируемым элементу
    while tmp<>nil do //пока не конец стека делать
    begin
      if tmp^.data<rab^.data then //если следует произвести замену, то
      begin
        pered:=P; //становимся в вершину стека
        pered1:=P; //становимся в вершину стека
        if rab<>P then //если мы не стоим на изменяемом элементе, то
          while pered^.next<>rab do pered:=pered^.next; //станем на элементе перед изменяемым
        while pered1^.next<>tmp do pered1:=pered1^.next; //станем на элементе перед изменяемым, который находится за
        //первым изменяемым
        pocle:=tmp^.next; //запоминаем адрес элемента после второго изменяемого
        if rab^.next=tmp then //если элементы "соседи", то
        begin
          tmp^.next:=rab; //меняем ссылки, тут если не понятно рисуйте на листочке
          rab^.next:=pocle
        end
        else //в случае если элементы не соседи, то
        begin
          tmp^.next:=rab^.next;//меняем ссылки, тут если не понятно рисуйте на листочке
          rab^.next:=pocle;
        end;
        if pered1<>rab then//советую просмотреть на листочке
          pered1^.next:=rab;
        if rab<>P then//советую просмотреть на листочке
          pered^.next:=tmp
        else//всё советую просмотреть на листочке
          P:=tmp;
        pered1:=tmp;//советую просмотреть на листочке
        tmp:=rab;//советую просмотреть на листочке
        rab:=pered1;//советую просмотреть на листочке
      end;
      tmp:=tmp^.next; //переходим на следующий элемент
    end;
    rab:=rab^.next;//переходим на следующий элемент
  end;
}
end;
 
///Вывод значений списка на экран
procedure ListOut(P: PNode);
begin
  while P <> nil do
  begin
    Write(P^.Data, ' > ');
    P := P^.Next;
  end;
  Writeln('nil');
end;
///Вывод адресов списка на экран
procedure ListAdOut(P: PNode);
begin
  while P <> nil do
  begin
    Write(P, ' > ');
    P := P^.Next;
  end;
  Writeln('nil');
end;
 
///Поиск первого встретившегося узла со значением Data
///Возращает узел, если элемент найден, иначе - nil
function Search(P: PNode; Data: TType): PNode;
begin
  //TODO Рекурсивная функция!
  Result := P;
 
  if P = nil then exit;
  if P^.Data = Data then exit;
 
  Result := Search(P^.Next, Data);
end;
///Поиск узла с адресом Ad
///Возращает узел, если элемент найден, иначе - nil
function Search(P, Ad: PNode): PNode;
begin
  //TODO Рекурсивная функция!
  Result := P;
 
  if P = nil then exit;
  if P = Ad then exit;
 
  Result := Search(P^.Next, Ad);
end;
///Возращает узел с порялковым номером Pos
///P - вершина стека, Pos - номер позиции (1 - вершина)
function GetElem(P: PNode; Pos: integer): PNode;
var
  i: integer;
begin
  if (Pos <= 0) or (P = nil) then  exit;
 
  i := 1;
  while (P^.Next <> nil) do
  begin
    if i = Pos then
    begin
      Result := P;
      exit;
    end;
    Inc(i);
    P := P^.Next;
  end;
end;
 
///Возращает глубину списка (nil не учитывается)
function GetDepth(P: PNode): integer;
begin
  Result := 0;
 
  while P <> nil do
  begin
    Result += 1;
    P := P^.Next;
  end;
end;
 
end.

Показательный пример:

Открыть спойлер

Результат:

Открыть спойлер

Изменено XakepPRO (20.01 / 13:55) (всего 1 раз)

Прикрепленные файлы:

stek3.png (4.59 кб.) Скачано 323 раза

stek2.gif (0.86 кб.) Скачано 322 раза

stek1.gif (1.67 кб.) Скачано 311 раз

StackLib.zip (2.75 кб.) Скачано 137 раз

20.01.2012 / 18:43	#134987 Скопировать ссылку Скопировать как BB-код Перейти к посту
TAPAHbl4 Пользователь Сейчас: Offline Имя: TAPAHbl4 Регистрация: 15.01.2012	XakepPRO, ты думаешь оно кому-то здесь надо? А вообще у меня есть книга "Методы алгоритмизации". Там на паскале и стеки, и кучи, и списки, и графы - всё есть

20.01.2012 / 18:51	#135002 Скопировать ссылку Скопировать как BB-код Перейти к посту
XakepPRO Модератор форума Сейчас: Offline Регистрация: 20.06.2012	TAPAHbl4, давай её сюда Ты знаешь, какова была мотивация aNNiMON'a создать этот и предыдущие сайты?

23.01.2012 / 05:18	#136342 Скопировать ссылку Скопировать как BB-код Перейти к посту
ptiCa Пользователь	Можно пример где стек необходим? Просто я думаю он не очень удобен.

23.01.2012 / 09:09	#136368 Скопировать ссылку Скопировать как BB-код Перейти к посту
Maxxxl123 Пользователь Сейчас: Offline Имя: Макс Откуда: Чернигов Регистрация: 13.10.2011	Народ, а чеза паскаль абц? Не слышал раньше... ЗЫ щя турбо учю

23.01.2012 / 09:20	#136374 Скопировать ссылку Скопировать как BB-код Перейти к посту
ptiCa Пользователь	Maxxxl123, wiki offsite

<< 1 2 3 4 ... 54 >>

Всего сообщений: 540

Фильтровать сообщения

Поиск по теме

Файлы топика (22)