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

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

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

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

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

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

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

Сортировка массива пузырьковым методом и методом вставки - C++
нужно написать программу которая будет делать сортировку этими способами в массиве 3x10, две кнопки, таблица (3х10), собственно...

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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!
1511 / 1214 / 69
Регистрация: 21.04.2012
Сообщений: 2,550
Завершенные тесты: 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!
1511 / 1214 / 69
Регистрация: 21.04.2012
Сообщений: 2,550
Завершенные тесты: 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;
}
}

При вставке элемента в стек идет проверка, не меньше ли вставляемый элемент последнего элемента стека. Если вставляемый элемент меньше верхнего, то верхний извлекается и перегоняется в дополнительный стек, далее все тот же вставляемый элемент проверяется с новым верхним элементом.
Так до тех пор пока вставляемый не будет больше верхнего, и затем все изъятые элементы добавляются в стек?
gray_fox
What a waste!
1511 / 1214 / 69
Регистрация: 21.04.2012
Сообщений: 2,550
Завершенные тесты: 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);
   }
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.06.2012, 19:51
Привет! Вот еще темы с ответами:

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

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

Отсортировать столбцы матрицы методом вставки - 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++
#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; ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
06.06.2012, 19:51
Ответ Создать тему
Опции темы

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