Учебно-методический комплекс для специальности 1-31 03 07 «Прикладная информатика



бет5/8
Дата14.10.2019
өлшемі3,71 Mb.
#49870
түріУчебно-методический комплекс
1   2   3   4   5   6   7   8
Байланысты:
УМКАлгор и стр данн Инеттен (1)

элементов списка в консоль.

current = head;

while(current != NULL)

{

cout << current->data << “ “;



current = current->link;

}


Самые естественные операции со списком это

1. создание списка;

2. добавление элементов;

3. удаление элементов;

4. поиск и извлечение элементов.



60

ДОБАВЛЕНИЕ ЭЛЕМЕНТОВ В ОДНОСВЯЗНЫЙ

СПИСОК.

Пусть список имеет следующий вид:

head

11

p

Нужно добавить в список элемент сразу после элемента, на который указывает

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;

head

11

p

//запись информационной частии указателя

newNode

50

NULL

23

38

47

NULL

3. newNode->link = p->link;

//инициализация указателя нового элемента

head

11

p

newNode

50

23

38

47

NULL

4. p->link = newNode;

//перенаправление указателя p

head

11

p

newNode

50

23

38

47

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* next;

Node(const Type& d = Type(),

Node* p = nullptr):date{d},

next{p}{}

};

2. Класс

template

class Node

{

public:


.............

private:


T date;

Node* next;

};

Поскольку класс определяющий структуру данных содержит члены-

указатели, в него обязательно должны быть включены:



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& operator=

(const LinkedList&);



// Перегрузка оператора присваивания.

LinkedList(const LinkedList& otherList);

// Копирующий конструктор

bool isEmpty() const;

// Отвечает на вопрос пуст список или нет.

Возвращает true, если список не пуст и false в

противном случае.

void print() const;

int length() const;

// Выводит данные из каждого элемента списка.

// Возвращает количество элементов в списке.

void empty();

// Удаляет все узлы списка. В результате

68

список пуст:first = NULL, last = NULL,

count = 0;

T front() const;

// Возвращает информационную часть первого

элемент списка.

T end() const;// Возвращает информационную часть

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



void insertFirst(const T& newItem);

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

void insertLast(const T& newItem);

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

Node* findNode(const T& item);

// Ищет в списке элемент item и возвращает

укзатель на этот элемент.



Node* nextNode(Node* curr = nullptr);

// Возвращает указатель на следующий элемент

списка.


void deleteNode(const T& item);

// Удаляет элемент item из списка.

private:

void copyList(const LinkedList



&otherList);

// Функция, создающая копию списка otherList.

int count;// кол-во элементов списка.

Node* first;// Указатель на первый элемент списка.

Node* last;// Указатель на последний элемент

списка.

};

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* link;

};


template

class LinkedStack

{

public:


linkedStack(); // Конструктор по умолчанию

linkedStack(const linkedStack

&otherStack);

// Копирующий конструктор

~linkedStack();// Деструктор



const linkedStack& operator=(const

linkedStack& otherStack);



// Перегрузка оператора присваивания

bool isEmpty() const;

// Отвечает на вопрос пуст ли стэк?

void initialize();

// Опустошает стэк.(top = NULL)

void push(const Type& newItem);

// Добавляет newItem в стэк

Type top() const;

// Возвращает данные top элемента стэка

void pop();// Удаляет top элемент стэка



74

private:


Node* top;// указатель на последний

добавленный элемент стэка

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. сделать запрос на ввод данных для моделирования:



Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет