Розовая методичка. Огнева М. В., Кудрина Е. В. Структуры данных и алгоритмы программирование на языке c

• Название: Огнева М. В., Кудрина Е. В. Структуры данных и алгоритмы программирование на языке c
• Анкор: Розовая методичка.pdf
• Дата: 04.10.2017
• Размер: 1.93 Mb.
• Имя файла: Розовая методичка.pdf
• Тип: Документы; #9204
• страница: 6 из 8

Замечание. Класс ListException помещен в отдельный файл exception.срр и выглядит следующим образом:
#include
"exception"
#include
"string"
using namespace std; class
ListException
: public exception
{ public
:
ListException
(
const string
& message=
""
): exception
(message.c_str()) {}
};
Более подробно основные операции с однонаправленными списками рассмотрим на примере членов-функций класса List.
1. Проход по списку (например, член-функции Print)
Для реализации этого действия необходим вспомогательный указатель, который вначале устанавливается на первый элемент списка, а потом «пробегает» весь список, указывая поочередно на каждый элемент.
Чтобы установить указатель на первый элемент списка выполняем команду:
Element
*cur=head;
Для вывода содержимого текущего узла в глобальный поток out используется оператор: out<inf;
Для перехода на следующий узел используется команда: cur=cur->next;
58

И заканчивается проход по списку тогда, когда указатель cur примет значение
NULL.
В результате получаем цикл: for (
Element
*cur = head; cur!=
NULL
; cur = cur-> next)
{ cout << cur->inf <<
" "
;
}
Замечание Аналогичный прием используется в функции Find, которая возвращает указатель на элемент списка с номером index Отличие только в том, что мы завершаем перемещение по списку тогда, когда найдем элемент с заданным номером.
2. Вставка нового элемента в список в заданную позицию (на примере член- функции Insert).
Существует два варианта вставки элемента в список.
Вариант первый - это вставка элемента в начало списка. В этом случае, нам необходимо последовательно выполнить две команды: newPtr->next = head;
//1
head = newPtr;
//2
Заметим, что вставка в пустой список - это вставка элемента в начало списка, у которого head=NULL.
Второй вариант - вставка элемента в середину списка. В этом случае нам необходимо знать указатель на предшествующий элемент. Это можно сделать с помощью команды:
Element
*prev=Find(index-1);
Следующие команды позволят нам вставить новый элемент в заданную позицию: newPtr->next = prev->next;
//1
prev->next = newPtr;
//2
59

Рис. 5.7. Вставка элемента в середину списка
Заметим, что вставка элемента в конец списка пройдет корректно, т.к. указатель prev определен и указатель prev->next равен NULL,
3. Удаление элемента из списка (на примере член-функции Remove)
Так же как и при вставке элемента в список существует два варианта. Первый вариант - удаление первого элемента из списка. В этом случае, нам необходимо последовательно выполнить две команды: cur = head;
//1
head = head->next;
//2
Рис. 5.8. Удаление первого элемента из списка
Второй вариант - вставка элемента в середину списка. В этом случае нам необходимо знать указатель на предшествующий элемент. Это можно сделать с помощью команды:
Element
*prev = Find(index-1);
Следующие команды позволят нам удалить требуемый элемент: cur = prev->next;
//1
prev->next = cur->next;
//2
Рис. 5.9. Удаление элемента из середины списка
Заметим, что удаление элемента из конца списка пройдет корректно, т.к. указатель prev определен и указатель prev->next равен NULL.
Замечание. При работе со стеком и очередью нам не требовался деструктор, т.к. обработка стека и очереди подразумевает извлечение из них элементов. В результате чего в конце работы указанные виды списков остаются пустыми. При работе со списками общего
60

вида элементы из него могут и не извлекаться. Поэтому нам требуется корректно освободить память, выделенную под список. Что и делает деструктор.
5.8.
Решение практических задач с использованием однонаправленных
списков
1.
Дана последовательность натуральных чисел. Создать из них список и после каждого элемента равного х вставить элемент равный у. Входная последовательность целых чисел и заданные числа х и у хранятся в файле input.txt, выходная последовательность целых чисел записывается в файл output.txt.
#include

#include

using namespace std;
//подключаем файл с реализацией класса-шаблона список
#include
"list.cpp"
//подключаем глобальные потоки
ifstream in(
"input.txt"
); ofstream out(
"output.txt"
); int main()
{
List
<
int
> l; int value, x, y; in >> x >> y;
//пока файл не пуст, считываем из него очередной элемент и
//помещаем в список; позиция, в которую вставляем новый элемент
//будет на 1 больше, чем количество элементов в списке
while
(in >> value)
l.lnsert(l.GetLength()+1.value); in.close(); out <<
"Исходный список: "
; l.Print();
//просматриваем список поэлементно
for
(
int i = 1; i <= l.GetLength(); i++)
{ if
(l.Get(i)==x)
//если значение элемента в i-той позиции равно х
{ l.lnsert(i+1 ,у);
//вставляем элемент у в эту позицию
i++;
}
} out <<
"Измененный список:"
; l.Print();
61

l.

List();
//вызываем деструктор
out.close(); return
0;
}
Результата работы программы:
______input.txt ________ __________________ output.txt _______________________
7 0
Исходный список: 7 7 1 3 7 5 2 5 7 2 7 9 3 7 7 7 7 1 3 7 5 2 5 7 2 7 9 3 7 7
Измененный список: 7 0 7 0 1 3 7 0 5 2 5 7 0 2 7 0 9 3 7 0 7 0 2.
Дана последовательность натуральных чисел. Создать из них очередь и каждый ее элемент, равный х заменить на элемент равный у. Входная последовательность целых чисел и заданные числа х и у хранятся в файле input.txt, выходная последовательность целых чисел записывается в файл output.txt.
Решение данной задачи можно свести к применению двух член-функций Insert и
Remove. Так в функции main можно перебрать все элементы списка и, если встречаем элемент равный х, то удаляем его, а на его место вставляем элемент равный у. Этот алгоритм можно реализовать следующим способом: for
(
int i = 1; i <= l.GetLength(); i++)
{ if
(l.Get(i) == x)
{ l.Remove(i); l.lnsert(i,y);
}
}
Однако для решения данной задачи более рационально добавить новую член- функцию Change в класс List. В функции Change мы просматриваем все элементы списка и, если значение очередного элемента совпадает со значением х, то заменяем значение этого элемента на у. Это алгоритм можно реализовать следующим способом: void
Change(
ltem х,
Item у)
{
Element
*cur = head;
//устанавливаем указатель на начало списка
//перебираем элементы списка по очереди
for
(
Element
*cur = head; cur !=
NULL
; cur = cur->next)
{ if
(cur->inf == x)
//если элемент равен x
{ cur->inf = y;
//заменяем его на у
}
}
}
Второй способ решения задачи соответствует идеологии ООП, а добавление новой член-функции в класс List, существенно расширяет его функциональные возможности.
62

Теперь полное решение данной задачи выглядит следующим образом:
#include

#include

using namespace std;
#include
"list.cpp"
//не забудьте добавить функцию Change в класс List
ifstream in(
"input.txt"
); ofstream out(
"output.txt"
); int main()
{
List
<
int
> l; int value, x, y; in >> x >> y; while
(in >> value)
{ l.lnsert(l.GetLength()+1,value);
} in.close(); out <<
"Исходный список:"
; l.Print(); l.Change(x, y);
//вызов член-функции Change
out <<
"Измененный список:"
; l.Print(); lList(); out.close(); return
0;
}
Результата работы программы:
______input.txt_______ _____________output.txt_______________
7 0
Исходный список: 7 7 1 3 7 5 2 5 7 2 7 9 3 7 7 7 7 1 3 7 5 2 5 7 2 7 9 3 7 7
Измененный список: 0 0 1 3 0 5 2 5 0 2 0 9 3 0 0
5.9.
Двунаправленный список
До сих пор мы рассматривали однонаправленные списки. В таких списках можно передвигаться лишь в одном направлении, а чтобы, например, удалить элемент, необходимо иметь указатель на предыдущий элемент. Однако иногда требуется одинаково эффективно передвигаться по списку в обоих направлениях. В этом случае используют двунаправленные списки, когда в каждом узле имеются два указателя: на следующий и на предыдущий элемент:
63

Рис. 5.10. Структура двунаправленного списка
Базовый элемент двунаправленного списка содержит:
•
информационное поле inf, которое может быть любого типа, кроме файлового, и будет использоваться для хранения значений, например чисел, строк, записей;
•
поля-указатели next и prev, в которых хранятся адреса следующего и предыдущего элементов двунаправленного списка соответственно, и которые будут использоваться для организации связи элементов.
Замечание В общем случае базовый элемент списка может содержать несколько информационных полей
Предложенный базовый элемент двунаправленного списка может быть описан следующим образом: struct
Element
{
Item inf;
//информационное поле типа Item
Element
*next;
//указатель на следующий элемент списка
Element
*prev;
//указатель на предыдущий элемент списка
Element(
Item х): inf(x), next(0), prev(0) {}
}
Поскольку в каждом узле такого списка задействовано два указателя вместо одного, механизм операций вставки и удаления будет несколько усложнен по сравнению с односвязными списками. Зато можно удалять элемент, на который есть указатель, и вставлять элементы до и после заданного, не задействуя дополнительные указатели.
Приведем объектно-ориентированную реализацию двунаправленного списка, а затем подробно рассмотрим базовые операции с данным видом списка.
Внимание! Код ниже не редактировался (сил уже моих нет), там могут быть опечатки! Лучше смотрите его в печатной версии методички или качайте исходники с гитхаба (ссылка на второй странице).
#include
"exception.cpp"
template
<
class
Item
> class
DoubleLinkedList
{ struct
Element
{
Item inf;
Element
*next;
Element
*prev;
Element(
Item x): inf(x), next(0), prev(0) {}
};
64

Element
*head;
Element
*tail; int size;
//возвращает указатель на элемент списка с номером index
Element
*Find (
int index)
{ if
((index<1)||(index>size))
{ return
NULL
;
} else
{
Element
*cur=head; for
(int i=1; i{ cur=cur->next;
} return cur;
}
} public
:
DoubleLinkedList():head(0),tail(0),size(0)
//конструктор
{
}
DoubleLinkedList()
//деструктор
{ while
(!Empty())
{
Remove(1);
}
} bool
Empty()
//проверяет список на пустоту
{ return head==0;
} int
GetLength()
//возвращает количество элементов в списке
{ return size;
}
//возвращает значение элемента списка по его номеру
Item
Get(
int index)
{ if
((index<1)||(index>size))
{
65

throw
DoubleListException
(
"Exception: get— double-linked list error"
);
} else
{
Element
*r=Find(index);
Item i=r->inf; return i;
}
}
//осуществляет вставку элемента со значением data слева от
//элемента с позицией index
void lnsertLeft(
int index,
Item data)
{ if
((index<1)||(index>size+1))
{ throw
DoubleListException
(
"Exception:
insert — double-linked list error
");
} else
{
Element
*newPtr = new
Element
(data); size = GetLength()+1;
//увеличиваем размерность списка
//устанавливаем указатель на элемент списка с заданным
номером
Element
*cur=Find(index);
//если этот указатель NULL, то список был пуст, поэтому
//новый элемент будет и первым и последним
if
(cur==
NULL
)
//см. рис. 5.11.
{ head = newPtr; tail = newPtr;
} else
//иначе производим вставку в непустой список, при этом
//есть два случая: 1 -частный случай (вставка перед
//первым элементом списка), 2 - общий случай
{ newPtr->next=cur; newPtr->prev=cur->prev; cur->prev=newPtr; if
(cur==head)
{ head=newPtr;
//случай 1
} else
{ newPtr->prev->next=newPtr;
//случай 2
66

}
}
}
}
//осуществляет вставку элемента со значением data слева от
//элемента с позицией index
void lnsertRight(
int index,
Item data)
{ if
((index<1&&head!=
NULL
)||(index>size+1))
{ throw
DoubleListException
(
"Exception: insert — double-linked list error"
);
} else
{
Element
*newPtr=
new
Element
(data); size= GetLength()+1;
//увеличиваем размерность списка
//устанавливаем указатель на элемент списка с заданным
номером
Element
*cur=Find(index);
//если этот указатель NULL, то список был пуст, поэтому
//новый элемент будет и первым и последним
if
(cur==
NULL
)
{ head=newPtr; tail=newPtr;
} else
//иначе производим вставку в непустой список, при этом
//есть два случая: 1 - вставка после последнего элемента
//списка, 2 - вставка в середину списка
{ newPtr->next=cur->next; newPtr->prev=cur; cur->next=newPtr; if
(cur==tail)
{ tail=newPtr;
//случай 1
} else
{ newPtr->next->prev=newPtr;
//случай 2
}
}
}
}
//осуществляет удаление элемента с номером index из списка
67

//выделяем четыре случая: 1 - после удаления список становится
пустым,
//2 - удаляем первый элемент, 3 - удаляем последний элемент,
// 4 - общий случай
void
Remove(
int index)
{ if
((index<1)||(index>size))
{ throw
DoubleListException
(
"Exception: remove — double- linked list error"
);
} else
{
//устанавливаем указатель на заданный элемент
Element
*cur=Find(index);
--size
//уменьшаем размерность списка
if
(size==0)
//случай 1
{ head=
NULL
; tail=
NULL
;
} else if
(cur==head)
//случай 2
{ head=head->next; head->prev=
NULL
;
} else if
(cur==tail)
//случай 3
{ tail=tail->prev; tail->next=
NULL
;
} else
//общий случай, см.рис. 5.14
{
cur->prev->next=cur->next; cur->next->prev=cur->prev;
} cur->next=
NULL
; cur->prev=
NULL
; delete cur;
}
}
//вывод элементов списка в глобальный поток out в прямом порядке
void
PrintLeftToRight()
{ for
(
Element
*cur = head; cur!=
NULL
; cur = cur->next)
{ out << cur->inf<<
" "
;
} out<68

}
//вывод элементов списка в глобальный поток out в обратном порядке
void
PrintRightToLeft ()
{ for
(Element *cur = tail; cur!=
NULL
; cur = cur->prev)
{ out << cur->inf<<
" "
;
} out<}
};
Замечание. Класс DoubleListException помещен в отдельный файл exception.cpp и выглядит следующим образом:
#include
"exception"
#include
"string"
using namespace std; class
DoubleListException
: public exception
{ public
:
DoubleListException(
const string
& message=
""
): exception
(message.c_str()) {}
};
Более подробно основные операции с двунаправленными списками рассмотрим на примере член-функций класса DoubleLinkedList.
1. Проход по списку в обратном порядке (на примере член-функции
PrintRightToLeft)
Для реализации этого действия необходим вспомогательный указатель, который вначале устанавливается на последний элемент списка, а потом «пробегает» весь список в обратном порядке по указателям prev.
Чтобы установить указать на первый элемент списка, выполняем команду:
Element *cur=head;
Для вывода содержимого текущего узла в глобальный поток out используется оператор: out<inf;
Для перехода на следующий узел используется команда: cur=cur->prev;
И заканчивается проход по списку тогда, когда указатель cur примет значение
NULL.
В результате получаем цикл: for
(
Element
*cur = tail; cur!=
NULL
; cur = cur-> prev)
{ out << cur->inf <<
" "
;
}
69

Замечание. Проход по списку в прямом порядке используется в функции
PrintLeftToRight. Рассмотрите данную функцию самостоятельно.
2.
Вставка нового элемента в список слева от заданной позиции (на примере член-функции InsertLeft).
При вставке нового элемента в двунаправленный список слева от заданной позиции нужно рассмотреть несколько возможных ситуаций.
Если первоначально список пустой, то новый элемент станет одновременно первым и последним. Для этого необходимо установить указатели head и tail на новый элемент:
Рис. 5.11. Добавление элемента в пустой список
Если список не пустой, то возможны два случая: частный - вставка перед первым элементом в списке (см. рис 5.12), и общий случай - вставка в произвольное место списка
(5.13). Рассмотрим фрагмент функции InsertLeft более подробно на рисунках: newPtr->next=cur;
//1 newPtr->prev=cur->prev;
//2 cur->prev=newPtr;
//3
if
(cur==head)
//4
{ head=newPtr;
//5
} else
{ newPtr->prev->next=newPtr;
//6
}
Рис. 5.12 Частный случай вставки нового элемента в начало двунаправленного списка
70

Рис. 5.13 Общий случай вставки нового элемента в двунаправленный список слева от заданной позиции
Как видно из рисунков, вставка элемента в список требует аккуратной работы с указателями. В противном случае, будет нарушена целостность списка, а также последовательность расположения элементов в списке.