Учебно-методический комплекс для специальности 1-31 03 07 «Прикладная информатика
жүктеу/скачать 3,71 Mb.
|
УМКАлгор и стр данн Инеттен (1)
|
элементов списка в консоль.
{ cout << current->data << “ “; current = current->link; }
Самые естественные операции со списком это 1. создание списка; 2. добавление элементов; 3. удаление элементов; 4. поиск и извлечение элементов. 60 ДОБАВЛЕНИЕ ЭЛЕМЕНТОВ В ОДНОСВЯЗНЫЙ СПИСОК.
p. Эта задача решается следующим образом: 23 38 47 NULL 1. newNode = new nodeType; //создание нового эл-та списка 2. newNode->data = 50; //запись информационной части 3. newNode->link = p->link; //инициализация указателя нового элемента 4. p->link = newNode; //перенаправление указателя p Работа с указателями должна осуществляться именно в такой последовательности — существующий указатель p сначала используется, а только потом перенаправляется.
Графическая иллюстрация: 1. newNode = new nodeType; head 11 p //создание нового эл-та списка newNode 23 38 47 NULL 61 2. newNode->data = 50; newNode->link = NULL;
данных! А именно: 62 3. p->link = newNode; head 11 p newNode 50 23 38 47 NULL 4. newNode->link = p->link; head 11 p newNode 50 23 38 47 NULL В этом случае элементы списка со значениями 38 и47удалены из списка и потеряны. УДАЛЕНИЕ ЭЛЕМЕНТОВ ИЗ ОДНОСВЯЗНОГО СПИСКА.
Пусть список имеет такой же вид, как в предыдущем примере: head 11 p Нужно удалить из списка элемент, следующий сразу же после того элемента, на который указывает p. Удалить элемент из списка можно следующим образом:
23 38 47 NULL p->link = p->link->link; Выглядит это так: head 11 p 23 38 47 NULL 63 Однако, удалённый из списка элемент продолжает занимать выделенную ему память и она недоступна для использования. Чтобы освободить память нужно иметь указатель на этот элемент. Поэтому полное решение задачи будет таким:
1. 2. 3. 4. nodeType *q; q = p->link; p->link = q->link; delete q; Графическая иллюстрация В этом случае элемент удаляется из списка и освобождается память. 1. nodeType *q; 2. q = p->link; //дополнительный указатель q для освобождения памяти
head 11 p 23 q 38 47 NULL 3. p->link = q->link; //перенаправление указателя p — удаление элемента из списка head 11 p 23 q 38 47 NULL 4. delete q; //освобождение памяти head 11 P 23 47 NULL 64 СОЗДАНИЕ ОДНОСВЯЗНОГО СПИСКА. До сих пор речь шла о уже существующем, непустом списке. Чтобы создать самый простой список используем три указателя. Один из них будет указывать на первый элемент списка, второй на последний и третий на новый.
nodeType *first, *last, *newNode; int num;
//поскольку списка ещё нет … 1. first = NULL; 2. last = NULL; first NULL lastNULL //ввод числа с консоли и сохранение в переменной num 3. cin >> num; //выделение памяти под новый элемент списка 4. newNode = new nodeType; //инициализация инф. части элемента и установка в NULL поля-указателя link элемента newNode(т.к. список пока пуст).
5. newNode->data = num; 6. newNode->link = NULL; newNode num NULL 7. if (first == NULL) //если в списке нет ни одного элемента … { 8. first = newNode; 9. last = newNode; } //указатели first и last направлены на newNode — первый, и пока единственный элемент нового списка 65 first
NULL newNode num last 10. else //список не пуст... 11. last->link = newNode; //новый узел newNode добавляется в конец списка first Num last newNode num1 NULL { 12. last = newNode; //указатель last перенаправляется на последний элемент списка — newNode first num last newNode num1 NULL }. 66 ОДНОСВЯЗНЫЙ ЛИНЕЙНЫЙ СПИСОК КАК АБСТРАКТНЫЙ ТИП ДАННЫХ (ADT). Поскольку в форме ОЛН (односвязный линейный список) можно представить различные объекты и типы данных, естественно сделать независимой реализацию методовсписка от природы объектов, образующих список. Это достигается с помощью шаблона класса. Для реализации ОЛН потребуется как минимум два шаблона один для узлов списка, второй для самого списка. Узлы списка можно описывать как стуктуру(struct) или класс (class). Например,в простейшем случае
1. Структура template struct Node { Type date; Node Node(const Type& d = Type(), Node next{p}{} };
2. Класс template class Node { public:
............. private:
T date; Node };
Поскольку класс определяющий структуру данных содержит члены- указатели, в него обязательно должны быть включены: 1. Деструктор, освобождающий память от указателей; 2. Перегруженный оператор присваивания ‘ = ’; 3. Копирующий конструктор.
67 Поддерживаемые операции 1. 2. 3. 4. 5. 6. 7. 8.
9. 10.
11. 12.
13. вставить элемент в начало списка; вставить элемент в конец списка; получить указатель на первый элемент списка. получить указатель на последний элемент списка. получить информационную часть последнего элемента списка. получить информационную часть первого элемента списка. получить указатель на следующий, относительно текущего, элемент; найти элемент с указанной информационной частью и вернуть укзатель на него. вставить элемент после текущего элемента и вернуть указатель на него; удалить выбранный элемент из списка; очистить список; копировать список; вывести в консоль все элементы списка. Пример интерфейса класса LinkedList template class LinkedList { public:
LinkedList(); // Конструктор по умолчанию. Создаёт пустой список. ~LinkedList();// Деструктор const LinkedList (const LinkedList // Перегрузка оператора присваивания. LinkedList(const LinkedList // Копирующий конструктор bool isEmpty() const; // Отвечает на вопрос пуст список или нет. Возвращает true, если список не пуст и false в противном случае.
void print() const; int length() const; // Выводит данные из каждого элемента списка. // Возвращает количество элементов в списке. void empty(); // Удаляет все узлы списка. В результате 68 список пуст:first = NULL, last = NULL, count = 0;
элемент списка. T end() const;// Возвращает информационную часть последнего элемента списка. void insertFirst(const T& newItem); // Добавляет элемент в начало списка. void insertLast(const T& newItem); // Добавляет элемент в конец списка. Node // Ищет в списке элемент item и возвращает укзатель на этот элемент. Node // Возвращает указатель на следующий элемент списка.
void deleteNode(const T& item); // Удаляет элемент item из списка. private: void copyList(const LinkedList &otherList); // Функция, создающая копию списка otherList. int count;// кол-во элементов списка. Node Node списка.
}; 69 Контрольные вопросы 1. Что такое абстрактная структура данных? 2. Основные свойства структуры данных односвязный линейный список? 3. Напишите алгоритм основных операций с односвязным линейным списком. 4. Какие способы реализации структуры данных односвязный линейный список вы знаете?
ПРАКТИЧЕСКИЕ ЗАДАНИЯ Задание 1 Разработать консольное приложение, которое с помощью абстрактной структуры данных ОДНОСВЯЗНЫЙ ЛИНЕЙНЫЙ СПИСОК формирует список из: строкопределйннойтематики(тематикувыбрать самостоятельно); массивов чисел; массивов строк; структур, содержащих не менее 2-х числовых и 2-х строковых полей. Приложение должно: 1. делать запрос на ввод данных пользователем при создании списка; 2. выводить по запросу длину (к-во элементов) списка; 3. осуществлять поиск данных по введённому значению и сообщать номер найденного элемента или соответствующее сообщение, в случае, если данные не найдены.
70 Лабораторная работа №2 Цель работы: Изучение принципов организации и работы с абстрактной структурой данных СТЭК в форме односвязного линейного списка. Стэк — структура данных, в которую можно добавлять элементы и извлекать их, причём элемент, котрый был добавлен последним, извлекается первым (LIFO–Last In First Out, последний пришёл первый ушёл).Указатель top всегда указывает на последний добавленный элемент.
Графическая иллюстрация: top 11 23 38 47 NULL Поддерживаемые операции 1. 2. 3. 4. 5. 6. добавить элемент в стэк; извлечь информационную часть «верхнего» элемента; удалить «верхний» элемент; проверить на пустоту; очистить стэк; копировать стэк. 71 ДОБАВЛЕНИЕ ЭЛЕМЕНТОВ В СТЭК (метод push()) Графическая иллюстрация: 1 newNode 81 NULL top 11 top 2 newNode 81 11 23 23 38 38 47 47 NULL 3 newNode top 11 … … 47 47 NULL NULL 72 81 top NULL 4 81 УДАЛЕНИЕ ЭЛЕМЕНТОВ ИЗ СТЭКА (метод pop()) Графическая иллюстрация: 1 temp top 81 2 temp 81 11 top 11 23 23 38 38 47 47 NULL NULL 3 top 11 23 38 … 73 Пример интерфейса класса LinkedStack и структуры Node template struct Node { Type info; Node };
template class LinkedStack { public:
linkedStack(); // Конструктор по умолчанию linkedStack(const linkedStack &otherStack);
// Копирующий конструктор ~linkedStack();// Деструктор const linkedStack linkedStack // Перегрузка оператора присваивания bool isEmpty() const; // Отвечает на вопрос пуст ли стэк? void initialize(); // Опустошает стэк.(top = NULL) void push(const Type& newItem); // Добавляет newItem в стэк Type top() const; // Возвращает данные top элемента стэка void pop();// Удаляет top элемент стэка 74 private:
Node добавленный элемент стэка void copy(const linkedStack &otherStack); // Функция копирования. Создаёт копию стэка otherStack и присваивает её this стэку. Контрольные вопросы 5. 6. 7. 8. 9.
Что такое абстрактная структура данных? Основное свойство структуры данных стэк? Напишите алгоритм основных операций со стэком. Какие способы реализации структуры данных стэк вы знаете? Каков будет результат применения операций PUSH(S,4), PUSH(S,1), PUSH(S,3), POP(S), PUSH(S,6), PUSH(S,4), PUSH(S,1), PUSH(S,3), POP(S), POP(S) к пустому стэку, хранящемуся в массиве S[1..6]? К тому же стэку, уже хранящему 2 элемента? ПРАКТИЧЕСКИЕ ЗАДАНИЯ Задание 1 Разработать консольное приложение, которое с помощью абстрактной структуры данных СТЭК располагает элементы данного массива (вектора) в обратном порядке (инвертирует). Тип данных элементов массива выбрать произвольно. Приложение должно: 1. делать запрос на ввод размера и элементов создаваемого массива; 2. выводить в консоль исходный массив после его создания; 3. делать запросы на: 3.1. инвертирование исходного массива: в случае «Да» выводить в консоль инвертированный массив; 3.2. изменение исходного массива: в случае «Да» создавать новый массив и выводить его в консоль;
3.3. выход из приложения в случае «Да» выходить из приложения; Задание 2
Разработать консольное приложение, которое с помощью абстрактной структуры данных СТЭК проверяет соответствие открывающих и 75 закрывающих HTML-тэгов во фрагменте HTML кода, введённого с клавиатуры. Приложение должно: 1. делать запрос на ввод HTML кода; 2. выводить в консоль: в случае соответствия – сообщение об этом; в случае несоответствия – сообщение об этом и тэг(и), для которого нет пары; 3. делать запрос на выход из приложения. Задание 3
Разработать консольное приложение, которое с помощью абстрактной структуры данных СТЭК вычисляет арифметическое выражение, записанное в постфиксной форме (postfix notation). Выражение может содержать 4 основных действия, скобки и числа. Для распознавания чисел их можно вводить сразу после определённого символа, например, #. Приложение должно: 1. делать запрос на ввод выражения в постфиксной форме; 2. выводить в консоль: введённое выражение и результат вычислений в случае корректного ввода; сообщение об ошибке и введённое выражение в случае некорректного ввода; 3. делать запрос на выход из приложения.
Лабораторная работа №3 Цель работы: Изучение принципов организации и работы с абстрактной структурой данных ОЧЕРЕДЬ в форме односвязного линейного списка.
Очередь — структура данных, в которую можно добавлять элементы и извлекать их, причём элемент, котрый был добавлен первым, извлекается также первым (FIFO–First In First Out, первый пришёл первый ушёл). Указатель front указывает на первый добавленный элемент, а rear – на последний. 76 Графическая иллюстрация: NULL rear 47 38 23 front 11 Поддерживаемые операции 1. 2. 3. 4. 5. 6. добавить элемент в очередь; извлечь информационную часть «первого» элемента; удалить «первого» элемент; проверить на пустоту; очистить очередь; копировать очередь. 77 ДОБАВЛЕНИЕ ЭЛЕМЕНТОВ В ОЧЕРЕДЬ (метод enQueue()) Графическая иллюстрация: 1 NULL newNode 81 NULL rear 47 rear newNode 2 NULL 81 47 38 38 23 23 front 11 front 11 3 newNode rear 81 NULL rear 4 NULL 81 47 47 … … front 11 front 11 78 УДАЛЕНИЕ ЭЛЕМЕНТОВ ИЗ ОЧЕРЕДИ (метод deQueue()) Графическая иллюстрация: 1 NULL rear 47 2 NULL rear 47 38 38 23 front 23 front temp 11 temp 11 3 NULL rear 47 38 front 23 79 Контрольные вопросы 1. 2. 3. 4. 5.
Что такое абстрактная структура данных? Основное свойство структуры данных очередь? Напишите алгоритм основных операций с очередью. Какие способы реализации структуры данных очередь вы знаете? Каковбудетрезультатпоследовательностиопераций ENQUEUE(Q,4), DEQUEUE(Q), DEQUEUE(Q), ENQUEUE(Q,1), ENQUEUE(Q,3), ENQUEUE(Q,6), DEQUEUE(Q), ENQUEUE(Q,8), ENQUEUE(Q,11), ENQUEUE(Q,2), DEQUEUE(Q), DEQUEUE(Q) к пустой очереди, хранящейся в массиве Q[1..6]? К той же очереди, уже хранящей 2 элемента? ПРАКТИЧЕСКИЕ ЗАДАНИЯ Задание 1 Разработать консольное приложение, которое с помощью абстрактной структуры данных ОЧЕРЕДЬ моделирует работу аэропорта (или другой системы массового обслуживания) с одной взлётно-посадочной полосой, которую в каждый момент времени (цикл for) может использовать только один самолёт – для взлёта или посадки. Приложение должно: 1. сделать запрос на ввод данных для моделирования: жүктеу/скачать 3,71 Mb. Достарыңызбен бөлісу:
|