Study & Dev | Blog Archive | Структуры данных и алгоритмы. Практика. Сортировки и поиск элемента массива

Структуры данных и алгоритмы. Практика. Сортировки и поиск элемента массива

January 13, 2007

1. Задача поиска в массиве некоторого элемента. При решении данной задачи я решил немного отойти за границы традиционных объектов, с которыми мы работаем: числа и символы. Теперь мы будем исследовать файловую систему, и искать в ней файлы по определенному критерию. Прежде всего, посмотрите на далее приведенный пример кода, где находятся все файлы в текущем каталоге с расширением ”*.cpp” и выводится информация о них на экран:

```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
#include <io.h>
```
```
#include <time.h>
```
```
 
```

void print_info (struct _finddata_t *info_about_file);

```
 
```
```
void main (void){
```

    struct _finddata_t info_about_file;

```
     /* 
```

      структура содержащая внутри себя все сведения

      о найденном файле: его имя, размер, дату создания и прочее

```
     */
```

     // уникальное число которое будет использовано в дальнейшем для продолжения поиска

```
    long hFile;
```
```
    /*
```

       ищем первый файл по заданной маске. Если поиск был неудачен, то функция

      _findfirst возвращает значение -1, в этом случае мы выводим сообщение об

      ошибке и прекращаем поиск

```
    */
```

    if( (hFile = _findfirst( "*.cpp", &info_about_file )) == -1 )

       printf( "No *.cpp files in current directory!\n" );

```
    else
```
```
    {
```
```
      print_info (&info_about_file);
```
```
      /* 
```

       а теперь мы продолжим искать файлы дальше пока не переберем их всех

       для связи между функциями чтобы  _findnext знала по какой маске искать файлы

       используется ранее объявленное значение  hFile

```
      */
```
```
 
```

      // если следующий файл  был найден, то функция возвращает 0

      while( _findnext( hFile, &info_about_file ) == 0 ){

         // данная функция выполняет печать информации о очередном найденном файле

```
         print_info (&info_about_file);
```
```
      }
```
```
 
```

      // когда мы завершаем поиск то необходимо освободить системные ресурсы

```
      _findclose( hFile );
```
```
    }//if
```
```
}
```
```
 
```

void print_info (struct _finddata_t *info_about_file){

    // поле имени файла в виде обычного массива char*

    printf ("FileName: %s\n"  , info_about_file->name);

    // размер файла - целое число

    printf ("FileSize: %d\n", info_about_file->size);

```
 
```
```
    /*
```

    с датой хитрее: поле info_about_file->time_create имеет нам уже знакомый тип time_t

    (вспомнили работу с функцией time -  определение текущего времени)

    функция ctime выполняет преобразование числа хранящего количество секунд от сотворения мира

    (согласитесь что это не слишком удобно для вывода) в строку символов

```
    */
```

    printf ("FileDateOfCreation: %s\n", ctime(&info_about_file->time_create));

```
}
```
```
 
```
```
/*
```

 Результат запуска программы:

```
  FileName: 2.cpp
```
```
  FileSize: 1178
```

  FileDateOfCreation: Tue Jun 22 18:07:35 2004

```
 
```
```
  FileName: StdAfx.cpp
```
```
  FileSize: 288
```

  FileDateOfCreation: Tue Jun 22 17:38:33 2004

```
*/
```

Вам необходимо, после того как разберетесь с этим примером, найти все файлы с любыми расширениями в текущем каталоге или любом другом, где файлов будет побольше и поинтереснее, и поместить информацию о них в вектор (stl-библиотека) структур идентичных использованной в примере “struct _finddata_t”. Затем по запросу пользователя должна выполняться сортировка по:

имени файла,
расширению файла;
размеру файла;

На экран выводятся элементы данного вектора в нужном порядке. В качестве основы для алгоритма сортировки используйте алгоритм сортировки методом шелла. Организуйте несложный диалог с пользователем: например выведите на экран варианты меню:

Собрать информацию обо всех файлах в заданном каталоге:
Вывести отсортированными по имени
... по расширению
... по размеру
выход

2) Игра. Данное задание является примером использования алгоритма поиска элемента в массиве методом половинного деления. Программа должна загадывать некоторое число, а пользователь должен его угадать. Число находится в диапазоне от 1…10^6 (подумайте, как сгенерировать подобное случайное число). Пользователь вводит свой вариант числа, а машина ему сообщает: угадал или нет, и если нет, то в какой половине следует искать нужное значение.

3) Задание на эвристический метод поиска. Это задание развивает и применяет способ поиска, основанный на упорядочении элементов массива по относительным частотам их использования. Необходимо создать класс RangedArray который играет роль обертки для массива целых чисел (массив должен создаваться динамически). Предусмотреть методы которые бы позволяли бы добавлять в массив элементы. Перегрузите оператор:

```
int & operator [] (int indexOfElement))
```

И добавьте в состав данного класса метод для поиска элемента и его позиции “int getIndexOfElement(int Value)” (данный метод должен находить позицию элемента переданного как входной параметр и возвращать номер данного элемента). Для оптимизации поиска используется счетчик относительных частот использования каждого из элементов. Дисциплина внутреннего функционирования класса-контейнера RangedArray должна предусматривать способ переупорядочивания элементов например после выполнения 100 обращений к элементам. Для подобного переупорядочивания предусмотрите метод "Reorganize".

Для демонстрации и проверки корректности работы созданного нами на предыдущем шаге контейнера необходимо заполнить массив числами в отрезке от 0-100.

Далее необходимо выполнить 10, затем 100, затем 1000, ... 10^6 обращений к элементам. Запрашиваемые элементы должны быть в диапазоне от 0-100, но здесь внимание (мы моделируем работу приложения в реальных условиях) некоторые элементы должны быть более востребованы, чем остальные.

Здесь перед нами стоит задача написания генератора случайных чисел в отрезке от 0-100, но не равномерно распределенных (так работает стандартная функция rand()), а например, нормальное распределение. Входными параметрами для подобного распределения являются: среднее значение MO и дисперсия DI. Мы зададим MO = 50, а дисперсию DI =20. Для генерации случайных чисел нормально распределенных использую формулу: для i=1-12: (Сумма(Pi) – 6)*Disp – MO (Про нее я упоминал на теоретическом занятии);

4) При решении данного задания следует использовать сортировку слиянием:

a. Заданы два массива случайных чисел (количество элементов в каждом порядка 50,

диапазон случайных чисел = [-100..100], включая обе границы), при этом первый из этих массивов “A” упорядочен по возрастанию,

а второй - “B” - упорядочен по убыванию.

Вам необходимо сформировать третий массив “C” упорядоченный по убыванию.

b. Данное задание является развитием предыдущего: при выполнении операции слияния необходимо избавиться от дублирующихся элементов.

c. Необходимо выполнить сортировку массива заполненного неупорядоченными случайными числами от –1000 до 1000.

5) Данная задача посвящена поиску внутри некоторой строки S заданной подстроки. Так в строке S например S=”the boy goes to school”, надо найти S1=”boy goes”. Наша программа должна вернуть номер позиции “i=4”. Для поиска подстроки тоже есть способ улучшить скоростные показатели. В основе своей данный прием пробует все возможные точки, откуда может начаться в S подстрока S1, у нас это диапазон 0..(length(S) – length(S1) – 1). Поиск подстроки в строке обычной подстановкой к каждой позиции строки всей подстроки - метод неэффективный. Существует способ, когда выполняется предварительная оценка того, имеет ли смысл выполнять сравнение подстрок. Для этого вычисляется для подстроки S (k1..kn) некоторая числовая характеристика, а затем сравнивается с этой же характеристикой для подстроки S1. в качестве числовой характеристики можно использовать как простейший вариант сумму кодов символов образующих строку. Реализуйте данный алгоритм поиска подстроки в строке.

Categories: Структуры данных и алгоритмы

Study & DevО программировании и не только

Структуры данных и алгоритмы. Практика. Сортировки и поиск элемента массива

Поиск

Недавнее

Архив

Разделы