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

Тема в разделе "C/C++/C#", создана пользователем Again, 11 дек 2010.

  1. Again

    Again Гость

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

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

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

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    А где сам файл??? (Запостите пожалуйтса)
     
  3. Again

    Again Гость

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

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    "Где сам файл" - это я имел ввиду, почему вы его не запостили...

    Вот недавно писал про поиск... http://codeby.net/ipb.html?s=&sh...st&p=194337
    А так если хотите получить готовую реализацию, то запостите пожалуйста входной файл
     
  5. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Начал вашу задачу писать, у вас тут не большая не состыковка в условии...
    Написанно столбикИ, но 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]

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

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

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

    }
    А сам вызов будет такой:
    Код (C++):
    qsort((void*)Arr,m,sizeof(int*),Compare);


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

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

    DarkKnight Well-Known Member
    C\C++ Team

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

    Вложения:

    • 124.txt
      Размер файла:
      108 байт
      Просмотров:
      10
    • binlinesort.jpg
      binlinesort.jpg
      Размер файла:
      121,2 КБ
      Просмотров:
      20
Загрузка...
Похожие Темы - Задача Файловый ввод
  1. Янчик
    Ответов:
    0
    Просмотров:
    486
  2. TrishaRay
    Ответов:
    1
    Просмотров:
    782
  3. elzim
    Ответов:
    0
    Просмотров:
    931
  4. ShaoKahn
    Ответов:
    1
    Просмотров:
    1.125
  5. eremin-sanek
    Ответов:
    3
    Просмотров:
    1.107

Поделиться этой страницей