Содержание
Введение
1. Определение АТД
2. Общие положения
3. Описание операций
3.1 Операция добавления элемента
3.2 Операция добавления элемента послеуказанного
3.3 Операция удаления указанного элемента
3.4 Операция распечатки записей списка
4. Реализация АТД-список
4.1 Главная функция
4.2 Интерфейс
4.3 Реализация методов
Заключение
Список литературы
Приложение A:граф-схемы алгоритмов
Введение
Независимо от типарешаемых задач, любая программа оперирует какими-то данными, а сама программапредстваляет собой методы управления и обработки этих данных. Скоростьвыполнения программой поставленной задачи зависит не только от алгоритмов,использованных в ней для обработки и управления данными, но также и от самойорганизации данных. Таким образом, мы приходим к понятию о структурах данных.
Прямое взаимодействиемежду программой через пользователя и структурами данных оставляет открытымимножество данных, модификация которых нелегитимным способом (минуя интерфейс)может привести к нежелательным последствиям. Чтоб миновать данную проблемунеобходимо «возвести стены» между данными и программой, оставив лишь «окошко»в виде интерфейса. Для этого необходимо определить абстрактные типы данных, спомощью которых эти стены воздвигаются.
В данной работеразрабатывается абстрактный тип данных (АТД) – список, который впоследствииреализуется в виде связного списка, реализованного при помощи косвеннойадресации, основанной на указателях. Более подробно вопросы разработки АТДрассматриваются в [3].
1.Определение АТД
Абстракция данныхописывает, что можно делать с набором данных, игнорируя вопрос «какимобразом это делается?». Абстракция данных – это способ разрабатыватьотдельные компоненты программы, независимо от остальной ее части (остальныхкомпонентов). Таким образом, абстракция данных – естественное расширение функциональнойабстракции, позволяющей разрабатывать функции в относительной изоляции друг отдруга. Набор данных в сочетании с совокупностью операций над ними называетсяабстрактным типом данных. Описание операций, входящих в АТД, должно бытьдостаточно строгим, чтоб точно указать их воздействие на данные. Но в нем недолжен указываться способ хранения данных или детали выполнения операций.Конкретный способ хранения данных (структура данных) выбирается только приреализации АТД. Структура данных – конструкция, определенная в языкепрограммирования для хранения набора данных. Согласно варианту задания,определены следующие данные:
1. Наименованиемикросхемы
2. Стоимость
3. Количество
Над ними определеныследующие операции:
1.Добавление элемента в неупорядоченныйсписок
2.Удаление элемента с заданным полем изнеупорядоченного списка
3.Добавление элемента после указанного
4.Удаление всех элементов с заданнымполем
5.Распечатка списка
Данный набор определяетмножество допустимых операций над опеределенными в задании данными, т.е. нам заданабстрактный тип данных.
Далее будут рассмотреныкаждая из операций в отдельности, определены их спецификации и предложеныконкретные реализации.
2.Общие положения
Абстрактный список можнореализовать в виде массива – на первый взгляд, очевидный шаг. Массив имеетфиксированный размер (в большинстве языков программирования), в то время какдлина абстрактного списка неограничена. Таким образом, структура данныхстановится статической, что является недостатком.
Другой существенныйнедостаток является продолжением достоинства массивов – последовательноерасположение данных в смежных ячейках, иными словами, столь часто производимые,следовательно, требующие максимальной скорости выполнения, операции как вставкаи удаления элемента приводят к необходимости сдвигать элементы массива,затрачивая дополнительное время.
Принцип реализациисписка, не использующего сдиг элементов, основан на косвенной адресации. Одругих способах реализации абстарктных списков подробно рассказывается в [3].
Каждый узел связанногосписка состоит из двух частей: непосредственно данных и указателя на следующийэлемент – такой же узел или константу NULL.
Поскольку, согласнопринципу инкапсуляции, доступ к данным должен осуществляться только посредствомметодов, определенных для этой цели, для данных определен спецификатор доступа private.
Механизм выделения памятипод элементы списка, основанного на указателях, предполагает динамическоевыделение памяти при помощи операторов new и delete. Таким образом, при создании нового элемента имеет смысл выделять памятьтолько лишь под новые данные, а не под уже определенные методы – операциисписка. Следовательно, необходимо вынести методы из структуры данных. В даннойработе, была применена методика расширения интерфейса созданием структурыметодов – дружественного класса, методы которого имеют доступ к закрытым членамкласса узла.
Подробней о принципахобъектно-ориентированного программирования можно узнать из [1, 3].
Указатели на голову ихвост списка объявлены в классе Listпоскольку по сути необходимы для реализации методов АТД, в то время как длясамой структуры данных они не имеют ни малейшего смысла.
Методы, которые не должныникоим образом модифицировать данные, объявлены с использованием ключевогослова const.
3.Описание операций
3.1Разработка операции добавления элемента
В данной реализации АТД-списокподразумевается (по умолчанию) принцип добавления элемента, тождественныйаналогичному в АТД-очередь. Таким образом можно сформулировать инварианты дляоперации (по умолчанию) добавления элемента в список:
Предусловие: списоксуществует
Постусловие: указатель нахвост указывает на созданный элемент
Так как все операции надструктурами данных являются методами дружественного класса, реализующегосписок, то, очевидно, что операция добавления элемента также является методомэтого класса. Следовательно, чтобы выполнить данный метод необходимо создатьэкземпляр класса List, инымисловами, предусловие выполняется всегда.
Следует отметить, чтоуказатели в С++ должны быть инициализированы. Так как список изначальносоздается пустым, указатели должны быть инициализированы константой NULL. Это операция реализуется вконструкторе по умолчанию класса List:
Таким образом, врезультате выполнения операции добавления элемента в список, указатели будут инициализированыкорректно.
Логично, что операцияинициализации данных в создаваемом элементе следует сразу за созданием узла(записи) списка. Данную операцию удобно не выносить в интерфейс в виде метода,а поручить конструктору по умолчанию класса Node – в данной реализации списка не предусмотренавозможность существования пустых записей:
Процесс связываения узловотличается в зависимости от того, пуст ли список или нет.
В первом случае сначаланеобходимо создать голову списка, создав экземпляр класса Node. Поскольку список в данном случаесостоит лишь из одного узла, то для выполнения условия связности непустогосписка указатель на хвост должен указывать на последний созданный узел – вданном случае на голову. Этот факт и составляет основное отличие между двумяпроцессами добавления элемента, поскольку в данном случае память выделялаcь для первого элемента, а в остальныхслучаях – для последнего.
Операция добавления (поумолчанию) элемента в пустой список:
/>
Операция добавленияэлемента в конец списка:
/>
Макрос assert, определенный в библиотеке cassert проверяет была ли выделена память подузлы корректным образом.
3.2операциЯ добавления элемента после указанного
Операция добавленияэлемента после указанного сильно отличается от уже разработанной операциидобавления элемента в список и пред-, постусловия предыдущей операций будутнеполными в данном контексте. Прежде всего это связано с тем, что вводитсярешающий фактор существования (или не существования) элемента, указываемогопользователем по имени. В случае несуществования элемента, указанногопользователем, вставка становится невозможной.
К тому же, необходимосначала найти указанный элемент или выявить признак его отсутствия. Для этойцели необходимо произвести обход списка. Так как список неупорядоченный мы неможем применить бинарный поиск, который значительно более эффективный, чемпоследовательный – его сложность порядка О(log2n) против О(n),т.е., например, при количестве записей 106, алгоритм бинарногопоиска найдет элемент в худшем случае за 19 тактов, в то время какпоследовательный – за 106 тактов. Основные алгоритмы поиска исортировки подробно рассмотрены в [3, 4, 5].
Последовательный поискпредставляет собой обход списка со сравнением с контрольным ключом (в данномслучае именем микросхемы) в каждом узле. Поскольку данный процесс совершеннолинейный, удобно реализовать всю функцию рекурсивно. Базовая задача – созданиенового узла и его связывание с предыдущим и последующим узлами, шаг рекурсии –сравнение записи с контрольной, условие завершения рекурсии – решение базовойзадачи либо завершение обхода.
Предусловия: списоксуществует, указанный элемент существует
Постусловие: новый элементвставлен после указанного, сохраняя связность списка
3.3ОперациЯ удаления указанного элемента
Инварианты для даннойоперации сходны с аналогичными для предыдущей операции, так как основнымпроцессом является последовательный поиск указанного элемента.
Предусловие: списоксуществует, указанный элемент существует
Постусловие: указанныйэлемент удален, связность списка сохранена
Очевидно, что длясохранения связности списка необходимо переопределить связи элементов записитаким образом, чтоб миновать в цепочке указанный элемент, но сохранитьуказатель на удаляемый узел, во избежании утечки памяти. Для этой цели, кромеуказателя на удаляемый узел, необходим указатель на предыдущий узел. Обходсписка совершается как раз для получения такого указателя.
Очевидно, что операцииудаления первого и последнего элементов списка представляют собой отдельныезадачи, так как требуют переопределения указателей на голову и хвост списка.
Случай удаления хвостасписка, кроме всего прочего, означает, что указатель на хвост получает значениеконстанты NULL, несмотря на то, что списокнеобязательно пуст. Строго говоря, установка значения указателя на хвост(голову) равным константе NULLявляется флагом, устанавливающим, признак того, что список пуст. Это приводит ктому, что нарушается механизм, обеспечивающий связность списка, иными словамисписок перестает существовать.
Во избежании подобнойситуации, носящей для списка, вообще говоря, катастрофический характер,необходимо в теле самой функции, непосредственно в блоке, в котором реализованалгоритм удаления узла, являющегося хвостом списка, предусмотреть операциюустановки указателя на хвост.
Для этого достаточносовершить обход списка, начиная с головы до тех пор, пока не будет достигнутхвост.
Для удаления всехэлементов с указанным именем, необходимо реализовать цикл, в котором бывыполнялась уже реализованная процедура удаления одного элемента.
В данном случае, нетнеобходимости совершать обход в этой же функции, тем более, что необходимо нетолько произвести обход, но и определить, существует ли еще элемент с указаннымименем.
Пусть данная функцияпоиска возвращает ноль, если элемент не найден, единицу, если элемент суказанным именем найден. Данная функция не имеет права модифицировать данные,следовательно, объявляется с ключевым словом const.
Очевидно, что отзначения, возвращаемого функцией поиска, зависит, будет ли продолженпоследовательный обход списка для удаления элемента.
Таким образом, функция Remove_ предполагает интерфейс для операцийудаления вне зависимости от количества удаляемых записей.
Операция удаления первогоэлемента:
/>
Операция удаленияуказанного элемента:
/>
3.4Операция распечатки записей списка
По сути, операцияраспечатки записей списка представляет собой все тот же последовательный обходсписка, начиная с головы списка. Единственным дополнением является тот момент,что при посещении каждого узла, производится вывод на экран данных, хранящихсяв каждом конкретном узле (записи).
Обход списка реализованрекурсивно.
4.Реализация АТД-список
4.1 Главная функция
#include
#include«iface.h»
#include«code.h»
usingnamespace std;
int main() {
List aList;
char temp[50];
bool exit =false;
for (;;) {
int choice =menu();
switch(choice){
case (1):
aList.Insert();
break;
case (2):
cout>temp;
aList.Insert(temp,aList.GetHead());
break;
case (3):
cout>temp;
aList.Remove_(temp);
break;
case (4):
aList.Print(aList.GetHead());
break;
case (5):
exit = true;
break;
default:
cout
break;
}
if (exit)break;
}
return 0;
}
4.2 Интерфейс
class Node {
public:
Node();
~Node();
friend classList;
private:
int Price;
int Number;
char Name[50];
Node *pNext;
};
class List {
public:
~List();
List();
Node*GetHead() const;
void Insert();
voidInsert(char*, Node*);
voidRemove(char*);
voidRemove_(char*);
voidPrint(Node*) const;
voidSetTail(Node*);
intSearch(char*) const;
private:
Node *pHead;
Node *pTail;
};
int menu();
int Correct();
4.3 Реализация методов
#include
#include
#include
usingnamespace std;
Node::Node() {
cout>Name;
cout
cout
cout
}
List::List() {
pHead = NULL;
pTail = NULL;
cout
}
List::~List(){
Node* pTemp;
while (pHead){
pTemp = pHead;
pHead = pHead->pNext;
delete pTemp;
cout
}
}
Node*List::GetHead() const {
return pHead;
}
voidList::Insert() {
if (pHead ==NULL) {
pHead = newNode;
assert(pHead!= NULL);
pHead->pNext= NULL;
pTail = pHead;
}
else {
pTail->pNext= new Node;
assert(pTail->pNext!= NULL);
pTail =pTail->pNext;
pTail->pNext= NULL;
}
}
voidList::Insert(char *Query, Node *Pointer) {
int Match;
Node*pNewNode;
if (Pointer ==NULL) {
cout
return;
} else {
Match =strcmp(Query, Pointer->Name);
if (Match ==0) {
pNewNode = newNode;
assert(pNewNode!= NULL);
pNewNode->pNext= Pointer->pNext;
Pointer->pNext= pNewNode;
}else
Insert(Query,Pointer->pNext);
}
}
voidList::Print(Node *Pointer) const {
if (Pointer ==NULL)
return;
coutName
coutPrice
coutNumber
Print(Pointer->pNext);
}
voidList::Remove(char *Query) {
if (pHead ==NULL) {
cout
return;
}
Node *pPrev =pHead;
Node *pTemp =pHead->pNext;
if(strcmp(Query, pHead->Name) == 0) {
pTemp = pHead;
pHead =pHead->pNext;
delete pTemp;
cout
return;
}
while (pTemp!= NULL) {
if(strcmp(Query,pTemp->Name)==0)
break;
pPrev = pTemp;
pTemp =pTemp->pNext;
}
if (pTemp ==NULL) {
cout
return;
}
else {
pPrev->pNext= pTemp->pNext;
if (pTemp ==pTail) {
delete pTemp;
SetTail(pHead);
cout
return;
}
delete pTemp;
cout
}
}
voidList::Remove_(char *Query) {
int choice;
cout
cout>choice;
if (choice !=2) {
Remove(Query);
return;
}
while(Search(Query) == 1) {
Remove(Query);
}
}
intList::Search(char *Query) const {
Node *Pointer= pHead;
while (Pointer!= NULL) {
if(strcmp(Query,Pointer->Name)==0)
return 1;
Pointer =Pointer->pNext;
}
return 0;
}
voidList::SetTail(Node *Pointer) {
if(Pointer->pNext == NULL) {
pTail =Pointer;
return;
}
if (Pointer ==NULL) {
pTail = pHead;
return;
}
SetTail(Pointer->pNext);
}
int menu() {
int choice;
cout
cout
cout
cout
cout
cout
choice =Correct();
return choice;
}
int Correct(){
int number =0; char buffer[10];
cin>>buffer;
for (int i =0; i != 9; i++) {
if(buffer[i]>='0' && buffer[i]
number = number*10+ buffer[i] — '0';
}
return number;
}
Заключение
В данном курсовом проектебыл реализован абстрактный тип данных – односвязный список на основеуказателей.
В процессе реализациибыли соблюдены принципы объектно-ориентированного программирования. Особоевнимание было уделено инкапсуляции данных и разработке интерфейса, исключающегонелигитимное модифицирование данных, определенных в задании.