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

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

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

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

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

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

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

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

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

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

Студент

Бутаков В.В.

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

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

Группа

АС-09

Принял

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

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

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

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

Липецк 2010

1. Задание

Цель работы

Приобретение навыков реализации алгоритмов программного поиска в информационных массивах.

Задание кафедры

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

Вариант 2

Формат ключа: int, float[]

Вид поиска: по интервалу

Формат неключевых полей записи: char[]

Метод поиска: многоаспектный поиск с использованием инверсных массивов

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

При выполнении любого рода вычислений часто требуется решать задачу поиска, заключающуюся в решении вопроса о соответствии данных, содержащихся в некоторой записи информационного массива, установленному критерию выдачи. Запрос на поиск формализуется заданием аргумента поиска. Поиск записи с определенным признаком называется одноаспектным; если аргумент поиска представляет собой перечень признаков, поиск является многоаспектным.

Многоаспектный поиск с использованием инверсных массивов

Данные хранятся во внешней памяти. Среди записей выделяют поля, по которым может быть осуществлен запрос на многоаспектный поиск. Пусть имеется m таких полей. Создается m копий информационного массива, каждая из которых сортируется по одному из m ключевых полей и называется инверсным массивом. Для осуществления поиска по аргументу, состоящему из m ключей, в каждой из копий информационного массива проводится поиск по соответствующему ключевому полю. Над полученными m множествами записей проводится операция теоретико-множественного пересечения.

Поиск по интервалу

Аргумент содержит имена одного или нескольких признаков и пределы изменения значений этих признаков. В процессе поиска из информационного массива выделяется подмножество записей, значения полей из аргумента поиска которых попадают в интервал элемента поиска.

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

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

#include<stdio.h>

#include<windows.h>

#include<conio.h>

#include<math.h>

#include<string.h>

#define L 5

int N,K=0;

struct unit{int key1;float key2[L];char data[L];};

int comparison(unit a,unit b,int q)

{

if(q==1)

{

for(int i=0;i<L;i++)

{

if(a.key2[i]>b.key2[i])return 1;

else if(a.key2[i]<b.key2[i])return -1;

}

return 0;

}

else if(!q)

{

if(a.key1<b.key1)return -1;

else if(a.key1>b.key1)return 1;

else return 0;

}

else

{

for(int i=0;i<L;i++)

{

if(a.data[i]>b.data[i])return 1;

else if(a.data[i]<b.data[i])return -1;

}

return 0;

}

}

unit* shell(unit *items,int q)

{

register int i, j, gap;

unit x;

gap=(int)(N/2);

while(gap>0)

{

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

{

x=items[i];

for(j=i-gap;(comparison(x,items[j],q)==-1)&&(j>=0);j=j-gap)

{

items[j+gap]=items[j];

}

items[j+gap]=x;

}

gap=(int)(gap/2);

}

return items;

}

unit* search(unit*I)

{

int a1,a2,N1=0,N2=0;

unit b1,b2;

unit* A=new unit[N];

unit* B=new unit[N];

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

{

A[i]=I[i];

B[i]=I[i];

}

A=shell(A,0);

B=shell(B,1);

printf("Input bottom border key(int):\t");

scanf("%d",&a1);

printf("Input top border key(int):\t");

scanf("%d",&a2);

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

{

if(A[i].key1>a2)break;

if(A[i].key1>=a1)A[N1++]=A[i];

}

A=(unit*)realloc(A,sizeof(unit)*(N1));

for(int i=0;i<L;i++)

{

printf("Input %d elemet bottom border key(float):\t",i+1);

scanf("%f",&b1.key2[i]);

}

for(int i=0;i<L;i++)

{

printf("Input %d element top border key(float):\t",i+1);

scanf("%f",&b2.key2[i]);

}

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

{

if (comparison(B[i],b2,1)==1)break;

if(!(comparison(B[i],b1,1)==-1))B[N2++]=B[i];

}

B=(unit*)realloc(B,sizeof(unit)*(N2));

for(int i=0;i<N1;i++)

{

for(int j=0;j<N2;j++)

{

if((A[i].key1==B[j].key1)&&!comparison(A[i],B[j],1)&&!comparison(A[i],B[j],2))A[K++]=A[i];

}

}

A=(unit*)realloc(A,sizeof(unit)*(K));

return A;

}

void main()

{

SYSTEMTIME tim;

GetSystemTime(&tim);

srand(tim.wMilliseconds);

printf("Input count elements:\t");

scanf("%d",&N);

unit* I=new unit[N];

unit* O;

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

{

I[i].key1=rand();

for(int j=0;j<L;j++)I[i].key2[j]=rand()/100.;

for(int j=0;j<L;j++)I[i].data[j]=(char)(rand()%220+32);

}

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

{

printf("%d\t",I[i].key1);

for(int j=0;j<L;j++)printf("%.3f\t",I[i].key2[j]);

printf("\t");

for(int j=0;j<L;j++)printf("%c",I[i].data[j]);

printf("\n");

}

O=search(I);

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

for(int i=0;i<K;i++)

{

printf("%d\t",O[i].key1);

for(int j=0;j<L;j++)printf("%.3f\t",O[i].key2[j]);

printf("\t");

for(int j=0;j<L;j++)printf("%c",O[i].data[j]);

printf("\n");

}

getch();

}

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