12.4 Использование кода Дьюи в древовидных списках

В конце 19 века американец Мельвиль Дьюи предложил универсальную десятичную классификацию. В 1876 г. вышло первое, очень краткое, издание таблиц этой классификации. Предложенный код Дьюи удобно использовать для указания узлов дерева. Например, корень дерева всегда 1., сыновья корня слева направо - 1.1., 1.2., 1.3. и т.д. Сыновья узла 1.2. будут иметь соответственно коды: 1.2.1, 1.2.2., 1.2.3. и т.д. Количество чисел в коде показывает глубину дерева.

Ниже предлагается механизм работы с древовидными списками на основе кода Дьюи.

Запишем ряд определений
1. Размер кода Дьюи, предполагается, что глубина дерева не превышает 100.
#define CODEDEWEYSIZE 100
2. Задаем новый тип CodeDewey
typedef int CodeDewey[CODEDEWEYSIZE];
Запишем Функцию преобразования строки символов в код
Дьюи (CodeDewey).
int* AscizToCodeDewey(CodeDewey c,char *str)
{
      //преобразование строки в код дьюи
      int i=0;
      int k=0;
      char num[6]; //строка для выделения числа
      c[0]=1; c[1]=0;//начальные значения кода
      while(1) {
            if(isdigit(*str)) {
                  if(i<5) num[i++]=*str; //здесь предполагается, что число не превышает 5 рязрядов
                  str++;
            }
            else
                  if(*str==’.’) { //преобразовать в число
                        num[i]=0; i=0;
                        if(k<CODEDEWEYSIZE-1) c[k++]=atoi(num);//вызвать библиотечную функцию atoi
                        str++;
                  }
                  else
                        if(*str==0) { //конец строки
                             c[k]=0; //признак конца
                             break;
                        }
                        else str++; //пропускаем
      }
      return &c[0];
}
Функция преобразования кода Дьюи в строку символов
void CodeDeweyToAsciz(char *str,CodeDewey c)
{//обратное преобразование
      char snum[6];
      str[0]=0;
      for(int i=0; i<CODEDEWEYSIZE; i++) {
            if(c[i]>0) {
                  sprintf(snum,"%d.",c[i]);
                  strcat(str,snum);
            }
            else break;
      }
}

Входные параметры
NodeTreeList node- адрес корня древовидного списка
void(*func)(void*,CodeDewey) - указатель на функцию обработки
узла с заданным кодом Дьюи (ниже описан пример такой функции OutWithCode)
CodeDewey c- код Дьюи узла
int Level - переменная содержащая глубину рассматриваемого узла.
void ForEachTreeListLeftNodeWithCode(NodeTreeList *node, void(*func)(void*,CodeDewey),CodeDewey c,int level)
{
      if(node==NULL) return;
      func(node->data,c);
      c[level+1]=1; c[level+2]=0;
      ForEachTreeListLeftNodeWithCode(node->down,func,c,level+1);
      c[level+1]=0; c[level]++;
      ForEachTreeListLeftNodeWithCode(node->right,func,c,level);
}
Функция поиска узла с заданным кодом Дьюи
NodeTreeList* FindTreeListNode(KruTreeList *tree, CodeDewey c)
{
      int i=0;
      int cont=c[i];
      NodeTreeList*addr=tree->root;
      while(i<CODEDEWEYSIZE) {
            for(int k=0; k<(c[i]-1); k++) { //движение вправо
                  if(addr==NULL) return NULL;
                  if(addr->right!=NULL) addr=addr->right;
                  else return NULL;
            }
            i++;
            if(c[i]==0) return addr; else addr=addr->down;
      }
      return addr;
}
Функция для запуска алгоритма ForEachTreeListLeftNodeWithCode
void OutWithCode(void *str,CodeDewey c)
{
      char sCode[100];
      CodeDeweyToAsciz(sCode,c);
      printf("%s %s\n",sCode,(char*)str);
}
Тестовый пример показывающий работу описанных функций
char *classif[] = { "Enimal", "xxxx", "yyyy", "zzzzz", "kkkkk"};
void KruTestTreeListDewey()
{
      char sCodeDewey[100];
      KruTreeList tree;
      CodeDewey code;
      AscizToCodeDewey(code,"1.333.5.6.80.23");
      CodeDeweyToAsciz(sCodeDewey,code);
      printf("%s\n",sCodeDewey);
      tree.root=CreateTreeListNode((void*)classif[0]);
      AscizToCodeDewey(code,"1.");
      NodeTreeList* addr=FindTreeListNode(&tree,code);
      printf("Add -> %s\n",(char*)(addr->data));
      for(int i=1; i<3; i++)
            AddTreeListNodeRightSon(addr,(void*)classif[i]);
      AscizToCodeDewey(code,"1.1.");
      addr=FindTreeListNode(&tree,code);
      printf("Add-> %s\n",(char*)(addr->data));
      for(int i=3; i<5; i++)
            AddTreeListNodeRightSon(addr,(void*)classif[i]);
      ForEachTreeListLeftNode(tree.root,Out);
      printf("_________________\n");
      ForEachTreeListLeftLeaf(tree.root,Out);
      AscizToCodeDewey(code,"1.");
      ForEachTreeListLeftNodeWithCode(tree.root,OutWithCode,code,0
      printf("________________\n");
      while(!kbhit());
}
void Out(void* str) {
      printf("%s\n",(char*)str);
}