Перевод списка в массив и обратно
Главное преимущество списка перед массивом в том, что в него можно добавлять элементы, не имея ограничений. Это может применяться когда мы точно не знаем сколько именно нам нужно будет элементов. А потом, когда мы закончим ввод данных, можно перенести всё в массив.
Конечно, во многих случаях обычно берут просто число элементов массива про запас, например тысячу- и потом просто оставляют ненужные элементы пустыми. Но проблема в том, что во-первых всё равно есть ограничение, а во-вторых этот огромный массив "про запас" перегружает оперативную память и занимает много места. Использование списков позволит сэкономить память и сделать программу более оптимизированной.
К слову, удалить лишний последний элемент в списке тоже проще и быстрее чем в массиве.
Можно один раз написать класс для списка и просто использовать его, копируя из программы в программу как шаблон. Или сделать даже отдельный заголовочный файл для этого класса и добавлять просто класс.
Мы сделаем стопку шаблонной, чтобы можно было заносить туда элементы любого типа. И вот ниже будет представлен весь заголовочный файл. В класс стопки мы добавим дополнительные важные методы. Саму же стопку мы переименуем в список для удобства.
#ifndef KATMUR_LIST
#define KATMUR_LIST
#include <iostream>
using namespace std;
////////////////////////////////////
// тарелка тоже шаблонная- т.к. инфополе может принимать значение любого типа данных, а не только int как было раньше
|
|
|
template <typename Type>
class tarelka {
public:
Type info;
tarelka *next;
tarelka () { next= NULL; }
};
template <typename Type>
class spisok {
tarelka <Type> *first;
public:
tarelka <Type> *current;
// конструкторы
spisok(Type a) {
current= new tarelka <Type>;
current->info= a;
first= current;
}
spisok() {
current= new tarelka <Type>;
first= current;
}
// поменять значение текущего элемента
void change(Type a) { current->info= a; }
// значение текущего элемента (тарелки)
Type value() { return current->info; }
// подняться наверх на 1 тарелку
void goup () { current= current->next; }
// добавить новую тарелку и подняться наверх
void push (Type a) {
tarelka <Type> *up= new tarelka <Type>;
current->next= up;
up->info= a;
up->next= NULL;
goup();
}
|
|
|
// значение верхнего элемента
Type top() {
while (current->next!=NULL) goup();
return current->info;
}
// удалить верхний элемент списка
void pop() {
current= first;
if(first->next!=NULL) {
while (current->next->next!=NULL) goup();
current->next= NULL;
delete current->next;
}
}
// удалить весь список
void del() {
current= first;
while(first->next!=NULL) pop();
current= first= NULL;
delete current; delete first;
cout << "The stopka has been deleted" << endl;
}
// размер списка- сколько в нём элементов
int size() {
if(first==NULL) return 0;
else {
current= first;
int n= 1;
if(first->next!=NULL) {
|
|
|
while (current->next!=NULL) {
goup();
n++;
}
}
current= first;
return n;
}
}
// n-й элемент начиная снизу (по сути мы делаем возможным лёгкое обращение к любому элементу из всего списка)
Type nvalue(int n) {
current= first;
if(n==1) return current->info;
else {
for (int i=2; i<=n; i++) goup();
return current->info;
}
}
// максимальный и минимальный элементы
Type max() {
current= first;
Type m= nvalue(1);
|
|
|
for(int i=2; i<=size(); i++) if(nvalue(i)>m) m= nvalue(i);
return m;
}
Type min() {
current= first;
Type m= nvalue(1);
for(int i=2; i<=size(); i++) if(nvalue(i)<m) m= nvalue(i);
return m;
}
// копирование списка
spisok <Type> copy() {
spisok <Type> res(nvalue(1));
if(size()>1) {
for(int i=2; i<=size; i++) res.push(nvalue(i));
}
}
};
// вывод списка
template <typename Type>
ostream& operator<<(ostream& str, spisok <Type> & x) {
for (int i=1; i<=x.size(); i++) cout << x.nvalue(i) << " ";
return str;
}
// перевод списка в массив
template <typename Type>
Type *ListToArray (spisok <Type> x) {
Type *res= new Type [x.size()];
for(int i=0; i<x.size(); i++) res[i]= x.nvalue(i+1);
return res;
}
// перевод массива в список
template <typename Type>
spisok <Type> ArrayToList (Type x[], int size) {
spisok <Type> res(x[0]);
if(size>1) {
for(int i=2; i<=size; i++) res.push(x[i-1]);
}
return res;
}
#endif
Добавление и удаление в середине списка
Ещё одной из особенностью списка является то что мы можем спокойно вырезать в середине какой-то элемент или добавлять новый- при этом не надо как в массиве выделять для этого новый порой огромный блок памяти. В этой главе как раз будут показаны такие функции.
Для начала добавим в поле private вспомогательную функцию, которая будет возвращать тарелку с указанным номером:
tarelka <Type> *ntar (int n) {
current= first;
if(n==1) return current;
else {
for (int i=2; i<=n; i++) goup();
return current;
}
}
Далее напишем эти 2 функции- добавления и удаления. Начнём с добавления. Будут некие малые отличия от того куда мы добавляем. Если мы добавляем в середину, то там своя схема. Если же на самое дно- то немного надо изменить алгоритм и учесть что этот новый элемент станет теперь первым.
void add (Type a, int n) {
// если n=0, т.е. добавляем на самое дно
if(!n) {
tarelka <Type> *p= new tarelka <Type>;
p->info= a;
p->next= first;
first= p;
}
// добавляем поверх n-го элемента
else {
current= ntar(n); // переместились на энную тарелку- именно на неё мы будем класть новую
tarelka <Type> *p= new tarelka <Type>; // создали новую тарелку
p->info= a; // присваиваем инфополе
p->next= current->next; // присваиваем куда она должна вести
current->next= p; // текущая тарелка где мы стоим теперь будет вести на новую нами созданную тарелку
}
}
Теперь функция удаления n-го элемента. Тут уже 3 случая: первый, последний и средний. Если последний, то используем стандартный метод pop().
void cut (int n) {
if(n==size()) pop();
else if (n==1) {
current= first; // встанем на первой
first= current->next; // первой тарелкой теперь будет та которая выше, потому что текущую мы удалим
current->next= NULL; // удаляем ссылку на новую уже первую
current= NULL; // удаляем саму старую первую
}
else {
current= ntar(n-1); // встанем ниже той, которую хотим удалить
tarelka <Type> *p= new tarelka <Type>; // вспомогательная переменная для тарелки
p= current->next; // та которую удаляем
current->next= p->next; // с той которую стоим меняем ссылку на следующую теперь на ту что была следующей для той которую мы удаляем
p= NULL; // удаляем
}
}
Деревья
Ссылочные данные могут быть организованы не только линейно, но и разветвлённо. И особо важное значение тут имеет такой способ организации данных как дерево.
Я вставил рисунок, чтобы сразу было всё понятно. Самый верхний элемент называется корнем. Все элементы называются узлами. Последние элементы (в данном случае 2, 5, 11, 4) называются листьями. Для узла элементы ниже называются сыновьями. Например, у корня 2 сына- левый (7) и правый (5). У элемента 5 справа только 1 сын (9). У листьев сыновей нету. В обратную сторону- можно считать узлы выше родительскими. Например, для узла 11 родительским будет 6. Также есть термин "потомки"- это все элементы ниже. Например, для узла 7 будут потомки 2, 6, 5, 11.
Выше нарисовано бинарное (двоичное) дерево- тут каждый узел имеет не более 2 сыновей. В общем случае сыновей может быть сколько угодно.
...
Посмотрим как реализовать дерево на программном уровне. Рассмотрим двоичное дерево, оно используется чаще чем остальные. Мы будем использовать 2 класса: класс узла и класс собственно дерева.
Класс узла выглядит так:
class node {
public:
int info; node *left,*right,*parent;
node() { info=0; parent=NULL; right=NULL; left=NULL; }
};
В классе узла (по-английски node) у нас хранится 4 параметра: само информационное поле (int info) и 3 указателя- на левого сына, правого сына и на родительский узел.
Далее идёт конструктор класса, который присваивает значения по умолчанию. NULL это значит ничего, т.е. пусто.
Теперь класс самого дерева- он у нас будет состоять из указателя на текущий узел и различных функций (методов)- типа перейти в одну сторону, другую и прочее.
class tree {
public:
node *current; // указатель на текущий узел
tree() { current = new node; } // конструктор
// создать левый узел
void createL(int num) {
node *p = new node;
current->left = p;
p->info=num;
p->parent = current;
}
// создать правый узел
void createR(int num) {
node *p = new node;
current->right = p;
p->info=num;
p->parent = current;
}
// переместиться на левого сына
void goL() { current = current->left; }
// переместиться на правого сына
void goR() { current = current->right; }
// переместиться на родительский узел
void goUP() { current = current->parent; }
// присвоить информационному полю значение
void change(int a) { current->info = a; }
// вывести значение информационного поля
void get() { cout<< current->info << endl; }
// нарисовать дерево (начиная с корня)
void print(node *root,unsigned k=0) {
if (root != NULL) {
print(root->left, k + 3);
for(unsigned i = 0; i < k; i++) cout<<" ";
cout<< root->info << endl;
print(root->right, k + 3);
}
}
// удалить дерево
void del() {
if (current->parent->left==current) {current->parent->left=NULL;}
if (current->parent->right==current) {current->parent->right=NULL;}
delete current;
}
};
И далее мы можем это использовать в программе, например:
tree t; // создаём пустое дерево
node *root = t.current; // запоминаем корень
// заполняем дерево значениями
t.change(3);
t.createL(8);
t.goL();
t.createL(1);
t.createR(0);
t.goUP();
t.createR(5);
t.goR();
t.createL(4);
// выводим получившееся дерево
t.print(root);
Есть много различных вариаций деревьев, например двоичное дерево поиска, всякие способы балансировки деревьев и прочее, что можно про все эти структуры данных и методы работы с ними целую книгу писать, но мы это тут рассматривать не будем по ненадобности. Здесь мы на простом и поверхностном уровне рассмотрели, что представляет из себя двоичное дерево на программном уровне, на этом будет достаточно.
________________________________________________
РАЗДЕЛ 4
РАБОТА С ГРАФИКОЙ ЧЕРЕЗ SFML
Установка SFML
SFML или Simple and Fast Multimedia Library- простая и быстрая мультимедийная библиотека. Это высокоуровневая библиотека, по которой мы можем научиться делать графические вещи на с++ без лишних усложнений в плане кода, чтобы сконцентрироваться больше на алгоритмах обработки изображений и т.п. Позже посмотрим более низкоуровневую, но и универсальную библиотеку- OpenGL.
SFML полностью бесплатна и скачать её можно на официальном сайте sfml-dev.org. Либо у меня с яндекс диска, где я собрал также все необходимые dll файлы для работы программ:
https://yadi.sk/d/nrm4h6O13KZV5j
Мы скачиваем архив, разархивируем и помещаем всю папку на диск С для удобства.
Инструкция для devcpp:
1. Создаём проект windows forms и всё стираем.
2. Заходим в параметры проекта
3. Вкладка "Параметры", колонка "Linker". Прописываем туда:
-lsfml-audio
-lsfml-graphics
-lsfml-system
-lsfml-window
4. Вкладка "файлы/каталоги", колонка "библиотек". Добавляем ссылку на папку lib: C:\SFML-2.4.2\lib
Аналогично "файлов включения" и C:\SFML-2.4.2\include
5. Подтвердить
6. Вставить тестовый код, скомпилировать, проверить
7. Добавить dll файлы из папки bin в папку с проектом. Также м.б. понадобится установить дополнительные dll файлы на компьютер.
Также все эти dll файлы мы перемещаем в папки system32 (для 32-битных файлов) и sysWOW64 (для 64-битных файлов)
Тестовый код:
#include <SFML/Graphics.hpp>
int main()
{
sf::RenderWindow window(sf::VideoMode(200, 200), "SFML works!");
sf::CircleShape shape(100.f);
shape.setFillColor(sf::Color::Green);
while (window.isOpen())
{
sf::Event event;
while (window.pollEvent(event))
{
if (event.type == sf::Event::Closed)
window.close();
}
window.clear();
window.draw(shape);
window.display();
}
return 0;
}
Должно запуститься окошечко и вывестись зелёный кружочек. Если потребует какие-то dll файлы, то докачать и установить в system32 и sysWOW64. Версия SFML может отличаться, т.к. периодически выходят новые, но это не принципиально- установка одинаковая для всех версий, просто имя папки вместо SFML-2.4.2 будет другое и соответственно с этим при установке тоже прописывать эти другие имена папки.
...
Как только у тебя всё заработало, можно приступать к дальнейшему обучению.
Для начала обратимся к этому куску кода:
sf::RenderWindow window(sf::VideoMode(200, 200), "SFML works!");
sf::CircleShape shape(100.f);
shape.setFillColor(sf::Color::Green);
Здесь ты можешь поменять размер начального окна (VideoMode), заголовок окна (следующий аргумент), радиус круга (вместо 100 написать другой) и цвет этого круга (третья строчка)- поэкспериментируй с этим. И после этого мы идём дальше- создавать нашу первую игру.
Дата добавления: 2018-09-22; просмотров: 322; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!