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

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

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

  Yandex ТИЦ:  
   Google PR:  

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

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

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





По сути, двоичное дерево — это просто видоизмененный двусвязный список. Его основное преимущество заключается в возможности быстрого поиска. Именно благодаря этому удается очень быстро выполнять вставки и затрачивать совсем немного времени на доступ к элементам. (Ведь двоичные деревья идеально подходят для приложений, в которых требуется структура связанного списка, в которой поиск должен занимать совсем немного времени.)

Чтобы использовать двоичное дерево для реализации электронной таблицы, необходимо изменить структуру cell следующим образом:

struct cell {
  char cell_name[9];  /* имя ячейки, напр., A1, B34 */
  char  formula[128]; /* данные, напр., 10/B2 */
  struct cell *left;  /* указатель на левое поддерево */
  struct cell *right; /* указатель на правое поддерево */
} list_entry;

Функцию street() из главы 22 можно модифицировать так, чтобы она строила дерево на основании имени ячейки. В следующем коде предполагается, что параметр n является указателем на вставляемый элемент дерева.

struct cell *stree(
        struct cell *root,
        struct cell *r,
        struct cell *n)
{
  if(!r) {    /* первая вершина поддерева */
    n->left = NULL;
    n->right = NULL;
    if(!root) return n;  /* первый вход в дерево */
    if(strcmp(n->cell_name, root->cell_name) < 0)
      root->left = n;
    else
      root->right = n;
    return n;
  }

  if(strcmp(r->cell_name, n->cell_name) <= 0)
    stree(r, r->right, n);
  else
    stree(r, r->left, n);

  return root;
}

При вызове функции stree() ей необходимо передавать указатели на корень дерева в качестве первых двух параметров и указатель на новую ячейку в качестве третьего. Функция возвращает указатель на корень.

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

struct cell *dtree(
        struct cell *root,
        char *key)
{
  struct cell *p, *p2;

  if(!root) return root; /* элемент не найден */

  if(!strcmp(root->cell_name, key)) { /* удаление корня */
    /* это означает пустое дерево */
    if(root->left == root->right){
      free(root);
      return NULL;
    }
    /* или если одно из поддеревьев пустое */
    else if(root->left == NULL) {
      p = root->right;
      free(root);
      return p;
    }
    else if(root->right == NULL) {
      p = root->left;
      free(root);
      return p;
    }
    /* или если оба поддерева непустые */
    else {
      p2 = root->right;
      p = root->right;
      while(p->left) p = p->left;
      p->left = root->left;
      free(root);
      return p2;
    }
  }
  if(strcmp(root->cell_name, key)<=0)
    root->right = dtree(root->right, key);
  else root->left = dtree(root->left, key);
  return root;
}

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

struct cell *search_tree(
        struct cell *root,
        char *key)
{
  if(!root) return root;  /* пустое дерево */
  while(strcmp(root->cell_name, key)) {
    if(strcmp(root->cell_name, key) <= 0)
      root = root->right;
    else root = root->left;
    if(root == NULL) break;
  }
  return root;
}

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

Применение двоичного дерева значительно уменьшает время вставки и поиска элементов по сравнению со связанным списком. Следует помнить, что последовательный поиск требует в среднем n/2 сравнений, где n — количество элементов списка. По сравнению с этим двоичный поиск требует только log2n сравнений (если дерево сбалансировано). Кроме того, двоичные деревья так же экономно расходуют память, как и связанные списки. Тем не менее, в некоторых ситуациях есть лучшие альтернативы, чем двоичные деревья.


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

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.