Последовательности (связанное распределение, стеки и очереди)

Связанное распределение

В лекции 11 даны примеры и программные реализации списков, стеков и очередей. Неудобство включения и исключения элементов при последовательном распределении происходит из-за того, что порядок следования элементов задается неявно требованием, чтобы смежные элементы последовательности находились в смежных ячейках памяти. В результате многие элементы последовательности во время включения или исключения должны передвигаться. Если это требование опущено, то можно выполнить операции включения и исключения без того, чтобы передвигать элементы последовательности. При связанном распределении последовательности (связанном списке) каждому $$s_i$$ поставлен в соответствии указатель (ссылка) $$P_i$$, отмечающий ячейку, в которой записаны $$s_{i + 1}$$ и $$P_{i + 1}$$. Существует также указатель $$P_0$$, который указывает начальную ячейку последовательности, то есть ячейку с символами $$s_1$$ и $$P_1$$. Все сказанное выше проиллюстрировано на рис. 3.1.

Здесь каждый узел состоит из двух полей. Под узлом понимается одно или несколько последовательных слов в памяти машины, которые выступают как единое целое и разделены на части, именуемые полями. В поле $$INFO$$ размещен сам элемент последовательности, а в поле $$LINK$$ - указатель на следующий за ним элемент.

Linked list - список с использованием указателей: список, в котором каждый элемент содержит указатель на следующий элемент или два указателя - на следующий и предыдущий. Поскольку для $$s_n = INF0(l_n)$$ следующего элемента не существует, будем использовать обозначение $$P_n = LINK(l_n ) = \Lambda $$, где $$\Lambda$$ - пустой , или нулевой указатель . Так как точные значения $$l_1,l_2,\ldots,l_n$$ для программиста не существенны, то в более общем виде связанное представление, показанное на рис. 3.1, можно изобразить так, как показано на рис.3.2.

Связанное представление последовательностей облегчает операции включения элемента после некоторого $$s_i$$ и исключения элемента $$s_{i + 1}$$, если ячейка для $$s_i$$ известна. Для этого необходимо лишь изменить значения некоторых указателей. Например, чтобы исключить элемент $$s_2$$ из последовательности, изображенной на рис. 3.2, необходимо только положить $$LINK(l_1) = LINK(l_2);$$ после такой операции элемента $$s_2$$ в последовательности больше не будет (рис.3.3). Чтобы в последовательность, изображенную на рис. 3.2, включить новый элемент $$s_5$$, необходимо только воспроизвести новый элемент в некоторой ячейке $$l_5$$ с $$INFO(l_5 ) = s_5$$ и $$LINK(l_5)=LINK(l_1)$$ и присвоить $$LINK(l_1 ) \leftarrow l_5$$.Это изображено на рис.3.4.

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

Будем предполагать, с целью использования в различных алгоритмах, существование операции порождения ячейки get_cell ; если эта операция присутствует в правой части оператора присваивания, то она дает адрес (место) новой неиспользованной ячейки памяти. Таким образом, чтобы добавить элемент $$s_5$$, как показано на рис. 3.4 нужно фактически использовать оператор get_cell для того чтобы найти значение $$l_5$$. Проблему сбора ненужных ячеек памяти будем полностью игнорировать, предполагая лишь, что их каким-то образом собирают для последующего использования; такой процесс носит название сбора мусора.

Недостаток при связанном распределении - приходится тратить память на указатели $$P_i^{}$$. В приложениях при выборе последовательного или связанного представления нужно сначала проанализировать типы операций, которые будут выполняться над последовательностью. Если операции производятся преимущественно над случайными элементами, осуществляют поиск специфических элементов или производят упорядочение элементов, то обычно лучше применять последовательное распределение. Связанное распределение предпочтительнее, если в значительной степени используются операции включения и(или) исключения элементов, а также сцепления и (или) разбиения последовательностей.

Разновидности связанных списков

Тривиальной модификацией связанного списка, изображенного на рис 3.2, будет следующее несколько более гибкое представление последовательности: если $$P_n$$ указывает на $$s_1$$, как показано на рис.3.5, то мы имеем так называемый циклический список. Такая форма списка дает возможность достигнуть любой элемент из любого другого элемента последовательности. Включение и исключение элементов здесь осуществляется так же, как и в нециклических списках, в то время как сцепление и разбиение реализуются несколько более сложно.

Еще большая гибкость достигается, если использовать дважды связанный список, когда каждый элемент $$s_i$$ последовательности вместо одного имеет два связанных с ним указателя. Как показано на рис. 3.6, они указывают на элементы $$s_{i-1}$$ и $$s_{i+1}$$. В таком списке для любого элемента имеется мгновенный прямой доступ к предыдущему и последующему элементам, в связи с чем облегчаются такие операции, как включение нового элемента перед $$s_i$$ и исключение элемента $$s_i$$ без предварительного знания его предшественника. Если есть необходимость, дважды связанный список очевидным образом можно сделать циклическим.

Стеки и очередь

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

Стеки и очереди имеют важное значение. Для выполнения какой-либо определенной задачи может потребоваться выполнение ряда подзадач. Каждая подзадача может также привести к другим требующим выполнения подзадачам. И стеки, и очереди являются механизмом, посредством которого запоминаются подзадачи, подлежащие выполнению, а также порядок, в котором они должны быть выполнены. В некоторых случаях порядок таков: " Первым пришел - последним ушел "; тогда удобно использовать стеки. Если порядок подчиняется правилу " Первым пришел - первым ушел ", то подходящим инструментом являются очереди.

Задачи

Задача 1. Создать список, элементами которого являются числа: 1 2 3 4 5 6 7 8 9. Вывести список на экран терминала. Включить в связанный список элемент 2005 после каждого элемента, который делится на 3. Модифицированный список вывести на экран терминала.

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

Программы

Программа 1. Создание списка.

// Алгоритм реализован на языке программирования Turbo-C++.
#include <stdio.h>
#include <conio.h>
#include <dos.h>

struct List{int i;
         List*next;
        };
List*head=NULL;

void Hed(int i)
{if(head==NULL){head=new List;
        head->i=1;
        head->next=NULL;
           }else
{
 struct List*p,*p1;
 p=head;
 while(p->next!=NULL)
 p=p->next;

 p1=new List;
 p1->i=i;
 p1->next=NULL;
 p->next=p1;
}
}

int s=0;

 void Print(List*p)
{cprintf(" %d",p->i);
 if(p->next!=NULL)Print(p->next);
}

 void delist()
{List*p;
 while(head!=NULL)
 {p=head;
  head=head->next;
  delete(p);
 }
}
void Vstavka(int i1,int c)
{List*p=head,*p1;
 while(p->i!=i1)
 p=p->next;
 p1=new List;
 p1->i=c;
 p1->next=p->next;
 p->next=p1;
}

void main()
{
 clrscr();
 for(int i=1;i<=10;i++)
 Hed(i);
textcolor(12);
 Print(head);
textcolor(1);
 Vstavka(10,11);
 printf("\n");
 Print(head);
  textcolor(11);
 Vstavka(3,12);
 printf("\n");
 Print(head);
 textcolor(14);
 Vstavka(5,13);
 printf("\n");
Print(head);
 delist();
 getch();
}

Программа 2. Создание стека и работа со стеком.

//Работа со стеком
// Алгоритм реализован на языке программирования Turbo-C++.
#include <stdio.h>
#include <dos.h>
#include <iostream.h>
#include <PROCESS.H>
#include <STDLIB.H>
#include <conio.H>
#define max_size 200
// char s[max_size]; //компоненты стека
int s[max_size];
     int next=0; //  позиция стека
     int Empty()
     {
          return next==0;
     }
     int Full()
     {
          return next==max_size;
     }
     void Push()
     { if (next==max_size)
          {
           cout <<"Ошибка: стек полон"<<endl;}

     else {  next++;cout <<"Добавлен"<<endl;
           cout <<"Что поместить в стек?"<<endl;
           cin <<s[next-1];
           }
     }
     void OUTst()
     {int i=0;
      if (next==0)
             {
              cout <<"Cтек пуст"<<endl;}

     else { for(i=0;i <next;i++)
           cout <<s[i] <<"" <<endl;
           }
     }
     void Clear()
     {
          next=0;
     }
     Poz()
     {
          return next;
     }
     void Del()
     {
     int a;
          if (next==0) cout <<"Ошибка: стек пуст" <<endl; else
          {next--;cout <<"Удален" <<endl;}
     }
     void menu(){
           cout <<"0: распечатать стек" <<endl;
           cout <<"1: добавить в стек" <<endl;
           cout <<"2: удалить из стека" <<endl;
           cout <<"3: узнать номер позиции в стеке" <<endl;
           cout <<"4: узнать, пуст ли стек" <<endl;
           cout <<"5: узнать, полон ли стек" <<endl;
           cout <<"6: очистить стек" <<endl;
           cout <<"7: выход" <<endl;
     }
     main()
      {
       char c;
        clrscr();
        textcolor(11);
        do {
            menu();
            cin"c;
            clrscr();
            switch (c)  {
            case "0":OUTst();getch();break;
            case "1":Push();break;
            case "2":Del();getch();break;
            case "3":cout <<"Hомер" <<Poz() <<endl;getch();break;
            case "4":if (Empty()==1) cout <<"Пуст" <<endl; else cout <<"Hе
            пуст" <<endl;getch();break;
            case '5':if (Full()==1)cout <<"Полон" <<endl; else cout <<"Hе
            полон" <<endl;getch();break;
            case '6':Clear();cout <<"Стек очищен" <<endl;getch();break;
            case '7':exit(1);
       }
       delay(200);
       }
       while (c!=7);
    return 0;
    }