Лабораторная работа №2 Вариант 17

2

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ

Лабораторная работа №2

по дисциплине

«Технология программирования»

на тему:

«Программирование алгоритмов ускоренного поиска информации»

Студент

Понарьин С.Н.

^подпись, дата

^фамилия, инициалы

Группа

АС-09

Принял

Домашнев П.А.

^ученая степень, звание

^подпись, дата

^фамилия, инициалы

Липецк 2010

1. 1. Задание:

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

№ п/п	Формат ключа	Вид поиска: 1 - по совпадению 2 – по интервалу 3 – по выражению	Формат неключевых полей записи	Метод поиска
17	char[]	1	float	2.г

1. Поиск по двоичному дереву (2.г)

Осуществляется в соответствии с принципами, по которым построено дерево поиска (см. п. 1.1.1). Первое обращение производится в корень. Если текущий элемент (из узла дерева, в начале – из корня) меньше аргумента, следующим будет рассматриваться правое поддерево; если текущий элемент больше аргумента, следующим будет рассматриваться левое поддерево; если при попытке осуществить переход по левой или правой обнаруживается, что ссылка отсутствует, результат поиска является отрицательным. Наименьшее число сравнений, требующееся при поиске в двоичном сбалансированном дереве, log₂N.

4. 2. Блок-схема программы

5. 3. Листинг программы

#include <conio.h>

#include <stdio.h>

#include <locale.h>

#include <stdlib.h>

#include <string.h>

typedef struct baza

{

char word[15];

float value;

};

typedef struct tree

{

baza w;

struct tree *left;

struct tree *right;

};

tree *Addtree(tree *root, baza new_el)

{

if (root==NULL)

{

root=(tree*)malloc(sizeof(tree));

root->left=root->right=NULL;

root->w=new_el;

return root;

}

if(strcmp(root->w.word,new_el.word)<0)

root->right=Addtree(root->right,new_el);

if(strcmp(root->w.word,new_el.word)>0)

root->left=Addtree(root->left,new_el);

return root;

}

int Search(tree *root, char *key)

{

if(root==NULL)

{

printf("\n\n----------------------------------------");

printf("\nПоиск не дал результатов");

return 0;

}

if(strcmp(root->w.word,key)<0)

Search(root->right,key);

if(strcmp(root->w.word,key)>0)

Search(root->left,key);

if(strcmp(root->w.word,key)==0)

{

printf("\n\n----------------------------------------");

printf("\nРезультат поиска:\n\n%s ",root->w.word);

printf("%f",root->w.value);

}

}

void main()

{

setlocale(LC_ALL,"Rus");

int n,i;

printf("Введите количество данных: ");

scanf("%d",&n);

char key[15];

baza *masstruct;

tree *root;

root=NULL;

masstruct=(baza*)malloc(sizeof(baza)*n);

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

{

printf("\nВведите слово %d: ",i+1);

scanf("%s",masstruct[i].word);

printf("Число %d: ",i+1);

scanf("%f",&masstruct[i].value);

root=Addtree(root,masstruct[i]);

}

printf("\nВведите элемент поиска: ");

scanf("%s",key);

Search(root,key);

free(masstruct);

getch();

}

6. 4. Контрольный пример