|
Читайте также: |
МЕТА РОБОТИ
Вивчення фундаментальної абстрактної структури даних списка. Набуття практичних навичок побудови списка, дослідження динаміки його вмісту та використання списків для розв'язання прикладних задач.
2. ПОСТАНОВКА ЗАДАЧІ
Змоделювати лінійний зв'язаний одно- або двонаправлений список, реалізований за допомогою вказівників (вибір здійснити виходячи з умови задачі). Написати основні операції для роботи зі списком і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>=10) різних цілих чисел (числа вводити з клавіатури). Всі додатні і нульові числа послідовно вставляти у відповідне місце списку так, щоб список весь час залишався відсортованим по зростанню значень його елементів. Кожне від'ємне число має вилучати зі списку всі елементи, значення яких дорівнюють модулю цього від'ємного числа. Якщо в списку таких елементів не буде знайдено, то видавати відповідне повідомлення про відсутність цього числа у списку і продовжувати роботу. Виводити на екран динаміку вмісту списку під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу всіх основних операцій.
Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності визначити, чи кількість всіх парних чисел списку буде меншою за кількість непарних, чи ні.
3. ДИНАМІКА ВМІСТУ СПИСКУ
3.1. Послідовність K цілих (додатніх, від'ємних, нульових, парних і непарних) чисел
Моя послідовність: 7, 2, 1, 14, 0, 2, -2, -88, 10, 2
3.2. Схематичне зображення списку після обробки всієї послідовності
| Схематичне зображення списку після обробки всієї послідовності | |||||||||||||||||||||||||
|
data next | ||||||||||||||||||||||||
|
Free
data next |
3.3. Реалізація побудованого списку на базі масиву розмірністю 15
| Реалізація списку на базі масиву розмірністю 15 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
data next
|
3.4. Визначити, чи кількість всіх парних чисел списку буде меншою за кількість непарних, чи ні.
Кількість парних чисел більша.
4. АЛГОРИТМ РОЗВ’ЯЗАННЯ ЗАДАЧІ
Для створення лінійного зв'язаного однонаправленого списку спочатку я створив структуру цього списка у класі, а також для зручності дві структури Iterator і MutableIterator для доступу до елементів послідовності. MutableIterator дозволяє змінювати елементи, а Iterator - ні. Ітератор містить в собі покажчик на поточний елемент і на останній. Перевага такого літератора у тому що немає необхідності уточнювати тип елемента. Реалізую функції які потрібні для роботи зі списком так як вказано у методичних вказівках, а саме:
insert (pos, elem)
push_back (elem)
push_front (elem)
remove (val)
erase (pos)
clear ()
а також функції:
append() – синонім PushBack створений для зручності
+ перевантажую оператори для літераторів
Для сортування списку по зростанню я після введення кожного елемента в список перебираю всі елементи списку в циклі порівнюю їх і за допомогою функції INSERT() сортую, до того часу поки вказівник Next не дійде до кінця списку.
Для того щоб вилучити елементи при додаванні в послідовність відємного числа я використовую той самий цикл але з перевіркою чи вміст комірки рівний модулю відємного числа і якщо так то вилучаю його.
Для того щоб перевірити яких елементів більше – парних чи не парних я використовую той самий цикл тільки при цьому підраховую кількість парних і не парних елементів (парність взнаю за допомогою операції взяття по модулю), вкінці порівнюю лічильник парних і непарних і виводжу результат.
РЕЗУЛЬТАТИ ВИКОНАННЯ ПРОГРАММИ
ВИСНОВКИ
На цій лабораторній роботі я вивчив фундаментальну абстрактну структуру даних – списки. Набув практичних навичок побудови списків та провів дослідження динаміки їх вмісту.
ДОДАТКИ
#include <iostream>
#include <conio.h>
#include <assert.h>
#include <math.h>
using namespace std;
typedef struct {void *p; void *pEnd;} Iterator;
typedef struct {void *p; void *pEnd;} MutableIterator;
template <typename T>
class List
{
// Структура списка
struct ListItem
{
// посилання на наструпний елемент
ListItem* Next;
T Data;
// Конструктор за замовчуванням
ListItem(const T& init)
: Data(init)
{}
};
// Структура списка
struct ListHeader
{
int Size;
int RefCount;
// посилання на перший елемент списку
ListItem* pFront;
// посилання на значення
ListItem* pTail;
// Конструктор за замовчуванням
ListHeader()
: Size(0), RefCount(1), pFront(0), pTail(0)
{
}
ListItem* Root() const
{
return (ListItem*)(void*)&pFront;
}
} *m_header;
// Перед записуванням копіює елементи.
void CopyBeforeWrite()
{
assert(m_header);
if (m_header->RefCount == 1) return;
List<T> list;
for (ListItem* p = m_header->pFront; p!= 0; p = p->Next)
{
ListItem* item = new ListItem(p->Data);
item->Next = 0;
if (m_header->pTail!= 0) m_header->pTail->Next = item;
m_header->pTail = item;
if (m_header->pFront == 0) m_header->pFront = item;
m_header->Size ++;
}
ListHeader* t = m_header;
m_header = list.m_header;
list.m_header = t;
}
// Знищує список.
void Release()
{
assert(m_header);
if (--m_header->RefCount == 0)
{
ListItem* p = m_header->pFront;
while (p!= 0)
{
ListItem* p2 = p;
p = p->Next;
delete p2;
}
delete m_header;
}
}
public:
// Конструктор за замовчуванням
List()
: m_header(new ListHeader)
{
}
// Конструктор
List(const List<T>& list)
: m_header(list.m_header)
{
assert(m_header);
m_header->RefCount++;
}
// Вилучає всі елементи списку (контейнер залишається порожнім)
void Clear()
{
List<T> empty;
ListHeader* t = m_header;
m_header = empty.m_header;
empty.m_header = t;
}
// Додає копію елемента в початок списку
void PushFront(const T& item)
{
ListItem* li = new ListItem(item);
CopyBeforeWrite();
li->Next = m_header->pFront;
m_header->pFront = li;
if (m_header->pTail == 0) m_header->pTail = li;
m_header->Size ++;
}
// Додає копію елемента в кінець списку
void PushBack(const T& item)
{
ListItem* li = new ListItem(item);
CopyBeforeWrite();
li->Next = 0;
if (m_header->pTail!= 0) m_header->pTail->Next = li;
m_header->pTail = li;
if (m_header->pFront == 0) m_header->pFront = li;
m_header->Size ++;
}
// Той самий PushBack
void Append(const T& item)
{
PushBack(item);
}
/* Повертає ініціалізований ітератор для перерахування всіх елементів послідовності
Дозволяє використовувати ітератор всередині циклів */
operator Iterator() const
{
Iterator it;
it.p = (void*)m_header->Root();
it.pEnd = (void*)m_header->pTail;
return it;
}
// Перевантажений оператор [] для Iterator
const T& operator[](const Iterator& it) const
{
assert(it.p);
ListItem* current = ((ListItem*)it.p)->Next;
assert(current);
// Повертає поточний елемент, на який вказує ітератор.
return current->Data;
}
/* Повертає ініціалізований ітератор для перерахування всіх елементів послідовності.
Дозволяє використовувати ітератор всередині циклів: for() а також змінювати елементи */
operator MutableIterator()
{
MutableIterator it;
CopyBeforeWrite();
it.p = (void*)m_header->Root();
it.pEnd = (void*)m_header->pTail;
return it;
}
// Повертає True, якщо ітератор ще не досяг кінця послідовності.
bool HasNext(const MutableIterator& it) const
{
return ((ListItem*)it.p)->Next!= 0;
}
/* Переходить до наступного ітератора і повертає True;
Або по досягненні кінця діапазону залишає ітератор без змін і повертає false. */
bool Next(MutableIterator& it) const
{
assert(it.p);
if (it.p == 0 || it.p == it.pEnd) return false;
it.p = ((ListItem*)it.p)->Next;
return true;
}
// Перевантажений оператор [] для змінюваного оператора MutableIterator
T& operator[](const MutableIterator& it) const
{
assert(it.p);
ListItem* current = ((ListItem*)it.p)->Next;
assert(current);
// Повертає поточний елемент, на який вказує ітератор.
return current->Data;
}
// Вставляє копію item в позицію ітератора place і повертає позицію нового елемента
void Insert(const MutableIterator& place, const T& item)
{
assert(m_header->RefCount == 1);
ListItem* it = new ListItem(item);
ListItem* p = (ListItem*)place.p;
it->Next = p->Next;
p->Next = it;
m_header->Size ++;
if (m_header->pTail == p) m_header->pTail = it;
}
// Вилучає елемент в позиції ітератора place і повертає позицію наступного елемента списку
void Erase(const MutableIterator& place)
{
assert(m_header->RefCount == 1);
ListItem* p = (ListItem*)place.p;
// Неможна вилучати неіснуючий елемент вказуючий на pTail
assert(p!= m_header->pTail);
ListItem* removed = p->Next;
p->Next = removed->Next;
if (removed == m_header->pTail) m_header->pTail = p;
delete removed;
m_header->Size --;
}
// декструктор
~List()
{
Release();
}
};
void main()
{
setlocale(LC_ALL, "russian_Russia.1251");
List<int> l; // обєкт списку
int num; // число з клавіатури
MutableIterator it = l; // ітератор
//Зчитуємо 10 чисел
for(int i = 0; i < 10; i ++)
{
cout << endl;
cout << "Введiть число: ";
cin >> num;
if(num >= 0) // якщо число рівне 0
{
// заносимо в список
bool b = false;
if(i == 0) l.Append(num);
if(i > 0)
{
it = l;
//або заносимо по зростанню поки не відсотуємо всі елементи
while(l.HasNext(it))
{
if(l[it] > num){ l.Insert(it, num); b = true; break;}
l.Next(it);
}
if(b!= true) l.Append(num);
}
it = l;
// виводимо весь список
cout << "=============================" << endl;
cout << "Вмiст списку: " << endl;
while(l.HasNext(it))
{
cout << l[it] << " ";
l.Next(it);
}
cout << endl << "=============================" << endl;
}
//якщо число менше 0
else
{
bool mes = false;
it = l;
//видаляємо елементи == йому по модулю
while(l.HasNext(it))
{
if(l[it] == abs(num)){ l.Erase(it);it = l; mes = true;}
l.Next(it);
}
it = l;
//виводимо весь список
cout << "=============================" << endl;
cout << "Вмiст списку: " << endl;
while(l.HasNext(it))
{
cout << l[it] << " ";
l.Next(it);
}
//якщо потрібно виводимо повідомлення що елементів не знайдето
if(!mes)
cout << endl << "Елементiв для видалення не знайдено." << endl;
cout << endl << "=============================" << endl;
}
}
// рахуєм парні та не парні числа
int tak = 0, ni = 0;
it = l;
while(l.HasNext(it))
{
if(l[it]%2 == 0) tak ++;
else ni ++;
l.Next(it);
}
cout << endl << endl;
if(tak > ni) cout << "Бiльше парних, а саме - (" << tak << ")";
if(tak < ni) cout << "Бiльше не парних, а саме - (" << ni << ")";
if(tak == ni) cout << "Одинакова кiлькiсть парних i не парних.";
getch();
}
Дата добавления: 2015-11-14; просмотров: 29 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Chill Mould Casting | | | Constitutional law |