Задания для самоконтроля

1. Последовательность целых чисел А₁, А₂, …, А_n задана как линейный список в связанном хранении и задан указатель первого элемента. Написать функцию для обращения этого списка, т.е. получить список A_n, A_n-1, … , A₁ в связанном хранении.

2. Написать функцию, которая, исследуя элементы линейного списка К₁, К₂, … К_nв связанном хранении. Упорядочивает их в список элементов К^’₁, K^’₂, …, K^’_s, K₁, K^”₁,…, K”_t, где s + t + 1=n, K’_I<K₁, K”_iK₁ в связанном хранении (указатель на первый элемент списка задан).

3. Последовательность F= А₁, А₂, …, А_k целых чисел А₁ А₂ …  А_k и стек V свободной памяти хранятся как простые связанные структуры с указателями AF и AV на их начало. Написать фрагмент программы, который для каждого I, 1 ik-1, такого, что A_i=A_i+1, удаляет число A_i+1 из списка и добавляет освободившийся участок памяти к стеку V свободной памяти.

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

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

6. По заданной фамилии выдать телефоны всех однофамильцев.

2.5. Стеки и очереди

В зависимости от метода доступа к элементам линейного списка различают разновидности линейных списков называемые стеком, очередью и двусторонней очередью.

Стек– это конечная последовательность некоторых однотипных элементов – скалярных переменных, массивов, структур или объединений, среди которых могут быть и одинаковые.

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

Стек обозначается в виде: S= и представляет динамическую структуру данных; ее количество элементов заранее не указывается и в процессе работы, как правило изменяется. Если в стеке элементов нет, то он называется пустым и обозначается S=<>.

Допустимыми операциями над стеком являются:

- проверка стека на пустоту S=<>,

- добавление нового элемента S_n+1 в конец стека - преобразование < S₁,..., S_n> в < S₁ ,..., S_n+1>;

- изъятие последнего элемента из стека - преобразование < S₁,..., S_n-1 , S_n> в < S₁,..., S_n-1>;

- доступ к его последнему элементу S_n, если стек не пуст.

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

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

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

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

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

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

Одной из форм представления выражений является польская инверсная запись, задающая выражение так, что операции в нем записываются в порядке выполнения, а операнды находятся непосредственно перед операцией.

Например, выражение (6+8)*5-6/2 в польской инверсной записи имеет вид 6 8 + 5 * 6 2 / -.

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

S=<<6><6,8><14><14,5><70><70,6>

<70,6,2><70,3><67>.

Ниже приведена функция eval, которая вычисляет значение выражения, заданного в массиве m в форме польской инверсной записи, причем m[i]0 означает неотрицательное число, а значения m[i]<0 - операции. В качестве кодировки операций сложения, вычитания, умножения и деления выбраны отрицательные числа -1, -2, -3, -4. Для организации последовательного хранения стека используется внутренний массив stack. Параметрами функции являются входной массив m и его длина l.

float eval (float *m, int l)

{

int p,n,i;

float stack[50],c;

for(i=0; i<l; i++)

if ((n=m[i])<0)

{

c=st[p--];

switch(n)

{

case -1: stack[p]+=c; break;

case -2: stack[p]-=c; break;

case -3: stack[p]*=c; break;

case -4: stack[p]/=c;

}

}

else stack[++p]=n;

return(stack[p]);

}

Рассмотрим другую задачу. Пусть требуется ввести некоторую последовательность символов, заканчивающуюся точкой, и напечатать ее в обратном порядке (т.е. если на входе будет «ABcEr-1», то на выходе должно быть «1-rEcBA»). Представленная ниже программа сначала вводит все символы последовательности, записывая их в стек, а затем содержимое стека печатается в обратном порядке. Это основная особенность стека - чем позже элемент занесен в стек, тем раньше он будет извлечен из стека. Реализация стека выполнена в связанном хранении при помощи указателей p и q на тип, именованный именем STACK.

#include <STDLIB.H>

#include <STDIO.H>

#include <CONIO.H>

typedef struct st { /* объявление типа STACK */

char ch;

struct st *ps;

} STACK;

void main()

{

STACK *p, *q;

char a;

p=NULL;

do /* заполнениестека */

{

a=getch();

q=(STACK*)malloc(sizeof(STACK));

q->ps=p; p=q;

q->ch=a;

} while(a!='.');

do /* печатьстека */

{

p=q->ps;free(q);q=p;

printf("%c",p->ch);

} while(p->ps!=NULL);

}

Задания для самоконтроля

1. Написать функцию копирования очереди, реализованной в виде циклического списка.

2. Написать функцию копирования двусторонней очереди, которая реализована в виде списка с двумя связями.

3. Пусть два целых положительных числа N и K даны на входе. Предположим, что числа 1,2,…,N расположены упорядоченно по кругу. Составить программу, которая, начиная с 1 и продолжая по часовой стрелке, печатает текущее число, удаляет его из круга и затем рассматривает K-е следующие число в списке, причем процесс продолжается до тех пор, пока список не станет пустым. Так для значений N=10, K<>3 получаем выход: 1,4,7,10,5,9,6,3,8,9.

4. Пусть задан одномерный массив из 100 элементов, используемых для последовательного хранения очереди. На входе заданна последовательность целых чисел, Если число n>0, то его нужно добавить в очередь; если n=-1, то очередной элемент из очереди следует удалить; если n=0, то имеем конец списка. Написать фрагмент программы, который работает с очередью как с циклической структурой и печатает сообщения об ошибках каждый раз при обнаружении аварийной ситуации.

5. Разработать программу для одновременного хранения пяти стеков в одномерном массиве из M элементов. При необходимости перераспределения стеки следует упорядочить так, чтобы свободные участки памяти были поровну распределены между ними. С начала все стеки пустые. Вход содержит пары целых чисел (i,j), 1abs5, причем пара (i,j), где j>0, указывает, что элемент со значением i добавляется в j-й стек; пара (i,j), где j<0, указывает, что очередной элемент j-го стека нужно удалить(i здесь не используется). Программа должна печатать расположение стеков до и после каждого перераспределения.