Информационные технологии и основы программирования

1.

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И ОСНОВЫ ПРОГРАММИРОВАНИЯ
2 семестр
Лекции
Практические работы
Экзамен
Курсовой проект
18 часов (одно занятие в 2 недели)
54 часа (три занятия в 2 недели)
с 6 по 15 недели
оценка в диплом
оценка в диплом
Темы лекций
1. Структуры данных . Виды списков
2. Линейные списки
3. Линейные списки с ограниченными возможностями: Стеки, очереди, деки
4. Иерархические списки: Деревья
5. Нелинейные списки: Сети
6. Списки с элементами сложной структуры: Таблицы
Темы практических работ
(сроки выполнения)
1. Линейные списки
( 1-5 недели)
2. Стеки, очереди, деки
(6-8 недели)
3. Деревья
(9-12 недели)
4. Создание таблиц
(13-15 недели)
5. Алгоритмы сортировки таблиц (16-18 недели)
Баллы за практическую работу max/min: 4/2 (программа) + 4/2 (отчет) + 4/2 (защита) = 12/6
Баллы за курсовой проект max/min:
100/50 баллов
1

2.

Лекция 1 по ИТиОП 2 семестр
« СТРУКТУРЫ ДАННЫХ. ВИДЫ СПИСКОВ »
2

3.

Понятие структуры данных
Решая задачи различных типов, программист сталкивается с большим
разнообразием данных и необходимостью организации их представления в форме
наиболее полно соответствующей понятиям и объектам предметной области.
Такие способы организации данных обычно отсутствуют в языках программирования.
Программист вынужден сам конструировать эти способы, определяя одновременно
- структуру значения ( - размер оперативной памяти,
- представление значения в оперативной памяти,
- множество допустимых значений)
- набор операций удобный для обработки этих данных (набор операций определяется
как набор подпрограмм).
Абстрактными типами данных или пользовательскими типами называют
способы организации данных, ориентированные на представление объектов
и понятий предметной области решаемой задачи.
Структура данных это организованная информация, которая может быть описана,
создана и обработана программой.
Структура данных (как и структуры управления
фундаментальной компонентой программирования.
вычислениями)
является
3

4.

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

5.

Связное и несвязное представление данных
Данные динамической структуры могут иметь связное и несвязное представление в оперативной
памяти.
Несвязное (последовательное, линейное) представление возможно как в статической, так и в
динамической памяти с использованием массива. При отображении динамической структуры данных
в статической памяти приходится вносить ограничение на размер данных (максимальное число
элементов в значении структуры) и обеспечивать возможность изменения фактической размерности в
процессе выполнения программы.
• Преимущество: прямое обращение к элементу.
• Недостаток: сложно менять порядок элементов, удалять и добавлять элементы.
Связное представление возможно только в динамической памяти. При отображении динамических
данных в динамической памяти динамическая структура данных характеризуется еще и тем что:
- ей выделяется память в процессе выполнения программы;
- при связном представлении она не имеет имени.
- при связном представлении динамической структуре данных ставится в соответствие статическая
переменная типа указатель посредством которой осуществляется доступ к динамической
структуре. Значение этого указателя - адрес первого элемента структуры данных, первый элемент
хранит адрес другого элемента и т.д.
• Преимущество: легко менять порядок элементов, удалять и добавлять элементы.
• Недостаток: последовательное обращение к элементу.
5

6.

Одно- и двусвязное представление данных
Связное представление бывает односвязным или двусвязным (другое название:
однонаправленным или двунаправленным).
При односвязном (однонаправленном) представлении списка каждый элемент списка
хранит адрес следующего элемента списка.
• Преимущества: требует меньше объем памяти, проще удалять и добавлять элементы.
• Недостаток: перемещение по списку только в одном направлении.
При двусвязном (двунаправленном) представлении списка каждый элемент списка хранит
адреса предыдущего и следующего элементов списка.
• Преимущество: перемещение по списку в двух направлениях.
• Недостатки требует больше объем памяти, сложнее удалять и добавлять элементы.
6

7.

Виды списков
Список – это конечное (возможно пустое) множество данных, имеющих некоторый общий смысл
для решаемой задачи, размерность множества может быть заранее неизвестна.
Виды списков:
ЛИНЕЙНЫЙ
ИЕРАРХИЧЕСКИЙ ( ДЕРЕВО )
СЕТЬ
В ЛИНЕЙНОМ списке у каждого элемента есть один предыдущий и один следующий элемент (это
справедливо для всех элементов кроме первого и последнего. У первого элемента нет
предыдущего, у последнего нет последующего элемента).
В нелинейном списке типа ДЕРЕВО у каждого элемента есть один предыдущий и m>=0 следующих
элементов (это справедливо для всех элементов кроме первого. У первого элемента нет
предыдущего элемента).
В нелинейном списке типа СЕТЬ у каждого элемента есть n>=0 предыдущих и m>=0 следующих
элементов.
7

8.

Линейный список
Линейный список – это множество, состоящее из n (n ≥ 0) элементов (x1, x2,…, xn), структурные свойства
которого, ограничиваются линейным относительным положением элементов, т.е. если n > 0, то есть элемент
который является первым x1, есть элемент последний xn, тогда xk элемент следующий за xk-1, а за xk следует
xk+1 для всех 1<k<n.
Рекурсивное определение линейного списка:
<cписок> = <пустой список> │<непустой список>
<непустой список> = <элемент из множества объектов>
<непустой список> = <непустой список> <элемент из множества объектов>
В статической памяти несвязный список можно представить как множество данных, которые располагаются
в списке последовательно и непрерывно друг за другом (массив) и это множество дополнено
информацией, которая позволяет вносить изменения в динамическую структуру данных.
Будем называть такой список (условно) – статический список. На языке Си++ статический список можно
представить структурой:
struct list
{ int n;
type elem [ k ]; };
где n определяет фактическое количество элементов в списке, ( если n = 0, то список пуст;
если n = k , то список полон) ;
elem (в данном случае массив) определяет само множество элементов списка,
type – тип элемента списка,
k– константа задающая максимально возможное количество элементов списка.
8

9.

Динамический линейный односвязный список
В динамической памяти список можно представить как множество данных, расположенных в памяти
произвольно (в процессе их создания) и связанных между собой указателями. Будем называть такой
список (условно) – динамический список.
Линейный односвязный список – это динамический список, каждый элемент которого состоит минимум
из двух полей. Одно (или более) поле содержит информацию (или ссылку на нее), другое поле
содержит ссылку на следующий элемент списка. Элемент списка называют «звено» списка. Таким
образом, список – это цепочка связанных между собой звеньев от первого до последнего. По
однонаправленному списку можно двигаться только в одном направлении – от первого (или
заглавного) звена к последнему.
Ациклическим называется динамический список, у которого последнее звено в ссылочном поле хранит
значение NULL - пустой указатель.
Циклическим называется динамический список, у которого последнее звено в ссылочном поле хранит
адрес первого звена списка.
Пример 1 последовательность символов “BETA” представлена в виде ациклического списка.
Информационные поля
хранят по одному символу. Ссылочные поля поля
хранят адрес
следующего звена. Последнее звено в поле ссылки имеет значение NULL (Ø)
В
Е
Т
А Ø
Пример 2 последовательность символов “BETA” представлена в виде циклического списка, в котором
последнее звено в поле ссылки хранит адрес первого звена.
В
Е
Т
А
9

10.

Список может иметь имеет заглавное (фиктивное ) звено, которое хранит адрес первого элемента
списка. Информационное поле заглавного звена, как правило, не используется. Заглавное звено
позволяет обрабатывать первое звено списка также как и другие его звенья, так как у первого звена
появился предшествующий элемент.
Пример 3 последовательность символов “BETA” представлена в виде ациклического списка с
заглавным звеном
В
Е
Т
А Ø
Пример 4 пустые списки с заглавным звеном ациклический
Ø
и циклический
Чтобы задать динамический список надо описать тип его звена (элемента). Так как звено состоит из
полей разных типов, то описать его можно неоднородным типом struct . Задание типа элемента
списка:
struct list
{ type elem ;
list *next ;
};
// list – имя типа структуры
// type – тип информационного поля, elem - имя информационного поля
// next – имя ссылочного поля, указатель на структуру типа list
Для примеров 1-4 элемент списка может быть определен: struct
list {char info ; list *next ;};
10

11.

Обращение к элементам списка
Чтобы работать со списком как с единым объектом, надо ввести в употребление статическую переменнуюуказатель, значение которой – это адрес первого (или заглавного) звена списка. Если список пустой, она
должна иметь значение NULL.
Для списка с элементами типа struct list {char elem; list *next ;} определение статической переменнойуказатель:
list *headlist ;
Создание пустого списка без фиктивного звена: headlist = NULL;
Создание пустого ациклического списка c фиктивным звеном: headlist = new list; headlist->next = NULL;
Создание пустого циклического списка c фиктивным звеном: headlist = new list; headlist->next = headlist;
headlist
В
Е
Т
А Ø
Используя указатель, можно обращаться к элементам списка:
headlist . . .
//указатель на заглавное звено списка
headlist - > next . . .
//указатель на первое звено списка (с символом ‘B’)
headlist - > next - > next . . .
//указатель на второе звено списка (с символом ‘E’)
headlist - > next - > elem . . .
//обращение к информационному полю первого элемента списка
Для более удобной работы со списком лучше ввести еще один указатель, который ссылается на текущий
элемент списка.
list *p; p = headlist ;
// установили указатель р на заглавное звено списка
for ( int i = 0 ; i < 4 ; i ++) p = p -> next ; //переместили указатель р на четвертый элемент списка
p
p -> next = headlist ;
// получили циклический список
11

12.

Пример создания списка и перемещения по списку
Пример 5. Дано предложение, заканчивающееся точкой. Посчитать количество слов в предложении.
// СОЗДАНИЕ ЛИНЕЙНОГО ОДНОСВЯЗНОГО АЦИКЛИЧЕСКОГО СПИСКА С ЗАГЛАВНЫМ ЗВЕНОМ
struct list { char elem; list *next ;} ;
//описали тип элемента списка
list *headlist, *p;
// указатели на заглавное звено headlist и текущее звено списка р
char ch ;
p = headlist = new list ; // создали заглавное звено списка; p и headlist ссылаются на заглавное звено
scanf_s(“%c”, & ch, 1) ;
// прочитали первый символ в ch
while ( ch != ‘.’ )
// пока не прочитали точку
{
p -> next = new list ;
// создали новое звено списка, его адрес записали в p -> next
p = p -> next;
// р перевели на новое звено
p -> elem = ch;
// в новое звено записали прочитанный символ
scanf_s(“%c”, & ch, 1) ; // прочитали следующий символ в ch
}
p -> next = NULL;
// в ссылочное поле последнего звена записали признак конца списка
// ПОДСЧЕТ КОЛИЧЕСТВА ПРОБЕЛОВ В СПИСКЕ
int kol_slov ;
// переменная для хранения количества слов в предложении
p = headlist -> next ;
// установили указатель р на первое звено (после заглавного)
kol_slov = ( p == NULL) ;
// если хотя бы одно слово в предложении есть, kol_slov = 1
// если список пустой, kol_slov = 0
while ( р != NULL )
// пока не прошли все звенья списка
{
kol_slov += (p -> elem == ‘ ‘) ;
// если встретили пробел, увеличили kol_slov на 1
p = p -> next ;
//переместили указатель р на следующий элемент списка
}
12

13.

Основными операциями обработки списка являются:
1) поиск заданного элемента по его значению или порядковому номеру;
операция заканчивается, когда элемент найден или просмотрен весь список (если
элемента нет); результат операции должен определять, есть ли элемент в списке или
нет и, если есть, то возможно его адрес или значение;
Примеры операции поиск элемента в линейном односвязном ациклическом списке:
struct list
{ list *next ;
int el ; } ;
- поиск по значению
list * find1 (list *p, int x)
{
while (p != NULL && p ->el != x)
p = p -> next;
return p;
}
- поиск по значению - рекурсивная реализация операции
list * find2 (list *p, int x)
{
if (p == NULL) return NULL;
if (p->el == x) return p;
return find2( p->next , x);
}
13

14.

2) включение (вставка) в список нового элемента перед или после заданного элемента (в том числе перед первым
элементом или после последнего);
Включению, как правило, предшествует поиск элемента после и/или перед которым происходит включение.
При включении элемента перед первым в список без заглавного звена меняется заголовок списка.
При включении после некоторого элемента меняется ссылочное поле у элемента, после которого происходит
включение, поэтому надо определять ссылку на элемент после которого происходит включение.
Примеры операции включение элемента в линейный односвязный ациклический список:
struct list { list *next ; int el ; }
- включение элемента в начало списка (без заглавного звена)
void insert1 (list *& p, int x)
{list *r;
r = new list; r->el=x; r->next= p;
p=r;
}
// р – адрес первого элемента списка
- включение элемента в конец списка без заглавного звена
list* insert2 (list *p, int x)
{list *r;
r = new list; r -> el=x; r -> next = NULL;
//создать новое звено
if (!p) p = r;
// если список был пустой, новый элемент- это весь список
else {while (p -> next) p = p -> next; // иначе увести р на последнее звено списка
p -> next = r;
//присоединить новое звено к последнему звену списка
}
return p; }
- включение элемента x после элемента с адресом р
void insert3 (list *p, int x)
{list *r; r = new list; r -> el = x; r -> next = p -> next ; p -> next = r; }
14

15.

3) исключение (удаление) заданного элемента из списка (в том числе удаление первого элемента или последнего);
Исключению, как правило, предшествует поиск, исключаемого элемента. Результатом поиска должна быть ссылка на
элемент предшествующий исключаемому, так как при удалении элемента из списка меняется ссылочное поле у
элемента, предшествующего удаляемому.
При удалении первого элемента в списке без заглавного звена меняется адрес списка.
Примеры операции исключение элемента из односвязного ациклического списка: struct list { list *next ;
int el ; }
- удаление по значению из списка без заглавного звена
int del1 (list *&p, int x) // р передается по ссылке, т.к. при удалении первого элемента адрес начала списка изменится
{ list *r,*t;
if (p) if (p->el ==x) { r = p; p = p -> next; delete r; return 1; }
// удаление первого элемента списка, меняется р
else { t = p;
// t – указатель для поиска элемента
while ( t->next != NULL && t->next->el != x) t = t->next ; // поиск элемента, t – адрес предыдущего элемента
if ( t->next ){ r = t->next; t->next = r->next; delete r; return 1; } //если нашли , удаление элемента после t
else return 0;
// не нашли элемент
}
else return 0;
//список был пустой
}
-
удаление по значению из списка с заглавным звеном
int del2 (list *p, int x)
// параметр р передается по значению, т.к. адрес начала списка не изменится
{ list *r ;
while ( p->next != NULL && p-> next -> el != x ) p = p->next ;
// поиск элемента, р – адрес
предыдущего элемента
if (p->next) { r = p->next ; p->next = r->next ; delete r; return 1; } //если нашли элемент, удаление элемента
после р
else return 0;
// не нашли элемент
}
15

16.

Другие операции над списком:
• определение числа звеньев списка;
• копирование списка;
• объединение списков;
• сравнение списков;
• упорядочение элементов списка по значению информационного поля и т.д.
16

17.

Линейный двунаправленный ( двусвязный ) список
Динамический список, в котором каждый элемент (кроме возможно первого и последнего)
связан с предыдущим и следующим за ним элементами называется двусвязным.
Каждый элемент такого списка имеет два поля с указателями (одно поле содержит ссылку
на следующий элемент, другое поле – ссылку на предыдущий) и третье поле информационное (возможно несколько информационных полей). Наличие ссылок на
следующее звено и на предыдущее позволяет двигаться по списку от каждого звена в
любом направлении: от звена к концу списка или от звена к началу списка, поэтому
такой список называют еще и двунаправленным.
Пример 6 Последовательность символов BETA представлена двусвязным ациклическим
списком без заглавного звена
headlist2
B Ø
E
T
А
Ø
Описание типа звена двусвязного списка:
struct
list2 { type elem ;
list2 * next, * pred ;
};
list2 * headlist2 ;
//информационное поле
//ссылочные поля
//указатель на начало списка
17

18.

Операции с двусвязным списком
Переменная-указатель headlist2 задает список как единый программный объект, ее значение указатель на первый (или заглавный ) элемент списка.
Создание пустого списка без фиктивного звена:
headlist2 = NULL;
Создание пустого ациклического списка c фиктивным звеном:
headlist 2 = new list2; headlist2 -> pred = headlist2 -> next = NULL;
Создание пустого циклического списка c фиктивным звеном:
headlist2 = new list2; headlist2 -> pred = headlist2 -> next = headlist2;
Основные операции, выполняемые над двусвязным списком, те же, что и для односвязного списка.
Так как двусвязный список более гибкий, чем односвязный, то:
При включении элемента в список, можно использовать указатель как на элемент, за которым
происходит включение, так и указатель на элемент перед которым происходит включение.
При исключении элемента из списка можно использовать как указатель на сам исключаемый элемент,
так и указатель на элемент предшествующий или следующий за исключаемым.
Но так как элемент двусвязного списка имеет два указателя, то при выполнении операций
включения/исключения элемента надо изменять больше связей, чем в односвязном списке.
Поиск элемента в двусвязном списке можно вести:
а) просматривая элементы от начала к концу списка,
б) просматривая элементы от конца списка к началу,
в) просматривая список в обоих направлениях одновременно: от начала к середине списка и от конца
к середине (учитывая, что элементов в списке может быть четное или нечетное количество).
18

19.

Примеры работы с двусвязным списком
• Просмотр циклического (возможно пустого) списка без заглавного звена в направлении от
начала к концу списка
void exam1( list2 *p)
{ list2 *ph;
if ( p == NULL ) return; // список пуст
ph = p;
do { . . .
//действия ради который происходит просмотр,
//например, печать элементов
p = p -> next; }
while ( p != ph ); }
// просмотр пока текущий указатель p
// не равен указателю на начало списка ph
• Просмотр кольцевого (возможно пустого) списка с заглавным звеном в направлении от конца
списка к началу
void exam2( list2 *p)
{ list2 *pr;
if ( p –> next = = p ) return;
// список пустой
pr = p -> pred;
// текущий указатель pr получил адрес на последний элемент списка
while (pr != p) //просмотр пока текущий указатель pr не равен указателю на заглавное звено p
{ . . . pr = pr -> pred; }
•. . . Включение нового элемента (в список с заглавным звеном) перед элементом, на который
ссылается p
x = new list2;
x -> pred = p -> pred;
x -> next = p;
p -> pred -> next = x;
p -> pred = x;
...
•Исключение из списка с заглавным звеном элемента, на который ссылается указатель p
p -> pred -> next = p -> next;
p -> next -> pred = p -> pred;
delete p;
// р стал неопределен, можно потерять место в списке
19

20.

Пример 7 операции поиск по значению в линейном двусвязном кольцевом списке без заглавного
звена от начала списка (указатель р) и от конца списка (указатель t) к середине списка
(список не пустой!) :
struct list2
{ int elem ;
list2 * next, * pred ;
} ;
list2 * find3 ( list2 *p, int x) // р – указатель на первый элемент списка, х – искомое значение
{ list2 *t; t = p->pred;
// t – указатель на последний элемент списка /
while ( p != t && p->pred ! = t && p->elem != x && t->elem != x)
{ p = p->next; t = t->pred; }
if ( p = = t )
// если нечетное количество элементов в списке
if (p-> elem = = x) return p; //если центральный элемент равен х
else return NULL;
// элемент не найден
else
if (p->pred = = t) return NULL;
// элемент не найден
else
if ( p->elem != x ) return p; //элемент найден от начала списка
else return t;
//элемент найден от конца списка
}
20