Учебник по Visual C++ .Net



             

Использование STL


В подобных ситуациях владение стандартными динамическими структурами данных и алгоритмами может сэкономить массу усилий, так как их разработчики уже выполнили большую часть неблагодарной черновой работы, тщательно отладили динамику жизни структур данных и все ветви алгоритмов. Кроме того, они провели анализ эффективности алгоритмов и привели их оценки. Сравним для примера две реализации алгоритма сортировки. Все знают, что рекурсивный алгоритм быстрой сортировки Quicksort, —изобретенный С. A. R. Ноаге в 1960 году, считается одним из самых эффективных в смысле количества необходимых операций для выполнения работы. Так, для сортировки массива в п элементов этому алгоритму понадобится всего лишь O(n Iog2 n) операций.

В библиотеке, подключаемой файлом заголовков stdlib.h, есть функция qsort, которая использует алгоритм Quicksort для сортировки массива элементов произвольного типа. Кроме сортируемого массива в функцию qsort необходимо передать адрес функции, которая сравнивает два элемента между собой. Алгоритм использует это сравнение для упорядочивания массива. Следующая программа демонстрирует, как можно воспользоваться функцией qsort для сортировки массива целых, вводимого пользователем. Для ее отладки я воспользовался проектом Console консольного типа, процедура создания которого была описана ранее. Из-за ошибок, связанных с использованием бета-версии Studio.Net, мне пришлось изменить конфигурацию проекта с Debug на Release. Это можно сделать, дав команду Build > Configuration Manager и выбрав Release в окне Active Solution Configuration:

#include <stdlib.h>

#include <iostream>

using namespace std;

//=== Внешняя функция сравнения переменных типа int

inline int crop (const void *a, const void *b)

{

int i = *(int *)a, j = *(int *)b;

return (i < j) ? -1 : (i > j) ? 1 : 0;

}

void main()

{

int array [1024],

// Сортируемый массив n - 0;

// Счетчик элементов

cout «"Enter some integers (Press Ctrl+z to stop)\n";

//=== Вводим по принципу "пока не надоест". Для выхода




Содержание  Назад  Вперед