/*
Постановка задачи
Данные хранятся в файле на диске. Реализовать их обработку, как указано в задаче. Реализовать заданный алгоритм сортировки и поиска данных.
При выполнении этого задания необходимо:
1. Имя файла задается в командной строке. Если оно там не было задано, то после соответствующего запроса вводится пользователем.
2. Использовать динамическое выделение памяти (размер массива задается пользователем после соответствующего запроса). Освобождать память, выделенную под динамические переменные, ОБЯЗАТЕЛЬНО.
Условие задачи:
Есть матрица m * n, действительных чисел. Упорядочить ее столбики методом Quick Sort. Методами последовательного и бинарного поиска найти заданное число в указанном столбце. Данные вводятся из файла.
*/
/*
codeby.net
Autor: DarkKnight125 (Denis Goncharov)
*/
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <memory.h>
#include <time.h>
#include <string.h>
//Функция сортировки двумерного массив (по столбцам)
// Arr - указатель на массив, SizeM, SizeN - размерность массива
void qsort(int **Arr, int SizeM, int SizeN)
{
int i, j, k;
for (i = 0; i<SizeN; i++)
{
for (j = 0; j<SizeM; j++)
{
for (k = j+1; k < SizeM; k++)
{
if (Arr[j][i] > Arr[k][i])
{
int Temp = Arr[k][i];
Arr[k][i] = Arr[j][i];
Arr[j][i] = Temp;
}
}
}
}
}
//Функция линейного поиска в заданном столбце
// Arr - указатель на массив, SizeM, SizeN - размерность массива
// Col - заданный столбец для поиска
// Value - значение которое ищим
int SearchLine (int **Arr, int SizeM, int SizeN,int Col, int Value)
{
bool isSearch = false; //Результат поиска
int Result = -1; //Результат индекс элемента или -1 если элемент не найден
int Iteration = 0; //Кол-во итераций поиска
int i;
for (i = 0; i <SizeM; i++)
{
Iteration++; //Увеличим итерацию
if (Arr[i][Col] == Value)
{
isSearch = true;
Result = i;
break;
}
}
//Выведим информацию для статистики
printf("Линейный поиск элемента %i \n", Value);
if (isSearch)
printf("Элемент %i - найден. Его позиция(строка) %i\n", Value, Result);
else
printf("Элемент %i - НЕ найден.\n", Value);
printf("Итераций на поиск: %i\n", Iteration);
return Result;
}
//Функция Двоичного(бинарного поиска) поиска в заданном столбце
// Arr - указатель на массив, SizeM, SizeN - размерность массива
// Col - заданный столбец для поиска
// Value - значение которое ищим
int SearchBin (int **Arr, int SizeM, int SizeN,int Col, int Value)
{
int bFirst = 0; //Начальный индекс массива (отсортированного)
int bEnd = SizeM - 1; //Конечный индекс массива (отсортированного)
int bMiddle; //Переменная середины массива
int Result = -1; //Результат индекс элемента или -1 если элемент не найден
int Iteration = 0; //Кол-во итераций поиска
printf("Двоичный поиск элемента %i \n", Value);
if (Value < Arr[bFirst][Col] || Value > Arr[bEnd][Col])
{
printf ("Элемент лежит вне отсортированой колонки");
return Result;
}
while ( bFirst < bEnd) //Пока вычисляемые индексы Начала меньше выч. индекса Конца
{
bMiddle = (bFirst + bEnd) / 2; //Найдем индекс середины (целочисленное деление)
if (Value <= Arr[bMiddle][Col]) //Если элемент поиска <= значение массива при срединном индексе
bEnd = bMiddle; //Сместим тогда конец в середину, ведь наш элемент лежит от нач. до средины, или же в аккурат середины
else //Иначе лежит в пределеот (средина, конец]
bFirst = bMiddle + 1;
Iteration++;
}
if (Arr[bEnd][Col] == Value) //Если индекс конца указывает на эл. поиска
{
Result = bEnd;
}
//Выведим информацию для статистики
if (Result != -1)
printf("Элемент %i - найден. Его позиция(строка) %i\n", Value, Result);
else
printf("Элемент %i - НЕ найден.\n", Value);
printf("Итераций на поиск: %i\n", Iteration);
return Result;
}
//Главная функция программы (точка входа)
int main (int argc, char *argv[])
{
setlocale(LC_ALL,".1251"); //Подгрузим локаль
srand(time(NULL)); //Генератор случ. величины инициализация
int **Arr; //Наш массив m x n
int m,n; //Размерность массива
int i,j;
int selected = 0; //Выбор
int SearchValue; //Значение для поиска
int Col = 0; //Колонка в массиве с которой будем работать
FILE *File = NULL; //Файловый дескриптор
char filename[32]={0}; //Имя файла
//Если в командную строке есть имя файла
if (argv[1])
{
printf("В коммандной строке указан файл : %s",argv[1]);
strncpy(filename,argv[1],31);
}
else //Если в командной строке нет имени файла
{
printf("Введите имя файла : ");
scanf("%31s",filename);
printf("Прользователь указал имя файла : %s \n",filename);
printf("Выберите режим файла <0>- чтение, <1> - запись : ");
scanf("%i",&selected);
}
if (selected == 0)
{
printf("Режим чтения\n");
File = fopen(filename,"r+");
}
else
{
File = fopen(filename,"w");
printf("Режим записи\n");
}
if (!File)
{
printf("Ошибка открытия файла");
return 1;
}
if (selected !=0)
{
printf("Введите размерность [m,n] :");
scanf("%i,%i", &m, &n);
fprintf(File,"%i %i", m, n); //Введем в файл размерность массива
}
else
fscanf(File,"%i %i ",&m,&n);//Размерность массива
printf("Размерность массива %ix%i\n",m,n);
Arr = (int**) malloc(sizeof(int*) * m); //Выделим память под строки
for (int i = 0; i< m; i++)
{
Arr[i] = (int*) malloc(sizeof(int) * n); //Выделим память под столбцы
for (int j = 0; j < n; j++)
{
Arr[i][j] = rand()%100;
if (selected !=0)
{
fprintf(File," %i", Arr[i][j]); //Введем в файл размерность массива
}
else
fscanf(File," %i",&Arr[i][j]);//Размерность массива
printf("Arr[%i][%i] = %i\n", i, j, Arr[i][j]);
}
}
fclose(File);
//Ввод рабочей колонки
printf("Введите столбец в котором будем производить поиск (индекс нач. с 0) : ");
scanf("%i",&Col);
//Ввод элемента который будем искать
printf("Введите элемент для поиска : ");
scanf("%i",&SearchValue);
//Линейный поиск
SearchLine (Arr, m, n,Col, SearchValue);
//Сортировка массив по столбцам
qsort(Arr,m,n);
//Выведим массив после сортировки
for (int i = 0; i< m; i++)
{
for (int j = 0; j<n; j++)
printf("%4i",Arr[i][j]);
printf("\n");
}
//Бинарный поиск
SearchBin (Arr, m, n,Col, SearchValue);
system("pause");
}
