VPF::[C++] Двоичный поиск в массиве - Форум программистов

nygger

Дата 2.11.2006, 00:02 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 1.11.2006

Репутация: нет
Всего: нет

Помогите!!! Необходимо разработать и отладить программу, в которой реализовать алгоритмы поиска в соответствии с заданием. Определить время сортировки, сделать выводы.
Для выполнения задания использовать два одномерных массива целых чисел А и В (количество элементов в массиве может быть изменено). Вычислить одномерный массив С, который содержит элементы в одном экземпляре (без повторений).
Примечание: Исходные массивы не менять и другие массивы не использовать. Массив А является исходным для поиска. Элементы массива В ищутся в массиве А. Результат помещается в массив С.

в прикреплённом файле вариант №9

Присоединённый файл ( Кол-во скачиваний: 8 )

lab4.html 23,03 Kb

Earnest

Дата 2.11.2006, 11:01 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 2
Всего: 183

Для домашних заданий, курсовых, существует "Центр Помощи"

Тема перенесена!

--------------------

...

Oleg_Ci

Дата 3.11.2006, 13:52 (ссылка)

(нет голосов)

Загрузка ...

Friend

Профиль
Группа: Участник
Сообщений: 485
Регистрация: 28.5.2006
Где: Новосиб.обл.

Репутация: 25
Всего: 30

чтобы из цикла ввода выйти введи строку 'end'
"Определить время сортировки" - сам сделай...

Код


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void search( const int * a, const int * b, int *& c, const int size_a, const int size_b, int & size_c );// создаём новый массив из двух
void resize( int *& a, const int size ); // изменение размера массива
void copy( int *& a, const int * b, int & size_a, const int size_b ); // копирование масcивов
void enter( int *& a, int & size, const char * c = "" ); // ввод чисел в массив
int cmp( const void * a, const void * b ); // для сравнения
int Bin_Search ( const int * a, const int low, const int high, const int key ); // бинарный поиск
void out( const int * a, const int size, const char * c = "\n" ); // выод содержимого массива
//_________ MAIN_________________
int main(int argc, char *argv[])
{ 
    int *a=NULL, *b=NULL, *c=NULL;
    int size_a=0, size_b=0, size_c=0;
    // "введите числа для первой матрицы A  ( для выхода введите строку - "end" )"
    enter( a, size_a, "Enter the numbers for a A tract of land:" );
    // "введите числа для второй матрицы  B (выход-"end")"
    enter( b, size_b, "Enter the numbers for a B tract of land:" );
    search( a, b, c, size_a, size_b, size_c );
    out( a, size_a, "content of the tract A of land:" ); // вывод содержимого массива A
    out( b, size_b, "content of the tract B of land:" );
    out( c, size_c, "content of the tract C of land:" );
    getchar();
    getchar();
    return 0;
}
//________ END MAIN ______________
void search( const int * a, const int * b, int *& c, const int size_a, const int size_b, int & size_c ){
    size_c = 0;
    resize( c, size_a + size_b );
    for( int i=0; i<size_b; i++ )
        if( Bin_Search( a, 0, size_a, b[i] )){
        c[size_c++] = b[i];
        while( b[i] == b[i+1] && i<=size_b ) i++;
        }
    resize( c, size_c );
}
void resize( int *& a, const int size ){
    if( a == NULL ){ // если массив отсутствует
        a=(int*)calloc( size, sizeof(int));
        return;
    }
    int * buf = (int*)realloc( a, size*sizeof(int)); // увеличение или уменьшение размера массива
    if( buf != NULL && a != buf ){
        free( a );
        a = buf;
    }
}
void copy( int *& a, const int * b, int & size_a, const int size_b ){
    if( size_a != size_b ) resize( a, size_b ); // если длинна массива а и b неодинаковы, делаем одинаковыми
    memcpy( a, b, size_b * sizeof(int)); // копируем данные
}
void enter( int *& a, int & size, const char * c ){
    puts( c );
    puts("Enter  \"end\"  to exit..."); // "Введите слово "end" для выхода из цикла ввода чисел"
    int i=0;
    char str[100] = {0};
    while( 1 ){
        if( !size || size <= i ){ // если чисел введено больше чем выделено памяти ...
            size += 10;
            resize( a, size ); // ... то выделяем больше памяти
        }
        scanf("%s", str );
        if( strcmp( str, "end" ) == 0 ) break; // если ввели "end" выходим из цикла
        else sscanf(str, "%d", a+i ); // вводим число в массив
        i++;
    }
    if ( i != size ){
        resize( a, i );
        size = i;
    }
    qsort( a, size, sizeof(int), cmp );
    puts("\n");
}
int cmp( const void * a, const void * b ){
    return *(int*) a - *(int*) b;
}
int Bin_Search ( const int * a, const int low, const int high, const int key ){
    if( low > high ) return 0;
    int temp = ( low + high ) / 2;
    if( a[temp] == key ) return temp;
    else if( a[temp] > key ) Bin_Search( a, low, temp-1, key );
    else Bin_Search( a, temp+1, high, key );
}
void out( const int * a, const int size, const char * c ){
    puts( c );
    for( int i=0; i<size; i++ )
        printf("%d ", a[i] );
    puts("\n");
}

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »