Int main() {
char *s, *s1, *s2;
s1 = strdup(" text0 ");
s2 = strdup(" text1 ");
s = malloc(128);
*s="\0"; //Я инициализирую строки так это -
//намного быстрее вызовов strcpy
strcat(s,s1); //Функция strcat
strcat(s,s2);
printf("%s\n", s);
free(s1);
free(s2);
free(s);
return 0;
}
Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти. Второй важный признак структуры данных - характер упорядоченности её элементов. По этому признаку структуры можно делить на линейные и нелинейные структуры. В зависимости от характера взаимного расположения элементов в памяти, линейные структуры можно разделить на структуры с последовательным распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с произвольным связным распределением элементов в памяти (односвязные, двусвязные списки). Перечислимый тип представляет собой упорядоченный тип данных, определяемый программистом, т.е. программист перечисляет все значения, которые может принимать переменная этого типа. Значения являются неповторяющимися, количество которых не может быть больше 256. Путь от узла к самому себе называется циклом, а граф, содержащий такие пути -циклическим База данных основывается на использовании иерархической, сетевой или реляционной модели, на комбинации этих моделей или на некотором их подмножестве.
28) Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр — разъездной сбытовой посредник) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется средигамильтоновых циклов.
Для
возможности применения математического
аппарата для решения проблемы, ее следует
представить в виде математической
модели.
Проблему коммивояжёра можно представить
в виде модели на графе,
то есть, используя вершины и ребра между
ними. Таким образом, вершины графа (на
рис.: От A до D) соответствуют городам, а
ребра 
между
вершинами
и
—
пути сообщения между этими городами.
Каждому ребру
можно
сопоставить критерий выгодности
маршрута 
(На
рис.: 20, 42, …), который можно понимать
как, например, расстояние между городами,
время или стоимость поездки. Маршрутом
(также гамильтоновым маршрутом) называется
маршрут на таком графе, в который входит
по одному разу каждая вершина графа.
Задача заключается в отыскании кратчайшего
маршрута.
В целях упрощения задачи и гарантии существования маршрута, обычно считается, что модельный граф задачи является полностью связным, то есть, что между произвольной парой вершин существует ребро. В тех случаях, когда между отдельными городами не существует сообщения, этого можно достичь путем ввода рёбер с максимальной длиной. Из-за большой длины такое ребро никогда не попадет к оптимальному маршруту, если он существует.
В зависимости от того, какой критерий выгодности маршрута сопоставляется величине ребер, различают различные варианты задачи, важнейшими из которых являются симметричная и метрическая задачи.
5) алгоритмы поиска (например, пересечение, включение, окрестности) используют ограничивающие прямоугольники для принятия решения о необходимости поиска в дочерней вершине. Таким образом, большинство вершин никогда не затрагиваются в ходе поиска. Как и в случае с B-деревьями, это свойство R-деревьев обуславливает их применимость для баз данных, где вершины могут выгружаться на диск по мере необходимости.
Для расщепления переполненных вершин могут применяться различные алгоритмы, что порождает деление R-деревьев на подтипы: квадратичные и линейные.
7) Топологическая сортировка (Topological sort) — один из основных алгоритмов на графах, который применяется для решения множества более сложных задач. Задача топологической сортировки графа состоит в следующем: указать такой линейный порядок на его вершинах, чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует. Ориентированной сетью (или просто сетью) называют бесконтурный ориентированный граф. В задачах подобного плана рассматриваются только конечные сети. Иерархическая модель организует данные в виде древовидной структуры.
К основным понятиям иерархической структуры относятся: уровни элемент (узел), связь. Дерево представляет собой иерархию элементов называемых узлами. Узел - это совокупность атрибутов данных, описывающих некоторый объект. На самом верхнем уровне иерархии имеется один и только один узел - корень. Каждый узел, кроме корня, связан с одним узлом на более ( высоком уровне, называемым исходным для данного узла. Ни один элементов не имеет более одного исходного узла. Каждый элемент может быть связан с одним или несколькими элементами на более низком уровне. Они называются порожденными
14) Рассмотрим частный вид графов, широко используемых, например, в теории электрических цепей, химии, вычислительной технике и в информатике.
Определение 1. Деревом называется связный граф, не содержащий циклов. Любой (в том числе несвязный) граф без циклов называется ациклическим. Несвязный граф, каждая компонента связности которого является деревом, называется лесом. Можно сказать, что деревья являются компонентами леса. На рис.1 изображены два дерева G1, G2 и лес G3.
20) Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
Бинарный поиск
#include <iostream> using namespace std;
int BinSearch(int *M, int n, int k);
int main() { const int n=5; int A[n]; int x;
for (size_t i=0; i<n; i++) { cout << "Please, input A[" << i+1 << "] = "; cin >> A[i]; }
cout << "find this -> "; cin >> x;
cout << BinSearch(A, n, x); // A, n, x – параметры функции
return 0; }
int BinSearch(int *M, int n, int k) { int L = 0; int R = n; // для чего нужна переменная R
int m; int z = 0;
while (L<R) // что за условие { z++; m = (L+R)/2; // для чего? if (k > M[m]) L = m; //что выполняет? if (k < M[m]) R = m; if (k == M[m]) break; // в каком случае? }
return 0; }
|
24) Рассмотрим ориентированный граф, G (N, A) , где N и представляют собой набор узлов и дуг, соответственно. С каждой дуги (I, J) в это экономически C (I, J) . Пусть | N | = п и | A | = м .Проблема заключается в том, чтобы найти корни направлены каркас, G (N, S) , где S является подмножеством таких, что сумма C (I, J) для всех (I, J) в S сведено к минимуму. Корни направлены связующего дерева определяется как граф, который соединяет без цикла, все узлы с N-1 дуг, т. е. каждый узел, кроме корня, имеет одну и только одну входящую дугу.
Алгоритма Прима
PRIM алгоритма [1], которая решает неориентированный проблемы MST, в коротком решения направлены коллегой. Следующие экспонаты, например, что итерационный жадные решение больше не может последовательно дают оптимальное решение.
Решение проблемы Режиссер MST
Чу и Лю [2], Эдмондс [3], а также Bock [4] независимо друг от друга данной эффективные алгоритмы для нахождения MST на ориентированном графе. Чу-Лю и Эдмондс алгоритмы практически идентичны; алгоритм Бок похожа, но заявил о матрицах, а не на графах. Кроме того, распределенный алгоритм задается Humblet [5]. В дальнейшем, мы должны кратко иллюстрируют алгоритм Chu-Liu/Edmonds, следуя за исчерпывающий пример (в связи с [1]). Читатель может также обратиться к [6] [7] для эффективной реализации, O (mlogn) и O (N ^ 2)для плотного графика, этого алгоритма.