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

RFpro.ru: Алгоритмы и теория программирования

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 295 RSS
←   Январь 2011   →
 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://rfpro.ru/
Открыта: 11-11-2009

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

Статистика

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

RFpro.ru: Алгоритмы и теория программирования


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

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

Лучшие эксперты данной рассылки

Гаряка Асмик
Статус: Профессор
Рейтинг: 6969
∙ повысить рейтинг » 		Boriss
Статус: Академик
Рейтинг: 2655
∙ повысить рейтинг » 		Абаянцев Юрий Леонидович aka Ayl
Статус: Профессионал
Рейтинг: 2257
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / Алгоритмы и теория программирования

Номер выпуска:133
Дата выхода:31.01.2011, 19:30
Администратор рассылки:lamed (Профессор)
Подписчиков / экспертов:384 / 171
Вопросов / ответов:2 / 2

Вопрос № 181962: Здравствуйте, уважаемые эксперты! Нужна программа реализации алгоритма сортировки Шелла для АТД «Очередь» (очередь с одной головой). Можно на Паскале. Заранее спасибо....

Вопрос № 181986: Здравствуйте, уважаемые эксперты! Прошу решить задачу по вычислительной математике: Заранее спасибо. ...
Вопрос № 181962:

Здравствуйте, уважаемые эксперты!

Нужна программа реализации алгоритма сортировки Шелла для АТД «Очередь» (очередь с одной головой).
Можно на Паскале.

Заранее спасибо.

Отправлен: 23.01.2011, 02:41
Вопрос задал: pikvar (Посетитель)
Всего ответов: 1
Страница вопроса »

Отвечает Лысков Игорь Витальевич (Старший модератор) :
Здравствуйте, pikvar!
Теория

Будет непонятно, обращайтесь в мини-форум

Код:
#include <time.h>
#include <iostream.h>
#include
<stdlib.h>

typedef struct _queue    //структура для хранения одного элемента очереди
{
 int  item;     //значение
 _queue *pNext;     //адрес следующего в очереди
}QUEUE, *PQUEUE;

//помещение элемента в очередь
//ppQueueHead - адрес адреса головы (куда помещается новый)
//ppQueueTail - адрес адреса хвоста (откуда извлекается)
//iItem    - значение нового элемента, который помещаем в голову очереди
voi
 d PushQueueItem(QUEUE **ppQueueHead, QUEUE **ppQueueTail,int iItem)
{
 PQUEUE pQueueItem = new QUEUE; //запросим память под новый элемент очереди
 
 if (*ppQueueHead == NULL)  //если очередь пуста
 {
  *ppQueueTail = pQueueItem; //запоминаем в адресе хвоста адрес нового элемента (он будет первым в очереди)
 }
 else
 {
  (*ppQueueHead)->pNext = pQueueItem; //иначе, добавляем новый элемент в цепочку очереди
 }
 pQueueItem->item = iItem;  //сохраним значение элемента
 pQueueItem->pNext
= NULL;  //пометим, что последний
 *ppQueueHead = pQueueItem;  //сохраним, как новую голову
}

//извлечение элемента из очереди
//ppQueueHead - адрес адреса головы (куда помещается новый)
//ppQueueTail - адрес адреса хвоста (откуда извлекается)
//piItem   - адрес переменной, куда пишем значение элемента из хвоста очереди
//возвращает 1, если элемент получен и 
//    0, если очередь пуста
int PopQueueItem(QUEUE **ppQueue
 Head, QUEUE **ppQueueTail, int *piItem)
{
 PQUEUE pQueueItem = *ppQueueTail; //адрес хвоста
 if (pQueueItem)      //если очередь непуста
 {
  *piItem = pQueueItem->item;  //извлекаем значение элемента
  *ppQueueTail = pQueueItem->pNext; //запоминаем новый адрес хвоста
  if (NULL == *ppQueueTail)  //если все извлекли
   *ppQueueHead = NULL;  // то обнулим и адрес головы
  
  delete pQueueItem;    //удалим ненужный уже элемент из памяти
  return 1;      //элемент получен
 }
 return
0;       //очередь пуста
}

//создание очереди со случайным содержимым
//ppQueueHead - адрес адреса головы (куда помещается новый)
//ppQueueTail - адрес адреса хвоста (откуда извлекается)
void CreateQueue(QUEUE **ppQueueHead, QUEUE **ppQueueTail)
{
 srand(time(0));      //инициируем генератор псевдослучайных чисел

 int count = 20 + rand()%100;  //случайное число количества элементов очереди (20 <= count < 120)

 
 for (int i=0; i<count; i++)   //построим очередь из чисел 0-1000
  PushQueueItem(ppQueueHead, ppQueueTail, rand()%1000);
}

//получение длины очереди
//pQueueTail - адрес хвоста
//возвращает длину очереди
int GetCount(QUEUE *pQueueTail)
{
 QUEUE *pQueueItem;    //указатель на элемент очереди
 int  count;      //счетчик

 //пробежим по очереди, пока не дойдем до конца (пустого указателя), одновременно считая шаги
 for (count=0, pQueueItem=pQueueTail; pQueueItem; pQueueItem=pQueueItem->pNext,
count++);
 return count;      //вернем найденный счетчик
}

//получение значение элемента очереди по индексу (без удаления из очереди)
//pQueueTail - адрес хвоста
//index   - индекс
//iValue  - адрес переменной, куда запишем значение элемента
//возвращает 1, если элемент получен и 
//    0, если индекс выходит за пределы очереди
int GetQueueItem(QUEUE *pQueueTail, int index, int *iValue)
{
 QUEUE *pQueueItem;
 
 int  i;       //индекс для прохода по очереди

 //найдем адрес элемента очереди (считаем индекс, пока не будет равен требуемому
)
 for (i=0,pQueueItem=pQueueTail; pQueueItem, i!= index; i++,pQueueItem=pQueueItem->pNext);
 if (pQueueItem)      //нашли?
 {
  *iValue = pQueueItem->item;  //получаем значение
  return 1;      //все ок
 }
 return 0;       //не нашли
}

//запись значение элемента очереди по индексу
//pQueueTail - адрес хвоста
//index   - индекс
//iValue  - значение, которое пишем
//возвращает 1, если элемент записан и 
//    0, если индекс выходит за пределы очереди
int SetQueueItem(QUEUE
*pQueueTail, int index, int iValue)
{
 QUEUE *pQueueItem;
 int  i;       //индекс для прохода по очереди

 //найдем адрес элемента очереди (считаем индекс, пока не будет равен требуемому)
 for (i=0,pQueueItem=pQueueTail; pQueueItem, i!= index; i++,pQueueItem=pQueueItem->pNext);
 if (pQueueItem)      //нашли?
 {
  pQueueItem->item = iValue;  //меняем содержимое элемента очереди на новое
  return 1;      //все ок
 } return 0;       //не нашли
}

//вычисление последовательности приращений для сортировки Шелла
int increment(int inc[], int size) 
{
 int p1, p2, p3, s;

 p1 = p2 = p3 = 1;
 s = -1;
 do 
 {
  if (++s % 2) 
  {
   inc[s] = 8*p1 - 6*p2 + 1;
  } 
  else 
  {
   inc[s] = 9*p1 - 9*p3 + 1;
   p2 *= 2;
   p3 *= 2;
  }
  p1 *= 2;
 } while(3*inc[s] < size);  

 return s > 0 ? --s : 0;
}

//сортировка Шелла
void shellSort(PQUEUE
pQueueTail) 
{
 int  inc, i, j, item, temp, seq[40];
 int  s;
 int  size = GetCount(pQueueTail);

 // вычисление последовательности приращений
 s = increment(seq, size);
 while (s >= 0) 
 {
  // сортировка вставками с инкрементами inc[] 
  inc = seq[s--];

  for (i = inc; i < size; i++) 
  {
   GetQueueItem(pQueueTail, i, &temp);  //temp = Queue[i]
   for (j = i-inc; j >= 0; j -= inc)
   {
    GetQueueIte
 m(pQueueTail, j, &item); //item = Queue[j]
    if (item < temp)     //сортируем по возрастанию от хвоста к голове
     break;
    SetQueueItem(pQueueTail, j+inc, item); //Queue[j+inc] = item = Queue[j]
   }
   SetQueueItem(pQueueTail, j+inc, temp); //Queue[j+inc] = temp = Queue[i]
  }
 }
}

void main()
{
 PQUEUE pQueueHead = NULL;      //указатель на голову очереди
 PQUEUE pQueueTail = NULL;      //указатель на хвост очереди
 int  item;
 
 CreateQueue(&pQueueHead,
&pQueueTail);   //создадим очередь из случайных чисел < 1000 случайной длины 20 <= len < 120

 cout << "Before sorting:\n";     //для наглядности выведем элементы очереди до сортировки
 for (int i=0; GetQueueItem(pQueueTail, i, &item); i++) //получаем, пока не дойдем до конца
  cout << item << " ";      //выводим значение элемента
 cout << endl << endl;       //перевод строки
 
 shellSo
 rt(pQueueTail);       //сортируем

 cout << "After sorting:\n";      //выведем отсортированную очередь
 while(PopQueueItem(&pQueueHead, &pQueueTail, &item)) //получаем, одновременно удаляя из очереди, очередной элемент
 {
  cout << item << " ";      //выводим
 }
 cout << endl << endl;       //перевод строки
}

-----
Люби своего ближнего, как самого себя

Ответ отправил: Лысков Игорь Витальевич (Старший модератор)
Ответ отправлен: 26.01.2011, 12:45
Номер ответа: 265612
Украина, Кировоград
Тел.: +380957525051
ICQ # 234137952
Mail.ru-агент: igorlyskov@mail.ru

Оценка ответа: 5

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

    • Вопрос № 181986:

    Здравствуйте, уважаемые эксперты! Прошу решить задачу по вычислительной математике:



    Заранее спасибо.

    Отправлен: 23.01.2011, 19:08
    Вопрос задал: Sanek (Посетитель)
    Всего ответов: 1
    Страница вопроса »

    Отвечает lamed (Профессор) :
    Здравствуйте, Sanek!
    Решение 181986.doc (46.0 кб)
    Проверьте, пожалуйста, вычисления, особенно выбор функции.
    Если требуются разъяснения, задавайте вопросы в мини-форуме.
    Удачи!

    Ответ отправил: lamed (Профессор)
    Ответ отправлен: 30.01.2011, 19:06
    Номер ответа: 265660

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

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

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

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

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

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

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

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