Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Программирование на C / C++

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 5.423 RSS
←   Март 2010   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://prog.rusfaq.ru/C
Открыта: 14-03-2002

Автор
Калашников О.А.

Статистика

5.423 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Программирование на C / C++


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный хостинг на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

Гаряка Асмик
Статус: Специалист
Рейтинг: 2959
∙ повысить рейтинг » 		lamed
Статус: Практикант
Рейтинг: 2202
∙ повысить рейтинг » 		Boriss
Статус: Академик
Рейтинг: 1892
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И ПО / Программирование / C/C++

Номер выпуска:1505
Дата выхода:29.03.2010, 09:30
Администратор рассылки:Verena, Профессионал
Подписчиков / экспертов:641 / 195
Вопросов / ответов:1 / 1
IRC-канал по теме:#C

Вопрос № 177430: Задача (тема: Указатели и ссылки) В отсортированный массив чисел ввести новые числа, разместив их в соответствии с упорядоченностью массива. (Не использовать алгоритм, по которому число добавляется в конец массива, потом массив сортируется!) <...

Вопрос № 177430:

Задача (тема: Указатели и ссылки)
В отсортированный массив чисел ввести новые числа, разместив их в соответствии с упорядоченностью массива. (Не использовать алгоритм, по которому число добавляется в конец массива, потом массив сортируется!)

Во вложении код моей программы, которая сортирует массив в порядке спадания элементов. Помогите дописать программу, а именно ввод новых чисел и размещение их в соответствии с упорядоченностью массива.
Спасибо!

Отправлен: 24.03.2010, 08:16
Вопрос задал: Lesija, Х Заблокирован
Всего ответов: 1
Страница вопроса »

Отвечает Micren, Профессионал :
Здравствуйте, Lesija.
Программа. С++. Компилировал GCC.

Дело в том, что в стандартный массив С++ невозможно вставить элемент не потеряв при этом другой т. к. массивы С++ имеют фиксированный размер. Если необходимо другое поведение то можно использовать контейнерные классы или динамическое размещение элементов массива.

Код:
#include <iostream>
#include <iomanip>
#include <locale>
#include <algorithm>
#include <functional>
#include <cstdlib>

using namespace std;

const size_t COUNT=20;      //  Количество элементов массива
const size_t INS_COUNT=3;   //  Количество вставляемых элементов

typedef int dataType;       //  Тип данных для массива

//  Выводит массив н
 а stdout
template<class Ty,size_t Dim>
void printArray(const char* const msg,Ty (&arr)[Dim])
{
    cout<<msg<<endl;
    for(size_t i=0;i<Dim;++i)
    {
        cout<<setw(4)<<arr[i]<<' ';
    }
    cout<<endl;
}

//  Заполняет массив случайными числами
template<class Ty,size_t Dim>
void fillArray(Ty (&arr)[Dim])
{
    for(size_t i=0;i<Dim;++i)
    {
        arr[i]=rand()%50;
    }
}

//
 Вставляет в упорядоченный по возрастанию массив значение сохраняя порядок
template<class Ty,size_t Dim>
void insertInArray(Ty (&arr)[Dim],Ty val)
{
    //  Бинарный поиск места вставки в массиве
    size_t first=0,last=Dim;
    while(first<last)
    {
        size_t mid=(last-first)/2+first;
        if(arr[mid]>val)
        {
            last=mid;
        }
        else
        {
            first=mid+1;
  
       }
    }
    // Вставка и сдвиг элементов
    for(size_t i=first;i<Dim;++i)
    {
        swap(arr[i],val);
    }
}

int main()
{
    srand(time(0));
    locale::global(locale(""));

    // Массив
    dataType array[COUNT];

    // Заполним массив
    fillArray(array);
    // Распечатаем
    printArray("Исходный массив:",array);

    // Отсортируем массив
    sort(array,array+COUNT,less<dataType>());
 
  printArray("Отсортированный массив:",array);

    cout<<"Вставим "<<INS_COUNT<<" числа"<<endl;
    // Вставим несколько элементов
    for(size_t i=0;i<INS_COUNT;++i)
    {
        dataType value=rand()%50;
        cout<<"Вставим число "<<value<<endl;
        insertInArray(array,value);
        printArray("Массив после вставки:",array);
    }

    return 0;
}


Пример работы программы:
Код:
Исходный массив:
  41   45   16    9   15   38   23   30   22   43   17   24   31   42    8   11   27   47   32    3
Отсортированный массив:
   3    8    9   11   15   16   17   22   23   24   27   30   31   32
  38   41   42   43   45   47
Вставим 3 числа
Вставим число 37
Массив после вставки:
   3    8    9   11   15   16   17   22   23   24   27   30   31   32   37   38   41   42   43   45
Вставим число 10
Массив после вставки:
   3    8    9   10   11   15   16   17   22   23   24   27   30   31   32   37   38   41   42   43
Вставим число 20
Массив после вставки:
   3    8    9   10   11   15   16   17   20   22   23   24   27   30   31   32   3
 7   38   41   42


Добавил с динамическим размещением согласно просьбе из мини-форума.
Код:
#include <cstdlib>
#include <cstdio>
#include <locale>
#include <limits>
#include <iostream>
#include <iomanip>
#include <stdexcept>

using namespace std;

typedef int dataType; //  Тип данных для элементов массива

template<class Ty>
Ty
input(const char* const msg)
{
    while (true)
    {
        Ty result = Ty();
        cout << msg;
        cin >> result;
        if (cin.fail())
        {
            cout << "Ошибочный ввод" << endl;
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
        }
        else
        {
            cin.ignore(numeric_limits<streamsiz
 e>::max(), '\n');
            return result;
        }
    }
}

//  Варианты ввода
enum menuChoice
{
    MANUAL,
    RANDOM
};

//  Меню выбора вариантов ввода
menuChoice menu()
{
    while (true)
    {
        cout << "Выберите как будут вводиться данные:" << endl
                << "1 - Вручную" << endl
                << "2 - Автогенерация" << endl
                <<
"Ваш выбор:";

        char choice = 0;
        cin.get(choice);
        cin.ignore(numeric_limits<streamsize>::max(), '\n');

        switch (choice)
        {
        case '1':
            return MANUAL;
        case '2':
            return RANDOM;
        }
        cout << "Будьте внимательней!" << endl;
    }
}

//  Выводит массив на stdout
void pr
 intArray(const char* const msg, dataType* arr, size_t count)
{
    cout << msg << endl;
    for (size_t i = 0; i < count; ++i)
    {
        cout << setw(4) << arr[i] << ' ';
    }
    cout << endl;
}

//  Вставка в упорядоченный массив
void insertInArray(dataType* &array, size_t& count, dataType value)
{
    // Выделяем дополнительно память
    dataType* newPtr = static_cast<dataType*> (realloc(array, sizeof (dataType)*(count
+ 1)));
    if (!newPtr)
    {
        throw bad_alloc();
    }
    array = newPtr;

    //  Бинарный поиск места вставки в массиве
    size_t first = 0, last = count++;
    while (first < last)
    {
        size_t mid = (last - first) / 2 + first;
        if (array[mid] > value)
        {
            last = mid;
        }
        else
        {
            first = mid + 1;
        }
    }

 
    // Вставка и сдвиг элементов
    for (size_t i = first; i < count; ++i)
    {
        swap(array[i], value);
    }

}

//  Заполнение массива
void fillArray(dataType* &array, size_t maxCount, menuChoice choice)
{
    size_t count = 0;
    while (count < maxCount)
    {
        dataType value;
        switch (choice)
        {
        case MANUAL:
            value = input<dataType>("Введите значение:");
            break;

       case RANDOM:
            value = rand() % 50;
            break;
        default:
            throw runtime_error("Ошибка в параметре choice");
        }
        insertInArray(array, count, value);
        cout << "Вставим элемент " << value << endl;
        printArray("Массив:", array, count);
    }
}

int main()
{
    srand(time(0));
    locale::global(locale("&q
 uot;));

    dataType* array = 0; //  Массив будем хранить здесь

    try
    {
        size_t maxCount = input<size_
t > ("Количество элементов :"), count = 0;
        fillArray(array, maxCount, menu());
    }
    catch (bad_alloc&)
    {
        cout << "Невозможно выделить память" << endl;
    }
    catch (runtime_error& ex)
    {
        cout << ex.what() << endl;
    }

    if (array)
    {
        delete[] array;
    }

    return 0;
}

Примеры работы:
Код:
Количество элементов :5
Выберите как будут вводиться данные:
1 - Вручную
2 - Автогенерация
Ваш выбор:1
Введите значение:2
Вставим элемент 2
Массив:
   2
Введите значение:8
Вставим элемент 8
Массив:
   2    8
Введите значение:4
Вставим элемент 4
Массив:

    2    4    8
Введите значение:1
Вставим элемент 1
Массив:
   1    2    4    8
Введите значение:7
Вставим элемент 7
Массив:
   1    2    4    7    8
-------------------------------------------
Количество элементов :5
Выберите как будут вводиться данные:
1 - Вручную
2 - Автогенерация
Ваш выбор:2
Вставим элемент 27
Массив:
  27
Вставим элемент 23
Массив:
  23   27
Вставим элемент 5
Массив:
   5   23   27
Вставим элемент 5
Массив:

  5    5   23   27
Вставим элемент 42
Массив:
   5    5   23   27   42

Ответ отправил: Micren, Профессионал
Ответ отправлен: 24.03.2010, 10:40
Номер ответа: 260323

Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 260323 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

    Задать вопрос экспертам этой рассылки »

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров »

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

    © 2001-2010, Портал RFpro.ru, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2010.6.14 от 03.03.2010
    В избранное