38. Понятие список, линейный список, последовательный список, связный список. Операции с линейными списками.

Списком называется линейную упорядоченность(последовательность) А(1)А(2)А(3)…А(n)

Каждый элемент последовательности имеет один и тот же набор полей. Определенный таким способом список называется линейным списком .Упорядоченность может задаваться путем последовательного расположения его элементов как в логической структуре так и в физической структуре. Такой список называют последовательным.Упорядоченность элементов может быть задана путем специальных указателей, располагаемых вместе с элементом и дающий возможность для каждого элемента определить его предшественника или последователя .Такие списки называют связными списками.Операции над списками :1)получить доступ к k-тому элементу списка, чтобы проанализировать или изменить его содержание.2)включить новый элемент перед/после k-того элемента3)исключить k-тый элемент4)объединить два или больше списков в один5)разбить один список на два или больше списков6)определить количество элементов7)выполнить сортировку8)найти элемент с заданным значением в некотором поле.

39. Операции над всеми ЛСД.Над любыми структурами данных могут выполняться четыре общие операции: создание, уничтожение, выбор (доступ), обновление.Операция создания заключается в выделении памяти для структуры данных. Память может выделяться в процессе выполнения программы или на этапе компиляции. В Си для структурированных данных операция создания включает в себя установку начальных значений параметров, создаваемой структуры. Для структур данных, объявленных в программе, память выделяется автоматически средствами систем программирования либо на этапе компиляции, либо при активизации процедурного блока, в котором объявляются соответствующие переменные. Либо программист сам выделять память.Операция уничтожения структур данных противоположна по своему действию операции создания. В Cи структуры данных, имеющиеся внутри блока, уничтожаются в процессе выполнения программы при выходе из этого блока. Операция уничтожения помогает эффективно использовать память.Операция выбора используется для доступа к данным внутри самой структуры. Форма операции доступа зависит от типа структуры данных, к которой осуществляется обращение. Метод доступа - один из наиболее важных свойств структур. Операция обновления позволяет изменить значения данных в структуре данных. Примером операции обновления является операция присваивания, или, более сложная форма - передача параметров. Вышеуказанные четыре операции обязательны для всех структур и типов данных. Помимо этих общих операций для каждой структуры данных могут быть определены операции специфические, работающие только данной структурой

40. Полустатическая структура данных стек. Операции над структурой данных стек.Это такой последовательный список с переменной длинной, включение или исключение элементов из которого выполняется только с одной стороны списка (список типа LIFO).Важнейшая операция доступа к стеку, включение/исключение элементов осуществляется только с вершины стека и в каждый момент времени для исключения доступен только элемент, находящийся в вершине стека. Вершина стека адресуется с помощью специального указателя. Для того чтобы включить новый элемент в стек, необходимо переместить указатель вершины стека и затем, по значению этого указателя, поместить в стек информацию о новом элементе. При исключении элемента из стека сначала прочитывается информация об исключаемом элементе по значению указателя вершины стека и затем указатель смещается на один элемент. Стек считается пустым, если в нем нет ни одного элемента. Чаще всего число элементов в стеке не может превышать некоторой величины. Такой стек называют ограниченным, а максимальным число элементов в нем называют глубиной стека. Если в процессе заполнения ограниченного стека, указатель вершины стека выйдет за границу стека, то происходит переполнение стека. Что случится при переполнение стека зависит от нас. При работе со стеком может возникнуть ситуация, когда мы захотим исключить из него элементы в то время, когда он пуст.При написании алгоритма по обработке стека, необходимо предусмотреть механизмы обнаружения, переполнения и антипереполнения стека. Если он отсутствует, то это приведет к дальнейшим ошибкам в работе программы при отсутствии переполнения, мы можем включать элементы в стек. Несмотря на то, что длинна стека может изменяться в процессе его использования, эти изменения на должны выходить за пределы некоторого фиксированного значения поэтому стек – полустатическая структура данных.