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

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

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

  Yandex ТИЦ:  
   Google PR:  

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

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

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





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

  • Хранимые в ячейке данные
  • Логическая позиция ячейки в массиве
  • Ссылки на предыдущий и следующий элементы

Каждая новая структура помещается в список так, что элементы остаются упорядоченными по индексу в массиве. Доступ к массиву производится путем перехода по ссылкам.

Например, в качестве носителя элемента разреженного массива в электронной таблице можно использовать следующую структуру:

struct cell {
  char cell_name[9];  /* имя ячейки, напр., A1, B34 */
  char  formula[128]; /* информация, напр., 10/B2 */
  struct cell *next;  /* указатель на следующую запись */
  struct cell *prior; /* указатель на предыдущую запись */
} ;

Поле cell_name содержит строку, соответствующую имени ячейки, например, А1, В34 или Z19. Строковое поле formula хранит формулу (данные) из соответствующей ячейки таблицы.

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

Следующие глобальные переменные указывают на начало и конец связанного списка:

struct cell *start = NULL; /* первый элемент списка */
struct cell *last = NULL;  /* последний элемент списка */

В большинстве электронных таблиц при вводе формулы в ячейку создается новый элемент разреженного массива. Если электронная таблица построена на основе связанного списка, этот элемент вставляется в список с помощью функции, аналогичной функции dls_store(), приведенной в главе 22. Помните, что список упорядочен по именам ячеек; например, А12 предшествует А13 и т.д.

/* Вставка ячеек в упорядоченный список. */
void dls_store(struct cell *i, /* указатель на вставляемую ячейку */
               struct cell **start, 
               struct cell **last) 
{
  struct cell *old, *p;

  if(!*last) { /* первый элемент в списке */
    i->next = NULL;
    i->prior = NULL;
    *last = i;
    *start = i;
    return;
  }

  p = *start; /* начать с головы списка */

  old = NULL;
  while(p) {
    if(strcmp(p->cell_name, i->cell_name) < 0){
      old = p;
      p = p->next;
    }
    else { 
      if(p->prior) { /* это элемент из середины */
        p->prior->next = i;
        i->next = p;
        i->prior = p->prior;
        p->prior = i;
        return;
      }
      i->next = p; /* новый первый элемент */
      i->prior = NULL;
      p->prior = i;
      *start = i;
      return;
    }
  }
  old->next = i; /* вставка в конец */
  i->next = NULL;
  i->prior = old;
  *last = i;
  return;
}

В приведенной выше функции параметр i — указатель на новую вставляемую ячейку. Параметры start и last являются соответственно указателями на указатели на начало и конец списка.

Нижеследующая функция deletecell() удаляет из списка ячейку, имя которой передается в качестве параметра.

void deletecell(char *cell_name,
            struct cell **start,
            struct cell **last)
{
  struct cell *info;

  info = find(cell_name, *start);
  if(info) {
    if(*start==info) {
      *start = info->next;
      if(*start) (*start)->prior = NULL;
      else *last = NULL;
    }
    else {
      if(info->prior) info->prior->next = info->next;
      if(info != *last)
          info->next->prior = info->prior;
      else
        *last = info->prior;
    }
    free(info); /* освободить системную память */
  }
}

Последняя функция, которая понадобится для реализации разреженного массива на основе связанного списка — это функция find(), находящая указанную ячейку. Для нахождения ячейки данной функции приходится выполнять линейный поиск, но, как было показано в главе 21, среднее количество сравнений при линейном поиске равно n/2, где n — количество элементов в списке. Ниже приведен текст функции find():

struct cell *find(char *cell_name, struct cell *start)
{
  struct cell *info;

  info = start;
  while(info) {
    if(!strcmp(cell_name, info->cell_name)) return info;
    info = info->next; /* перейти к следующей ячейке */
  }
  printf("Ячейка не найдена.\n");
  return NULL; /* поиск неудачный */
}

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

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

----------

[1]Многие пользователи шутят, что сама Microsoft не знает, сколько же точно занимает ее Excel. Конечно, это только шутка, но лично я иногда думаю, что в ней 100 % правды.


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

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.