Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.86
Morozy4
0 / 0 / 0
Регистрация: 04.06.2012
Сообщений: 9
#1

Сортировка стека методом вставки - C++

04.06.2012, 18:53. Просмотров 1934. Ответов 7
Метки нет (Все метки)

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

Будет ли сортировкой вставкой использование ханойских башен?
Если да, то на что дальше следует обратить внимание?
Заранее спасибо
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.06.2012, 18:53     Сортировка стека методом вставки
Посмотрите здесь:

Сортировка методом центрированной вставки - C++
Доброго времени суток. Может у кого-нибудь есть пример на С++ этой сортировки? Буду рад поглядеть) В интернете не нашел примеров)

Сортировка диагоналей матрицы методом вставки - C++
В общем нужно сортировать методом вставки диагонали, параллельные главной по убыванию Код сделан на половину, отлично сортирует...

Непонятно. Сортировка методом вставки + перегруженные функции. - C++
непонятно. помогите пожалуйста. #include <iostream.h> #include <stdlib.h> #include <conio.h> void sort(int n, int a); ...

Сортировка массивов методом пузырька, вставки и быстрым способом - C++
Помогите сделать три программы которые создают двумерные массивы рандомом и сортируют методом пузырька, вставки и быстрым способом.

Быстрая сортировка с внутренней досортировкой небольших частей методом вставки - C++
здравствуйте!!! интересует алгоритм задачи на быструю сортировку с внутренней досортировкой небольших частей методом вставки Sortlnsert0...

Двумерный массив рациональных чисел + среднее арифметическое чисел массива + сортировка методом вставки - C++
Ничего не могу понять!Вроде все правильно создавал, но считает неправильно. +Выдает ошибку Так же не могу отсортировать методом вставки...

Нужна сорировка методом вставки - C++
Имеется следующая программа. #include <iomanip.h> #include <fstream.h> #include <stdlib.h> #include <string.h> #include <io.h>...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
David Sylva
1285 / 947 / 51
Регистрация: 17.05.2012
Сообщений: 2,687
04.06.2012, 20:09     Сортировка стека методом вставки #2
Не факт, что я правильно понял задание, но стек лучше реализовать в классе в котором содержится функция вставки и вывода
C++
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
32
33
34
35
36
#include <iostream> 
using namespace std; 
 
class Stack    // класс стек
{ 
private: 
    static const int MAX = 10; // размер
    int st[MAX]; 
    int top; 
public: 
    Stack() 
    { top = 0; } 
    void push (int var ) // функция вставки
    { st [++top] = var; } 
    int pop() 
    { return st[top--]; } // функция вывода
}; 
 
int main()
{   
    Stack s1;
 
    s1.push(11); 
    s1.push(22);    
    s1.push(33);    
    s1.push(44);    
    s1.push(55);    
    s1.push(66); 
    cout << s1.pop() << endl;
    cout << s1.pop() << endl;   
    cout << s1.pop() << endl;   
    cout << s1.pop() << endl;   
    cout << s1.pop() << endl;   
    cout << s1.pop() << endl;  
 
}
Morozy4
0 / 0 / 0
Регистрация: 04.06.2012
Сообщений: 9
04.06.2012, 21:23  [ТС]     Сортировка стека методом вставки #3
Извините, но пока знаком только с си.
Еще раз напишу задание, написал действительно ацкий ад)
Дан стек отображенный на массив.
Необходимо написать процедуру, вставляющую элемент в стек (упорядоченный по возрастанию) с сохранением порядка.
Для сортировки использовать метод сортировки простой вставки.
П.С. нельзя использовать статические свойства стека(реализацию). По возможности использовать рекурсию.
gray_fox
What a waste!
1411 / 1140 / 55
Регистрация: 21.04.2012
Сообщений: 2,362
Завершенные тесты: 3
04.06.2012, 23:00     Сортировка стека методом вставки #4
Если правильно понял то так:
C
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdlib.h>
#include <stdio.h>
 
 
#define MAX_STACK_SIZE 128
 
typedef struct {
   int buffer[MAX_STACK_SIZE];
   size_t top;
} stack_t;
 
void init_stack(stack_t * stack) {
   stack->top = 0;
}
 
int empty_stack(stack_t const* stack) {
   return stack->top == 0;
}
 
int top_stack(stack_t const* stack) {
   return stack->buffer[stack->top - 1];
}
 
void pop_stack(stack_t * stack) {
   --stack->top;
}
 
void push_stack(stack_t * stack, int value) {
   stack->buffer[stack->top++] = value;
}
 
void push_sorted_stack(stack_t * stack, int value) {
   int top;
   
   if (!empty_stack(stack)) {
      top = top_stack(stack);
      
      if (top > value) {
         pop_stack(stack);
         push_sorted_stack(stack, value);
         push_stack(stack, top);
         return;
      }
   }
   
   push_stack(stack, value);
}
 
void print_stack(stack_t const* stack) {
   size_t i;
   
   for (i = 0; i != stack->top; ++i) {
      printf("%d ", stack->buffer[i]);
   }
   printf("\n");
}
 
 
int main() {
   stack_t sorted;
   stack_t unsorted;
   int i;
   
   init_stack(&unsorted);
   for (i = 9; i != 0; --i) {
      push_stack(&unsorted, (i * 17) % 25);
   }
   printf("unsorted: ");
   print_stack(&unsorted);
   
   init_stack(&sorted);
   for (i = 9; i != 0; --i) {
      push_sorted_stack(&sorted, (i * 17) % 25);
   }
   printf("sorted:   ");
   print_stack(&sorted);
 
   return EXIT_SUCCESS;
}
http://liveworkspace.org/code/0e4608...e2ce59413bcd0c
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
05.06.2012, 13:05     Сортировка стека методом вставки #5
Цитата Сообщение от Morozy4 Посмотреть сообщение
То есть после вставки стек должен быть отсортирован.
А если вставить среднее? Получается, в середину? Это уже не стек.
gray_fox
What a waste!
1411 / 1140 / 55
Регистрация: 21.04.2012
Сообщений: 2,362
Завершенные тесты: 3
05.06.2012, 18:09     Сортировка стека методом вставки #6
Цитата Сообщение от taras atavin Посмотреть сообщение
Это уже не стек.
Я так понял нужна приоритетная очередь на основе стека.
Morozy4
0 / 0 / 0
Регистрация: 04.06.2012
Сообщений: 9
06.06.2012, 18:53  [ТС]     Сортировка стека методом вставки #7
Спасибо за помощь)
Можно еще уточнить алгоритм самой сортировки?
Правильно понял эту функцию?

void push_sorted_stack(stack_t * stack, int value) {
int top;

if (!empty_stack(stack)) {
top = top_stack(stack);

if (top > value) {
pop_stack(stack);
push_sorted_stack(stack, value);
push_stack(stack, top);

return;
}
}

При вставке элемента в стек идет проверка, не меньше ли вставляемый элемент последнего элемента стека. Если вставляемый элемент меньше верхнего, то верхний извлекается и перегоняется в дополнительный стек, далее все тот же вставляемый элемент проверяется с новым верхним элементом.
Так до тех пор пока вставляемый не будет больше верхнего, и затем все изъятые элементы добавляются в стек?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.06.2012, 19:51     Сортировка стека методом вставки
Еще ссылки по теме:

Отсортировать столбцы матрицы методом вставки - C++
void Matrix::Sort_Matrix() { for (int k=0; k&lt;Col; ++k) { for (int i = 1,j; i&lt;Row; i++) { int tmp = Numbers ...

Создание дерева методом вставки в корень - C++
Реализация BST-деревьев Создание дерева методом вставки в корень. Печать элементов дерева в упорядоченном виде.

Неправильно сортирует массив методом вставки - C++
#include &lt;iostream&gt; #include &lt;cstdlib&gt; using namespace std; int main() { setlocale (LC_ALL, &quot;RUS&quot;); int z,n,x,i,j,N,M,a; ...

Задача на сортировку массива методом вставки на С++ - C++
Помогите, пожалуйста, решить задачу. Отсортируйте по возрастанию методом вставки одномерный целочисленный массив, введенный с клавиатуры....

Сортировка стека - C++
Пытаюсь сортировать стек, но ничего не выходит, помогите пожалуйста #include &quot;stdafx.h&quot; #include &quot;iostream&quot; #include &quot;stack&quot; ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
gray_fox
What a waste!
1411 / 1140 / 55
Регистрация: 21.04.2012
Сообщений: 2,362
Завершенные тесты: 3
06.06.2012, 19:51     Сортировка стека методом вставки #8
Ну да, только дополнительный стек явно не задаётся, он получается за счёт рекурсивных вызовов. Так то, если без рекурсии, всё выглядит проще: снимаешь из стека до нужного места, кладёшь элемент, кладёшь всё снятое обратно. Примерно так:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void push_sorted_stack(stack_t * stack, int value) {
   stack_t values;
   int top;
 
   init_stack(&values);
 
   while (!empty_stack(stack)) {
      top = top_stack(stack);
      if (top <= value) {
         break;
      }
      push_stack(&values, top);
      pop_stack(stack);
   }
 
   push_stack(stack, value);
 
   while (!empty_stack(&values)) {
      push_stack(stack, top_stack(&values));
      pop_stack(&values);
   }
}
Yandex
Объявления
06.06.2012, 19:51     Сортировка стека методом вставки
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru