Programmirovanie_i_osnovyi_algo
.pdfKey Word (если |
строка найдена, то |
ее индекс line, а флаг результата |
|
поиска found=\) |
или получить ответ, что такой строки в таблице нет |
||
(found=0). |
|
|
|
Основными способами поиска в таблице являются. |
|||
/. Последовательный |
поиск. |
Эффективность поиска (среднее |
|
число обращений к таблице для нахождения искомой строки) равна size/2.
2, Логарифмический |
поиск (бинарный, с помощью двоичного |
||||
дерева). Число обращений к таблице равно \Q>%^{size). |
|
||||
J. ПоисКу использующий |
прямой доступ |
к таблице. |
Число |
||
обращений к таблице равно единице. |
|
|
|||
4. Поиск |
с использованием |
перемеиганной, |
слабо |
заполнен |
|
ной таблицы |
(хэт-таблицы). |
Число обращений к таблице близко к |
|||
единице. |
|
|
|
|
|
Рассмотрим перечисленные способы поиска, кроме малоупотребимого поиска с прямым доступом, рассмотренного в [6].
17.2. Последовательный поиск
Пример таблицы, заполненной для последовательного поиска, показан на рис. 97.
|
lesson |
лекция |
П |
|
|
Р |
|||
|
type |
тип |
о |
|
|
с |
|||
|
word |
слово |
||
|
м |
|||
size-1 |
work |
работа |
о |
|
т |
||||
|
|
|
||
|
ключ |
данное |
|р| |
|
|
^-*^ |
|||
Рис. 97. Пример таблицы для последовательного |
поиска |
|||
Поиск выполняется в полностью заполненной таблице. Про смотр таблицы выполняется последовательно, в соответствии с рос том индексов строк таблицы. Если в какой-то строке таблицы поле ключа совпадает с KeyWord^ то поиск окончен с результатом "на шли". Если этого не произошло, а конец таблицы достигнут - поиск окончен с результатом "не нашли".
Для таблицы, показанной на рис. 97, для ключевого слова |
word |
||
результатом поиска 6yjXQT found |
= 1; line |
= 2. Аналогично, для клю |
|
чевого слова a«<i результатом поиска 6yjxQT found = 0. |
|
||
Как указано выше, эффективность |
поиска определяется |
чис |
|
лом обращений к таблице. Для |
последовательного поиска эффек- |
||
290
тивность поиска составляет в среднем size/2 обращений. Программный проект, в котором содержатся определения
функций для поиска в таблице и пример их использования, приво дится ниже. В примере на данном этапе следует рассмотреть только данные и те фрагменты проекта, которые относятся к функции SequentialSearch для последовательного поиска в таблице. К числу та ких фрагментов относятся, в том числе, функции AllocTableDM (размещение таблицы в динамической памяти), FreeTableDM (осво бождение занятой таблицей динамической памяти), SeqlnpTab (за полнение таблицы), PrintTab (печать содержимого таблицы) и PrintSearch (вывод результатов поиска).
/* |
Файл |
|
TestSearch.срр. |
|
|
|
|
|
|
|
|
|
||
|
|
в |
таблице. |
|
|
|
|
|
|
|||||
|
Тестирование |
поиска |
таблице |
приведено |
в файле |
|||||||||
|
Определение |
методов |
поиска |
в |
||||||||||
Sea rch Tab! |
е. срр. |
|
|
|
- файл SearchTable. |
|
h. |
|
||||||
|
Заголовочный |
файл проекта |
|
|
||||||||||
|
Для |
откытия |
и |
закрытия |
файлов |
используются |
|
универсальные |
||||||
функции^ |
|
определенные |
|
в |
файлах |
OpenCloseFile.h |
и |
|||||||
OpenCloseFile.срр. |
Консольное |
приложение. |
Visual |
|
C++ 6 |
|
||||||||
*/ |
Давыдов |
В.Г. |
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// |
Включаемый |
файл |
программного |
проекта для |
поиска в |
таблице |
||||||||
^include |
|
"SearchTable.h" |
|
|
|
|
|
|
|
|
||||
±nt |
main |
( |
|
ArgC, |
// |
Возвращает |
О при |
|
успехе |
|
||||
|
±nt |
|
|
// |
Число |
аргументов |
в |
командной |
||||||
//строке
|
dbai: |
|
|
*ArgV[ |
] |
) / |
/ Массив |
указателей |
|
на |
аргументы |
|||||||
|
|
|
|
|
|
|
|
// |
командной |
строки |
(ArgV[ |
О ] |
- |
|||||
|
|
|
|
|
|
|
|
// |
.ехе |
файл, |
в |
|
интегрированной |
|||||
|
|
|
|
|
|
|
|
// |
среде |
программирования |
известен |
|||||||
|
|
|
|
|
|
|
|
// |
и |
не |
задается/ |
2 |
ArgV[ |
1 |
] - |
файл |
||
|
|
|
|
|
|
|
|
// |
ввода/ |
ArgV[ |
] |
- |
файл |
вывода) |
||||
{ |
// |
Проверка |
|
числа |
аргументов |
командной |
|
строки |
|
|
||||||||
|
|
|
|
|
||||||||||||||
|
±f( |
ArgC |
!= |
3 ) |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
{ |
printf( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
"\n |
|
В командной |
строке |
должно |
быть |
три аргумента: |
" |
|||||||||||
Ошибка |
5. |
|||||||||||||||||
"\п |
Имя_проекта. |
|
ехе имя_файла_ввода |
имя_файла_вывода |
\п" ) / |
|||||||||||||
|
|
exi |
t ( |
5 |
) / |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// |
Создаем |
|
и |
инициализируем |
таблицу |
из |
4 |
строк |
|
|
|||||||
|
AllocTableDM( |
|
4 ) / |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
±пЬ |
|
|
|
found, |
|
// |
1 - |
нашли ключевое |
|
слово |
|
|
|||||
|
|
|
|
|
line/ |
|
// |
Индекс найденной |
|
строки |
|
|
||||||
291
// Заполняем |
таблицу |
для |
последовательного |
|
поиска |
и |
||||||||||
// |
печатаем |
ее |
1 ] |
) ; |
|
|
|
|
|
|
|
|
|
|
||
SeqInpTab |
( |
ArgV[ |
|
|
|
|
|
|
|
|
|
|
||||
PrintTab( |
ArgV[ |
2 |
7/ |
"^"г |
таблицы:" |
|
) |
; |
|
|
|
|||||
|
|
|
" |
|
|
Состояние |
|
|
|
|
||||||
// |
Тестирование |
последовательного |
поиска |
в |
таблице |
|||||||||||
FILE |
|
*pStructFlleOut |
= |
OpenFile( |
|
|
ArgV[ |
2 |
], |
"a", |
||||||
fprintf( |
|
pStructFileOutr |
|
|
|
|
|
170 |
) ; |
|
|
|||||
|
последовательного |
|
|
поиска |
|
\л" ) ; |
||||||||||
|
"\n\n |
|
Тестирование |
180 |
|
|||||||||||
CloseFile( |
|
pStructFileOut, |
ArgV[ |
2 7, |
) |
; |
|
|
||||||||
SequentialSearch |
( |
"and", |
founds |
line |
) |
; |
|
"and" |
) |
; |
||||||
PrintSearchi |
|
ArgV[ |
2 |
], |
"a", |
found, |
line, |
; |
||||||||
SequentialSearch( |
|
"word", |
found, |
line |
) |
|
"word" |
|
) ; |
|||||||
PrintSearch( |
|
ArgV[ |
2 |
], |
"a", |
found, |
line, |
|
|
|||||||
// |
Заполняем |
таблицу |
для |
логарифмического |
|
|
поиска |
|
и |
|||||||
//печатаем ее
InpTabLog( |
ArgV[ |
2 |
1 ] |
) |
; |
|
|
|
|
|
|
|
|
||
PrintTab( |
ArgVf |
], |
|
"a", |
|
|
|
|
|
|
|
||||
|
|
" |
|
|
|
Состояние |
таблицы:" |
) |
; |
|
|
||||
// |
Тестирование |
|
логарифмического |
|
поиска |
в |
таблице |
|
|||||||
pStructFileOut |
|
|
= OpenFile( |
ArgV[ |
2 |
], |
"а", |
190 ) |
; |
|
|||||
fprintf( |
|
pStructFileOut, |
|
|
|
|
|
|
|
|
|||||
|
"\n\n |
Тестирование |
|
логарифмического |
200 |
поиска |
\п" ) ; |
||||||||
CloseFile( |
pStructFileOut, |
|
ArgV[ |
2 |
], |
) ; |
|
|
|||||||
LogariphmSearch |
|
( |
"and", |
|
found, |
|
line |
) ; |
|
"and" |
) |
; |
|||
PrintSearch |
( |
ArgVf |
2 |
], |
|
"a", |
found, |
line, |
|||||||
LogariphmSearch |
|
( |
"word", |
found, |
|
line |
) ; |
"word" |
) |
; |
|||||
PrintSearch( |
|
ArgV[ |
2 |
], |
|
"a", |
found, |
line, |
|||||||
// |
Заполняем |
таблицу |
для |
хэш-поиска |
и |
печатаем |
ее |
|
|||||||
BeginTable( |
ArgV[ |
1 |
], |
2 |
) ; |
|
|
|
|
|
|
|
|||
PrintTab( |
ArgV[ |
2 |
], |
|
"a", |
таблицы:" |
) |
; |
|
|
|||||
|
|
" |
|
|
|
Состояние |
|
|
|||||||
//Тестирование кэш-поиска в таблице
pStructFileOut |
|
|
= OpenFile( |
|
ArgV[ |
2 |
], |
"а", |
|
210 ) |
; |
|
|||
fprintf( |
|
|
pStructFileOut, |
|
хэш-поиска |
\n" |
) ; |
|
|
||||||
"\n\n |
Тестирование |
|
|
||||||||||||
CloseFile( |
pStructFileOut, |
|
ArgVf |
2 |
], |
220 |
) |
; |
|
|
|||||
HashSearch |
( |
"work", |
2 |
found, |
"a", |
line |
) |
; |
line, |
"work" |
) |
; |
|||
PrintSearchi |
|
|
ArgV[ |
], |
found, |
; |
|||||||||
HashSearch( |
( |
"type", |
2 |
found, |
"a", |
line |
) |
line, |
"type" |
) |
; |
||||
PrintSearch |
|
ArgVf |
], |
found, |
|
||||||||||
//Освобождение динамической памяти, занятой таблицей
FreeTableDMi |
) ; |
292
retuxm 0;
}
-_
Файл SearchTable.h. |
Включаемый файл для поиска в |
таблице. |
|||
Давыдов В. Г. Консольное приложение^ Visual |
C-h+ |
6 |
|||
V |
|
|
|
|
|
// Предотвращение возможности многократного |
подключения |
||||
// данного |
файла |
|
|
|
|
Hfndef |
SEARCHTABLE_H |
|
|
||
^define |
SEARCHTABLE_H |
|
|
||
^include |
<string.h> |
// Для строковых функций |
|
||
// |
Для открытия-закрытия файлов |
|
|
||
#Include |
"OpenCloseFile.h" |
|
|
||
const ±nt LKEY = 9; // Длина ключа в строке таблицы
//LKEY-1
//Длина данного в строке таблицы LDATA-1
const ±nt LDATA = 63;
//Тип для строки таблицы
stmict STRTAB
{
//Ключ
char кеу[ LKEY ];
//Данные
char data[ LDATA ];
} |
; |
|
|
|
// |
Объявление |
объектов с описателем класса хранения |
||
// |
внешний. |
Они доступны в других |
файлах проекта^ в |
|
// |
которых подключен |
данный файл |
|
|
extern STRTAB |
|
|
|
|
|
*рТаЫе; // |
Адрес первой |
строки таблицы в |
|
//динамической памяти
extern ±nt size; |
|
// |
Размер таблицы |
|
|
|||||
// |
Указатель на структуру со сведениями о файле |
ввода |
||||||||
extern FILE |
|
|
|
|
|
|
|
|
||
|
|
*pStructFlleInp; |
|
|
|
|
|
|||
// |
Прототипы функций |
|
|
|
|
|
|
|||
void |
AllocTableDM( |
int |
); |
|
|
|
|
|
||
void. |
FreeTableDM( |
void |
); |
|
|
|
|
|
||
void |
SeqInpTab ( char * ) ; |
|
|
|
|
|
||||
void |
PrlntTab ( char |
*pFlleOut, |
chstr |
*, char |
*pHead ); |
|||||
void |
SequentlalSearch |
( char |
[ ], |
int |
<5, int |
& ); |
|
|||
void |
PrlntSearch(,char |
|
*, char |
*, int, int, |
char |
[ ] ); |
||||
void |
Round( int ); |
|
|
|
|
|
|
|
|
|
void InpTabLog ( char * ); |
|
|
|
|
|
|||||
void |
LogarlphmSearch |
( char |
[ ], |
int |
&, int & ); |
|
||||
int |
Kod( char ); |
|
|
|
|
|
|
|
|
|
293
±nt |
Hash ( chstr |
[ |
] ) ; |
*, |
±nt ) |
; |
void. |
BeglnTable |
( |
сЬлг |
|||
void. |
HashSearch |
( |
сЪах: |
[ |
], inb |
&, inb & ) , |
§endif |
|
|
|
|
|
|
|
и |
Файл OpenCloseFile.h. |
Включаемый |
файл для |
функций открытия |
|||
закрытия |
файлов. |
программных |
|
проектах. |
|
||
|
Используются |
в любых |
|
Сч-+ 6 |
|||
|
Давыдов |
В.Г. |
Консольное |
приложение,. |
Visual |
||
// |
Предотвращение |
возможности многократного |
подключения |
||||
//данного файла
i^lfndef |
OPENCLOSEFILE_H |
|
|
|
^define |
OPENCLOSEFILE_H |
|
||
^Include |
<stdlo.h> |
// |
Для |
ввода-вывода |
ilnclude |
<stdllb.h> |
// |
Для |
функции exit ( ) |
//Прототипы функций
FILE |
* |
OpenFlle |
( char |
*, |
char |
*, inb |
) ; |
|
) ; |
||
void |
CloseFlle( |
|
FILE |
*, |
char |
*, int |
WarnNum |
||||
#endlf |
|
|
|
|
|
|
|
|
|
|
|
Файл |
OpenCloseFile.cpp. |
Универсальные |
|
функции |
открытия и |
||||||
3акрытия |
|
файлов. |
в |
любых программных |
проектах. |
|
|
||||
Используются |
C++ 6 |
||||||||||
Давыдов |
В.Г. |
Консольное |
приложение. |
Visual |
|||||||
*/
//Включаемый файл
ilnclude "OpenCloseFile.h"
//Открытие файла
FILE * |
OpenFlle |
( |
|
// |
Возвращает |
указатель |
на структуру |
|||
// |
Указатель |
на |
|
// |
со |
сведениями |
об |
открытом |
файле |
|
имя .расширение |
открываемого |
файла |
|
|||||||
сЬаг |
*pFl 1 eNam е , |
|
на режим |
открытия |
файла |
|||||
cha.r |
*pMode, |
// |
Указатель |
|||||||
// |
Номер ошибки |
или |
|
предупреждения |
|
|
|
|
||
int |
|
ErrWarnNum |
|
) |
|
|
|
|
|
|
{ |
Указатель |
на |
структуру со |
сведениями |
об |
открытом |
файле |
|||
// |
||||||||||
FILE |
|
*pStructFlle/ |
|
|
|
|
|
|||
//Открытие файла
pStructFlle |
= |
fopen |
( pFlleName, |
pMode ) ; |
|
if( |
IpStructFlle |
) |
|
|
|
{
294
printf(
"\n Ошибка %d. Ошибка открытия файла %s в режиме \"%s\"\п", ErrWarnNum, pFileName, pMode ) ;
exit ( ErrWarnNum )/
}
jc&tum pStructFile;
)
// Закрытие файла void. CloseFile (
//Указатель на структуру со сведениями о закрываемом
FILE *pStructFile,
//Указатель на имя.расширение закрываемого файла
char |
*pFileNaine^ |
Int |
WarnNum ) // Номер предупреждения |
{
//Закрытие файла
х£( fclose( pStructFile ) == EOF )
{
printf(
"\n Предупреждение %d. Файл %s не закрыт. \n" "\n Выполнение программы продолжается \n",
WarnNum^ pFileName );
}
геЬгит;
}
Файл SearchTable.cpp. Функции поиска в таблице:
* размещение таблицы в динамической памяти и ее инициа ЛИЗ а ция ;
*освобождение динамической памяти, занятой таблицей/
*заполнение массива значениями, читаемыми из файла на
магнитном диске (для последовательного поиска);
*заполнение таблицы значениями, читаемыми из файла на
магнитном диске (для логарифмического поиска); * вывод содержимого таблицы в файл на магнитном диске/
*последовательный поиск в таблице;
*вывод результатов поиска в таблице в файл на магнитном диске;
*обход вершин дерева с целью формирования словаря для
бинарного (логарифмического) |
поиска; |
|
|
||||
* бинарный (логарифмический) |
поиск в таблице, |
подготовленной |
|||||
в форме алфавитно-упорядоченного |
двоичного |
дерева/ |
|||||
* преобразование |
символа |
ключа |
~ строчная латинская буква, |
||||
цифра или пробел |
- в его порядковый номер |
(целое число) ; |
|||||
* хэш-функция ключа |
"KeyWord" из "LKEY-1" символа (символ - |
||||||
строчная латинская |
буква, |
цифра или пробел) |
для таблицы из |
||||
size строк; |
|
|
|
|
|
|
|
* начальная подготовка хэш-таблицы;
295
* |
поиск в хэш-таблице. |
|
|
|
|
||
|
Используется |
в программном проекте для |
поиска в |
таблице. |
|||
JV |
Давыдов В.Г. |
Консольное приложение^ Visual |
C-h+ |
6 |
I |
||
|
|
|
|
i |
|
|
|
// Включаемый файл программного проекта для |
поиска |
в |
таблице |
||||
^include |
"SearchTable.h" |
|
|
|
|
||
// |
Определения объектов с описателем класса хранения |
|
внешний. |
||||
// |
Их объявление имеется в заголовочном |
файле проекта и |
|||||
//доступно в других файлах проекта
STRTAB |
*рТаЫе; |
// Адрес первой строки таблицы в |
|
±nt |
|
// |
динамической памяти |
size; |
// Размер таблицы |
||
//Указатель на структуру со сведениями о файле ввода
FILE |
|
|
|
*pStructFileInp; |
|
||
// |
Размеш.ение таблицы в динамической памяти и ее |
||||||
// |
|
инициализация |
|
|
|||
void |
AllocTableDM( |
|
|
||||
|
±nt |
|
s |
) |
// Число строк таблицы |
||
{ |
// |
Проверяем г подходит ли размер таблицы? |
|||||
|
|||||||
|
±£( |
S < 1 ) |
|
|
|
||
|
{ |
|
|
|
|
|
|
|
|
|
printf( |
|
|
|
|
"\п |
Предупреждение |
10. Таблица должна содержать не менее" |
|||||
" двух |
строк" |
|
|
|
|||
"\п |
(задано |
%d строк) . Принимается размер таблицы 2. " |
|||||
"\п |
Выполнение |
программы продолжается. |
" ) ; |
||||
|
|
|
S = 2; |
|
|
|
|
|
} |
|
|
|
|
|
|
|
// |
|
Размещаем таблицу в динамической |
памяти |
|||
|
рТаЫе = new STRTAB[ s ] ; |
|
|||||
|
±f( |
!рТаЫе |
) |
|
|
||
|
{ |
|
printf( |
"\n |
Ошибка 20. Таблица |
не была размеш,ена " |
|
|
|
|
|||||
|
|
|
|
|
"в динамической памяти " ) ; |
||
|
|
|
exit( |
20 ) ; |
|
|
|
}
//Инициализация таблицы
fori ±nt i = О; i < s; 1ч-+ )
{
pTablef i ] . key[ 0 ] = '\0'/ pTablel i ].data[ 0 ] = '\0';
}
size = s;
jretujrn/
296
// Освобождение динамической памяти, занятой таблицей
void |
FreeTableDM( |
void |
) |
|
|
|
||
{ |
|
|
) |
|
|
|
|
|
xf( рТаЫе |
|
|
|
|
|
|
||
{ |
delete |
|
[ ] |
рТаЫе; |
рТаЫе |
= NULL; |
|
|
} |
|
|
||||||
|
|
|
|
|
|
|
|
|
} |
|
|
|
|
|
|
|
|
// Заполнение |
массива |
значениями, |
читаемыми |
из файла на |
||||
// |
магнитном |
( |
диске |
|
(для |
последовательного |
поиска) |
|
void |
SeqInpTab |
на |
файл |
ввода |
|
|
||
// |
Указатель |
|
|
|||||
сЬаг |
|
*pFlleInp |
) |
|
|
|||
{
//Открытие файла для чтения
FILE |
*pStructFileInp |
|
= OpenFile |
( |
pFilelnp, |
|||||||
|
|
|
|
|
|
|
|
|
"г", |
|
30 |
) ; |
// Заполнение |
массива |
|
|
|
|
|
|
|
|
|||
£ою ( ±nt |
1=0; |
Ksize; |
|
i + + |
) |
|
|
|
|
|
|
|
{ |
fscanfi |
pStructFilelnp, |
|
" |
%s |
%s", |
|
|
|
|||
±f( |
|
|
|
|
||||||||
|
pTablef |
i |
].key, |
pTable[ |
i |
].data |
) |
!= |
2 ) |
|||
{ |
printf( |
"\n |
Ошибка |
40. |
Ошибка |
чтения |
строки^ |
|||||
|
||||||||||||
|
exit( |
" |
) |
таблицы |
с индексом |
%d ", |
i |
) ; |
|
|||
|
40 |
; |
|
|
|
|
|
|
|
|
||
}
}
//Закрытие файла ввода
|
CloseFile( |
pStructFilelnp, |
|
pFilelnp, |
50 |
) |
; |
|
|
return/ |
|
|
|
|
|
|
|
} |
|
|
|
|
|
|
|
|
// |
Заполнение |
таблицы |
значениями, |
читаемыми |
из |
файла на |
||
// |
магнитном |
диске |
(для |
логарифмического |
|
поиска) |
||
void |
InpТаbLog |
( |
|
|
|
|
|
|
|
// Указатель на файл |
ввода |
|
|
|
|
||
|
сЬаг |
*pFileInp |
) |
|
|
|
|
|
{
//Открытие файла для чтения
pStructFilelnp |
= |
OpenFile( |
pFilelnp, |
"г", 60 |
) ; |
Round( 1 ) ; |
|
// |
Рекурсивное |
заполнение |
таблицы |
// Закрытие |
файла |
ввода |
|
|
|
297
CloseFile( |
|
pStructFilelnp, |
|
|
pFllelnp, |
70 |
) |
|
|
|
||||
retvLrn; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// Вывод содержимого таблицы |
в файл |
на магнитном |
|
диске |
|
|||||||||
void |
PrintTab( |
*pFlleOut,// |
|
Указатель |
на |
файл |
вывода |
|
||||||
char |
|
// |
файла |
|||||||||||
char- |
|
*pMode^ |
) |
Указатель |
на |
режим |
открытия |
|||||||
char |
|
"^pHead |
// |
Указатель |
на |
заголовок |
для |
печати |
||||||
{ |
Открытие |
файла |
для |
|
записи |
|
|
|
|
|
|
|
||
// |
|
OpenFile |
( pFileOut, |
pMode, |
||||||||||
FILE |
|
*pStructFileOut |
|
= |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
80 ) |
; |
|
|
// |
Печать |
таблицы |
с |
|
заголовком |
\п", |
pHead |
) ; |
|
|
||||
fprintf( |
pStructFileOut, |
|
i++ |
"\п |
%s |
|
|
|||||||
tor( |
±nt |
1=0; l<size; |
|
) |
|
|
|
|
|
|
|
|||
{ |
fprintfC |
pStructFlleOutr |
|
"\n |
%-8s%-62s", |
|
|
|||||||
|
|
|
|
|||||||||||
|
|
|
pTable |
[ |
i |
].key, |
pTable |
[ i |
J.data |
) ; |
|
|||
}
//Закрытие файла вывода
|
CloseFile( |
pStructFlleOut, |
|
pFileOut, |
90 |
) ; |
|
||||
|
return; |
|
|
|
|
|
|
|
|
|
|
} |
|
|
|
|
|
|
|
|
|
|
|
// |
Последовательный |
поиск |
в |
|
таблице |
|
|
|
|||
void |
SequentlalSearch |
|
( |
|
|
в |
таблице |
|
|
||
|
// Ключ |
для поиска |
строки |
|
|
||||||
|
char |
Keyword |
[ |
], |
|
|
|
|
|
|
|
|
±nt |
&foundr |
) |
// |
1 |
- нашли |
|
строки |
|||
|
±пЬ |
&line |
|
// |
Индекс |
найденной |
|||||
{ |
±nt |
1, |
|
|
// |
Индекс |
анализируемой |
строки |
|||
|
|
|
|||||||||
|
|
EndTab; |
|
// |
1 |
- конец |
заполненной |
части |
|||
//та блицы
//Подготовка к поиску
found = О; EndTab = 0;
// |
Поиск |
|
|
|
1 = |
0; |
.'found |
&& /EndTab |
) |
while |
( |
|||
{ |
±£( |
Istrcmpi |
Keyword^ |
pTable [ 1 ] . key ) ) |
|
||||
Щ |
{ |
|
// |
Нашли |
|
|
found |
= 1; line |
= 1; |
}
else
298
if( i == size-1 |
// Шаг вперед |
по |
таблице |
) |
|
|
|
{ |
1/ |
|
|
EndTab = |
|
|
;
else
{
i + + /
}}
}
retuim;
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// |
Вывод |
результатов |
|
поиска |
в |
таблице |
в файл |
на |
магнитном |
|||||||||
// |
диске |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
void |
char |
PrintSearch( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
*pFileOutг// |
|
Указатель |
на |
файл |
вывода |
|
|
||||||||
|
char |
|
|
*pMode, |
|
// |
Указатель |
на |
режим |
открытия |
файла |
|||||||
|
±nt |
|
|
found, |
|
|
// |
1 |
- нашли |
в |
таблице |
|
|
|
||||
|
±iib |
|
|
line |
г |
|
// |
Индекс |
строки |
|
в |
|
таблице |
|
|
|||
|
// |
Ключевое |
слово |
для |
|
поиска |
|
|
|
|
|
|
|
|
|
|||
|
char |
|
|
Keyword[ |
] |
|
) |
|
|
|
|
|
|
|
|
|
|
|
{ |
// |
Открытие |
файла |
для |
|
записи |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
FILE |
|
*pStructFlleOut |
|
|
= |
OpenFile |
( |
pFileOut, |
pMode, |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
100 |
) |
; |
|
|
|
|
fprintf( |
pStructFlleOutr |
|
|
"\n |
Результаты |
|
|
поиска |
|
для" |
|
||||||
|
|
|
" |
ключевого |
слова: |
%s\n'\ |
KeyWord |
) |
; |
|
|
|||||||
|
±f( |
found |
|
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( |
fprintf( |
|
|
|
pStructFileOutr |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
"Индекс |
строки |
|
в таблице: |
|
%d. |
Найденная |
строка: |
|
\ л " , |
line |
) ; |
|||||||
|
|
fprintf( |
|
pStructFileOut, |
|
|
"%-8s%-62s |
|
|
\ л " , |
|
|
|
|||||
|
|
|
|
рТаЫе |
[ |
line |
J.key, |
рТаЫе |
|
[ |
line |
] .data |
) ; |
|||||
|
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
else |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
{ |
fprintf( |
|
pStructFileOut, |
|
|
"Строка |
с |
ключом |
\"%s\" |
в" |
|||||||
|
|
|
|
|
||||||||||||||
|
|
|
|
" |
таблице |
|
не |
найдена, |
\п", |
|
Keyword |
) ; |
|
|||||
}
//Закрытие файла вывода
|
CloseFile( |
pStructFileOutг |
pFileOut, |
110 |
) ; |
|
|
|
return/ |
|
|
|
|
|
|
} |
|
|
|
|
|
|
|
// |
Обход вершин |
дерева |
с целью |
формирования |
|
словаря |
для |
// |
бинарного |
(логарифмического) |
поиска, |
!!! |
Читаемые |
данные |
|
299