Лабораторная работа №10.
Тема: Разработка и отладка алгоритма с использованием динамических структур данных

Вы не можете скачивать файлы с нашего сервера

Цель: Приобрести навыки программирования динамических структур данных.
Оснащение: IBM PC, Borland C++ 5.02

Методические указания:

Стек - это линейный список, где элементы могут добавляться или удаляться только в конце списка (как стопка тарелок на столе). Для стека определены операции «Положить элемент», «Взять элемент»

Очередь - это линейный список, где элементы удаляются из начала списка, а добавляются в конце списка (как обыкновенная очередь в магазине). Операции аналогичны стеку.

Двусторонняя очередь это линейный список, где элементы добавляются и удаляются как в начало, так и в конец списка (как располагаются книги в книжном шкафу). Для двухсторонней очереди определены 4 операции: «добавить элемент в конец», «добавить элемент в начало», «взять из начала», «взять из конца».

Динамические структуры данных логично описывать в виде структур. Например, для очереди необходимо иметь указатель на очередь для того, чтобы взять элемент, указатель на конец памяти очереди, чтобы не выйти за пределы и указатель на текущий элемент, который находится в конце очереди, чтобы положить элемент.

Пример объявления структуры-очереди

struct turn // объявляем тип данных «очередь» в виде структуры
{
  int *element; // указатель на текущий элемент
  int *begin; // указатель на начало
  int *end; // указатель на конец
} t1; // здесь объявляем переменную-очередь 

Прототипы функций, для работы очереди

void push(int x); // взять элемент
int pop(void); // положить элемент

Размер очереди вводится с клавиатуры и память выделяется под массив «element» динамически. Команда 
s1.element=(int *) malloc(size*sizeof(int));
выделит size байтов на массив element структуры t1
затем необходимо задать указатели на начало массива element и на конец массива (указатели *t1.begin и *t1.end). Конец это начало, сдвинутое на размер массива (size). Указатель *t1.element сначала указывает на начало массива.

Организуйте цикл ввода элементов до тех пор, пока мы не введём -1. При вводе какого-либо числа заносим его в очередь ( push(); ), при вводе 0 вытаскиваем элемент из очереди (pop() ).

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

Опишем процедуру взятия элемента из очереди. Элемент берётся с начала очереди, затем вся очередь сдвигается влево в памяти  

3 4 5 3 1
Вытаскиваем первый элемент и сдвигаем всю очередь, в конец заносим 0

4 5 3 1 0
Вытаскиваем первый элемент и сдвигаем всю очередь, в конец заносим 0
Необходимо также поставить проверку на пустоту, чтобы мы не смогли вытащить элемент из пустой очереди. Если указатель на начало совпадает с указателем на текущий элемент, значит выдаём сообщение о том, что очередь пуста и выходим из программы, иначе мы меняем местами все элементы сначала, на на место последнего элемента заносим 0.

Для того, чтобы сдвинуть всю очередь влево, необходимо в цикле менять местами элементы (разумно будет реализовать на примере функции swap). Цикл будет от начала массива до количества текущих элементов, которое будет t1.element-t1.begin, то есть количество элементов между текущим и начальными элементами. Для того, чтобы прогонять по всем элементам в очереди необходимо будет объявить временный указатель *temp, который с начального элемента. Функция возвратит последний элемент (потому как начальный элемент «всплывёт» в конец) и занулить его. Указатель сдвинуть на 1 элемент влево, чтобы он указывал на последний значащий элемент
Пример цикла, меняющего местами элементы
int *x;
x=t1.begin;
for(int i=0; i<t1.element - t1.begin; i++ )
  { swap( x ,x+1 ); x++; }

Пример реализации стека без помощи структур

#include <stdio.h>
#include <stdlib.h>

#define SIZE 50

void push(int i);
int pop(void);

int *tos, *p1, stack[SIZE];

int main(void)
{
  int value;

  tos = stack; /* tos ссылается на основание стека */
  p1 = stack; /* инициализация p1 */

  do {
  printf("Введите значение: ");
  scanf("%d", &value);

  if(value != 0) push(value);
  else printf("значение на вершине равно %d\n", pop());

  } while(value != -1);

  return 0;
}

void push(int i)
{
  p1++;
  if(p1 == (tos+SIZE)) {
  printf("Переполнение стека.\n");
  exit(1);
  }
  *p1 = i;
}

int pop(void)
{
  if(p1 == tos) {
  printf("Стек пуст.\n");
  exit(1);
  }
  p1--;
  return *(p1+1);
}