2. Поиск

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

При линейном поиске происходит сравнение каждого элемента массива с ключом поиска. Поскольку массив не упорядочен особым образом, вероятность нахождения требуемого значения в первом и в последнем элемен­тах массива одинакова. Таким образом, в среднем программа должна будет сравнить ключ поиска с половиной элементов массива.

Метод линейного поиска хорошо работает для небольших или несортиро­ванных массивов. Однако для больших массивов он неэффективен. В случае сортированного массива может быть использован высокоскоростной метод двоичного поиска.

При двоичном алгоритме поиска после каждого сравнения исключается по­ловина элементов массива, в котором проводится поиск. Алгоритм находит сред­ний элемент массива и сравнивает его с ключом поиска. Если они равны, ключ поиска считается найденным и возвращается индекс этого элемента. Если они не равны, задача упрощается до поиска в одной половине массива.

Если ключ поиска меньше среднего элемента массива, поиск производит­ся в первой половине массива, в противном случае поиск производится во вто­рой половине. Если ключ поиска в указанном подмассиве (части первоначального массива) не найден, алгоритм повторяется для четверти массива. Поиск продолжается до тех пор, пока ключ не окажется равен среднему элементу подмассива или пока подмассив не будет состоять из одного элемента, не рав­ного ключу (это означает, что ключ поиска не найден).

3. Практическая часть

Постановка задачи: разработать программу «Сортировки сотрудников фирмы по номеру паспорта», которая должна содержать структуру из трех полей ( ) и четыре функции пользователя:

– функция ввода информации;

– функция вывода информации на экран;

– сортировка;

– запись в файл.

Обязательное условие – это наличие меню, что позволит пользователю самому выбирать те действия, которые он хочет совершить над данными

Текст программы

#include <iostream>

#include <stdio.h>

using std::cin;

using std::cout;

using std::endl;

struct sotrfirm

{

int npasporta[5];

char fio[5][80];

int vozrast[5];

};

sotrfirm sSotr; //объевляем как глобальную переменную

//для простоты и спользования в процедурах

FILE *cfPtr ; //указатель на фыйл firma dat

void vvoddannih(void); // процедура ввода данных в структуру

void vivoddannih(void); // процедура вывода данных

void sort(void); // процедура сортировки

void zapisvfail(void) ; // процедура записи данных в файл

void help(void); // процедура вывода справки

main()

{

char key='h';

while (key!='x')

{

if (key=='v')

{

cout<<endl;

vvoddannih();

}

if (key=='w')

{

cout<<endl;

vivoddannih();

}

if (key=='h')

{

cout<<endl;

help();

}

if (key=='s')

{

cout<<endl;

sort();

}

if (key=='r')

{

cout<<endl;

zapisvfail();

}

cin>>key;

}

return 0;

}

//процедура ввода данных в структуру

void vvoddannih (void)

{

int i;

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

{

cout<<"================================================"<<endl;

cout<<"Vedite FIO dla "<<i+1<<"-go satrudnika "<<endl;

cin>>sSotr.fio[i];

}

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

{

cout<<"================================================"<<endl;

cout<<"Vedite VOZRAST dla "<<i+1<<"-go satrudnika"<<endl;

cin>>sSotr.vozrast[i];

}

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

{

cout<<"Vedite nomer pasorta dla "<<i+1<<"-go satrudnika "<<endl;

cin>>sSotr.npasporta[i];

}

}

// процедура вывода данных

void vivoddannih(void)

{

int i;

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

{

cout<<"================================================"<<endl;

cout<<"dannie po "<<i+1<<"-mu sotrudniku :"<<endl;

cout<<"Nomer Pasporta: "<<sSotr.npasporta[i]<<endl;

cout<<"FIO : "<<sSotr.fio[i]<<endl;

cout<<"Vozrast : "<<sSotr.vozrast[i]<<endl;

}

}

// сортировка

void sort(void)

{

int i,j,k,n1,n2,v1,v2;

int finish=0;

char fio1[80],fio2[80];

do

{

finish=0;

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

{

n1=sSotr.npasporta[i];

n2=sSotr.npasporta[i+1];

//////////////////////////////

for(j=0;j<80;j++)

{

fio1[j]=sSotr.fio[i][j];fio2[j]=sSotr.fio[i+1][j];

}

v1=sSotr.vozrast[i];

v2=sSotr.vozrast[i+1];

//////////////////////////////

if (n1>n2)

{

sSotr.npasporta[i]=n2;

sSotr.npasporta[i+1]=n1;

sSotr.vozrast[i]=v2;

sSotr.vozrast[i+1]=v1;

for(k=0;k<80;k++)

{

sSotr.fio[i][k]=fio2[k];

sSotr.fio[i+1][k]=fio1[k];

}

finish--;

}

else

{

finish++;

}

}

}

while (finish<4);

cout<<"Sortirovka zavershena"<<endl;

}

void zapisvfail(void)

{

int i,j;

int nP,vO;

char fio [80];

if ((cfPtr=fopen("Firma.dat","w"))==NULL)

cout<<"File could not be opened"<<endl;

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

{

nP=sSotr.npasporta[i];

vO=sSotr.vozrast[i];

for (j=0;j<80;j++)

{

fio[j]=sSotr.fio[i][j];

}

fprintf(cfPtr,"%d %s %d\n",vO,fio,nP);

}

fclose(cfPtr);

cout<<"Zapish dannih zavershena"<<endl;

}

void help(void)

{

cout<<"Dla vvoda dannih vvedite: v"<<endl;

cout<<"Dla vivoda dannih na ekran vvedite: w"<<endl;

cout<<"Dla sortirowki vvedite: s"<<endl;

cout<<"Dla zapisy dannix v fayl vvwdite: r"<<endl;

cout<<"Dla vizova spravji ssedite: h"<<endl;

cout<<"Dla vihoda vvwdite: x "<<endl;

}