Односвязный список на основе указателей (стр. 2 из 2)

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

Случай удаления хвоста списка, кроме всего прочего, означает, что указатель на хвост получает значение константы 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<<"&bsol;nEnter name: "; cin>>temp;

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

break;

case (3):

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

aList.Remove_(temp);

break;

case (4):

aList.Print(aList.GetHead());

break;

case (5):

exit = true;

break;

default:

cout<<"&bsol;n-----Try to enter defined keys!-----&bsol;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 created&bsol;n";

}

List::List() {

pHead = NULL;

pTail = NULL;

cout<<"List constructor called; new list created&bsol;n";

}

List::~List() {

Node* pTemp;

while (pHead) {

pTemp = pHead;

pHead = pHead->pNext;

delete pTemp;

cout<<"Destroying the list...&bsol;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 found&bsol;n";

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<<"&bsol;n";

Print(Pointer->pNext);

}

void List::Remove(char *Query) {

if (pHead == NULL) {

cout<<"The list is already empty&bsol;n";

return;

}

Node *pPrev = pHead;

Node *pTemp = pHead->pNext;

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

pTemp = pHead;

pHead = pHead->pNext;

delete pTemp;

cout<<"Entry removed successfully&bsol;n";

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 assigned&bsol;n";

return;

}

delete pTemp;

cout<<"Entry removed successfully&bsol;n";

}

}

void List::Remove_(char *Query) {

int choice;

cout<<"(1) Remove only one entry with specified name&bsol;n";

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<<"&bsol;n(1) Add entry";

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

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

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

cout<<"&bsol;n(5) Quit&bsol;n";

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;

}

Заключение

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

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