Двусвязные списки
Выполнил студент группы ПМИб-2301-01-00 _______________/ Д. А. Смирнов /
Проверил преподаватель кафедры ФИиПМ _______________ / Т.Г. Прозорова /
Киров 2017
Цель работы
Изучить особенности работы с динамической структурой данных – двусвязным списком.
Задание на лабораторную работу
Написать программу, позволяющую работать с предметным указателем.
Каждая компонента указателя содержит слово и номера страниц, на которых это слововстречается. Количество номеров страниц, относящихся к одному слову, лежит в диапазоне отодного до десяти.
Описание алгоритмов работы программы
Предметный указатель представляет из себя двусвязный список структур –компонент, хранящих слово и ссылки на него (номера страниц). Эти номера страниц хранятся также в виде двусвязного списка.
Добавление ссылки на слово осуществляется следующим образом. Среди элементов предметного указателя (двусвязного списка) ищется такая компонента, слово которой совпадает со словом, на которое ссылается добавляемая ссылка. Если такаякомпонента была найдена, то среди номеров страниц этой компоненты ищется номер страницы, на которую ссылается добавляемая ссылка. Если такой номер не был найден, то в двусвязный список номеров страниц этой компоненты добавляется добавляемая ссылка.
Если среди компонент предметного указателя не была найдена компонента, слово которой совпадает со словом, на которое ссылается добавляемая ссылка, то в предметный указатель добавляется компонента со словом, на которое ссылается добавляемая ссылка, а в список номеров страниц добавленной компоненты добавляется номер страницы, на которую ссылается добавляемая ссылка.
Удаление ссылки на слово осуществляется следующим образом. Среди элементов предметного указателя (двусвязного списка) ищется такая компонента, слово которой совпадает со словом, на которое ссылается удаляемая ссылка. Если такая компонента была найдена, то среди номеров страниц этой компоненты ищется номер страницы, на которую ссылается добавляемая ссылка. Если такой номер был найден, то он удаляет из двусвязного списка номер страниц. Если после удаления этот список оказался пуст, то данная компонента удаляется из предметного указателя.
Алгоритмы добавления, удаления и поиска элементов в двусвязном списке.
Добавление элемента в двусвязный список осуществляется следующим образом.
Во-первых, под добавляемый элемент и под указатели на следующий и на предыдущий элементы выделяется память.
Если элемент добавляется в начало списка, то указатель на предыдущий элемент добавляемого элемента принимает значение NULL, указатель на следующий элемент добавляемого элемента принимает значение указателя, указывающего на первый элемент, ауказатель первого элемента (если таковой имеется) на предыдущий элемент принимает значение указателя, указывающего на выделенный под новый элемент участок памяти.
Если элемент добавляется в конец списка, то указатель на следующий элемент добавляемого элемента принимает значение NULL, указатель на предыдущий элемент добавляемого элементапринимает значение указателя, указывающего на последний элемент, а указатель последнего элемента на следующий элемент принимает значение указателя, указывающего на выделенный под новый элемент участок памяти.
Если элемент добавляется в середину (и до, и после добавляемого элемента есть другие элементы) после элемента node, то указатель на предыдущий элемент добавляемого элемента принимает значение указателя, указывающего на элемент node, указатель на следующий элемент добавляемого элемента принимает значение указателя на следующий элемент элемента node, указатель на следующий элемент элемента nodeпринимает значение указателя, указывающего на выделенный под новый элемент участок памяти, указатель на предыдущий элемент элемента, на который указывает указатель на следующий элемент нового элемента, принимает значение указателя, указывающего на выделенный под новый элемент участок памяти.
Поиск элемента в двусвязном списке осуществляется следующим образом.
Создаётся указатель currentnode. Далее ему присваивается значение указателя на первый элемент списка. И пока значение указателя currentnode не равно NULL, выполняются следующие действия.
Для элемента, на который указывает currentnode, проверяется условие (в программе условие реализовано с помощью лямбда-выражений), по которому происходит поиск. Если оно истинно, то возвращается указатель на этот элемент и метод поиска завершается. Если ложно, то указатель currentnode принимает значение указателя на следующий элемент элемента, на который указывает currentnode.
Удаление элемента из двусвязного списка осуществляется следующим образом.
В списке осуществляется поисктакого элемента, который удовлетворяет некоторому условию. Назовём указатель на этот элемент removingnode. Если же элемент, удовлетворяющий данному условию, не был найден, метод удаления завершается.
Если removingnode указывает на первый элемент списка, то указатель на первый элемент списка принимает значение указателя на следующий за первым элементом элемент, иначе указатель на следующий элемент элемента, на который указывает указатель на предыдущий элемент элемента, на который указывает указатель removingnode, принимает значение указателя removingnode.
Если removingnode указывает на последний элемент списка, то указатель на последний элемент списка принимает значение указателя на предыдущий последнему элементу элемент, иначе указатель на предыдущий элемент элемента, на который указывает указатель на следующий элемент элемента, на который указывает указатель removingnode, принимает значение указателя removingnode.
Далее происходит очистка памяти, занимаемой удаляемым элементом.
Листинг
Файл.h, содержащий реализацию двусвязного списка
#pragmaonce
#include<functional>
#include<utility>
usingnamespacestd;
template<classT>
classDoublyLinkedList
{
template<classT>
structDLLNode
{
T value;
DLLNode<T> *next;
DLLNode<T> *prev;
DLLNode()
{
next = nullptr;
prev = nullptr;
}
DLLNode(Tv)
{
value = v;
next = nullptr;
prev = nullptr;
}
};
private:
DLLNode<T> *head;
DLLNode<T> *tail;
public:
DoublyLinkedList();
DoublyLinkedList(constDoublyLinkedList<T>&);
~DoublyLinkedList();
voidpush_tail(constT);
voidpush_tail(constT, constint);
T&back_head() const;
T&back_tail() const;
T&back_head(constint) const;
void clean();
pair<bool, T*> find(constfunction<bool(T)>) const;
bool remove(constfunction<bool(T)>);
bool empty() const;
int size() const;
};
template<classT>
DoublyLinkedList<T>::DoublyLinkedList()
{
head = nullptr;
tail = nullptr;
}
template<classT>
DoublyLinkedList<T>::DoublyLinkedList(constDoublyLinkedList<T>&list)
{
head = nullptr;
tail = nullptr;
DLLNode<T>* currentNode = list.head;
while (currentNode!= nullptr)
{
push_tail(currentNode->value);
currentNode = currentNode->next;
}
}
template<classT>
DoublyLinkedList<T>::~DoublyLinkedList()
{
while (head!= nullptr)
{
DLLNode<T> *removingNode = head;
head = head->next;
deleteremovingNode;
}
tail = nullptr;
}
// Добавление элемента в конец двусвязного списка
template<classT>
voidDoublyLinkedList<T>::push_tail(constTnewItem)
{
DLLNode<T>* newNode = newDLLNode<T>(newItem);
if (empty())
{
head = newNode;
tail = newNode;
}
else
{
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
}
// Добавление элемента с конца двусвязного списка, проталкивая его вглубь на index позиций
template<classT>
voidDoublyLinkedList<T>::push_tail(constTnewItem, constintindex)
{
if (index == 0) { push_tail(newItem); }
else
{
DLLNode<T>* currentNode = tail; // Указатель на элемент, после которого должен вставиться новый элемент
for (inti = 1; i<index; i++)
{
if (currentNode->prev == nullptr) { throw"Error 1"; }
else { currentNode = currentNode->prev; }
}
if (currentNode->prev == nullptr) { push_head(newItem); }
else
{
DLLNode<T>* newNode = newDLLNode<T>(newItem);
newNode->prev = currentNode->prev;
newNode->next = currentNode;
currentNode->prev->next = newNode;
currentNode->prev = newNode;
}
}
}
// Возвращает элемент, находящийся в начале двусвязного списка
template<classT>
T&DoublyLinkedList<T>::back_head() const
{
if (head == nullptr) { throw"Error 1"; }
else{ returnhead->value; }
}
// Возвращает элемент, находящийся в конце двусвязного списка
template<classT>
T&DoublyLinkedList<T>::back_tail() const
{
if (tail == nullptr) { throw"Error 1"; }
else{ returntail->value; }
}
// Возвращает элемент, находящийся на позиции index от начала двусвязного списка
template<classT>
T&DoublyLinkedList<T>::back_head(constintindex) const
{
DLLNode<T>* currentNode = head;
for (inti = 0; i<index; i++)
{
if (currentNode == nullptr) { throw"Error 1"; }
else { currentNode = currentNode->next; }
}
if (currentNode == nullptr) { throw"Error 1"; }
else { returncurrentNode->value; }
}
// Очищаетдвусвязныйсписок
template<classT>
voidDoublyLinkedList<T>::clean()
{
DoublyLinkedList<T>::~DoublyLinkedList();
}
// ВыполняетпоискэлементаItemвдвусвязномспискетакого, чтозначениеpredicate(Item) истинно
template<classT>
pair<bool, T*>DoublyLinkedList<T>::find(function<bool(T)>predicate) const
{
DLLNode<T>* currentNode = head;
while (currentNode!= nullptr)
{
if (predicate(currentNode->value))
{
returnpair<bool, T*>(true, ¤tNode->value);
}
else { currentNode = currentNode->next; }
}
returnpair<bool, T*>(false, nullptr);
}
// Удаляет из двусвязного списка такой элемент Item, что значение predicate(Item) истинно
template<classT>
boolDoublyLinkedList<T>::remove(constfunction<bool(T)>predicate)
{
DLLNode<T>* currentNode = head;
while (currentNode!= nullptr)
{
if (predicate(currentNode->value))
{
if (head == currentNode) { head = currentNode->next; }
else { currentNode->prev->next = currentNode->next; }
if (tail == currentNode) { tail = currentNode->prev; }
else { currentNode->next->prev = currentNode->prev; }
deletecurrentNode;
returntrue;
}
else { currentNode = currentNode->next; }
}
returnfalse;
}
// Возвращает, пуст ли двусвязный список
template<classT>
boolDoublyLinkedList<T>::empty() const
{
if (head == nullptr) { returntrue; }
else{ returnfalse; }
}
// Возвращает количество элементов в двусвязном списке
template<classT>
intDoublyLinkedList<T>::size() const
{
DLLNode<T>* currentNode = head;
int count = 0;
while (currentNode!= nullptr)
{
currentNode = currentNode->next;
count++;
}
return count;
}
Файл.cpp, содержащий реализацию предметного указателя и метод main
#include"stdafx.h"
#include"DoublyLinkedList.h"
#include"Menu.h"
usingnamespacestd;
structComponent
{
string Word;
DoublyLinkedList<int> Links;
Component()
{
Word ="";
Links =DoublyLinkedList<int>();
}
Component(stringword)
{
Word =word;
Links =DoublyLinkedList<int>();
}
};
structSubjectIndex
{
DoublyLinkedList<Component>wordsList;
// Добавлениессылкислова word настраницу page
voidaddLink(conststringword, constintpage)
{
function<bool(Component)>prComponent = [word](Componentobject) { returnobject.Word==word; };
pair<bool, Component*>neededComponent = wordsList.find(prComponent);
int sup2 = 0;
if (!neededComponent.first)
{
wordsList.push_tail(Component(word));
wordsList.back_tail().Links.push_tail(page);
}
else
{
function<bool(int)>prLink = [page](intobject) { returnobject == page; };
pair<bool, int*>neededLink = neededComponent.second->Links.find(prLink);
if (!neededLink.first) { neededComponent.second->Links.push_tail(page); }
}
intsup = 0;
}
// Удаление ссылки слова word на страницу page
voidremoveLink(conststringname, constintpage)
{
function<bool(Component)>prComponent = [name](Componentobject) { returnobject.Word==name; };
pair<bool, Component*>neededComponent = wordsList.find(prComponent);
if (neededComponent.first)
{
function<bool(int)>prLink = [page](intobject) { returnobject == page; };
neededComponent.second->Links.remove(prLink);
if (neededComponent.second->Links.empty())
{
wordsList.remove(prComponent);
}
}
}
// Считывание предметного указателя из текстового файла с именем name
voidreadFromFile(conststringname)
{
wordsList.~DoublyLinkedList();
ifstream file(name);
intnWords;
file>>nWords;
for (inti = 0; i<nWords; i++)
{
string word; file >> word;
intnLinks; file >>nLinks;
ComponentnewComponent = Component(word);
wordsList.push_tail(newComponent);
for (int j = 0; j <nLinks; j++)
{
int page; file >> page;
wordsList.back_tail().Links.push_tail(page);
}
}
file.close();
}
// Запись предметного указателя в текстовый файл с именем name
voidwriteToFile(conststringname)
{
ofstream file(name);
file<<wordsList.size() <<endl;
for (inti = 0; i<wordsList.size(); i++)
{
ComponentcurrentComponent = wordsList.back_head(i);
file<<currentComponent.Word<<" "<<currentComponent.Links.size() <<" ";
for (int j = 0; j <currentComponent.Links.size(); j++)
{
file<<currentComponent.Links.back_head(j) <<" ";
}
file<<endl;
}
file.close();
}
};
SubjectIndex subjectindex1 = SubjectIndex();
voidread()
{
cout<<"Введите имя файла (без расширения), из которого необходимо считать предметный указатель:"<<endl;
string name;
cin>> name; name +=".txt";
ifstream file;
file.open(name);
if(!file)
{
cout<<"Файл с именем "<<name<<" не был найден."<<endl;
_getch();
}
else
{
file.close();
subjectindex1.wordsList.clean();
subjectindex1.readFromFile(name);
}
}
voidwrite()
{
cout<<"Введите имя файла (без расширения), в который необходимо записать предметный указатель:"<<endl;
string name;
cin>> name; name +=".txt";
ofstream file;
file.open(name);
if(!file)
{
cout<<"Файл с именем "<<name<<" не был найден."<<endl;
_getch();
}
else
{
file.close();
subjectindex1.writeToFile(name);
}
}
void clean()
{
subjectindex1.wordsList.clean();
cout<<"Предметный указатель был очищен.";
_getch();
}
voidadd()
{
cout<<"Введите слово и номер страницы:"<<endl;
string word; int page;
cin>> word >> page;
if (cin.fail())
{
cin.clear();
cin.ignore(32767, '\n');
cout<<"Некорректныйввод."<<endl;
_getch();
}
else
{
subjectindex1.addLink(word, page);
}
}
voidremove()
{
cout<<"Введите слово и номер страницы:"<<endl;
string word; int page;
cin>> word >> page;
if (cin.fail())
{
cin.clear();
cin.ignore(32767, '\n');
cout<<"Некорректныйввод."<<endl;
_getch();
}
else
{
subjectindex1.removeLink(word, page);
}
}
voidwriteOnScreen()
{
if (subjectindex1.wordsList.empty())
{
cout<<"Предметный указатель пуст.";
}
else
{
for (inti = 0; i< subjectindex1.wordsList.size(); i++)
{
cout<< subjectindex1.wordsList.back_head(i).Word <<" ";
for (int j = 0; j < subjectindex1.wordsList.back_head(i).Links.size(); j++)
{
cout<< subjectindex1.wordsList.back_head(i).Links.back_head(j) <<" ";
}
cout<<endl;
}
}
_getch();
}
int main()
{
setlocale(LC_ALL, "Russian");
Menu menu1 = Menu();
menu1.AddWindow(nullptr);
menu1.AddWindow(read);
menu1.AddWindow(write);
menu1.AddWindow(clean);
menu1.AddWindow(add);
menu1.AddWindow(remove);
menu1.AddWindow(writeOnScreen);
menu1.AddWindow(nullptr);
menu1.AddJunction(0, 1, "Считать предметный указатель из текстового файла");
menu1.AddJunction(0, 2, "Записать предметный указатель в текстовый файл");
menu1.AddJunction(0, 3, "Очистить предметный указатель");
menu1.AddJunction(0, 4, "Добавить в предметный указатель ссылку на какое-либо слово");
menu1.AddJunction(0, 5, "Удалить из предметного указателя ссылку на какое-либо слово");
menu1.AddJunction(0, 6, "Вывести на экран ссылки предметного указателя");
menu1.AddJunction(0, 7, "Выйти");
menu1.AddJunction(1, 0, "");
menu1.AddJunction(2, 0, "");
menu1.AddJunction(3, 0, "");
menu1.AddJunction(4, 0, "");
menu1.AddJunction(5, 0, "");
menu1.AddJunction(6, 0, "");
menu1.Start();
}
Выводы
В ходе лабораторной работы была изучена динамическая структура данных двусвязный список. Также были применены шаблоны классов.