Спонсоры сайта:

Наличие этой страницы в поиске?

Информеры ТИЦ и PR

  Yandex ТИЦ:  
   Google PR:  

Путешественникам, меломанам, бизнесменам, вебмастерам, новости.

Содержание | <<< | >>>

Зачем нужны разреженные массивы?





Чтобы понять, зачем нужны разреженные массивы, вспомните следующие два факта:

  • При описании обычного массива в языке С вся память, требуемая для размещения массива, выделяется сразу после его создания.
  • Большие массивы, особенно многомерные, могут занимать огромные объемы памяти.

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

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

Существуют многочисленные примеры приложений, требующих обработки разреженных массивов. Многие из них относятся к работе с матрицами или к научным и инженерным задачам, которые понятны лишь экспертам в соответствующих областях. Однако есть одно очень популярное приложение, в котором обычно применяется разреженный массив — электронная таблица. Несмотря на то, что матрица в средней электронной таблице очень большая, в любой момент времени используется лишь некоторая ее часть. В ячейках электронных таблиц хранятся формулы, значения и строки. При использовании разреженного массива память для каждого элемента выделяется только при необходимости. Поскольку фактически используется лишь небольшая часть элементов массива, весь он (то есть электронная таблица) кажется очень большим, но занимает минимально необходимую память.

В этой главе будут часто повторяться два термина: логический массив и физический массив. Логический массив — это массив, который мыслится как существующий в системе. Например, если матрица электронной таблицы имеет размер 1`000x1`000, то логический массив, реализующий матрицу, также будет иметь размер 1`000x1`000 — даже несмотря на то, что физически такой массив не существует в компьютере. Физический массив — это массив, который реально существует в памяти компьютера. Так, если используются только 100 элементов матрицы электронной таблицы, то для хранения физического массива требуется память, необходимая для хранения лишь этих 100 элементов. Методы обработки разреженных массивов, раскрытые в данной главе, обеспечивают связь между логическими и физическими массивами.

Ниже будут рассмотрены четыре различных способа создания разреженного массива: связанный список, двоичное дерево, массив указателей и хеширование. Несмотря на то, что программа работы с электронными таблицами не разрабатывается целиком, все примеры ориентируются на матрицу электронной таблицы, показанную на рис. 23.1. На этом рисунке элемент X расположен в ячейке В2.

Рис. 23.1. Организация простой электронной таблицы

    ---A--- ---B--- ---C---
1
2              X
3
4
5
6
7
.
.
.

Содержание | <<< | >>>

C++ исходники. Все примеры - рабочие:

часы:

Dev C++ WinAPI Стрелочные часы Analog Clock

Dev C++ WinAPI Цифровые прозрачные часы. Текст на рабочем столе. Digital transparent clock. Text on desktop

Dev C++ OLE WinApi CALENDAR and DIGITAL CLOCK (15kb). Календарь и цифровые часы

Dev C++ OLE WinAPI Календарь и цифровые часы почти Vista SideBar всего 21kb

плееры:

Microsoft Visual C++ 2008 Direct Show DVD Mini Player 10.5kb

Dev C++ WinAPI Микро медиа плеер 3.5kb

Dev C++ WinAPI Мини медиа плеер 4.5kb

Dev C++ WinAPI Hint Всплывающая подсказка

Dev C++ WinAPI RECT - имитатор кнопки

Dev C++ WinAPI Заполнить ListBox

Dev C++ WinAPI Заполнить, редактировать, сохранить, загрузить ListBox (PlayList)

Dev C++ WinAPI Индикатор уровня

Dev C++ WinAPI MP3 Микро плеер Открыть с помощью...

Dev C++ WinAPI Своя кнопка

изображения:

Dev C++ GDI+ WinAPI Mini FotoResizer (16kb), изменяет размеры всех фото (JPG) до указанного размера в выбраной папке и её подпапках

Dev C++ WinAPI Сохранить BITMAP экрана, десктопа, окна, клиентской области.

Dev C++ WinAPI Изменить размер изображения BMP RESIZE. Загрузка изображений из ФАЙЛА, вывод на экран и сохранение в файл.

Dev C++ WinAPI Загрузка изображений из РЕСУРСОВ и вывод на экран.

Dev C++ GDI+ WinAPI. Преобразовать изображения из одного формата в другой (JPG в BMP, GIF, PNG и обратно ), используя дополнительные библиотеки GDI+. Загрузка изображений из файла и сохранение в файл.

Dev C++ GDI+ WinAPI масштабирование JPG RESIZE

Dev C++ OLE WinAPI. Преобразовать изображения из JPG в BMP, используя дополнительные библиотеки OLE. Загрузка изображений из РЕСУРСОВ и сохранение в файл.

Dev C++ OLE WinAPI преобразовать JPG в BMP, используя дополнительные библиотеки OLE. Загрузка изображений из ФАЙЛА и сохранение в файл.

Dev C++ OLE WinAPI масштабирование BMP RESIZE

разное:

Dev C++ WinAPI Dev C++ Преобразовать цвет точки экрана в HTML код

Dev C++ WinAPI NOTIFYICONDATA WS_EX_TOOLWINDOW Иконка в области уведомлений (notification area, tray, трей). Удалить с панели задач (taskbar).

Dev C++ WinAPI ShellExecute Создать ссылку на WEB сайт

Dev C++ WinAPI ShellExecute Создать окно со ссылкой на WEB сайт

Dev C++ WinAPI CreateProcess ShellExecute WinExec Запуск приложения из приложения

Dev C++ OLE WinAPI Создать регион Regions PopUp Меню Menu

Dev C++ FindFiles. Поиск файлов заданного типа (в примере *.JPG) в папке и её подпапках

библиотеки:

Скачать библиотеку GDI+ для Dev C++

Скачать справочнник с примерами языка C.