Консультации Портала - Консультация #177430

Задать вопрос Консультации Пользователи Форум

Задать вопрос экспертам

Консультация № 177430

24.03.2010, 08:16

0.00 руб.

0 6 1

Компьютеры Программирование

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

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

Приложение:
#include<stdio.h>
#include<iostream>
using namespace std;
int n; //размерность массива

typedef int array[20]; //переименование типа int на тип array[20]

array *ptr,*ptr1; //массивы указателей

//////////////////////// Ввод массива //////////////////////////////

array* input(int size) //возвращение указателя на массив

{ cout<<"Input array:"<<endl;

ptr1=new array[20]; //выделение динамической памяти для массива

for(int i=0;i<size;i++) //заполнение массива указателей значениями элементов

cin>>*ptr1[i];

return ptr1;

}

////////////////////////// Вывод массива //////////////////////////////

void output(array* ptr,char *message)

{ //передаются как параметры указатель на массив и сообщение

cout<<message<<endl; //вывод сообщения

for (int i=0;i<n;i++)

cout<<*ptr[i]<<" "; //вывод значения по указателю

cout<<"\n"; } //переход на новую строчку экрана

////////////////// сортировка массива ( метод пузырька) /////////////////

void sort(array *ptr)

{ //параметр – массив указателей

int temp; //вспомогательная переменная

for(int i=0;i<n-1;i++) //выбор эталона для стравнения

{ for (int j=i+1; j<n; j++) //выбор текущего элемента массива

if (*ptr[j]>*ptr[i] ) //сравнение эталона и текущего элемента

{ temp=*ptr[j]; //поменять местами элементы массива

*ptr[j]=*ptr[i];

*ptr[i]=temp;

}

}

}

//////////////////////// Главная программа //////////////////////

void main()

{ cout<<"sort array"<<endl<<"\nInput number of array's members: ";

cin>>n; ptr=input(n); //инициализация указателя на массив чисел

output(ptr,"Entered array"); //вывод массива

sort(ptr); //сортировка массива

output(ptr,"Sorted array"); //вывод отсортированного массива

}

Обсуждение

Неизвестный

24.03.2010, 10:40

общий

это ответ

Здравствуйте, 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   37   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<streamsize>::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 printArray(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(""));

    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

Неизвестный

24.03.2010, 14:02

общий

Lesija:
Только сейчас обратил внимание на тему(Указатели и ссылки). Если Вам необходимо динамическое размещение массива напишите здесь в мини-форуме. Так же можете описать как, по вашему, должна производиться вставка элемента и другие пожелания. Исправлю как Вам угодно.

Неизвестный

24.03.2010, 16:06

общий

Огромное спасибо за программу!
Но мне всё же нужно использовать динамический массив (указатели).
Какие пожедаоания? Желательно, чтоб размерность массива и количество вставляемых элементов задавалось пользователем.
И если можно еще дописать в программке, чтоб генерация массива и вставляемых элементов была как рандомом, так и вводились вручную пользователем. Своего рода такая мини-менюшка.

Спасибо! Буду благодрана любой помощи!!!

Неизвестный

24.03.2010, 22:05

общий

Lesija:
Добавил в ответ.

Неизвестный

25.03.2010, 00:40

общий

Micren, спасибо большое!!! Вы меня выручаете!!!

И еще такой вопросик:
по условию - "в отсортированный массив чисел ввести новые числа, разместив их в соответствии с упорядоченностью массива."
Т.е. нужно, чтоб первоначально уже был задан массив чисел, а потом уже в него добавлять новые элементы?

Неизвестный

25.03.2010, 11:15

общий

Lesija:
Каждое новое число и так уже добавляется в уже отсортированный массив. Вы его и так создаете вводя новые числа. Считайте, что вначале Вы уже имеете массив с количеством элементов равных 0.

Форма ответа

Отправка постов/ответов доступна только зарегистрированным и подтвержденным пользователям.

Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.