ProPowerPoint.Ru Алгоритмизация и программирование Структуры данных 10 класс по учебнику Калинина И.А. и Самылкиной Н.Н.

ProPowerPoint.Ru Структуры данных Списки Деревья

ProPowerPoint.Ru Основные элементы при построении Указатель Адрес области памяти, в которой лежат данные. Если обговорено, какие это данные, указатель может быть использован для доступа к ним. Структурированный набор На языке Pascal – записи (record) Аналог массива, состоящий из переменных разного типа.

ProPowerPoint.Ru Пример структуры Массив – индексированный набор элементарных переменных. Массив представляет собой структуру, в которую входит один тип переменных.

ProPowerPoint.Ru Хранение данных в структурах Место для всех данных отводится сразу (чаще – в начале блока), во время программы не изменяется. Используется при объявлении переменных. Статический тип Количество элементов заранее неизвестно, меняется во время исполнения программы. Память отводится и освобождается самой программой. Динамический тип

ProPowerPoint.Ru Динамические структуры Требуют дополнительных операций! Компилятор не всегда может проконтролировать правильность выполнения! Список динамическая структура данных, в которой каждый элемент состоит из указателя на следующий элемент и одинакового для всех элементов набора дополнительных данных. Место элемента в последовательности определяется не номером, а указателем на него в предыдущем или в следующем по порядку элементе, т. е. частью структуры. Список хранят как вход в него, т. е. указатель на «голову» списка. Если указатель на «голову» пуст, то и список пуст. Дерево - динамическая структура данных, которая имеет минимум два возможных выхода из каждого элемента и не имеет циклов, т. е. путей, связывающих между собою не «родственные» элементы.

ProPowerPoint.Ru Списки Односвязные В структуру входит только указатель на следующий элемент. Если указатель пуст (имеет специальное значение nil), то это последний элемент. Двусвязные В структуру входят указатели на следующий и на предыдущий элементы, т. е. можно двигаться не только «вперед», но и «назад». Можем рассматривать не только "голову", но и "хвост". Виды по количеству связей: Примечание: мы будем рассматривать двусвязные списки.

ProPowerPoint.Ru Основные операции Указатель на «голову» списка хранится в переменной head. Пустое значение указателя обозначим в коде как nil. 1. Добавление элемента в «голову» списка: newListItem = new ListItem //добавляем новый элемент newListItem.next = head //нынешнее первое «спускаем» newListItem.prev = nil //пустое значение предыдущего, т.к. его нет. if (head <> nil) // если список существовал head.prev = newListItem //вносим элемент первым head = newListItem //заносим значение как «голову» Сложность алгоритма: О(1) Алгоритм не зависит от размеров списка.

ProPowerPoint.Ru 2. Поиск элемента в списке: (т. е. элемента со значением данных target) currItem = head //начинаем с «головы» while ((currItem <> nil)and(currItem.data <> target)) //до тех пор, пока у нас есть список и элемент не найден currItem = currItem.next //проходим дальше, переобозначая Сложность алгоритма: О(n) В худшем случае необходимо проверить весь список. 3. Удаление элемента из списка: If (delItem.next <> nil) //если след. элемент есть (не пуст) delItem.next.prev = delItem.prev //сдвигаем назад if (delItem.prev <> nil) //если пред.элемент не пуст delItem.prev.next = delItem.next // «перешагиваем» на след. delete delItem //удаляем нужный элемент При удалении элемента из списка важно сохранить его связность. Поэтому сначала мы исключаем элемент из цепочки, а потом освобождаем занятую им память. Сложность алгоритма: Если элемент не нужно искать (например, мы удаляем элемент из «головы» списка), то количество действий останется O(1), если нужно, то O(n).

ProPowerPoint.Ru Чем полезен список? Задание: Подумайте над вопросом, чем удобней в применении список по сравнению с массивом и когда он хуже. Резюмируя результаты: если заранее неизвестно количество элементов; 1. неудобен, когда нужен быстрый доступ к произвольному элементу (необходимо проходить каждый раз весь список или хранить указатели в отдельном массиве). 2. не нужно заботиться о выходе за границы; 3. позволяет быстро производить вставку, удаление элементов.

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

ProPowerPoint.Ru Двоичные деревья Элемент N (текущий) n Элемент Q q q<n Элемент P p pn

ProPowerPoint.Ru Операции над деревьями Дерево хранится как указатель на его первый элемент, который называется корневым. Будем считать, что указатель на корень дерева хранится в переменной root. 1. Поиск элемента в дереве: curItem = root //начинаем с корня while ((curItem <> nil)and(curItem.data <> a)) //пока дерево не кончилось и элемент не нашёлся if (curItem.data > a) //рассматриваем элемент curItem = curItem.left //присваиваем меньшее значение («левое») else curItem = curItem.right //присваиваем большее или равное значение //(«правое») Сложность алгоритма: зависит от кол-ва элементов дерева и порядка, в котором их добавляли. Если элемента в дереве нет, то последним текущим элементом станет nil.

ProPowerPoint.Ru 2. Вставка элемента в дерево: Сложность алгоритма: если дерево сбалансировано – О(log n), если в дерево элементы добавлялись неудачно (например, по возрастанию), оно становится списком, а сложность возрастает до О(n). Дерево называется сбалансированным, если в нём мало или совсем нет узлов с одним потомком.

ProPowerPoint.Ru Типовые структуры данных Стек (stack) Линейная структура данных, в которой есть две операции: помещения и извлечения. При извлечении всегда выдается последний помещенный в структуру элемент. Такой принцип называется LIFO ( Last In First Out, т.е. «последний зашёл – первый вышел»). Пример-аналогия: стопка тарелок (можно брать только последнюю) или люди в набитом автобусе. Очередь Линейная структура с двумя операциями, но извлекается не последний, а первый помещенный элемент, т.е. используется принцип FIFO (First In First Out). Пример-аналогия: очередь в магазине (первый встал - первый купил и вышел). Двоичное дерево поиска В этом дереве каждый элемент имеет не более двух потомков, причем левый меньше текущего ключа, а правый больше. Могут быть реализованы и с помощью динамических, и с помощью статических структур.

ProPowerPoint.Ru Практическая часть 1. Вас просят написать программу, которая получает данные о книгах. О каждой книге будет известно название, автор, цена, количество и расположение на складе. Общее количество книг заранее неизвестно. Опишите структуру данных, которую целесообразно использовать для хранения. program task4_18_1; Type book = record // Структура для хранения данных о конкретной книге на складе title : string; author: string; count : word; price : longword; place : word; end; pNode = ^ListNode; // Общая структура для организации учета склада ListNode = record next : pNode; bookData : book; end; // Добавление элемента в список function itemListNew (title : string; author: string; count : word; price : longword; place : word; next : PNode):pNode; begin new (Result); Result^.bookData.title := title; Result^.bookData.author := author; Result^.bookData.count := count; Result^.bookData.price := price; Result^.bookData.place := place; Result^.next := next; end; // Ввод данных о книге с клавиатуры function itemListKeyboard (next : pNode) : pNode; var title, author: string; count : word; price : longword; place : word; begin write ('Введите название==>'); readln(title); write ('Введите автора==>'); readln(author); write ('Введите количество==>'); readln(count); write ('Введите цену==>'); readln(price); write ('Введите место==>'); readln(place); Result := itemListNew (title,author,count,price,place, next); end; var head : pNode; answ : char; begin // Создание списка repeat write('Желаете ввести новую книгу?(д/н)'); readln(answ); if answ = 'д' then head := itemListKeyboard(head); until answ <> 'д'; end. //Вывод списка в этой задаче не требовался. Для рассмотрения скопируйте код в компилятор!

ProPowerPoint.Ru 2. Подготовьте программу, которая вводит и выводит данные о книгах. Вводиться будут данные из предыдущей задачи, а выводиться название и общая стоимость книг этого наименования. program task4_18_2; Type book = record // Структура для хранения данных о конкретной книге на складе title : string; author: string; count : word; price : longword; place : word; end; pNode = ^ListNode; // Общая структура для организации учета склада ListNode = record next : pNode; bookData : book; end; // Функция-итератор, подробно рассмотренная в задачнике iterate = function( item : pNode): pNode; procedure iteratorList(start : pNode; iterateFunction : iterate); var current : pNode; begin current := start; repeat current:=iterateFunction(current); until current = nil; end; // Добавление элемента в список function itemListNew (title : string; author: string; count : word; price : longword; place : word; next : PNode):pNode; begin new (Result); Result^.bookData.title := title; Result^.bookData.author := author; Result^.bookData.count := count; Result^.bookData.price := price; Result^.bookData.place := place; Result^.next := next; end; // Ввод данных о книге с клавиатуры function itemListKeyboard (next : pNode) : pNode; var title, author: string; count : word; price : longword; place : word; begin write ('Введите название==>'); readln(title); write ('Введите автора==>'); readln(author); write ('Введите количество==>'); readln(count); write ('Введите цену==>'); readln(price); write ('Введите место==>'); readln(place); Result := itemListNew (title,author,count,price,place, next); end; function printListItem (item : pNode) : pNode; begin writeln(item^.bookData.title,',',item^.book Data.price*item^.bookData.count); result := item^.next; end; var head : pNode; answ : char; begin // Создание списка repeat write('Желаете ввести новую книгу?(д/н)'); readln(answ); if answ = 'д' then head := itemListKeyboard(head); until answ <> 'д'; iteratorList(head,printListItem); // Вывод всех значений списка – решение задачи 2 end.

ProPowerPoint.Ru 3. Подготовьте программу, которая выведет только книги заданного автора. program task4_18_3; Type book = record // Структура для хранения данных о конкретной книге на складе title : string; author: string; count : word; price : longword; place : word; end; pNode = ^ListNode; // Общая структура для организации учета склада ListNode = record next : pNode; bookData : book; end; // Функция-итератор, подробно рассмотренная в задачнике iterate = function( item : pNode): pNode; procedure iteratorList(start : pNode; iterateFunction : iterate); var current : pNode; begin current := start; repeat current:=iterateFunction(current); until current = nil; end; // Добавление элемента в список function itemListNew (title : string; author: string; count : word; price : longword; place : word; next : PNode):pNode; begin new (Result); Result^.bookData.title := title; Result^.bookData.author := author; Result^.bookData.count := count; Result^.bookData.price := price; Result^.bookData.place := place; Result^.next := next; end; function printListItemAuthor (item : pNode) : pNode; begin if item^.bookData.author='Калинин И.А.,Самылкина Н.Н.' then writeln(item^.bookData.author,',',item^.bo okData.title,',',item^.bookData.price); result := item^.next; end; // Ввод данных о книге с клавиатуры function itemListKeyboard (next : pNode) : pNode; var title, author: string; count : word; price : longword; place : word; begin write ('Введите название==>'); readln(title); write ('Введите автора==>'); readln(author); write ('Введите количество==>'); readln(count); write ('Введите цену==>'); readln(price); write ('Введите место==>'); readln(place); Result := itemListNew (title,author,count,price,place, next); end; function printListItem (item : pNode) : pNode; begin writeln(item^.bookData.title,',',item^.book Data.price*item^.bookData.count); result := item^.next; end; var head : pNode; answ : char; begin // Создание списка head := itemListNew ('Информатика - 10','Калинин И.А.,Самылкина Н.Н.',10,210,1,nil); head := itemListNew ('Информатика - 11','Калинин И.А.,Самылкина Н.Н.',10,180,1,head); repeat write('Желаете ввести новую книгу?(д/н)'); readln(answ); if answ = 'д' then head := itemListKeyboard(head); until answ <> 'д'; writeLn('Книги искомого автора(ов):'); iteratorList(head, printListItemAuthor); end.

ProPowerPoint.Ru 4*. Опишите структуру, которая позволит вводить данные о нескольких авторах и их книгах (неизвестно заранее, сколько их будет), а также по желанию пользователя дополнять описание книг атрибутами (например, ключевыми словами). //Универсальная структура хранения данных. До типов атрибутов. pAttribute = ^attribute; attribute = record; nextAttribute : pAttribute; attributeType : word; //Тип атрибута: 1 - автор, 2 - название, 3 - ключевое //слово и т.д. attributeNumber : longword; //Значение атрибута - число attributeString : longword; //Значение атрибута - строка end; pBook = ^BookUniversal; bookUniversal = record //Книга, обладающая любым кол-вом атрибутов next : pBook; attributeList :pAttribute; end; *Требуется только описать структуру, а не программу. Примечания: для удобства необходимо оговорить нумерацию атрибутов (например, составить отдельную таблицу соответствия). Некоторые атрибуты могут встречаться несколько раз.

ProPowerPoint.Ru 5. Опишите структуру данных, которая может быть использована для определения растения по наличию или отсутствию признаков (т. е. признак либо есть, либо нет). *Требуется только описать структуру, а не программу. Ответом будет построение двоичного дерева, описанного в учебнике и рассмотренного здесь ранее. pBinaryNode = ^BinaryTreeNode; //необходимая структура BinaryTreeNode = record left,right : pNode; //Правая и левая ветви – записи. queryText : string; //Содержат текстовое описание признаков. end;

ProPowerPoint.Ru 6. Напишите программу, определяющую растение заданного семейства по стандартной определительной карте (например, крестоцветное). program task4_18_6; type pNode = ^TreeNode; TreeNode = record left, right: pNode; leftText, rightText: string; end; function itemListNew(leftText: string): pNode; begin new(Result); Result^.leftText := leftText; Result^.left := nil; Result^.right := nil; end; procedure infoNode(current: pNode); var leftText, rightText: string; begin leftText := 'Споранхии есть.'; current^.leftText := leftText; rightText := 'Споранхий нет.'; current^.rightText := rightText; leftText := 'Зрелый лист.'; current^.left := itemListNew(leftText); rightText := 'Молодой лист.'; current^.right := itemListNew(rightText); end; var answ: char; head, current: pNode; begin head := itemListNew('Что-то живое'); current := head; infoNode(current); begin writeln('Вариант 1: ', current^.leftText); writeln('Вариант 2: ', current^.rightText); writeln('Выберите вариант 1 или 2 '); readln(answ); if answ = '1' then current := current^.left else current := current^.right; writeln('У нас есть только один вариант: ', current^.leftText); end; end.

ProPowerPoint.Ru 7*. Напишите программу, которая позволит расширить карту. program task4_18_7; type pNode = ^TreeNode; TreeNode = record left, right: pNode; leftText, rightText: string; end; function itemListNew(leftText: string): pNode; begin new(Result); Result^.leftText := leftText; Result^.left := nil; Result^.right := nil; end; procedure newNode(current: pNode); var leftText, rightText: string; answ: char; begin writeln('Ввведите признак первого варианта '); readln(leftText); current^.leftText := leftText; writeln('Ввведите признак второго варианта '); readln(rightText); current^.rightText := rightText; writeln('Ввведите вывод по первому варианту '); readln(leftText); current^.left := itemListNew(leftText); writeln('Ввведите вывод по второму варианту '); readln(rightText); current^.right := itemListNew(rightText); end; var answ: char; head, current: pNode; begin head := itemListNew('Что-то живое'); current := head; repeat while current <> nil do begin if current^.leftText <> '' then writeln('Вариант 1: ', current^.leftText); if current^.leftText <> '' then writeln('Вариант 2: ', current^.rightText); if (current^.left <> nil) and (current^.right <> nil) then begin writeln('Выберите вариант 1 или 2 '); readln(answ); if answ = '1' then current := current^.left else current := current^.right; end else begin writeln('У нас есть только один вариант: ', current^.leftText); writeln('Желаете добавить ветвление? (д/н)'); readln(answ); if answ = 'д' then newNode(current); end; writeln('Желаете повторить определение? (д/н)'); readln(answ); until answ = 'н'; end.