С++ для новичков, вопросы, ответы, книги, с чего начать Опции

[pokemon4eg]

- Он придумал С++

Попробуем сделать что-то хорошее для С++ и начинающих программистов

В описании раздела программирования есть много языков. В том числе и С++. Правда поиском по форуму по слову "С++" ничего не нашел. Вот и решил сделать тему в которой будем отвечать на вопросы и помогать друг-другу в этом не легком, а порой и очень нервном деле

С чего начать?
C++ wiki: http://ru.wikipedia.org/wiki/C%2B%2B

Вам понадобится 3 вещи:
1) Google
2) IDE (интегрированная среда разработки)
3) Книга: С++ для чайников: http://forum.0day.kiev.ua/index.php?showtopic=103405

IDE:

» Нажмите, чтобы показать спойлер - нажмите опять, чтобы скрыть... «

Windows :
- думаю что для виндовса проще всего Visual Studio. Есть бесплатная (обрезанная) версия которая вполне подойдет для начала.
http://ru.wikipedia.org/wiki/Microsoft_Visual_Studio_Express

Позже (дет 1-2 года ) с ней начнутся проблемы, надо будет доустанавливать СДК по 400 мб, не будет чет поддерживать и т.п.... тогда можно будет поискать полную версию ну или установить ее сразу :\

Там же есть ссылка "Сравнение IDE"...

Linux:
- KDevelop умеет работать с С++ и не только) : http://www.kdevelop.org/index.html?filenam...amp;set_lang=ru
- Monodevelop: http://monodevelop.com/download

Первая программа. Hello C++:

» Нажмите, чтобы показать спойлер - нажмите опять, чтобы скрыть... «

#include <iostream>  

int main(int argc, char** argv)
{
    std::cout << "Hello";  // вывод на екран
    return 0;
}

// - так обозначаются строчные коментарии

/*    а так блочные
    тоесть многострочные
*/

// директива #include говорит препроцессору что мы хотим подключить файлик iostream
// а надо на это для того чтоб можно было использовать std::cout - стандартный поток вывода

// С++ программа всегда начинается с функции main. ну это все вы прочитаете в книге :)

// return 0; - возвращаем 0 чем говорим операционной системе что наша программа
// завершилась без ошибок

Бесплатные технологи для С++ :

» Нажмите, чтобы показать спойлер - нажмите опять, чтобы скрыть... «

Разработка игр:
Microsoft: http://gdk.thegamecreators.com/ - майкрософтовская разработка для вижуал студии и майкрософта)
Ogre 3d: http://www.ogre3d.ru/wik/pmwiki.php?n=Main...%ec%e0%f6%e8%ff - требует достаточной подготовки С++. Есть доки на русском.

Trolltech (Nokia):
Qt: http://ru.wikipedia.org/wiki/Qt - кросс-платформенная библиотека для создания графического интерфейса, работы с сетью, XML, OpenGL и т.д. Есть книги, доки на русском.

Boost:
Boost: http://ru.wikipedia.org/wiki/Boost - собрание библиотек, расширяющих C++. Есть доки на русском.

Free C / C++ Libraries, Source Code and Frameworks
Open source libraries: http://www.thefreecountry.com/sourcecode/cpp.shtml

Open source + cross-platform:
http://www.shlomifish.org/open-source/portability-libs/ - бесплатные, кросс-платформенные библиотеки

По возможности буду выкладывать примеры вот сюда:
http://github.com/k0ndr0ng1thub/0dayForumC...er/CppExamples/

Книги:

» Нажмите, чтобы показать спойлер - нажмите опять, чтобы скрыть... «

http://forum.0day.kiev.ua/index.php?showtopic=132019 - C/C++ и MS Visual C++ 2008 для начинающих
http://forum.0day.kiev.ua/index.php?showtopic=132381 - Microsoft Visual Studio 2008, Ларс Пауэрс, Майк Снелл

Сообщение отредактировал pokemon4eg - Dec 3 2009, 17:23

[Tamplier]

Наиболее часто задаваемые вопросы по С++. Реализация распространенных алгоритмов, решения типовых задач.

Алгоритмы сортировки строк

Сортировка выбором

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

template<class T>
void selectSort(T a[], long size) {
long i, j, k;
T x;

[color=#3333FF]for[/color]( i=0; i < size; i++) { // i - номер текущего шага
k=i; x=a[i];
for( j=i+1; j < size; j++) // цикл выбора наименьшего элемента
if ( a[j] < x ) {
k=j; x=a[j]; // k - индекс наименьшего элемента
}
a[k] = a[i]; a[i] = x; // меняем местами наименьший с a[i]
}
}

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

Сортировка пузырьком

Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

template<class T>
void bubbleSort(T a[], long size) {
  long i, j;
  T x;

  for( i=0; i < size; i++) {            // i - номер прохода
    for( j = size-1; j > i; j-- ) {     // внутренний цикл прохода

      if ( a[j-1] > a[j] ) {
      x=a[j-1]; a[j-1]=a[j]; a[j]=x;
    }
  }
}
}

Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.
На практике метод пузырька, даже с улучшениями, работает слишком медленно. А потому - почти не применяется.

Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.
На практике метод пузырька, даже с улучшениями, работает слишком медленно. А потому - почти не применяется.

Сортировка вставками

Сортировка простыми вставками в чем-то похожа на вышеизложенные методы.

template
void insertSort(T a[], long size) {
  T x;
  long i, j;

  for ( i=0; i < size; i++) {  // цикл проходов, i - номер прохода
    x = a[i];    
    // поиск места элемента в готовой последовательности
    for ( j=i-1; j>=0 && a[j] > x; j--)
      a[j+1] = a[j];      // сдвигаем элемент направо, пока не дошли
    // место найдено, вставить элемент
    a[j+1] = x;
  }
}

Аналогично сортировке выбором, среднее, а также худшее число сравнений и пересылок оцениваются как Theta(n2), дополнительная память при этом не используется.

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

Алгоритм можно слегка улучшить. Заметим, что на каждом шаге внутреннего цикла проверяются 2 условия. Можно объединить из в одно, поставив в начало массива специальный сторожевой элемент. Он должен быть заведомо меньше всех остальных элементов массива.

// сортировка вставками со сторожевым элементом
template
inline void insertSortGuarded(T a[], long size) {
T x;
long i, j;
T backup = a[0]; // сохранить старый первый элемент

setMin(a[0]); // заменить на минимальный

// отсортировать массив
for ( i=1; i < size; i++) {
x = a[i];
for ( j=i-1; a[j] > x; j--)
a[j+1] = a[j];
a[j+1] = x;
}
// вставить backup на правильное место
for ( j=1; j< backup; j++)
a[j-1] = a[j];
// вставка элемента
a[j-1] = backup;

}

Функция setmin(T& x) должна быть создана пользователем. Она заменяет x на элемент, заведомо меньший(меньший или равный, если говорить точнее) всех элементов массива.

Сортировка Шелла

Сортировка Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками.

int increment(long inc[], long size) {
  int p1, p2, p3, s;
  p1 = p2 = p3 = 1;

  s = -1;
  do {
    if (++s % 2) {
      inc[s] = 8*p1 - 6*p2 + 1;
    } else {
      inc[s] = 9*p1 - 9*p3 + 1;
      p2 *= 2;
      p3 *= 2;
    }
    p1 *= 2;
  } while(3*inc[s] < size);  

  return s > 0 ? --s : 0;
}

template
void shellSort(T a[], long size) {
  long inc, i, j, seq[40];
  int s;
// вычисление последовательности приращений
  s = increment(seq, size);
  while (s >= 0) {
    // сортировка вставками с инкрементами inc[]
    inc = seq[s--];
    for (i = inc; i < size; i++) {
      T temp = a[i];
      for (j = i-inc; (j >= 0) && (a[j] > temp); j -= inc)
        a[j+inc] = a[j];
        a[j+inc] = temp;
    }
  }
}

Часто вместо вычисления последовательности во время каждого запуска процедуры, ее значения рассчитывают заранее и записывают в таблицу, которой пользуются, выбирая начальное приращение по тому же правилу: начинаем с inc[s-1], если 3*inc[s] > size.

Пирамидальная сортировка

Пирамидальная сортировка является первым из рассматриваемых методов, быстродействие которых оценивается как O(n log n).

template
void downHeap(T a[], long k, long n) {
  //  процедура просеивания следующего элемента
  //  До процедуры: a[k+1]...a[n]  - пирамида
  //  После:  a[k]...a[n]  - пирамида
  T new_elem;
  long child;
  new_elem = a[k];
  while(k <= n/2) {          // пока у a[k] есть дети
    child = 2*k;
    //  выбираем большего сына
    if( child < n && a[child] < a[child+1] )
    child++;
    if( new_elem >= a[child] ) break;
    // иначе
    a[k] = a[child];     // переносим сына наверх
    k = child;
  }
  a[k] = new_elem;
}
template
void heapSort(T a[], long size) {
  long i;
  T temp;
  // строим пирамиду
  for(i=size/2-1; i >= 0; i--) downHeap(a, i, size-1);
  // теперь a[0]...a[size-1] пирамида
  for(i=size-1; i > 0; i--) {
    // меняем первый с последним
    temp=a[i]; a[i]=a[0]; a[0]=temp;
    // восстанавливаем пирамидальность a[0]...a[i-1]
    downHeap(a, 0, i-1);
  }
}

Построение пирамиды занимает O(n log n) операций, причем более точная оценка дает даже O(n) за счет того, что реальное время выполнения downheap зависит от высоты уже созданной части пирамиды.

Вторая фаза занимает O(n log n) времени: O(n) раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок (n log n)/2, и отклонения от этого значения сравнительно малы.

Метод не является устойчивым: по ходу работы массив так "перетряхивается", что исходный порядок элементов может измениться случайным образом.

Сообщение отредактировал Tamplier - Mar 20 2009, 20:31