Организация списков и их обработка


Содержание

Вопросы и ответы для государственного экзамена (кафедра САПР) — файл metoda.doc

Доступные файлы (1):

metoda.doc 6827kb. 09.06.2004 23:05 скачать

содержание

    Смотрите также:
  • Вопросы государственного междисциплинарного аттестационного экзамена для студентов, обучающихся по специальности Прикладная информатика в экономике[ вопрос ]
  • Ответы на вопросы экзамена на получение квалификационного аттестата аудитора[ документ ]
  • Вопросы и ответы — Гражданский процесс РФ[ документ ]
  • Ответы на Экзаменационный Тест САПР ДВС[ шпаргалка ]
  • Вопросы для ГОСа по БЖД[ документ ]
  • по САПР (Мухутдинова)[ документ ]
  • Шпоры по компьютерной графике. Геометрическое моделирование в САПР. 45 вопросов к экзамену и ответы[ документ ]
  • Билеты ГОС. Экзамена по украинскому языку с примерными ответами (для филологов)[ вопрос ]
  • Ответы на вопросы для сдачи экзамена кандидатского минимума по общей педагогике[ шпаргалка ]
  • Вопросы и ответы к экзамену. Буровые и тампонажные растворы[ вопрос ]
  • Билеты и ответы на ГОСы по менеджменту на бакалавра 2010[ документ ]
  • Принципы построения САПР[ документ ]

metoda.doc

1.4. Динамические структуры данных в языке «С» — списки. Основные виды и способы реализации. Операции со списками.

Понятие линейного списка.

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

Линейный список List , состоящий из элементов Element 1, Element 2, …, Element N , записывают в виде последовательности значений заключенной в угловые скобки List =<>, или представляют графически:

Рис.1. Изображение линейного списка.

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

^ Последовательное хранение линейных списков.

При последовательном хранении элементы линейного списка размещаются в массиве maslist фиксированных размеров, например, 100 , и длина списка указывается в переменной len , т.е. в программе необходимо иметь объявления вида:

float maslist [100]; /* Объявление массива размером в 100 элементов */

int len ; /* Объявление переменной целого типа */

Размер массива 100 ограничивает максимальные размеры линейного списка. Список List в массиве maslist формируется так:

maslist [0]=7; /* Ввод элементов */

maslist [1]=10; /* массива */

len =2; /* Ввод значения переменной len */

Полученный список хранится в памяти согласно схеме на рис.2.

Рис.2. Последовательное хранение линейного списка.

^ Связанное хранение линейных списков.

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

Рис.3. Элемент списка.

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

Определение и объявление.

В простейшем случае каждый узел содержит всего одну ссылку.

Рис.4. Организация односвязного списка.

Каждый элемент содержит также ссылку на следующий за ним элемент. У последнего в списке элемента поле ссылки содержит NULL . Чтобы не потерять список, мы должны хранить адрес его первого узла — он называется «головой» списка. В программе надо объявить два новых типа данных — узел списка Node и указатель на него PNode . Узел представляет собой структуру, которая содержит три поля — строку, целое число и указатель на такой же узел. Правилами языка Си допускается объявление:

/* Определение структуры элементов списка. */

typedef struct list <

char word [40]; /* Объявление массива символов размером 40 символов */

int count ; /* Объявление переменной целого типа */

struct list * next ; /* Объявление указателя на следующий элемент списка */

struct list * PNode ; /* Объявление указателя на любой элемент списка */

PNode head ; /* Объявление указателя на первый элемент списка */

^ Операции со списком.

/* Создание нового элемента. */

PNode CreateNode ( char NewWord [])<

PNode NewNode ; /* Создание указателя для нового узла */

NewNode = malloc ( sizeof ( Node )); /* Выделение памяти для нового узла */

strcpy ( NewNode -> word , NewWord ); /* Заполнение полей */

NewNode -> count = 1; /* нового узла списка */

NewNode -> next = NULL ; /* Ссылка на следующий узел (пустая) */

return NewNode ; /* Возвращение указателя на созданный узел */

После этого узел надо добавить к списку.

^ Добавление узла в начало списка .

Рис.5. Добавление элемента в начало списка.

По такой схеме работает процедура AddFirst . Предполагается, что адрес начала списка хранится в глобальной переменной head .

/* Добавление элемента в начало списка. */

void AddFirst ( PNode NewNode )<

NewNode -> next = head ; /* Следующий узел–первый в старом списке */

head = NewNode ; /* Текущая запись – первая в новом списке */

^ Поиск заданного элемента в списке.

Добавление узла после заданного.

Дан адрес NewNode нового узла и адрес р одного из существующих узлов в списке. Требуется вставить в список новый узел после узла с адресом р. Эта операция выполняется в два этапа:

1. Установить ссылку нового узла на узел, следующий за данным;

2. Установить ссылку данного узла р на NewNode .

Рис.6. Добавление элемента после заданного.

^ Добавление узла перед заданным.

Эта схема добавления самая сложная. Проблема заключается в том, что в односвязном списке мы можем, зная адрес узла, получить адрес предыдущего узла, только пройдя весь список сначала. Задача сведется либо к вставке узла в начало списка (если заданный узел -п ервый), либо к вставке после заданного узла.

Существует еще один интересный прием: если надо вставить новый узел NewNode до заданного узла р , вставляют узел после этого узла, а потом выполняется обмен данными между узлами NewNode и р. Таким образом, по адресу р в самом деле будет расположен узел с новыми данными, а по адресу NewNode — с теми данными, которые были в узле р , то есть мы решили задачу. Этот прием не сработает, если адрес нового узла NewNode запоминается где-то в программе и потом используется, поскольку по этому адресу будут находиться другие данные.

^ Добавление узла в конец списка.

Для решения задачи надо сначала найти последний узел, у которого ссылка равна NULL , a затем воспользоваться процедурой вставки после заданного узла. Отдельно надо обработать случай, когда список пуст.

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

Рис.7. Удаление элемента списка.

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

Определение и объявление.

Многие проблемы, присущие односвязным спискам, вызваны тем, что в них невозможно перейти к предыдущему элементу. Возникает естественная идея — хранить в памяти ссылку не только на следующий, но и на предыдущий элемент списка. Для доступа к списку используется не одна переменная-указатель, а две — ссылка на «голову» списка ( head ) и на «хвост» — последний элемент ( tail ).

Рис.8. Организация двусвязного списка.

Каждый узел содержит (кроме полезных данных) также ссылку на следующий за ним узел (поле next ) и предыдущий (поле prev ). Поле next у последнего элемента и поле prev у первого содержат NULL . Узел объявляется так:

^ Операции со списком.

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

Добавление узла в начало списка.

При добавлении нового узла NewNode в начало списка надо

1. Установить ссылку next узла NewNode на голову существующего списка и его ссылку prev в NULL ;

2. Установить ссылку prev бывшего первого узла (если он существовал) на NewNode ;

3. Установить голову списка на новый узел;

4. Если в списке не было ни одного элемента, хвост списка также устанавливается на новый узел.

Рис.9. Добавление элемента в начало списка.

По такой схеме работает следующая процедура:

/* Определение структуры элементов списка. */

void AddFirst ( PNode NewNode )<

NewNode ->next = head;

NewNode -> prev = NULL;

if (head) head-> prev = NewNode ;

if (!tail) tail = head;

^ Добавление узла в конец списка.

Благодаря симметрии добавление нового узла NewNode в конец списка проходит совершенно аналогично, в процедуре надо везде заменить head на tail и наоборот, а также поменять prev и next .

^ Поиск заданного элемента в списке.

Проход по двусвязному списку может выполняться в двух направлениях — от головы к хвосту (как для односвязного) или от хвоста к голове.

^ Добавление узла после заданного.

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

1. установить ссылки нового узла на следующий за данным ( next ) и предшествующий ему ( prev );

2. установить ссылки соседних узлов так, чтобы включить NewNode в список.

Рис.10. Добавление элемента после заданного.

Такой метод реализует приведенная ниже процедура (он а учитывает также возможность вставки элемента в конец списка — именно для этого в параметрах передаются ссылки на голову и хвост списка):

/* Добавление элемента после заданного. */

void AddAfter ( PNode p , PNode NewNode )<

/* Добавление последнего узла в список */

AddLast (head, tail, NewNode );

/* Добавление узла в середине списка */

NewNode ->next = p->next;

NewNode -> prev = p;

p->next-> prev = NewNode ;

p -> next = NewNode ;

Эта операция выполняется почти также с учетом симметричности структуры.

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

Рис.11. Удаление элемента списка.

void Delete( PNode &head, PNode &tail, PNode OldNode )<

/* Удаляемый узел — первый */

if (head == OldNode )<

head = OldNode ->next;

head-> prev = NULL;

/* Удаляемый узел – любой другой */

OldNode -> prev ->next = OldNode ->next;

if ( OldNode ->next)

OldNode ->next-> prev = OldNode -> prev ;

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

Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) List = Node 1, Node 2. Node n >. Требуется переставить элементы списка В так, чтобы получить упорядоченный список List ‘= Node ‘1, Node ‘2. Node ‘ n >, в котором для любого 1 Node ‘( i ) Node ‘( i +1).

При обменной сортировке упорядоченный список List ‘ получается из List систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.

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

List =, исходный список; List 1= , первый просмотр; List 2= , второй просмотр; List 3= , третий просмотр.

В последующих примерах будем считать, что сортируется одномерный массив (либо его часть от индекса n до индекса m ) в порядке возрастания элементов.

Пузырьковая сортировка выполняется при количестве действий Q =( n — m )*( n — m ) и не требует дополнительной памяти.

^ Циклические списки, стеки, очереди, деки.

Иногда список (односвязный или двусвязный) замыкают в кольцо, то есть указатель next последнего элемента указывает на первый элемент, и (для двусвязных списков) указатель prev первого элемента указывает на последний. В таких списках понятие «хвоста» списка не имеет смысла, для работы с ним надо использовать указатель на «голову», причем «головой» можно считать любой элемент.

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

Стек называют структурой типа LIFO ( Last In — First Out ) — последним пришел, первым ушел. Моделью стека может служить стопка с подносами, уложенными один на другой — чтобы достать какой-то поднос надо снять все подносы, которые лежат на нем, а положить новый поднос можно только сверху всей стопки. На рисунке показан стек, содержащий 6 элементов.

Рис.12. Организация стека.

В современных компьютерах стек используется для

— размещения локальных переменных .

— размещения параметров процедуры или функции .

— сохранения адреса возврата (по какому адресу надо вернуться из процедуры) .

— временного хранения данных, особенно при программировании на Ассемблере .

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

^ Реализация стека в языке Си.

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

/* Определение структуры элемента стека. */

/* Ссылки на соседние элементы */

struct list * next , * prev ;

typedef Node * PNode ;

Для удобства чтобы не работать с отдельными указателями на хвост и голову списка, объявим структуру, в которой будет храниться вся информация о стеке:

/* Информация о граничных элементах стека. */

PNode head, tail;

В самом начале надо записать в обе ссылки стека NULL .

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

^ Добавление элемента на вершину стека.

Фактически это добавление нового элемента в начало двусвязного списка. Эта процедура уже была написана ранее, теперь ее придется немного переделать, чтобы работать не с отдельными указателями, а со структурой типа Stack . В параметрах процедуры указывается не новый узел, а только данные для этого узла, то есть целое число. Память под новый узел выделяется в процедуре, то есть, скрыта от нас и снижает вероятность ошибки.

void Push (Stack &S, int i )<

/* Выделение памяти для нового узла */


NewNode = malloc ( sizeof ( Node ));

/* Заполнение полей новой записи */

NewNode -> data = i ;

/* Внесение нового узла в стек */

NewNode -> next = S . h ead ;

NewNode -> prev = NULL;

if( S. h ead ) S. h ead -> prev = NewNode ;

S. h ead = NewNode ;

if(! S. t ail ) S. t ail = S. h ead ;

^ Получение верхнего элемента с вершины стека.

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

/* Получение элемента стека и удаление его. */

int Pop (Stack &S)<

PNode TopNode = S. h ead ;

/* Проверка на наличие элементов в стеке */

if(! TopNode ) return 0;

/* Получение данных от узла стека */

i = TopNode -> data ;

/* Удаление первого узла списка */

S . h ead = TopNode -> next ;

if( S. h ead ) S. h ead -> prev = NULL;
else S. t ail = NULL;

^ Системный стек в программах.

В языке Си на системный стек по умолчанию отводится 4 Кб памяти. Это очень немного и довольно частой ошибкой в больших программах является переполнение стека — выход за границы отведенной памяти. Чтобы сразу получить сообщение о переполнении, надо включить опцию Test stack overflow компилятора. В этом случае при каждом новом вызове процедур программа будет проверять, достаточно ли места в стеке. При переполнении стека происходит аварийный выход. Если в самом деле надо расширить область стека, в начале основного модуля программы напишите

extern unsigned _ stklen = 10000;

Дело в том, что размер стека определяется системной глобальной переменной _ stklen , которую мы и изменили.

При программировании для Windows размер стека по умолчанию равен 1 Мб, этого хватает для всех стандартных приложений.

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

Хорошо знакомой моделью является очередь в магазине. Очередь называют структурой типа FIFO ( First In — First Out ) — первым пришел, первым ушел. На рисунке изображена очередь из 3-х элементов.

Рис.13. Организация очереди.

Наиболее известные примеры применения очередей в программировании — очередь событий системы Windows и ей подобных. Очереди используются также для моделирования в задачах массового обслуживания (например, обслуживания клиентов в банке).

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

Дек может быть реализован на основе стека, рассмотренного выше. Остается добавить только две функции — добавление нового элемента в конец ( PushTail ) и получение последнего элемента с его удалением из дека (функция PopTail ). Они легко получаются из уже написанных Push и Pop путем замены head на tail и prev на next , и наоборот.

Организация списков.

Преимущества динамической памяти становятся особенно очевидными при организации динамических структур

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

Элементы динамической структуры связаны через адреса (стеки, очереди, деревья, сети и т.д.). Основой моделирования таких структур являются списки.

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

Список — структура данных, в которой каждый элемент имеет информационное поле (поля) и ссылку (ссылки), то есть адрес (адреса), на другой элемент (элементы) списка. Список — это так называемая линейная структура данных, с помощью которой задаются одномерные отношения.

Каждый элемент списка содержит информационную и ссылочную части. Порядок расположения информационных и ссылочных полей в элементе при его описании — по выбору программиста, то есть фактически произволен. Информационная часть в общем случае может быть неоднородной, то есть содержать поля с информацией различных типов. Ссылки однотипны, но число их может быть различным в зависимости от типа списка. В связи с этим для описания элемента списка подходит только тип «запись», так как только этот тип данных может иметь разнотипные поля. Например, для однонаправленного списка элемент должен содержать как минимум два поля: одно поле типа «указатель», другое — для хранения данных пользователя. Для двунаправленного — три поля, два из которых должны быть типа «указатель».

Структура элемента линейного однонаправленного списка представлена на рисунке.

Следует рассмотреть разницу в порядке обработки элементов массива и списка.

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

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

Односвязный список

Введение. Основные операции

О дносвязный список – структура данных, в которой каждый элемент (узел) хранит информацию, а также ссылку на следующий элемент. Последний элемент списка ссылается на NULL.

Для нас односвязный список полезен тем, что

  • 1) Он очень просто устроен и все алгоритмы интуитивно понятны
  • 2) Односвязный список – хорошее упражнение для работы с указателями
  • 3) Его очень просто визаулизировать, это позволяет «в картинках» объяснить алгоритм
  • 4) Несмотря на свою простоту, односвязные списки часто используются в программировании, так что это не пустое упражнение.
  • 5) Эта структуру данных можно определить рекурсивно, и она часто используется в рекурсивных алгоритмах.

Для простоты рассмотрим односвязный список, который хранит целочисленное значение.

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

Чтобы не писать каждый раз struct мы определили новый тип.
Теперь наша задача написать функцию, которая бы собирала список из значений, которые мы ей передаём. Стандартное имя функции – push, она должна получать в качестве аргумента значение, которое вставит в список. Новое значение будет вставляться в начало списка. Каждый новый элемент списка мы должны создавать на куче. Следовательно, нам будет удобно иметь один указатель на первый элемент списка.

Вначале списка нет и указатель ссылается на NULL.
Для добавления нового узла необходимо

  • 1) Выделить под него память.
  • 2) Задать ему значение
  • 3) Сделать так, чтобы он ссылался на предыдущий элемент (или на NULL, если его не было)
  • 4) Перекинуть указатель head на новый узел.

1) Создаём новый узел

2) Присваиваем ему значение

3) Присваиваем указателю tmp адрес предыдущего узла

4) Присваиваем указателю head адрес нового узла

5) После выхода из функции переменная tmp будет уничтожена. Получим список, в который будет вставлен новый элемент.

Так как указатель head изменяется, то необходимо передавать указатель на указатель.

Теперь напишем функцию pop: она удаляет элемент, на который указывает head и возвращает его значение.

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

Уже после этого можно удалить первый элемент и вернуть его значение

Не забываем, что необходимо проверить на NULL голову.

Таким образом, мы реализовали две операции push и pop, которые позволяют теперь использовать односвязный список как стек. Теперь добавим ещё две операции — pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение.

Для дальнейшего разговора необходимо реализовать функции getLast, которая возвращает указатель на последний элемент списка, и nth, которая возвращает указатель на n-й элемент списка.

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

Переходя на следующий элемент не забываем проверять, существует ли он. Вполне возможно, что был указан номер, который больше размера списка. Функция вернёт в таком случае NULL. Сложность операции O(n), и это одна из проблем односвязного списка.

Для нахождение последнего элемента будем передирать друг за другом элементы до тех пор, пока указатель next одного из элементов не станет равным NULL

Теперь добавим ещё две операции — pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение.

Для вставки нового элемента в конец сначала получаем указатель на последний элемент, затем создаём новый элемент, присваиваем ему значение и перекидываем указатель next старого элемента на новый

Односвязный список хранит адрес только следующего элемента. Если мы хотим удалить последний элемент, то необходимо изменить указатель next предпоследнего элемента. Для этого нам понадобится функция getLastButOne, возвращающая указатель на предпоследний элемент.

Функция должна работать и тогда, когда список состоит всего из одного элемента. Вот теперь есть возможность удалить последний элемент.

Удаление последнего элемента и вставка в конец имеют сложность O(n).

Можно написать алгоритм проще. Будем использовать два указателя. Один – текущий узел, второй – предыдущий. Тогда можно обойтись без вызова функции getLastButOne:

Теперь напишем функцию insert, которая вставляет на n-е место новое значение. Для вставки, сначала нужно будет пройти до нужного узла, потом создать новый элемент и поменять указатели. Если мы вставляем в конец, то указатель next нового узла будет указывать на NULL, иначе на следующий элемент

Покажем на рисунке последовательность действий

После этого делаем так, чтобы новый элемент ссылался на следующий после n-го

Динамические структуры данных: однонаправленные и двунаправленные списки

Цель лекции: изучить понятия, классификацию и объявление списков, особенности доступа к данным и работу с памятью при использовании однонаправленных и двунаправленных списков, научиться решать задачи с использованием списков на языке C++.

Понятие списка хорошо известно из жизненных примеров: список студентов учебной группы, список призёров олимпиады, список (перечень) документов для представления в приёмную комиссию, список почтовой рассылки, список литературы для самостоятельного чтения и т.п.

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

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

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

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

  • однонаправленные (односвязные) списки;
  • двунаправленные ( двусвязные ) списки;
  • циклические (кольцевые) списки.

В основном они отличаются видом взаимосвязи элементов и/или допустимыми операциями.

Однонаправленные (односвязные) списки

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

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

Описание простейшего элемента такого списка выглядит следующим образом:

struct имя_типа поле ; адресное поле ; >;

где информационное поле – это поле любого, ранее объявленного или стандартного, типа;

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

Информационных полей может быть несколько.

Каждый элемент списка содержит ключ , который идентифицирует этот элемент. Ключ обычно бывает либо целым числом, либо строкой.

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

  • создание списка;
  • печать (просмотр) списка;
  • вставка элемента в список;
  • удаление элемента из списка;
  • поиск элемента в списке
  • проверка пустоты списка;
  • удаление списка.

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

Рассмотрим подробнее каждую из приведенных операций.

Для описания алгоритмов этих основных операций используется следующее объявление:

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

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

Печать (просмотр) однонаправленного списка

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

Списковые структуры (списки).

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

Различают одно- и двунаправленные, одно- и многосвязные списки. Списки легко обобщаются до понятия графа.

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

В списке выделяется собственная информация (записи с содержательными сведениями) и ассоциативная информация, т. е. все адреса связи.

Описание записей списка на языке программирования (например, Паскаль) может быть произведено двумя способами.

1. Определение адресов связи как начальных адресов записей.

2. Определение адресов связи, как номеров записей.

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

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

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

При формировании упорядоченного списка записей возможны два варианта:

• вновь поступающие записи вставлять так, чтобы не нарушать упорядоченность по ключу;

• создать сначала неупорядоченный список, а затем отсортировать его.

Учитывая, что для сортировки можно использовать метод слияния, второй вариант следует признать более целесообразным. Односвязные и двусвязные списки:

Хэш-адресация.

Бинарные деревья, B+деревья и их использование в СУБД. Объектно-ориентированное визуальное проектирование приложений в объектно-ориентированных СУБД. Понятие транзакции. Управление доступом, привилегии.

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

Бинарное (двоичное) дерево (binary tree) — это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.
Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева.
Узел дерева, не имеющий потомков, называется листом.
Схематичное изображение бинарного дерева:

Бинарное дерево может представлять собой пустое множество.

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

B+ дерево — структура данных, представляет собой сбалансированное дерево поиска. Является модификацией B-дерева, истинные значения ключей которого содержатся только в листьях, а во внутренних узлах — ключи-разделители, содержащие диапазон изменения ключей для поддеревьев.

При построении B+ дерева, его временами приходится перестраивать. Это связано с тем, что количество ключей в каждом узле (кроме корня) должно быть от k, до 2k, где k — степень дерева. При попытке вставить в узел (2k+1)-й ключ возникает необходимость разделить этот узел. В качестве ключа-разделителя сформированных ветвей выступает (k+1)-й ключ, который помещается на соседний ярус дерева. Особым же случаем является разделение корня, так как в этом случае увеличивается число ярусов дерева. Особенностью разделения листа B+ дерева является то, что он делится на неравные части. При разделении внутреннего узла или корня возникают узлы с равным числом ключей k. Разделение листа может вызвать «цепную реакцию» деления узлов, заканчивающуюся в корне.

В B+ дереве легко реализуется независимость программы от структуры информационной записи.

Поиск обязательно заканчивается в листе.

Удаление ключа имеет преимущество — удаление всегда происходит из листа.

Другие операции выполняются аналогично B-деревьям.

B+ деревья требуют больше памяти чем B-деревья для представления.

B+ деревья имеют возможность последовательного доступа к ключам.

Транзакция –набор команд на SQL языке, выполняемых единым блоком, который выполняется по принципу все или ничего.

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

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

Доступ к данным и возможностям СУБД персонифицирован. Для каждого действия, выполняемого в системе, определено, каким пользователем оно выполняется. Пользователь (user) — это некоторое имя, определенное в базе данных и связанное с некоторым субъектом, который может соединяться с базой данных и выполнять доступ к ее объектам.

Логически пользователь понимается рассматриваемыми СУБД одинаково, хотя с принципиально различными реализациями этого понятия.

Процедура аутентификации (authentication) состоит в представлении пользователя системе при установлении соединения с базой данных и подтверждении его подлинности. Подтверждение подлинности выполняется паролем (password) . Процедура аутентификации выполняется при запуске пользователем приложения.

Привилегия — некоторый поддерживаемый системой признак, который определяет, разрешение не выполнение какой-либо конкретной операции (общей или относящейся к конкретному объекту). Каждое действие, выполняемое пользователем в базе данных, сопровождается процедурой авторизации (authorization), которая заключается в проверке того, может ли данный пользователь выполнять запрошенное действие над данным объектом, т.е., имеет ли данный пользователь данную привилегию. По результатам авторизации запрос на доступ выполняется или отклоняется.

Методы аутентификации

Для аутентификации могут использоваться внутренние или внешние методы.

При применении внутренних методов данные аутентификации пользователи являются объектами базы данных и их имена и пароли хранятся в СУБД.

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

Последнее изменение этой страницы: 2020-04-19; Нарушение авторского права страницы

Работа со списками данных в Excel

Добрый день уважаемый читатель!

Сегодня я хочу поговорить об одной из основных возможностях — это работа со списками данных в Excel. К самим спискам можно отнести практически любые структурированные данные, такие как, номера телефонов, адреса, ФИО, номенклатурные наименования товаров, перечень заведений, поставщики, сотрудники и много-много другой информации, своего рода база данных. Я думаю, с такими данными вы сталкивались, а значится и инструменты для систематизации и анализа таких данных будут очень полезны, особенно при создании дашбордов. По большому счёту от обычной таблицы списки ничем особым не отличаются, за исключением своих размеров, они достаточно велики. При работе со списками используют понятия: для строк – записи, а для столбиков – поля.

Для примера используем список или базу данных сотрудников и их личных данных: Для создания правильных списков данных, с которыми эффективно можно работать, необходимо следовать нескольким правилам, а именно:

  • За каждым столбиком должна быть закреплена информация только одного типа. Например, в столбик с данными о днях рождениях вводится только такие данные, с именами сотрудников, только имена, и смешение типов данных недопустимы;
  • Информацию лучше всего делить по максимум. Например, ФИО стоить разделить на три разных поля, так как поиск и работа с данными будет легче (по имени можно поздравить в связи с праздником);
  • В обязательном порядке каждое поле должно иметь заголовок, несмотря на то, что с многоуровневыми «шапками» Excel не очень умело умеет работать;
  • В списке должны отсутствовать пустые строки и столбцы, так как это определяется программой как окончание созданного списка и в дальнейшем создаются проблемы и ошибки при отображении данных;
  • Размещение иных данных в стороне от списка не рекомендуются, так как в момент наложения любого из фильтров они будут скрыты.


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

При работе с объёмными таблицами любой пользователь сталкивается с проблемой, когда заголовки полей уходят за пределы окна и в связи с этим появляется неудобства пользования. Для избегания этого необходимо закрепить «шапку» нашей таблицы, что бы полоса прокрутки не влияла на отображения первых строк и столбцов ваших списков. Это можно осуществить в панели управления, вкладка «Вид», блок «Окно» и нажать выпадающий список «Закрепить область».

Вариантов закрепить область прокрутки всего три, это:

  1. Закрепить область – производится закрепление области слева и сверху от текущей ячейки, то есть по горизонтали и вертикали одновременно;
  2. Закрепить верхнюю строку – закрепление по горизонтали сверху установленной ячейки таблицы;
  3. Закрепить первый столбец – произвести вертикальное закрепление списков слева от установленной ячейки.

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

Отбор с помощью фильтра

Excel предоставляет возможность отфильтровать ваши списки по заданным критериям двумя вариантами, с помощью:

  1. Расширенного фильтра;
  2. Автофильтра.

Если вы будете использовать автофильтр, то данные, которые не соответствуют указанным условиям, будут спрятаны. В документе отражаться будут только отобранные по критериям записи в одном столбике.

Способностей расширенного фильтра гораздо больше, что позволит делать отбор записей по нескольким условиям и даже переносить их в другой диапазон рабочей книги.

Детально работу с фильтрами, я описал в статье «Автофильтр в Excel» с которой вы можете ознакомиться, перейдя по соответствующей ссылке.

Создаем промежуточные отчёты

Очень часто возникает необходимость группировать данные списков по определенным показателям с расчётами по ним итогов. Так создаются удобные и очень полезные в работе отчёты и анализы, прекрасный инструмент для любого бухгалтера и экономиста. Создать такой детализированный список данных в Excel с выделением групп и подбитием итогов по группам и общий по полю, не очень трудно. Всё это можно произвести в несколько шагов, но обязательным условием применения промежуточных итогов к спискам, это сортировка данных по полю для которого создается итог. Подробно и в деталях об этом можно узнать, прочитав статью «Промежуточные итоги в Excel», перейдя по ссылке.

Сортируем свои списки

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

Работаем со сводными таблицами

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

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

Для создания сводной таблицы необходимо установить курсор на любую ячейку таблицы или базы данных, и на панели управления во вкладке «Вставка» выбрать пункт «Сводная таблица». В диалоговом окне указываем, где размещены данные для анализа (по умолчанию будет указан диапазон таблицы, где стоит курсор) и куда нужно поместить результат. Следующим шагом в «Конструкторе сводной таблицы» вы можете из полей и записей вашей БД создать отчёт в таком виде, который вам нужен. При внесении изменений в базу данных, автоматических изменений в сводной таблице не происходит. Все изменения стают, доступны только при нажатии кнопки «Обновить данные», через контекстное меню или вкладка «Данные» и кнопка «Обновить всё».

Группируем элементы таблицы

Иногда для удобства навигации по вашей базе данных или для сворачивания некоторых элементов таблицы можно использовать инструменты «Группировка» и «Разгруппировать». Эта возможность позволит свернуть данные, которые в данный момент вам не интересны и отображать их не стоит. Очень полезный инструмент, когда возникает необходимость создать диапазон печати для некоторых данных.

А на этом у меня всё! Я очень надеюсь, что всё вышеизложенное о работе со списками данных в Excel вам пригодилось и было понятным. Буду очень благодарен за оставленные комментарии, так как это показатель читаемости и вдохновляет на написание новых статей! Делитесь с друзьями, прочитанным и ставьте лайк!

Организация списков и их обработка

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

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

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

Сортировка списков

Необходимость сортировки записей в списках возникает, обычно, для последующего быстрого поиска информации в списке. Существуют два способа сортировки: по возрастанию и по убыванию признака сортировки, которым является один из столбцов списка. Для простой сортировки строк следует активизировать любую ячейку внутри списка и щелкнуть по одному из значков (по возрастанию или по убыванию) на панели инструментов. Excel автоматически определяет границы списка и сортирует строки целиком. Если пользователь сомневается в правильности определения границ списка, то целесообразно выделить сортируемый диапазон и выполнить Данные/Сортировка . В окне «Сортировка диапазона» следует задать признак сортировки (заголовок столбца), а также как сортировать — по возрастанию или по убыванию.

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

В качестве примера рассмотрим таблицу с итогами сессии.

Отсортируем таблицу по двум признакам: первичный – группа (по возрастанию), вторичный – фамилия (по алфавиту). Для этого выделим диапазон B2:E17 и выполним Данные/Сортировка . Зададим настройки, как показано в окне «Сортировка диапазона» . В результате получим отсортированную таблицу.

Обратим внимание на следующие особенности сортировки:

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

Гораздо реже, чем сортировка по строкам, применяется сортировка по столбцам. Но она в Excel также возможна. В этом случае признаком сортировки является одна из строк списка, например, заголовок, или итоговая строка. Для выполнения сортировки необходимо в окне «Сортировка диапазона» нажать кнопку «Параметры» и установить переключатель «Сортировать столбцы диапазона».

Поиск записей

Для поиска записей следует обратиться к меню Правка/Найти , в поле «Что» диалогового окна «Найти» ввести образец поиска, а в поле «Область поиска» установить «значения» . После этого табличный курсор будет установлен на искомую ячейку. Если ячеек с искомым признаком несколько, то для продолжения нажать кнопку «Найти далее» . В начале поиска курсор должен быть установлен в начало списка. Допускается применение масок. Маска – это текстовый шаблон, составленный из обычных и специальных символов. В качестве специальных используются символы ? и *. Первый означает любой символ; второй – любой текст. Например, если для рассмотренного выше примера задать поиск информации по маске ?е*, то в таблице будут найдены фамилии Непошеваленко И., Дедикова Т. и Немчинов А.

Применение фильтров

Фильтр — это средство для отбора записей в таблице по некоторому критерию. В Excel имеются два типа фильтров: автофильтр и расширенный фильтр . Автофильтр показывает записи, совпадающие с критериями фильтрации, и скрывает не совпадающие. Расширенный фильтр способен сформировать новую таблицу из отфильтрованных записей.

Автофильтр

Для применения автофильтра необходимо выделить любую клетку внутри фильтруемой таблицы и обратиться к меню Данные/Фильтр. /Автофильтр . После обращения в заголовке таблицы должны появиться кнопки для раскрытия списков. Нажатие любой кнопки приводит к раскрытию списка элементов соответствующего столбца таблицы. Выбранный элемент является критерием фильтрации. Строки таблицы, в которых элементы столбца не совпадают с критерием будут скрыты, причем за совпавшими сохраняются их прежние порядковые номера. Выбор второго критерия в другом списке приведет к дополнительной фильтрации записей и т.д. В качестве примера рассмотрим применение автофильтра для таблицы с итогами сессии. На рисунке показаны результаты фильтрации по условию «Оценка по информатике»=5.

Обратите внимание, что записи, не отвечающие условию фильтрации скрыты. Поэтому нумерация строк идет не по порядку и выделена синим цветом.

Для задания более сложного условия фильтрации необходимо в соответствующем раскрывающемся списке выбрать «[Условие. ]» и сформулировать его в открывшемся окне «Пользовательский автофильтр». Окно содержит поля для ввода знаков логических отношений и метки логических операций И и ИЛИ. Например, для отбора записей, соответствующих студентам, получившим по информатике 4 или 5, следует выполнить настройки, как показано на рисунке.

Отменить результаты фильтрации можно через Данные/Фильтр. и убрать флажок с меню Автофильтр .

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

Расширенный фильтр

Для применения расширенного фильтра требуется предварительная подготовка, состоящая из двух этапов:

  • подготовки вспомогательной таблицы (диапазона) критериев;
  • планирования места для размещения результатов фильтрации.

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

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

В качестве примера рассмотрим условие фильтрации («Группа»=154 И «Оценка по информатике»>3) ИЛИ («Группа»=155 И «Оценка по информатике»>3).

Исходная таблица, блок критериев и новая таблица с результатами фильтрации показаны на рисунке.

В рассмотренном примере блок критериев расположен в диапазоне G1:H3.
Запуск расширенного фильтра выполняется через меню Данные/Фильтр. /Расширенный фильтр . В окне «Расширенный фильтр» следует задать настройки, как показано на рисунке.

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

Контрольные вопросы

Что называется списком в табличном процессоре Excel?

Как Excel определяет границы списка?

Что такое режим автозаполнения ячеек?

Для чего применяется сортировка списков?

В каких ситуациях применяется сортировка списков по нескольким признакам?

Список состоит из двух полей: фамилии студента и оценке по информатике. Какие из этих полей следует использовать как первичный и вторичный признаки сортировки? Обоснуйте ответ.

Как сделать так, чтобы при сортировке списка поле с порядковыми номерами записей осталось неотсортированным?

Что такое поиск информации в списке?

Что такое маска поиска? Как она записывается?

Что такое фильтр? Какие виды фильтров имеются в Excel?

Объясните принцип работы автофильтра.

Объясните принцип работы расширенного фильтра.

Чем расширенный фильтр отличается от автофильтра?

Каковы правила формирования блока критериев в расширенном фильтре?

Организация работы с персональными данными

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

Что такое персональные данные

Федеральный закон от 27.07.2006 N 152-ФЗ «О персональных данных» (далее — Закон N 152-ФЗ) определяет персональные данные как любую информацию, прямо или косвенно относящуюся к физическому лицу (субъекту персональных данных). Об этом сказано в п. 1 ст. 3 Закона N 152-ФЗ.

Согласно ч. 1 ст. 85 Трудового кодекса под персональными данными сотрудника понимают информацию, касающуюся конкретного работника, которая необходима работодателю в связи с трудовыми отношениями. Речь идет о таких данных, как:

  • фамилия, имя, отчество;
  • дата и место рождения;
  • пол;
  • адрес;
  • семейное положение;
  • должность (профессия);
  • зарплата, другие доходы;
  • владение недвижимым имуществом, денежные вклады и др.;
  • образование, квалификация, профессиональная подготовка, сведения о повышении квалификации;
  • привычки и увлечения, в том числе вредные (алкоголь, наркотики и др.);
  • факты биографии и предыдущая трудовая деятельность (место работы, размер заработка, судимость, служба в армии, работа на выборных должностях, на государственной службе и др.);
  • физиологические особенности, здоровье;
  • деловые и иные личные качества;
  • другие сведения.

Перечень кадровых документов, в которых содержатся персональные данные работников, приведен в табл. 1 на с. 76.

Таблица 1. Документы, в которых содержатся персональные данные работников

N Документ Сведения
1 Анкета, автобиография, личный
листок по учету кадров
(заполняется при приеме на
работу)
Анкетные и биографические данные
работника
2 Копия документа,
удостоверяющего личность
работника
Ф.И.О., дата рождения, адрес
регистрации, семейное положение,
состав семьи
3 Личная карточка (форма N Т-2,
утверждена Постановлением
Госкомстата России
от 05.01.2004 N 1)
Ф.И.О. работника, место его рождения,
состав семьи, образование, а также
данные документа, удостоверяющего
личность
4 Трудовая книжка Сведения о трудовом стаже, предыдущих
местах работы
5 Копии свидетельств о заключении
брака, рождении детей
Состав семьи, изменения в семейном
положении
6 Документы воинского учета Информация об отношении работника к
воинской обязанности, необходимая
работодателю для осуществления
воинского учета работников
7 Справка о доходах с предыдущего
места работы
Ф.И.О., данные о сумме дохода и
удержанного НДФЛ
8 Документы об образовании Подтверждают квалификацию работника,
обосновывают занятие определенной
должности
9 Документы обязательного
пенсионного страхования
Ф.И.О., личные данные
10 Трудовой договор Сведения о должности работника,
заработной плате, месте работы,
рабочем месте, а также иные
персональные данные работника
11 Приказы по личному составу Информация о приеме, переводе,
увольнении и иных событиях,
относящихся к трудовой деятельности
работника

Оператор по обработке персональных данных

Согласно Закону N 152-ФЗ лицо (юридическое или физическое), которое организует и (или) осуществляет обработку персональных данных, определяет их состав, цели обработки, действия, совершаемые с персональными данными, называют оператором (п. 2 ст. 3 Закона N 152-ФЗ). В нашем случае это работодатель.

Обработка персональных данных — любое совершаемое с ними действие. Операции по обработке персональных данных:

  • сбор;
  • запись;
  • систематизация;
  • накопление;
  • хранение;
  • уточнение (обновление, изменение);
  • извлечение;
  • использование;
  • передача (распространение, предоставление, доступ);
  • обезличивание;
  • блокирование;
  • удаление;
  • уничтожение персональных данных.

Положение о работе с персональными данными

Порядок выполнения обработки оператором персональных данных может быть установлен в Положении о работе с персональными данными сотрудников (далее — Положение). Унифицированной формы документа нет. Рассмотрим, как составить этот документ с учетом требований Закона N 152-ФЗ. Положение состоит из нескольких разделов. Они представлены в табл. 2. В ней же кратко указаны сведения, которые должны содержать разделы. Развернутая информация представлена во фрагменте Положения о персональных данных работников, которое приведено на с. 80.

Таблица 2. Структура Положения о персональных данных работников

N Обязанность Содержание раздела
1 Общие положения Цель принятия Положения
Вопросы, которые регулирует Положение
Ссылки на нормативные акты. Указывают, на
основании каких документов составляется
Положение.
В организациях, где работают государственные
гражданские служащие, дается ссылка на:
— Федеральный закон от 27.07.2004 N 79-ФЗ
«О государственной гражданской службе Российской
Федерации»;
— Указ Президента РФ от 30.05.2005 N 609 «Об
утверждении Положения о персональных данных
государственного гражданского служащего
Российской Федерации и ведении его личного
дела»;
— нормативные акты субъекта РФ
2 Основные понятия.
Состав персональных
данных работников
Основные понятия. Даются определения понятий
«персональные данные», «обработка персональных
данных», «использование персональных данных»,
указывается срок хранения документов и т.д.
Отдельно должно быть указано, что относится к
персональным данным в конкретной компании с
учетом ее особенностей (данные, используемые в
работе, например сведения о работе на режимных
объектах, об оформлении допуска к
государственной тайне, о соответствии здоровья
для профессий, связанных с тяжелыми и вредными
условиями, и т.д.)
Перечень документов организации, которые
содержат персональные данные
3 Получение
персональных данных
работников
Процедура получения персональных данных.
Указывается, что данные получают и обрабатывают
на основании письменного согласия работника.
Указываются случаи, когда согласие не нужно
4 Использование
персональных данных
Цели использования личной информации сотрудников
5 Обработка
персональных данных
Условия, соблюдаемые при обработке персональных
данных работника
6 Передача
персональных данных
(доступ к
персональным данным)
Порядок передачи персональных данных внутри
организации (внутренний доступ), сторонним лицам
и государственным органам (внешний доступ)
7 Ответственность за
нарушение норм,
регулирующих
обработку и защиту
персональных данных
Указывают тех, кто несет ответственность за
нарушение правил хранения и использования
персональных данных

Фрагмент Положения о персональных данных работников

Введение Положения в действие

Положение о персональных данных утверждается руководителем компании и вводится в действие приказом по организации (образец приведен на с. 90). Запись об утверждении Положения нужно сделать в журнале регистрации локальных нормативных актов.

Образец приказа

Если есть профсоюз

Если в компании есть профсоюз, с ним нужно согласовать Положение. Для этого проект положения направляют в выборный орган профсоюза (ст. 372 ТК РФ). Тот должен выразить свое мнение (в письменной форме) не позднее пяти рабочих дней со дня получения проекта. Если профсоюз не согласен с проектом или имеет предложения по его совершенствованию, у администрации есть два выхода. Первый — согласиться. Второй — в течение трех дней после получения мотивированного мнения провести дополнительные консультации с профсоюзом в целях достижения взаимоприемлемого решения. Если и это не поможет, следует оформить протокол разногласий. После этого администрация имеет право принять Положение без учета требований профсоюза. Однако тот сможет обжаловать Положение или начать процедуру коллективного трудового спора в порядке, предусмотренном гл. 61 Трудового кодекса.

Ознакомление работников с Положением

Работники должны быть ознакомлены с Положением под роспись (п. 8 ст. 86 ТК РФ). Данный факт может фиксироваться:

  • в тексте трудового договора каждого работника (перечисление локальных нормативных актов, с которыми работник ознакомлен до подписания договора);
  • — листе ознакомления с Положением (образец на с. 91);
  • — журнале ознакомления работников с локальными нормативными актами (образец на с. 91).

Образец листа ознакомления с локальными нормативными актами

N
п/п
Наименование локального нормативного акта Дата Подпись
1 Правила внутреннего трудового распорядка
ООО «Черный лес»
03.10.2011 Евстахов
2 Положение об оплате труда, премировании и
социальном обеспечении сотрудников ООО «Черный
лес»
03.10.2011 Евстахов
3 Инструкция по информационной безопасности,
утвержденная Приказом от 15.06.2008 N 1
03.10.2011 Евстахов
4 Положение о персональных данных 03.10.2011 Евстахов
5 Положение о материальной ответственности
работников за ущерб, причиненный ООО «Черный лес»
03.10.2011 Евстахов

Фрагмент журнала ознакомления с Положением о персональных данных

N
п/п
Ф.И.О. работника Дата
ознакомления
Подпись
1 Алексеева Диана Николаевна 15.08.2011 Алексеева
2 . . .
6 Евстахов Сергей Сергеевич 03.10.2011 Евстахов
7 . . .
8 . . .
9 . . .

Примечание. Срок хранения персональных данных

Локальные нормативные акты (положения, инструкции) о персональных данных должны храниться постоянно. Что касается заявлений работников о согласии на обработку данных (о них будет рассказано в следующих номерах), других документов работника, то они хранятся 75 лет. Об этом говорится в Перечне, утвержденном Приказом Минкультуры России от 25.08.2010 N 558.

Административная ответственность

Меры административной ответственности (в основном предусмотрены штрафы, дисквалификация в данном случае не применяется) для предприятия и его должностных лиц за нарушение порядка получения, обработки, хранения и защиты персональных данных сотрудников приведены в табл. 3.

Таблица 3. Ответственность за нарушение порядка получения, обработки, хранения и защиты персональных данных сотрудников

Нарушение Ответственность Норма
законодательства
Нарушение установленного законом
порядка сбора, хранения,
использования или распространения
информации о гражданах
(персональных данных)
Для должностных лиц:
от 500 до 1000 руб.;
для юридических лиц:
от 5000 до 10 000
руб.
Статья 13.11
КоАП РФ
Разглашение информации, доступ к
которой ограничен (персональных
данных), лицом, получившим к ней
доступ в связи с исполнением
служебных или профессиональных
обязанностей
Для должностных лиц:
от 4000 до 5000 руб.
Статья 13.14
КоАП РФ

Ответственный за организацию работы с персональными данными работников

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

Образец приказа

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

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

  • начальника отдела кадров;
  • (старшего) инспектора по кадрам;
  • директора по персоналу;
  • заместителя начальника отдела (директора по персоналу);
  • специалиста по работе с персоналом.

Может быть введена и новая должность.

Автор: А.Ю.Тьевар, старший научный редактор журнала «Зарплата»

Списки: основные виды и способы реализации

Список представляет собой множество, между элементами которого установлено отношение «предыдущий-следующий». Можно сказать, что линейный список – это последовательность однотипных элементов, т.е. множество элементов, для которого установлен линейный порядок следования элементов друг за другом. Каждый элемент списка представляется записью, состоящей из двух полей. В первом поле размещается сам элемент, а во втором – указатель на следующую запись. Указатель – это переменная, значениями которой являются адреса памяти. Для последнего в списке элемента во втором поле помещают указатель с «пустым» значением Nil (тупик).

Для обозначения линейных списков обычно используют рисунки.

Для работы с линейными списками достаточно знать указатель на первый элемент списка. Линейные списки бывают следующих видов:

· дважды связанные (симметрические),

· циклические дважды связанные.

К специальным видам линейных списков относятся стеки и очереди. Это динамические структуры данных, которые часто используют в программировании для определения порядка выполнения подзадач. Стек – это линейный список, в котором все включения и исключения производятся на одном конце списка, называемом вершиной стека («последним пришел – первым ушел»). Очередь – это линейный список, в котором все включения производятся на одном конце списка (в конце очереди), а все исключения – на другом его конце (в начале очереди) («первым пришел – первым ушел»).

К основным операциям над линейными спискамиотносятся:

· Подсчет узлов (элементов) списка;

· Конкатенация (соединение) списков;

· Поиск минимального (максимального) элемента, суммы, произведения;

· Изменение чисел в списке;

· Исключение (включение) узла;

· Упорядочение узлов и др.

К основным способам реализации операций над линейными списками относятся:

В языке Pascal для работы со списками используют данные типа record (запись), типизированные и нетипизированные указатели, адресный оператор @, символ ^, который помещают после имени указателя и процедуры New и Dispose, соответственно выделяющую память под динамически размещаемую переменную и освобождающую память.

Вопросы для экзамена по курсу «Технология программирования»

Вопросы для экзамена по курсу «Технология программирования»

1. Технология программирования и основные этапы ее развития

2. Технологии COM, OLE-automation, ActiveX, CORBA, CASE. Проблемы разработки сложных программных систем (ПС)

3. Блочно-иерархический подход к созданию сложных систем (СС)

4. Жизненный цикл и этапы разработки программного обеспечения

5. Оценка качества процессов создания программного обеспечения

6. Понятие технологичности программного обеспечения

7. Два способа декомпозиции ПО. Модули и их свойства. Сцепление модулей

8. Модули и их свойства. Связность модулей. Библиотеки ресурсов

9. Основные понятия программирования. Этапы решения задачи на компьютере

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

11. Описание алгоритмов с помощью псевдокодов, Flow-форм, диаграмм Насси-Шнейдермана

12. Стиль оформления программы. Правила оформления модулей.

13. Введение в Pascal . Главное окно и главное меню IDE Delphi

14. Технология работы с консольными приложениями

15. Основные понятия языка Pascal. Структура программы. Операторы ввода-вывода данных

16. Типы данных. Простые типы данных

17. Типы данных. Стандартные типы данных

18. Типы данных. Пользовательские типы данных

19. Структурированные типы данных (строки, массивы, множества)

20. Структурированные типы данных (записи, файлы). Работа с текстовыми файлами

21. Другие типы данных (указатели, процедурные типы, вариантные типы)

22. Выражения, операнды, операции

23. Простые операторы

24. Структурные операторы (составной, условный, выбора)

25. Структурные операторы (цикла, доступа). Работа с массивами

27. Рекурсивные подпрограммы. Параметры и аргументы

28. Стандартные процедуры и функции

29. Модули в Pascal

30. Списки: основные виды и способы реализации

31. Жизненный цикл программы (каскадная модель, модель создания прототипов, спиральная модель)

32. Постановка задачи, оценка осуществимости

33. Планирование, управление

34. Тестирование, обеспечение качества

35. Психология программирования, организация коллектива разработчиков

37. Сопровождение, реинжиниринг

38. Управление качеством

39. Стандарты ISO

40. Стандарт CMM

42. Технология программирования встроенных систем реального времени

43. Технология CUDA

Для заочников обязательными являются лекции 1, 5 – 15 (вопросы по материалу этих лекций включены в экзаменационные билеты). В лекциях 8 – 15 излагаются принципы работы с интегрированной средой Turbo Delphi, технология работы с консольными приложениями и основы языка программирования Delphi (Pascal).

Организация списков с помощью указателей и структур

Доброго времени суток.
Имеется три программы, времени очень мало, нужно разобраться что да как работает, очень прошу просто написать что эта функция делает, что это за переменная и тд.
Кто что сможет, прошу
Может эти программы пригодятся кому-нибудь к тому же

3. Организация списков с помощью указателей и структур:
Заменить на заданный идентификатор значение
а) k-го по порядку элемента списка;
б) предпоследнего элемента списка;
в) последнего элемента списка.

26.06.2015, 17:53

Организация списков путём применения указателей и структур
Помогите, пожалуйста! Есть программа, в программе у меня допущены ошибки, как поправить, непонятно.

Массив указателей на заголовки списков
Добрый день нужно реализовать подобный класс Список у меня реализован следующим образом: .

Массив указателей списков смежных вершин
Добрый день. Помогите пожалуйста в реализации списка смежности для графа. Знаю, в инете много.

Шаблон структуры данных — массив указателей на заголовки списков
Мне выдали задание на курсовую работу: «Шаблон структуры данных — массив указателей на заголовки.

Применение указателей, структур и объединений
Здравствуйте, люди добрые!! (^_^)/ Очень нуждаюсь в вашей помощи. Помогите разобраться.

26.06.2015, 17:53

Разбор указателей и структур — каковы их суть и назначение
Доброго времени суток форумчане. В университете мы изучаем C++ по учебнику Павловской и Щупака.

Организация контейнера для структур
Доброго времени суток! Решая задачу по реализации контейнера столкнулся с проблемой выделения.

Алгоритмы и программы по использованию указателей и динамических структур данных
Здравствуйте! Прошу Вас помочь мне в написании задачи на С++. Вот текст: Дан указатель P1 на.

Илон Маск рекомендует:  Что такое код create table
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL