12.Понятие «дек».

Дек – структура, обладающая свойствами очереди и стека. Элементы можно добавлять как в начало, так и в конец списка.

13.Обратная польская запись: алгоритм ее составления.

Если посмотреть внимательно, можно заметить, что операнды в постфиксной форме не меняют своего относительного расположения, а вот порядок следования операций и функций меняется как по отношению к операндам, так и по отношению друг к другу.

Правила перевода следующие

1. Ввести в стек левую скобку '('

2. Добавить в конец строки с инфиксным выражением правую скобку ')'

3. Пока стек не пуст, считываем символы из строки содержащей инфиксное выражение слева направо и выполняем следующие действия.

   1. Если текущий символ в инфиксной строке – левая скобка, помещаем ее в стек.

   2. Если текущий символ в инфиксной строке – правая скобка, извлекаем знаки операций из стека и вставляем их в результирующую строку, до тех пор пока на вершине стека не появиться левая скобка. Извлечь левую скобку и отбросить ее.

   3. Если текущий символ в инфиксной строке – знак операции, извлекаем знаки операций из стека (если они там есть), пока соответсвующее им операции имеют равный или более высокий приоритет по сравнению с текущей операцией, и вставляем извлеченные знаки операций в результирующую строку. Вставим текущий символ в стек.

   4. Если текущий символ в инфиксной строке – цифра, копируем его в результирующую строку.

15.Двусвязные списки и их свойства.

Связанное хранение линейного списка называется списком с двумя

связями или двусвязным списком, если каждый элемент хранения имеет два

компонента указателя (ссылки на предыдущий и последующий элементы линейного списка).

Реализация одного элемента списка

typedef struct node

{

int data;

struct node *next;

struct node *previos;

}ITEM;

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

typedef struct head

{

struct node *first;

struct node *last;

}HEAD;

16.Иерархические списки и их свойства.

- это несколько подсписков ранжированных по уровням так, что элементы подсписка уровня 0 являются головным элементом для подсписков уровня 1, и так далее.

Элементы списка имеют компоненты головного элемента подсписка нижележащего.

При реализации нужно учитывать:

1. кол-во уровней

2. кол-во разных типов подсписков, расположенных на одном уровне.

Кол-во уровней велико и на каждом уровне могут располагаться несколько типов подсписков.