4. Контрольные вопросы

11. Что такое ключ (в контексте поисковых алгоритмов)?

12. Как работает последовательный поиск?

13. Объясните причину сокращения времени поиска при использовании усовершенствованных алгоритмов последовательного поиска (быстрого и в упорядоченной таблице).

14. Где применяется каждый из описанных видов поиска и почему?

15. Какие из описанных алгоритмов поиска являются статическими, а какие динамическими? Почему?

5. Варианты заданий

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

Таблица 3

Вариант	Алгоритм поиска
	S	Q	T
1	+	+
2	+	+
3	+		+
4	+		+
5	+	+
6	+	+
7	+		+
8	+		+
9	+	+
10	+	+
11	+		+
12	+		+
13	+	+
14	+	+
15	+		+
16	+		+
17	+	+
18	+	+
19	+		+
20	+		+
21	+	+
22	+	+
23	+		+
24	+		+

6. Содержание отчёта

1. Наименование работы

2. Цель работы

3. Краткие теоретические сведения

4. Вариант задания

5. Код программы

6. Пример работы программы

7. Анализ полученных результатов и выводы

8. Ответы на контрольные вопросы

9. Подпись исполнителя

Приложение

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

// Прототипы функций, реализующих методы поиска

void * alg_s(int);

void * alg_q(int);

void * alg_t(int);

// Максимальное количество записей в таблице

#define max_N 15

int N = max_N;

int i;

// Структура, описывающая единичную запись с ключом

typedef struct {

int k;

void *field;

} item;

// Объект, представляющий собой таблицу записей с ключами

item items[max_N+1];

void main()

{

// Объявление переменных и чтение таблицы из файла

FILE *in;

int k;

void *data;

char buf[259];

char s[3];

char flag=0;

if((in = fopen("input.txt","rt")) == NULL)

{

printf("Невозможно открыть файл\n");

return;

}

i=0;

while(fgets(buf,255,in) != NULL)

{

items[i].k = atoi(buf);

if(buf[strlen(buf)-1] == '\n')

buf[strlen(buf)-1] = '\0';

items[i].field = malloc(strlen(&buf[3]));

strcpy(items[i].field,&buf[3]);

i++;

}

N = i;

fclose(in);

// Конец чтения из файла

// Ввод ключа

printf("%s\n","Введите ключ:");

gets(s);

while((k = atoi(s)) < 0)

{

printf("%s\n","Ключ должен быть >0 и <32767");

printf("%s\n","Введите новый ключ:");

gets(s);

}

// Исполнение алгоритма S

data = alg_s(k);

// Вывод результатов

printf("Алгоритм S:\n");

if(data == NULL)

printf("Запись не найдена, i=%d\n",i+1);

else

printf("Запись: \"%s\", i=%d\n",data,i+1);

// Исполнение алгоритма Q

items[N].field = NULL; // фиктивная запись

data = alg_q(k);

// Вывод результатов

printf("Алгоритм Q:\n");

if(data == NULL)

printf("Запись не найдена, i=%d\n",i+1);

else

printf("Запись: \"%s\", i=%d\n",data,i+1);

// Исполнение алгоритма T

items[N].k = 32767; // Вставка Kn = ∞

items[N].field = NULL;

data = alg_t(k);

// Вывод результатов

printf("Алгоритм T:\n");

if(data == NULL)

printf("Запись не найдена, i=%d\n",i+1);

else

printf("Запись: \"%s\", i=%d\n",data,i+1);

// Освобождение памяти

for(i=0;i<N;i++)

free(items[i].field);

}

// Алгоритм S

void * alg_s(int key)

{

// Шаг 1. Начальная установка

i=0;

do

{

// Шаг 2. Сравнение

if(key == items[i].k)

return items[i].field;

// Шаг 3. Продвижение

i++;

}

// Шаг 4. Завершение

while(i<N);

return NULL;

}

// Алгоритм Q

void * alg_q(int key)

{

// Шаг 1. Начальная установка

i = 0;

items[N].k = k; // вставка Kn = K

// Шаг 2. Сравнение

while(!(key == items[i].k))

// Шаг 3. Продвижение

i++;

// Шаг 4. Завершение

if(i<N)

return items[i].field;

return NULL;

}

// Алгоритм T

void * alg_t(int key)

{

// Шаг 1. Начальная установка

i = 0;

// Шаг 2. Сравнение

while(!(key < items[i].k))

// Шаг 3. Продвижение

i++;

// Шаг 4. Завершение

if(key == items[i].k)

return items[i].field;

return NULL;

}