СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ

430а (гл.корпус),
406 (нов.корпус)

???

посещения лекций (проверка!)
Проверка домашних заданий (оценка)
Защита лабораторных работ (оценка)
Защита курсового

проекта (оценка)
Экзамен (оценка)
Конспект лекций (конкурс!)

работы: оценки 3, 4, 5, 5+

баллы 3, 5, 7, 10
пропуск (-5)
Домашние задания: оценки 3, 4, 5, 5+
баллы 1, 3, 5, 7

Автомат: ≥80% от max, все лабораторные ≥4, ДЗ ≥4, контрольные сроки ≥ 1
Собеседование (полуавтомат):
от 60% до 80% от max, все лабораторные ≥3, ДЗ ≥3, контрольные сроки ≥ 0
Экзамен по билетам: <60% от max с предварительной отработкой лабораторных работ

на лабы
Сортировки
Lab1.doc Lab2.doc
…

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

в процессе работы программы, при этом изменяется объём выделенной памяти.

различаются количеством байт, отведённых в памяти и наличием знака. (int,

short, long)
Вещественные типы характеризуются точностью представления числа. (double, float, long double)

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

всех возможных значений.

Логический тип - частный случай перечислимого типа с

двумя возможными значениями ИСТИНА и ЛОЖЬ.

разного типа.

Массивы – структура данных, которая представляет собой фиксированное

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

скалярный.

Массив – это структура данных со случайным (прямым) доступом.

времени доступен любой элемент.
Последовательный доступ – (к+1)-й элемент может быть

получен только путем просмотра предыдущих к элементов.

могут быть разных типов.
Пример. Struct data { char day;

char month;
int year; }
zap[n]; - массив записей.
Поле записи может являться записью, тогда образуются вложенные записи.

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

данные только одного типа.
Пример. Union w
{ int a;
char b [2]; }

int


char char

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

ветвления и повтора.

ELSE

FI
IF (условие1)

<действие1>
ELSE IF (условие2) <действие2>
FI
FI

Цикл с постусловием

DO

OD (условие)

n )

OD

4. Бесконечный цикл

DO

<действия>
…
IF (условие) OD FI
…
OD

Присваивание :=
Обмен значений

курсе

Сортировка – фундаментальная деятельность, без которой не обходится ни одна

обработка реальных данных.

2) На примере сортировки удобно
рассматривать множество алгоритмов,
сравнивать и анализировать их.

…, аn }.
Для всех его элементов определены операции

отношения: меньше, больше, равно (<, >, =).
Необходимо отсортировать массив, т.е.
переставить элементы массива А таким образом,
что выполняется одно из следующих неравенств:
a1 ≤ а2 ≤ а3 ≤ … ≤ аn (1)
a1 ≥ a2 ≥ a3 ≥ ... ≥ an (2)

Если выполняется неравенство (1), то массив отсортирован по возрастанию или в прямом порядке.
Если выполняется неравенство (2), то массив отсортирован по убыванию или в обратном порядке.

массиве.

5 6 8 1 3

5 5 4 2 7 6

5 неубывающих послед-тей => 5 серий

Массив, отсортированный по возрастанию, состоит из одной серии,
а в массиве, отсортированном по убыванию, количество серий равно количеству элементов в массиве (если все элементы различны).

состоит из:
Фамилии; Имени; Телефона; Адреса.
Чтобы его отсортировать, нужно определить

отношения порядка (<,>,=).
Например, пусть при сравнении двух элементов меньше тот, чья фамилия идет раньше по алфавиту.
Если фамилии совпадают, то меньше элемент, у которого имя раньше по алфавиту.
Если фамилии и имена совпадают, то будем считать, что элементы равны.

порядка (,=).
Определение. Та часть информации, которая учитывается при определении

отношения порядка, называется ключом сортировки.
В данном примере ключ сортировки: фамилия и имя - составной ключ из двух полей (фамилия – старшая часть ключа, имя – младшая часть ключа).
Ключ поиска обычно
-равен ключу сортировки или
-состоит из его старшей части.

от исходной упорядоченности массива.

массиве не меняется относительный порядок элементов с одинаковыми ключами.
Пример:
1

2 5’ 6 3 4 5”
Итог сортировки:
1 2 3 4 5’ 5” 6 - устойчивая сортировка
1 2 3 4 5” 5’ 6 - неустойчивая сортировка
В общем случае устойчивая сортировка лучше, чем неустойчивая. В частности, когда данные уже были ранее упорядочены по другим ключам.

сортировки в зависимости от исходных данных.
Но все же…
Главным качественным

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

(“Compare”);
2. Перестановки элементов – M (“Move”).

Мы будем оценивать трудоемкость количеством

операций сравнения и перестановки:
С + M = T

C и M зависят от количества элементов в массиве:
C(n) + M(n) = T(n),

где C(n), M(n), T(n) – функции от количества элементов массива.

элементы массива.
Предварительно обнулить счетчики C=0; M=0;
При подсчете количества сравнений счетчик

желательно ставить перед условным оператором.
Пример: С++; if (ai < x) …
При подсчете количества пересылок счетчик ставится до или после оператора присваивания:
Пример: ai=x; M++;

от 1 до n: А = { а1 , а2

, …, аn }.

Для удобства реализации алгоритмов на языке C++, массив возможно описывать следующим образом:
int A [ 1+n ];

Тогда при заполнении, обработке и выводе массива элемент А[0] не используется.
A[0] A[1] A[2] ... A[n]