Задача: Файловый ввод/вывод, последовательный и бинарынй поиск в масси

[Again]

Постановка задачи
Данные хранятся в файле на диске. Реализовать их обработку, как указано в задаче. Реализовать заданный алгоритм сортировки и поиска данных.

При выполнении этого задания необходимо:
1. Имя файла задается в командной строке. Если оно там не было задано, то после соответствующего запроса вводится пользователем.
2. Использовать динамическое выделение памяти (размер массива задается пользователем после соответствующего запроса). Освобождать память, выделенную под динамические переменные, ОБЯЗАТЕЛЬНО.

Условие задачи:
Есть матрица m * n, действительных чисел. Упорядочить ее столбики методом Quick Sort. Методами последовательного и бинарного поиска найти заданное число в указанном столбце. Данные вводятся из файла.

 

[DarkKnight]

Данные хранятся в файле на диске.

А где сам файл??? (Запостите пожалуйтса)

 

[Again]

А где сам файл??? (Запостите пожалуйтса)

Где сам файл это не важно. Тут имеется ввиду что нужно прописать путь к файлу в программе(это как я понимаю)...

 

[DarkKnight]

Данные хранятся в файле на диске. Реализовать их обработку, как указано в задаче.

Где сам файл это не важно. Тут имеется ввиду что нужно прописать путь к файлу в программе(это как я понимаю)...

"Где сам файл" - это я имел ввиду, почему вы его не запостили...

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

 

[DarkKnight]

Начал вашу задачу писать, у вас тут не большая не состыковка в условии...

Упорядочить ее столбики методом Quick Sort.

Написанно столбикИ, но qsort'ом нельзя упорядочить, как не крути, в двумерном массиве (массив указателей) сразу по нескольким столбцам одновремено.. Этого вам просто не даст сделать сама память....
Попробую обяснить понятнее...
Двумерный массив:
int **Arr, представляет собой указатель на массив указателей тоесть:
Arr указывает на
int* Arr[0], int*Arr[1] ... до m
Видите это единое целое все, цепочка в памяти..
В свою очередь каждый указатель Arr указывает на массив элементов (память выделеную под некое кол-во int)
int Arr[0][0], int Arr[0][1] ... n

А теперь смотри что у нас происходит при использование qsort как сортировка столбца
Мы меняем массив указателей, переставля указатели таким образом, что бы соблюдалось увеличение Arr[0][0], Arr[1][0], Arr[2][0]... и тд.
получая при этом например что Arr указывает уже например
int* Arr[1], int Arr[3], int Arr[0]

Блин, не могу нужные слова найти что бы объяснить... Попробую так

1 18 3 10
5 17 4 8
2 5 6 1

Если мы отсортируем по столбцу 2, то получим
2 5 6 1
5 17 4 8
1 18 3 10
А если затем попытаемся отсортировать столбец 3, то выдет уже
1 18 3 10
5 17 4 8
2 5 6 1
Видите, вернулись к исходному...

Так же будет работать и qsort, т.к. работает он с памятью....

Вот если бы отсортировать нужно было по-строчно, то не было бы проблем работали бы с указателем обячным Arr и все.... Сортируй не хочу... А тут целых 2 связанных между собой указателя....

Да и сама функция qsorta иметь будет не очень кошерный вид ;-)
вот примерно так....

int gCol = 0; //Глобальная переменная сдвиг на нужный столбец, по которому будем сортировать
int Compare(const void* a, const void* b)
{
//тут gCol - приращение (глобальная переменная)
return *(*(int**)a+gCol) - *(*(int**)b+gCol);

}

А сам вызов будет такой:

qsort((void*)Arr,m,sizeof(int*),Compare);

Добавлено: Так что уточните задание!
Мое мнение там должно звучать так :

Упорядочить заданный столбец методом Quick Sort. Методами последовательного и бинарного поиска найти заданное число в указанном столбце.

Добавлено: Пока что вот...

/*
Постановка задачи
Данные хранятся в файле на диске. Реализовать их обработку, как указано в задаче. Реализовать заданный алгоритм сортировки и поиска данных.
При выполнении этого задания необходимо:
1. Имя файла задается в командной строке. Если оно там не было задано, то после соответствующего запроса вводится пользователем.
2. Использовать динамическое выделение памяти (размер массива задается пользователем после соответствующего запроса). Освобождать память, выделенную под динамические переменные, ОБЯЗАТЕЛЬНО.
Условие задачи:
Есть матрица m * n, действительных чисел. Упорядочить ее столбики методом Quick Sort. Методами последовательного и бинарного поиска найти заданное число в указанном столбце. Данные вводятся из файла. 
*/
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <memory.h>
#include <time.h>
#include <string.h>

int gCol = 0;
int Compare(const void* a, const void* b)
{
//тут gCol - приращение (глобальная переменная)
return *(*(int**)a+gCol) - *(*(int**)b+gCol);

}
//Главная функция программы (точка входа)
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; //Выбор

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);

//Быстрая сортировка по второму столбцу
gCol = 1;
qsort((void*)Arr,m,sizeof(int*),Compare);


//Выведим массив после сортировки
for (int i = 0; i< m; i++)
{
for (int j = 0; j<n; j++)
printf("%i ",Arr[i][j]);
printf("\n");
}

//Продолжение следует....

system("pause");
}

 

[DarkKnight]

 /*
Постановка задачи
Данные хранятся в файле на диске. Реализовать их обработку, как указано в задаче. Реализовать заданный алгоритм сортировки и поиска данных.
При выполнении этого задания необходимо:
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");
}