Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
Timas
0 / 0 / 1
Регистрация: 22.11.2014
Сообщений: 153
1

Сортировка линейным выбором

03.05.2017, 13:28. Просмотров 726. Ответов 16
Метки нет (Все метки)

Есть стек
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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct _Item
{
    float _key;
    char _str[31];
} Item;
 
typedef Item UDT_TYPE;
 
typedef struct _Udt
{
    UDT_TYPE *_data;
    int _capacity;
    int _size;
} Udt;
 
void udtCreate(Udt *udt, const int capacity);
int udtPush(Udt *udt, const UDT_TYPE value);
void udtPop(Udt *udt);
UDT_TYPE udtTop(const Udt *udt);
int udtSize(const Udt *udt);
int udtEmpty(const Udt *udt);
void udtPrint(Udt *udt);
void udtDestroy(Udt *udt);
Как его отсортировать методом выбора?
Есть пока только своп и чуть-чуть от функции сортировки.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void udtSwap(Udt *udt1, Udt *udt2)
{
    Udt tmp;
 
    tmp = *udt1;
    *udt1 = *udt2;
    *udt2 = tmp;
}
 
void udtSelectionSort(Udt *udt)
{
    const int cap = udtCapacity(udt);
    Udt sorted, tmp;
    UDT_TYPE item;
 
    if (cap < 2)
        return;
 
    udtCreate(&sorted, cap);
    udtCreate(&tmp, cap);
    
    while (!udtEmpty(udt))
    {
Навсякий случай добавлю функции, но с ними все в порядке
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
80
81
82
83
84
void udtCreate(Udt *udt, const int capacity)
{
    int i;
    UDT_TYPE item;
 
    item._key = 0.0f;
    item._str[0] = '\0';
 
    if (capacity <= 0)
        return;
 
    udt->_data = (UDT_TYPE *)malloc(sizeof(UDT_TYPE) * capacity);
 
    for (i = 0; i < capacity; i++)
        udt->_data[i] = item;
 
    udt->_capacity = capacity;
    udt->_size = 0;
}
 
int udtPush(Udt *udt, const UDT_TYPE value)
{
    if (udt->_size == udt->_capacity)
        return 0;
    
    udt->_data[udt->_size++] = value;
 
    return 1;
}
 
void udtPop(Udt *udt)
{
    if (udt->_size == 0)
        return;
    
    udt->_size--;
}
 
UDT_TYPE udtTop(const Udt *udt)
{
    return udt->_data[udt->_size - 1];
}
 
int udtSize(const Udt *udt)
{
    return udt->_size;
}
 
int udtEmpty(const Udt *udt)
{
    return udt->_size == 0;
}
 
void udtPrint(Udt *udt)
{
    int i;
    Item item;
 
    printf("+-------+------------+------------------------------+\n");
    printf("| Номер |    Ключ    |            Строка            |\n");
    printf("+-------+------------+------------------------------+\n");
 
    for (i = 0; i < udtSize(udt); i++)
    {
        item = udt->_data[i];
 
        printf("|%7d|%12.2f|%30s|\n", i + 1, item._key, item._str);
    }
 
    printf("+-------+------------+------------------------------+\n");
}
 
void udtDestroy(Udt *udt)
{
    if (udt->_data != NULL)
    {
        free(udt->_data);
 
        udt->_data = NULL;
    }
 
    udt->_capacity = 0;
    udt->_size = 0;
}
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.05.2017, 13:28
Ответы с готовыми решениями:

Сортировка на С линейным выбором и подсчётом
#include &lt;stdio.h&gt; #include &lt;time.h&gt; int k=0; int c=0; // число сравнений const int m = 10;...

Сортировка выбором
Вот код. Нужно лишь поменять так, чтобы сортировало четные элементы массива (где нужно увеличить на...

Сортировка выбором
Напишите программу, реализующую сортировку выбором

Сортировка выбором (2 в 1)
Пишу вот сортировку... выбором Должна быть по возрастанию и убыванию.. ! имеем две функции...

Сортировка выбором
Нужно отсортировать массив по возрастанию #include&lt;stdio.h&gt; int main() { int temp=0; int ...

16
Timas
0 / 0 / 1
Регистрация: 22.11.2014
Сообщений: 153
04.05.2017, 18:45  [ТС] 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
37
38
39
40
41
42
void udtSelectionSort(Udt *udt)
{
    const int cap = udtCapacity(udt);
    Udt sorted, tmp;
    UDT_TYPE item;
 
    if (cap < 2)
        return;
 
    udtCreate(&sorted, cap);
    udtCreate(&tmp, cap);
    
    while (!udtEmpty(udt))
 
 
 
 
    {
        udtPush(&tmp, udtTop(udt));//
        udtPop(udt);           //
 
        while (!udtEmpty(udt))
        {
            item = udtTop(udt);
 
            udtPop(udt);
 
            if (item._key < udtTop(&tmp)._key)
                udtPush(&tmp, item);
        }
 
        udtPush(&sorted, udtTop(&tmp));
        udtPop(&tmp);
        
        udtSwap(udt, &tmp);
    }
 
    udtSwap(udt, &sorted);
 
    udtDestroy(&sorted);
    udtDestroy(&tmp);
}
push-Добавить (положить) в конец стека новый элемент
pop-Извлечь из стека последний элемент
back-Узнать значение последнего элемента (не удаляя его)
size-Узнать количество элементов в стеке
clear-Очистить стек (удалить из него все элементы)

Могу прикрепить весь код.
0
shvyrevvg
1246 / 722 / 345
Регистрация: 12.05.2016
Сообщений: 2,021
04.05.2017, 19:02 3
Timas, полный текст задания в студию.
1
Timas
0 / 0 / 1
Регистрация: 22.11.2014
Сообщений: 153
05.05.2017, 08:34  [ТС] 4
shvyrevvg, Удалить максимальный элемент стека, используя метод сортировки линейным выбором.

Добавлено через 13 часов 28 минут
Сам принцип сортировки понимаю. Но с реализацией проблемы. Есть у кого-нибудь идеи?
0
05.05.2017, 08:34
oldnewyear
423 / 416 / 158
Регистрация: 21.05.2016
Сообщений: 1,329
05.05.2017, 08:53 5
Что такое сортировка линейным выбором?

Добавлено через 5 минут
Я так понял это обычная сортировка выбором
1
shvyrevvg
1246 / 722 / 345
Регистрация: 12.05.2016
Сообщений: 2,021
05.05.2017, 09:00 6
Цитата Сообщение от Timas Посмотреть сообщение
Сам принцип сортировки понимаю. Но с реализацией проблемы. Есть у кого-нибудь идеи?
Гоняете из стека в стек, в результирующий закидываете минимумы, потом делаете pop. А вообще, по-моему, сортировать стек это надо быть отбитым вконец
2
Timas
0 / 0 / 1
Регистрация: 22.11.2014
Сообщений: 153
05.05.2017, 10:14  [ТС] 7
shvyrevvg, задание такое, ничего не могу поделать.

Добавлено через 14 секунд
oldnewyear, да

Добавлено через 26 минут
shvyrevvg, Все-таки я неправильно понял. Видимо нужно прогнать стек через функцию сортировки выбором.
0
shvyrevvg
1246 / 722 / 345
Регистрация: 12.05.2016
Сообщений: 2,021
05.05.2017, 10:22 8
Цитата Сообщение от Timas Посмотреть сообщение
Видимо нужно прогнать стек через функцию сортировки выбором.
Я не понимаю что значит прогнать стек через функцию. Для начала, запишите для обычного массива сортировку.
1
Timas
0 / 0 / 1
Регистрация: 22.11.2014
Сообщений: 153
05.05.2017, 13:38  [ТС] 9
shvyrevvg,
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void sort1(int *a, const int n)
{
    int i, j;
    int min;
 
    for (i = 0; i < n - 1; i++)
    {
        min = i;
 
        for (j = i + 1; j < n; j++)
            if (a[j] < a[min])
                min = j;
 
        swap(&a[i], &a[min]);
    }
}
0
shvyrevvg
1246 / 722 / 345
Регистрация: 12.05.2016
Сообщений: 2,021
05.05.2017, 14:13 10
Timas, я так понимаю во внутрь стека лазить запретили? Разрешается использовать только функции push, pop, top?
1
Timas
0 / 0 / 1
Регистрация: 22.11.2014
Сообщений: 153
05.05.2017, 14:59  [ТС] 11
shvyrevvg, да

Добавлено через 16 минут
shvyrevvg, также стек отображается на массив
0
shvyrevvg
1246 / 722 / 345
Регистрация: 12.05.2016
Сообщений: 2,021
05.05.2017, 15:18 12
Цитата Сообщение от Timas Посмотреть сообщение
shvyrevvg, также стек отображается на массив
Если можно лазить в массив data, то проблем вообще нет Сортируете data и не паритесь.
1
oldnewyear
423 / 416 / 158
Регистрация: 21.05.2016
Сообщений: 1,329
05.05.2017, 15:33 13
Удалить максимальный элемент стека, используя метод сортировки линейным выбором
Что-то не так с заданием. В задании не сказано, что нужно отсортировать стек, а удалить элемент сортировкой нельзя.
2
shvyrevvg
1246 / 722 / 345
Регистрация: 12.05.2016
Сообщений: 2,021
05.05.2017, 15:39 14
Цитата Сообщение от oldnewyear Посмотреть сообщение
Что-то не так с заданием. В задании не сказано, что нужно отсортировать стек, а удалить элемент сортировкой нельзя.
Угу, еще смущает, что для поиска максимального элемента надо весь стек ковырять сортировкой.. Или сортировка чтобы максимум оказался последним и его можно было pop-ом удалить Предлагаю сделать сортировку массива data, если не прокатит, тогда через push, pop
1
Timas
0 / 0 / 1
Регистрация: 22.11.2014
Сообщений: 153
05.05.2017, 18:21  [ТС] 15
shvyrevvg, Я решил через push, pop и остальные. Также решил использовать временные стеки. В tmp кидал минимальное, в tmp1 все остальные, потом своп tmp и sorted. Но возникла проблема. В каком месте надо делать своп tmp1(остальных) и начального стека, чтобы алгоритм стал рекурсивным.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
while (!udtEmpty(udt)){
 
        udtPush(&tmp, udtTop(udt));
        udtPop(udt);                            
        while (!udtEmpty(udt)) 
        {
 
            item = udtTop(udt);
            udtPop(udt);
            if (item._key < udtTop(&tmp)._key){
                
                udtPush(&tmp1, udtTop(&tmp));
                udtPop(&tmp);
                udtPush(&tmp, item);}
                
            else{udtPush(&tmp1, item);}     
        }   
        udtSwap(&tmp, &sorted);}
0
shvyrevvg
1246 / 722 / 345
Регистрация: 12.05.2016
Сообщений: 2,021
05.05.2017, 18:30 16
Timas, так нужно делать swap элементов стека(нужно как-то их выбирать в стеке), а у Вас udtSwap обменивает структуры стека.

Не по теме:

завтра посмотрю, сегодня я уже не хочу думать :beer2:

1
Timas
0 / 0 / 1
Регистрация: 22.11.2014
Сообщений: 153
06.05.2017, 16:17  [ТС] 17
shvyrevvg,
Цитата Сообщение от shvyrevvg Посмотреть сообщение
так нужно делать swap элементов стека
Да это я тоже понимаю, но проблема в
Цитата Сообщение от shvyrevvg Посмотреть сообщение
нужно как-то их выбирать в стеке
Мне кажется, что подойдет и то, что я почти написал, нехватает только рекурсии.

Также прикрепляю весь код
main.c
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <stdio.h>
#include "sort.h"
 
void getLine(char *str, const int size);
 
int main(void)
{
    const int N = 10;
    int action;
    char tmpCh;
    Udt udt;
    Item item;
 
    udtCreate(&udt, N);
 
    do
    {
        printf("Меню\n");
        printf("1) Добавить элемент\n"); 
        printf("2) Удалить элемент\n");
        printf("3) Размер стека\n");
        printf("4) Сортировка\n");
        printf("5) Печать\n");
        printf("6) Выход\n");
        printf("Выберите действие: ");
        scanf("%d", &action);
 
        switch (action)
        {
            case 1:
            {
                printf("Введите ключ: ");
                scanf("%f", &item._key);
                scanf("%c", &tmpCh);
                printf("Введите Строку: ");
                getLine(item._str, sizeof(item._str));
 
                if (udtPush(&udt, item))
                    printf("Элемент с ключом %f и строкой '%s' добавлен успешно\n", item._key, item._str);
                else
                    printf("Дек полон\n");
            }
            break;
 
            case 2:
            {
                if (udtSize(&udt) > 0)
                {
                    item = udtTop(&udt);
 
                    udtPop(&udt);
 
                    printf("Элемент с ключом %f и строкой '%s' удален успешно\n", item._key, item._str);
                }
                else
                    printf("Стек пуст\n");
            }
            break;
            
            case 3:
            {
                printf("Размер стека: %d (Реальный размер: %d)\n", udtSize(&udt), N);
            }
            break;
 
            case 4:
            {
                udtSelectionSort(&udt);
 
            break;
            }       
 
            case 5:
            {
                if (udtSize(&udt) > 0)
                {
                    printf("Стек:\n");
 
                    udtPrint(&udt);
                }
                else
                    printf("Стек пуст\n");
            }
            break;
 
            case 6: break;
 
            default:
            {
                printf("Ошибка. Такого пункта меню не существует\n");
            }
            break;
        }
    }
    while (action != 6);
    
    udtDestroy(&udt);
 
    return 0;
}
 
void getLine(char *str, const int size)
{
    int cnt = 0, ch;
 
    while ((ch = getchar()) != '\n' && cnt < size - 1)
        str[cnt++] = ch;
 
    str[cnt] = '\0';
}
sort.h:
C
1
2
3
4
5
6
7
8
9
#ifndef UDT_SORT_H
#define UDT_SORT_H
 
#include "udt.h"
 
void udtSwap(Udt *udt1, Udt *udt2);
void udtSelectionSort(Udt *udt);
 
#endif
sort.c
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
#include "sort.h"
 
void udtSwap(Udt *udt1, Udt *udt2)
{
    Udt tmp;
 
    tmp = *udt1;
    *udt1 = *udt2;
    *udt2 = tmp;
}
 
void udtSelectionSort(Udt *udt)
{
    const int cap = udtCapacity(udt);
    Udt sorted, tmp,tmp1;
    UDT_TYPE item;
 
    if (cap < 2)
        return;
 
    udtCreate(&sorted, cap);
    udtCreate(&tmp, cap);
    udtCreate(&tmp1, cap);      
        
 
    while (!udtEmpty(udt)){
 
        udtPush(&tmp, udtTop(udt));
        udtPop(udt);                            
        while (!udtEmpty(udt)) 
        {
 
            item = udtTop(udt);
            udtPop(udt);
            if (item._key < udtTop(&tmp)._key){
                
                udtPush(&tmp1, udtTop(&tmp));
                udtPop(&tmp);
                udtPush(&tmp, item);}
                
            else{udtPush(&tmp1, item);}     
        }   
        udtSwap(&tmp, &sorted);
    }
 
    
    
}

udt.h
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
#ifndef UDT_H
#define UDT_H
 
#include <stdio.h>
#include <stdlib.h>
 
typedef struct _Item
{
    float _key;
    char _str[31];
} Item;
 
typedef Item UDT_TYPE;
 
typedef struct _Udt
{
    UDT_TYPE *_data;
    int _capacity;
    int _size;
} Udt;
 
void udtCreate(Udt *udt, const int capacity);
int udtPush(Udt *udt, const UDT_TYPE value);
void udtPop(Udt *udt);
UDT_TYPE udtTop(const Udt *udt);
int udtSize(const Udt *udt);
int udtEmpty(const Udt *udt);
void udtPrint(Udt *udt);
void udtDestroy(Udt *udt);
 
#endif
udt.c
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
80
81
82
83
84
85
86
87
88
89
90
#include "udt.h"
 
void udtCreate(Udt *udt, const int capacity)
{
    int i;
    UDT_TYPE item;
 
    item._key = 0.0f;
    item._str[0] = '\0';
 
    if (capacity <= 0)
        return;
 
    udt->_data = (UDT_TYPE *)malloc(sizeof(UDT_TYPE) * capacity);
 
    for (i = 0; i < capacity; i++)
        udt->_data[i] = item;
 
    udt->_capacity = capacity;
    udt->_size = 0;
}
 
int udtPush(Udt *udt, const UDT_TYPE value)
{
    if (udt->_size == udt->_capacity)
        return 0;
    
    udt->_data[udt->_size++] = value;
 
    return 1;
}
 
void udtPop(Udt *udt)
{
    if (udt->_size == 0)
        return;
    
    udt->_size--;
}
 
UDT_TYPE udtTop(const Udt *udt)
{
    return udt->_data[udt->_size - 1];
}
 
int udtSize(const Udt *udt)
{
    return udt->_size;
}
 
int udtEmpty(const Udt *udt)
{
    return udt->_size == 0;
}
 
void udtPrint(Udt *udt)
{
    int i;
    Item item;
 
    printf("+-------+------------+------------------------------+\n");
    printf("| Номер |    Ключ    |            Строка            |\n");
    printf("+-------+------------+------------------------------+\n");
 
    for (i = 0; i < udtSize(udt); i++)
    {
        item = udt->_data[i];
 
        printf("|%7d|%12.2f|%30s|\n", i + 1, item._key, item._str);
    }
 
    printf("+-------+------------+------------------------------+\n");
}
 
void udtDestroy(Udt *udt)
{
    if (udt->_data != NULL)
    {
        free(udt->_data);
 
        udt->_data = NULL;
    }
 
    udt->_capacity = 0;
    udt->_size = 0;
}
int udtCapacity(const Udt *udt)
{
    return udt->_capacity;
}
Добавлено через 21 час 30 минут
Сделал, готово. Спасибо всем за помощь.
0
06.05.2017, 16:17
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.05.2017, 16:17

Сортировка массива выбором
Вот программы на паскале, кто может преобразовать их в си? {Сортировка массива выбором (в порядке...

Сортировка простым выбором
можете помочь,в чём ошибка? сортировка методом простого выбора - по алгоритму(на си) Код: ...

Сортировка столбцов матрицы выбором
Дана матрица nxn, содержащая вещественные числа. Отсортировать каждый столбец матрицы по...


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
Опции темы

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