Односвязный список на основе указателей

Содержание

Введение

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 операциЯ добавления элемента после указанного

Операция добавления элемента после указанного сильно отличается от уже разработанной операции добавления элемента в список и пред-, постусловия предыдущей операций будут неполными в данном контексте. Прежде всего это связано с тем, что вводится решающий фактор существования (или не существования) элемента, указываемого пользователем по имени. В случае несуществования элемента, указанного пользователем, вставка становится невозможной.

К тому же, необходимо сначала найти указанный элемент или выявить признак его отсутствия. Для этой цели необходимо произвести обход списка. Так как список неупорядоченный мы не можем применить бинарный поиск, который значительно более эффективный, чем последовательный – его сложность порядка О(log₂n) против О(n), т.е., например, при количестве записей 10⁶, алгоритм бинарного поиска найдет элемент в худшем случае за 19 тактов, в то время как последовательный – за 10⁶ тактов. Основные алгоритмы поиска и сортировки подробно рассмотрены в [3, 4, 5].

Последовательный поиск представляет собой обход списка со сравнением с контрольным ключом (в данном случае именем микросхемы) в каждом узле. Поскольку данный процесс совершенно линейный, удобно реализовать всю функцию рекурсивно. Базовая задача – создание нового узла и его связывание с предыдущим и последующим узлами, шаг рекурсии – сравнение записи с контрольной, условие завершения рекурсии – решение базовой задачи либо завершение обхода.

Предусловия: список существует, указанный элемент существует

Постусловие: новый элемент вставлен после указанного, сохраняя связность списка

3.3 ОперациЯ удаления указанного элемента

Инварианты для данной операции сходны с аналогичными для предыдущей операции, так как основным процессом является последовательный поиск указанного элемента.

Предусловие: список существует, указанный элемент существует

Постусловие: указанный элемент удален, связность списка сохранена

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

Очевидно, что операции удаления первого и последнего элементов списка представляют собой отдельные задачи, так как требуют переопределения указателей на голову и хвост списка.

Случай удаления хвоста списка, кроме всего прочего, означает, что указатель на хвост получает значение константы NULL, несмотря на то, что список необязательно пуст. Строго говоря, установка значения указателя на хвост (голову) равным константе NULL является флагом, устанавливающим, признак того, что список пуст. Это приводит к тому, что нарушается механизм, обеспечивающий связность списка, иными словами список перестает существовать.

Во избежании подобной ситуации, носящей для списка, вообще говоря, катастрофический характер, необходимо в теле самой функции, непосредственно в блоке, в котором реализован алгоритм удаления узла, являющегося хвостом списка, предусмотреть операцию установки указателя на хвост.

Для этого достаточно совершить обход списка, начиная с головы до тех пор, пока не будет достигнут хвост.

Для удаления всех элементов с указанным именем, необходимо реализовать цикл, в котором бы выполнялась уже реализованная процедура удаления одного элемента.

В данном случае, нет необходимости совершать обход в этой же функции, тем более, что необходимо не только произвести обход, но и определить, существует ли еще элемент с указанным именем.

Пусть данная функция поиска возвращает ноль, если элемент не найден, единицу, если элемент с указанным именем найден. Данная функция не имеет права модифицировать данные, следовательно, объявляется с ключевым словом const.

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

Таким образом, функция Remove_ предполагает интерфейс для операций удаления вне зависимости от количества удаляемых записей.

Операция удаления первого элемента:

Операция удаления указанного элемента:

3.4 Операция распечатки записей списка

По сути, операция распечатки записей списка представляет собой все тот же последовательный обход списка, начиная с головы списка. Единственным дополнением является тот момент, что при посещении каждого узла, производится вывод на экран данных, хранящихся в каждом конкретном узле (записи).

Обход списка реализован рекурсивно.

4. Реализация АТД-список

4.1 Главнаяфункция

#include <iostream>

#include "iface.h"

#include "code.h"

using namespace 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<<"nEnter name: "; cin>>temp;

aList.Insert(temp, aList.GetHead());

break;

case (3):

cout<<"nEnter name: "; cin>>temp;

aList.Remove_(temp);

break;

case (4):

aList.Print(aList.GetHead());

break;

case (5):

exit = true;

break;

default:

cout<<"n-----Try to enter defined keys!-----n";

break;

}

if (exit) break;

}

return 0;

}

4.2 Интерфейс

class Node {

public:

Node();

~Node();

friend class List;

private:

int Price;

int Number;

char Name[50];

Node *pNext;

};

class List {

public:

~List();

List();

Node* GetHead() const;

void Insert();

void Insert(char*, Node*);

void Remove(char*);

void Remove_(char*);

void Print(Node*) const;

void SetTail(Node*);

int Search(char*) const;

private:

Node *pHead;

Node *pTail;

};

int menu();

int Correct();

4.3 Реализацияметодов

#include <iostream>

#include <cassert>

#include <cstdlib>

using namespace std;

Node::Node() {

cout<<"Enter name: ";cin>>Name;

cout<<"Enter price (use only digits): ";Price = Correct();

cout<<"Enter number (use only digits): ";Number = Correct();

cout<<"Node constructor called; new entry createdn";

}

List::List() {

pHead = NULL;

pTail = NULL;

cout<<"List constructor called; new list createdn";

}

List::~List() {

Node* pTemp;

while (pHead) {

pTemp = pHead;

pHead = pHead->pNext;

delete pTemp;

cout<<"Destroying the list...n";

}

}

Node* List::GetHead() const {

return pHead;

}

void List::Insert() {

if (pHead == NULL) {

pHead = new Node;

assert(pHead != NULL);

pHead->pNext = NULL;

pTail = pHead;

}

else {

pTail->pNext = new Node;

assert(pTail->pNext != NULL);

pTail = pTail->pNext;

pTail->pNext = NULL;

}

}

void List::Insert(char *Query, Node *Pointer) {

int Match;

Node *pNewNode;

if (Pointer == NULL) {

cout<<"No match foundn";

return;

} else {

Match = strcmp(Query, Pointer->Name);

if (Match == 0) {

pNewNode = new Node;

assert(pNewNode != NULL);

pNewNode->pNext = Pointer->pNext;

Pointer->pNext = pNewNode;

}else

Insert(Query, Pointer->pNext);

}

}

void List::Print(Node *Pointer) const {

if (Pointer == NULL)

return;

cout<<"Name: "<<Pointer->Name<<"";

cout<<"Price: "<<Pointer->Price<<"";

cout<<"Number: "<<Pointer->Number<<"n";

Print(Pointer->pNext);

}

void List::Remove(char *Query) {

if (pHead == NULL) {

cout<<"The list is already emptyn";

return;

}

Node *pPrev = pHead;

Node *pTemp = pHead->pNext;

if (strcmp(Query, pHead->Name) == 0) {

pTemp = pHead;

pHead = pHead->pNext;

delete pTemp;

cout<<"Entry removed successfullyn";

return;

}

while (pTemp != NULL) {

if (strcmp(Query,pTemp->Name)==0)

break;

pPrev = pTemp;

pTemp = pTemp->pNext;

}

if (pTemp == NULL) {

cout<<"No match found";

return;

}

else {

pPrev->pNext = pTemp->pNext;

if (pTemp == pTail) {

delete pTemp;

SetTail(pHead);

cout<<"New tail of list assignedn";

return;

}

delete pTemp;

cout<<"Entry removed successfullyn";

}

}

void List::Remove_(char *Query) {

int choice;

cout<<"(1) Remove only one entry with specified namen";

cout<<"(2) Remove all entries with specified name: "; cin>>choice;

if (choice != 2) {

Remove(Query);

return;

}

while (Search(Query) == 1) {

Remove(Query);

}

}

int List::Search(char *Query) const {

Node *Pointer = pHead;

while (Pointer != NULL) {

if (strcmp(Query,Pointer->Name)==0)

return 1;

Pointer = Pointer->pNext;

}

return 0;

}

void List::SetTail(Node *Pointer) {

if (Pointer->pNext == NULL) {

pTail = Pointer;

return;

}

if (Pointer == NULL) {

pTail = pHead;

return;

}

SetTail(Pointer->pNext);

}

int menu() {

int choice;

cout<<"n(1) Add entry";

cout<<"n(2) Add entry after specified";

cout<<"n(3) Remove entry";

cout<<"n(4) Print the list";

cout<<"n(5) Quitn";

cout<<" Select action: ";

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]<='9')

number = number*10 + buffer[i] - '0';

}

returnnumber;

}

Заключение

В данном курсовом проекте был реализован абстрактный тип данных – односвязный список на основе указателей.

В процессе реализации были соблюдены принципы объектно-ориентированного программирования. Особое внимание было уделено инкапсуляции данных и разработке интерфейса, исключающего нелигитимное модифицирование данных, определенных в задании.