Лабораторная работа №2 По курсу «Структуры и алгоритмы обработки данных» - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Программа дисциплины «Алгоритмы и структуры данных» 3 260.07kb.
Курсовая работа "Структуры и алгоритмы обработки данных" вариант... 2 301.58kb.
Учебно-методический комплекс по дисциплине "структуры и алгоритмы... 1 266.6kb.
Вопросы экзамена по курсу базы данных 1 516.36kb.
Контрольная работа содержит четыре варианта для выполнения математической... 1 38.07kb.
Программа элективного курса по информатике для учащихся 9 класса... 1 228.24kb.
Лабораторная работа №9 структура программы. Скалярные типы данных. 4 863.77kb.
Лабораторная работа №1 «Длинная арифметика» 1 80.64kb.
Лабораторная работа №6 по курсу «Программное обеспечение цифрового... 1 19.49kb.
Лабораторная работа по теме: «Комбинированный тип данных. Записи. 1 33.73kb.
Лабораторная работа 5 ms excel. Обработка и анализ данных 1 291.3kb.
Задание к практической работе №5 «Блоковое помехоустойчивое кодирование»... 1 34.44kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

Лабораторная работа №2 По курсу «Структуры и алгоритмы обработки данных» - страница №1/1

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОУ ВПО
«НИЖНЕВАРТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

ЛАБОРАТОРНАЯ РАБОТА №2

По курсу


«Структуры и алгоритмы обработки данных»
Факультет Информатики и Вычислительной Техники
3 семестр
вариант № 4

Выполнил:

студент гр. 22, дневное отделение

Королёв В.О.

Проверил:

___________________Т.Б. Казиахметов

Нижневартовск, 2013

Записи. Реализация стека, очереди на статических структурах
Задание№1:


  1. Сортировать файл структуры: Фамилия, дата_рождения, адрес обменной сортировкой, сортировкой вставками по полю Фамилия. Оценить реальное время на сортировку каждым из методов на текущем компьютере. Количество элементов файла не менее 10000.

Код программы:


#include

#include

#include

#include

#include

#include

struct baza

{char fam[64];

char date[16];

char add[64];

};

struct fams



{

char s[64];

};
struct ads

{

char s[64];



};

int main()

{

setlocale(0,"");



FILE *f;

int n=10000,i=0;

baza m[n];

fams fa[5000]; ads ad[1000];

char *s=new char;

//s=(char*)malloc(sizeof(char));

f=fopen("Surnames.txt","rt");

int res=fread(s, sizeof(char),1150,f);

char *ptr;

ptr = strtok(s,"," );

while (ptr!=NULL)

{

strcpy(fa[i].s, ptr);



//printf("\n%d = %s", i, fa[i].s);

ptr = strtok(NULL, ",");

i++;

}

int nof=i-1;



fclose(f);
f=fopen("Adresses.txt","rt");

delete(s);

i=0; printf("\n");

res=fread(s, sizeof(char),1100,f);

ptr = strtok(s,"," );

while (ptr!=NULL)

{

strcpy(ad[i].s,ptr);



//printf("\n%d = %s", i, ad[i].s);

ptr = strtok(NULL, ",");

i++;

}

int noa=i-1;



free(s); fclose(f);
srand (time (NULL));

int r1,r2,r3; char *str=new char, *str1=new char;

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

{

r1=rand()%nof;



r2=rand()%noa;

r3=(rand()%31)+1;

itoa(r3,str1,10);

strcpy(str,str1); strcat(str,"."); free(str1);

r3=(rand()%12)+1;

itoa(r3,str1,10);

strcat(str,str1); strcat(str,"."); free(str1);

r3=(rand()%20)+1980;

itoa(r3,str1,10);

strcat(str,str1); free (str1);

strcpy(m[i].date, str); free(str);

strcpy(m[i].fam,fa[r1].s);

strcpy(m[i].add,ad[r2].s);

//printf("№%d\n\tФамилия: %s\n\tАдрес: ул. %s\n\tДата рождения: %s\n", i, m[i].fam, m[i].add, m[i].date);

}

int key;


printf("Метод сортировки:\n\n1-Обменная\n2-Вставками\n");

scanf("%d",&key);

switch(key){

case 1:


{

float fTimeStart = clock()/(float)CLOCKS_PER_SEC;

int flag, k; baza tmp;

for (k=n;k>=0;k--)

{

flag=0;


for(i=0;i

{

if (stricmp(m[i].fam,m[i+1].fam)>0)



{

//printf("\nМеняю %s на %s", m[i].fam,m[i+1].fam);

tmp=m[i];

m[i]=m[i+1];

m[i+1]=tmp;

flag=1;


}

}

if (flag==0) break;



}

float fTimeStop = clock()/(float)CLOCKS_PER_SEC;

printf("Длительность процесса %f секунд\n", fTimeStop-fTimeStart);

}; break;

case 2:

{

float fTimeStart = clock()/(float)CLOCKS_PER_SEC;



baza tmp; int j;

/*i=1;


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

{

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



{

if (stricmp(m[j].fam,m[i].fam)>0)

{

//printf("m[%d] (%s) и m[%d] (%s): меняю...\n",j,m[j].fam,i,m[i].fam);



//Sleep(1000);

tmp=m[i];

m[i]=m[j];

m[j]=tmp;

} //else printf("m[%d] (%s) и m[%d] (%s): норм\n",j,m[j].fam,i,m[i].fam);

}

}*/



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

{

tmp=m[i];



j=i-1;

while ((j>0)&&(stricmp(m[j].fam,tmp.fam)>0))

{

m[j+1]=m[j];



j=j-1;

}

m[j+1]=tmp;



}

float fTimeStop = clock()/(float)CLOCKS_PER_SEC;

printf("Длительность процесса %f секунд\n", fTimeStop-fTimeStart);

}; break;

}

//printf("Отсортировано\n"); getch();



//for (i=0;i<=n;i++) printf("№%d\n\tФамилия: %s\n\tАдрес: ул. %s\n\tДата рождения: %s\n", i, m[i].fam, m[i].add, m[i].date);

return 0;

}


  1. Обменная сортировка



e:\документы\алгоритмы и системы\лаб 2\1\1.jpg


  1. Сортировка вставками

e:\документы\алгоритмы и системы\лаб 2\1\2.jpg

Задание№2:
Для сортированного массива Х(1000) вещественных чисел реализовать методы последовательного и бинарного поиска. Определить количество шагов необходимых для поиска введенного с клавиатуры элементов первым и вторым методом.
Код программы:
#include

#include

#include

#include

#include
int main()

{

setlocale(0,"");



int i,n=100,key,imem;

float x[n],a;

char ch[2]="y";

srand(time(NULL));

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

x[i]=rand()%1000;


int flag, k; float tmp;

for (k=n;k>=0;k--)

{

flag=0;


for(i=0;i

{

if (x[i]>x[i+1])



{

//printf("\nМеняю %s на %s", m[i].fam,m[i+1].fam);

tmp=x[i];

x[i]=x[i+1];

x[i+1]=tmp;

flag=1;


}

}

if (flag==0) break;



}

for (i=0;i<=n;i++) printf("%d: %f\n",i,x[i]);

while (stricmp(ch,"n")!=0)

{

printf("Введите искомое значение\n");



scanf("%f",&a);

//system ("cls");

printf("Выберите метод поиска\n\n1-Последовательный\n2-Бинарный\n");

scanf("%d",&key);

switch(key)

{

case 1:



{

int flag=0;

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

{

if (x[i]==a)



{

imem=i;


printf("%d: %f\n",i,x[i]);

flag=1;


}

}

if ((i==n+1)&&(flag==0)) printf("Элемент не найден\n");


}; break;

case 2:


{ imem=0;

int bord1=-1,bord2=n+1,mid,mid1,mid2;

while (bord1

{

mid=bord1+(bord2-bord1)/2;



if (x[mid]>a) bord2=mid;

if (x[mid]

//printf("Низ - %d, верх - %d, середина - %d[%.2f]\n", bord1, bord2, mid, x[mid]);

imem++;


if (x[mid]==a) break;

//Sleep(1000);

}

if (x[mid]==a)



{

mid1=mid2=mid;

while (x[mid1-1]==a) mid1--;

while (x[mid2+1]==a) mid2++;

if (mid1<0) mid1=0;

if (mid2>n) mid2=n;

for (i=mid1;i<=mid2;i++) printf("%d: %f\n",i,x[i]);

}

if (x[mid]!=a) printf("Элемент не найден\n");



} break;

}

printf("Количество шагов: %d\n",imem);



printf("Повторить? (y/n)\n");

scanf("%s",&ch);

}

//for (i=0;i<=n;i++) printf("%d: %f\n",i,x[i]);


return 0; getch();

}

Скриншот:


e:\документы\алгоритмы и системы\лаб 2\2\1.jpg
Задание№3:
Реализовать методы последовательного и бинарного поиска для массива записей следующей структуры: Фамилия, дата_рождения, адрес. Методы реализовать для поля Фамилия.
Код программы:
#include

#include

#include

#include

#include

#include

struct baza

{char fam[64];

char date[16];

char add[64];

};

struct fams



{

char s[64];

};
struct ads

{

char s[64];



};

int main()

{

setlocale(0,"");



FILE *f;

int n=30,i=0,imem;

baza m[n];

fams fa[5000]; ads ad[1000];

char *s=new char;

//s=(char*)malloc(sizeof(char));

f=fopen("Surnames.txt","rt");

int res=fread(s, sizeof(char),1150,f);

char *ptr;

ptr = strtok(s,"," );

while (ptr!=NULL)

{

strcpy(fa[i].s, ptr);



//printf("\n%d = %s", i, fa[i].s);

ptr = strtok(NULL, ",");

i++;

}

int nof=i-1;



fclose(f);
f=fopen("Adresses.txt","rt");

delete(s);

i=0; printf("\n");

res=fread(s, sizeof(char),1100,f);

ptr = strtok(s,"," );

while (ptr!=NULL)

{

strcpy(ad[i].s,ptr);



//printf("\n%d = %s", i, ad[i].s);

ptr = strtok(NULL, ",");

i++;

}

int noa=i-1;



free(s); fclose(f);
srand (time (NULL));

int r1,r2,r3; char *str=new char, *str1=new char;

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

{

r1=rand()%nof;



r2=rand()%noa;

r3=(rand()%31)+1;

itoa(r3,str1,10);

strcpy(str,str1); strcat(str,"."); free(str1);

r3=(rand()%12)+1;

itoa(r3,str1,10);

strcat(str,str1); strcat(str,"."); free(str1);

r3=(rand()%20)+1980;

itoa(r3,str1,10);

strcat(str,str1); free (str1);

strcpy(m[i].date, str); free(str);

strcpy(m[i].fam,fa[r1].s);

strcpy(m[i].add,ad[r2].s);

}
/////////////////////////Сортировка


int flag, k; baza tmp;

for (k=n;k>=0;k--)

{

flag=0;


for(i=0;i

{

if (stricmp(m[i].fam,m[i+1].fam)>0)



{

//printf("\nМеняю %s на %s", m[i].fam,m[i+1].fam);

tmp=m[i];

m[i]=m[i+1];

m[i+1]=tmp;

flag=1;


}

}

if (flag==0) break;



}
/////////////////////////Поиск

char ch[2]="y";

char a[32];

int key;


system ("cls");

for (i=0;i<=n;i++) printf("№%d\n\tФамилия: %s\n\tАдрес: ул. %s\n\tДата рождения: %s\n", i, m[i].fam, m[i].add, m[i].date);

while (stricmp(ch,"n")!=0)

{

printf("\nВведите искомое значение\n");



scanf("%s",&a);

//system ("cls");

printf("Выберите метод поиска\n\n1-Последовательный\n2-Бинарный\n");

scanf("%d",&key);

switch(key)

{

case 1:



{

int flag=0;

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

{

if (stricmp(m[i].fam,a)==0)



{

imem=i;


printf("№%d\n\tФамилия: %s\n\tАдрес: ул. %s\n\tДата рождения: %s\n", i, m[i].fam, m[i].add, m[i].date);

flag=1;


}

}

if ((i==n+1)&&(flag==0)) printf("Элемент не найден\n");


}; break;

case 2:


{

imem=0;


int bord1=-1,bord2=n+1,mid,mid1,mid2;

while (bord1

{

mid=bord1+(bord2-bord1)/2;



if (stricmp(m[mid].fam,a)>0) bord2=mid;

if (stricmp(m[mid].fam,a)<0) bord1=mid;

//printf("Низ - %d, верх - %d, середина - %d[%s]\n", bord1, bord2, mid, m[mid].fam);

imem++;


if (stricmp(m[mid].fam,a)==0) break;

//Sleep(1000);

}

if (stricmp(m[mid].fam,a)==0)



{

mid1=mid2=mid;

while (stricmp(m[mid1-1].fam,a)==0) mid1--;

while (stricmp(m[mid2+1].fam,a)==0) mid2++;

if (mid1<0) mid1=0;

if (mid2>n) mid2=n;

for (i=mid1;i<=mid2;i++)

printf("№%d\n\tФамилия: %s\n\tАдрес: ул. %s\n\tДата рождения: %s\n", i, m[i].fam, m[i].add, m[i].date);

}

if (stricmp(m[mid].fam,a)!=0) printf("Элемент не найден\n");



} break;

}

printf("Количество шагов: %d\n",imem);



printf("Повторить? (y/n)\n");

scanf("%s",&ch);

}

return 0; getch();



}

Скриншот:


e:\документы\алгоритмы и системы\лаб 2\3\1.jpg


izumzum.ru