Здесь приведены функции для обработки строк. Аналоги для некоторых имеются в стандартных библиотеках языка С.
Скачать файл заголовков(.h), а также библиотеку (.lib).
/************** Tree ***************/
Функции для деревьев
(связь в них двунаправленная)
Графические схемы –
struct ListP *MakeRootElement(char * source);
Создает корневой элемент дерева и добавляет туда строку source. Возвращает указатель на этот самый корневой элемент.
struct ListP *MakeRootElement1(char *
source,int N);
То же самое, но из массива source берется N байт.
int AddNewTreeToNodeEnd(struct ListP *P0,struct
ListP *P1);
Добавляет поддерево (указатель на корень этого поддерево – P1) в качестве последнего элемента узла, адрес которого – P0. Напоминаю, что в узле дерева может находиться несколько элементов. Возвращает 1 в случае удачи и 0 в случае неудачи.
struct ListP *GetNodeAddress(struct ListP
*P0,char *S);
Возвращает адрес узла, путь к которому (похожий на путь в файловой системе – примеры: “*”, “*0”, “*0*1”, “*0*2*7*0”, номер – позиция в узле, нумерация – с нуля) – в строке S. Адрес дерева, в котором происходит поиск – P0. В случае неудачи возвращает NULL.
Кстати, * - путь к корневому элементу.
int ReadOnAddress(struct ListP *P0,char
*Address,char *dest);
Читает в строку dest элемент дерева P0, который находится по пути в строке Address. Если ничего ен найдено, возвращает NULL.
int ReadOnAddress1(struct ListP *P0,char
*Address,char *dest,int N);
Читает в массив dest N байт элемента дерева P0, который находится по пути в строке Address. Если ничего ен найдено, возвращает NULL.
struct ListP *GetOneOfNextAddresses(struct
ListP *P,int Pos);
Возвращает адрес поддерева с номером Pos (отсчитывается от 0), присоединенного к узлу с адресом P. Если возвращено NULL, значит поддерева с таким номером нет.
struct ListP *GetPrevAddress(struct ListP *P0);
Возвращает адрес родителя узла P0. Если NULL, то родителя нет.
struct ListP *RepTreeInNode(struct ListP
*P0,struct ListP *P1,int Pos);
Заменяет (Pos)-е поддерево, прикрепленное к узлу с адресом P0, поддеревом с адресом корневого элемента P1. Возвращает адрес поддерева, которое было прикреплено к этому узлу раньше, то есть было заменено. Оно не удаляется.
int AddTreeToNode(struct ListP *P0,struct ListP
*P1,int Pos);
Добавляет поддерево с адресом корневого элемента P1 в узел с адресом P0 на место с номером Pos (отсчитывается от 0). Остальные поддеревья сдвигаются. Если Pos слишком велико, ставит в конец. Возвращает 1, если все хорошо и 0, если не удалось выделить память.
void DelTree(struct ListP *P);
Уничтожает дерево с адресом корневого элемента P и освобождает занятую им память.
int DelTreeInNode(struct ListP *P0,int Pos);
Уничтожает (Pos)-е поддерево, прикрепленное к узлу P0. Возвращает 0, если такого поддерева нет и 1, если оно есть (точнее говоря было, т.к. оно уже уничтожилось).
int RepOnAddress(struct ListP *P0,char
*Address,char *source);
Заменяет в дереве с корнем P0 элемент-строку по пути Address на ту, что по адресу source. Возвращает 0, если элемент не найден и 1 в случае удачи.
int RepOnAddress1(struct ListP *P0,char
*Address,char *source,int N);
То же самое, что и предыдущая функция, но заменяет не строку, а N-байтовый массив (адрес исходного массива - source). То-есть то, что раньше было в узле (строка, заканчивающаяся нулем или массив – убирается, и на это место встает массив из N байт (на это место – имеется ввиду не физическая память, а место в дереве))
int LenInNode(struct ListP *P);
Возвращает число поддеревьев, подсоединенных к узлу с адресом P.
int LenOnAddress(struct ListP *P0,char
*Address);
Возвращает число поддеревьев, подсоединенных в дереве с адресом P0 к узлу по пути Address. Возвращает -1, если поддерево по этому пути не найдено.
int AddToEndOnAddress(struct ListP *P0,char
*Address,char *source);
Добавляет к узлу дерева P0 по пути Address подчиненный узел с содержимым source (последним, если есть другие подузлы). Возвращает 0 в случае неудачи и 1 в случае удачи.
int AddToEndOnAddress1(struct ListP *P0,char
*Address,char *source,int N);
То же самое, но из source берется N байт.
int WhatIsMyNumber(struct ListP *P0);
Сообщает каким номером выходит из родительского узла (или стоит в родительском узле) подузел P0 (нумерация от 0). Если (–1) – значит родителя нет. Если меньше –1 – значит другая ошибка.
int WhatIsMyWay(struct ListP *P0,char *dest);
Узнает путь к узлу P0 и записывает его в dest. Возвращает 1 в случае успеха, 0 в случае неудачи.
int ReadInNode(struct ListP *P0,char *dest);
Читает элемент узла с адресом P0. Возвращает 1 в случае удачи, 0 в случае неудачи.
int ReadInNode1(struct ListP *P0,char *dest,int
N);
То же самое, но читает N байт.
struct ListP * WaysInTreeToList(struct ListP
*P0,struct ListP *PR);
Пути всех элементов дерева P0 помещает в список и возвращает его адрес. При запуске PR должно быть NULL. Если P0 = NULL, возвратит NULL.
struct ListP * SearchInTree(struct ListP
*P0,char *S,struct ListP *PR);
Ищет строку S в дереве P0, найденные пути помещаются в список, адрес которого возвращается. При запуске PR должно быть NULL. Если P0 = NULL, возвратит NULL.
struct ListP * SearchEndsInTree(struct ListP
*P0,struct ListP *PR);
Ищет концевые точки дерева и помещает их пути в список, адрес которого возвращается. При запуске PR должно быть NULL. Если P0 = NULL, возвратит NULL
int CountWords1_42(char *S0);
Возвращает количество уровней в пути (строка с путем – S0). Например –
“*” - 0
“*1” – 1
“*1*3” или “*1*4”- 2
и др.
Примечание – в пути – не более 9999 знаков, в слове, то-есть в отрезке строки между разделяющими символами (в данном случае *) – не более 999.
int CountWords1(char *S0,char Sp,char D);
Возвращает количество слов в S0, разделитель –D, роль пробела играет Sp (вначале удаляются).
struct ListP * NodesOnLevelToList(struct ListP
*P0,int N,struct ListP * PR);
Ищет узлы, стоящие на N-м уровне от корня дерева P0 (корень – 0-й уровень) и помещает их в список, адрес которого возвращает. При запуске PR должно быть NULL. Если P0 = NULL, возвратит NULL.
struct ListP * NodesFromNodeToList(struct ListP
*P0,char *Address);
Выводит в список элементы в подузлах, подключенных к узлу с путем Address, и возвращает адрес этого списка. В случае неудачи возвращает NULL.
struct ListP * NodesFromNodeToList1(struct
ListP *P0,char *Address,int N);
То же самое, но в подузлах читает по N байт.
Получающийся список желательно пояснить с помощью графической схемы –
struct ListP * FindRoot(struct ListP *P0);
Ищет адрес корневого элемента дерева , зная адрес P0 какого-либо подузла.
struct ListP * ListToTree(struct ListP *P0);
Из списка специального вида (с адресом P0) делает дерево (и возвращает его адрес). В случае неудачи возвращает NULL.
struct ListP * CopyTree(struct ListP *P0,struct
ListP *PR);
Копирует дерево P0, возвращает адрес скопированного дерева. PR Должно быть NULL. В случае неудачи возвращает NULL.
struct ListP * TreeToList_(struct ListP
*P0,struct ListP *PR);
Копирует элементы дерева P0 в список (его адрес возвращается), при этом само дерево портится (структуры данных изменяются). PR Должно быть NULL. В случае неудачи возвращает NULL.
struct ListP * TreeToList(struct ListP *P0);
То же самое, но дерево не портится. 2-го параметра нет, NULL загонять не нужно.
int CompareTrees(struct ListP *P0,struct ListP
*P1,struct ListP *PR);
Сравнивает деревья P0 и P1. Если P0 или P1 равно NULL, возвратит (-1).
Если одинаковы – возвратит 0.
Если разные – 1.
int ChangeMembersInTree(struct ListP *P0,char
*Address,int i,int j);
У узла дерева P0 по пути Address меняются местами подчиненные узлы с номерами i и j. Напоминаю, что нумерация идет с 0. В случае удачи возвращает 1, в случае неудачи – 0.
struct ListP * TextFileToList_std(char *filename);
Из строк текстового файла делает список, адрес которого возвращается. Символы 13 и 10 выкидываются. В случае неудачи возвращает NULL.
struct ListP * FileToTree(char *filename);
Текстовый файл (специального вида) экспортирует в дерево (адрес которого возвращает). В случае неудачи – NULL.
int TreeToFile(struct ListP *P,char *filename);
Сохраняет дерево в текстовом файле (специального вида). В случае удачи возвращает 1, в случае неудачи – 0.
int AddListOnAddress(struct ListP *P,struct
ListP *P1,char *Address);
Добавляет к узлу дерево P (путь к узлу – Address) серию подузлов с содержимым из списка P1 (узлы добавляются в конец, то-есть после уже находящихся). В случае удачи возвращает 1, в случае неудачи – 0.
/**************/
void ToLOW1(unsigned char *S);
Преобразует символы строки S1 к нижнему регистру (обычная, то-есть досовская кодировка русских букв, еще ее называют альтернативной).
ОЧЕРЕДЬ
Внутренние параметры –
Int B – номер байта, где начало очереди (где самый старый элемент). Нумерация – с нуля.
Int E – номер байта, где конец очереди (первый свободный элемент).
Int L – длина очереди (максимальная).
Char HeadTail – сперва 0, потом, когда E=B (голова достигла хвоста), устанавливается в 1, потом же, когда занятые элементы будут освобождаться (и голова расцепится с хвостом), опять станет 0.
void
* CreateQueue(int N);
Создает очередь (длина N). В случае удачи возвращает указатель на очередь, в случае неудачи – NULL.
Примечание (насчет внутренних параметров ): при создании устанавливаются E,B,HeadTail – в 0, L – в N.
int DeleteQueue(void *pQ);
Уничтожает очередь с адресом pQ (освобождает память). Если pQ=NULL, возвратит (-1). Если не NULL – возвратит 0.
int AddToQueue(void *pQ,char C);
Добавляет 1 байт (тот, что в C) в очередь pQ. Если очередь заполнена, новый байт затирает старый. Если pQ=NULL, возвратит (-1). Если не NULL – возвратит 0.
int GetFromQueue(void *pQ,char *Res);
Читает байт из очереди (и вынимает его, то-есть заполненная часть очереди становится меньше). Байт помещается по адресу Res.
Если успех, возвратит 0.
Если pQ=NULL, возвратит (-3).
Если длина очереди <1, возвратит (-2).
Если (голова)=(хвост), а это бывает, когда очередь пуста, возвратит (-1), но байт все равно берет и помещает по адресу Res. То-есь, если очередь пуста, возвратит (-1), но все-равно что-то прочитает.
int
GetLengthOfQueue(void *pQ);
Возвращает длину очереди (максимальную, а не количество помещенных символов). Если pQ=NULL, возвратит (-3).
int
GetParOfQueue(void *pQ,int A);
Это функция для диагностики внутренних параметров очереди.
Если A=0, возвратит B (откуда берется).
Если A=1, возвратит E (куда кладется).
Если A=2, возвратит L (длина очереди).
Если A>2, возвратит HeadTail (параметр, равный 0, если голова не достигает хвоста, и 1, если достигает, то-есть очередь полна).
Если pQ=NULL, возвратит (-3).
int
GetStringFromQueue(void *pQ,char *S);
Вынимает из очереди байты и помещает их в S. S заканчивается нулем. Очередь при этом очищается.
Если очередь пуста, в S помещается нуль в самом начале. Если pQ=NULL, возвратится (-1), если не NULL – то 0.
int
LookStringInQueue(void *pQ,char *S);
Просто читает все символы из очереди (не изменяя состояния очереди, не очищая ее). Прочитанные символы помещаются в S. S заканчивается 0. Возвращает:
-3 – если pQ=NULL,
-2 – если длина очереди <1,
-1 – очередь пуста,
0 – в остальных случаях.
int
LookArrayInQueue(void *pQ,char *S,int M);
То же самое, но читает в S первые M символов. Если M<(число символов в очереди), S заканчивается 0.
int AddToQueueNoErase(void *pQ,char C);
Тоже добавляет в очередь байт C, но если очередь полна, то байт не добавляется, затирания не происходит. Возвращается при этом (то-есть когда очередь полна) 1. Если pQ=NULL, возвращается (-1). В случае успеха возвращается 0.
int
AddArrayToQueueNoErase(void *pQ,char *S,int N);
Помещает N байт массива S в очередь pQ без затирания уже ранее добавленных.
Если pQ=NULL, возвратит (-1).
В противном случае (pQ не равно NULL) возвратит число добавленных байт.
int
GetArrayFromQueue(void *pQ,char *S,int N);
Пытается взять N байт из очереди pQ и поместить их в массив S. Если pQ=NULL, возвратит (-1). Если pQ не равно NULL, то возвращает число взятых байт. Если какой-то байт не удалось взять, функция заканчивает работу, записав в S 0 (ноль) – на место, где должен был быть байт, который неудачно попытались взять.
int
UniversalScanner(struct ListP *P1,
struct ListP *P2,
void *Q1,
void *Q2,
char B,
void (*F0)(struct ListP *),
int Sw);
Это – сложная функция (в 2 словах что она делает не объяснишь). В нее засылается раз за разом байт B.
P1 – список со строками-образцами поиска в засылаемом потоке байтов.
P2 – список для результатов поиска. В 1-й элемент помещается обнаруженный образец, а в 0-й элемент – фрагмент между нынешним найденным образцом и предыдущим (или началом работы, если нынешний найденный образец – первый). Этот список с результатами передается в функцию F0 (вызывается при обнаружении образца).
Q1 – “малая” очередь (для служебных целей – используется во внутренней работе функции, должна быть создана перед запуском функции). По длине равна самому длинному из образцов поиска.
Q2 – “большая” очередь (тоже для служебных целей – используется во внутренней работе функции). По длине равна максимальной длине фрагмента, которые нас интересуют (фрагменты – это промежутки между образцами, допустим если образец –это строка из 2 байт 13 и 10, тогда фрагмент – это строка текстового файла).
B – передаваемый байт (передается по очереди много байт, для каждого вызывается функция).
F0 – указатель на функцию. Она вызывается при нахождении образца и в нее передается список P2.
Sw – если 0 , то ищет промежутки между образцами (или между первым образцом и началом потока символов, если найденный образей – первый). Если же закончили передавать байты и хотим знать, что осталось после последнего найденного образца - вызываем с Sw=1. Параметр B при этом любой.
Чтобы все это понять, нужно посмотреть примеры.
Возвращает – 0 – если успех (то-есть работа прошла нормально, а не то, что что-то найдено).
-1 – Если P1 – NULL
-2 – Если P2 – NULL
-3 – Если Q1 – NULL
-4 – Если Q2 – NULL
-9 - если (длина P2)<2
-6 - если (длина P1)<1
-5 – если не удалось добавить в Q1 и Q2
-7 – не удалось посмотреть в Q1
-8 – не удалось посмотреть содержимое в Q2
int UniversalScanner0(struct ListP *,
struct ListP *,
void *,
void *,
char,
void (*)(struct ListP *));
Это первоначальный вариант предыдущей функции – без параметра Sw. После последнего вхождения образца остаток потока байтов недоступен (то-есть его не получишь с помощью этой функции).
Примеры использования UniversalScanner
СТЕК
Параметры –
Int B – голова стека (куда кладем байт).
Int L – длина (максимальная).
Далее N байт под данные.
void * CreateStack(int N);
Создает стек длиной N. Dвозвращает NULL в случае неудачи, адрес стека в случае удачи.
Примечание насчет внутренних параметров – при создании – B=0, L=N.
int DeleteStack(void *pQ);
Удаляет стек с адресом pQ. Если pQ=NULL, возвратит (-1). В противном случае – 0 (т.е. когда pQ не NULL).
int
AddToStack(void *pQ,char C);
Добавляет байт C в стек.
Если pQ=NULL, возвратит (-1).
Если стек полон (B=L) – возвратит 1.
Если (B>L), возвратит 2. Хотя такого по логике работы программы появляться не должно.
В случае успеха – 0.
int
GetFromStack(void *pQ,char *Res);
Читает байт из стека с адресом pQ.
Если pQ=NULL, возвратит (-3).
Если стек пуст (B=0) – возвратит 1.
Если (B>L), возвратит (-1). Хотя такого по логике работы программы появляться не должно.
Если L<1 – возвратит (-2).
В случае успеха – 0.
int AddArrayToStack(void *pQ,char *S,int N);
Добавляет N байт массива S в стек pQ.
Если pQ=NULL, возвратит (-1), иначе – возвратит число добавленных байт.
int GetArrayFromStack(void *pQ,char *S,int N);
Берет из стека pQ N байт и помещает их по адресу S.
Если pQ=NULL, возвратит (-1), иначе – возвратит число взятых байт.
int AddArrayToStackNoPart(void
*pQ,char *S,int N);
Помещение в стек массива (как и AddArrayToStack). Но массив помещается в стек весь (не частью). Если же N<(остающееся свободное пространство), возвращается (-2) и в стек ничего не добавляется.
Если pQ=NULL, возвратит (-1), иначе – возвратит число добавленных байт (это число по логике работы функции должно быть N).
Примечание – эта функция введена чтоб решить такую проблему. Если последняя порция данных (то-есть массив) закачалась в стек не вся, а назад берем такими-же порциями, то все спутается (получать будем не то, что клали). Все вынимаемые элементы исказятся.
Похожая проблема есть, кстати, и с очередью. Правда там, если последний массив не уберется, при вынимании искаженным окажется только он, а не все.
Вообще говоря желательно – если все массивы одинаковые, то длину очереди (и стека) делать кратной их длине.
int GetParOfStack(void *pQ,int A);
Это функция для диагностики внутренних параметров стека.
Если A=0, возвратит содержимое указателя на голову (т.е. B) – это есть реальная длина стека..
Иначе – длина стека (максимально возможная) - L.
Если pQ=NULL, возвратит (-3).
Еще – методы из Windows-программ:
void CTree1Dlg::CopyTree0(struct ListP
*P0,struct ListP *pPR,HTREEITEM hP)
Для копирования дерева P0 в элемент управления (дерево). pPR=NULL при вызове.
Вызов - CopyTree0(PP_other1,NULL,TVI_ROOT);
InvalidateRect(NULL);
void CTree1Dlg::CopyList0(struct ListP *P0,int
D)
Для копирования списка в контрол-список.
Вызов - CopyList0(PL1,IDC_LIST1);
InvalidateRect(NULL);
Пример тестовой Windows-программы (MS Visual C++ 5.0) с использованием деревьев