Информационных технологий имени

ТАШКЕНТСКИЙ УНИВЕРСИТЕТ
ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ИМЕНИ
МУХАММАДА АЛ-ХОРАЗМИЙ

Группа ДИФ 320-21

Задания – 2
по предмету: Структуры данных и алгоритмы
Выполнил: Юлдашев Ж.
Приняла: Азизова З.

Задание по практической работе 2
Напишите три программные реализации алгоритмов сортировки по представленным задачам. Продемонстрируйте работу программ. Сформируйте выводы по выполнению работы.
Задание 1: Дана структура (с 1 по 21). Считать данные структур с массива. Сортировать данные методом прямого включения. Вывести на экран показатели эффективности (количество сравнений и замен). Результат работы программы:
Задание 2: Дана структура (с 1 по 21). Считать данные структур с массива. Сортировать данные методом прямого выбора. Вывести на экран показатели эффективности (количество сравнений и замен).
Задание 3: Дана структура (с 1 по 21). Считать данные структур с массива. Сортировать данные методом прямого обмена (пузырьковая). Вывести на экран показатели эффективности (количество сравнений и замен).

#include

#include
#include
using namespace std;
template bool swapAbiturInfo(iter a, iter b, int c) {
switch (c) {
case 0: return (a->SurNameAndName[0] > b->SurNameAndName[0]) ? true : false; break;
case 1: return (a->year > b->year) ? true : false; break;
case 2: return (a->ball > b->ball) ? true : false; break;
case 3: return (a->status > b->status) ? true : false; break;
}
}
template pair BubbleSort(iter begin, iter end, int c) {
int i = 0, j = 0;
iter Begin = begin, End = --end;
while (1) {
int key = 0;
for (; Begin != End; Begin++, i++) {
if (swapAbiturInfo(Begin, Begin + 1, c)) {
swap(*(Begin + 1), *Begin);
key++; j++;
}
}
if (key == 0) break;
else Begin = begin;
}
return pair(i, j);
}
template pair InsertionSort(iter begin, iter end, int c) {
int i = 0, j = 0;
iter beg = begin, End = --end;
for (; beg != End; beg++, i++) {
iter t = begin;
if (swapAbiturInfo(beg, beg + 1, c)) {
swap(*(beg + 1), *beg);
j++;
for (; beg != begin; beg--, i++) {
if (swapAbiturInfo(beg - 1, beg, c)) {
swap(*(beg - 1), *beg);
j++;
}
else { beg = t; break; }
}
}
}
return pair(i, j);
}
template pair SelectionSort(iter begin, iter end, int c) {
int i = 0, j = 0;
iter End = --end;
for (; begin != End; begin++) {
iter min = begin;
for (iter beg = begin; beg != End + 1; beg++, i++)
if (swapAbiturInfo(min, beg, c)) min = beg;
swap(*min, *begin);
j++;
}
return pair(i, j);
}
enum statusAbitur {
Active = 0, Default = 1, Noactive = 2
};
struct Abiturient {
public:
string SurNameAndName; int year;
float ball; statusAbitur status;
Abiturient(string a, int b, float c, statusAbitur d = statusAbitur::Active) : SurNameAndName(a), year(b), ball(c), status(d) {}
void printinfo() {
string txt;
switch (status) {
case statusAbitur::Active: txt = "Active"; break;
case statusAbitur::Default: txt = "Default"; break;
case statusAbitur::Noactive: txt = "Noactive"; break;
}
printf("Абитуриент ФИ : %s\n Дата рождения : %d\n Балл : %3.1f\n статус : %s\n\n", SurNameAndName.c_str(), year, ball, txt.c_str());
}
};
int main() {
setlocale(LC_ALL, "");
int p;
cout << " Сортировать по каким атрибутам: ";
cin >> p;
vector NewStudents{
Abiturient("Karimov Salim", 2003, 123.4, statusAbitur::Default),
Abiturient("Akramov Bosid", 2003, 96.4),
Abiturient("Valijonov Akbar", 2002, 102.4),
Abiturient("Farhodov Shuxrat", 2001,146.4, statusAbitur::Noactive),
Abiturient("Muradov Xusan", 2003, 104.3)
};
vector press = NewStudents;
Abiturient* mas = new Abiturient[5]{
Abiturient("Karimov Salim", 2003, 123.4, statusAbitur::Default),
Abiturient("Akramov Bosid", 2003, 96.4),
Abiturient("Valijonov Akbar", 2002, 102.4),
Abiturient("Farhodov Shuxrat", 2001,146.4, statusAbitur::Noactive),
Abiturient("Muradov Xusan", 2003, 104.3)
};
pair res1 = InsertionSort(press.begin(), press.end(), p);
pair res2 = SelectionSort(NewStudents.begin(), NewStudents.end(), p);
pair res3 = BubbleSort(mas, mas + 5, p);
for (auto t : NewStudents) t.printinfo();

printf("InsertionSort %d %d \n", res1.first, res1.second);

printf("SelectionSort %d %d \n", res2.first, res2.second);
printf("BubbleSort %d %d \n", res3.first, res3.second);
}

5.1 Составьте хеш-таблицу, содержащую буквы и количество их вхождений во введенной строке (вводится Фамилия_Имя_студента(ки)). Вывести таблицу на экран. Осуществить поиск введенной буквы в хеш-таблице.

#include
#include
#include
#include
using namespace std;
class node {
public:
int index;
node* next;
};
class hesh {
public:
int key;
vector* listNodes;
hesh(int key) : key(key) {
listNodes = new vector;
for (int c = 0; c < key; c++) listNodes->push_back(new node);
}
void addValue(char t, int a) {
node* ptr = listNodes->at(tolower(t) - 'a');
while (ptr->index > -1) ptr = ptr->next;
ptr->index = a;
ptr->next = new node;
}
void search(char t) {
node* ptr = listNodes->at(tolower(t) - 'a');
while (ptr->index > -1) {
cout << ptr->index << " ";
ptr = ptr->next;
}
}
};
int main() {
ifstream file("c:/file.txt");
string text;
while (file.is_open()) {
if (getline(file, text)) {
cout << text << endl;
}
else break;
}
hesh* tab = new hesh(30);
for (int c = 0; c < text.length(); c++) tab->addValue(text[c], c);
cout << " Simvol = "; char t;
cin >> t;
node* ptr = tab->listNodes->at(tolower(t) - 'a');
while (ptr->index > -1) {
cout << ptr->index << " ";
ptr = ptr->next;
}
}