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

Сортировка ЛОС - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
burst
1 / 1 / 0
Регистрация: 29.04.2010
Сообщений: 13
02.08.2010, 09:41     Сортировка ЛОС #1
Подскажите, как можно реализовать функцию шаблон сортировки элементов линейного однонаправленного списка ?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Fedogor
209 / 95 / 4
Регистрация: 23.07.2010
Сообщений: 235
02.08.2010, 09:58     Сортировка ЛОС #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
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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
typedef struct NODE {
        int value;
        struct NODE * next;
} node_t;
 
node_t * new_node(int val, node_t * last){
        node_t * n;
        if ( ( n = (node_t*)malloc(sizeof(node_t)) ) == NULL )
                return NULL;
        n->value = val;
        n->next = NULL;
        if ( last )
                last->next = n;
        return n;
}
 
node_t * min_node(node_t * n){
        node_t * minNode = n;
        while ( n = n->next )
                if ( n->value < minNode->value )
                        minNode = n;
        return minNode;
}
 
void swap_vals(node_t * a, node_t * b){
        int val;
        val = a->value;
        a->value = b->value;
        b->value = val;
}
 
void sort_nodes(node_t * n){
        node_t * minNode;
        while ( n->next ){
                if ( ( minNode = min_node(n) ) != n )
                        swap_vals(n, minNode);
                n = n->next;
        }
}
 
void print_nodes(const node_t * n){
        while ( n ){
                printf("%02d ", n->value);
                n = n->next;
        }
        printf("\n");
}
 
void delete_nodes(node_t * n){
        node_t * t;
        while ( n ){
                t = n->next;
                free(n);
                n = t;
        }
}
 
int main(void){
        node_t * first, * last;
        int needed;
 
        first = last = NULL;
        printf("Nodes needed: ");
        if ( scanf("%d", &needed) != 1 || needed < 1 ){
                fprintf(stderr, "Wrong number!\n");
                exit(EXIT_FAILURE);
        }
 
        srand(time(NULL));
        while ( needed-- ){
                if ( ( last = new_node(rand() % 100, last) ) == NULL ){
                        fprintf(stderr, "Can't create a new node!\n");
                        exit(EXIT_FAILURE);
                }
                if ( ! first )
                        first = last;
        }
 
        if ( ! first ){
                fprintf(stderr, "Shit happens!\n");
                exit(EXIT_FAILURE);
        }
 
        printf("Unsorted:\n");
        print_nodes(first);
 
        sort_nodes(first);
 
        printf("Sorted:\n");
        print_nodes(first);
 
        delete_nodes(first);
        exit(EXIT_SUCCESS);
}
burst
1 / 1 / 0
Регистрация: 29.04.2010
Сообщений: 13
02.08.2010, 10:13  [ТС]     Сортировка ЛОС #3
как написать сортировку списка я знаю....
меня интересует как написать функцию сортировки которая будет работать с разными типами, не сам алгоритм сортировки а скелет функции....
пс: не массива, не массива указателей а списка ....
Fedogor
209 / 95 / 4
Регистрация: 23.07.2010
Сообщений: 235
02.08.2010, 10:41     Сортировка ЛОС #4
Может эти примеры помогут:

статья1

статья2
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
02.08.2010, 10:54     Сортировка ЛОС #5
Цитата Сообщение от burst Посмотреть сообщение
меня интересует как написать функцию сортировки которая будет работать с разными типами
В С++ для этих целей шаблоны используются, но Вам же на С нужно? Тут с этим сложнее. Если писать функцию типа qsort, которая принимает указатели на void, всё равно понадобится функция для сравнения данных какого-то определённого типа...

Добавлено через 2 минуты
Fedogor, ага, помню, было такое... Но строки например так не сравнишь...
burst
1 / 1 / 0
Регистрация: 29.04.2010
Сообщений: 13
02.08.2010, 11:21  [ТС]     Сортировка ЛОС #6
Цитата Сообщение от easybudda Посмотреть сообщение
В С++ для этих целей шаблоны используются, но Вам же на С нужно? Тут с этим сложнее. Если писать функцию типа qsort, которая принимает указатели на void, всё равно понадобится функция для сравнения данных какого-то определённого типа...

Добавлено через 2 минуты
Fedogor, ага, помню, было такое... Но строки например так не сравнишь...
как раз таки на с++

я вот думаю мб я как то нитак задание понимаю ...

звучит оно так:

Разработать параметрическую функцию сортировки элементов заданной в варианте структуры данных по заданному алгоритму. Структуры - однонаправленный линейный список, проверочные типы int, char, float.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
02.08.2010, 17:08     Сортировка ЛОС #7
burst, а что мешает сразу задание озвучить?
burst
1 / 1 / 0
Регистрация: 29.04.2010
Сообщений: 13
02.08.2010, 21:35  [ТС]     Сортировка ЛОС #8
Задание: разработать параметрическую функцию сортировки элементов в заданной структуре данных. Написать программу позволяющую проверить применение данной функции на различных типах данных;
Содержание варианта: структура данных - однонаправленный линейный список; проверочные типы данных: int, char, float;

Как я понимаю в функцию должна в качестве аргумента передаваться структура, реализую компилятор ругается, что типа неправильный аргумент выбран в качестве передачи, вот код проги:

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
#include <iostream>
#include <conio.h>
 
using namespace std;
 
///////////////////////
struct int_lul
{
    int element;
    int_lul *next;
} *first, *last;
///////////////////////
 
void add()
{
    int_lul *ptr = new int_lul;
    ptr->element = ( rand()%99 + 1 );
    if( first == NULL )
        first = ptr;
    else
        last->next = ptr;
    ptr->next = NULL;
    last = ptr;
}
 
//---------------------------------------------------//
 
void show()
{
    int_lul *ptr = first;
    while( ptr != NULL )
    {
        cout << ptr->element;
        ptr = ptr->next;
        cout << endl;
    }
}
 
//---------------------------------------------------//
 
template <typename T>
void sort( T lul )
{
    int tmp;
    lul *ptr1 = first, *ptr2;
    while( ptr1 != NULL )
    {
        ptr2 = first;
        while( ptr2->next != NULL )
        {
            if( ptr2->element > ptr2->next->element )
            {
                tmp = ptr2->element;
                ptr2->element = ptr2->next->element;
                ptr2->next->element = tmp;
            }
            ptr2 = ptr2->next;
        }
        ptr1 = ptr1->next;
    }
}
//---------------------------------------------------//
 
int main()
{
    first = last = NULL;
    for( int i = 0; i < 10; i++ )
        add();
    show();
    cout << endl;
    sort( int_lul ); // <- "int_lul" аргумент на который ругается компилятор
    show();
    _getch();
}
Отсюда и вопрос есть ли возможность передавать различные структуры в качестве аргументов, если нет то тогда каким путем идти ....
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
03.08.2010, 05:41     Сортировка ЛОС #9
Тебе нужно передавать в функцию не тип, а экземляр этого типа. Т.е., в твоем случае, чтобы можно было изменять значение указателей, тебе нужно передать в функцию двойной указатель на тип int_lul (или ссылку на указатель, что будет более удобно).
Второе. Тип элемента структуры в функции сортировки у тебя жестко указан (т.е. с помощью твоей функции sort можно отсортировать только список, содержащий тип int). Так что нужно либо передавать его вторым параметром шаблона, либо сделать саму структуры шаблонной.
Yurii_74
paladin
 Аватар для Yurii_74
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
03.08.2010, 07:16     Сортировка ЛОС #10
Тут можно прочитать про шаблоны. Читаем, разбираемся, пишем.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
03.08.2010, 08:36     Сортировка ЛОС #11
Переделал твою программу для шаблонного класса списка:
myList.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
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#ifndef MYLIST_H
#define MYLIST_H
 
#include <stdexcept>
#include <iostream>
 
namespace my
{
    template<class M>
    struct node
    {
        M           value;
        node<M>*    next;
        node(M val) :  value(val), next(NULL) {}
    };
 
    template<class T>
    class list
    {
    public:
        list();
        list(const list<T>& rhs);
        ~list();
        void push(const T& rhs); // Добавление элемента в конец списка
        void unshift(const T& rhs); // Добавление элемента в начало списка
        T pop(); // Удаление элемента с конца
        T shift(); // Удаление элемента с начала
        bool empty() const; // true, если список пуст
        size_t size() const; // Размер списка
        void show(char delim = EMPTY) const; // Печать массива
 
        void sort(); // Сортировка списка
    private:
        node<T>*    m_pFirst; // Указатель на первый элемент списка
        size_t      m_nSize; // Размер списка
        static const char EMPTY = ' ';
    };
 
 
    template<class T>
    list<T>::list()
        : m_pFirst(NULL), m_nSize(0)
    {
    }
 
    template<class T>
    list<T>::list(const list<T>& rhs)
        : m_nSize(rhs.m_nSize), m_pFirst(NULL)
    {
        if(m_nSize)
        {
            node<T>* ptr = rhs.m_pFirst;
            if(ptr)
                m_pFirst = new node<T>(ptr->value);
            ptr = ptr->next;
            node<T>* temp = m_pFirst;
            while(ptr)
            {
                node<T>* newNode = new node<T>(ptr->value);
                temp->next = newNode;
                temp = temp->next;
                ptr = ptr->next;
            }
        }
    }
 
    template<class T>
    list<T>::~list()
    {
        while(m_pFirst)
        {
            node<T>* temp = m_pFirst;
            m_pFirst = m_pFirst->next;
            delete temp;
            --m_nSize;
        }
    }
 
    template<class T>
    void list<T>::push(const T& rhs)
    {
        if(!m_pFirst)
            m_pFirst = new node<T>(rhs);
        else
        {
            node<T>* temp = m_pFirst;
            while(temp->next)
                temp = temp->next;
            node<T>* newNode = new node<T>(rhs);
            temp->next = newNode;
        }
        ++m_nSize;
    }
 
    template<class T>
    void list<T>::unshift(const T& rhs)
    {
        node<T>* newNode = new node<T>(rhs);
        newNode->next = m_pFirst;
        m_pFirst = newNode;
        ++m_nSize;
    }
 
    template<class T>
    T list<T>::pop()
    {
        if(!m_pFirst)
            throw(std::runtime_error("Unable to delete the last node: the list is empty")); 
        node<T>* temp = m_pFirst;
        while(temp->next)
            temp = temp->next;
        node<T>* delNode = temp->next;
        T returnValue = delNode->value;
        delete delNode;
        temp->next = NULL;
        --m_nSize;
        return returnValue;
    }
 
    template<class T>
    T list<T>::shift()
    {
        if(!m_pFirst)
            throw(std::runtime_error("Unable to delete the first node: the list is empty")); 
        node<T>* temp = m_pFirst;
        T returnValue = temp->value;
        m_pFirst = m_pFirst->next;
        delete temp;
        --m_nSize;
        return returnValue;
    }
 
    template<class T>
    bool list<T>::empty() const
    {
        return (m_nSize == 0);
    }
 
    template<class T>
    size_t list<T>::size() const
    {
        return m_nSize;
    }
 
    template<class T>
    void list<T>::show(char delim) const
    {
        node<T>* temp = m_pFirst;
        while(temp)
        {
            std::cout << temp->value << delim;
            temp = temp->next;
        }
        std::cout << std::endl;
    }
 
    template<class T>
    void list<T>::sort()
    {
        for(node<T>* ptr1 = m_pFirst; ptr1; ptr1 = ptr1->next)
        {
            for(node<T>* ptr2 = m_pFirst; ptr2->next; ptr2 = ptr2->next)
            {
                if((ptr2->value) > (ptr2->next->value))
                {
                    T temp = ptr2->value;
                    ptr2->value = ptr2->next->value;
                    ptr2->next->value = temp;
                }
            }
        }
    }
};
 
#endif // MYLIST_H

main.cpp
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
#include <iostream>
#include <stdexcept>
#include <ctime>
 
#include "myList.h"
 
int main()
{
    try
    {
        srand(static_cast<int>(time(NULL)));
        const int MAX = 10;
        my::list<int> lst;
        for(size_t i = 0; i < 5; ++i)
        {
            lst.push(rand() % MAX);
            lst.unshift(rand() % MAX);
        }
        std::cout << "Unsorted list:" << std::endl;
        lst.show();
        lst.sort();
        std::cout << "Sorted list:" << std::endl;
        lst.show();
    }
    catch(std::exception& e)
    {
        std::cout << e.what() << std::endl;
    }
    system("pause");
    return EXIT_SUCCESS;
}
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
04.08.2010, 00:00     Сортировка ЛОС #12
Nameless One, спасибо, интересно...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.08.2010, 06:14     Сортировка ЛОС
Еще ссылки по теме:

C++ Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом?
Сортировка ЛОС C++
C++ Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется

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

Или воспользуйтесь поиском по форуму:
burst
1 / 1 / 0
Регистрация: 29.04.2010
Сообщений: 13
04.08.2010, 06:14  [ТС]     Сортировка ЛОС #13
Nameless One, спасибо, буду разбираться .... странно еще что в гугле ничего по этому поводу не нашел
Yandex
Объявления
04.08.2010, 06:14     Сортировка ЛОС
Ответ Создать тему
Опции темы

Текущее время: 14:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru