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

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

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

  Yandex ТИЦ:  
   Google PR:  

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

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

Представление разреженного массива в виде массива указателей





Допустим, что электронная таблица имеет размер 26x100 (от А1 до Z100), то есть состоит из 2`600 элементов. Теоретически можно хранить элементы таблицы в следующем массиве структур:

struct cell {
  char cell_name[9];
  char  formula[128];
} list_entry[2600];   /* 2600 ячеек */

Ho 2`600, умноженное на 137 байтов (размер этой структуры в байтах), равняется 356`200 байтов памяти. Это слишком большой объем памяти, чтобы тратить его на не полностью используемый массив. Тем не менее, можно создать массив указателей (pointer array) на структуры типа cell. Для хранения массива указателей требуется намного меньше памяти, чем для массива структур. При каждом присвоении ячейке логического массива данных под эти данные выделяется память, а соответствующему указателю в массиве указателей присваивается адрес выделенного фрагмента. Такая схема позволяет добиться более высокой производительности, чем при связанном списке или двоичном дереве. Описание массива указателей выглядит следующим образом:

struct cell {
  char cell_name[9]; 
  char formula[128];
} list_entry;

struct cell *sheet[2600]; /* массив из 2600 указателей */

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

Рис. 23.2. Представление разреженного массива в виде массива указателей

+-+-+-+-+-+-+-+-+-+-+-+-+
|.|.|0|0|.|0|0|0|.|0|0|0|
+|+|+-+-+|+-+-+-+|+-+-+-+
 | |     |       |  +----+
 | |     |       '->|A[8]|
 | |     |          +----+
 | |     |  +----+
 | |     '->|A[4]|
 | |        +----+
 | |  +----+
 | '->|A[1]|
 |    +----+
 |  +----+
 '->|A[0]|
    +----+

Перед использованием массива указателей каждый его элемент необходимо проинициализировать нулем (NULL), что означает отсутствие данной записи. Ниже показана функция инициализации массива:

void init_sheet(void)
{
  register int t;

  for(t=0; t < 2600; ++t) sheet[t] = NULL;
}

Когда пользователь вводит формулу в ячейку, занимающую определенное положение в электронной таблице (а положение ячейки, как известно, определяется ее именем), вычисляется индекс в массиве указателей sheet. Этот индекс получается путем преобразования строкового представления имени ячейки в число, как показано в следующем листинге:

void store(struct cell *i)
{
  int loc;
  char *p;

  /* вычисление индекса по заданному имени */
  loc = *(i->cell_name) - 'A'; /* столбец */
  p = &(i->cell_name[1]);
  loc += (atoi(p)-1) * 26; /* количество строк * ширина строки +
                              столбец */

  if(loc >= 2600) {
    printf("Ячейка за пределами массива.\n");
    return;
  }
  sheet[loc] = i; /* поместить указатель в массив */
}

При вычислении индекса в функции store() предполагается, что все имена ячеек начинаются с прописной буквы, за которой следует целое число, например, В34, С19 и т.д. Поэтому в результате вычислений по формуле, запрограммированной в функции store(), имя ячейки А1 соответствует индексу 0, имя В1 соответствует индексу 1, А2 — 26 и т.д. Поскольку имена ячеек уникальны, индексы также уникальны и указатель на каждую запись хранится в соответствующей позиции массива. Если сравнить эту процедуру с версиями, использующими связанный список или двоичное дерево, становится понятно, насколько она проще и короче.

Функция удаления ячейки deletecell() также становится очень короткой. При вызове она просто обнуляет указатель на элемент и возвращает системе память.

void deletecell(struct cell *i)
{
  int loc;
  char *p;

  /* вычисление индекса по заданному имени ячейки */
  loc = *(i->cell_name) - 'A'; /* столбец */
  p = &(i->cell_name[1]);
  loc += (atoi(p)-1) * 26; /* количества строк * ширина строки + 
                              столбец */

  if(loc >= 2600) {
    printf("Ячейка за пределами массива.\n");
    return;
  }
  if(!sheet[loc]) return; /* не освобождать, если указатель нулевой
                             (null) */

  free(sheet[loc]);  /* освободить системную память */
  sheet[loc] = NULL;
}

Этот код также намного быстрее и проще, чем в версии со связанным списком.

Процесс поиска ячейки по имени прост, поскольку имя ячейки однозначно определяет индекс в массиве указателей. Поэтому функция поиска принимает следующий вид:

struct cell *find(char *cell_name)
{
  int loc;
  char *p;

  /* вычисление индекса по заданному имени ячейки */
  loc = *(cell_name) - 'A'; /* столбец */
  p = &(cell_name[1]);
  loc += (atoi(p)-1) * 26; /* количества строк * ширина строки + 
                              столбец */

  if(loc>=2600 || !sheet[loc]) { /* эта ячейка пустая */
    printf("Ячейка не найдена.\n");
    return NULL;  /* поиск неуспешный */
  }
  else return sheet[loc];
}

Анализ метода представления разреженного массива в виде массива указателей

Метод реализации разреженного массива на основе массива указателей обеспечивает намного более быстрый доступ к элементам, чем методы на основе связанного списка и двоичного дерева. Если массив не очень большой, выделение памяти для массива указателей лишь незначительно уменьшает объем свободной памяти системы. Тем не менее, в массиве указателей для каждой ячейки выделяется некоторый объем памяти независимо от того, используется она или нет. В некоторых приложениях это может быть ограничением, хотя в общем случае это не является проблемой.


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

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.