Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Алгоритмізація та програмування
Частина тексту файла (без зображень, графіків і формул):
Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
Кафедра АПЕПС
Алгоритмізація та програмування - 2. Процедурне програмування
ЗВІТ
до лабораторної роботи № 3
«Списки»
Варіант № 18
Дата «10» червня 2022
ЗАВДАННЯ:
1. Дослідити особливості створення одно- та дво-направлених списків.
2. Вивчити і реалізувати механізми додавання нових записів у список, пошуку записів у списку за певними полями, видалення записів зі списку та редагування знайдених записів, а також збереження всього списку у файлі та зчитування списку із файлу до пам’яті з відновленням всіх зв’язків.
3. Розробити Блок-схему програмного алгоритму.
4. Оформити ЗВІТ до лабораторної роботи згідно вимог та методичних рекомендацій.
РЕЗУЛЬТАТ РОБОТИ:
1. Роздрукувати (вивести на екран) попередньо сформовані та підготовлені для запису в файл дані.
2. Роздрукувати (вивести на екран) результат виконання операції читання даних із файлу.
3. ЗВІТ до комп’ютерного практикуму для перевірки додати в Клас.
4. Програмний код (відкритий для редагування) розмістити на сайті Repl.it (посилання виключно через кнопку «+Invite »).
Теоретичні відомості:
Елемент списку є складовою (структурованою) змінною, що містить збережені дані і покажчики на сусідів:
struct elem { // визначення структурованого типу
int value; // значення елемента (збережені дані)
elem *next; // єдиний покажчик
//elem *next,*prev; // два покажчика
elem *links[10]; // обмежена кількість покажчиків (максимум 10) //elem **plinks; // довільна кількість покажчиків
};
Як видно з прикладу, змінна такого типу може містити одну, дві, не більше 10 і довільну (динамічний масив) кількість вказівників на аналогічні змінні. Але це ще не список, а опис його складових (елементів) як типу даних. З нього випливає тільки, що кожен з них посилається на аналогічні елементи. Ніяк не можна визначити ні кількості таких змінних в структурі даних, ні характеру зв’язків між ними (послідовний, циклічний, довільний).
Отже, конкретний тип структури даних (лінійний список, дерево, граф) залежить від функцій, які з нею працюють.
Залежно від зв’язків списки бувають наступних видів:
• однозв’язні – кожен елемент списку має покажчик на наступний;
• двозв’язні – кожен елемент списку має покажчик на наступний і на попередній елементи;
• циклічні – перший і останній елементи списку посилаються один на одного і ланцюжок представляє собою кільце.
Звідси ж випливає, що звичайні (розімкнуті) списки мають в якості обмежувача послідовності NULL-покажчик. Відповідно, можливий випадок пустого списку, в якому заголовок – покажчик на перший елемент також містить значення NULL.
Бінарне дерево – це впорядковане дерево, кожна вершина якого має не більше двох піддерев, причому для кожного вузла виконується правило: в лівому піддереві містяться тільки ключі, що мають значення, менші, ніж значення даного вузла, а в правому піддереві містяться тільки ключі, що мають значення, більші, ніж значення даного вузла.
Дерево складається з гілок (вузлів) і листя (елементів). Листя – це вузли, які не вказують ні на кого, у них немає гілочок. Бінарне дерево – це дерево, в якому у гілки може бути не більше двох листів або гілок. Звідси і його назва – «бінарне», тобто елементів два або менше. Але ніяк не більше двох.
Розглянемо структуру, що описується як динамічний список: Поле даних і два покажчика на праву і ліву гілки. У динамічних списках два покажчика зазвичай пов’язують наступний і попередній елементи, у випадку з деревом цього не знадобиться, оскільки, як правило, прохід по дереву йде з кореня. Хоча звичайно ж може бути і зворотний зв’язок.
struct Branch
{
char Data;
Branch *LeftBranch;
Branch *RightBranch;
};
Поле Data представляє дані, на підставі яких будується дерево. Точніше один з елементів даних. Поля Branch описують ліву і праву гілки дерева, і є покажчиками на таку ж структуру.
Елементами дерева можуть бути будь-які значення. Масиви, рядки, інші дерева. Полів з даними може бути безліч. На кожне поле можна будувати своє дерево.
Варіант індивідуального завдання:
/
Опис програми:
Програма використовує список для збереження даних, що вводить користувач. Операції над списком здійснюються за допомогою функцій. Інформація про кожний автобус записується в окремому файлі, з яких вона може бути зчитана програмою при запиті користувача.
Результат програми:
/
Файл BusStationN0.txt:
/
Файл BusStationN1.txt:
/
Файл BusStationN2.txt:
/
Висновок: Написано програму, що використовує фунціонал списку для збереження даних, введених користувачем. Дані зберігаються у файлах, запис інформації здійснено за допомогою окремих функцій.
Посилання на replit: https://replit.com/join/guvppleqbn-okseniait
Код:
//Черкас Оксана 10.06.2022 Лабораторна робота №4 Алгоритмізація та програмування 18 варіант
#include <iostream>
#include <fstream>
#include "string"
using namespace std;
//Створення об'єкту Node (вузел)
template<typename T>
class Node{
public:
Node *pNext;
T data;
Node(T data = T(), Node *pNext = nullptr){
this->data = data;
this->pNext = pNext;
}
};
//Створення об'єкту List (список)
template<typename T>
class List{
public:
~List();
List();
int GetSize(){
return SIZE;
}
//Функціії роботи зі списком
void pushAway(T data);
T& operator[](const int index);
int Search(T Data);
void remove(int index);
void Write(std::string filename);
void Read(std::string filename);
private:
int SIZE;
Node<T> *pHead;
};
int main() {
int num=0;
//Введення кількості автобусів
printf("Кількість автобусів: ");
scanf("%d",&num);
List<string> lst[num];
string str;
//Введення даних користувачем
for(int i = 0;i < num;i++){
cout << "\nАвтобус номер " << i+1 << ":" <<"\nПункт призначення: ";
cin >> str;
lst[i].pushAway(str);
cout << "Дні проходження: ";
cin >> str;
lst[i].pushAway(str);
cout << "Час прибуття: ";
cin >> str;
lst[i].pushAway(str);
cout << "Час стоянки: ";
cin >> str;
lst[i].pushAway(str);
}
//Створення файлу для кожного з автобусів та виклик функції для запису даних у файл
string filename[num];
for(int i = 0;i < num;i++){
filename[i] = "BusStationN" + to_string(i) + ".txt";
lst[i].Write(filename[i]);
}
//Виведення інформації, що зчитується з файлу, який обирає користувач
int fileId=0;
List<string> readlst;
cout << "\nВведіть номер автобуса: ";
cin >> fileId;
readlst.Read(filename[fileId-1]);
cout << "Пункт призначення: " << readlst[0] << "\nДні проходження: " << readlst[1] << "\nЧас прибуття: " << readlst[2] << "\nЧас стоянки: " << readlst[3] << endl;
return 0;
}
template<typename T>
List<T>::List(){
SIZE = 0;
pHead = nullptr;
}
template<typename T>
T & List<T>::operator[](const int index){
int count = 0;
Node<T> *current = this->pHead;
while(current != nullptr){
if(count == index){
return current->data;
}
current = current->pNext;
count++;
}
}
template<typename T>
void List<T>::pushAway(T data){
if(pHead == nullptr){
pHead = new Node<T>(data);
}
else{
Node<T> *current = this->pHead;
while(current->pNext != nullptr){
current = current->pNext;
}
current->pNext = new Node<T>(data);
}
SIZE ++;
}
template<typename T>
void List<T>::remove(int index){
if(index == 0){
Node<T> *first = this->pHead;
pHead = first->pNext;
delete first;
SIZE --;
}
else{
Node<T> *prev = this->pHead;
for(int i = 0;i < index - 1;i++){
prev = prev->pNext;
}
Node<T> *next = prev->pNext;
prev->pNext = next->pNext;
delete next;
SIZE--;
}
}
template<typename T>
List<T>::~List(){
for(int i = 0;i < SIZE;i++){
remove(i);
}
}
template<typename T>
void List<T>::Read(std::string filename){
std::ifstream file;
file.open(filename);
if(SIZE != 0){
while(SIZE != 0){
this->remove(0);
}
}
std::string input;
while(file >> input){
this->pushAway(input);
}
file.close();
}
template<typename T>
void List<T>::Write(std::string filename){
std::ofstream file;
file.open(filename);
if(SIZE != 0){
Node<T> *current = this->pHead;
while(current->pNext != nullptr){
file << current->data << std::endl;
current = current->pNext;
}
file << current->data;
}
file.close();
}
template<typename T>
int List<T>::Search(T Data){
Node<T> *current = this->pHead;
for(int i = 0;i < SIZE;i++){
if(current->data == Data){
return i;
}
current = current->pNext;
}
return -1;
}
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора