+214.71
195 читателей, 198 топиков

Очередь

Очередь – структура данных состоящая из упорядоченного набора элементов, в котором элементы могу вставляться только с одного конца, а удалятся только с другого конца, конец с которого идет удаление называется – начало очереди, конец с которого идет вставка – конец очереди. Очередь основана на принципе обслуживания в порядке поступления, реализует принцип FIFO. Элемент в начале очереди называют первым элементом, процедура добавление элемента – постановка очереди, удаление – удаление из очереди. Возможен более гибкий тип очереди, который называется, который называется очередь по приоритету. Очереди – это не ошибки, часто используются в программах моделирования, так как они часто возникают в реальной жизни. Очередь по приоритету – та же очерь, но сохраняет элементы вместе со значением приоритета для каждого элемента. При удаление элементы с высшим приоритетом выходя первыми если при этом есть несколько элементов с разными элементами они идут в порядке вхождения в очередь.
Кольцевая очередь – разновидность обычной очереди. Отличие в том что элемент, который вышел из очереди не теряется без возратно а перемещается в конец очереди.
  • avatar
  • 0
  • 0

Примеры функций

Пример использования функции getchar

#include<cstdio>
 
intmain ()
{
  charcharacter;
  puts("Введите символ, символ точки - выход('.'):");
  do
  {
    character = getchar(); // считать введённый спотока ввода символ
    putchar(character);   // вывести этот символ
  } while(character != '.'); //пока введенный символ не точка
  return0;
}


Пример использования функции putchar для печати алфавита

#include <cstdio>
 
intmain ()
{
  for(charc = 'A'; c <= 'Z'; c++)
      putchar©;   // вывод на экран символ внглийского алфавита
  return0;
}


Пример использования функции gets

#include<iostream>
#include <cstdio>
 
intmain()
{
  charstring [256];
  std::cout<< "Введите свой полный адрес: ";
  gets(string); // считать строку из стандартного потока ввода
  std::cout<< "Вашадрес: "<< string;
  return0;
}

Пример использования функции puts

#include<cstdio>
 
intmain()
{
  charstring[] = "Войны выигрывают люди, а не магические фокусы.";
  puts(string);                                        // вывод на экран
}


Пример использования функции strcat
#include<iostream>
#include <cstring>
 
intmain()
{
  charstr[100];
  strcpy(str, "Эти ");                // скопироватьстроку "Эти" вstr
 
  // добавить к строке str строку, передаваемую во втором параметре
  strcat( str, "строки "          );
  strcat( str, "объединены "    );
  strcat( str, "операцией "      );
  strcat( str, "конкатенации.");
 
  std::cout<<str<<std::endl;
  return0;
}


Пример использования функции strncat
#include<iostream>
#include <cstring>
 
intmain()
{
  charstr1[40];
  charstr2[40];
 
  strcpy(str1,"Быть ");       // скопировать строку "Быть" в str1
  strcpy(str2,"или не быть"); // скопировать "или не" и добавить к строке str2
 
  strncat(str1, str2, 11);    // объединить строки str1 и str2
  std::cout<< str1 <<std::endl;
  return0;
}

Пример использования функции strchr
#include<iostream>
#include<cstring>
 
intmain ()
{
  charlotr[] = "_-=Властелин к0лец=-_";               // строка в которой будем искать символ 0
 
  std::cout<< "Ищите кольцо всевластия в LOTR!!!n";
  char* ring = strchr(lotr, '0');                     // поиск символа 0 в строке lotr
 
  std::cout<< "Моя прелесть находится в "
            << (ring - lotr + 1) << " квадратеn";     // определяем позицию символа
 
  return0;
}


Пример использования функции strrchr
#include<iostream>
#include <cstring>
 
intmain ()
{
  charstr[] = "АвтономнаяРеспубликаКрым";
  char* pch = strrchr(str,'м');
  std::cout<< "Последнее вхождение символа 'м' - "<< (pch - str + 1) << " позицияn";
  return0;
}


Пример использования функции strcmp


#include<iostream>
#include <cstring>
 
intmain ()
{
  charfruit[] = "яблоко";                         // загаданныйфрукт
  charanswer[80];                                 // строка-ответ
 
  do
  {
     std::cout<< "Угадайте мой любимый фрукт! >> ";
     std::cin  >> answer;
  } while( strcmp(fruit, answer) != 0);           // пока фрукт не отгадан, цикл будет работать
 
  std::cout<< "Правильный ответ!n";
  return0;
}


Пример использования функции strncmp

#include<iostream>
#include <cstring>
 
int main()
{
  chardroids[][10] = { "R2D2", "C3PO", "R2A6"};                           
 
  std::cout<<  "Ищете R2-дроидаастромеханика...n";
 
  for(intcounter = 0 ; counter <= 2 ; counter++) // проходподроидам
    if( strncmp( droids[counter], "R2**", 2 ) == 0 ) //сравниваем первые два символа строк
    {
        std::cout<< "дроид [+_+] >> "<<droids[counter] << "n";
    }
  return0;
}

Пример использования функцииstrcspn

#include <iostream>
#include <cstring>
 
int main()
{
  charstr[] = "LOST: 4-8-15-16-23-42";
  charkeys[] = "1234567890";
 
  // поиск первого вхождения в строку str любого из символов строки keys
  intix = strcspn(str, keys);
  std::cout<<  "Позиция первой цифры в искомой строке: "
            << (ix + 1) << "n";              // позиция найденной цифры
  return0;
}


Пример использования функции strlen

#include<iostream>
#include <cstring>                        // дляstrlen
 
int main()
{
  charinput[256];
  std::cout<< "Введитестроку: ";
  std::cin>> input;
  std::cout<< "Строка "<< input << " содержит "<<strlen(input) << " символов\n";
  return0;
}


Пример использования функции strpbrk
#include <iostream>
#include <cstring>
 
int main()
{
  charstr[] = "Police Academy";
  charkey[] = "aeiou";
 
  std::cout<< "Поискгласныхбукввстроке "<< """ <<str<< ""n";
  char* pch = strpbrk(str, key);                            // первыйпоиск
 
  while(pch != NULL)                                         // пока есть гласные буквы в строке
  {
      std::cout<< *pch<< " ";                               // печать гласного символа
    pch = strpbrk(pch+1,key);                                // поиск гласных букв
  }
 
  std::cout<< "n";
  return0;
}
  • avatar
  • 0
  • 0

Стэк

Динамические структуры данных – это динамические объекты, которые способны при необходимости выделять память под новые элементы или удалять выделенную память для ненужных элементов по ходу программы. Существует несколько видом динамических структур данных, наиболее известные из них – стэки, связные списки разных видов, двоичные деревья, графы. Каждая из таких структур обладает своими плюсами и минусами, выбор одной из них зависит от решаемой задачи. Стэки и очереди достаточно похожи друг на друга. По сути они отличаются только правилом определяющим какой элемент удаляется из структуры первого
Стэк – это структура данных состоящая из упорядоченного набора элементов, доступ к которым осуществляется только с одного конца, подчиняется правилу(LIFO–первым пришел, последним ушел). Элементы стэка должны удалятся в порядке обратном тому, в котором они помещаются в стэк. Добавление элементов в стэк называют заталкивание, удаление – выталкивание.

Немного отвлечемся от нашего стэка, вы когда общались с помощью — DrugVokrug. Если нет, то попробуйте, интересная альтернатива аське.

Применение стэка
1.Большинство компиляторов используют их для анализа синтаксиса программы.
2.Для хранения локальных переменных при исполнении программы.
3.Стэки могут использоваться для алгоритма поиска в других динамических структурах.
Основные ошибки:
1. Попытка занести элемент в полный стэк(переполнение стэка).
2. Попытка извлечь элемент из пустого стэка(исчерпание).
Стэк можно реализовывать на основе массива или связанного списка, в случае связанного списка нет ограничения на кол-во элементов в стэке. Стэк характеризуется базовым адресом и указателем на вершину стэка (top).
Алгоритм работы функции
1. Функция просматривает символы строки.
2. Любой символ отличный от скобки игнорируется.
3. Каждый раз, когда функция встречает открывающию скобку, он заносит ее в стэк.
4. Каждый раз когда она встречает закрывающию скобку из стэка удаляется открывющая.
5. Если строка закончена и стэк пуст, функция возвращает true, если стэк пуст в момент, когда нужно извлечь очередной символ или на момент окончания строки в стэке что-то осталось, функция возвращает false.
  • avatar
  • 0
  • 0

Указатели на объекты

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

Статические элементы класса
Данные элементы класса объявляют с спецификатором static (и нельзя с спецификаторами auto, extern, register)таким образом память под статические поля резервируется при запуске программы. То есть до того, как явно создаётся 1 объект данного типа. При этом все объекты используют эту единственную, заранее созданную копию статического члена. Статический член класса должен быть инициализирован после определения класса и до 1 описания объекта этого класса. При такой инициализации используют полное имя статического члена.

На статические данные класса распространяется правила статуса доступа. Если статические данные имеют статус private, обращение только через функции, методы, классы. То есть, если к моменту необходимости обращения к закрытому статическому полю экземпляр класса ещё не определён обращение невозможно, поэтому чтобы иметь возможность обойтись без имени конкретного объекта при обращении к статическим данным
класса создают статический метод класса.

Приведем простой пример указателя на объект:

#include <iostream.h>
class P_example {
int num;
public:
void set_num(int val) {num = val; }
void show_num();
};
void P_example::show_num()
{
cout << num << " \n";
}
int main()
{
P_example ob, *p; // объявление объекта и указателя на него
ob.set_num(1); // прямой доступ к ob
ob.show_num();
р = &ob; // присвоение р адреса ob
p->show_num(); // доступ к ob с помощью указателя
return 0;
}

Повторное объявление пространства имен

Если два пространства имен имеет одинаковые называния, второе считается логическим продолжением первого.

Прямой доступ к пространству имен
Если вы уверены, что пространство не содержит дублирующих членов, можно произвести его слияние с глобальным пространством имен. Благодаря этому, пропадает необходимость, постоянно указывать оператор разрешения области видимости и индификатор пространств аимен. Существует два метода прямого доступа к пространству имен:
1.Объявление using
Объявление показывает, что работа будет идти с определенным членом, области видимости более низкого уровня. После этого отпадает необходимость явно указывать область видимости.

pop.h
using namespace std;
#include<iostream>

namespaceSp{
	int x = 100;
}

main
#include"pop.h"
#include<iostream>
usingnamespacestd;

void main(){
	setlocale(LC_ALL, "rus");
	usingSp::x;
	cout<< x;
	system("pause");
}

2.Директива using
Директива показывает, что работа будет производиться со всеми членами конкретного пространства имен. Воспользовавшись директивой, избавляемся от необходимости уточнять имена компонентов пространства, до конца программы.

Создание без именных пространств имен
Что бы избежать конфликта имен пространств, можно создать пространство без имени.
Синтаксис объявления:
Namespace{
Компоненты;
}

При работе с безымянными пространствами, C++ позволяет обращаться к компонентам безымянного пространства через, безымянные пространства, носят локальных характер и могут быть использованы, только в том файле, в котором они объявлен.

Pop.h
usingnamespacestd;
#include<iostream>

namespace {
	void f1(){
		cout<<"Вывод"<<endl;
	}
}

Main
#include"pop.h"
#include<iostream>
usingnamespacestd;

void main(){
	setlocale(LC_ALL, "rus");
	::f1();
	system("pause");
}

Обход двоичных деревьев

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

1.Прямой обход – корень обрабатывается перед своими под деревьями.
Корень – на лево – на право. Алгоритм обхода.
Если дерево не пустое:
1. Обработать корень
2. Обработать узлы в левом под дереве с помощью рекурсивного вызова.
3. Обработать узлы в правом под дереве с помощью рекурсивного вызова.

2.Симметричный обход – корень обрабатывается между своими под деревьями.
Алгоритм обхода.
Если дерево не пустое:
1. Обработать узлы левого под дерева (рекурсия).
2. Обработать корень.
3. Обработать узлы правого под дерева(рекурсия).

3.Обратный обход – корень обрабатывается после своих двух под деревьем. Левый – правый – корень. Алгоритм обхода. Если дерево не пустое:

1. Обработать узлы левого под дерева(рекурсия).
2. Обработать узлы правого под дерева(рекурсия).
3. Обработать корень.

Рассмотрим пример кода:

1.Прямой обход


#include<iostream>
usingnamespace std;
//Три обхода дерева
classNode{
	int info;
	Node *left, *right, *cur;
};
classTree{
	Node *root;
	Tree();
public:
	Tree();
	void Print(Node *cur);
};
voidTree::Print(Node *cur){
	if (cur != 0){
		cout <<cur->info;
		Print(cur->left);
		Print(cur->right);
	}
}



2.Симметричный обход

#include<iostream>
usingnamespace std;
//Три обхода дерева
classNode{
	int info;
	Node *left, *right, *cur;
};
classTree{
	Node *root;
	Tree();
public:
	Tree();
	void Print(Node *cur);
};
voidTree::Print(Node *cur){
	if (cur != 0){
		Print(cur->left);
		cout <<cur->info;
		Print(cur->right);
	}
}


3.Обратный обход

#include<iostream>
usingnamespace std;
//Три обхода дерева
classNode{
	int info;
	Node *left, *right, *cur;
};
classTree{
	Node *root;
	Tree();
public:
	Tree();
	void Print(Node *cur);
};
voidTree::Print(Node *cur){
	if (cur != 0){
		Print(cur->left);
Print(cur->right);	
		cout <<cur->info;
	}
}



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

Двоичные деревья

Дерево – еще одна динамическая структура данных, в основе которых лежат узлы, но более сложная чем связные списки и имеющая не линейный вид. В информационной части узлов дерева может храниться любая информация, любых типов, в том числе и сложных.
Двоичное или бинарное дерево – это простейшее и наиболее распространенная форма дерева. Чаще всего, такие структуры используются для организации информации, о которой нужен эффективный поиск. По сути дерево представляет собой конечное множество узлов, которые расположены по принципу иерархической связи, где каждый узел может быть связан не более чем двумя другими, если узел не связан не с одним узлом.

1.Узлы как в списках, но не линейно.
2.Указатель, который держит все дерево, называется корнем. Дерево на схеме представляют сверху в низ. Корень дерева называют – root.
3.У каждого узла есть для связи с другими узлами 2 указателя (левый и правый), на них могут быть подцеплены другие узлы, а могут и нет, тогда указатели занулены.

Основные принципы построения дерева

1.В дереве может быть только один корень.
2.Каждый узел двоичного дерева, может иметь до двух узлов потомков. Один связан слева, другой справа.
3.Узел не имеющий потомков, называют листом.
4.Каждый узел кроме корняимеет только одного родителя, корень не является не чьим потомком.
5.Если начать с любого узла и двигаться от родителя к родителю, однозначно приходим к корню.
6.Любой узел в дереве, может рассматриваться как корень меньшего дерева. То есть у каждого узла могут быть левая и правая под деревья.
  • avatar
  • 0
  • 0

Связной список

Связной список — это структура узлов. Доступ к ним через связной указатель, который храниться в каждом узле. Список не имеет фиксированного размера. Это плюс если число объектов в списке не известно до времени выполнения. Бывают списки односвязные в которых связующие указатели направлены только в 1 сторону. Или двухсвязные, содержит 2 связующих указателя. 1 направлен на след узел, а другой на предыдущий. Обычно для их работы со связными списками используют 2 класса. 1 класс определяет узел. В нём любое кол-во полей, которое определяет необходимую для хранения инфу. А так же в 1 связном списке 1 указатель и 2 в двухсвязном.

Вставка узла в средину списка
1. Выделить память под новый узел.
2. Записать в новый узел значение.
3. Записать в указатель связку, адрес узла, который должен располагаться после нового узла.
4. В узле, который должен стоять перед новым, заменить адрес указателя на адрес нового узла. Если осуществить эти действия в другом порядке, можно потерять одни узел или часть списка.

Удаление узла из середины
1. Записать адрес узла, который находится за удаляемым в указатель узла перед удаляемым.
2. Удалить узел
Вставка в начало
1. Создаем новый узел.
2. Направляем его на первый узел.
3. Указатель на первый узел перемещаем на новый узел.

Удаление из начала
1. Создаем новый указатель и направляем на первый узел.
2. Указатель на первый узел перемещаем на второй узел.
3. Указатель на первый узел обнуляем.
4. Уничтожаем или переносим в другой список не нужный нам сейчас.

Вставка в конец
1. Позиции присваиваем первый список
2. Создаем новый список
3. Указатель на последний адрес присваиваем адрес нового списка.
4. Связываем предпоследний узел и последний.

Удаление с конца
1. Направляем временный указатель на конец списка.
2. Направляем указатель на предыдущий узел списка.
3. Временный указатель обнуляем.
  • avatar
  • 0
  • 0

Вложенные классы

Если объявить вложенный класс в секции паблик, это означает что вложенный класс можно использовать как тип во всей программе, в том числе и за пределами определений членов и друзей класса.Этот прием дает широкую область видимости для вложенного класса. Но по сколько вложенный класс обычно реализуется только для нужд объемлющего класса, он не должен быть доступен во всей программе. Поэтому лучше объявить вложенный класс закрытым членом объемлющего. После этого тип Bдоступен только из определений членов и друзей класса A, поэтому все члены класса Bможно сделать открытыми. При таком подходе не нужно объявлять в другом.

Class A{
Class B{
Public:
B(intval=0);
Intval;
}
B *x;
Public:
}


Если конструктор внутреннего класса не реализован внутри вложенного класса он должен быть определен вне самого внешнего из объемлющих классов.

Class A{
Class B{
Public:
B(intval=0);
Void f();
B *obj;
Intval;
};
B *x;
Public:
};



Void A::B::f();
A::B::B(int val=0){
}


Если внутри вложенного класса имеется статистические члены, то их стоит помещать в глобальную область видимости. При этом они не обязаны быть открытыми данными вложенного класса.

Int A::B::stat=100;

Вложенный класс разрешается определять вне тела объемлющего класса. При этом объявление Bв теле Aопускать нельзя.

Class A{
Class B;
B *obj;
Public:
….
};
Class A::B{
Public:
B();
Void f();
}


При внешней реализации внутреннего класса, эта реализация должна находиться внутри того же исходного файла. Кроме того пока компилятор не видит определение вложенного класса разрешается всего лишь объявлять указатели и ссылки на этот класс, если появляется объект данного типа, происходит ошибка компиляции.
Вложенный класс можно сначала объявить, а определить позже но в теле объемлющего класса. Это позволяет иметь в нескольких вложенных классах, члены которые ссылаются друг на друга.

Class A{
Class B;
Class C{
B *p1;
};
Class B{
C *p2;
};
Public:
};

Вложенный класс не может на прямую обращаться к не статическим членам объемлющего, даже если они открыты. Любое такое обращение должно производиться через указатель, ссылку или объект объемлющего класса. Это связано с не явным использованием указателя this.

Class A{
Public:
Intinit(int);
Private:
Class B{
B(intval=0);
Void f(A&);
Int value;
};
};
A::B::B(int val){
Value=init (val); //Не верное использование функции init
}
Void A::B f(A& a){
Value = a.init();
}
  • avatar
  • 0
  • 0

Пространство имен

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

Namespace имя {
Перечень данных;
}


Применение пространства имен
Пространство имен позволяет разместить два компонента с одним именем в различных областях видимости, не создавая при этом проблем с конфликтом имен. Кроме того, можно разместить все компоненты связанные с определенным направлением, в отдельном пространстве имен.

Глобальное пространство имен – это область видимости нависшего уровня, где существуют глобальные переменные. Что бы обратиться к компоненту глобального пространства, используют следующие запись:
:: компонент
Это необходимо если, в локальных и глобальных пространствах, существуют совпадающие имена, так как по умолчанию, всегда выбирается переменная с наименьшей областью видимости.

Прямой доступ к пространству имен
Если вы уверены, что пространство не содержит дублирующих членов, можно произвести его слияние с глобальным пространством имен. Благодаря этому, пропадает необходимость, постоянно указывать оператор разрешения области видимости и индификатор пространстваимен. Существует два метода прямого доступа к пространству имен:
1.Объявление using
Объявление показывает, что работа будет идти с определенным членом, области видимости более низкого уровня. После этого отпадает необходимость явно указывать область видимости.

using имя_пространства::компонент;


pop.h
usingnamespacestd;
#include<iostream>

namespaceSp{
	int x = 100;
}


main
#include"pop.h"
#include<iostream>
usingnamespacestd;

void main(){
	setlocale(LC_ALL, "rus");
	usingSp::x;
	cout<< x;
	system("pause");
}