среда, 19 июня 2013 г.

Автор: на Комментариев нет:

среда, 12 июня 2013 г.



  1. Алгоритм. Свойства. Способы записи.
  1. Машина Тьюринга.
  1. Архитектура компьютера.
тетрадь
  1. Структура программы. Заголовочные файлы, файлы реализации. Препроцессор.
  1. Понятие переменной. Типы данных. Области видимости. Время жизни.
  1. Арифметические, логические операции. Приоритет.
  1. Побитовые операции. Операции сдвига.
  1. Арифметика указателей. Связь между указателями и массивами. Ссылки.
  1. Операторы ввода-вывода.
  1. Условный оператор. Оператор выбора.
  1. Виды циклов.
  1. Псевдослучайные числа. Получение целого(вещественного) числа из заданного отрезка
    [a, b]
  2. Одномерные массивы. Статическая память.
Динамическая память.
  1. Сортировка выбором. Трудоемкость.
  1. Сортировка обменом. Модификации. Трудоемкость.
)
  1. Сортировка вставками. Модификации. Трудоемкость.
  1. Задачи поиска минимума (максимума) и его номера.
мин
Самое тупое - заведите две переменных, положите в первую значение нулевого элемента массива, во вторую - ноль и идите по массиву дальше, сравнивая каждый элемент со значением в первой переменной. Если значение элемента массива меньше первой переменной, кладёте туда значение этого элемента, а во вторую переменную его номер. После окончания прохода массива у вас в переменных будут результаты.
Можно отсортировать массив через qsort(), тогда в нулевой ячейке окажется элемент с наименьшим значением. Правда, это будет уже другой массив :)
#include <iostream>

using namespace std;

int main ()
{
int n;
cout << "Введите количество элементов в массиве: ";
cin >> n;
int *A = new int[n];
int minIdx = 0;
for (int i = 0; i < n; i++)
{
 cout << "Введите значение " << i << "-ого элемента массива:";
 cin >> A[i];
 if (A[i] < A[minIdx])
  minIdx = i;
}
cout << "Минимальный элемент массива: " << A[minIdx] << " и его номер: " << minIdx << endl;

delete[] A;
return 0;
}


  1. Поиск в одномерном массиве(Линейный, бинарный).


  1. Изменение массива (добавление, удаление элементов).
  2. Двумерные массивы. Статическая память. Динамическая память.
  3. Функции. Способы передачи параметров.
  1. Рекурсивные функции. Алгоритм Евклида (НОД).
  1. Работа с файлами.
  1. Функции работы со строками.


  1. Многофайловые проекты.
  2. Структуры. Статическая память. Динамическая память.
  3. Стек. Реализация на базе массива.
 Стеком называется структура данных, организованная по принципу LIFO – last-in, first-out , т.е. элемент, попавшим в множество последним, должен первым его покинуть. При практическом использовании часто налагается ограничение на длину стека, т.е. требуется, чтобы количество элементов не превосходило N для некоторого целого N.
Создание исполнителя стек предполагает наличие следующих функций
      инициализация
      добавление элемента на вершину стека
      взятие/извлечение элемента с вершины стека
      проверка: пуст ли стек?
      очистка стека

Стек можно реализовать на базе массива или (в языке С ) это можно сделать на базе указателей.


  1. Динамический стек.
  1. Очередь. Реализация на базе массива.

Очередь.

 Очередью называется структура данных, организованная по принципу FIFO – first-in, first-out , т.е. элемент, попавшим в множество первым, должен первым его и покинуть. При практическом использовании часто налагается ограничение на длину очереди, т.е. требуется, чтобы количество элементов не превосходило N для некоторого целого N.
Создание исполнителя очередь предполагает наличие следующих функций
      инициализация
      добавление элемента в конец очереди
      взятие/извлечение элемента с начала очереди
      проверка: пуста ли очередь?
      очистка очереди

Обычно, используется реализация циклической очереди. Т.е. под очередь отводится некоторый непрерывный кусок памяти (массив) и при подходе хвоста очереди к концу массива хвост автоматически перебрасывается на противоположный конец массива. Например, для реализации стандартной очереди из менее чем 100 целых чисел на базе массива в языке С следует определить следующие данные

  1. Динамическая очередь.
  1. Дек. Реализация на базе массива.
Деком называется структура данных, представляющих собой упорядоченное множество элементов,  в котором элементы можно добавлять в начало и конец множества и извлекать их можно с обеих сторон.
Создание исполнителя дек предполагает наличие следующих функций
      инициализация
      добавление элемента в начало дека
      добавление элемента в конец дека
      взятие/извлечение элемента из начала дека
      взятие/извлечение элемента с конца дека
      проверка: пуст ли дек?
      очистка дека

  1. Динамический дек.
  1. Линейный список.
днонаправленный линейный список - это список, который имеет указатель на начало списка, при этом каждый список имеет указатель на следующий список, а последний список принимает указатель NULL, что говорит о том, что он последний.

Как правило, рассматриваются односвязные и двусвязные списки. Данные в списках представляют собой некоторым способом упорядоченное множество. В множестве вводится понятие текущего элемента. В каждый момент можно получать данные только о текущем элементе. За одну операцию можно выбрать в качестве текущего элемента первый элемент в списке. Далее за одну операцию можно переместиться к следующему или предыдущему (для двусвязного списка) элементу. Можно стереть текущий элемент или вставить новый элемент вслед за текущим.
Более конкретно, создание исполнителя односвязный список (L1-список) предполагает наличие следующих функций
      инициализация
      установка текущего элемента в начало списка
      перемещение текущего элемента к следующему элементу списка
      взятие значения текущего элемента
      уничтожение текущего элемента с автоматическим перемещением текущего элемента к следующему элементу списка
      вставка нового элемента после текущего
      проверка: пуст ли список?
      проверка: текущий элемент в конце списка?
      очистка списка
Двусвязный список отличается от односвязного наличием дополнительных операций:
      перемещение текущего элемента к предыдущему элементу списка
      вставка нового элемента перед текущим
      проверка: текущий элемент в начале списка?
Иногда используются циклические списки. В них ссылки на концах списка циклически замыкаются. Хотя, формально, в данной структуре данных нет начала и конца, тем не менее, понятие первого элемента списка следует оставить, т.к. без него сложно, например,  реализовать перебор всех элементов списка. Список предписаний несколько модифицируется. Например, для двусвязного списка он может выглядеть следующим образом:
      инициализация
      установка текущего элемента в первый элемент списка
      перемещение текущего элемента к следующему элементу списка
      перемещение текущего элемента к предыдущему элементу списка
      взятие значения текущего элемента
      уничтожение текущего элемента с автоматическим перемещением текущего элемента к следующему элементу списка
      вставка нового элемента после текущего
      вставка нового элемента перед текущим
      проверка: пуст ли список?
      проверка: текущий элемент первый в списке?
      очистка списка

  1. Двунапрвленный линейный список.
  1. Бинарное дерево поиска. Реализация. Обход.
  1. Сжатие данных. Алгоритм Хаффмана.


Автор: на Комментариев нет:
Подписаться на: Сообщения (Atom)