Реферати

Курсова робота: Односвязний список на основі покажчиків

Коала 2. КОАЛА (Phascolarctos cinereus) безсумнівно, саме цікаве й улюблене австралійцями сумчаста тварина. Слово "коала" мовою племен Нового Південного Уельсу означає "не пити". Перше згадування про коала міститься в звіті невідомого автора про подорож у Блакитні гори в 1798 р. Автор звіту пише, що в Блакитних горах є тварина, називане куллавайн, що нагадує зовні південноамериканського лінивця.

Оздоровчі методики і системи в РФ. Система Купера й Амосова. МІНІСТЕРСТВО УТВОРЕННЯ І НАУКИ РФ МОУ "ВОЛЗЬКИЙ ІНСТИТУТ ЕКОНОМІКИ ПЕДАГОГІКИ І ПРАВА" Кафедра фізичної культури Реферат по фізичній культурі

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

Шпаргалка по Психології 2. 25. Структура діяльності, її комnоненти, універсальні асnекти. Діяльність - специфічно человеч. форма активного відношення до навколишнього світу, зміст до-рій складає його доцільна зміна і перетворення. Д. чоловік припускає определ. протиставлення суб'єкта й об'єкта Д.: людина противополагает собі об'єкт Д. як матеріал, к-рий повинний одержати нову форму і св-ва, перетворитися з матеріалу в продукт Д.

Звіт по переддипломній практиці інспектора по кадром. Федеральне агентство по утворенню ГОУ ВПО Уральський державний технічний університет - УПИ Факультет гуманітарного утворення Кафедра Соціальної антропології і психології

Зміст

Введення

1. Визначення АТД

2. Загальні положення

3. Опис операцій

3.1 Операція додавання елемента

3.2 Операція додавання елемента після вказаного

3.3 Операція видалення вказаного елемента

3.4 Операція роздруку записів списку

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

4.1 Головна функція

4.2 Інтерфейс

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

Висновок

Список літератури

Додаток А: графи-схеми алгоритмів

Введення

Незалежно від типу задач, що вирішуються, будь-яка програма оперує якимись даними, а сама програма предстваляет собою методи управління і обробки цих даних. Швидкість виконання програмою поставленої задачі залежить не тільки від алгоритмів, використаних в ній для обробки і управління даними, але також і від самої організації даних. Таким чином, ми приходимо до поняття про структури дані.

Пряма взаємодія між програмою через користувача і структурами даних залишає відкритими безліч даних, модифікація яких нелегітимним способом (минуя інтерфейс) може привести до небажаних наслідків. Щоб минути дану проблему необхідно "звести стіни" між даними і програмою, залишивши лише "віконце" у вигляді інтерфейса. Для цього необхідно визначити абстрактні типи даних, за допомогою яких ці стіни споруджуються.

У даній роботі розробляється абстрактний тип даних (АТД) - список, який згодом реалізовується у вигляді зв'язного списку, реалізованого за допомогою непрямої адресації, заснованій на покажчиках. Більш детально питання розробки АТД розглядаються в [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. Оскільки список в цьому випадку складається лише з одного вузла, то для виконання умови связности непустого списку покажчик на хвіст повинен вказувати на останній створений вузол - в цьому випадку на голову. Цей факт і складає основну відмінність між двома процесами додавання елемента, оскільки в цьому випадку пам'ять виділялася для першого елемента, а в інших випадках - для останнього.

Операція додавання (за умовчанням) елемента в пустий список:

Операція додавання елемента в кінець списку:

Макрос assert, визначений в бібліотеці cassertпроверяет чи була виділена пам'ять під вузли коректним образом.

3.2 операциЯ додатки елемента після вказаного

Операція додавання елемента після вказаного сильно відрізняється від вже розробленої операції додавання елемента в список і перед-, постусловия попередньої операцій будуть неповними в даному контексті. Передусім це пов'язано з тим, що вводиться вирішальний чинник існування (або не існування) елемента, що указується користувачем на ім'я. У разі неіснування елемента, вказаного користувачем, вставка стає неможливою.

До того ж, необхідно спочатку знайти вказаний елемент або виявити ознаку його відсутності. Для цієї мети необхідно зробити обхід списку. Оскільки список неврегульований ми не можемо застосувати бінарний пошук, який значно більш ефективний, ніж послідовний - його складність порядку Про (log2n) проти О (n), т. е., наприклад, при кількості записів 106, алгоритм бінарного пошуку знайде елемент в гіршому випадку за 19 тактів, в той час як послідовний - за 106тактов. Основні алгоритми пошуку і сортування детально розглянуті в [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 created\n";

}

List::List() {

pHead = NULL;

pTail = NULL;

"cout < < List constructor called; new list created\n";

}

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 found\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 < < \n";

Print(Pointer- > pNext);

}

void List::Remove(char *Query) {

"if (pHead == NULL) {

cout < < The list is already empty\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\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\n";

return;

}

delete pTemp;

"cout < < Entry removed successfully\n";

}

}

void List::Remove_(char *Query) {

int choice;

cout < < " (1) Remove only one entry with specified name\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 < < \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) Quit\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;

}

Висновок

У даному курсовому проекті був реалізований абстрактний тип даних - односвязний список на основі покажчиків.

У процесі реалізації були додержані принципи об'єктно-орієнтованого програмування. Особлива увага була приділена інкапсуляції даних і розробці інтерфейса, що виключає нелигитимное модифікування даних, визначених в завданні.